EE Digital Communications

Size: px

Start display at page:

Download "EE Digital Communications"

阿伟施
5 years ago
Views:

1 Principles of Communications Weiyao Lin Shanghai Jiao Tong University Chapter 11: Channel Coding Textbook: Chapter 13.1 ~ /2010 Meixia SJTU 1

2 Homework 5 Ch 12: 12.2, 12.9, 12.15, Ch 13: 13.9, 13.11, 13.13(1)(2)(3), 13.15(1)(2)(3)(4), Homework questions available on ftp://public.sjtu.edu.cn Username: zhangyihao password: public Filename: chapter12_problem.pdf Due: Wednesday (Dec. 26) In class Reminder: Project due next Friday (Dec. 21) by the TA 2009/2010 Meixia SJTU

3 Reminder (1) My PRP project: Title: 多媒体搜索结果可视化与拼贴 o Currently look for students o Plan to look for about 3 students o Each student will do his own work Only one student will do this prp topic Other 1-2 students will do other topics on video and image processing o Basic target: writing papers, creating useful systems, and hopefully some students can continue to pursue master in my group Publish at least one paper on major conferences Try to publish 2 papers before you finish your undergraduate study 2009/2010 Meixia SJTU

4 Reminders (2) Requirements and preference: Good at English reading and understanding (good to read papers) Self-motivated and quick working Strong ability on programming o C (opencv), C++, Matlab o Optional: MFC, JAVA Good at Mathematics 2009/2010 Meixia SJTU

5 Reminders (6) If interested, send your resume to or 简历里可以列出你们比较得意的经历和能力, 此外, 请在简历里包含以下内容 : (1) 对将来本科毕业的打算, 是准备直接出国, 工作, 还是准备继续在交大 ( 特别能在我这里 ) 继续读研究生 (2) 专业 ( 信工, 电科, 计算机, 联读班, 试点班, 联合学院, 等等 ) (3) 平均 GPA, (4) 上过的主要专业课和计算机编程的课的名字和分数 ( 如果上我的通信原理课, 也把通信原理期中考试的分数列一下 ). (5) 熟悉的编程语言和做过的一些主要的 projects. Also welcome to apply my Summer project ( 暑期实习 ) Can be paper writing or doing some projects 2009/2010 Meixia SJTU

6 Topics to be Covered Source A/D converter Source encoder Channel encoder Modulator Absent if source is digital Noise Channel User D/A converter Source decoder Channel decoder Detector Linear block code Convolutional code 2009/2010 Meixia SJTU 6

7 Information Theory and Coding In 1948, Claude Shannon showed that controlled redundancy in digital communications allows transmission at arbitrarily low bit error rate (BER) Error control coding (ECC) uses this controlled redundancy to detect and correct errors How to use error control coding depends on the system requirements (e.g. data, voice, video) and the nature of the channel (e..g wireless, mobile, high interference) The key in error control coding research is to Find a way to add redundancy to the channel so that the receiver can fully utilize that redundancy to detect and correct the errors and to improve the coding gain the effective lowering of the power required 2009/2010 Meixia SJTU 7

8 Example We want to transmit data over a telephone link using a modem under the following conditions Link bandwidth = 3kHz The modem can operate up to the speed of 3600 bits/sec at an error probability Target: transmit the data at rate of 1200 bits/sec at maximum output SNR = 13 db with a probability of error 2009/2010 Meixia SJTU 8

9 Solution: Shannon Theorem For the above communication link, the channel capacity is Since B = 3000 and S/N = 20 (13 db = 10log 10 20) Thus, by Shannon s theorem, we can transmit the data with an arbitrarily small error probability Note that without coding P e = For the given modem, criterion P e = is not met. 2009/2010 Meixia SJTU 9

10 Solution: A Simple Code Design Design a simple code which yields an overall probability of error of 10-4 Possible solution: When b k = 0 or 1, the codeword 000 or 111 is transmitted Based on the received codewords, the decoder attempts to extract the transmitted bits using majority-logic decoding scheme 2009/2010 Meixia SJTU 10

11 Tx bits b k Codewords Rx bits Clearly, the transmitted bits will be recovered correctly as long as no more than one of the bits in the codeword is affected by noise 2009/2010 Meixia SJTU 11

12 With this simple error control coding, the probability of error is 2009/2010 Meixia SJTU 12

13 Channel Coding Coding techniques are classified as either block codes or convolutional codes, depending on the presence or absence of memory A block code has no memory, since it collects and therefore isolate k-bit in a buffer prior to processing The encoder adds n-k redundant bits to the buffered bits. The added bits are algebraically related to the buffered bits The encoded block contains n bits, known as codeword Each output codeword of an (n, k) block code depends only on the current buffer The ratio k/n is known as the code rate. The difference 1-k/n is known as redundancy 2009/2010 Meixia SJTU 13

14 Channel Coding (cont d) A convolutional coder may process one or more buffers during an encoding cycle If the number of sample points (buffers) > 1, a small FIFO is needed to hold them The encoder acts on the serial bit stream as it enters the transmitter Each bit in the output stream is not only dependent on the current bit, but also on those processed previously. This implies a form of memory Performance of a convolutional coder is less sensitive to SNR variations than that of block codes 2009/2010 Meixia SJTU 14

15 11.1 Block Codes An (n,k) block code is a collection of M = 2 k codewords of length n. Each codeword has a block of k information bits followed by a group of r = n-k check bits that are derived from the k information bits in the block preceding the check bits The code is said to be linear if any linear combination of 2 codewords is also a codeword i.e. if c i and c j are codewords, then c i + c j is also a codeword (where the addition is always module-2) 2009/2010 Meixia SJTU 15

16 Code rate (rate efficiency) = Matrix description Each block code can be generated using a Generator Matrix G (dim: ) Given G, then = codeword = message bits codeword message 2009/2010 Meixia SJTU 16

17 I k = identity matrix of order k P = matrix of order, which is selected so that the code will have certain desirable properties 2009/2010 Meixia SJTU 17

18 Systematic Codes The form of G implies that the 1 st k components of any codeword are precisely the information symbols This form of linear encoding is called systematic encoding Systematic-form codes allow easy implementation and quick look-up features for decoding For linear codes, any code is equivalent to a code in systematic form (given the same performance). Thus we can restrict our study to only systematic codes 2009/2010 Meixia SJTU 18

19 Example: Hamming Code A family of (n,k) linear block codes that have the following parameters: Codeword length # of message bits # of parity check bits Capable of providing single-error correction capability 2009/2010 Meixia SJTU 19

20 (7, 4) Hamming Code Consider a (7,4) Hamming code with generator matrix Find all codewords 2009/2010 Meixia SJTU 20

21 Solution Let This example indicates that in general, the encoder must store G (or at least P) and then performs binary arithmetic operations to generate codewords Clearly, the complexity of encoder increases as n increases 2009/2010 Meixia SJTU 21

22 n = 7, k = 4 List of all Codewords message blocks Message codeword /2010 Meixia SJTU 22

23 Parity Check Matrix For each G, it is possible to find a corresponding parity check matrix H H is important since it can be used to verify if a codeword C is generated G Let C be a codeword generated by 2009/2010 Meixia SJTU 23

24 Error Syndrome Received codeword where e = Error vector or Error Pattern it is 1 in every position where data word is in error Example 2009/2010 Meixia SJTU 24

25 Error Syndrome (cont d) = Error Syndrome But 1. If s=0 r = c and m is the 1 st k bits of r 2. If s 0, and s is the j th row of H T 1 error in jth position of r 2009/2010 Meixia SJTU 25

26 Consider the (7,4) Hamming code example So if But if Note that s is the last row of H T Also note error took place in the last bit => Syndrome indicates position of error = Error syndrome s 2009/2010 Meixia SJTU 26

27 Cyclic Codes A code is cyclic if (7,4) Hamming code is cyclic message codeword /2010 Meixia SJTU 27

28 Important Parameters The Hamming Distance between codewords c i and c j is: d(c i, c j ) = # of components at which the 2 codewords differ The Hamming weight of a codeword c i is w(c i ) = # of non-zero components in the codeword The minimum Distance of a code is the minimum Hamming distance between any 2 codewords d min = min d(c i, c j ) for all i j 2009/2010 Meixia SJTU 28

29 The minimum Weight of a code is the minimum of the weights of the codewords except the all-zero codeword w min = min w(c i ) for all c i 0 Theorem: In any linear code, Example: Find d min for (7,4) Hamming code 2009/2010 Meixia SJTU 29

30 Major Classes of Block Codes Repetition Code Hamming Code Golay Code BCH Code Reed-Solomon Codes Walsh Codes BCH and RS codes are the most frequently used 2009/2010 Meixia SJTU 30

31 Soft-Decision and Hard-Decision Decoding Soft-decision decoder operates directly on the decision statistics Hard-decision decoder makes hard decision (0 or 1) on individual bits Here we only focus on hard-decision decoder 2009/2010 Meixia SJTU 31

32 Hard-Decision Decoding Minimum Hamming Distance Decoding Given the received codeword r, choose c which is closest to r in terms of Hamming distance To do so, one can do an exhaustive search too much if n is large. Syndrome Decoding Syndrome testing: with This implies that the corrupted codeword r and the error pattern have the same syndrome A simplified decoding procedure based on the above observation can be used 2009/2010 Meixia SJTU 32

33 Standard Array Let the codewords be denoted as A standard array is constructed as {,,, } c1 c2 K c M Coset leader 2 k Syndrome s 2 n k c c c 1 2 e e c e c e e c e c M M M e e c e c n k n k n k 2 1 M M M M coset 0 s = eh 1 s = e2h M n k T T s = e H 2 1 T Error patterns 2009/2010 Meixia SJTU 33

34 Hard-Decoding Procedure Find the syndrome by r using s=rh T Find the coset corresponding to s by using the standard array Find the cost leader and decode as 2009/2010 Meixia SJTU 34

35 Error Correction Capability A linear block code with a minimum distance d min can Detect up to Correct up to errors in each codeword errors in each codeword t is known as the error correction capability of the code 2009/2010 Meixia SJTU 35

36 Probability of Codeword Error for Hard- Decision Decoding Consider a linear block code (n, k) with an error correcting capability t. The decoder can correct all combination of errors up to and including t errors. Assume that the error probability of each individual coded bit is p and that bit errors occur independently since the channel is memoryless If we send n-bit block, the probability of receiving a specific pattern of m errors and (n-m) correct bits is 2009/2010 Meixia SJTU 36

37 Total number of distinct pattern of n bits with m errors and (n-m) correct bits is So the total probability of receiving a pattern with m errors is Therefore, the codeword error probability is upper-bounded by with equality for perfect codes 2009/2010 Meixia SJTU 37

38 Error Detection vs. Error Correction To detect e bit errors, we have To correct t bit errors, we have d min e+ 1 dmin 2t /2010 Meixia SJTU 38

39 11.2 Convolutional Codes A convolutional code has memory It is described by 3 integers: n, k, and K Maps k bits into n bits using previous (K-1) k bits The n-tuple emitted by the encoder is not only a function of the current input k-tuple, but is also a function of the previous K-1 input k-tuples k/n = Code Rate (information bits/coded bit) K is the constraint length and is a measure of the code memory n does not define a block or codeword length 2009/2010 Meixia SJTU 39

40 Convolutional Encoding A rate k/n convolutional encoder with constraint length K consists of kk-stage shift register and n mod-2 adders At each unit of time: k bits are shifted into the 1 st k stages of the register All bits in the register are shifted k stages to the right The output of the n adders are sequentially sampled to give the coded bits There are n coded bits for each input group of k information or message bits. Hence R = k/n information bits/coded bit is the code rate (k<n) 2009/2010 Meixia SJTU 40

41 Input sequence (shift in k at a time) Encoder Structure (rate k/n, constraint length K) kk kk-stage shift register n n modulo-2 adders Codeword sequence with Typically binary codes with k=1 are used. Hence, we will mainly consider rate 1/n codes = i-th binary code symbol of the branch word U j 2009/2010 Meixia SJTU 41

42 Conv. Codes Representation To describe a convolutional code, we must describe the encoding function that characterizes the relationship between the information sequence m and the output coded sequence U There are 4 popular methods for representation Connection pictorial and connection polynomials (usually for encoder) State diagram Tree diagram Trellis diagram Usually for decoder 2009/2010 Meixia SJTU 42

43 Connection Representation Specify n connection vectors, each of the n mod-2 adders for Each vector has kk dimension and describes the connection of the shift register to the mod-2 adders A 1 in the i th position of the connection vector implies shift register is connected A 0 implies no connection exists 2009/2010 Meixia SJTU 43

44 Example: K = 3, Rate 1/ /2010 Meixia SJTU 44

45 State Diagram Representation The contents of the rightmost K-1 stages (or the previous K-1 bits) are considered the current state => states Knowledge of the current state and the next input is necessary and sufficient to determine the next output and next state For each state, there are only 2 transitions (to the next state) corresponding to the 2 possible input bits The transitions are represented by paths on which we write the output word associated with the state transition A solid line path corresponds to an input bit 0 A dashed line path corresponds to an input bit /2010 Meixia SJTU 45

46 Example: K =3, Rate = 1/2 Input/output 0/00 1/11 a=00 0/11 0/10 b=10 1/00 c=01 1/01 d=11 0/01 1/10 Current State Input Next State Output /2010 Meixia SJTU 46

47 Example Assume that m=11011 is the input followed by K-1 = 2 zeros to flush the register. Also assume that the initial register contents are all zero. Find the output sequence U. Branch word at Output sequence: U = /2010 Meixia SJTU 47

48 Trellis Diagram The trellis diagram is similar to the state diagram, except that it adds the dimension of time The code is represented by a trellis where each trellis branch describes an output word 2009/2010 Meixia SJTU 48

49 Trellis Diagram state a= b= c= d= Trellis structure repeats itself after depth K = /2010 Meixia SJTU 49

50 Every input sequence (m 1,m 2, ) corresponds to a path in the trellis a state transition sequence (s 0,s 1, ), (assume s 0 =0 is fixed), an output sequence ((u 1,u 2 ),(u 3,u 4 ), ) Example: Let s 0 =00, then b 1 b 2 b 3 =000 gives output and states aaaa b 1 b 2 b 3 =100 gives output and states abca b 1 b 2 b 3 a= b=10 c= d= /2010 Meixia SJTU 50

51 We have introduced conv. code Constraint length K and rate R = 1/n Update Polynomials representation State diagram representation Trellis diagram representation We will talk about decoding of convolutional code Maximum Likelihood Decoding Viterbi Algorithm Transfer Function 2009/2010 Meixia SJTU 51

52 Maximum Likelihood Decoding Transmit a coded sequence (correspond to message sequence m) using a digital modulation scheme (e.g. BPSK or QPSK) Received sequence Maximum likelihood decoder Find the sequence such that Will minimize the probability of error if b is equally likely 2009/2010 Meixia SJTU 52

53 Maximum Likelihood Metric Assume a memoryless channel, i.e. noise components are independent. Then, for a rate 1/n code i-th branch of Z Then the problem to find a path (each path defines a codeword) through the trellis such that by taking log Log-likelihood path metric i-th branch metric Log-likelihood of 2009/2010 Meixia SJTU 53

54 Decoding Algorithm: Log-Likelihood For AWGN channel (soft-decision) and P( ) is Gaussian with mean and variance Hence Note that the objective is to compare which Σ i ln(p(z u)) for different u is larger, hence, constant and scaling does not affect the results Then, we let the log-likelihood be and Thus, soft decision ML decoder is to choose the path whose corresponding sequence is at the minimum Euclidean distance to the received sequence 2009/2010 Meixia SJTU 54

55 For binary symmetric channel (hard decision) u 0 1-p 0 p p 1 1-p 1 z p( z u) p = 1 p if if z z = u u LL( z ji u ji ) = ln p( z ji u ji ) ln p = ln(1 p) if if z z ji ji u = u ji i ji (as since p<0.5) Thus Hamming distance between Z and U( m), i.e. they differ in d m positions Hard-Decision ML Decoder = Minimum Hamming Distance Decoder 2009/2010 Meixia SJTU 55

56 Maximum Likelihood Decoding Procedure Compute, for each branch, the branch metric using the output bits associated with that branch and the received symbols Compute, for each valid path through the trellis (a valid codeword sequence ), the sum of the branch metrics along that path The path with the maximum path metric is the decoded path To compare all possible valid paths we need to do exhaustive search or brute-force, not practical as the # of paths grow exponentially as the path length increases The optimum algorithm for solving this problem is the Viterbi decoding algorithm or Viterbi decoder 2009/2010 Meixia SJTU 56

57 Viterbi Decoding (R=1/2, K=3) Input data sequence m: Coded sequence U: Received sequence Z: Branch metric a=00 b=10 c=01 d= /2010 Meixia SJTU 57

58 Basic idea: Viterbi Decoder If any 2 paths in the trellis merge to a single state, one of them can always be eliminated in the search Let cumulative path metric of a given path at t i = sum of the branch metrics along that path up to time t i Consider t 5 The upper path metric is 4, the lower math metric is 1 The upper path metric CANNOT be part of the optimum path since the lower path has a lower metric This is because future output branches depend only on the current state and not the previous state 2009/2010 Meixia SJTU 58

59 Path Metrics for 2 Merging Paths Path metric = 4 a=00 b=10 c=01 d= Path metric = /2010 Meixia SJTU 59

60 Viterbi Decoding At time t i, there are states in the trellis Each state can be entered by means of 2 states Viterbi Decoding consists of computing the metrics for the 2 paths entering each state and eliminating one of them This is done for each of the nodes at time t i The decoder then moves to at time t i+1 and repeats the process 2009/2010 Meixia SJTU 60

61 Example 2009/2010 Meixia SJTU 61

62 2009/2010 Meixia SJTU 62

63 Distance Properties d free = Minimum Free distance = Minimum distance of any pair of arbitrarily long paths that diverge and remerge A code can correct any t channel errors where (this is an approximation) a=00 b=10 c=01 d= /2010 Meixia SJTU

64 Transfer Function The distance properties and the error rate performance of a convolutional code can be obtained from its transfer function Since a convolutional code is linear, the set of Hamming distances of the code sequences generated up to some stages in the trellis, from the all-zero code sequence, is the same as the set of distances of the code sequences with respect to any other code sequence Thus, we assume that the all-zero path is the input to the encoder 2009/2010 Meixia SJTU 64

65 State Diagram Labeled according to distance from all-zero path a=00 b=10 c=01 e=00 input 01 d=11 10 output 10 DNL D m denote m non-zero output bits N if the input bit is non-zero L denote a branch in the path 2009/2010 Meixia SJTU 65

The transfer function T(D,N,L), also called the weight enumerating function of the code is By solving the state equations we get The transfer function indicates that: There is one path at distance 5

66 The transfer function T(D,N,L), also called the weight enumerating function of the code is By solving the state equations we get The transfer function indicates that: There is one path at distance 5 and length 3, which differs in 1 input bit from the correct all-zeros path There are 2 paths at distance 6, one of which is of length 4, the other length 5, and both differ in 2 input bits from all-zero path 2009/2010 Meixia SJTU 66

67 Known Good Convolutional Codes Good convolutional codes can only be found in general by computer search There are listed in tables and classified by their constraint length, code rate, and their generator polynomials or vectors (typically using octal notation). The error-correction capability of a convolutional code increases as n increases or as the code rate decreases. Thus, the channel bandwidth and decoder complexity increases 2009/2010 Meixia SJTU 67

68 Good Codes with Rate 1/2 Constraint Length Generator Polynomials d free 3 (5,7) 5 4 (15,17) 6 5 (23,35) 7 6 (53,75) 8 7 (133,171) 10 8 (247,371) 10 9 (561,753) (1167,1545) /2010 Meixia SJTU 68

69 Good Codes with Rate 1/3 Constraint Length Generator Polynomials d free 3 (5,7,7) 8 4 (13,15,17) 10 5 (25,33,37) 12 6 (47,53,75) 13 7 (133,145,175) 15 8 (225,331,367) 16 9 (557,663,711) (1117,1365,1633) /2010 Meixia SJTU 69

70 Basic Channel Coding for Wideband CDMA BER = 10-3 Block Codes Convolutional Codes Inner coding (conv.) Inner interleaving BER = 10-6 Outer coding (RS) Outer interleaving Inner coding (conv.) Inner interleaving Service-specific coding Convolutional code is rate 1/3 and rate ½, all with constraint length /2010 Meixia SJTU 70

71 Input bits Channel Coding for Wireless LAN (IEEE802.11a) Conv. Encoder r=1/2, K=7 Puncturing Baseband Modulator OFDM TX signals Source: Wireless Networks: The Definitive Guide / by M. Gast / O Reilly 2009/2010 Meixia SJTU 71

72 Other Advanced Channel Coding Turbo codes: Berrou et al 1993 Low-density parity check codes: Robert Gallager 1960 Trellis-coded modulation: Ungerboeck 1982 Space-time coding: Tarokh et al 1998 A family of codes that introduce correlation in both time and space (transmit antenna) dimensions It is a combined result of channel coding, modulation and transmit antenna diversity. 2009/2010 Meixia SJTU 72

Microsoft PowerPoint - STU_EC_Ch08.ppt

Microsoft PowerPoint - STU_EC_Ch08.ppt 樹德科技大學資訊工程系 Chapter 8: Counters Shi-Huang Chen Fall 2010 1 Outline Asynchronous Counter Operation Synchronous Counter Operation Up/Down Synchronous Counters Design of Synchronous Counters Cascaded Counters