CT_EE9樊昌信《通信原理》(第六版)

1、通信原理通信原理电子信息工程学院电子信息工程学院 郎百和郎百和6/15/2021 9:11:38 AM第九第九章章 差差错控制编码错控制编码通信原理通信原理26/15/2021 9:11:38 AM引引 言言p差错控制编差错控制编码信码信道编道编码码n在在数字通信中数字通信中，编，编码可分为码可分为信源编码信源编码和和信道编码信道编码。p信信源编源编码码:u为为了提了提高高有有效效性性和和数数字化字化而采取的编码而采取的编码。p信信道编道编码码:u是是为了降低误码为了降低误码率、提高可率、提高可靠性而采取的编码靠性而采取的编码。n为降低数字通信误码、提高抗为降低数字通信误码、提高抗干扰性干扰性

2、能能u加加大发射功大发射功率率u降降低接收设备本身的噪低接收设备本身的噪声声u合合理选择调制、解调方理选择调制、解调方法、采用均衡、分集技术等法、采用均衡、分集技术等u信信道编码技术道编码技术。36/15/2021 9:11:38 AM引引 言言n按照噪声或干扰的变化规律，可把信道分为三类：按照噪声或干扰的变化规律，可把信道分为三类：随机信道随机信道、突发信道突发信道和和混合信道混合信道。n恒参高斯白噪声信道恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。机的，而且错误之间是统计独立的。n具具有脉冲干扰的信道有脉冲干扰的

3、信道是典型的突发信道，是典型的突发信道， 错误是成串成群出现错误是成串成群出现的，即在短时间内出现大量错误。的，即在短时间内出现大量错误。n短短波信道和对流层散射信道波信道和对流层散射信道是混合信道的典型例子，随机错误是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。同的差错控制方式。 46/15/2021 9:11:38 AM目目 录录p9.1 差错控制编码的基本概念差错控制编码的基本概念p9.2 线性分组码线性分组码p9.3 循环码循环码p9.4 卷积码卷积码p9.5 差错控制编码对系

4、统性能的改善差错控制编码对系统性能的改善p9.6 数字通信系统的应用举数字通信系统的应用举例例56/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念p常用的差错控制方式常用的差错控制方式n前前向纠错（向纠错（FEC: forward error correction）u只只需正向信道，单向传输需正向信道，单向传输，实，实时性时性好；编好；编译码设备复译码设备复杂杂n自动请求重自动请求重发（发（ARQ: automatic repeat request）u译码设备简单，译码设备简单，需需要反馈信道要反馈信道，对，对突发错误和信道干扰较严重时有效，突发错误和

5、信道干扰较严重时有效， 但实时性差但实时性差n混混合纠错（合纠错（HEC:hybrid error correction）u前向纠错方式和检错重发方式的结合与折衷前向纠错方式和检错重发方式的结合与折衷u外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错重发。外层先采用前向纠错，当前向纠错不能解决问题时，内层再采用检错重发。66/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念pFEC方式方式pARQ方式方式pHEC方式方式76/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念p停停发等候重发发等候重发p返

6、返回重发回重发p选选择重发择重发86/15/2021 9:11:38 AM交交换方式分类换方式分类p电路交换电路交换-Circuit Switchingp存储转发交存储转发交换换-Store-and-Forward Switchingn报文交换报文交换-Message Switchingn分组交换分组交换-Packet Switchingu数据数据报交换方式报交换方式 -data message switchingu虚电虚电路交换方式路交换方式 -virtual circuit switching交换虚电路交换虚电路 -Switched Virtual Circuit永久虚电路永久虚电路 -P

7、ermanent Virtual Circuitn快速分组交换快速分组交换- Fast Packet Switchingu帧帧中中继继 -Frame Relayu异步传输模异步传输模式式 -Asynchronous Transfer Mode96/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念p差错控制编码分差错控制编码分类类n根据码的用途，可分为根据码的用途，可分为检错码检错码和和纠错码纠错码。n根据码根据码组组信息元信息元和和监督元监督元的函数关系，可分为线的函数关系，可分为线性码性码和和非线性非线性码码。n根据信息元与码组的记忆关系，可根据信息元

8、与码组的记忆关系，可分分为为无记忆码无记忆码分分组码组码和和有记忆码有记忆码卷卷积码积码。u分分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，息元有关， 而且还与前面若干组的信息元有关。而且还与前面若干组的信息元有关。n分组码循环码分组码循环码BCH码码RS码码uBose-Chaudhuri-Hocquenghem; uReed-Solomon 106/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念p几种简单的检错几种简单的检错码码n1. 奇偶监督码奇偶监督码n编码

9、方编码方法：把法：把信息码元先分组，在每组最后加一位监督码元，信息码元先分组，在每组最后加一位监督码元，使该码组中使该码组中1的数目为奇数或偶的数目为奇数或偶数。数。n奇数时称为奇校验奇数时称为奇校验码码u禁用码组为禁用码组为000，011，101，110u许用码组为许用码组为001，010，100，111n偶偶数时称为偶校验数时称为偶校验码码u许用码组为许用码组为000，011，101，110u禁禁用码组为用码组为001，010，100，11111011 0naaa011 1naaa6/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念n1. 奇偶监督码

10、奇偶监督码n不不满足校验关系，传输一定错误满足校验关系，传输一定错误！满足校验关系，传满足校验关系，传输也不一输也不一定准定准确。确。n奇偶校验只能发现奇数个奇偶校验只能发现奇数个(单个单个)错误，不能检测出偶数个错误。错误，不能检测出偶数个错误。n编编码方法简单且实用性强，适用于检测码方法简单且实用性强，适用于检测随随机机错误错误。n奇奇偶监督码的编码效偶监督码的编码效率率R=n-1/n126/15/2021 9:11:38 AM111112102222121012101210nnnnmmmmnnnnaaaaaaaaaaaacccc9.1 差错控制编码的基本概念差错控制编码的基本概念n2.

11、二维奇偶监督二维奇偶监督码（方阵码）码（方阵码）n检检出所有出所有行和列行和列中的奇数个差错中的奇数个差错 n能能检检出方阵中大出方阵中大多数偶数个差错多数偶数个差错n能够检能够检测突发错测突发错码码136/15/2021 9:11:38 AM9.1 差错控制编码的基本概念差错控制编码的基本概念n3. 重复重复码码u如：如：111，000n4. 恒比恒比码码（定比码、等重码、范德伦码）（定比码、等重码、范德伦码）u从从固定码长的码组中选择那些固定码长的码组中选择那些1和和0的比例恒定的码组作为许用码的比例恒定的码组作为许用码组。组。n中国中国电传通电传通信信采采用用五三定比五三定比码（码（1与

12、与0的比例的比例3 2）u表表示示 10 个阿拉伯数个阿拉伯数字字u每个汉每个汉字以字以4位位十进制数十进制数来表示来表示u许用码组许用码组n国国际电报系统际电报系统七七三定比三定比码（码（ 1与与0的比例的比例3 4 ）u代表代表26个英文字母和一些符号个英文字母和一些符号。u许用码许用码组组14355!103!(53)!C 377!353!(73)!C 6/15/2021 9:11:39 AM9.1 差错控制编码的基本概念差错控制编码的基本概念n5. ISBN国际统一图书编国际统一图书编号号nISBN-1015组区号出版公司图书编号校验码6/15/2021 9:11:39 AM9.1 差错

13、控制编码的基本概念差错控制编码的基本概念n5. ISBN国际统一图书编号国际统一图书编号nISBN-13n本书：本书：978-7-302-15515-7uEANUCC前缀前缀 n校校验验位的计算：位的计算：n1奇数奇数位位 3偶数偶数位位 mod 10nefficacy=10-remainder166/15/2021 9:11:39 AM9.1 差错控制编码的基本概念差错控制编码的基本概念n6.中国居民身份证编中国居民身份证编码码18位位2 2 0 1 0 4 1 9 8 0 0 9 0 1 0 0 1 xn7 9 10 5 8 4 2 1 6 3 7

14、9 10 5 8 4 2n对对应位应位相乘并求相乘并求和和，mod11，求，求remnremainder=0 1 2 3 4 5 6 7 8 9 10nefficacy= 1 0 x 9 8 7 6 5 4 3 2 17地区代码吉林省长春市朝阳区出生日期1980.9.1顺序号男奇数;女偶数效验位6/15/2021 9:11:39 AM9.1 差错控制编码的基本概念差错控制编码的基本概念n检检错与纠错的基本原理错与纠错的基本原理n信息码元信息码元监监督督码元码元，增加信，增加信息的息的冗余冗余度度。n如：如：000、001、010、011、100、101、110、111码全部用码全部用来传来传递

15、信息递信息，无冗余度，无无冗余度，无法检错法检错；n只用只用000、011、101、110用来传递信息用来传递信息可以检一位错可以检一位错，但无法，但无法纠错；纠错；n000、111用来传递信息用来传递信息可以可以检检1位位或或2位位错错，或或可可以以纠纠1位位错码错码。n码码组间的差组间的差异（异（码距码距）决定纠）决定纠检错能检错能力。力。186/15/2021 9:11:39 AM目目 录录p9.1 差错控制编码的基本概念差错控制编码的基本概念p9.2 线性分组码线性分组码p9.3 循环码循环码p9.4 卷积码卷积码p9.5 差错控制编码对系统性能的改善差错控制编码对系统性能的改善p9.

16、6 数字通信系统的应用举数字通信系统的应用举例例196/15/2021 9:11:39 AM9.2 线性分组线性分组码码(linear block codes)p线性分组码线性分组码(n,k) 的基本概念的基本概念n二二进进制时制时n许许用码用码组组有有2k个码字个码字n禁用码禁用码组组有有2n-2k个码个码字字20krn信息码元监督码元6/15/2021 9:11:39 AM9.2 线性分组线性分组码码(linear block codes)p线性分组码线性分组码(n,k) 的基本概念的基本概念n信息码元信息码元监督码元监督码元n监督码元是信息码元的监督码元是信息码元的线性组合线性组合。n具

17、有封具有封闭性，即任意两个许用码组之和（模闭性，即任意两个许用码组之和（模2加），结果仍为加），结果仍为一许用码组一许用码组。n编编码效率码效率n衡量有效性衡量有效性: R=k/nn系系统码统码:信息码元与原码字排列相同，并且与监督码元分开。信息码元与原码字排列相同，并且与监督码元分开。n非系非系统码统码:分组码字中不能直接看出信息码元分组码字中不能直接看出信息码元216/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p线性分组码线性分组码(n,k) 的基本概念的基本概念n码码重重、汉明重量汉明重量(Hamming Weights)n组

18、组码码中非中非零码元的数零码元的数目。目。u如如 10110，w=3。n码距码距、汉汉明距离明距离(Hamming Distance) n两两个个等长码组等长码组之之间对应位间对应位取值不同的数取值不同的数目。目。u如如 11000 与与 10011，d=3。n最小码最小码距距dminn码码组集中组集中任意两个码字任意两个码字之间距离的最小之间距离的最小值。值。n是是衡量码检错、纠错能力的依据衡量码检错、纠错能力的依据 。226/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p最最小码距小码距dmin与检与检错和纠错能力的关错和纠错能力

19、的关系系n若若检测检测e个错误，则要求个错误，则要求dmine+1;n若纠正若纠正t个错误，则要求个错误，则要求dmin2t+1;n若纠正若纠正t个错误，同个错误，同时时检测检测e个错误，则要求个错误，则要求dmint+e+1; ;23e+12t+1t+e+1C1C2C1C2C1C1eettC1C2etC16/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p线性分组码线性分组码(n,k) 的基本概念的基本概念p结论：结论：n用用差错控制编码提高通信系统的可靠性，差错控制编码提高通信系统的可靠性， 是以降低有效性为代是以降低有效性为代价换

20、来的价换来的。线性码的最小码距正好等于非零码的最小线性码的最小码距正好等于非零码的最小码重码重n对对纠错码的基本要求是纠错码的基本要求是:要根据要根据具具体通信系统指体通信系统指标要标要求，求，检检错错和纠错能力尽量强；和纠错能力尽量强； 编码效率尽量高；编码规律尽量简编码效率尽量高；编码规律尽量简单。单。246/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n(7,4)分组分组码码a6 a5 a4 a3 a2 a1 a0n线性关系：线性关系：25信息码元监督码元6543210654321065432101110100011010100

21、10110010aaaaaaaaaaaaaaaaaaaaa 265416530643aaaaaaaaaaaa6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n记为：记为：n简记为简记为nH为为监督矩监督矩阵阵或或校验矩校验矩阵阵260TTHC 0TCH65432101 11010001 101010010110010Taaaaaaa 6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n监监督矩督矩阵阵具有具有H=P Ir形形式式的称的称为为典型监督矩阵典型监督矩阵。n其中其中n

22、H用用来作为来作为判断接收码判断接收码字是字是否出错否出错的依据。的依据。271 1101001 1010101011001rr nr nHPI r kP rr rII6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n(7,4)分组码分组码a6 a5 a4 a3 a2 a1 a0n补补充为下列方充为下列方程组程组n简简记为记为28TTTCG MCM G信息码元监督码元65645342310100001000010*0001111011011011aaaaaaaaaaa66554433265416530643aaaaaaaaaaaaaa

23、aaaaaa6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n称称G为为生成矩生成矩阵阵n可写成可写成G= IK Q形式的矩阵称为形式的矩阵称为典型生成矩典型生成矩阵阵n其其中中nG是用来由信息码字生成分组码字的。是用来由信息码字生成分组码字的。291000111010011000101010001011kk nk nGIQ k rQ kk kII6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n总结：总结：n其中其中nH与与G为正交矩阵为正交矩阵30 TQP TPQ 111

24、knkk nkk rk nCMGMIQ 1110TTTrr nnr knrr nHCPIC 0TGH 0THG kk nk nGIQrr nr nHPI6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p伴伴随式随式(校正子校正子)Sn设发送码组设发送码组C=an-1, an-2 , a1, a0n 接接收码组收码组R=bn-1, bn-2 , b1, b0n错误图样错误图样 E=en-1, en-2 , e1, e0nRC+En伴随式或校正伴随式或校正子子 S=RHTn可获得可获得E-S对照表对照表。310, 1, iiiiibaeb

25、a()TTTTTSRHCE HCHEHEH6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n(7,4)分组码分组码S与与E的对应关系的对应关系 n纠纠错解码过程：错解码过程：n根据根据R，计算，计算S=RHT，由，由S查表得查表得E，n得，得，C=R+E，326/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n【例例】已已知知(6,3)码的生成矩阵为码的生成矩阵为G，求，求：(1) 编码码编码码组及其码组及其码重；重；(2) 最小码最小码距及距及其差错控制能力其差错控制能力。n

26、解：解：33100101010011001110G000000 000001001 110010010 011100101011011 101 010011100100 101001110101101 011110110 110111111 000C6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n信息码组、编码码组及码重信息码组、编码码组及码重如表如表所所示示n非零码组的最小码非零码组的最小码重为重为3 3，所以，所以d dminmin= =3 3n该该码码可可纠纠1 1错错; ;或或检检2 2错错; ;34信息码组信息码组编码码组

27、编码码组码重码重W0 0 00 0 0 0 0 000 0 10 0 1 1 1 030 1 00 1 0 0 1 130 1 10 1 1 1 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 11 1 1 0 0 036/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n【例例】上例中，若上例中，若收收到码组到码组R=1 1 1 0 1 1时，解出对应的信息时，解出对应的信息码组码组D。n由典型由典型G，可得，可得n由由n注注意：意：S111时对应一种时对应一种双错图

28、双错图案案，不代表能纠不代表能纠2位错码位错码35101100011010110001HTSEHESES0 0 0 0 0 00000 0 0 1 0 01001 0 0 0 0 01010 0 0 0 1 00100 1 0 0 0 00110 0 0 0 0 10010 0 1 0 0 01101 0 0 0 1 01116/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n接收码接收码组矢量组矢量R=1 1 1 0 1 1n查查E-S对照表对照表，对应差，对应差错矢错矢量量 E=0 1 0 0 0 0n解码：解码：C=R+E=1 0

29、 1 0 1 1n得得信信息码息码组组 D=1 0 1360 1 1TSRH6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p汉汉明明(Hamming)码码n1950年提出年提出，一，一种种(n,k)线性分组码，并有如下特性：线性分组码，并有如下特性：n(1)码长码长n=2r-1; n(2)信息码长信息码长k=2r-1-r;n(3)监督码长监督码长r=n-k; n(4)最小码距最小码距dmin=3;n(5)纠错能力纠错能力t=1n(6)编编码效码效率率n当当码长码长n很大时，很大时，值接近于值接近于1，但汉明码的不足在于其纠错能，但汉

30、明码的不足在于其纠错能力不力不高高。3721121rrkrrnn 6/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)n(7,4)汉汉明明(Hamming)码码n汉明码汉明码字字381000011010010100101100001111G0111 10010110101101001H00000000 00001000100 10110001000 01111001100 11000010001 11101010101 01010011001 10011011101 00100100010 11001100110 01110101010

31、10111101110 00000110011 00101110111 10010111011 01011111111 1116/15/2021 9:11:39 AM9.2 线性分组码线性分组码(linear block codes)p汉明汉明(Hamming)码码39a6a5a4a3a2a1a0(7,4)编码器6/15/2021 9:11:40 AM9.2 线性分组码线性分组码(linear block codes)p汉明汉明(Hamming)码码40(7,4)译码器a6a5a4a3再编码器3-8译码器Y7Y6Y5Y4Y3Y2Y1Y0ABCa2a1a0a6a5a4a3误码指示6/15/202

32、1 9:11:40 AM目目 录录p9.1 差错控制编码的基本概念差错控制编码的基本概念p9.2 线性分组码线性分组码p9.3 循环码循环码p9.4 卷积码卷积码p9.5 差错控制编码对系统性能的改善差错控制编码对系统性能的改善p9.6 数字通信系统的应用举数字通信系统的应用举例例416/15/2021 9:11:40 AM9.3 循环循环码码(Cyclic Code)n循环循环码码(Cyclic Code)属于属于分分组组码码n有有系统循环码系统循环码；非系统循环码非系统循环码n具具有有封闭性封闭性，循循环性环性，即一许用码组经循环移位后得到另一个，即一许用码组经循环移位后得到另一个许用码组

33、许用码组。n循循环码环码码码字多项字多项式式C(x)nC(x)=cn-1xn-1+cn-2xn-2+c1x+c0n循环循环码码码码字矢量字矢量C(0)nC(0)=cn-1,cn-2,c1,c0426/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n循环码码字矢量循环码码字矢量的的循环移位循环移位nxC(x)= x(cn-1xn-1+cn-2xn-2+c1x+c0)n = cn-1xn+cn-2xn-1+c1x2+c0 xn = cn-2xn-1+c1x2+c0 x+ cn-1 (模模xn+1)n记为：记为：nC(1)=cn-2,cn-3,c0,cn-1nC(

34、0)=cn-1,cn-2,c1,c0n模模xn+1相当于相当于xn+1=0；xn=1436/15/2021 9:11:40 AM(7,4)(7,4)系统循环码：系统循环码：g(x)=xg(x)=x3 3+x+1+x+144信息码字信息码字循环码字循环码字码字多项式码字多项式g(x)g(x)的倍式的倍式倍式编码倍式编码00000000 00000000000010001 011x3+x+11000100100010 110 x4+x2+xx001000110011 101x4+x3+x2+1x+1001101000100 111x5+x2+x+1x2+1010101010101 100 x5+x

35、3+x2x2010001100110 001x5+x4+1x2+x+1011101110111 010 x5+x4+x3+xx2+x011010001000 101x6+x2+1x3+x+1101110011001 110 x6+x3+x2+xx3+x101010101010 011x6+x4+x+1x3+1100110111011 000 x6+x4+x3x3100011001100 010 x6+x5+xx3+x2+x111011011101 001x6+x5+x3+1x3+x2+x+1111111101110 100 x6+x5+x4+x2x3+x2110011111111 111x6+

36、x5+x4+x3+x2+x+1x3+x2+111016/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n(7,4)系统循环码的编码及码字多项式系统循环码的编码及码字多项式如如上上表表n可可以看出：每个码字的循环移位仍然属于这个码组。以看出：每个码字的循环移位仍然属于这个码组。n并不是说并不是说码组是由码组是由一个码字一个码字的循环移位构成的的循环移位构成的，上表上表中中是由四是由四个码字的循环移位构成的。个码字的循环移位构成的。n系系统统循环循环码码n非系统非系统循环循环码码n循循环环码码的的生成多项式生成多项式： g(x)=x3+x+1n循环码的循环码的生

37、成矩阵生成矩阵456/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p循循环码环码的生成多项的生成多项式式定义定义n在一个在一个(n,k)循环码中，循环码中，有且仅有一个有且仅有一个次数为次数为n-k=r的码字多项的码字多项式，记为式，记为：g(x)=xr+gr-1xr-1+g1x+1n每每个码字多项式都是个码字多项式都是g(x)的倍式；每个次的倍式；每个次数数n-1的的g(x)的倍式必的倍式必为一个码字多项式为一个码字多项式。n这时称这时称g(x)的的(n,k)码的生成多项式。码的生成多项式。n上上例可例可见，见，g(x)=x3+x+1为为(7,4)循环码

38、的生成多项式循环码的生成多项式。466/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p循环码循环码的生成多项的生成多项式式性质性质n生成多项式生成多项式是是循环码循环码C中次数最低的非零码字多项式，并且是中次数最低的非零码字多项式，并且是唯一的，其次数为唯一的，其次数为r=n-k。n令令g(x)=xr+gr-1xr-1+g1x+g0为一个为一个(n,k)循环码循环码C中最低次数中最低次数码字多项式，则其常数项必为码字多项式，则其常数项必为g0=1。n(n,k)循环码的生成多项式循环码的生成多项式g(x)是是xn+1的因式。的因式。n由由本原多项式构成的码称

39、为本原多项式构成的码称为本本原循环码原循环码。476/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p非系统循环码的编码方法非系统循环码的编码方法：nC(x)=m(x)g(x)n【例例】n(7,4)循环码，循环码，g(x)=x3+x+1n若，若，m=1101; C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1n得：得：C=1111111n若，若，m=0101; nC=01011011=0100111486/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic

40、 Code)p非系统循非系统循环码的生成矩阵环码的生成矩阵：n其中其中n非非标准型生成矩标准型生成矩阵阵4912( )( )( )( )( )kkxg xxg xG xxg xg x1110( )rrrrg xg xgxg xg110110110110000000000n kn kn kn kn kn kn kn kggggggggGgggggggg 01; 1rgg6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p非系统循非系统循环码的生成矩阵环码的生成矩阵：n由由非非标准型生成矩标准型生成矩阵阵转换为典转换为典型型生成矩生成矩阵阵:u经经列列换位换位；

41、u经经初初等行变换等行变换；u经经列换列换位位初初等行变换等行变换；506/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n【例例】 (7,3)循环循环码的码的非系统循环码非系统循环码的生成的生成矩矩阵阵nn=7, k=3, r=4,n非非标标准型准型生生成矩阵成矩阵51432( )1g xxxx65422543432( )( )( )( )1xxxxx g xG xxg xxxxxg xxxx3 71110100011 1010001 1101G6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n【例例】已已知知(7,4

42、)循环码的生成多项式为循环码的生成多项式为g(x)=x3+x+1，n非非标准型生成矩标准型生成矩阵：阵：n只使用初等行变只使用初等行变换换; 使用使用列换位初等行变换列换位初等行变换;n可知可知典型典型生生成矩阵是成矩阵是不唯一不唯一的的。5236432532423( )( )( )( )( )1x g xxxxx g xxxxG xxg xxxxg xxx1011000010110000101100001011G1000101010011100101100001011G1000111010010100101100001011G6/15/2021 9:11:40 AM9.3 循环码循环码(Cy

43、clic Code)p非系统循环码的非系统循环码的监督矩阵监督矩阵：n监督多项式监督多项式n其其中，中，n其中，其中，n为互逆多项式为互逆多项式5311101( )( )nkkkkxh xh xhxh xhg x1*( )( )*( )*( )n kxhxH xxhxhx 120121*( )kkkkkhxh xh xh xhxh011011011011000000000kkkkkkkkhhhhhhhhHhhhhhhhh01; 1khh6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p非系统循环码的非系统循环码的监督矩阵监督矩阵：n由由非标准型非标准型监督

44、监督矩阵矩阵转换为转换为标准型标准型监督监督矩阵矩阵:u经经列列换位换位；u经经初初等行变换等行变换；u经经列换列换位位初初等行变换等行变换；546/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n【例例】(7,4)循环码的生成多项式循环码的生成多项式g(x)=x3+x+1，而监督多项式，而监督多项式为为h(x)=x4+x2+x+1。n可可以验证以验证：n由由非标准非标准型型监督监督矩矩阵阵转换为转换为标准标准型型监督监督矩矩阵阵:551011000010110000101100001011G1110100011 1010001 1101H 0TGH11 1

45、010001 110101101001H6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系统循环码的编码方法系统循环码的编码方法：n1. 信息码元左移：信息码元左移：xn-km(x)n2. 求监督码元：求监督码元：r(x)=remxn-km(x)/g(x)n3. 得系统循环码：得系统循环码：C(x)= xn-km(x) r(x)uremainder: 余余数，余式，余项数，余式，余项 566/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系统循环码的编码方法系统循环码的编码方法：n【例例】n(7,4)循环码的生成多项

46、式为循环码的生成多项式为g(x)=x3+x+1，求，求m=1010的循环码的循环码。n解解：nm(x)=x3+x, xn-k=x3; nxn-km(x)=x3(x3+x)=x6+x4n r(x)=x+1n C(x)=xn-km(x)+r(x)=x6+x4+x+1nC=1010 011576/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系系统循环码的生成矩阵统循环码的生成矩阵：n生成多项式生成多项式的标准型为的标准型为：n其其中：中：nr1(x)=remxn-1/g(x)nr2(x)=remxn-2/g(x)nrk(x)=remxn-k/g(x)58 11

47、22nnn kkxr xxrxG xxrx6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系系统循环码的生成矩统循环码的生成矩阵与监督矩阵阵与监督矩阵：n生成矩阵生成矩阵标准标准型为：型为：nr1 r2 rk分别为分别为r1(x)、r2(x)rk(x)的向量形式的向量形式nr1(x)=remxn-1/g(x)nr2(x)=remxn-2/g(x)nrk(x)=remxn-k/g(x)59 12100010001krrGr6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n【例例】二二元元(7,4)循环循环码码g(x)=

48、x3+x+1标准标准生生成矩成矩阵阵nr1(x)=remxn-1/g(x)=remx6/g(x) =x2+1; nr1=101。nr2(x)=remxn-2/g(x)=remx5/g(x) =x2+x+1 ; nr2=111。nr3(x)=remxn-3/g(x)=remx4/g(x) = x2+x ; nr3=110。nr4(x)=remxn-4/g(x)=remx3/g(x) = x+1 ; nr4=011。n技巧：可以由低到高一次技巧：可以由低到高一次求求解。解。606/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)n生生成矩阵的标准型成矩阵的标准型为

49、为：n由由于于H=P Ir; G=IK Q; Q=PT; P=QTn监监督矩阵的标准型为：督矩阵的标准型为：611000101010011100101100001011G11 1010001 110101101001H6/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p非系统循环码编码电路非系统循环码编码电路n(7,4)汉明汉明码，码，g(x)= x3+x+1nC(x)=m(x)g(x)626/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系系统循环码编码电路统循环码编码电路n(7,4)汉明汉明码，码，g(x)=x3+x

50、+1nC(x)= xn-km(x) remxn-km(x)/g(x)636/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系统循环码编码电路系统循环码编码电路nm=1001, C=1001 110的编码过程如的编码过程如下：下：64时钟时钟信息码字信息码字D D0 0D D1 1D D2 2输出码字输出码字C C00001111012001103000104111015011160011700006/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p系统循环码编码电路系统循环码编码电路n寄寄存器的初始状态存器的初始状态为为

51、0，门，门1开，门开，门2关关。nm3,m2,m1,m0 一一方面通过或门输出，另一方面送入除法电路。方面通过或门输出，另一方面送入除法电路。在除法电路的右端输入在除法电路的右端输入m(x)相当于完成了相当于完成了循环循环移位移位n-k=3位位。n四四次移位后，信息码元已输出，形成了系统循环码的前四位信次移位后，信息码元已输出，形成了系统循环码的前四位信息位。同时寄存器中存放的就是余式多项式的系数，从右到左息位。同时寄存器中存放的就是余式多项式的系数，从右到左分别是分别是(c2,c1,c0)。n门门1关，关，门门2开，经三次移位开，经三次移位， (c2,c1,c0)输输出出。n门门1开，门开，

52、门2关，进行关，进行第二个码字第二个码字的编码的编码。656/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p线性分组码的译码线性分组码的译码n线线性分组性分组码的码的译码大体分为两类译码大体分为两类：u频频域译码域译码u时时域译域译码码666/15/2021 9:11:40 AM9.3 循环码循环码(Cyclic Code)p时时域译码域译码：n一一类类是利用码字的代数结构进行译码，称为是利用码字的代数结构进行译码，称为代数译码代数译码。u捕获（错）译码，大数逻辑译码捕获（错）译码，大数逻辑译码n另另一类不仅利用代数结构，而且还利用信道干扰统计特性等概一类

53、不仅利用代数结构，而且还利用信道干扰统计特性等概率理论，称为率理论，称为概率译码概率译码。u最最大后验概率（大后验概率（MAP）译码）译码u最大似然（最大似然（ML）译码）译码u最小汉明距离译码最小汉明距离译码uViterbi译码译码u硬判决译码硬判决译码：汉：汉明距离明距离最小准最小准则则u软判决译码软判决译码：欧几里德距离（几何距离）：欧几里德距离（几何距离）最最小小准准则则nAWGN信道，信道，软软判决译码判决译码比比硬判决译码硬判决译码多多1.52dB增增益益n衰衰落信道，落信道，软判决译软判决译码码增益更高增益更高676/15/2021 9:11:40 AM9.3 循环码循环码(Cy

54、clic Code)p循环循环码码的译码的译码n接收码字接收码字r(x)计算出校验子计算出校验子n错错误图样识别误图样识别器器通过查表通过查表法，由校验子得到法，由校验子得到e(x)n正确的译码输出正确的译码输出c(x)=r(x)+e(x)686/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)p梅吉特梅吉特(Meggit)译码器译码器696/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)n开始译码开始译码时时,门门打打开开,移移位寄存位寄存器器为为全全0。收到的码。收到的码字字为为R(x)=r6x6+r0 由高次到低由高次

55、到低次输次输入到入到7级缓存器和除法电级缓存器和除法电路路,7次移位次移位后后,缓缓存器存入整个码字，除法电路存器存入整个码字，除法电路S(x)=E(x)/g(x), E(x)=x6得到校验子得到校验子S0=s2,s1,s0。这时门关上进行译码。这时门关上进行译码。n如如果果S0(x)=x6=x2+1mod g(x)，这时，这时101识别电路输出为识别电路输出为1，表，表明明r6为有错为有错。n译译码器继续移位，通过码器继续移位，通过101识别电路可以将识别电路可以将r6位的错误纠正位的错误纠正。n在纠错的同时，在纠错的同时，101识别电路的输出又反馈到除法电路的输入识别电路的输出又反馈到除法

56、电路的输入端，以消除错误码元对除法电路的下一个校验子计算的影响。端，以消除错误码元对除法电路的下一个校验子计算的影响。n校校验子产生电路开始在无输入的情况下移位，输入验子产生电路开始在无输入的情况下移位，输入R(x)第第7次次移位后产生了校验子移位后产生了校验子S0，第，第8次移位时对次移位时对r6进行纠正，同时将进行纠正，同时将101识别电路的输出的识别电路的输出的1输入到除法电路的输入端，结果使除输入到除法电路的输入端，结果使除法电路的寄存器状态为法电路的寄存器状态为000，消除了，消除了e6的影响的影响。706/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Co

57、de)p大数逻辑译码器大数逻辑译码器(门限译码器门限译码器)716/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)n由由(7,3)循环码生成多项式循环码生成多项式g(x)=x4+x3+x2+1的除法电路，计算的除法电路，计算R(x)的校验子多项式的校验子多项式S(x)。n=7次移位后得到校验子次移位后得到校验子(s0,s1,s2,s3)，存存于于校校验子移位寄存器中，此时，验子移位寄存器中，此时，R(x)已全部进入已全部进入7级缓存器级缓存器中。中。n停止译码器输停止译码器输入，并开入，并开始检始检查查A1=s3,A2=s1,A3=s2+s0中中1的个数。的

58、个数。如果如果1的个数为的个数为3，大数门输出，大数门输出1。此时，缓存器移位一次，输。此时，缓存器移位一次，输出出r6，对它进行纠错，如果，对它进行纠错，如果1的个数小于的个数小于3，大数门无输出，大数门无输出，r6直接输出。直接输出。n除除法电路循环移位一次，对法电路循环移位一次，对r5进行检查，此时校验子寄存器中进行检查，此时校验子寄存器中的内容是对的内容是对r5的计算结果。如果大数门输出的计算结果。如果大数门输出1，则对，则对r5进行纠错，进行纠错，否则，否则，r5直接输出直接输出。726/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)n重复上述步骤

59、，直至重复上述步骤，直至n=7次为止；次为止；n第第n=7次移位完毕后，如果校验子除法电路的状态为全次移位完毕后，如果校验子除法电路的状态为全0，则说，则说明明R(x)中的错误是可以纠正的，否则说明是不可纠正的中的错误是可以纠正的，否则说明是不可纠正的。n若若是不可纠正的，译码器送出一个信号至用户，表示是不可纠正的，译码器送出一个信号至用户，表示R(x)有误。有误。然后重新清洗译码器的初始状态，准备接收第二各码字。然后重新清洗译码器的初始状态，准备接收第二各码字。n图图中的虚线是把大数门输出的中的虚线是把大数门输出的1反馈到除法电路的输入端，以反馈到除法电路的输入端，以消除该错误码元对除法电路

60、的影响消除该错误码元对除法电路的影响。736/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)p捕错译码捕错译码748级缓存器7级缓存器门1门5门2门3门4W(Si(x)2检测电路R(x)C (x)6/15/2021 9:11:41 AM9.3 循环码循环码(Cyclic Code)n适应于纠突发错误适应于纠突发错误码码n若若接收码字接收码字R(x)对应的校验子多项式为对应的校验子多项式为S0(x)，经过，经过i次循环移位次循环移位后，后，xiR(x)=Ri(x)对应的校验子多项式为对应的校验子多项式为Si(x)。n一一旦检测出旦检测出Si(x)的重量的重量W