纠错码Lecture4-线性分组码(I)

Lecture4

线性分组码(I)2内容基本概念生成矩阵与校验矩阵对偶码、系统码、缩短码汉明码、极长码伴随式与标准阵列译码3基本概念线性分组码：

一个[n,k]线性分组码,是把信息划成k个码元为一段(称为信息组),通过编码器变成长为n个码元的一组，作为[n,k]线性分组码的一个码字。若每位码元的取值有q种(q为素数幂),则共有qk个码字。n长的数组共有qn组，在二进制情况下，有2n个数组。显然，qn个n维数组(n重)组成一个GF(q)上的n维线性空间。如果qk(或2k)个码字集合构成了一个k维线性子空间，则称它是一个[n,k]线性分组码。4线性分组码[n,k]线性分组码是GF(q)上的n维线性空间Vn中的一个k维子空间Vn,k。由于该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为群码。通常用[n,k,d]或[n,k]，而[n,M,d]表示码字数目为M的任何码，此时码率R=n-1logqM。5线性分组码简单重复码[n,1,n]；简单奇偶校验码[n,n-1,2][7,3,4]码(汉明码的对偶码)

信息组码字00000101001110010111011100000000011101010011101110101001110101001111010011110100表1[7,3,4]码字码表6线性分组码的性质

[n,k,d]线性分组码的最小距离等于非零码字的最小重量。GF(2)上[n,k,d]线性分组码中，任何两个码字C1，C2之间有如下关系：

w(C1

+C2)=w(C1)+w(C2)-2w(C1·C2)

或

d(C1,C2)≤w(C1)+w(C2)其中C1·C2

是两个码字的内积。7线性分组码的性质GF(2)上线性分组码任3个码字C1，C2，C3之间的汉明距离，满足以下三角不等式d(C1,C3)≤d(C1,C2)＋d(C2,C3)任何[n,k,d]线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数。8码的生成矩阵编码问题给定参数n、k，如何根据k个信息比特来确定n-k个校验比特？利用校验矩阵或生成矩阵利用生成矩阵由于[n,k,d]线性分组码是一个k维线性空间，因此，必可找到k个线性无关的矢量，能张成该线性空间。设C1，C2,…,Ck是k个线性无关的矢量，则对任意的码字C，有称为该分组码的生成矩阵9码的生成矩阵Remarks生成矩阵G中的每一行都是一个码字任意k个线性独立的码字都可以作为生成矩阵给定一个[n,k,d]线性分组码，其生成矩阵可有多个

表1中的[7,3,4]码，可从8个码字中任意挑k=3个线性无关的码字作为码的生成矩阵10码的校验矩阵从线性方程组的角度描述线性分组码n-k个校验位可用k个已知的信息位表示出来11码的校验矩阵校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k以校验矩阵的n-k行为基底，可张成一个n-k维线性子空间12码的校验矩阵例子：表1的[7,3,4]码(P5)的4个校验元可由如下线性方程组求得因此，校验矩阵为13码的校验矩阵Remarks校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k校验矩阵的n-k行为基底，可张成一个n-k维线性子空间任意一个合法码字C均满足HCT=0T交换校验矩阵的各列并不影响其纠错能力校验矩阵和生成矩阵的关系校验矩阵H与任意一个码字之积为零，因此有校验矩阵H中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。14最小汉明距离定理:[n,k,d]线性分组码最小汉明距离等于d的充要条件是：H的任意d-1列线性无关Proof.[hint:必要性：采用反证法；充分性：将H中某些d列线性相关的列的系数作为码字中对应的非0分量]推论:[n,k,d]线性分组码的最大可能的最小汉明距离为n-k+1Proof:由于校验矩阵H的n-k行是线性无关的，也就是说H的行秩为n-k，从而可推出H的列秩最大是n-k，即H最多有任意n-k列线性无关，由定理得到n-k≥d-1,有d≤n-k+115对偶码对偶码：设[n,k,d]线性分组码C的生成矩阵为G，校验矩阵为H,以H作为生成矩阵,G为对应的校验矩阵,可构造另一个[n,n-k,d]线性分组码C1,我们称C1为C的对偶码。

[7,3,4]码的对偶码必是[7,4,3]码，其生成矩阵G[7,4]就是[7,3,4]码的校验矩阵H[7,3]。16系统码系统码：若信息组以不变的形式在码组的任意k位（通常在最前面:cn-1,cn-2,…,cn-k）中出现的码称为系统码，否则为非系统码。

G=[IkP](前k位为信息位，后n-k位为校验位)

H=[-PTIn-k]（-PT是P矩阵的转置）系统码的特点：系统码的编码相对而言比较简单，且由G可以方便的得到H（反之亦然），容易检查编出的码字是否正确。同时，对分组码而言，系统码与非系统码的纠错能力完全等价。

17缩短码缩短码:在[n,k,d]码的码字集合中，挑选前i个信息位数字均为0的所有码字，组成一个新的子集。由于该子集的前i位信息位均取0，故传输时可以不送它们，仅只要传送后面的n-i位码元即可。这样该子集组成了一个[n-i,k-i,d]分组码，称它为[n,k,d]码的缩短码。缩短码的特点：由于缩短码是k维子空间Vn,k中取前i位均为0的码字组成的一个子集，显然该子集是Vn,k空间中的一个k-i维的子空间Vn,k-i，因此[n-i,k-i,d]缩短码的纠错能力至少与原[n,k,d]码相同。18缩短码表1的[7,3,4]码：0000000，0011101，0100111，0111010，1001110，1010011，1101001，1110100[6,2,4]缩短码为：000000，011101，100111，111010原码和缩短码的生成矩阵分别为去掉G的第一列第一行，就得到缩短码的生成矩阵Gs19缩短码原码和缩短码的校验矩阵分别为对系统码而言，去掉G的前i列和前i行就可得到缩短码的生成矩阵Gs。去掉校验矩阵的前i列，可得到缩短码的校验矩阵Hs。20汉明码

要纠正一个错误的[n,k,d]分组码，要求其H矩阵中至少两列线性无关，且不能全为0。若为二进制码，则要求H矩阵中每列互不相同，且不能全为0。一个[n,k,d]分组码有n-k位检验元，在二进制码情况下，这n-k个校验元能组成2n-k列不同的n-k重，其中有2n-k-1列不全为0。所以用这2n-k-1列作为H矩阵的每一列，则由此H就产生了一个纠正单个错误的[n,k,3]码，它就是汉明码。21汉明码

GF(2)上汉明码的H矩阵的列，是由不全为0，且互不相同的二进制m重组成。该码有如下参数：n=2m-1，k=2m-1-m，R=(2m-1-m)/(2m-1)，d=3。

构造GF(2)上的[7,4,3]汉明码，这时取m=3，所有23=8个三重为：001,010,011,100,101,110,111,000。挑出其中7个非0的三重构成校验矩阵为：22汉明码

可以把GF(2)上的汉明推广到GF(q)上，得到多进制汉明码，此时码有如下参数：码长：n=(qm-1)/(q-1)信息位：k=n-m码率：R=(n-m)/n最小距离：d=3二进制[2m-1，2m-1-m，3]汉明码的对偶码是一个[2m-1，m，2m-1]码，也称为单纯码或极长码。

23伴随式伴随式设发送码字接收序列根据错误图样的概念，R=C+ES是校验矩阵H中某几列数据的线性组合，因而是n-k维向量，有2n-k种可能错误图样E是n维向量，共有2n种可能，因而每2k种错误图样对应一种伴随式。24伴随式式中，hn-i为H矩阵的第i列，它是一个n-k重列矢量。表示第i1，i2,...,it

位有错。25伴随式

S是H矩阵中相应于eij

≠0（j=1,2，…，t）的那几列hn-ij的线性组合，由于hn-ij是n-k重列矢量，故S也是一个n-k重的矢量（s1，s2，…，sn-k)。若没有错误，所有si=0,则S是一个零矢量。26伴随式[7,3,4]码的校验矩阵H为错误图样及其相应的伴随式E2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T=(1110)TS2T=HE2T=(1001)TS3T=HE3T=(1001)T27重要的结论一个[n,k,d]线性分组码，若要纠正≤t个错误，则其充要条件是H矩阵中任何2t列线性无关。由于d=2t+1，所以也相当于要求H矩阵中d-1列线性无关。[n,k,d]线性分组码有最小距离等于d的充要条件是，H矩阵中任意d-1列线性无关。(singleton限)[n,k,d]线性分组码的最大可能的最小距离等于n-k+1，即d≤n-k+1。MDS码：若系统码的最小距离d=n-k+1,则称此码为极大最小距离可分码，简称MDS码。28标准阵列译码标准阵列步骤1):

由接收到的序列R，计算伴随式S=RHT；2):若S=0，正确接收；若S不为零，寻找错误图样；3):由错误图样解出码字C=R-E。标准阵列基本原理根据许用码字将禁用码字进行分类，分类的依据是错误图样。关键问题在于如何选择错误图样，使错误概率尽可能小应首先选择重量最轻的错误图样,这样的安排使得每一列中的元素与列首的码字间距离最小，称为最小距离译码，在BSC下，等效与最大似然译码。29标准阵列译码C1C2…Ci……………………E2E3C2+E2C2+E3Ci+E3Ci+E2C2+Ci+码字禁用码字标准阵列译码(陪集首)30标准阵列译码发送端经过[7,3,4]码编码后的码字序列，通过有噪信道后，在接收端观测到的序列为R=(0001110)。采用标准阵列译码估计估计相应的信息序列。

当E1=(1000000)时S1T=HE1T=(1110)T因此，C=R+E1=(1001110)31标准阵列译码码字000000（陪集首）100110010011001111110101101001011100111010禁用码组1000000001101100111011110101010010011111000110100100001101100000110111111001011110010011001010100010001011100110110001111111011000010101001100100001001000100101