纠错码Lecture5-线性分组码(II)

1、信道编码理信道编码理邢莉娟、李卓，西安电子科技大学邢莉娟、李卓，西安电子科技大学Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理2修正的线性码修正的线性码扩展码，删余码扩展码，删余码增广码，增余删信码增广码，增余删信码延长码，延长码，Reed-Muller码码线性码的重量分布线性码的重量分布线性码的纠错能力线性码的纠错能力Singleton boundHamming (sphere packing) boundVarshamov-Gilbert boundMcEliece-Rodemich-Rumsey-Welch upper boundLect

2、ure 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理3纠错码的纠错码的设计码长设计码长通常由矩阵或多项式的代数和通常由矩阵或多项式的代数和组合特性决定组合特性决定线性分组码的设计码长通常不等于线性分组码的设计码长通常不等于理想码长理想码长例如：例如：二进制二进制Hamming码的设计码长为码的设计码长为2m-1(7, 15, 31,)修正方法修正方法线性分组码三个参数线性分组码三个参数(n, k, n-k): 增大增大一个参数，一个参数，降低降低另另一个参数，保持第三个参数一个参数，保持第三个参数不变不变。共有共有6种方法种方法Lecture 5 Lectu

3、re 5 线性分组码线性分组码(II)(II)信道编码理信道编码理4基本原理基本原理：对：对n, k, d线性分组码中的每一个码字，线性分组码中的每一个码字，增加一个校验元增加一个校验元 ，满足：，满足： 称为称为全校验位全校验位若若d为为偶数偶数， n, k, d码变成了码变成了n+1, k, d若若d为为奇数奇数， n, k, d码变成了码变成了n+1, k, d+1校验矩阵校验矩阵0c-1-2000nncccc0c11100HHLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理5校验矩阵校验矩阵00n-10i=01110 011 100 +,

4、 TTTTicccc CHCHHCCH0Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理6例子：例子： 7,4,3Hamming码的校验矩阵码的校验矩阵 增加一个全校验位后得到的增加一个全校验位后得到的8, 4 , 4扩展扩展Hamming码的校验矩阵码的校验矩阵011110010110101110001H11111111011110001011010011100010HLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理7基本原理基本原理：在原码基础上删去一个校验元，得到：在原码基础上删去一个校验元，

5、得到n-1, k码。码。是是扩展码的逆过程扩展码的逆过程在软判决译码和纠错纠删码中，将删去的符号看作在软判决译码和纠错纠删码中，将删去的符号看作不可靠不可靠符号符号最小汉明距离最小汉明距离可能比原码小可能比原码小1，也可能不变，也可能不变例如把上例中的例如把上例中的8, 4, 4码的最后一个校验位后，便得到了码的最后一个校验位后，便得到了7, 4, 3Hamming码。此时删余码的校验矩阵可直接从原码。此时删余码的校验矩阵可直接从原码的校验矩阵上删去第码的校验矩阵上删去第1行和最后行和最后1列得到列得到一般的，若删掉的校验位一般的，若删掉的校验位只参与了其中一个校验方程只参与了其中一个校验方程

6、，则，则在原码校验矩阵中在原码校验矩阵中删掉上述校验位对应的行和列删掉上述校验位对应的行和列，即可得，即可得到新码的校验矩阵到新码的校验矩阵Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理8基本原理基本原理在原码基础上，增加一个信息元，删去一个校验元得在原码基础上，增加一个信息元，删去一个校验元得到到 n, k+1, da码码基本实现方法基本实现方法在原码生成矩阵在原码生成矩阵G的基础上，再选择一个与的基础上，再选择一个与G中各行都中各行都不相关的不相关的n维向量，得到新矩阵维向量，得到新矩阵Ga，该矩阵有，该矩阵有n列，列，k+1行，即得到一个

7、行，即得到一个n, k+1, da码码若原码中没有全若原码中没有全1码，可在其码，可在其G矩阵上增加一组全为矩阵上增加一组全为1的的行，得到增广码的生成矩阵为：行，得到增广码的生成矩阵为：GG111a且且da=mind, n-dmax(C)aiCC1Cki2, 2 , 1Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理9生成矩阵生成矩阵最小最小Hamming重量重量 111111 0 1 , 1,2,2 , 1,2,2aaakikimiiCM GMMGGMG1MGC1Cminminmaxmin, (), 1,2,2 min, (), 1,2,2

8、min, -( )kaikidd did did n d1CCCLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理10基本原理基本原理在原码基础上删去一个信息元，增加一个校验元。在原码基础上删去一个信息元，增加一个校验元。和和增广码构造过程相反增广码构造过程相反基本实现方法基本实现方法删掉原码生成矩阵删掉原码生成矩阵G中的一行，得到新矩阵中的一行，得到新矩阵Ge，该矩阵，该矩阵有有n列，列，k-1行，即得到一个行，即得到一个n, k-1, de码码若若n, k, d码的最小汉明距离码的最小汉明距离d为奇数，则挑选所有偶数为奇数，则挑选所有偶数重量的

9、码字，即可构成重量的码字，即可构成n, k-1, d+1增余删信码增余删信码Recall: 任何任何n, k, d线性分组码，码字的重量或全部为线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数偶数，或者奇数重量的码字数等于偶数重量的码字数Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理11延长码延长码对增广码再填加一个全校验位得到对增广码再填加一个全校验位得到n+1, k+1码，此时码，此时码率码率R=(k+1)/(n+1)k/n。和缩短和缩短(Shortened) 码的构造码的构造过程相反过程相反RM码码如果把如果把

10、(2m-1, 2m-1 -m, 3)Hamming码的对偶码，即单纯码的对偶码，即单纯码码(2m-1, m, 2m-1)进行延长，就得到一个进行延长，就得到一个(2m, m+1, 2m-1)码，码，称之为称之为一阶一阶Reed-Muller码码，用，用RM(1, m)表示。表示。一般，一般，r阶阶RM码码RM(r, m)是是2m, k, 2m-r，其中，其中其对偶码为其对偶码为RM(m-r-1, m)码码1; 112121mmmmmmknkrmr Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理12Hadamard变换变换码长为码长为2m ，最小

11、距离为，最小距离为d=2m-r的的RM(r, m)码的生码的生成矩阵由成矩阵由 中的那些重量大于等于中的那些重量大于等于d的行构成的行构成22mmHH21101H41111010100110001H81111111101010101001100110001000100001111000001010000001100000001H2mHLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理13例子：例子：m=3如果以如果以V0到到V3的的4行作为行作为G矩阵的行，则得到一个矩阵的行，则得到一个RM(1, 3)码的生成矩阵码的生成矩阵若以若以V0到到V2

12、V1的的7个矢量作为个矢量作为G矩阵的行，则得到一个矩阵的行，则得到一个RM(2, 3)码的生成矩阵码的生成矩阵0321323121321(11111111) (00001111)(00110011) (01010101)(00000011) (00000101)(00010001) (00000001)VVVVVVVVV VVV VLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理14改变线性码参数改变线性码参数n, k, n-k的任意两个的任意两个 缩短码缩短码Shorten: 删除信息符号删除信息符号 延长码延长码lengthen: 增加信息

13、符号增加信息符号 删余码删余码Puncture: 删除校验符号删除校验符号 扩展码扩展码Expand :增加校验符号增加校验符号 增余删信码增余删信码Expurgate: 删除码字，增加校验符号删除码字，增加校验符号 增广码增广码Augment: 增加码字，删除校验符号增加码字，删除校验符号 fixed, nkkn fixed, nkkn fixed, knkn fixed, knkn fixed, nknk fixed, nknk Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理7,3,4汉明码的各类修正码之间的关系汉明码的各类修正码之间的关系

14、15Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理16码的性能不仅由码的码的性能不仅由码的最小汉明距离最小汉明距离决定，还可由决定，还可由码的码的重量分布重量分布有关有关定义定义设设Ai是是n, k ,d分组码中重量为分组码中重量为i的码字数目，则集合的码字数目，则集合A1, A2, , An称为该分组码的称为该分组码的重量分布重量分布也可以把码的重量分布写成如下的多项式形式也可以把码的重量分布写成如下的多项式形式 称称A(x)为码的为码的重量估值算子重量估值算子，或简称，或简称重量算子重量算子如如 3, 1, 3重复码的重量分布为重复码的重量

15、分布为1, 0, 0, 1，重量算子为，重量算子为010( )nniniiA xAA xA xA x3( )1A xx Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理17Singleton bound n,k,d线性分组码的最大可能的最小距离等于线性分组码的最大可能的最小距离等于n-k+1， 即即 若系统码的最小距离满足若系统码的最小距离满足d=n-k+1,称这类码为极大最称这类码为极大最小距离可分码，简称小距离可分码，简称MDS码。构造码。构造MDS码是编码理论码是编码理论中的一个重要课题。中的一个重要课题。1dnkLecture 5 Lec

16、ture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理18Plotkin bound GF(q)上的上的(n,M,d)分组码的最小距离分组码的最小距离d满足满足 (1)(1)nM qdMqLecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理19Hamming bound 长为长为n纠正纠正t个错误的个错误的q进制分组码的码字数进制分组码的码字数M满足满足0(1)ntiiqMnqi Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理20Varshamov-Gilbert bound若码的校验

17、元数目若码的校验元数目n-k满足满足的最小整数，则一定可以构造出一个长为的最小整数，则一定可以构造出一个长为n，最小距离为，最小距离为d的的n,k线性分组码。线性分组码。221111111122dn knnnqqqqd Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理21Plokin限和限和Hamming限都是必要条件，也就是说限都是必要条件，也就是说任何线性或非线性码都是必需满足的，否则码就任何线性或非线性码都是必需满足的，否则码就构造不出。越接近这个限越有效，等于时码达到构造不出。越接近这个限越有效，等于时码达到最佳。最佳。VG限是充分条件，并限定于线性码，满足这一限是充分条件，并限定于线性码，满足这一条件必存在一个最小距离为条件必存在一个最小距离为d的的n,k线性码。线性码。Lecture 5 Lecture 5 线性分组码线性分组码(II)(II)信道编码理信道编码理当当n时，比较时，比较3个限所表示的个限所表示的n、R、d之间的关之间的关系（只限于二进制码）系（只限于二进制码）当n时由P限可推出由汉明限可得到由V-G限可导出 式中22/1 2 /k nd n 2/