四信道编码(1)

1、 信道编码信道编码 分组码分组码(1)(1) Efficiency vs. Reliability Efficiency Average code length as small as possible Reliability The ability to recover from errors in the transmissionCodingDecodingInformation sourceSourcecodingChannelcodingInformationchannelChanneldecodingSourcedecodingDestination 提提 要要 概述概述-纠错码与差

2、错控制方式纠错码与差错控制方式 信道编码的一般原理信道编码的一般原理 几种简单实用的编码几种简单实用的编码 汉明码汉明码 线性分组码及其描述线性分组码及其描述 循环码及其编译码循环码及其编译码 BCH码与码与RS码简介码简介 卷积码的编码及卷积码的编码及Viterbi译码算法译码算法 交织码交织码, TCM, 级连码及级连码及Turbo码码 线性分组码线性分组码 Linear Block Codes戴书第5章 1 概述概述什么是信道编码（什么是信道编码（channel coding）? 差错控制编码（差错控制编码（error-control coding）- 信道编码又称为信道编码又称为差错控

3、制编码差错控制编码，简称为，简称为纠错编码纠错编码，即在信息序列中按一，即在信息序列中按一定的规则附加若干监督码元，以便对信息传输（或存储）定的规则附加若干监督码元，以便对信息传输（或存储）起检错与纠错作用，目的在于起检错与纠错作用，目的在于提高通信（或存储）的可提高通信（或存储）的可靠性，减低靠性，减低误误码率误误码率。 纠错码为什么具有纠检错能力？纠错码为什么具有纠检错能力？- 引入了冗（多）余度引入了冗（多）余度 多余度多余度可靠性可靠性 信息传输速率信息传输速率 （或带宽（或带宽 ） 有效性有效性 冗余度冗余度=1/3 差错控制能力与什么因素关？差错控制能力与什么因素关？ 编码规则（包

4、括码及码参数的选择）编码规则（包括码及码参数的选择） 差错控制方式差错控制方式 译码方法译码方法 不同信道宜采用不同的编码方案不同信道宜采用不同的编码方案 信道的分类信道的分类-随机干扰信道，突发干扰信道，混合信道随机干扰信道，突发干扰信道，混合信道差错控制方式（差错控制方式（error-control schemes）：）： 前向纠错（前向纠错（FEC） 自动请求重传（自动请求重传（ARQ）(1)自动请求重传自动请求重传（Automatic Repeat Request-ARQ）重发指令重发指令发端重发发端重发。 ARQ: 收端（检错）发现误码收端（检错）发现误码通过反馈信道向发端发出通过反

5、馈信道向发端发出 ARQ一般分为三种类型三种类型：等待等待ARQ，退，退N步步ARQ，选择，选择ARQ。 等待等待ARQStop-And-Wait ARQ (SAW ARQ)Transmitting Data1323TimeReceived Data1 23TimeACKACKNAKOutput Data123TimeErrorRetransmissionACK: AcknowledgeNAK: Negative ACK 退退N步步ARQGo-Back-N ARQ (GBN ARQ)Transmitting Data1TimeReceived DataNAKOutput DataTimeErr

6、orGo-back 32 3 4 5 3 4 4 5 6 7 51Time2 3 4 4 5ErrorNAKGo-back 51 23 4 45 选择选择ARQSelective-Repeat ARQ (SR ARQ)Transmitting Data1TimeReceived DataNAKErrorRetransmission2 3 4 5 3 6 7 8 9 71Time2 4 3 6 8 7ErrorNAKRetransmission59Buffer1Time24 3 68 759Output Data1Time24 368 759（2）前向纠错（）前向纠错（FEC-Forward E

7、rror Correction）:收端不仅收端不仅能检错，而且能自动纠错，故能检错，而且能自动纠错，故实时性能好，传输效率高，无实时性能好，传输效率高，无须反馈信道须反馈信道。（3）混合）混合ARQ（混合纠错法）：（混合纠错法）：FEC+ARQ 发生少量误码时，收端能自动纠正，超出其纠错能力时，发生少量误码时，收端能自动纠正，超出其纠错能力时，则要求重传，故传输效率与可靠性都可以做得很高。则要求重传，故传输效率与可靠性都可以做得很高。纠错码的分类：纠错码的分类：应用：应用： 通信（深空通信、卫星通信、移动通信、光纤通信、数据通通信（深空通信、卫星通信、移动通信、光纤通信、数据通信，信，Cabl

8、e Modem, ADSL Modem等）。等）。 计算机计算机: 计算机网络（计算机网络（LANs, MANs, WANs, Internet）；）； 软件检测；软件检测； 磁盘磁盘/光盘纠错；内存纠错；光盘纠错；内存纠错； 数字电视、数字广播、数字电视、数字广播、DVB、DAB； CD、DVD等等 2 信道编码的一般原理信道编码的一般原理如何通过增加冗余度来实现纠、检错？如何通过增加冗余度来实现纠、检错？例例1 气象台预报天气气象台预报天气 信码信码 监督元监督元 码字码字 （偶校验）传输中错一位（偶校验）传输中错一位 晴晴 00 0 （000）100，010，001 云云 01 1 （0

9、11） 111，001，010 阴阴 10 1 （101） 001，111，100 雨雨 11 0 （110） 010，100，111 许用码字许用码字 禁用码组禁用码组 可检一位错，之所以能检错，是因为引入了可检一位错，之所以能检错，是因为引入了冗余（禁用码组）冗余（禁用码组）例例2 附加两个监督元，设只有附加两个监督元，设只有“晴晴”、“雨雨”两种信息两种信息 信码信码 监督元监督元 码字码字 传输中错一位传输中错一位 晴晴 0 00 （000）100，010，001 0 雨雨 1 11 （111） 011，101，110 1 可纠可纠1位错位错若若传输中错传输中错2位位 ，（，（000）

10、110，011，101 （111） 001，010，100 可检查出可检查出2位错。位错。上述例子说明：上述例子说明： 附加监督元可实现检（纠错），监督元越多，码的纠、检错能力越强。附加监督元可实现检（纠错），监督元越多，码的纠、检错能力越强。 为了提高纠、检错能力，必须有为了提高纠、检错能力，必须有适当的适当的编译码规则。编译码规则。例如，在例例如，在例2中，若编码规则为中，若编码规则为 晴晴 011， 雨雨 000， 则无纠错能力。当发生则无纠错能力。当发生1位错时：位错时：（011）111，001，010（000） 001，100，010则不能纠则不能纠1位错，但仍能检位错，但仍能检1位

11、错。位错。分组码及其纠检错能力分组码及其纠检错能力 （1）分组码及其描述）分组码及其描述定义定义把消息序列分成等长的组（每组把消息序列分成等长的组（每组k个信息码元），每个信息码元），每 组再附加若干（组再附加若干（r=n-k）个监督元，从而构成）个监督元，从而构成n=k+r长的长的码字，这种编码方法就叫做分组编码，所有码字的集合码字，这种编码方法就叫做分组编码，所有码字的集合便构成一个便构成一个(n, k)分组码分组码。 最小距离最小距离d0决定码的纠、检错能力（2）汉明距离）汉明距离d与最小距离与最小距离d0 重量重量：一个码组中非：一个码组中非“0”位的数目，例如，位的数目，例如，010

12、11， w=3 汉明距离汉明距离：两个码组中对应位数值不同的位数，用：两个码组中对应位数值不同的位数，用d表示，表示， 例如，例如， 000和和111， d=3描述分组码的几个参数：描述分组码的几个参数： 码长码长n 信息长信息长k 码率码率（编码效率）：（编码效率）：R=k/n 对于线性码对于线性码，最小距离就等于最小重量最小距离就等于最小重量。（3）纠、检错能力与最小距离）纠、检错能力与最小距离d0之间的关系之间的关系 (n, k, d0)分组码的纠检错能力分组码的纠检错能力：10 de 个错误个错误； 只用于纠错只用于纠错(FEC)，能纠正，能纠正210dt个错误个错误； 用于既纠用于既

13、纠t个错，又检个错，又检e个错（个错（te） (混合混合ARQ)10dte 最小（汉明）距离最小（汉明）距离：一个码中汉明距离的最小数值，用：一个码中汉明距离的最小数值，用d0表示表示. 设一个码由设一个码由4个码字组成，它们分别是个码字组成，它们分别是000，011，101，110， 其重量分别是其重量分别是0，2，2，2，最小距离为，最小距离为2。 只用于检错只用于检错(ARQ)：能检出：能检出 A 只检只检e个错个错B 只纠只纠t个错个错AB10 de210dt几何解释几何解释：C 检检e个错，同时纠个错，同时纠t个错个错(tC2E 1(R)E 2 (R) P1P2 C一定，一定，n一定

14、，一定，R E(R) P R一定，一定，C一定，一定，n P eApRnE)(降低错误概率的方法：降低错误概率的方法： 增大信道容量增大信道容量C（增加带宽（增加带宽W，或增大平均功率，或增大平均功率S）；）； R一定时，可增大码长一定时，可增大码长n; n一定时，可降低码率一定时，可降低码率R。例例3 将一个二进制信源（将一个二进制信源（0、1随机产生）接到一个错误转移随机产生）接到一个错误转移概率为概率为0.1的二元对称信道（的二元对称信道（BSC）上，若不用信道编码，误）上，若不用信道编码，误码率便为码率便为0.1, 现以码长为现以码长为4， 码率为码率为1/2进行分组编码，试观进行分组

15、编码，试观察其编码效果察其编码效果。解：因解：因n=4, R=1/2, 故故k=2, 构成（构成（4，2）分组码）分组码 设码字设码字C=（C3， C2， C1， C0），且编码规则为），且编码规则为1111 0110 1000 0001 41100 0101 1011 0010 1010 0011 1101 0100 )( 0110 1111 0001 1000 1110 0111 1001 0000 11 01 10 00 0123 2323021位错第冗余禁用码组CCCCCCCCCCC假设在前三位中只发生一位错，第四位无错，假设在前三位中只发生一位错，第四位无错，879. 0)1 (3)

16、1 (34pppQ设译码后码元正确概率为设译码后码元正确概率为pc, 则则pcQ2037.0,2/1,6063.011可进一步降到则误比特率仍保持为增大到若将码长为译码后码元错误的概率RnQppcb正确译码概率正确译码概率： 复习思考题复习思考题信道编码的作用是什么？纠错码为什么具有信道编码的作用是什么？纠错码为什么具有纠检错能力？纠检错能力？差错控制方式通常有哪几类？其原理是什么？差错控制方式通常有哪几类？其原理是什么？各有什么优缺点？各有什么优缺点？信道编码的理论依据是什么？要降低误比特信道编码的理论依据是什么？要降低误比特率，可采用哪几种措施？率，可采用哪几种措施？4 4 说明说明(n,

17、 k, d(n, k, d0 0) )分组码具有怎样的纠检错能分组码具有怎样的纠检错能力。力。 3 几种简单的实用编码几种简单的实用编码 奇偶校验码奇偶校验码 二维奇偶校验码字二维奇偶校验码字 定比码定比码 重复码重复码奇偶校验码奇偶校验码：是一种只有一个监督元的是一种只有一个监督元的(n, n-1)分组码，在分组码，在奇校验码中，码字中奇校验码中，码字中“1”的数目为奇数；而在偶校验码中，的数目为奇数；而在偶校验码中，码字中码字中“1”的数目为偶数。的数目为偶数。（1）编码规则）编码规则：1021 aaann 偶校验码偶校验码 ：0021 aaann 奇校验码奇校验码 ：解：解： 天气 代码

18、 偶检验码 奇校验码 晴 00 000 001 云 01 011 010 阴 10 101 100 雨 11 110 111（2）检错能力：）检错能力： 能检出能检出奇数奇数个个错误，但不能检出偶数个错误错误，但不能检出偶数个错误。例例4 将晴、云、阴、雨这四种天气状况分别编成奇检验与偶校将晴、云、阴、雨这四种天气状况分别编成奇检验与偶校验码。验码。例例5 设信息序列为设信息序列为00000，分别将其编为偶检验码与奇检验码，分别将其编为偶检验码与奇检验码，当差错序列分别为当差错序列分别为101100和和011000时，判断其是否能检错。时，判断其是否能检错。（3）不可检错误概率）不可检错误概率

19、(不要求不要求)：解：解： 偶校验：偶校验： 发送码字为发送码字为000000 当差错序列为当差错序列为101100时，接收码组为时，接收码组为101100，可检；，可检； 当差错序列为当差错序列为011000时，接收码组为时，接收码组为011000，不可检；，不可检； 奇校验：奇校验： 发送码字为发送码字为000001 当差错序列为当差错序列为101100时，接收码组为时，接收码组为101101，可检；，可检； 当差错序列为当差错序列为011000时，接收码组为时，接收码组为011001，不可检；，不可检；对于对于BSC一个一个n长码字在长码字在BSC上传输，发生上传输，发生m位错误的概率为

20、位错误的概率为nmmmmnmmnppmnmnmpppmnmnmppppmpnwennc1) 1( )!( !)()!( !)(1)1 ()(概率为不编码时总的码字错误时可简单估算为当 采用奇偶校验码后采用奇偶校验码后 nmmppmnmnmppnwe. 4 , 2) 1( )!( !)(例如，当例如，当n=4, 104p时时，若不用编码，则若不用编码，则104)4()3()2()1 (44444pppppwe采用编码后采用编码后10)4()2(744pppwe奇偶校验码奇偶校验码-适用于随机错误信道，采用适用于随机错误信道，采用ARQ进行检错。进行检错。二维奇偶检验码（水平垂直检验码，方阵码）二

21、维奇偶检验码（水平垂直检验码，方阵码） （1）编码规则）编码规则：把信息序列排成一个阵列，然后分别将每：把信息序列排成一个阵列，然后分别将每行每列编成奇偶校验码。发送时，按顺序逐列发送；接收行每列编成奇偶校验码。发送时，按顺序逐列发送；接收后，再逐行逐列检测。后，再逐行逐列检测。（2）码率）码率：mnnmNk) 1)(1(（3）检错能力）检错能力：能检出行（列）中奇数个错误；能检出行（列）中奇数个错误； 能检出部分偶数个错误；能检出部分偶数个错误； 能检出长度小于等于能检出长度小于等于m(行数行数)的突发错误；的突发错误； 恰好位于矩形恰好位于矩形4个角上的错误无法检出。个角上的错误无法检出。

22、（4）适用范围）适用范围：突发错误信道或混合信道（采用：突发错误信道或混合信道（采用ARQ）。例例 中文电报中文电报汉字汉字4位阿拉伯数字位阿拉伯数字每位用一个每位用一个5中取中取3码的码字来表示码的码字来表示数字数字 码字码字 数字式数字式 码字码字 1 01011 6 10101 2 11001 7 11100 3 10110 8 01110 4 11010 9 10011 5 00111 0 01101 每个码字中每个码字中“1”的数目是固定的，即的数目是固定的，即“1”与与“0”数目之数目之比为一定值，故称为定比码。在数学上又称为比为一定值，故称为定比码。在数学上又称为“n中取中取m码

23、码”。（1 1）常用定比码：）常用定比码：5 5中取中取3 3码（用于中文电报），码（用于中文电报），7 7中取中取4 4码码3 定比码定比码 五 邑 大 学 0063 6712 1129 133101101 01101 10101 10110 10101 11100 01011 1100101011 01011 11001 10011 01011 10110 10110 010111035ccmn码字总数（2 2）编码效率：）编码效率：nRcmn2log对于对于5中取中取3码，码，检错能力：可检出所有检错能力：可检出所有奇数个奇数个错误和错误和部分偶数个部分偶数个错误错误；不可检错误概率：不

24、可检错误概率： 不能检出的情况不能检出的情况 “1”“0”，“0”“1”成对出现，其中，成对出现，其中，出现一对的概率最大，两对以上概率较小，可忽略，因而只须出现一对的概率最大，两对以上概率较小，可忽略，因而只须估算出现一对时的情况。估算出现一对时的情况。mppcm1一个码字中有一个码字中有n-m个个0，故，故0变成变成1的概率为的概率为pmnpcmn)(1所以，定比码的不可检错误概率可近似为所以，定比码的不可检错误概率可近似为pmnmpmnmppwe)()(2一个码字中有一个码字中有m个个1，故，故1变成变成0的概率为的概率为（3）检错能力与不可检查错误概率）检错能力与不可检查错误概率(不要

25、求推导不要求推导)例如，例如，5中取中取3码，若码，若103p，则，则106)10()35(3632wep 若不用定比码，则若不用定比码，则5中错中错1个以上错就会发生差错，故错个以上错就会发生差错，故错误概率为误概率为105315552515 ccccwep（4）用途：用于电传机，或键盘产生的电码。）用途：用于电传机，或键盘产生的电码。重复码重复码：是一种最简单的纠错码，是一种最简单的纠错码，(n, k)=(n, 1)，n为奇数，为奇数，监督元是信息元的简单重复，用大数判决法译码监督元是信息元的简单重复，用大数判决法译码, 可纠正不可纠正不多于多于(n-1)/2个错误。个错误。 例如，例如，

26、n=5, 信元符号信元符号0和和1分别编为分别编为00000和和11111，在通过，在通过BSC传输，设信道转移概率传输，设信道转移概率p1/2, 当收到当收到01001时，因时，因0的数的数目比目比1多，故译成多，故译成0, 反之，译成反之，译成1。 4 汉明码汉明码 0021 aaann校正子校正子： 1 如何构造纠一位错的高效如何构造纠一位错的高效(n, k)码码?奇偶检验码：奇偶检验码： 0 1021无错有错 aaasnn一个监督元，一个监督元， 得到一个校正子，只能表示有错与无错；得到一个校正子，只能表示有错与无错； 两个监督元，得到两个校正子，共两个监督元，得到两个校正子，共4种状

27、态，可表示有错及种状态，可表示有错及3个错位，即个错位，即个错位可表示无错及种状态共为监督元3 ,11,10,01,004211,0 12120211ssaaaaasaaasnnnn 同理，同理，r个监督元个监督元 得到得到r个校正字，共个校正字，共 种状态种状态 一种表一种表示无错，其余的表示示无错，其余的表示 个错位个错位 可构造一个可构造一个 ，k=n-r k=n-r 纠一位错的纠一位错的(n, k)分组码，当等号成立分组码，当等号成立时效率最高。时效率最高。因此，要构造一个纠一位错的因此，要构造一个纠一位错的(n, k)码，须满足码，须满足12rkr其中，其中，k为信息长，为信息长，r

28、为监督元的数目为监督元的数目，n = k + r 。2 如何得到如何得到r个监督关系式？个监督关系式？例例6 试设计一个试设计一个k=4, 纠一位错的高效纠一位错的高效(n, k)分组码。分组码。 取取r = 3，等号成立，等号成立，k 最大，故效率最高，为（最大，故效率最高，为（7,4）码。）码。解解设编出的码字为设编出的码字为c = (a6 a5 a4 a3 a2 a1 a0)，其中，其中a6 a5 a4 a3 为信息元为信息元，a2 a1 a0 为监督元。为监督元。 构造构造3 3个监督方程，将得到个监督方程，将得到S S1 1 S S2 2 S S3 3 的的8 8种不同状态，将其与种

29、不同状态，将其与错误状态的对应关系列表，再按列读出，便可写出监督关系式错误状态的对应关系列表，再按列读出，便可写出监督关系式034611356224563aaaasaaaasaaaas编码时须满足编码时须满足S1=S2=S3=0， 即即000034613562456aaaaaaaaaaaa故编码规则为故编码规则为346035614562aaaaaaaaaaaa 111 110 101 011 100 010 001 000 SSS6543210 32 1 aaaaaaa无错错位例例7 设待编码的信息组为设待编码的信息组为)0001()(3456aaaa则则1 1, , 0012aaa)0001

30、011()(0123456aaaaaaac 经传输后若接收码组为（经传输后若接收码组为（0000011），将其代入方），将其代入方程组，得程组，得110034631356224561aaaasaaaasaaaas 查表，知错在查表，知错在a3位，取反，译得码字为（位，取反，译得码字为（0001011），），即信息组为（即信息组为（0001）。）。这就是著名的（这就是著名的（7，4）汉明码）汉明码。3（n, k）汉明码的描述）汉明码的描述 12nrrkr1230d 码率码率： nrnkR1码字错误概率：码字错误概率：pCppCpiniinpininiinwe212)1 ( 码参数码参数：汉明码是一种完备码（汉明码是一种完备码（perfect code）(不要求不要求) )12(2222rkknk禁用码组数个许用码字数 其中，落在球心的为码字，其余为禁用码组；其中，落在球心的为码字，其余为禁用码组；接收码组中发生接收码组中发生1tc个错误个错误禁用码组；禁用码组；以每个码字为球心，以以每个码字为球心，以 为半径作球，共为半径作球，共 禁用码