信道编码理论

1、1线性分组码基本概念线性分组码基本概念码的生成矩阵与校验矩阵码的生成矩阵与校验矩阵对偶码，系统码，缩短码与汉明码对偶码，系统码，缩短码与汉明码标准阵列译码标准阵列译码2定义定义n, k线性分组码是线性分组码是GF(q)上的上的n维线性空间中的一个维线性空间中的一个k维子空间。该子空间在加法运算下构成维子空间。该子空间在加法运算下构成Abelian群，群，所以线性分组码又称群码。若码字的最小距离为所以线性分组码又称群码。若码字的最小距离为d，则记为则记为n, k, d码，码率码，码率R=k / n；或记为；或记为(n, M, d)码，码，其中其中M表示可用码字个数，此时码率表示为表示可用码字个数

2、，此时码率表示为R= (logqM) / n2k2n3例子例子简单重复码简单重复码n, 1, n；简单奇偶校验码简单奇偶校验码n, n-1, 27, 3, 4码码 120nccc, 1,2,icc in信息组码字00000101001110010111011100000000011101010011101110101001110101001111010011110100表表1 7, 3, 4码字码表码字码表4性质性质 n, k, d码中码中d等于非零码字的最小重量，即等于非零码字的最小重量，即 GF(2)上上n, k, d码中，任何两个码字码中，任何两个码字C1，C2之间有如下关系：之间有如下

3、关系： w(C1 + C2)=w(C1)+w(C2)-2w(C1 C2) 或或 d(C1, C2) w(C1)+w(C2) 式中，式中， C1 C2是两个码字的内积。是两个码字的内积。 GF(2)上线性分组码任上线性分组码任3个码字个码字C1，C2 ，C3之间的汉明距离满足：之间的汉明距离满足： d(C1, C3) d(C1, C2) d(C2, C3) 任何任何n, k, d码，码字的重量或全部为偶数，或者奇、偶重量码，码字的重量或全部为偶数，或者奇、偶重量码字数相等。码字数相等。 , min()iiCn kdw C5编码问题编码问题给定参数给定参数n、k，如何根据，如何根据k个信息比特来确

4、定对应的个信息比特来确定对应的n-k个校验比特？个校验比特？利用校验矩阵或生成矩阵。利用校验矩阵或生成矩阵。利用生成矩阵利用生成矩阵由于由于n, k, d线性分组码是一个线性分组码是一个k维线性空间，因此，必维线性空间，因此，必可找到可找到k个线性无关的矢量，能个线性无关的矢量，能张成张成该线性空间。设该线性空间。设 是是k个线性无关的矢量，则对任意的码字个线性无关的矢量，则对任意的码字C，有有G称为该分组码的生成矩阵。称为该分组码的生成矩阵。12,kC CC11221212 , kkTkkmmmm mmCCCCC CCmG6Remarks 生成矩阵生成矩阵G中的每一行都是一个码字；中的每一行

5、都是一个码字； 任意任意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 1G7从线性方程组的角度描述线性分组码从线性方程组的角度描述线性分组码n-k个校验位可用k个已知的信息位表示出来：个校验位个信息位knknknkkn

6、nncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 118000100010001021)(,011, 0, 21, 2, 11, 1ccchhhhhhnnnknknnknknnknknknnkn列行，校验矩阵校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k。以校验矩阵的以校验矩阵的n-k行为基底，可张成一个行为基底，可张成一个n-k维线性子空间。维线性子空间。9

7、例子：表例子：表1的的7, 3, 4码的码的4个校验元可由如下线性个校验元可由如下线性方程组求得：方程组求得：因此，校验矩阵为：因此，校验矩阵为：36542654165406541101111111101011cccccccccccccccc 1011000111010011000100110001H10Remarks校验矩阵的各行之间是线性无关的，即校验矩阵的行校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为秩为n-k；校验矩阵的校验矩阵的n-k行为基底，可张成一个行为基底，可张成一个n-k维线性子空间；维线性子空间；任意一个合法码字任意一个合法码字C均满足均满足 HCT=0T；交换校验矩

8、阵的各列并不影响其纠错能力。交换校验矩阵的各列并不影响其纠错能力。校验矩阵和生成矩阵的关系校验矩阵和生成矩阵的关系校验矩阵校验矩阵H与任意一个码字之积为零，因此有与任意一个码字之积为零，因此有校验矩阵校验矩阵H中各行张成的子空间的零空间即为生成矩阵中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。各行张成的子空间。TTTTH CHG m0HG011定理定理: n, k, d线性分组码最小汉明距离等于线性分组码最小汉明距离等于d的充的充要条件是：要条件是：H的任意的任意d-1列线性无关。列线性无关。Proof . hint: 必要性：采用反证法；充分性：将H中某些d列线性相关的列的系数作

9、为码字中对应的非0分量推论推论: n, k, d线性分组码的线性分组码的最大可能的最小汉明最大可能的最小汉明距离为距离为n-k+1。Proof: 由于校验矩阵H的n-k行是线性无关的，也就是说H的行秩为n-k，从而可推出H的列秩最大是n-k，即H最多有任意n-k列线性无关，由定理得到n-kd-1,有dn-k+1。12对偶码对偶码设n, k, d线性分组码C的生成矩阵为G，校验矩阵为H，以H作为生成矩阵，G为对应的校验矩阵，可构造另一个n, n-k, d线性分组码C1，我们称C1为C的对偶码。系统码系统码缩短码缩短码从n, k, d线性分组码的所有码字中，把前面i位全为零的码字挑选出来构成一个新

10、的子集，该子集即为n, k, d的缩短码。传输时，仅传输后面的n-i位码元，记为n-i, k-i, d码，其纠错能力至少与原n, k, d码相同。kGI PTn k HP I13例子：例子：表表1的的7, 3, 4码：码：0000000，0011101，0100111，0111010，1001110，1010011，1101001，11101006, 2, 4缩短码为：缩短码为： 000000，011101，100111，111010原码和缩短码的生成矩阵分别为：原码和缩短码的生成矩阵分别为：去掉去掉G的第一列第一行，就得到缩短码的生成矩阵的第一列第一行，就得到缩短码的生成矩阵Gs。10111

11、0111001sG101110011100100111001G14原码和缩短码的校验矩阵分别为：原码和缩短码的校验矩阵分别为：对系统码而言，去掉对系统码而言，去掉G的前的前i列和前列和前i行行就可得到缩短码就可得到缩短码的生成矩阵的生成矩阵Gs。去掉校验矩阵的前。去掉校验矩阵的前i列，可得到缩短码列，可得到缩短码的校验矩阵的校验矩阵Hs 。1000110010001100101110001101H100011010001001011000110sH15定义码长：码长： n=2m-1信息位长度：信息位长度： k=2m-1-m码率：码率： R=(n-m) / n最小汉明距离：最小汉明距离：d=3校

12、验矩阵有校验矩阵有 m行，行，2m-1列，取互不相同的列，取互不相同的m重构成。重构成。例子：例子： GF(2)上的上的7,4,3汉明码，汉明码，8个个3重为重为001, 010, 011, 100, 101, 110, 111, 000校验矩阵为：校验矩阵为：000111101100111010101H16伴随式伴随式设发送码字：设发送码字：接收序列：接收序列：根据错误图样的概念，根据错误图样的概念，R=C+E.S 称为称为伴随式（或校正子），伴随式（或校正子），是校验矩阵是校验矩阵H中某几列数中某几列数据的线性组合，因而是据的线性组合，因而是n-k维向量，有维向量，有2n-k种可能。种可能

13、。错误图样错误图样E是是n维向量，共有维向量，共有2n种可能，因而每种可能，因而每2k种错种错误图样对应一种伴随式。误图样对应一种伴随式。021,rrrnnRTTTEHHECRHS)(120,nncccC17例子例子7,3,4码的校验矩阵码的校验矩阵H为：为：错误图样及其相应的伴随式：错误图样及其相应的伴随式：1000110010001100101110001101HE2=(1100000)E3=(0010100)E1=(1000000)S1T=HE1T =(1110)TS2T=HE2T =(1001)TS3T=HE3T =(1001)T18标准阵列步骤标准阵列步骤: 1): 由接收到的序列由

14、接收到的序列R，计算伴随式，计算伴随式S=RHT ； 2): 若若S=0，正确接收；若，正确接收；若S不为零，寻找错误图样；不为零，寻找错误图样； 3): 由错误图样解出码字由错误图样解出码字C=R-E。19C1C2kC2CiE2E3knE2C2+E2C2+E3Ci+E3Ci+E222ECk32ECkknkEC22C2+Ci+knE2knE2码字禁用码字标准阵列译码(陪集首)20标准阵列基本原理标准阵列基本原理:根据许用码字将禁用码字进行分类，分类的依据是错根据许用码字将禁用码字进行分类，分类的依据是错误图样；误图样；关键问题在于如何选择错误图样，使错误概率尽可能关键问题在于如何选择错误图样，

15、使错误概率尽可能小；小；应首先选择重量最轻的错误图样。应首先选择重量最轻的错误图样。21发送端经过发送端经过7,3,4码编码后的码字序列，通过有噪信道后，码编码后的码字序列，通过有噪信道后，在接收端观测到的序列为在接收端观测到的序列为R=(0001110)。采用标准阵列译。采用标准阵列译码估计估计相应的信息序列。码估计估计相应的信息序列。 101100011101000 0 0 1 1 1 011000100110001 1 1 1 0TTSRH当当E1=(1000000)时 S1T=HE1T =(1110)T因此，因此，C=R+E1= (1001110).22完备译码完备译码n, k, d线

16、性分组码的所有线性分组码的所有2n-k个伴随式，在译码过程中个伴随式，在译码过程中若都用来纠正所有小于等于若都用来纠正所有小于等于 个随机错误，个随机错误，以及部分大于以及部分大于t的错误图样，则这种译码方法称为的错误图样，则这种译码方法称为完备完备译码。译码。限定距离译码限定距离译码 任一任一n, k, d码，能纠正码，能纠正 个随机错误。如个随机错误。如果在译码时，仅纠正果在译码时，仅纠正t k/n。和缩短和缩短(Shortened) 码的构造码的构造过程相反。过程相反。RM码码如果把如果把(2m-1, 2m-1 -m, 3)Hamming码的对偶码，即单纯码的对偶码，即单纯码码(2m-1

17、, 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 33Hadamard变换变换码长为码长为2m ，最小距离为，最小距离为d=2m-r的的RM(r, m)码的生码的生成矩阵由成矩阵由 中的那些重量大于等于中的那些重量大于等于d的行构成。的行构成。22mmHH21101H4111101010011

18、0001H81111111101010101001100110001000100001111000001010000001100000001H2mH34例子：例子：m=3如果以如果以V0到到V3的的4行作为行作为G矩阵的行，则得到一个矩阵的行，则得到一个RM(1, 3)码的生成矩阵；码的生成矩阵；若以若以V0到到V2 V1的的7个矢量作为个矢量作为G矩阵的行，则得到一个矩阵的行，则得到一个RM(2, 3)码的生成矩阵。码的生成矩阵。0321323121321(11111111) (00001111)(00110011) (01010101)(00000011) (00000101)(00010

19、001) (00000001)VVVVVVVVV VVV V35改变线性码参数改变线性码参数n, k, n-k的任意两个的任意两个 Shorten: 删除信息符号删除信息符号 lengthen: 增加信息符号增加信息符号 Puncture: 删除校验符号删除校验符号 Expand :增加校验符号增加校验符号 Expurgate: 删除码字，增加校验符号删除码字，增加校验符号 Augment: 增加码字，删除校验符号增加码字，删除校验符号 fixed, nkkn fixed, nkkn fixed, knkn fixed, knkn fixed, nknk fixed, nknk 36 汉明码的

20、各类修正码之间的关系图 37码的性能不仅由码的码的性能不仅由码的最小汉明距离最小汉明距离决定，还与码决定，还与码的的重量分布密切相关。重量分布密切相关。定义：定义：设设Ai是是n, k ,d分组码中重量为分组码中重量为i的码字数目，则集合的码字数目，则集合A0, A1, , An称为该分组码的称为该分组码的重量分布。重量分布。也可以把码的重量分布写成如下的多项式形式也可以把码的重量分布写成如下的多项式形式: 称称A(x)为码的为码的重量估值算子重量估值算子，或简称，或简称重量算子。重量算子。如如 3, 1, 3重复码的重量分布为重复码的重量分布为1, 0, 0, 1，重量算子为，重量算子为01

21、0( )nniniiA xAA xA xAx3( )1.A xx 38 定理定理: 设二进制设二进制n， k线性分组码及其线性分组码及其 n，n-k对偶码的重量算子分别是：对偶码的重量算子分别是： iiniiinixBxBxAxA00)()(则它们之间有如下关系： xxBxxAnkn11)1 (2)()(称此式为马克威伦( MacWilliams)恒等式。 39等重码：等重码： 除了一个全除了一个全0码字外，其余码字的重量都相等。码字外，其余码字的重量都相等。 例：汉明码的对偶码例：汉明码的对偶码2m-1, m, 2m-1.信息组码字000001010011100101110111000000

22、00011101010011101110101001110101001111010011110100表表1 7, 3, 4码字码表码字码表40任何一个二进制任何一个二进制n，k，d线性分组码的码字集合线性分组码的码字集合中，必有一个全中，必有一个全0码字码字;如果还有一个全如果还有一个全1码字的话，则由于线性码的封闭码字的话，则由于线性码的封闭性，该码的重量分布必是性，该码的重量分布必是对称对称的。的。 例：例：7, 4, 3汉明码，汉明码，Ai=1, 0, 0, 7, 7, 0, 0, 1.41根据不同的译码方法和译码器，一般译码错误根据不同的译码方法和译码器，一般译码错误概率分为概率分为不

23、可检错误概率不可检错误概率、译码失败概率译码失败概率和和译译码错误概率码错误概率。 42码字通过码字通过BSC传输时，传输时， 若由于干扰变成了另一若由于干扰变成了另一码字，码字， 则检错译码器就不能发现此种类型的错则检错译码器就不能发现此种类型的错误，误， 产生了产生了不可检错误不可检错误。码长为码长为n， 有有M个码字，个码字， 最小距离为最小距离为d的的(n， M， d)二进制分组码的平均不可检错误概率二进制分组码的平均不可检错误概率:,11(1)Mnin iudjj ieejiPPA pp43Aj, i是与第是与第j个码字的距离为个码字的距离为i的码字数。的码字数。 设设Aj(x)=A

24、j, 0+Aj, 1 x+Aj, 2 x2+Aj, nxn j=1, 2, , M.是是(n, M, d)码中第码中第j个码字的个码字的距离分布多项式距离分布多项式。若对码中所有码字恒有若对码中所有码字恒有 Aj(x)=A(x)=A0+A1x+A2x2+Anxn 则此码称为则此码称为不变距离分布码不变距离分布码或或同距离分布码同距离分布码。 44对线性码而言，对线性码而言， 由于码的封闭性，由于码的封闭性， 可知是同可知是同距离分布码，距离分布码， 且码的距离分布就等于码的重量且码的距离分布就等于码的重量分布。分布。 对对n, k, d二进制线性分组码的不可检错误二进制线性分组码的不可检错误概

25、率为概率为:ineieinijjudppAPPk)1 (121若码字等概发送， 则上式成为 ineieiniudppAP)1 (145定理定理: 二进制二进制n, k线性分组码集合中，线性分组码集合中， 码码的平均不可检错误概率的平均不可检错误概率:)1 (1 (2)(keknudpP式中， pe是BSC的误码率。 通常情况下， 1-(1-pe)k1， 所以 ()2n kudP最佳检错码最佳检错码46如果如果n, k, d码的译码器，码的译码器， 用来纠用来纠t个错误，个错误， 同时检测同时检测e个错误，个错误， 则称为则称为teD译码器。译码器。 此时要求此时要求dt+e+1， et; 0eD是纯检错译码器，是纯检错译码器， 这时这时ed-1； t0D是纯纠错译码器，是纯纠错译码器， 此时此时t(d-1)2。 teD译码器是一类限定距离译码器。译码器是一类限定距离译码器。 teD译码器正确译码的码字概率译码器正确译码的码字概率:ineieticppinP)1 (0这里及以后pe均指BSC的误码率， 且码字等概发送。 47译码中，若译码中，若teD译码器输出的码字与发送的码译码器输出的码字与发送的码字不相同，则产生了字不相同，则产生了译码错误译码错误。 如果译码器不能译出码字，如果译码器不能译出码字， 而仅指出