无线网络课件wireless comm信道编码6小时

1、1Wireless Communications Channel codingWireless Signal Processing & Networks Lab (WSPN)BUPTXing Zhang 2Error detection and correctionError happens due to Channel outagerandom noisesInterferencesHow to detect such error events?Can we make it up when error happens?RetransmitError correction3Retransmis

2、sionAutomatic repeat request (ARQ)Retransmit the data when an error is detected.How to detect an error event?messageCheck bitsredundant bitsBuild up relationships between message and check bits.At the receiver, checking the relationship between message and check bits.A transmission error event could

3、 be detected.4Error checking codeParity check codeCyclic redundancy code10111000Even parity check bitTotal number of “1” is even1011100CRC bits5CRC: exampleGenerator: Message: 10110010Message polynomial: 10110010 1100Encoded message by CRC6Error probability after retransmissionsAssume that the error

4、 happens independently with a probability of p for each transmission, the probability that requires m retransmissions is pm(1-p).The error probability decreases quickly as the number of retransmission increases.7Error correctionDrawbacks of ARQNeeds a feedback channelA whole block data will be repea

5、ted even only one bit error!Error correctionCorrect the error directly from the received data.Take advantage of redundancy bitsRedundancy bits are used to indicate an error pattern, which errors could be corrected directly.8Error correctionExample: Lets consider a simple repeat code, where “0” is en

6、coded as “000” and “1” is encoded as “111”. The decoder calculates the number of “1” of the received codeword and makes a decision.The decision rule is as follows: if the number of “1” is not less than 2, then “1” is claimed; else “0” is claimed.If one bit error happens during the transmission, the

7、error could be corrected by the above decision rule.9Error correction codeGiven k bits to be transmitted, how to encode them into n bits efficiently and obtain certain error correction ability?A code needs to beBandwidth efficiencydecodable with low complexity10Error correction codeBlock codeHamming

8、 codeBCH RSLow density parity check (LDPC)Convolutional code (CC)ConcatenatedTurboRS+CC11Fundamentals of Block codesDistance of two codewordsNumber of different elementsExample: 000110 and 100101, d=2Minimum distance of a code dminWeight of a codewordNumber of nonzero elementsExample: 100100s weight

9、=2(n,k) block codeK bitsn bits12Operations on the field(2)0+0=0 0*0=00+1=1 0*1=01+0=1 1*0=01+1=0 1*1=110111 =1000013Linear block codeAn encoder maps k-bit-message x into n-bit-codeword f(x).A linear block code means that such mapping is linear, which satisfiesf(a*x1+b*x2)=a*f(x1)+b*f(x2)Example: If

10、f(1000)= 1000110, f(0100)=0100011Then f(1100)= 1100101 A linear code A can be represented asHA=0Where H is a matrix with k rows and n columns.14线性分组码的基本性质线性分组码的码字的集合C对加法封闭，即若c1,c2C,则c1+c2 C全零序列是线性分组码中的一个码字线性分组码中任意两个不同码字间汉明距离的最小值称为码组的最小距离除全零码外，码字的最小重量称为码组的最小重量线性分组码各码字之间的最小距离等于某非零码字的最小汉明重量线性分组码例：(5,1)

11、重复码将k=1个比特重复n=5遍C中有两个码字：11111和00000码距是5，可纠正2位错编码率是1/5线性分组码例：(4,3)偶校验码给k=3个信息比特后缀n-k=1个校验比特，使码字中有偶数个1全部码字有8个：0000 0011 0101 01101001 1010 1100 1111编码率是3/4最小码距是2，可以检出所有奇数位错线性分组码例：(7,4)汉明码(7,4)汉明码给4个信息比特u3u2u1u0后缀3个校验比特p2p1p0校验规则：全部2k=16个码字：00000000001110001011100110010100101010101101100100111100100001

12、11001101101010010110101100110110100011100011111111码率是4/7最小码距是3，可以纠正1位错生成矩阵写成矩阵形式生成矩阵线性分组码是把k维的信息向量u通过线性变换G扩张成n维的c。通过这种扩张使码距扩大G的一些性质G有k行n列每个码字是G的各行的线性组合G的每一行是一个码字G的各行线性无关注意：给定C时， G不唯一21Linear block codeExample: (7,4) Hamming codeWith matrix H asThe Hamming code is A: HA=022The solution of HA=03 equat

13、ions，7 unknowns, 4 free degrees (4 input bits)G: generating matrix23The (7,4) linear block code(0000 000) (0001 011) (0010 101) (0011 110)(0100 110) (0101 101) (0110 011) (0111 000)(1000 111) (1001 100) (1010 010) (1011 001)(1100 001) (1101 010) (1110 100) (1111 111)(7,4) block code4 bits7 bitsCode

14、rate: R=k/n=4/724(7,4) Linear block codeAll the codewords A satisfy HA=0.If A is wrongly received, HA will not be 0.Assume only one bit error happens, the error bit position could be anywhere.Lets denote an error vector e=1000000 to indicate an error happens in the position a6, the received codeword

15、C=A+eSince every HA=0, we have HC=He=S. S is called error pattern vector. S=H0000001=0 0 1S=H0000010=0 1 0S=H0000100=1 0 0 S=H0001000=0 1 1S=H0010000=1 0 1S=H0100000=1 1 0S=H1000000=1 1 1Error bits position is a0Error bits position is a1Error bits position is a2Error bits position is a3Error bits po

16、sition is a4Error bits position is a5Error bits position is a625Cyclic codeLinearCyclicEach codewords cyclic shifts is still a codeword.(000,111) is a cyclic codeEach codeword can be generated by a generator polynomial g(x).26Cyclic code (example)Example: consider a (7,4) code with generator g(x)=x3

17、+x2+1, the corresponding cyclic codes generating matrix G is27Cyclic code (example)A=UGwhere28Cyclic code (example)Codewords:0001101, 0010111, 0011010, 01000110101110, 0110100, 0111001, 10001101001011, 1010001, 1011100, 11001011101000, 1110010, 1111111, 000000029Convolutional codeC1=m0+m1+m2C2=m0+m230Convolutional codeState(m1m2) diagram: a(00), b(10), c(01), d(11) Inputs: 1 0 1 1 1 1 0Outputs: 11 01 01 00 01 10 01 31Convolutional codeRepresent the structureExample: g1(x)=1+x+