信息论与编码理论-信道编码-线性分组码2剖析课件.ppt

1、第六章 信道编码2022/12/11 To choose time is to save time第六章 信道编码2022/12/126.2.1 一般概念一般概念6.2.2 一致监督方程和一致监督矩阵一致监督方程和一致监督矩阵6.2.3 线性分组码的生成矩阵线性分组码的生成矩阵6.2.4 线性分组码的编码线性分组码的编码6.2.5 线性分组码的最小距离、检错和纠错能力线性分组码的最小距离、检错和纠错能力6.2.6 线性分组码的译码线性分组码的译码6.2.7 线性分组码的性能线性分组码的性能6.2.8 汉明码汉明码6.2.9 由已知码构造新码的方法由已知码构造新码的方法6.2.10 线性分组码的

2、码限线性分组码的码限6.2 线性分组码线性分组码第六章 信道编码2022/12/13(2)纠错译码纠错译码 最佳译码准则（最大似然译码）最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于对于FEC方式，采用纠错码后的码字差错概率为方式，采用纠错码后的码字差错概率为pwe，p(C C)：发送码字：发送码字C C 的先验概率的先验概率p(C C/R R)：后验概率：后验概率若码字数为若码字数为 2k，对充分随机的消息源有，对充分随机的消息源有p(C C)=1/2k，所以最小化的，所以最小化的pwe等价为最

3、小化等价为最小化p(C CC CR R)，又等价为最大化，又等价为最大化p(C C=C CR R)；)()(RCCCpppwe6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/14对于对于 BSC 信道：最大化的信道：最大化的 p(C C=C CR R)等价于最大化的等价于最大化的 p(R RC C)，最大化的最大化的p(R RC C)又等价于最小化又等价于最小化 d(R R,C C)，所以使差错概率最小，所以使差错概率最小的译码是使接收向量的译码是使接收向量 R R 与输出码字与输出码字 C C 距离最小的译码。距离最小的译码。),(),(min:CRCRCCddi

4、i6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/15 标准阵列标准阵列码矢参数码矢参数发送码矢：取自于发送码矢：取自于 2k 个码字集合个码字集合C C；接收矢量：可以是接收矢量：可以是 2n 个个 n 重中任一个矢量。重中任一个矢量。译码方法译码方法把把 2n 个个 n 重重划分为划分为 2k 个互不相交的子集个互不相交的子集 ，使，使得在每个子集中仅含一个码矢；得在每个子集中仅含一个码矢；根据码矢和子集间一一对应关系，若接收矢量根据码矢和子集间一一对应关系，若接收矢量 R Rl 落在子集落在子集 D Dl中，就把中，就把 R Rl 译为子集译为子集 D Dl

5、含有的码字含有的码字 C Cl；当接收矢量当接收矢量 R R 与实际发送码矢在同一子集中时，译码就是正确与实际发送码矢在同一子集中时，译码就是正确的。的。标准阵列标准阵列：是对给定的：是对给定的(n,k)线性码，将线性码，将 2n 个个 n 重划分重划分为为 2k 个子集的一种方法。个子集的一种方法。6.2.6 线性分组码的译码线性分组码的译码k221,DDD第六章 信道编码2022/12/16标准阵列构造方法标准阵列构造方法先将先将 2k 个码矢排成一行，作为个码矢排成一行，作为标准阵列标准阵列的第一行，并将全的第一行，并将全0码矢码矢C C1=(000)放在最左面的位置上；放在最左面的位置

6、上；然后在剩下的然后在剩下的(2n2k)个个 n 重中选取一个重量最轻的重中选取一个重量最轻的 n 重重 E E2 放在放在全全0码矢码矢 C C1 下面，再将下面，再将 E E2 分别和码矢分别和码矢 相加，放在相加，放在对应码矢下面构成阵列第二行；对应码矢下面构成阵列第二行；在第二次剩下的在第二次剩下的 n 重中，选取重量最轻的重中，选取重量最轻的 n 重重 E E3，放在，放在 E E2 下面，下面，并将并将 E E3 分别加到第一行各码矢上，得到第三行；分别加到第一行各码矢上，得到第三行；，继续这样做下去，直到全部，继续这样做下去，直到全部 n 重用完为止。得到表重用完为止。得到表6.

7、2.2所示所示的给定的给定(n,k)线性码的标准阵列。线性码的标准阵列。6.2.6 线性分组码的译码线性分组码的译码k232,CCC第六章 信道编码2022/12/176.2.6 线性分组码的译码k2C22ECk32ECkknk22ECkni2ECkn22ECkn2E第六章 信道编码2022/12/18标准阵列的特性标准阵列的特性定理定理6.2.5：在标准阵列的同一行中没有相同的矢量，而且在标准阵列的同一行中没有相同的矢量，而且 2n 个个 n 重中任一个重中任一个 n 重在阵列中出现一次且仅出现一次。重在阵列中出现一次且仅出现一次。证明证明：L因为阵列中任一行都是由所选出某一因为阵列中任一行

8、都是由所选出某一 n 重重分别与分别与 2k 个码矢相个码矢相加构成的，而加构成的，而 2k 个码矢互不相同，它们与所选矢量的和也不个码矢互不相同，它们与所选矢量的和也不可能相同，所以在同一行中没有相同的矢量；可能相同，所以在同一行中没有相同的矢量；L在构造标准阵列时，是用完全部在构造标准阵列时，是用完全部 n 重为止，因而每个重为止，因而每个 n 重必重必出现一次；出现一次；L每个每个n重只能出现一次。重只能出现一次。假定某一假定某一 n 重重 X X 出现在第出现在第 l 行第行第 i 列，那么列，那么 X XE El+C Ci，又假设又假设 X X 出现在第出现在第 m 行第行第 j 列

9、，那么列，那么 X XE Em+C Cj，ll)的第的第 一个元素，而按阵列构造规则，后面行的第一个元素是前面一个元素，而按阵列构造规则，后面行的第一个元素是前面 行中未曾出现过的元素，这就和阵列构造规则相矛盾。行中未曾出现过的元素，这就和阵列构造规则相矛盾。6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/110定理定理6.2.6(线性码纠错极限定理线性码纠错极限定理)：二元二元(n,k)线性码能纠线性码能纠 2nk 个错误图样。个错误图样。这这 2nk 个可纠的错误图样，包括个可纠的错误图样，包括0 0矢量在内，矢量在内，即即。证明证明：L(n,k)线性码的标准阵

10、列有线性码的标准阵列有 2k 列（和码矢矢量相等），列（和码矢矢量相等），2n/2k=2nk行，且任何两列和两行都没有相同的元素。行，且任何两列和两行都没有相同的元素。L陪集陪集：标准阵列的每一行叫做码的一个陪集。：标准阵列的每一行叫做码的一个陪集。L陪集首陪集首：每个陪集的第一个元素叫做陪集首。：每个陪集的第一个元素叫做陪集首。L每一列包含每一列包含 2nk 个元素，最上面的是一个码矢，其它元素是个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第陪集首和该码矢之和，例如第 j 列为列为6.2.6 线性分组码的译码线性分组码的译码),(232jjjjjknCECECECD第六章

11、信道编码2022/12/111L若发送码矢为若发送码矢为 C Cj，信道干扰的错误图样是陪集首，则接收，信道干扰的错误图样是陪集首，则接收矢量矢量 R R 必在必在 D Dj 中；中；L若错误图样不是陪集首，则接收矢量若错误图样不是陪集首，则接收矢量 R R不在不在 D Dj 中，则译成中，则译成其它码字，造成错误译码；其它码字，造成错误译码；L当且仅当错误图样为陪集首时，译码才是正确的。当且仅当错误图样为陪集首时，译码才是正确的。L可纠正的错误图样可纠正的错误图样：这：这 2nk 个陪集首称为可纠正的错误图个陪集首称为可纠正的错误图样。样。6.2.6 线性分组码的译码线性分组码的译码第六章

12、信道编码2022/12/112线性码纠错能力与监督元数目的关系线性码纠错能力与监督元数目的关系：一个可纠一个可纠 t 个错个错误的线性码必须满足误的线性码必须满足 上式中等式成立时的线性码称为上式中等式成立时的线性码称为完备码完备码。即。即 证明证明：L纠一个错误的纠一个错误的(n,k)线性码，必须能纠正线性码，必须能纠正 个错误个错误图样，因此图样，因此6.2.6 线性分组码的译码线性分组码的译码11nnnkn1112tiknintnnn02112tiknin02第六章 信道编码2022/12/113L对纠两个错误的对纠两个错误的(n,k)线性码，必须能纠线性码，必须能纠 个错个错误图样，所

13、以误图样，所以L依此类推，一个纠依此类推，一个纠 t 个错误的个错误的(n,k)线性码必须满足线性码必须满足L对于完备码，对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的的错误图样数，所以完备码的(nk)个监督码元得到了充分的个监督码元得到了充分的利用利用。6.2.6 线性分组码的译码线性分组码的译码211nn2112nnkntiknintnnn02112第六章 信道编码2022/12/114定义定义：(n,k)线性码的所有线性码的所有 2nk 个伴随式，在译码过程中若都个伴随式，在译码过程中若都用来纠正所有小于等于用来

14、纠正所有小于等于 个随机错误，以及部分个随机错误，以及部分大于大于 t 的错误图样，则这种译码方法称为的错误图样，则这种译码方法称为完备译码完备译码。限定距离译码限定距离译码：任一个任一个(n,k)线性码，能纠正线性码，能纠正 个随机错误，如果在译码时仅纠正个随机错误，如果在译码时仅纠正 t t 个错误，而当错误个数个错误，而当错误个数大于大于t时，译码器不进行纠错而仅指出发生了错误，称这种方时，译码器不进行纠错而仅指出发生了错误，称这种方法为法为限定距离译码限定距离译码。2/)1(dt6.2.6 线性分组码的译码线性分组码的译码2/)1(dt第六章 信道编码2022/12/115从多维矢量空

15、间的角度看完备码从多维矢量空间的角度看完备码：假定围绕每一个码字假定围绕每一个码字 C Ci 放置一个半径为放置一个半径为 t 的球，每个球内包含的球，每个球内包含了与该码字汉明距离小于等于了与该码字汉明距离小于等于 t 的所有接收码字的所有接收码字 R R 的集合；的集合；这样，在半径为这样，在半径为 t=(dmin1)/2 的球内的接收码字数是的球内的接收码字数是因为有因为有 2k 个可能发送的码字，也就有个可能发送的码字，也就有2k 个不相重叠的半径为个不相重叠的半径为t的的球。包含在球。包含在2k个球中的码字总数不会超过个球中的码字总数不会超过2n个可能的接收码字。个可能的接收码字。于

16、是一个纠于是一个纠 t 个差错的码必然满足不等式个差错的码必然满足不等式如果上式中等号成立，表示所有的接收码字都落在如果上式中等号成立，表示所有的接收码字都落在 2k 个球内，个球内，而球外没有一个码，而球外没有一个码，这就是完备码这就是完备码。tikntinkinin00222即6.2.6 线性分组码的译码线性分组码的译码tiin0 第六章 信道编码2022/12/116完备码特性完备码特性：围绕：围绕 2k 个个码字，汉明距离为码字，汉明距离为t=(dmin1)/2的所有球的所有球都是不相交的，每一个都是不相交的，每一个接收码字都落在这些球接收码字都落在这些球中之一，因此接收码与中之一，因

17、此接收码与发送码的距离至多为发送码的距离至多为 t，这时所有重量这时所有重量t的错误的错误图样都能用最佳（最小图样都能用最佳（最小距离）译码器得到纠正，距离）译码器得到纠正，而所有重量而所有重量t+1的错误的错误图样都不能纠正。图样都不能纠正。6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/117举例：对纠一个错误的举例：对纠一个错误的(7,4)汉明码，汉明码，可见，可见，(7,4)汉明码是一个完备码。汉明码是一个完备码。所有汉明码都是完备码所有汉明码都是完备码（满足（满足2nk=2m=n+1）。）。标准阵列译码标准阵列译码=最小距离译码法最小距离译码法=最佳译码法

18、最佳译码法陪集首是可纠正的错误图样，为了使译码错误概率最小，陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的时是选取重量最轻的 n 重作陪集首；重作陪集首；这样，当错误图样为陪集首时（可纠的错误图样），接收这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；矢量与原发送码矢间的距离（等于陪集首）最小；6.2.6 线性分组码的译码线性分组码的译码112,811,

19、82nnknkn所以第六章 信道编码2022/12/118因此，选择重量最轻的元素作陪集首，按标准阵列译码就是因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；按最小距离译码；所以标准阵列译码法也是最佳译码法。所以标准阵列译码法也是最佳译码法。定理定理6.2.7：在标准阵列中，一个陪集的所有：在标准阵列中，一个陪集的所有 2k 个个 n 重有相同的重有相同的伴随式，不同的陪集伴随式互不相同。伴随式，不同的陪集伴随式互不相同。证明证明：设设 H H 为给定为给定(n,k)线性码的监督矩阵，在陪集首为线性码的监督矩阵，在陪集首为 E El 的陪集的陪集中的任意矢量中的任意矢量 R

20、 R 为为 R R=E El+C Ci,i=1,2,2k其伴随式为其伴随式为 S S=RHRHT=(E El+C Ci)HHT=E ElHHT+C CiHHT=E ElHHT上式表明：上式表明：陪集中任意矢量的伴随式等于陪集首的伴随式陪集中任意矢量的伴随式等于陪集首的伴随式。即同一陪集中所有伴随式相同。即同一陪集中所有伴随式相同。不同陪集中，由于陪集首不同所以伴随式不同。不同陪集中，由于陪集首不同所以伴随式不同。6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/119 结论结论任意任意 n 重的伴随式决定于它在标准阵列中所在陪集的陪集首。重的伴随式决定于它在标准阵列中

21、所在陪集的陪集首。标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到得多的译码表，从而得到(n,k)线性码的一般译码步骤。线性码的一般译码步骤。(n,k)线性码的一般译码步骤线性码的一般译码步骤计算接收矢量计算接收矢量 R R 的伴随式的伴随式 S ST=HRHRT；根据伴随式和错误图样一一对应的关系，利用伴随式译码表，根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出由伴随式

22、译出 R R 的错误图样的错误图样 E E；将接收字减错误图样，得发送码矢的估值将接收字减错误图样，得发送码矢的估值 C C=R RE E。6.2.6 线性分组码的译码线性分组码的译码第六章 信道编码2022/12/120 上述译码法称为伴随式译码法或查表译码法。上述译码法称为伴随式译码法或查表译码法。线性分组码一般译码器线性分组码一般译码器 译码器如图译码器如图6.2.9。这种查表译码法具有最小的译码延迟和最小的。这种查表译码法具有最小的译码延迟和最小的译码错误概率，原则上可用于任何译码错误概率，原则上可用于任何(n,k)线性码。线性码。6.2.6 线性分组码的译码线性分组码的译码第六章 信

23、道编码2022/12/121 在通信中检纠错码的实际性能是在统计上体现出来在通信中检纠错码的实际性能是在统计上体现出来的。以下分析均以的。以下分析均以BSC信道为模型。信道为模型。(1)不可检错误概率不可检错误概率(2)译码错误概率译码错误概率(3)译码失败概率译码失败概率(4)比特误码率比特误码率6.2.7 线性分组码的性能线性分组码的性能第六章 信道编码2022/12/122(1)不可检错误概率不可检错误概率 pud由由(n,k)线性码的重量分布求线性码的重量分布求 pud令令Ai为码的重量分布，表示重量为为码的重量分布，表示重量为i的码字个数，的码字个数，i=0,1,2,n；由于由于仅当

24、错误图样与码矢集合中的非仅当错误图样与码矢集合中的非0码矢相同时，才不能检码矢相同时，才不能检出错误出错误，所以（，所以（p是是BSC的误码率，且码字等概发送的误码率，且码字等概发送）举例举例：(7,3)码的重量分布是码的重量分布是 A0=1,A1=A2=A3=0,A4=7，其不可，其不可检错误概率为检错误概率为 pud7p4(1p)3，若，若p=0.01，则，则 pud6.8108。利用利用(n,k)码重量分布与其对偶码的重量分布关系求码重量分布与其对偶码的重量分布关系求 pud设设A0,A1,A2,An 是是(n,k)码码的重量分布；的重量分布；B0,B1,B2,Bn 是是它的对偶码它的对

25、偶码的重量分布；的重量分布；6.2.7 线性分组码的性能线性分组码的性能)23.2.6(11niiniiudppAp第六章 信道编码2022/12/123对偶码的重量枚举式对偶码的重量枚举式：下面的多项式称为：下面的多项式称为(n,k)码和它的对偶码和它的对偶码的重量枚举式。码的重量枚举式。MacWilliams恒等式恒等式：若已知线性码的对偶码的重量分布，就：若已知线性码的对偶码的重量分布，就可确定该码本身的重量分布。可确定该码本身的重量分布。由式由式(6.2.23)得得)24.2.6()()(22102210nnnnxBxBxBBxBxAxAxAAxA6.2.7 线性分组码的性能线性分组码

26、的性能)25.2.6(11)1(2)()(xxBxxAnkn)26.2.6(111niiinudppApp)23.2.6(11niiniiudppAp第六章 信道编码2022/12/124令令将这个恒等式代入式将这个恒等式代入式(6.2.26)得得将恒等式和将恒等式和(6.2.25)代入上式得代入上式得.)28.2.6(111ppAppnud6.2.7 线性分组码的性能线性分组码的性能)27.2.6(1111)24.2.6(110niiippAppAAppx，得到恒等式，并考虑到，代入式niiinknudpBpBppBp0)()21()21()29.2.6()1()21(2其中)24.2.6(

27、)()(22102210nnnnxBxBxBBxBxAxAxAAxA第六章 信道编码2022/12/125当当k(nk)时，用式时，用式(6.2.29)计算计算 pud 则更容易。则更容易。举例：已知举例：已知(7,4)码的监督矩阵码的监督矩阵 HH(7,4)，它等于其对偶码的生成，它等于其对偶码的生成矩阵矩阵 GG(7,3)，即，即 由此生成矩阵的行的线性组合，可得到由此生成矩阵的行的线性组合，可得到(7,3)码的码的8个码字个码字 由此得到由此得到(7,3)对偶码的重量枚举式为对偶码的重量枚举式为 B(x)=1+7x4 利用式利用式(6.2.29)得出得出(7,4)码的未检出错误概率为码的

28、未检出错误概率为 pud=231+7(12p)4(1p)7 设设 p=0.01，则，则 pud=6106。100101101011100010111)4,7()3,7(HG6.2.7 线性分组码的性能线性分组码的性能01001110011101110100111101001010011100111001110100000000第六章 信道编码2022/12/126(2)译码错误概率译码错误概率pwe正确译码概率正确译码概率pwc：纠正小于等于：纠正小于等于t个差错的概率个差错的概率译码错误概率译码错误概率 pwe译码错误发生在差错数目大于译码错误发生在差错数目大于 t，接收向量，接收向量 R

29、R 与另一码字与另一码字 C C 的距离小于等于的距离小于等于 t 的情况；的情况；D Di 是重量是重量 i 并译为错误码字的可能的接收向量并译为错误码字的可能的接收向量 R R 的数目，即的数目，即译码错误概率译码错误概率pwe为为6.2.7 线性分组码的性能线性分组码的性能tiiniwcppinp01)30.2.6(,)(CCCRRRDtdiWintiinintiiniiweppinppp1111D第六章 信道编码2022/12/127(3)译码失败概率译码失败概率pwf由于仍存在不满足式由于仍存在不满足式(6.2.30)的接收码矢的接收码矢 R R，对于限定距离译码，对于限定距离译码器

30、来说就处于译码失败状态，即器来说就处于译码失败状态，即 pwf=1 pwc pwe 图图6.2.30中中RA正确译码概率正确译码概率RB译码错误概率译码错误概率RC译码失败概率译码失败概率6.2.7 线性分组码的性能线性分组码的性能第六章 信道编码2022/12/128(4)比特误码率比特误码率pbc：信道的比特差错概率信道的比特差错概率，对于，对于BSC信道，信道，pbc等于信道转移概率等于信道转移概率p。pbd：译码错误导致的码字之间的比特差错率译码错误导致的码字之间的比特差错率。pbm：消息源与消息接收终端之间的比特差错概率消息源与消息接收终端之间的比特差错概率。一般认为消息和码字之间的

31、映射不改变码字差错导致在整个码一般认为消息和码字之间的映射不改变码字差错导致在整个码长内比特差错的均匀分布特性，在统计意义上有长内比特差错的均匀分布特性，在统计意义上有 pbm pbd6.2.7 线性分组码的性能线性分组码的性能第六章 信道编码2022/12/129pbe 译码错误的误码率译码错误的误码率：设码字是等概率发送，则：设码字是等概率发送，则 是发送全是发送全0码字并错接收为码字并错接收为 重量为重量为j的码字的概率；的码字的概率；Pbe 与与 pwe的关系的关系码字错必然有至少码字错必然有至少 2t+1位码字比特错；位码字比特错；每个码字平均有每个码字平均有 位消息比特错，所以位消

32、息比特错，所以pbe与与pwe有如下有如下渐进关系渐进关系njjwebejpnp1)(16.2.7 线性分组码的性能线性分组码的性能)(jwep)12(tnkwebepnktkp)12(第六章 信道编码2022/12/130pbf 译码失败造成的误码率译码失败造成的误码率pbd译码后总的误码率：译码后总的误码率：pbd=pbe+pbf6.2.7 线性分组码的性能线性分组码的性能ntiiniibfpipDinnp111第六章 信道编码2022/12/131汉明码是汉明于汉明码是汉明于1950年提出的纠一个错误的线性码，也年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系

33、统是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。和数据存储系统中得到广泛应用的一类线性码。汉明码的结构参数：汉明码的结构参数：纠一个错误的线性码，其最小距离纠一个错误的线性码，其最小距离 dmin=3；监督矩阵任意两列；监督矩阵任意两列线性无关线性无关/H H 的任两列互不相同的任两列互不相同；没有全；没有全0 0的列。的列。监督元个数监督元个数 nk=r；H H 阵中每列有阵中每列有 r 个元素，至多可构成个元素，至多可构成 2r1种互不相同的非种互不相同的非0 0列。列。对于任意正整数对于任意正整数 m3，汉明码的结构参数为，汉明码的结构参数为码

34、长：码长：n=2m1信息位数：信息位数：k=2mm1监督位数：监督位数：nk=m码的最小距离：码的最小距离：dmin=3(t=1)6.2.8 汉明码汉明码第六章 信道编码2022/12/132汉明码监督矩阵构成的两种方式汉明码监督矩阵构成的两种方式构成构成 H H 阵的标准形式，阵的标准形式，HH=Q IQ Im，其中，其中 I Im 为为 m 阶单位子阵，阶单位子阵，子阵子阵 Q Q 是构造是构造 I Im 后剩下的列任意排列。用这种形式的后剩下的列任意排列。用这种形式的 H H 阵编阵编出的汉明码是系统码。出的汉明码是系统码。按按m重（重量为重（重量为m）表示的二进制顺序排列。按这种形式）

35、表示的二进制顺序排列。按这种形式 H H 阵阵编出的码是非系统码。当发生可纠的单个错误时，伴随式为编出的码是非系统码。当发生可纠的单个错误时，伴随式为 H H 阵中对应的列，所以伴随式的二进制数值就是错误位置号，有阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。时这种码译码比较方便。由于汉明码可纠的错误图样数为由于汉明码可纠的错误图样数为6.2.8 汉明码汉明码因此汉明码是完备码。即满足式，tiknminnn02121第六章 信道编码2022/12/133(1)扩展扩展/Extending和打孔和打孔/Puncturing(2)增广增广/Augmenting和删信和

36、删信/Expunging/Expurgating(3)延长延长/Lengthening和缩短和缩短/Shortening(4)乘积乘积/Product(5)级联级联/Concatenating(6)交织交织/Interleaving6.2.9 由已知码构造新码的方法由已知码构造新码的方法第六章 信道编码2022/12/134(1)扩展扩展/Extending和打孔和打孔/Puncturing扩展扩展：保持码字数保持码字数 k 不变，增加冗余位数以增加码长。不变，增加冗余位数以增加码长。打孔打孔：保持保持 k 不变，减小冗余位。可以认为是扩展的逆过程。不变，减小冗余位。可以认为是扩展的逆过程。(

37、2)增广增广/Augmenting和删信和删信/Expunging/Expurgating增广增广：保持保持 n 不变，增加码字数目不变，增加码字数目 k。删信删信：保持保持 n 不变减小不变减小 k。(3)延长延长/Lengthening和缩短和缩短/Shortening延长延长：同时增加同时增加 k 和和 n。缩短缩短：同时减小同时减小 k 和和 n。6.2.9 由已知码构造新码的方法由已知码构造新码的方法第六章 信道编码2022/12/135举例举例：(7,4,3)汉明码的各种修正关系如图汉明码的各种修正关系如图6.2.31所示。所示。6.2.9 由已知码构造新码的方法由已知码构造新码的

38、方法第六章 信道编码2022/12/136(4)乘积乘积/Product 消息作为阵列，分别进行行列编码。消息作为阵列，分别进行行列编码。(5)级联级联/Concatenating对消息编码后的码字再进行一次编码。对消息编码后的码字再进行一次编码。级联编码的第一次所用码称外码；第二次所用码称内码。级联编码的第一次所用码称外码；第二次所用码称内码。级联编码常用于既有随机差错又有突发差错的信道编码。级联编码常用于既有随机差错又有突发差错的信道编码。(6)交织交织/Interleaving交织编码分为分组交织和卷积交织两种。交织编码分为分组交织和卷积交织两种。如果交织编码所用的如果交织编码所用的(n

39、,k)码可以纠正码可以纠正 t 个随机差错，那么交织深个随机差错，那么交织深度为度为 D 的交织编码可以纠正的交织编码可以纠正 D t 长的突发错误。长的突发错误。6.2.9 由已知码构造新码的方法由已知码构造新码的方法第六章 信道编码2022/12/137举例：视盘存储的纠错编码采用对举例：视盘存储的纠错编码采用对(31,21)纠双错的纠双错的BCH码码进行进行256深度的交织，可以有效纠正因为介质损坏、磁深度的交织，可以有效纠正因为介质损坏、磁（光）头污染或者定时抖动等引起的连续差错。（光）头污染或者定时抖动等引起的连续差错。6.2.9 由已知码构造新码的方法由已知码构造新码的方法第六章

40、信道编码2022/12/138(1)研究码限的意义研究码限的意义研究码的纠错能力，也就是分析码的研究码的纠错能力，也就是分析码的 n,k,d 之间的关系，之间的关系，不仅能从理论上指出哪些码可以构造出，哪些码不能构不仅能从理论上指出哪些码可以构造出，哪些码不能构造出，而且也为工程实验提供了对各种码性能估计的理造出，而且也为工程实验提供了对各种码性能估计的理论依据。论依据。研究码的纠错能力始终是编码理论中一个重要的课题。研究码的纠错能力始终是编码理论中一个重要的课题。在纠错编码实现上总希望在尽可能小的在纠错编码实现上总希望在尽可能小的 n 和和 r 条件下获条件下获得尽可能大的得尽可能大的 k,

41、d 或或 t。满足码限的码称为最佳码。满足码限的码称为最佳码。6.2.10 线性分组码的码限线性分组码的码限第六章 信道编码2022/12/139(2)三个码限三个码限普罗特金普罗特金(Plotkin)限限(P限限)对任意二元对任意二元(n,k,d)码满足码满足6.2.10 线性分组码的码限线性分组码的码限ndnkRnndkk2411221充分大时满足当第六章 信道编码2022/12/140汉明限汉明限(H限限)对任意二元对任意二元(n,k,2t+1)码满足码满足6.2.10 线性分组码的码限线性分组码的码限)1(log)1(log)(21222220 xxxxxHndHRnintikn其中为

42、充分大时汉明限可表示当码称为完备码。满足上式中等式成立的第六章 信道编码2022/12/141瓦尔沙莫夫吉尔伯特瓦尔沙莫夫吉尔伯特(Varshamov-Gilbert)(V-G限限)存在某个二元存在某个二元(n,k,d)码满足码满足6.2.10 线性分组码的码限线性分组码的码限 ndHRnindikn22112220充分大时当第六章 信道编码2022/12/142在在 n 充分大时各个充分大时各个码限的关系曲线如码限的关系曲线如图图6.2.33所示。图中所示。图中以以 V-G 限为下限，限为下限，H 限和限和 P 限为上限限为上限所围的区域所围的区域(蓝色区蓝色区域域)是好码（满足所是好码（满

43、足所有上述码限的有上述码限的(n,k,d)码）。码）。6.2.10 线性分组码的码限线性分组码的码限第六章 信道编码2022-12-143构造构造(7,4)汉明码的一致监督汉明码的一致监督矩阵并设计编、译码器。矩阵并设计编、译码器。已知（已知（7，4）汉明码的系统码形式为）汉明码的系统码形式为 课堂练习题课堂练习题10001010100111G00101100001011第六章 信道编码2022-12-144（7，4）汉明码的系统码形式为）汉明码的系统码形式为 监督矩阵为监督矩阵为(37)矩阵矩阵100101101011100010111H课堂练习题课堂练习题10001010100111G00

44、101100001011)14.2.6()()()()()(rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkSIQHQIGPQPQ0QPIPQIIPQIHGIPHQIG或所以，第六章 信道编码2022-12-145构造构造(7,4)汉明码的一致监督矩阵并设计编、译码器。汉明码的一致监督矩阵并设计编、译码器。解：监督矩阵为(37)矩阵100101101011100010111H课堂练习题课堂练习题3560345145620356134524560123456000000100101101011100010111CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCTT0HC第六章 信道编码2022-12-146构造(7,4)汉明码的伴随式课堂练习题课堂练习题0356013451245620120356134524560123456100101101011100010111RRRRSRRRRSRRRRSSSSRRRRRRRRRRRRRRRRRRRTTSHC第六章 信道编码2022-12-147构造(7,4)汉明码的纠错译码电路课堂练习题课堂练习题第六章 信道编码2022/12/148