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

第9章信道的纠错编码

信道编码的概念

线性分组码

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

按信息码元在编码后是否保持原形式：系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持位置不变。非系统码：信息位打乱，与编码前位置不同。3错误图样⑴当系统无干扰时R=C⑵当系统有干扰时R=C+E其中，E称为信道的错误图样，E=(e0,e1,…,en-1)；ei∈{0,1}；当ei=1，则第i位上有错；反之，无错。例：C=00101101E=01001001R=01100100由信道的对称性可知p(0/1)=p(1/0)=p(e=1)=p反之，若已知R，E则可求出C，这就是纠错码的原理，如：E=01001001R=01100100

C=001011015检错与纠错的原理⒈编码效率设：信息码长度为k，经信道编码后长度为n，则我们定义编码效率R为：R=k/n⒉几种简单的检纠错码奇/偶校验码——检错码重复码——纠错码6检错与纠错方式和能力⒈检纠错方式FEC（前向纠错）——纠错ARQ（自动请求重发）——检错⒉几个概念汉明距离/距离：在线性码中，两个码字U、V

之间对应码元位上符号取值不同的个数，称为码字U、V

之间的汉明距离。例如：(7,3)码的两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U和V的距离为4。线性分组码的一个码字对应于n维线性空间中的一点，码字间的距离即为空间中两对应点的距离。7检错与纠错方式和能力最小码距：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。码字的重量：码字中非0码元符号的个数，称为该码字的重量，又称为汉明重量。码的最小重量：线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量：Wmin=min{W(V),V∈CI

,V≠0}最小码距与最小重量的关系：线性分组码的最小码距等于它的最小重量。8检错与纠错能力--1最小码距与纠错能力的关系：定理：(n,k)线性码能纠t个错误的充要条件是码的最小距离为

dmin=2t

+1或t

=(dmin－1)/2V’9检错与纠错能力--2最小码距与检错能力的关系：定理：(n,k)线性码能够发现e个错误的充要条件是码的最小距离为

dmin=e+1或e=dmin－1V’e10检错与纠错能力--3最小码距与检、纠错能力的关系：定理：(n,k)线性码能纠t个错误，并能发现e个错误

(e>t)的充要条件是码的最小距离为

dmin=t+e+1或t+e=dmin－1eV’V’’11线性分组码

一、线性分组码的描述线性分组码是同时具有分组特性和线性特性的纠错码。定义：一个（n,k）线性分组码C是称为码字c的n维向量的集合。式中：为消息矢量，是一个k行n列的秩为k（n﹥k)的矩阵，我们称它为线性码的生成矩阵。第一种编码方法12线性分组码例：（4,3）偶校验码是一个（4,3）线性分组码，其生成矩阵为

求消息码010，110所对应的线性码。解：13线性分组码将消息码直接代入有：思考：此码是否为系统码？14线性分组码二、线性分组码的性质及定理当消息码为零向量0…0，所得的码字为零码字0…0。

线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。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个码字的一种线性组合，即15线性分组码16线性分组码三、线性分组码的监督阵⒈线性分组码的监督阵编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=n－k)

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

(7,3)分组码编码表

信息组

对应码字

000

0000000

001

0011101

010

0100111

011

0111010

100

1001110

101

101

0011

110

1101001

111

1110100

19线性分组码为了运算方便，将监督方程写成矩阵形式，得:20线性分组码推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定

令上式的系数矩阵为H，码字行阵列为C同样有我们称H为一致监督阵/监督阵。21线性分组码一致监督阵H22线性分组码⒉监督阵与生成阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足Hr×nCTn×1=0Tr×1，则有Hr×nGTn×k=0Tr×k

或

Gk×nHTn×r=0k×r线性分组码的监督矩阵与生成矩阵正交。

23四、(n,k)线性码的对偶码对偶码：对一个(n,k)线性码CI，由于Hr×nGTn×k=0Tr×k，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CId，码CId是一个(n,n－k)线性码，称码CId为原码的对偶码。

例如：(7,4)线性码的对偶码是(7,3)码：(7,3)码的监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4)线性分组码24线性分组码五、生成阵和监督阵的标准形式⒈生成阵的标准形式通过行初等变换，将G化为左边k列是单位子阵的标准形式，我们称之为生成阵的标准形式25线性分组码⒉线性系统分组码用生成阵的标准形式产生的码集合称为线性系统分组码。设：则有：则有：依次排在码的前面监督元依次排在码的后部26线性分组码线性系统分组码：用标准生成矩阵Gk×n

编成的码字，前面k位为信息数字，后面r=n－k位为校验数字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。信息码监督码Cn-1Cn-k

Cn-k-1C027线性分组码例：(7,4)线性码的生成矩阵为110100001101001110010101000174úúúúûùêêêêëé=*G[])1010011(11010000110100111001010100010101)1010(74417141=úúúúûùêêêêëé===****GmCm，则若28线性分组码⒊监督阵的标准形式同样对监督阵的各行进行初等变换，将右边r列化为单位阵即可得到监督阵的标准形式。29线性分组码⒋监督阵与生成阵的转换关系由于系统码的监督阵与生成阵同样彼此正交，所以有：所以，上述等式提供了监督阵与生成阵的互求。即，30线性分组码例：31线性分组码例：二元(7,3)码，若生成矩阵已知，求生成矩阵和监督矩阵的标准形式。解：得：②行和③行相加放入第②行①行和②行相加放入第③行32线性分组码六、线性码的最小距离与监督阵的关系定理1设H为(n,k)线性码的一致监督阵，若H中任意S列线性无关，而存在S+1列线性相关，则码的最小距离为S+1。即，dmin=S+1定理2

若码的最小距离为S+1，则该码的监督阵有任意S列线性无关，而必存在线性相关的S+1列。推理在二元线性码的监督阵H中，如果任一列都不为全零，且任二列都不相等，则该码能纠一个错。例：33线性分组码的译码

一、译码器的任务设：发送的码字C=(cn

-1，cn-2，…，c1，c0)，通过有扰信道传输，信道产生的错误图样E=(en-1,en-2，…,e1,e0)。接收端译码器收到的n重码R=(rn-1,rn-2,…,r1,r0)，其中R=C+E。译码器的任务：根据编码规则和信道特性，对接收码字R

作出判决，此判决过程又称为译码。译码器按任务可分为：检错译码和纠错译码。检错译码：输出接收码字，及差错标志。纠错译码：输出纠正的码字（在纠错能力之内）

输出接收码字及出错标志。（超出纠错能力）

34线性分组码的译码

二、检纠错译码原理⒈伴随式和错误检测用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收码字R后，可用监督矩阵H来检验R是否满足监督方程，即HRT＝0T是否成立。若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此，HRT的值是否为0是检验码字出错与否的依据。把S＝RHT或ST＝HRT，称为接收码字R的伴随式(或监督子，或校验子)。⒉不可检测的错误图样与码矢相同的错误图样是不可检测的错误图样。它在数量上与非零码矢一样多2k-1个。（含零码为2k个)35线性分组码的译码

根据上述原理，我们可知：⒊伴随式检错原理设：发送码字C＝(cn－1,cn－2,…,c0)，信道的错误图样为

E＝(en－1,en－2,…,e0)，式中：若ei＝0，表示第i位无错，若ei＝1，则表示第i位有错，i＝n－1，n－2，…，0。那么，接收码字R=(rn－1,rn－2,…,r0)=C＋E

=(cn－1+en－1，cn－2+en－2，…，c0+e0)检错译码基本原理判为无错（可能有错）一定出错36线性分组码的译码

将接收字用监督矩阵进行检验，即求接收码字的伴随式：其中H阵用列来表示，即，所以：ST＝HRT＝H(C＋E)T＝HCT＋HET由于HCT＝

0T，则有：

ST＝HET

所以，37线性分组码的译码

由上面分析得到如下结论：(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式：若S＝0，则判没有出错，（或存在一个不可检测的错误，接收字是一个码字），若S≠0，则判有错。(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。38线性分组码的译码

例：设(7,3)线性分组码的校验矩阵为试确定以下三种情况时的译码器的输出（1）接收码字R=(1010011)，（2）接收码字R=(1110011)，（3）接收码字R=(0011011)，39线性分组码的译码

解：对于⑴有：传输过程中没有误码，40线性分组码的译码

对于⑵有：，第2位出错，41线性分组码的译码

对于⑶有：与中的任一列都不相同，不能确定到底是哪两位出错，不能正确译码。42线性分组码的译码

定理：可纠t个错误的二元线性分组码与校验元个数的关系：三、采用伴随式纠错译码的方法⒈查表法⒉标准阵列法几个概念许用码组：在(n,k)线性码中，与2k个消息码对应的码字称为许用码组。禁用码组：在(n,k)线性码中，除了消息码外的2n-2k个码字。标准阵列的构造43线性分组码的译码

先将2k个码字排成一行，作为标准阵列的第一行，并将全0码字C0=(00…0)放在第一行的最左边的位置上；然后在剩下的(2n－2k)

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

例：已知(6,3)线性分组码的生成阵为求它的标准阵列。解：由生成阵可得该码许用码组的全部码字：消息码线性分组码消息码线性分组码00000000010010011000100110110110101101001001111011010101101111011111100045线性分组码的译码

则它的标准阵列为：00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000010000100001000010000010000100111100100100010101110110110110110001000101011101101100001111001111001001110001101001011000111011111011111110010010001010111011011000011000011110100110111110001111101101010100101011011111000111110110010100101101010011101011110011000010100001100001100146线性分组码的译码

有关标准阵列的几个概念：(n，k)线性码的标准阵列有2k列(和码矢数相等)，2n/2k＝2n－k行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集，每个陪集的第一个元素叫做陪集首，信道干扰的错误图样是陪集首。2n－k个陪集首称为可纠正的错误图样。这2n－k个可纠的错误图样，包括

0码矢在内，也就是说，把无错的情况也看成一个可纠的错误图样。定理：(n,k)线性码可纠2n-k个错误图样。定理：在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。译码原理：收到的n