ch7线性分组纠错编码

第七章线性分组纠错编码本章主要内容信道编码的基本概念、原理线性分组（纠错）码的一般概念线性分组（纠错）码的生成矩阵和校验矩阵线性分组（纠错）码的编码线性分组（纠错）码的译码二元Hamming码从一个已知线性分组码来构造一个新的线性分组码信道编码的基本概念信道编码的目的提高信息传输的可靠性（加冗余度）。基本思想

根据一定规律在待发的信息中加入一些多余的码元（监督码元），以保证传输质量。研究内容

怎样构造最小冗余度、最大抗干扰性能的“好码”。检错码纠错码线性码非线性码循环码非循环码纠随机错误码纠突发错误码纠混合错误码纠同步错误码系统码非系统码二元码多元码分组码卷积码信道编码分类信道编码的基本原理香农信道编码定理：R<C，无差错传输。

对于一个给定的有干扰信道，如果信道容量为C，只要发送端以低于C的速率R发送信息(R为编码器输入的二元码元速率)，则一定存在一种编码方法，使编码错误概率p随着码长n的增加，按指数下降到任意小的值。基本原理

在被传输的信息序列上附加一些码元(称为监督码元)，这些多余的码元与信息(数据)码元之间以某种确定的规则相互关联着。接收端根据既定的规则检验信息元与监督元之间的这种关系，如传输过程中发生差错，则信息元与监督元之间的这一关系将受到破坏，从而使接收端可以发现传输中的错误，乃至纠正错误。检错和纠错“好”——0“坏”——1

无检错纠错能力“好”——00“坏”——11

接收：00011011

译出：好？？坏检1位错码，无纠错能力“好”——000“坏”——111

接收：000001010011100101110111

译出：好？？？？？？坏译出：好好好坏好坏坏坏检至少2位错码，或检1位错码并纠正“好”——0000“坏”——1111

接收：00000001001000110100010101100111

译出：好好好？好？？坏接收：10001001101010111100110111101111

译出：好？？坏？坏坏坏检2位错码，并能纠正1位错码线性分组码的基本概念(n,k)线性分组码分组

k个信息元一组变换

n个码元线性监督元与信息元之间呈线性关系分组编码器信源可发出种不同的消息组。

(n,k)分组码共个码字（许用码字），其中只有k个是线性独立的。R=k/n

编码速率/码率

R越小，冗余度就越大，检错和纠错的能力越强；但也降低了传输信息的实际速率。R越大，码的效率也就越高或传信率越高。分组编码器

系统码结构示意图(r=n-k)kbit信息位（n-k）bit监督位分组编码器例：(7，3)线性分组码

设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元可按下式计算：码重：在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming)重量，简称码重。例如“010”码字的码重为1，记为。“011”码字的码重为2，记为码距：把两个码字之间对应码位上具有不同二元码元的位数定义为两码字的汉明距离，简称码距。例如dH(010,011)=1

最小汉明距离：码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以dmin表示；在非零码字中，重量最小者称为该码的最小汉明重量，它等于dmin

。汉明距离三个性质：(1)对称性：d(C1，C2)＝d(C2，C1)；(2)非负性：d(C1，C2)≥0；

(3)满足距离三角不等式：

d(C1，C2)≤d(C1，C3)＋d(C3，C2)。（n，k，dmin）：表示最小距离为dmin，码率为R＝k／n的线性分组码，dmin表示了码的纠错能力。

纠错码的基本任务：构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。

MDS码：(n，k，d)线性分组码的最小距离dmin≤n－k＋1。若系统码的最小距离

dmin＝n－k＋1，则称此码为极大最小距离可分码，简称MDS码。线性分组码的检错和纠错能力结论1.检测e个错码，则要求最小码距

dmin≥e＋1。2.纠正t个错码，则要求最小码距

dmin≥2t＋1。3.纠正t个错码，同时能检测e（e>t）个错码，则要求最小码距

dmin≥e＋t＋1。线性分组码的性质

(1)两个属于该码组码字的和仍是一个属于该码组的码字。

(2)全零码字总是码组中的一个码字。

(3)一个线性码组中两个码字之间的最小距离等于任何非零码字的最小重量。例：已知码组C=｛0000,1010,0101,1111｝是一个分组长度n=4的线性分组码。观察码字之间所有十种可能的和：0000+0000=0000,0000+1010=1010,0000+0101=0101,0000+1111=1111,1010+1010=0000,1010+0101=1111,1010+1111=0101,0101+0101=0000,0101+1111=1010,1111+1111=0000它们都在C中，全零码字也在C中。该码组的最小距离为dmin=2。(线性分组码的3个性质)线性分组码的生成矩阵消息码字若，则称G为(n,k)线性分组码的生成矩阵生成矩阵G与线性分组码是一一对应的。线性分组码的生成矩阵系统码－－码字的前k位与消息完全相同系统码生成矩阵－－例：(7，3)线性分组码

设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元按下式计算，求生成矩阵。已知GF(2)中码生成矩阵分别为：求：G1和G2分别对应的码字空间？线性分组码的监督矩阵在线性分组码（n，k）中，每个码字中r（r＝n－k）个监督元和信息元之间的关系为

H阵的r行代表了r个监督方程，即：

H阵的标准形式

例：(7，3)线性分组码

设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为信息元；c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ci∈GF(2)。监督元按下式计算，求监督矩阵。生成矩阵和监督矩阵的关系线性码的生成矩阵G和监督矩阵H的行矢量彼此正交。对系统码来说结论：系统码的生成矩阵G和监督矩阵H可以互化。对偶码原码CI

（n，k）对偶码CJ

（n，r）生成矩阵

GH监督矩阵

HG原码CI

与对偶码CJ的码字彼此正交。定理两个k×n矩阵,若一个可以由另一个通过一系列下述变换得到，则它们生成的GF(p)上的(n，k)线性码等价：

（1）对行置换；

（2）对行乘以一个非零常量；

（3）把一行乘以一个常量然后加到另一行上；

（4）对列置换；

（5）对任意列乘以一个非零常量。

G（7，3）编出的（7，3）码H（7，4）编出的（7，4）码小结信道编码的目的信道编码定理线性分组码的生成矩阵线性分组码的监督矩阵生成矩阵与监督矩阵的关系对偶码Galois域加法：1.F在加法下封闭，即若a,b2.满足结合律，即若3.满足交换律，即a+b=b+a。4.F中含有一个加法恒元0，满足a+0=a。5.

集合中每个元素a都有一个加法逆元–a，满足a+(–a)=0Galois域乘法：集合F*在乘法下封闭。F*为F除去加法恒元0，记作F*=F-{0}。满足交换律。满足结合律。满足乘加分配律，即(a+b)*c=a*c+b*cF中含有单位元１，对F中任意元素a满足a*1=a。F中任一非零元素a有乘法逆元a–1，满足a*a–1=1。域中元素个数q有限，就称为Galois域，记为GF(q)。Galois域例｛０,1｝就构成了最简单的有限域GF(2)

+01001110*01000101线性分组码的编码(n，k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(n>k)的码字,即先求出信息元和码元之间的关系,再利用此关系构造编码电路。

下面利用监督矩阵来构造(7，3)线性分组码的编码电路。设二元码字为码的监督矩阵为C＝[c6c5c4c3c2c1c0]线性分组码的编码线性分组码的编码++++线性分组码的译码—标准阵列译码线性分组码的译码—标准阵列译码定理假设C是ＧＦ(p)上的一个(n，k)码，则(1)任意长为n的向量b都属于C的某个陪集；

(2)每个陪集恰好包含pk个向量；

(3)两个陪集或者不相交或者完全重合；

(4)若a+C是C的一个陪集，且b∈(a+C)，则b+C=a+C。例:设C为一个二元(3，2)码，其生成矩阵：

码字C=｛000,010,101,111｝。C的标准阵列为：标准阵列译码若接收码字R位于标准阵列的第i行第j列，则将接收码字R译码为cj

，此时的错误图样为陪集首。当且仅当错误图样为陪集首时，译码才是正确的。所以，这2n－k个陪集首称为可纠正的错误图样。标准阵列译码例：已知二元(4,2)线性分组码生成矩阵为

(1)求系统的标准阵列。(2)若接收码字R=［1010］,错误图样E=［0100］,求对应的码字,并判断译码有无错误。(3)若接收码字R=［1010］,错误图样E=［0110］,求对应的码字,并判断译码有无错误。标准阵列译码(1)由生成矩阵可得，系统码组为0000,0111,1001，1110。标准阵列如下：(2)当接收字R＝［1010］时，把R译成码字C＝［1110］。位于第3行的陪集首［0100］是错误图样E，因此译码正确。(3)当接收字R＝［1010］时，把R译成码字C＝［1110］。位于第3行的陪集首［0100］不是错误图样E=［0110］，因此译码不正确。设二元(6，3）码的生成矩阵为(1)若接收码字R=［111011］，错误图样E=［010000］，求对应的码字，并判断译码有无错误。(2)若接收码字R=［100111］，错误图样E=［001100］，求对应的码字，并判断译码有无错误。线性分组码的译码—伴随式译码伴随式定义把S＝RH

T或S

T＝HR

T，称为接收码字R的伴随式(或监督子，或校验子)。错误图样

若ei＝0，表示第i位无错，若ei＝1，则表示第i位有错。伴随式性质①伴随式与发送码字无关，仅与错误图样有关。②伴随式S≠0，表示接收码字有错。如果没有错误出现，则伴随式S＝0。③不同的错误图样有不同的伴随式，即错误图样与伴随式一一对应。线性分组码的译码—伴随式译码伴随式译码步骤1.计算接收码字的伴随式：；2.由伴随式译出接收码字的错误图样；3.译码：。例：已知（7，3）码一致监督矩阵为试对接收码字1010011，1110011，0011011

分别进行译码。线性分组码的译码—伴随式译码对1010011的译码为1010011对1110011的译码为1010011对0011011的不能正确译码，只能发现有错。汉明码是1950年由汉明提出的一种能纠正全部单个错误的线性分组码。汉明码是一种特殊的(n,k,d)线性分组码码长信息位数监督位数最小距离汉明码二进制汉明码参数码长信息位数监督位数最小距离码率【例】构造一个二元的（7，4，3）汉明