信道的纠错编码课件

《信道的纠错编码课件》由会员分享，可在线阅读，更多相关《信道的纠错编码课件（49页珍藏版）》请在金锄头文库上搜索。

1、第第9章章 信道的纠错编码信道的纠错编码pp 信道编码的概念信道编码的概念pp 线性分组码线性分组码pp 循环码循环码1 1信道的纠错编码信道的纠错编码信道编码的纠错原理信道编码的纠错原理v信道编码的目的：提高系统的可靠性信道编码的目的：提高系统的可靠性v实现方法：实现方法：增加冗余度增加冗余度v信道编码的纠错原理信道编码的纠错原理 根据一定的规律在待发送的信息码元中人为的加入一些根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，冗余码元，这些这些冗余冗余码元与信息码元之间以某种确定的规则码元与信息码元之间以某种确定的规则相互关联（约束）。相互关联（约束）。 在接收端按照既定的规则检验

2、信息码元与监督码元之间在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。关系将受到破坏，从而可以发现错误乃至纠正错误。 纠错码纠错码2信道的纠错编码纠错码的分类纠错码的分类v 按功能分：按功能分：l 检错码：仅能检测误码。检错码：仅能检测误码。l 纠错码：可纠正误码。纠错码：可纠正误码。v 按信息码元与监督码元之间的检验关系分：按信息码元与监督码元之间的检验关系分：l 线性码：满足线性关系。线性码：满足线性关系。l 非线性码：不存在线性关系。非线性

3、码：不存在线性关系。 v 按信息码元在编码后是否保持原形式：按信息码元在编码后是否保持原形式：l系统码：信息码元与监督码元在分组内有确定位置，系统码：信息码元与监督码元在分组内有确定位置， 编码后的信息码元保持位置不变。编码后的信息码元保持位置不变。l非系统码：信息位打乱，与编码前位置不同。非系统码：信息位打乱，与编码前位置不同。 3信道的纠错编码纠错码的分类纠错码的分类v按信息码元与监督码元之间的约束方式不同分：按信息码元与监督码元之间的约束方式不同分：l 分组码分组码：将信息码元分为：将信息码元分为k位一组，每组相互独立，再按位一组，每组相互独立，再按编码规则变成编码规则变成n位码（位码（

4、nk)，其中，其中n-k=r位为监督码元，我位为监督码元，我们称之为（们称之为（n,k)分组码。分组码。本码组的监督码元仅和本码组的本码组的监督码元仅和本码组的信息码元相关。信息码元相关。l 卷积码卷积码：本码组的监督码元不仅和本码组的信息码元相：本码组的监督码元不仅和本码组的信息码元相关，而且与前面码组的信息码元有关。关，而且与前面码组的信息码元有关。 4信道的纠错编码错误图样错误图样 当系统无干扰时当系统无干扰时 R=C 当系统有干扰时当系统有干扰时 R=C+E其中，其中，E称为信道的错误图样，称为信道的错误图样，E=(e0,e1,en-1)；ei 0,1；当；当ei=1，则第，则第i位上

5、有错；反位上有错；反之，无错。之，无错。例：例： C = 0 0 1 0 1 1 0 1 E = 0 1 0 0 1 0 0 1 R = 0 1 1 0 0 1 0 0由信道的对称性可知由信道的对称性可知 p(0/1)=p(1/0)=p(e=1)=p反之，若已知反之，若已知R ，E 则可求出则可求出C，这就是纠错码的原理，如：，这就是纠错码的原理，如： E = 0 1 0 0 1 0 0 1 R = 0 1 1 0 0 1 0 0 C = 0 0 1 0 1 1 0 15信道的纠错编码检错与纠错的原理检错与纠错的原理 编码效率编码效率设：信息码长度为设：信息码长度为k，经信道编码后长度为，经信

6、道编码后长度为n，则我们定，则我们定义编码效率义编码效率R为：为：R=k/n 几种简单的检纠错码几种简单的检纠错码v奇奇/偶校验码偶校验码检错码检错码v重复码重复码纠错码纠错码6信道的纠错编码检错与纠错方式和能力检错与纠错方式和能力 检纠错方式检纠错方式vFEC（前向纠错）（前向纠错）纠错纠错vARQ （自动请求重发）（自动请求重发）检错检错 几个概念几个概念v汉明距离汉明距离/距离距离：在线性码中，两个码字：在线性码中，两个码字 U、V 之之间对应码元位上符号取值不同的个数，称为码字间对应码元位上符号取值不同的个数，称为码字 U、V 之间的汉明距离。之间的汉明距离。v例如例如：(7,3) 码

7、的两个码字码的两个码字 U=0011101,V=0100111，它们之间第，它们之间第2、3、4和和6位不同。因此，码字位不同。因此，码字 U 和和 V 的距离为的距离为4。v线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一维线性空间中的一点，码字间的距离即为空间中两点，码字间的距离即为空间中两对应点的距离。对应点的距离。7信道的纠错编码检错与纠错方式和能力检错与纠错方式和能力v最小码距最小码距：在码集合中，任两个码字间的距离为最小时，：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。该码距即为码集合的最小码距。v码字的重量码字的重量：码字中非：码

8、字中非0码元符号的个数，称为该码字码元符号的个数，称为该码字 的重量，又称为汉明重量。的重量，又称为汉明重量。v码的最小重量码的最小重量：线性分组码：线性分组码CI中，中，非非0码字码字重量最小重量最小 值，叫做码值，叫做码CI的最小重量：的最小重量：Wmin =minW(V),VCI ,V0v最小码距与最小重量的关系最小码距与最小重量的关系：线性分组码的最小码距：线性分组码的最小码距 等于它的最小重量。等于它的最小重量。8信道的纠错编码检错与纠错能力检错与纠错能力-1v最小码距与纠错能力的关系：最小码距与纠错能力的关系： 定理：定理：(n,k) 线性码能纠线性码能纠 t 个错误的充要条件是码

9、个错误的充要条件是码的最小距离为的最小距离为 d min =2t + 1 或或 t = (d min1)/2V V 9信道的纠错编码检错与纠错能力检错与纠错能力-2v最小码距与检错能力的关系：最小码距与检错能力的关系： 定理：定理：(n,k) 线性码能够发现线性码能够发现 e个错误的充要条件是码个错误的充要条件是码的最小距离为的最小距离为 d min =e + 1 或或 e = d min1VVe e10信道的纠错编码检错与纠错能力检错与纠错能力-3v最小码距与检、纠错能力的关系：最小码距与检、纠错能力的关系： 定理：定理：(n,k) 线性码能纠线性码能纠 t 个错误，并能发现个错误，并能发现

10、e 个错误个错误 (e t ) 的充要条件是码的最小距离为的充要条件是码的最小距离为 dmin=t +e +1 或或 t +e =dmin1e eVV11信道的纠错编码线 性 分 组 码 一、线性分组码的描述一、线性分组码的描述线性分组码是同时具有分组特性和线性特性的纠错码。线性分组码是同时具有分组特性和线性特性的纠错码。定义定义：一个：一个（n,k）线性分组码线性分组码C是称为码字是称为码字c的的n维向量的集合。维向量的集合。式中：式中： 为消息矢量，为消息矢量， 是一个是一个k行行n列的秩为列的秩为k（n k)的矩的矩阵，我们称它为线性码的阵，我们称它为线性码的生成矩阵生成矩阵。第一种编码

11、方法第一种编码方法12信道的纠错编码线 性 分 组 码例：例：（4,3）偶校验码是一个（）偶校验码是一个（4,3）线性分组码，其）线性分组码，其 生成矩阵为生成矩阵为 求消息码求消息码010，110所对应的线性码。所对应的线性码。解：解：13信道的纠错编码线 性 分 组 码将消息码直接代入有：将消息码直接代入有：思考思考：此码是否为系统码？：此码是否为系统码？14信道的纠错编码线 性 分 组 码二、线性分组码的性质及定理二、线性分组码的性质及定理v当消息码为零向量当消息码为零向量00，所得的码字为零码字，所得的码字为零码字0000。 v线性分组码的封闭性：线性分组码中任意两个码字之和线性分组码

12、的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。仍然是该码的码字。vG中每一行中每一行 gi=(gin-1,gin-2, gi0 ) 都是一个码字；都是一个码字；v对每一个信息组对每一个信息组m，由矩阵，由矩阵G都可以求得都可以求得 (n,k) 线性码对线性码对应的码字。信息码组长应的码字。信息码组长k位，有位，有 2k个不同的信息码组，则个不同的信息码组，则有有 2k 个码字与它们一一对应。个码字与它们一一对应。v在由在由 (n,k) 线性码构成的线性空间线性码构成的线性空间 Vn 的的 k 维子空间中，维子空间中，一定存在一定存在 k 个个线性独立线性独立的码字：的码字：g0,g1

13、, gk-1，码，码Ci 中其中其它任何码字它任何码字C都可以表为这都可以表为这 k 个码字的一种个码字的一种线性组合线性组合，即，即15信道的纠错编码线 性 分 组 码16信道的纠错编码线 性 分 组 码三、线性分组码的监督阵三、线性分组码的监督阵 线性分组码的监督阵线性分组码的监督阵v编码就是给已知信息码组按预定规则添加监督码元，以构编码就是给已知信息码组按预定规则添加监督码元，以构成码字。成码字。v在在 k 个信息码元之后附加个信息码元之后附加 r (r=nk) 个监督码元，使每个个监督码元，使每个监督码元是其中某些信息码元的模监督码元是其中某些信息码元的模2和。和。v举例：举例：k=3

14、, r=4，构成，构成 (7,3) 线性分组码。设码字为线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，为信息元，C3,C2,C1,C0为监督元，每个码元为监督元，每个码元取取“0”或或“1”监督元可按下面方程组计算监督元可按下面方程组计算17信道的纠错编码线 性 分 组 码v一致监督方程一致监督方程/一致校验方程一致校验方程：确定信息元得到监督元规则：确定信息元得到监督元规则的一组方程称为监督方程的一组方程称为监督方程/校验方程。由于校验方程。由于所有码字都按同所有码字都按同一规则确定一规则确定，又称为一致监督方程，又称为一致监督方程/一致校验方程。

15、一致校验方程。v由于一致监督方程是线性的，即监督元和信息元之间是线由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性性运算关系，所以由线性监督方程所确定的分组码是线性分组码。分组码。第二第二种编种编码方码方法法18信道的纠错编码线 性 分 组 码v信息码组信息码组 (101)，即，即C6=1, C5=0, C4=1v代入监督方程得：代入监督方程得： C3=0, C2=0, C1=1, C0=1v由信息码组由信息码组 (101) 编出的码字为编出的码字为 (1010011)。其它。其它7个码字如个码字如下。下。表表 9.1 (7,3) 分组码编码

16、表分组码编码表 信息组信息组 对应码字对应码字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 19信道的纠错编码线 性 分 组 码v为了运算方便，将监为了运算方便，将监督方程写成矩阵形式，督方程写成矩阵形式，得得:20信道的纠错编码线 性 分 组 码v推广到一般情况：对推广到一般情况：对 (n,k) 线性分组码，每个码字线性

17、分组码，每个码字中的中的 r (r=nk) 个监督元与信息元之间的关系可个监督元与信息元之间的关系可由下面的线性方程组确定由下面的线性方程组确定 令上式的系数矩阵为令上式的系数矩阵为 H，码字行阵列为，码字行阵列为 C 同样有同样有 我们称我们称H为一致监督阵为一致监督阵/监督阵监督阵。21信道的纠错编码线 性 分 组 码一致监督阵一致监督阵H22信道的纠错编码线 性 分 组 码 监督阵与生成阵的关系监督阵与生成阵的关系v由于生成矩阵由于生成矩阵G的每一行都是一个码字，的每一行都是一个码字，所以所以G 的每行都满足的每行都满足HrnCTn1=0Tr1，则，则有有HrnGTnk=0Trk 或或

18、GknHTnr=0krv线性分组码的监督矩阵与生成矩阵正交线性分组码的监督矩阵与生成矩阵正交。 23信道的纠错编码四、四、(n,k)线性码的对偶码线性码的对偶码对偶码对偶码：对一个：对一个(n,k)线性码线性码 CI，由于，由于HrnGTnk=0Trk， 如果以如果以G 作监督矩阵，而以作监督矩阵，而以H 作生成作生成矩阵，可构造另一个码矩阵，可构造另一个码CId，码，码CId是一个是一个(n,nk)线性码，称码线性码，称码CId为原码的为原码的对偶码对偶码。 例如例如： (7,4)线性码的对偶码是线性码的对偶码是(7,3)码：码：(7,3)码的监督矩阵码的监督矩阵H(7,3)是是(7,4)码

19、生成矩阵码生成矩阵G(7,4)线 性 分 组 码24信道的纠错编码线 性 分 组 码五、生成阵和监督阵的标准形式五、生成阵和监督阵的标准形式 生成阵的标准形式生成阵的标准形式通过通过行行初等变换，将初等变换，将 G 化为化为左边左边 k 列列是单位子阵的标是单位子阵的标准形式，我们称之为准形式，我们称之为生成阵的标准形式生成阵的标准形式25信道的纠错编码线 性 分 组 码 线性系统分组码线性系统分组码用生成阵的标准形式产生的码集合用生成阵的标准形式产生的码集合 称为称为线性系统线性系统分组码。分组码。设：设： 则有：则有：则有：则有：依次排在码的前面依次排在码的前面监督元依次排在码的后部监督元

20、依次排在码的后部26信道的纠错编码线 性 分 组 码线性系统分组码线性系统分组码：用标准生成矩阵：用标准生成矩阵 Gkn 编成的编成的码字，前面码字，前面 k 位为信息数字，后面位为信息数字，后面 r=nk 位位为校验数字，这种为校验数字，这种信息数字在前信息数字在前校验数字在后校验数字在后的线性分组码称为线性系统分组码。的线性分组码称为线性系统分组码。信信 息息 码码监监 督督 码码Cn-1 Cn-k Cn-k-1 C027信道的纠错编码线 性 分 组 码例：例：(7,4) 线性码的生成矩阵为线性码的生成矩阵为110100001101001110010101000174=*G)(110100

21、00110100111001010100010101)1010(74417141=*GmCm，则若28信道的纠错编码线 性 分 组 码 监督阵的标准形式监督阵的标准形式同样对监督阵的各行进同样对监督阵的各行进行行初等变换，将初等变换，将右边右边r列列化为单位化为单位阵即可得到阵即可得到监督阵的标准形式监督阵的标准形式。29信道的纠错编码线 性 分 组 码 监督阵与生成阵的转换关系监督阵与生成阵的转换关系由于系统码的监督阵与生成阵同样彼此正交，所以有：由于系统码的监督阵与生成阵同样彼此正交，所以有：所以，上述等式提供了监督阵与生成阵的互求。即，所以，上述等式提供了监督阵与生成阵的互求。即，30信

22、道的纠错编码线 性 分 组 码例：例：31信道的纠错编码线 性 分 组 码例：二元例：二元(7,3)码，若生成矩码，若生成矩阵已知，求生成矩阵和监阵已知，求生成矩阵和监督矩阵的标准形式。督矩阵的标准形式。解：解：得：得：行和行和行相加放入第行相加放入第行行行和行和 行相加放入第行相加放入第行行32信道的纠错编码线 性 分 组 码六、线性码的最小距离与监督阵的关系六、线性码的最小距离与监督阵的关系定理定理 1 设设H为为(n,k) 线性码的一致监督阵，线性码的一致监督阵，若若H中任意中任意S S列线性无关，而存在列线性无关，而存在S+1S+1列线性相关，则码的最小距离列线性相关，则码的最小距离为

23、为S+1S+1。 即，即， d dminmin=S+1=S+1定理定理 2 若码的最小距离为若码的最小距离为S+1S+1，则该码的，则该码的监督阵有监督阵有任意任意S S列线性无关，而必存在线性相关的列线性无关，而必存在线性相关的S+1S+1列。列。推理推理 在二元线性码的监督阵在二元线性码的监督阵H中，如果任一列都不为中，如果任一列都不为全零，且任二列都不相等，则该码能纠一个错。全零，且任二列都不相等，则该码能纠一个错。 例：例：33信道的纠错编码线 性 分 组 码 的 译 码 一、译码器的任务一、译码器的任务设：发送的码字设：发送的码字C=(cn -1，cn -2， ， c1， c0)，

24、通过有扰信道通过有扰信道传输，传输， 信道产生的错误图样信道产生的错误图样E=(en -1, en-2， , e1, e0)。接收。接收端译码器收到的端译码器收到的n 重码重码R=(rn -1, r n -2, r1, r0)， 其中其中R=C+E。译码器的译码器的任务任务：根据编码规则和信道特性，对接收码字根据编码规则和信道特性，对接收码字 R 作出判决，此判决过程又称为作出判决，此判决过程又称为译码译码。译码器按任务可分为：检错译码和纠错译码。译码器按任务可分为：检错译码和纠错译码。v检错译码：输出接收码字，及差错标志。检错译码：输出接收码字，及差错标志。v纠错译码：输出纠正的码字（在纠错

25、能力之内）纠错译码：输出纠正的码字（在纠错能力之内） 输出接收码字及出错标志。（超出纠错能力）输出接收码字及出错标志。（超出纠错能力） 34信道的纠错编码线 性 分 组 码 的 译 码 二、检纠错译码原理二、检纠错译码原理 伴随式和错误检测伴随式和错误检测 用用监监督督矩矩阵阵编编码码，当当然然也也用用监监督督矩矩阵阵译译码码。当当收收到到一一个个接接收收码码字字R后后，可可用用监监督督矩矩阵阵H来来检检验验R是是否否满满足足监监督督方方程程，即即HRT0T是是否否成成立立。若若关关系系式式成成立立，则则认认为为R是是一一个个码码字字，否否则则判判为为码码字字在在传传输输中中发发生生了了错错误

26、误。因因此此，HRT的的值值是是否否为为0 是是检检验验码码字字出出错错与与否否的依据。的依据。把把 SRHT或或 STHRT，称称为为接接收收码码字字R的的伴伴随随式式(或或监监督子，或校验子督子，或校验子)。 不可检测的错误图样不可检测的错误图样 与码矢相同的错误图样是不可检测的错误图样。与码矢相同的错误图样是不可检测的错误图样。它在数量上与它在数量上与非非零码矢一样多零码矢一样多2k-1个。（含零码为个。（含零码为2k个个)35信道的纠错编码线 性 分 组 码 的 译 码 根据上述原理，我们可知：根据上述原理，我们可知： 伴随式检错原理伴随式检错原理设：设：发送码字发送码字 C(cn1,

27、c n2,c0)，信道的错误图样，信道的错误图样为为E(en1,en2,e0) ， 式式中中：若若ei0，表表示示第第i位位无无错错，若若ei1，则则表表示示第第i位有错，位有错，in1，n2，0。那么，接收码字。那么，接收码字 R =(rn1,rn2,r0) =CE =(cn1+en1，cn2 +en2，c0+e0) 检错译码检错译码基本原理基本原理判为无错（判为无错（可能有错可能有错）一定出错一定出错36信道的纠错编码线 性 分 组 码 的 译 码 将接收字用监督矩阵进行检验，即求接收码字的伴随式：将接收字用监督矩阵进行检验，即求接收码字的伴随式：其中其中H阵用阵用列列来表示，即，来表示，

28、即，所以：所以：ST HRT H(CE)T HCT HET由于由于 HCT 0T，则有：，则有： ST HET 所以，所以，37信道的纠错编码线 性 分 组 码 的 译 码 由上面分析得到如下结论：由上面分析得到如下结论：(1)伴伴随随式式仅仅与与错错误误图图样样有有关关，而而与与发发送送的的具具体体码码字字无无关关，即伴随式仅由错误图样决定。即伴随式仅由错误图样决定。(2)伴伴随随式式是是错错误误的的判判别别式式：若若 S0，则则判判没没有有出出错错，（或或存存在在一一个个不不可可检检测测的的错错误误，接接收收字字是是一一个个码码字字），若若 S0，则判有错。，则判有错。(3)不不同同的的错

29、错误误图图样样具具有有不不同同的的伴伴随随式式，它它们们是是一一一一对对应应的，的，二元码伴随式是二元码伴随式是 H阵中与错误码元对应列之和。阵中与错误码元对应列之和。38信道的纠错编码线 性 分 组 码 的 译 码 例：例：设设(7,3)线性分组码的校验矩阵为线性分组码的校验矩阵为试确定以下三种情况时的译码器的输出试确定以下三种情况时的译码器的输出（1）接收码字）接收码字R=(1010011)，（2）接收码字）接收码字R=(1110011)，（3）接收码字）接收码字R=(0011011)，39信道的纠错编码线 性 分 组 码 的 译 码 解：对于解：对于有：有：传输过程中传输过程中没有没有误

30、码，误码，40信道的纠错编码线 性 分 组 码 的 译 码 对于对于 有：有：，第，第2位出错，位出错，41信道的纠错编码线 性 分 组 码 的 译 码 对于对于 有：有：与与 中的任一列都不相同，中的任一列都不相同，不能确定到底是哪两位出错，不能正确译码。不能确定到底是哪两位出错，不能正确译码。42信道的纠错编码线 性 分 组 码 的 译 码 定理：可纠定理：可纠t个错误的二元线性分组码与校验元个数的关系：个错误的二元线性分组码与校验元个数的关系：三、采用伴随式纠错译码的方法三、采用伴随式纠错译码的方法 查表法查表法 标准阵列法标准阵列法v几个概念几个概念v许用码组：在许用码组：在(n,k)

31、线性码中，与线性码中，与2k个消息码对应的个消息码对应的码字称为许用码组。码字称为许用码组。v禁用码组：在禁用码组：在(n,k)线性码中，除了消息码外的线性码中，除了消息码外的2n-2k个码字。个码字。v标准阵列的构造标准阵列的构造43信道的纠错编码线 性 分 组 码 的 译 码 v先将先将 2k 个码字排成一行，作为个码字排成一行，作为标准阵列标准阵列的第一行，并将的第一行，并将全全0码字码字C0=(000)放在第一行的最左边的位置上；放在第一行的最左边的位置上；v然后在剩下的然后在剩下的 (2n2k) 个个 n 重码中选取一个重码中选取一个重量最轻重量最轻的的 n 重重 E1 放在全放在全

32、0码字码字C0 下面，再将下面，再将 E1分别和各码字相加，分别和各码字相加，放在对应码字下面构成阵列第二行放在对应码字下面构成阵列第二行;v在第二次剩下的在第二次剩下的 n 重码中，选取重量最轻的重码中，选取重量最轻的 n 重重 E2，放，放在在 E1 下面，并将下面，并将 E2 分别加到第一行各码字上，得到第分别加到第一行各码字上，得到第三行；三行；v直到全部直到全部 n 重码字用完为止。得到重码字用完为止。得到 (n,k) 线性码的标准线性码的标准阵列。阵列。 （注意：注意：作为错误图样的作为错误图样的Ei不能与表内的其它码字相同！）不能与表内的其它码字相同！）44信道的纠错编码线 性

33、分 组 码 的 译 码 例：已知例：已知(6,3)线性分组码的生成阵为线性分组码的生成阵为求它的标准阵列。求它的标准阵列。解：由生成阵可得该码许用码组的全部码字：解：由生成阵可得该码许用码组的全部码字：消息码消息码线性分组码线性分组码消息码消息码线性分组码线性分组码00000000010010011000100110110110101101001001111011010101101111011111100045信道的纠错编码线 性 分 组 码 的 译 码 则它的标准阵列为：则它的标准阵列为：000000 001101010011 011110100110101011 110101 111000

34、000001 001100 010010011111100111101010 110100 11100100001000010000100001000010000010000100111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101

35、010011101011110011000010100001100001100146信道的纠错编码线 性 分 组 码 的 译 码 有关标准阵列的几个概念：有关标准阵列的几个概念：v(n，k)线性码的标准阵列有线性码的标准阵列有2k列列(和码矢数相等和码矢数相等)，2n/2k2nk行，且任何两列和两行都没有相同的元素，即列行，且任何两列和两行都没有相同的元素，即列和行都不相交。和行都不相交。v标准阵列的每一行叫做码的一个陪集，每个陪集的第一标准阵列的每一行叫做码的一个陪集，每个陪集的第一个元素叫做个元素叫做陪集首陪集首，信道干扰的错误图样是陪集首信道干扰的错误图样是陪集首。 2nk个陪集首称为可

36、纠正的错误图样。个陪集首称为可纠正的错误图样。v这这2nk个可纠的错误图样，包括个可纠的错误图样，包括 0码矢在内，也就是说，码矢在内，也就是说，把把无错的情况也看成一个可纠的错误图样。无错的情况也看成一个可纠的错误图样。v定理定理：(n,k)线性码可纠线性码可纠2n-k个错误图样。个错误图样。v定理：定理：在标准阵列中，一个陪集的所有在标准阵列中，一个陪集的所有2k个个n重码字有重码字有相同的伴随式，不同陪集的伴随式互不相同。相同的伴随式，不同陪集的伴随式互不相同。v译码原理：译码原理：收到的收到的n 重重R落在某一列中，落在某一列中， 则译码器就译则译码器就译成相应于该列最上面的码字。成相

37、应于该列最上面的码字。 47信道的纠错编码标准阵列译码标准阵列译码=最小距离译码法最小距离译码法=最佳译码法最佳译码法l陪集首是可纠正的错误图样，为了使译码错误概率最小，陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；应选取出现概率最大的错误图样作陪集首；l重量较轻的错误图样出现概率较大，所以在构造标准阵列重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的时是选取重量最轻的 n 重作陪集首；重作陪集首；l这样，当重量较轻的错误图样为陪集首时（可纠的错误图这样，当重量较轻的错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离

38、（等于陪集首）最样），接收矢量与原发送码矢间的距离（等于陪集首）最小；小；l因此，选择重量最轻的元素作陪集首，按标准阵列译码就因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；是按最小距离译码；l所以标准阵列译码法也是最佳译码法。所以标准阵列译码法也是最佳译码法。线 性 分 组 码 的 译 码 48信道的纠错编码线 性 分 组 码 的 译 码 补充习题：补充习题： 已知已知(7,4)线性分组码的生成阵为：线性分组码的生成阵为： 求：该码的全部码字，监督求：该码的全部码字，监督 阵，若接收到码字为阵，若接收到码字为 1001100时，译码器时，译码器 的输出。的输出。 已知已知(8,4)系统线性码的监督方程为：系统线性码的监督方程为： 式中式中m=(m3,m2,m1,m0)，为信息为信息 矢量，矢量，c3,c2,c1,c0，为编码监督为编码监督 字。字。 求：该码的生成阵，监督阵并求：该码的生成阵，监督阵并 证明证明dmin=4。49信道的纠错编码