信道的纠错编码.ppt
1,第9章 信道的纠错编码,信道编码的概念 线性分组码 循环码,2,信道编码的纠错原理,信道编码的目的：提高系统的可靠性实现方法：增加冗余度信道编码的纠错原理 根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。纠错码,3,纠错码的分类,按功能分：检错码：仅能检测误码。纠错码：可纠正误码。按信息码元与监督码元之间的检验关系分：线性码：满足线性关系。非线性码：不存在线性关系。按信息码元在编码后是否保持原形式：系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持位置不变。非系统码：信息位打乱，与编码前位置不同。,4,纠错码的分类,按信息码元与监督码元之间的约束方式不同分：分组码：将信息码元分为k位一组，每组相互独立，再按编码规则变成n位码（nk)，其中n-k=r位为监督码元，我们称之为（n,k)分组码。本码组的监督码元仅和本码组的信息码元相关。卷积码：本码组的监督码元不仅和本码组的信息码元相关，而且与前面码组的信息码元有关。,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，这就是纠错码的原理，如：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和6位不同。因此，码字 U 和 V 的距离为4。线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的距离即为空间中两对应点的距离。,8,检错与纠错方式和能力,最小码距：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。码字的重量：码字中非0码元符号的个数，称为该码字 的重量，又称为汉明重量。码的最小重量：线性分组码CI中，非0码字重量最小 值，叫做码CI的最小重量：Wmin=minW(V),VCI,V0最小码距与最小重量的关系：线性分组码的最小码距 等于它的最小重量。,9,检错与纠错能力-1,最小码距与纠错能力的关系：定理：(n,k)线性码能纠 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,线 性 分 组 码,一、线性分组码的描述线性分组码是同时具有分组特性和线性特性的纠错码。定义：一个（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)都是一个码字；对每一个信息组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)个监督码元，使每个监督码元是其中某些信息码元的模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,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的每一行都是一个码字，所以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,线 性 分 组 码,五、生成阵和监督阵的标准形式 生成阵的标准形式通过行初等变换，将 G 化为左边 k 列是单位子阵的标准形式，我们称之为生成阵的标准形式,26,线 性 分 组 码,线性系统分组码用生成阵的标准形式产生的码集合 称为线性系统分组码。设：则有：则有：,依次排在码的前面,监督元依次排在码的后部,27,线 性 分 组 码,线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验数字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。,28,线 性 分 组 码,例：(7,4)线性码的生成矩阵为,29,线 性 分 组 码,监督阵的标准形式同样对监督阵的各行进行初等变换，将右边r列化为单位阵即可得到监督阵的标准形式。,30,线 性 分 组 码,监督阵与生成阵的转换关系由于系统码的监督阵与生成阵同样彼此正交，所以有：所以，上述等式提供了监督阵与生成阵的互求。即，,31,线 性 分 组 码,例：,32,线 性 分 组 码,例：二元(7,3)码，若生成矩阵已知，求生成矩阵和监督矩阵的标准形式。解：得：,行和行相加放入第行,行和 行相加放入第行,33,线 性 分 组 码,六、线性码的最小距离与监督阵的关系定理 1 设H为(n,k)线性码的一致监督阵，若H中任意S列线性无关，而存在S+1列线性相关，则码的最小距离为S+1。即，dmin=S+1定理 2 若码的最小距离为S+1，则该码的监督阵有任意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 作出判决，此判决过程又称为译码。译码器按任务可分为：检错译码和纠错译码。检错译码：输出接收码字，及差错标志。纠错译码：输出纠正的码字（在纠错能力之内）输出接收码字及出错标志。（超出纠错能力）,35,线 性 分 组 码 的 译 码,二、检纠错译码原理 伴随式和错误检测 用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收码字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此，HRT的值是否为0 是检验码字出错与否的依据。把 SRHT或 STHRT，称为接收码字R的伴随式(或监督子，或校验子)。不可检测的错误图样 与码矢相同的错误图样是不可检测的错误图样。它在数量上与非零码矢一样多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)线性分组码的校验矩阵为试确定以下三种情况时的译码器的输出（1）接收码字R=(1010011)，（2）接收码字R=(1110011)，（3）接收码字R=(0011011)，,40,线 性 分 组 码 的 译 码,解：对于有：,传输过程中没有误码，,41,线 性 分 组 码 的 译 码,对于 有：,，第2位出错，,42,线 性 分 组 码 的 译 码,对于 有：,与 中的任一列都不相同，,不能确定到底是哪两位出错，不能正确译码。,43,线 性 分 组 码 的 译 码,定理：可纠t个错误的二元线性分组码与校验元个数的关系：三、采用伴随式纠错译码的方法 查表法 标准阵列法几个概念许用码组：在(n,k)线性码中，与2k个消息码对应的码字称为许用码组。禁用码组：在(n,k)线性码中，除了消息码外的2n-2k个码字。标准阵列的构造,44,线 性 分 组 码 的 译 码,先将 2k 个码字排成一行，作为标准阵列的第一行，并将全0码字C0=(000)放在第一行的最左边的位置上；然后在剩下的(2n2k)个 n 重码中选取一个重量最轻的 n 重 E1 放在全0码字C0 下面，再将 E1分别和各码字相加，放在对应码字下面构成阵列第二行;在第二次剩下的 n 重码中，选取重量最轻的 n 重 E2，放在 E1 下面，并将 E2 分别加到第一行各码字上，得到第三行；直到全部 n 重码字用完为止。得到(n,k)线性码的标准阵列。（注意：作为错误图样的Ei不能与表内的其它码字相同！）,45,线 性 分 组 码 的 译 码,例：已知(6,3)线性分组码的生成阵为求它的标准阵列。解：由生成阵可得该码许用码组的全部码字：,46,线 性 分 组 码 的 译 码,则它的标准阵列为：,000000,001101,010011,011110,100110,101011,110101,111000,000001,001100,010010,011111,100111,101010,110100,111001,000010,000100,001000,010000,100000,100001,001111,001001,000101,011101,101101,101100,010001,010111,011011,000011,110011,110010,011100,011010,010110,001110,111110,111111,100100,100010,101110,110110,000110,000111,101001,101111,100011,111011,010101,001010,110111,110001,111101,100101,001011,010100,111010,111100,110000,101000,011000,011001,47,线 性 分 组 码 的 译 码,有关标准阵列的几个概念：(n，k)线性码的标准阵列有2k列(和码矢数相等)，2n/2k2nk行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集，每个陪集的第一个元素叫做陪集首，信道干扰的错误图样是陪集首。2nk个陪集首称为可纠正的错误图样。这2nk个可纠的错误图样，包括 0码矢在内，也就是说，把无错的情况也看成一个可纠的错误图样。定理：(n,k)线性码可纠2n-k个错误图样。定理：在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。译码原理：收到的n 重R落在某一列中，则译码器就译成相应于该列最上面的码字。,48,标准阵列译码=最小距离译码法=最佳译码法陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的 n 重作陪集首；这样，当重量较轻的错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；所以标准阵列译码法也是最佳译码法。,线 性 分 组 码 的 译 码,49,线 性 分 组 码 的 译 码,补充习题：已知(7,4)线性分组码的生成阵为：求：该码的全部码字，监督 阵，若接收到码字为 1001100时，译码器 的输出。已知(8,4)系统线性码的监督方程为：式中m=(m3,m2,m1,m0)，为信息 矢量，c3,c2,c1,c0，为编码监督 字。求：该码的生成阵，监督阵并 证明dmin=4。,
