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

1、信道编码理论信道编码理论 邢莉娟，李卓，西安电子科技大学邢莉娟，李卓，西安电子科技大学Lecture 4Lecture 4 信道编码理论信道编码理论 2基本概念基本概念生成矩阵与校验矩阵生成矩阵与校验矩阵对偶码、系统码、缩短码对偶码、系统码、缩短码汉明码、极长码汉明码、极长码伴随式与标准阵列译码伴随式与标准阵列译码Lecture 4Lecture 4 信道编码理论信道编码理论 3线性分组码线性分组码 ： 一个一个 n, k 线性分组码线性分组码 , 是把信息划成是把信息划成 k 个码元为一段个码元为一段(称为信息组称为信息组),通过编码器变成长为通过编码器变成长为 n 个码元的一组，作为个码元

2、的一组，作为n, k 线性分组码的一个码字。若每位码元的取值有线性分组码的一个码字。若每位码元的取值有 q 种种( q 为素数幂为素数幂) , 则共有则共有 qk 个码字。个码字。n 长的数组共有长的数组共有 qn 组，组，在二进制情况下，有在二进制情况下，有 2n 个数组。个数组。 显然，显然，qn 个个 n 维数组维数组( n重重)组成一个组成一个GF(q)上的上的 n 维线维线性空间。如果性空间。如果 qk (或或 2k)个码字集合构成了一个个码字集合构成了一个 k 维线性子维线性子空间，则称它是一个空间，则称它是一个 n, k 线性分组码。线性分组码。Lecture 4Lecture

3、4 信道编码理论信道编码理论 4n, k线性分组码是线性分组码是 GF(q)上的上的 n维线性空间维线性空间 Vn 中中的一个的一个 k 维子空间维子空间 Vn,k。由于该线性子空间在加法运算下构成阿贝尔群，由于该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为群码。所以线性分组码又称为群码。通常用通常用 n, k, d 或或 n, k，而，而 n, M, d 表示码字数表示码字数目为目为 M 的任何码，此时码率的任何码，此时码率 R=n-1logqM。Lecture 4Lecture 4 信道编码理论信道编码理论 5u 简单重复码n, 1, n；u 简单奇偶校验码n, n-1, 2u

4、 7, 3, 4码(汉明码的对偶码) 120nccc, 1,2,icc in信息组信息组码字码字00000101001110010111011100000000011101010011101110101001110101001111010011110100表表1 7, 3, 4码字码表码字码表Lecture 4Lecture 4 信道编码理论信道编码理论 6 n, k, d 线性分组码的最小距离等线性分组码的最小距离等于非零码字的最小重量。GF(2)上上n, k, d线性分组码中，任何两个码字线性分组码中，任何两个码字C1，C2之间有如下关系：之间有如下关系： w(C1 + C2)=w(C1)

5、+w(C2)-2w(C1 C2) 或 d(C1, C2) w(C1)+w(C2)其中其中 C1 C2 是两个码字的内积。是两个码字的内积。 , min()iiCn kdw CLecture 4Lecture 4 信道编码理论信道编码理论 7GF(2)上线性分组码任上线性分组码任 3 个码字个码字C1，C2 ，C3 之间之间的汉明距离，满足以下三角不等式的汉明距离，满足以下三角不等式 d(C1, C3) d(C1, C2) d(C2, C3) 任何任何 n, k, d 线性分组码，码字的重量或全部为线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码偶数，或者奇数重量的码字数

6、等于偶数重量的码字数。字数。Lecture 4Lecture 4 信道编码理论信道编码理论 8编码问题编码问题 给定参数n、k，如何根据k个信息比特来确定n-k个校验比特？ 利用校验矩阵或生成矩阵利用生成矩阵利用生成矩阵 由于n, k, d线性分组码是一个k维线性空间，因此，必可找到k个线性无关的矢量，能张成该线性空间。设 C1，C2 ,Ck是k个线性无关的矢量，则对任意的码字C，有11221212 , kkTkkmmmm mmCCCCC CCmG称为该分组码的生成矩阵称为该分组码的生成矩阵GLecture 4Lecture 4 信道编码理论信道编码理论 9Remarks 生成矩阵G中的每一行

7、都是一个码字 任意k个线性独立的码字都可以作为生成矩阵 给定一个n, k, d线性分组码，其生成矩阵可有多个 表表 1 中的中的7, 3, 4码，可从码，可从8个码字中任意挑个码字中任意挑 k = 3个线个线性无关的码字作为码的生成矩阵性无关的码字作为码的生成矩阵1 0 0 1 1 1 00 1 0 0 1 1 10 0 1 1 1 0 1G1 1 1 0 1 0 00 1 0 0 1 1 10 0 1 1 1 0 1GLecture 4Lecture 4 信道编码理论信道编码理论 10从线性方程组的角度描述线性分组码从线性方程组的角度描述线性分组码n-k个校验位可用k个已知的信息位表示出来个

8、校验位个信息位knknknkknnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 11Lecture 4Lecture 4 信道编码理论信道编码理论 11000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校验矩阵校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k以校验矩阵

9、的以校验矩阵的n-k行为基底，可张成一个行为基底，可张成一个n-k维线性子空间维线性子空间Lecture 4Lecture 4 信道编码理论信道编码理论 12例子：表例子：表1的的7, 3, 4码码(P5)的的4个校验元可由如下个校验元可由如下线性方程组求得线性方程组求得因此，校验矩阵为因此，校验矩阵为36542654165406541101111111001011cccccccccccccccc 1011000111010011000100110001HLecture 4Lecture 4 信道编码理论信道编码理论 13Remarks校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k校

10、验矩阵的n-k行为基底，可张成一个n-k维线性子空间任意一个合法码字C均满足 HCT=0T交换校验矩阵的各列并不影响其纠错能力校验矩阵和生成矩阵的关系校验矩阵和生成矩阵的关系校验矩阵H与任意一个码字之积为零，因此有校验矩阵H中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。TTTTmH CHG0HG0Lecture 4Lecture 4 信道编码理论信道编码理论 14定理定理: n, k, d线性分组码最小汉明距离等于线性分组码最小汉明距离等于d的充的充要条件是：要条件是：H的任意的任意d-1列线性无关列线性无关Proof . hint: 必要性：采用反证法；充分性：将必要性：采用反证

11、法；充分性：将H中某中某些些d列线性相关的列的系数作为码字中对应的非列线性相关的列的系数作为码字中对应的非0分量分量推论推论: n, k, d线性分组码的线性分组码的最大可能的最小汉明最大可能的最小汉明距离为距离为n-k+1Proof: 由于校验矩阵由于校验矩阵H的的n-k行是线性无关的，也就是行是线性无关的，也就是说说H的行秩为的行秩为n-k，从而可推出，从而可推出H的列秩最大是的列秩最大是n-k，即，即H最多有任意最多有任意n-k列线性无关，由定理得到列线性无关，由定理得到n-kd-1,有有dn-k+1Lecture 4Lecture 4 信道编码理论信道编码理论 15对偶码：对偶码：设设

12、 n, k, d 线性分组码线性分组码 C 的生成矩阵为的生成矩阵为 G，校验，校验矩阵为矩阵为 H,以以 H 作为生成矩阵作为生成矩阵, G 为对应的校验矩阵为对应的校验矩阵,可构可构造另一个造另一个 n, n-k, d 线性分组码线性分组码C1,我们称我们称 C1 为为 C 的对偶的对偶码。码。 7,3,4码的对偶码必是码的对偶码必是7,4,3码，其生成矩阵码，其生成矩阵G7,4就是就是7,3,4码的校验矩阵码的校验矩阵H7,3。7,47,31011000111010011000100110001GHLecture 4Lecture 4 信道编码理论信道编码理论 16系统码：系统码：若信息

13、组以不变的形式在码组的任意若信息组以不变的形式在码组的任意k位（通常位（通常在最前面在最前面 : cn-1 , cn-2 , , cn-k）中出现的码称为系统码，否）中出现的码称为系统码，否则为非系统码。则为非系统码。G = IkP (前前 k 位为信息位，后位为信息位，后 n-k 位为校验位位为校验位) H = -PTIn-k （-PT 是是 P 矩阵的转置）矩阵的转置）系统码的特点系统码的特点 ：系统码的编码相对而言比较简单，且由系统码的编码相对而言比较简单，且由G可以方便的得到可以方便的得到 H（反之亦然），容易检查编出的码字是（反之亦然），容易检查编出的码字是否正确。同时，对分组码而言

14、，系统码与非系统码的纠错否正确。同时，对分组码而言，系统码与非系统码的纠错能力完全等价。能力完全等价。 Lecture 4Lecture 4 信道编码理论信道编码理论 17缩短码缩短码 : 在在 n, k, d 码的码字集合中，挑选前码的码字集合中，挑选前 i 个信息位个信息位数字均为数字均为 0 的所有码字，组成一个新的子集。由于该子集的所有码字，组成一个新的子集。由于该子集的前的前 i 位信息位均取位信息位均取 0 ，故传输时可以不送它们，仅只要，故传输时可以不送它们，仅只要传送后面的传送后面的 n-i 位码元即可。这样该子集组成了一个位码元即可。这样该子集组成了一个n-i, k-i, d

15、 分组码，称它为分组码，称它为 n, k, d 码的缩短码。码的缩短码。缩短码的特点缩短码的特点 ：由于缩短码是由于缩短码是 k 维子空间维子空间 Vn,k中取前中取前 i 位位均为均为 0 的码字组成的一个子集，显然该子集是的码字组成的一个子集，显然该子集是 Vn,k空间中空间中的一个的一个 k-i 维的子空间维的子空间 Vn,k-i，因此，因此 n-i, k-i, d 缩短码的纠缩短码的纠错能力至少与原错能力至少与原 n, k, d 码相同。码相同。Lecture 4Lecture 4 信道编码理论信道编码理论 18表表1的的7, 3, 4码：码：0000000，0011101，01001

16、11，0111010，1001110，1010011，1101001，11101006, 2, 4缩短码为：缩短码为： 000000，011101，100111，111010原码和缩短码的生成矩阵分别为原码和缩短码的生成矩阵分别为去掉去掉G的第一列第一行，就得到缩短码的生成矩阵的第一列第一行，就得到缩短码的生成矩阵Gs100111011101sG100111001001110011101GLecture 4Lecture 4 信道编码理论信道编码理论 19原码和缩短码的校验矩阵分别为原码和缩短码的校验矩阵分别为对系统码而言，去掉对系统码而言，去掉G的前的前i列和前列和前i行就可得到缩短码行就可

17、得到缩短码的生成矩阵的生成矩阵Gs。去掉校验矩阵的前。去掉校验矩阵的前i列，可得到缩短码列，可得到缩短码的校验矩阵的校验矩阵Hs。1000110010001100101110001101H011000110100100010110001sHLecture 4Lecture 4 信道编码理论信道编码理论 20u 要纠正一个错误的要纠正一个错误的 n, k, d 分组码，要求其分组码，要求其 H 矩阵中矩阵中至少两列线性无关，且不能全为至少两列线性无关，且不能全为 0。若为二进制码，则要。若为二进制码，则要求求 H 矩阵中每列互不相同，且不能全为矩阵中每列互不相同，且不能全为 0。u 一个一个 n

18、, k, d 分组码有分组码有 n-k 位检验元，在二进制码情位检验元，在二进制码情况下，这况下，这 n-k 个校验元能组成个校验元能组成 2n-k 列不同的列不同的 n-k 重，其中重，其中有有2n-k-1列不全为列不全为0。所以用这。所以用这 2n-k-1 列作为列作为 H 矩阵的每一矩阵的每一列，则由此列，则由此 H 就产生了一个纠正单个错误的就产生了一个纠正单个错误的n, k, 3码，码，它就是汉明码。它就是汉明码。Lecture 4Lecture 4 信道编码理论信道编码理论 21u GF(2)上汉明码的上汉明码的 H 矩阵的列，是由不全为矩阵的列，是由不全为 0，且互不，且互不相同

19、的二进制相同的二进制 m 重组成。该码有如下参数：重组成。该码有如下参数：n=2m-1，k=2m-1-m，R=(2m-1-m)/(2m-1)，d=3。u 构造构造GF(2)上的上的7, 4, 3汉明码，这时取汉明码，这时取m=3，所有，所有23=8个三重为：个三重为：001, 010, 011, 100, 101, 110, 111, 000。挑出其。挑出其中中7个非个非 0 的三重构成校验矩阵为：的三重构成校验矩阵为：000111101100111010101HLecture 4Lecture 4 信道编码理论信道编码理论 22u 可以把可以把 GF(2) 上的汉明推广到上的汉明推广到 GF

20、(q) 上，得到多进制上，得到多进制汉明码，此时码有如下参数：汉明码，此时码有如下参数： 码码 长：长： n=(qm-1)/(q-1) 信信 息息 位：位： k=n-m 码码 率：率： R=(n-m) / n 最小距离：最小距离： d=3u 二进制二进制 2m-1，2m-1-m，3汉明码的对偶码汉明码的对偶码 是一个是一个2m-1，m，2m-1码，也称为单纯码或极长码。码，也称为单纯码或极长码。 HC Lecture 4Lecture 4 信道编码理论信道编码理论 23伴随式伴随式设发送码字接收序列根据错误图样的概念，R=C+ES是校验矩阵H中某几列数据的线性组合，因而是n-k维向量，有2n-

21、k种可能错误图样E是n维向量，共有2n种可能，因而每2k种错误图样对应一种伴随式。021,rrrnnRTTTEHHECRHS)(120,nncccCLecture 4Lecture 4 信道编码理论信道编码理论 241,11,21,11,02,12,22,12,01210,1,2,1,0nnnnnnn k nn k nn kn khhhhhhhhhhhhHhhh h1210123(,)(0,0,0,0,0,0)nniiiiteee eeeeeEu 式中，式中，hn-i为为 H 矩阵的第矩阵的第 i 列，它是一个列，它是一个n-k重列矢量。重列矢量。u 表示第表示第 i1 ，i2 , . , i

22、t 位有错。位有错。Lecture 4Lecture 4 信道编码理论信道编码理论 25u S是是 H 矩阵中相应于矩阵中相应于eij 0（j=1,2，t）的）的那几列那几列 hn-ij 的线性组合，由于的线性组合，由于 hn-ij 是是 n-k重列矢量，重列矢量，故故 S 也是一个也是一个n-k重的矢量（重的矢量（s1，s2，sn-k)。若没。若没有错误，所有有错误，所有 si=0 ,则则 S 是一个零矢量。是一个零矢量。1212101122000nniiitiiiiititeeeeeehhSEHhhhhh Lecture 4Lecture 4 信道编码理论信道编码理论 267,3,4码的校

23、验矩阵H为错误图样及其相应的伴随式1000110010001100101110001101HE2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T =(1110)TS2T=HE2T =(1001)TS3T=HE3T =(1001)TLecture 4Lecture 4 信道编码理论信道编码理论 27一个一个 n, k, d 线性分组码，若要纠正线性分组码，若要纠正 t个错误，则其充要个错误，则其充要条件是条件是 H 矩阵中任何矩阵中任何 2t 列线性无关。由于列线性无关。由于 d=2t+1，所以，所以也相当于要求也相当于要求 H 矩阵中矩阵中 d-1列线性无关

24、。列线性无关。n, k, d 线性分组码有最小距离等于线性分组码有最小距离等于 d的充要条件是，的充要条件是，H 矩阵中任意矩阵中任意 d-1 列线性无关。列线性无关。(singleton限限) n, k, d 线性分组码的最大可能的最小距离线性分组码的最大可能的最小距离等于等于n-k+1，即，即 d n-k+1。MDS 码码 ：若系统码的最小距离：若系统码的最小距离 d=n-k+1, 则称此码为极大则称此码为极大最小距离可分码，简称最小距离可分码，简称 MDS 码。码。Lecture 4Lecture 4 信道编码理论信道编码理论 28标准阵列步骤标准阵列步骤 1): 由接收到的序列R，计算

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