信道的纠错编码幻灯片资料

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

1、1,第9章 信道的纠错编码,信道编码的概念 线性分组码 循环码,2,信道编码的纠错原理,信道编码的目的：提高系统的可靠性 实现方法：增加冗余度 信道编码的纠错原理 根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。 在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。 纠错码,3,纠错码的分类,按功能分： 检错码：仅能检测误码。 纠错码：可纠正误码。 按信息码元与监督码元之间的检验关系分： 线性码：满足线性关系。 非线性码：不存在线性

2、关系。 按信息码元在编码后是否保持原形式： 系统码：信息码元与监督码元在分组内有确定位置， 编码后的信息码元保持位置不变。 非系统码：信息位打乱，与编码前位置不同。,5,错误图样, 当系统无干扰时 R=C 当系统有干扰时 R=C+E 其中，E称为信道的错误图样， E=(e0,e1,en-1)；ei 0,1；当ei=1，则第i位上有错；反之，无错。 例： 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，这就是纠错码的原理，如：

3、 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 1,6,检错与纠错的原理, 编码效率 设：信息码长度为k，经信道编码后长度为n，则我们定义编码效率R为： R=k/n 几种简单的检纠错码 奇/偶校验码检错码 重复码纠错码,7,检错与纠错方式和能力, 检纠错方式 FEC（前向纠错）纠错 ARQ （自动请求重发）检错 几个概念 汉明距离/距离：在线性码中，两个码字 U、V 之间对应码元位上符号取值不同的个数，称为码字 U、V 之间的汉明距离。 例如：(7,3) 码的两个码字 U=0011101,V=0100111，它们之间第2、3

4、、4和6位不同。因此，码字 U 和 V 的距离为4。 线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的距离即为空间中两对应点的距离。,8,检错与纠错方式和能力,最小码距：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。 码字的重量：码字中非0码元符号的个数，称为该码字 的重量，又称为汉明重量。 码的最小重量：线性分组码CI中，非0码字重量最小 值，叫做码CI的最小重量： Wmin =minW(V),VCI ,V0 最小码距与最小重量的关系：线性分组码的最小码距 等于它的最小重量。,9,检错与纠错能力-1,最小码距与纠错能力的关系： 定理：(n,k) 线性码能纠

5、t 个错误的充要条件是码的最小距离为 d min =2t + 1 或 t = (d min1)/2,V,10,检错与纠错能力-2,最小码距与检错能力的关系： 定理：(n,k) 线性码能够发现 e个错误的充要条件是码的最小距离为 d min =e + 1 或 e = d min1,11,检错与纠错能力-3,最小码距与检、纠错能力的关系： 定理：(n,k) 线性码能纠 t 个错误，并能发现e 个错误 (e t ) 的充要条件是码的最小距离为 dmin=t +e +1 或 t +e =dmin1,12,线 性 分 组 码,一、线性分组码的描述 线性分组码是同时具有分组特性和线性特性的纠错码。 定义：

6、一个（n,k）线性分组码C是称为码字c的n维向量的集合。 式中： 为消息矢量， 是一个k行n列的秩为k（nk)的矩 阵，我们称它为线性码的生成矩阵。,第一种编码方法,13,线 性 分 组 码,例：（4,3）偶校验码是一个（4,3）线性分组码，其 生成矩阵为 求消息码010，110所对应的线性码。 解：,14,线 性 分 组 码,将消息码直接代入有：,思考：此码是否为系统码？,15,线 性 分 组 码,二、线性分组码的性质及定理 当消息码为零向量00，所得的码字为零码字00。 线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。 G中每一行 gi=(gin-1,gin-2, gi0

7、 ) 都是一个码字； 对每一个信息组m，由矩阵G都可以求得 (n,k) 线性码对应的码字。信息码组长k位，有 2k个不同的信息码组，则有 2k 个码字与它们一一对应。 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g0,g1, gk-1，码Ci 中其它任何码字C都可以表为这 k 个码字的一种线性组合，即,16,线 性 分 组 码,17,线 性 分 组 码,三、线性分组码的监督阵 线性分组码的监督阵 编码就是给已知信息码组按预定规则添加监督码元，以构成码字。 在 k 个信息码元之后附加 r (r=nk) 个监督码元，使每个监督码元是其中某些信息

8、码元的模2和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为 (C6,C5,C4,C3,C2,C1,C0) C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1” 监督元可按下面方程组计算,18,线 性 分 组 码,一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。 由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。,第二种编码方法,19,线 性 分 组 码,信息码组 (101)，即C6=1,

9、 C5=0, C4=1 代入监督方程得： C3=0, C2=0, C1=1, C0=1 由信息码组 (101) 编出的码字为 (1010011)。其它7个码字如下。,20,线 性 分 组 码,为了运算方便，将监督方程写成矩阵形式，得:,21,线 性 分 组 码,推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r (r=nk) 个监督元与信息元之间的关系可由下面的线性方程组确定 令上式的系数矩阵为 H，码字行阵列为 C 同样有 我们称H为一致监督阵/监督阵。,22,线 性 分 组 码,一致监督阵H,23,线 性 分 组 码, 监督阵与生成阵的关系 由于生成矩阵G的每一行都是一个码字，所

10、以G 的每行都满足HrnCTn1=0Tr1，则有 HrnGTnk=0Trk 或 GknHTnr=0kr 线性分组码的监督矩阵与生成矩阵正交。,24,四、(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)码生成矩阵G(7,4),线 性 分 组 码,25,线 性 分 组 码,五、生成阵和监督阵的标准形式 生成阵的标准形式 通过行初等变

11、换，将 G 化为左边 k 列是单位子阵的标 准形式，我们称之为生成阵的标准形式,26,线 性 分 组 码, 线性系统分组码 用生成阵的标准形式产生的码集合 称为线性系统分组码。 设： 则有： 则有：,依次排在码的前面,监督元依次排在码的后部,27,线 性 分 组 码,线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验数字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。,28,线 性 分 组 码,例：(7,4) 线性码的生成矩阵为,29,线 性 分 组 码, 监督阵的标准形式 同样对监督阵的各行进行初等变换，将右边r列化为单位阵即可

12、得到监督阵的标准形式。,30,线 性 分 组 码, 监督阵与生成阵的转换关系 由于系统码的监督阵与生成阵同样彼此正交，所以有： 所以，上述等式提供了监督阵与生成阵的互求。即，,31,线 性 分 组 码,例：,32,线 性 分 组 码,例：二元(7,3)码，若生成矩阵已知，求生成矩阵和监督矩阵的标准形式。 解： 得：,行和行相加放入第行,行和 行相加放入第行,33,线 性 分 组 码,六、线性码的最小距离与监督阵的关系 定理 1 设H为(n,k) 线性码的一致监督阵，若H中任意S列线性无关，而存在S+1列线性相关，则码的最小距离为S+1。 即， dmin=S+1 定理 2 若码的最小距离为S+1

13、，则该码的监督阵有任意S列线性无关，而必存在线性相关的S+1列。 推理 在二元线性码的监督阵H中，如果任一列都不为全零，且任二列都不相等，则该码能纠一个错。 例：,34,线 性 分 组 码 的 译 码,一、译码器的任务 设：发送的码字C=(cn -1，cn -2， ， c1， c0)， 通过有扰信道传输， 信道产生的错误图样E=(en -1, en-2， , e1, e0)。接收端译码器收到的n 重码R=(rn -1, r n -2, r1, r0)， 其中R=C+E。 译码器的任务：根据编码规则和信道特性，对接收码字 R 作出判决，此判决过程又称为译码。 译码器按任务可分为：检错译码和纠错译

14、码。 检错译码：输出接收码字，及差错标志。 纠错译码：输出纠正的码字（在纠错能力之内） 输出接收码字及出错标志。（超出纠错能力）,35,线 性 分 组 码 的 译 码,二、检纠错译码原理 伴随式和错误检测 用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收码字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此，HRT的值是否为0 是检验码字出错与否的依据。 把 SRHT或 STHRT，称为接收码字R的伴随式(或监督子，或校验子)。 不可检测的错误图样 与码矢相同的错误图样是不可检测的错误图样。 它在数量上

15、与非零码矢一样多2k-1个。（含零码为2k个),36,线 性 分 组 码 的 译 码,根据上述原理，我们可知： 伴随式检错原理 设：发送码字 C(cn1,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),检错译码基本原理,判为无错（可能有错）,一定出错,37,线 性 分 组 码 的 译 码,将接收字用监督矩阵进行检验，即求接收码字的伴随式： 其中H阵用列来表示，即， 所以： ST HRT H(CE)T HCT HET 由于 HCT 0T，则有： ST HET 所以，,38,线 性 分 组 码 的 译 码,由上面分析得到如下结论： (1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。 (2)伴随式是错误的判别式：若 S0，则判没有出错，（或存在一个不可检测的错误，接收字是一个码字），若 S0，则判有错。 (3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是 H阵中与错误码元对应列之和。,39,线 性 分 组 码 的 译 码,例：设(7,3)线性分组码的校验矩阵为 试确定以下三种情况时的译码器的输出 （