Coding and Error Control

Presentation on theme: "Coding and Error Control"— Presentation transcript:

1 Coding and Error Control
张宝贤：无线网络技术课程——2006年10月14日 Coding and Error Control 差错控制编码也称信道编码 Chapter 8

2 差错控制的基本概念 数据传输误码率：数据比特在传输过程中的差错概率
线性PCM: 10-7; 压扩PCM: 10-5 ; ADPCM: 10-4 如何才能降低传输误码率呢？ 加大传输功率：但在有些系统中不太适用，如手持终端系统中无限制地加大电池重量是不可接受的 采用分集(diversity)技术以对抗信号衰落(signal fading) 空间分集：采用两个或以上分得足够开的天线进行信号接收 频率分集：采用两个频率传输同样的信息比特——如前面说 过的快跳频技术 时间分集：同样的信息在不同的时间传输多次 采用全双工传输——即：同时双向数据传输 发送端沿一个信道向接收节点发送信息 接收节点沿另外一个反馈信道将收到的信息发回给发送节点 如果发送端发现错误，则重传数据 需要的带宽是单向（单工）传输的两倍——在频谱利用方面通常是不可接受的

3 差错控制的基本概念(续) ARQ (自动反馈重传：automatic repeat request)，主要有以下两种典型技术
停等模式(stop and wait) 连续ARQ (Continuous ARQ) Go-Back-N mode 收到NAK (Negative ACKnowledge) 或超时的分组，那么该分组及其以后的分组都要重传 Selective repeat 只重传收到NAK或超时的那些分组分组 选择性重传模式带宽利用效率高但需要的存储空间大 实现ARQ必须有差错检测码字的配合！ 检测分组在传输过程中是否出现差错 纠错码，或称前向纠错码(FEC: forward correction codes)——适合比特差错率(BER: Bit Error Rate)高的环境中 Designed to detect and correct errors

4 门限现象 比特误码率BER Eb：每比特 数据能量 图8.6显示FEC可以降低比特误码率
Eb/N0 (dB) 图8.6显示FEC可以降低比特误码率 - 如图中，当BER=10-6时，FEC带来2.77 dB增益 而未编码的传输方式的比特差错率为>10-3 另外：如果Eb/N0低于某一门限（在本图中为5 .4dB)，编码带来副效应——即：升高了误码率

5 差错控制的应用 Reed-Solomon码 通信应用 应用于光盘数据存贮中可以有效对抗突发差错 也用于计算机中的数据存贮和提取
移动无线通信系统（如GSM)中广泛应用 视听系统中常常采用FEC 因为视听数据时延要求比较严格 用于空间应用(Aerospace applications)的控制与通信系统

6 Error Detection Probabilities
Definitions Pb : Probability of single bit error (BER) P1 : Probability that a frame arrives with no bit errors P2 : While using error detection, the probability that a frame arrives with one or more undetected errors（也称剩余差错率) P3 : While using error detection, the probability that a frame arrives with one or more detected bit errors but no undetected bit errors

7 Error Detection Probabilities
With no error detection （如果没有差错检测技术的话） F = Number of bits per frame 帧越长，单个帧中比特数越多，整个帧中包含差错 位的概率越高

8 差错率计算一例 如果单个比特差错率为0.01,那么传送一个10比特的码字中出现0、1、2个比特差错的概率。假定各比特之间出现传送差错是相互独立的 单个比特成功接收的概率是1-0.01=0.99 无差错概率P( 0个差错) =(0.99)10 = 单比特差错概率P( 1个差错) =(0.01)1(0.99)9 10= 两比特差错概率P( 2个差错) =(0.01)2(0.99)8 C102 = 存在3个及以上差错的概率为 =

9 差错控制码大全 《数字通信》- Glover & Grant　 error=1

10 Error Detection Process
Transmitter For a given frame, an error-detecting code (check bits) is calculated from data bits Check bits are appended to data bits Receiver Separates incoming frame into data bits and check bits Calculates check bits from received data bits Compares calculated check bits against received check bits Detected error occurs if mismatch

11 Error Detection Process
Sender 合法码字总数2k Receiver

12 Parity Check (奇偶校验） As an option in ASCII coded data transmission
Parity bit appended to a block of data 码长度 n = k + 1 Even parity (能检查出来奇数个错） Added bit ensures an even number of 1s Odd parity (能检查出来奇数个错） Added bit ensures an odd number of 1s Example, 7-bit character [ ] Even parity [ ] Odd parity [ ] 应对突发差错(burst error)能力较差

13 Parity Check (Cont’d) 二维行列奇偶校验 n2 k2 Row checks k1 n1 Collumn checks
Checks on checks

14 Parity Check (Cont’d) Modulo-(2n-1) checksums 常用于网络连接中的差错检测
如在Internet协议消息的checksum计算中， 　将一个消息看成是长度１６比特为单位的字节的组合, 　消息:mw-1,…,m0 校验: 的反码 原始消息和计算出来的校验同时传输以使收端可以 进行差错检测

15 循环码 循环码的特征 符合(n,k)线性分组码特征 任何(n,k)码字连续位移i位后仍然是一个合法码字
线性分组码: 任意两个合法码字之和仍然是一个合法码字 (n,k)码字指一个码字由k位数据和n-k位校验位组成 任何(n,k)码字连续位移i位后仍然是一个合法码字

16 Cyclic Redundancy Check (CRC) (循环冗余校验)
易于电路实现编解码 检查到出错的分组/帧, 利用ARQ方式重传 Transmitter For a k-bit block, transmitter generates an (n-k)-bit frame check sequence (FCS) Resulting frame of n bits is exactly divisible by predetermined number Receiver Divides incoming frame by predetermined number If no remainder, assumes no error

17 CRC using Modulo 2 Arithmetic
模２运算就是无进位的２进制加法，它恰好就是异或(XOR)运算 模2加和模2减等价

18 CRC using Modulo 2 Arithmetic
Exclusive-OR (XOR) operation Parameters: T = n-bit frame to be transmitted D = k-bit block of data; the first k bits of T F = (n–k)-bit FCS; the last (n – k) bits of T P = pattern of n–k+1 bits; this is the predetermined divisor　（除数:长度n-k+1比特）…可以称之为样式 Q = Quotient (商） R = Remainder（余数）

19 CRC using Modulo 2 Arithmetic
For T/P to have no remainder, start with Divide 2n-kD by P gives quotient and remainder Use remainder as FCS(将余数作为FCS) 待传序列

20 CRC using Modulo 2 Arithmetic
Does R cause T/P have no remainder? Substituting, No remainder, so T is exactly divisible by P

21 CRC using Polynomials All values expressed as polynomials
例8.4: D= , 那么D(X) = X9 +X7 + X3+X2+1, 生成多项式P(X)= X5 +X4 + X2+1. 那么计算结果R(X) = X3+X2+X 具体过程见下页

22 CRC 一例 * **

23 CRC using Polynomials Widely used versions of P(X) (也称生成多项式) CRC–12
X12 + X11 + X3 + X2 + X + 1 CRC–16 X16 + X15 + X2 + 1 CRC – CCITT X16 + X12 + X5 + 1 CRC – 32 X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1

24 CRC using Digital Logic
Dividing circuit consisting of: XOR gates Up to n – k XOR gates Presence of a gate corresponds to the presence of a term in the divisor polynomial P(X) A shift register String of 1-bit storage devices Register contains n – k bits, equal to the length of the FCS

25 Digital Logic CRC

26 Wireless Transmission Errors
Error detection requires retransmission Detection inadequate for wireless applications Error rate on wireless link can be high, results in a large number of retransmissions Long propagation delay compared to transmission time 如卫星链路 常用的重传策略是重传出错帧及其以后的所有帧 Go-back-N ARQ, as explained later in details

27 Block Error Correction Codes
Transmitter Forward error correction (FEC) encoder maps each k-bit block into an n-bit block codeword Codeword is transmitted; analog for wireless transmission Receiver Incoming signal is demodulated Block passed through an FEC decoder

28 Forward Error Correction Process

29 FEC Decoder Outcomes Four possible outcomes as follows
No errors present Codeword produced by decoder matches original codeword Decoder detects and corrects bit errors Decoder detects but cannot correct bit errors; reports uncorrectable error Decoder detects no bit errors, though errors are present

30 Block Code Principles Hamming distance (汉明距离,或称海明距离) – for two n-bit binary sequences, the number of different bits E.g., v1=011011; v2=110001; d(v1, v2)=3 Minimal Hamming distance Dmin (最小汉明距离) 所有可能码字对间汉明距离最小值, 对于四个5位码字00000,00111,11100,11011来说最小汉明距离为3 最小汉明距离表征了一个block code的总体性能 线形分组码的最小汉明距离只考虑每个码和全零码字距离即可 纠错检错能力 纠错能力: t = 检错能力: Dmin-1 给定 n 和 k, Dmin越大,纠错检错能力越强 n-k 越小越好——降低开销，提高利用率 n-k 越大越好——降低差错率 Redundancy – ratio of redundant bits to data bits Code rate – ratio of data bits to total bits: k/n Coding gain – the reduction in the required Eb/N0 to achieve a specified BER of an error-correcting coded system 两者相互矛盾

31 Block Code Principles Nearest neighbor decoding of block codes
理论基础: 产生t个差错的概率大大高于产生t+1个错误的概率 - 见前面的例子 codewords 00000 11100 00111 11011 Single-bit error correctable pattern 10000 01000 00100 00010 00001 01100 10100 11000 11110 11101 10111 01111 00011 00101 00110 01011 10011 11111 11001 11010 double-bit error detectable pattern 10001 10010 01101 01110 10110 10101 01010 01001 最后一行中的码字都和两个可能的码字等距离, 无法纠正，因而只能检错,无法就错

32 Hamming Code Hamming Code is easy to analyze but is rarely used
Designed to correct single bit errors Family of (n, k) block error-correcting codes with parameters: Block length: n = 2m – 1 Number of data bits: k = 2m – m – 1 Number of check bits: n – k = m Minimum distance: dmin = 3 Single-error-correcting (SEC) code SEC double-error-detecting (SEC-DED) code，与SEC码相比较而言多一个额外的对整个码块的校验位

33 Hamming Code Process Encoding: k data bits + (n -k) check bits
Decoding: compares received (n -k) bits with calculated (n -k) bits using XOR Resulting (n -k) bits called syndrome word Syndrome range is between 0 and 2(n-k)-1 Each bit of syndrome indicates a match (0) or conflict (1) in that bit position (即：症候码的值表示的就是出差错的比特的位置）

34 汉明码——举例 例8.7 8比特数据为: 校验码为: 0111

35 汉明码——举例 校验码的位置在:1, 2, 4, …, 2n-k

36 汉明码——举例

37 Cyclic Codes Can be encoded and decoded using linear feedback shift registers (LFSRs) For cyclic codes, a valid codeword (c0, c1, …, cn-1), shifted right one bit, is also a valid codeword (cn-1, c0, …, cn-2) Takes fixed-length input (k) and produces fixed-length check code (n-k) In contrast, CRC error-detecting code accepts arbitrary length input for fixed-length check code

38 Cyclic Codes 传送码字T(X)=Xn-kD(X)+C(X)
如果没有差错发生的话,receiver收到的码字能够被生成多项式P(X)整除,余数为0 如果发生差错的话,receiver收到的码为Z(X) =T(X) +E(X), E(X)是n-bit差错多项式,发生差错的比特位系数为1 Z(X)/P(X)=T(X)/P(X)+E(X)/P(X)=S(X) 由于前一项T(X)/P(X)余数为0,所以症候码S(X)仅取决于差错多项式E(X) Receiver端: 用收到的n比特码字除以P(X), 得到的余数(如果不为0的话)就是症候码(syndrome codes),通过症候码查表就可以得知那一位或那些位发生差错

39 BCH Codes (Bose-Chaudhuri-Hocquengham)
For positive pair of integers m and t, a (n, k) BCH code has parameters: Block length: n = 2m – 1 Number of check bits: n – k  mt Minimum distance: dmin  2t + 1 Correct combinations of t or fewer errors Flexibility in choice of parameters Block length, code rate

40 BCH Codes (Bose-Chaudhuri-Hocquengham)

41 Reed-Solomon Codes Subclass of non-binary BCH codes
Data processed in chunks of m bits, called symbols An (n, k) RS code has parameters: Symbol length: m bits per symbol Block length: n = 2m – 1 symbols = m(2m – 1) bits Data length: k symbols Size of check code: n – k = 2t symbols = m(2t) bits Minimum distance: dmin = 2t + 1 symbols

42 Block Interleaving Data written to and read from memory in different orders Data bits and corresponding check bits are interspersed with bits from other blocks At receiver, data are deinterleaved to recover original order A burst error that may occur is spread out over a number of blocks, making error correction possible

43 Block Interleaving

44 Convolutional Codes （卷积码）
Generates redundant bits continuously Error checking and correcting carried out continuously (n, k, K) code Input processes k bits at a time Output produces n bits for every k input bits, code rate: k/n K = constraint factor k and n generally very small…in most cases, k=1 n-bit output of (n, k, K) code depends on: Current block of k input bits Previous K-1 blocks of k input bits

45 Convolutional Encoder
例:比如前两个比特是10 (un-1=1, un-2=0) 而接下来的比特un=1, 那么当前处在状态 b 下一个状态将是d(11). 而输出是 Vn1 =unun-1un-2 = 011=0 vn2= un un = 01 =1 Convolutional Encoder 状态指历史状态,即（un-1,un-2）的值

46 从状态a开始是因为寄存器的初态总是全零

47 Decoding Trellis diagram – expanded encoder diagram
Viterbi code – error correction algorithm Compares received sequence with all possible transmitted sequences Algorithm chooses path through trellis whose coded sequence differs from received sequence in the fewest number of places (汉明距离最小) Once a valid path is selected as the correct path, the decoder can recover the input data bits from the output code bits

48 Viterbi算法 Distance of a path =(distance of the last edge)
+ (distance of the last-but-one state) 对于一个(n,k,K)码字和一个解码窗口b,下面的步骤可以解出第一个输出块中的n比特, 0时刻网格图的状态为0 时刻i+1, 找到到达每个状态S的路径 (或路径集合)——采用第一行给出的式子。并以路径的距离标记S 算法在时刻b终止。若此时所有的active路径的第一条边相同，那么那条边的标记x0x1x2…xn-1就是我们要找的第一码块w0w1w2…wn-1.如果第一条边不唯一，那么差错不可纠正。

49 采用图8.9中的编码器, 粗实线表示活跃路径(active path) 接收序列为10 01 01 00 10 11 00…,解码窗口b=7
则无法成功解码 01 10 11

50 Automatic Repeat Request
Mechanism used in data link control and transport protocols Relies on use of an error detection code (such as CRC) Flow Control Error Control

51 Flow Control Assures that transmitting entity does not overwhelm a receiving entity with data Protocols with flow control mechanism allow multiple PDUs (协议数据单元) in transit at the same time PDUs arrive in same order they’re sent Sliding-window （滑动窗口） flow control Transmitter maintains list (window) of sequence numbers allowed to send Receiver maintains list allowed to receive

52 Flow Control Reasons for breaking up a block of data before transmitting: Limited buffer size of receiver Retransmission of PDU due to error requires smaller amounts of data to be retransmitted On shared medium, larger PDUs occupy medium for extended period, causing delays at other sending stations

53 Flow Control

54

55 Error Control Mechanisms to detect and correct transmission errors
Types of errors: Lost PDU : a PDU fails to arrive Damaged PDU : PDU arrives with errors

56 Error Control Requirements
Error detection Receiver detects errors and discards PDUs Positive acknowledgement Destination returns acknowledgment of received, error-free PDUs Retransmission after timeout Source retransmits unacknowledged PDU Negative acknowledgement and retransmission Destination returns negative acknowledgment to PDUs in error

57 Go-back-N ARQ Acknowledgments Contingencies （可能发生的意外事件）
RR = receive ready (no errors occur) REJ = reject (error detected) Contingencies （可能发生的意外事件） Damaged PDU Damaged RR Damaged REJ

58

59 作业 For P(X)=X5+X4+X+1 and D=11100011, 求CRC （给出过程）
Consider a convolutional encoder defined by (vn1=unun-1) and (un2=un-1un-2) Draw a shift register implementation for this encoder similar to Figure 8.9(a) Draw a Trellis diagram for this encoder similar to Figure 8.10 For the encoder of the above problem, assume that the shift register is initialized to all zeros and that after the transmission of the last information bit, two zero bits are transmitted Why are the two extra (all-zero) bits are needed? 假定信息输入为 ，那么编码后的输出比特流是什么？ (最左边的比特是最先输入到编码器的比特）