1、信息论与编码理论第8章 信道编码8.1 信道编码的基本概念8.1.1 编译码规则、检纠错能力信源编码信道编码目的压缩，通过去除信源冗余实现纠错，通过引入冗余实现主要指标平均码长平均错误译码概率影响主要指标的因素编码方法编码方法、译码方法编译码之间的关系一个编码方法对应一个译码方法，译码是编码的逆过程一个编码方法可能对应多个译码方法，在这多个译码方法中有一个能使平均错误译码概率最小例子n例8-1：奇偶校验码具有检错能力n例8-2：要传送A和B两个消息n例8-2-1：-0、B-1此时没有冗余当接收到010011时译码为ABAABB无法发现接收到的字符串中是否有错误例8-2续n例8-2-2：-00、
2、B-11此时有1位冗余，称为监督位（监督元、校验元）监督位（监督元、校验元）当接收到010011时会发现无法译码（01）具有检错能力“01”和“10”称为禁用码字禁用码字，而“00”和“11”称为许用码字许用码字n例8-2-3：-000、B-111此时有2位冗余当接收到010011时，会发现出现了禁用码子（010、011）具有检错能力无论000010，还是111010，均可判断出现错误因此可以检检2位错位错如果按照“大数法则”译码则译码结果为AB具有纠错能力如果000010，可正确译码为A；如果111010，不能正确译码，即该错误不能被正确纠正过来因此只能纠纠1位错位错8.1.2 平均错误译码
3、概率n例：二进制对称信道传递矩阵例：二进制对称信道传递矩阵 ，先不考虑编，先不考虑编码码n如果译码规则为如果译码规则为00、11，则，则0和和1被正确译码的概率均为被正确译码的概率均为1/4，即系统的平均正确译码概率为，即系统的平均正确译码概率为1/40和和1被错误译码的概率均为被错误译码的概率均为3/4，即系统的平均错误译码概率为，即系统的平均错误译码概率为3/4n如果译码规则为如果译码规则为01、10，则，则0和和1被正确译码的概率均为被正确译码的概率均为3/4，即系统的平均正确译码概率为，即系统的平均正确译码概率为3/40和和1被错误译码的概率均为被错误译码的概率均为1/4，即系统的平均
4、错误译码概率为，即系统的平均错误译码概率为1/4n由此可见，译码规则的设计也是非常重要的由此可见，译码规则的设计也是非常重要的n平均错误译码概率平均错误译码概率Pe为错误译码概率的均值为错误译码概率的均值nPe是衡量译码方法好坏的一个重要指标，所选择的译码规是衡量译码方法好坏的一个重要指标，所选择的译码规则应该使则应该使Pe尽可能小。尽可能小。13443144P 1()neieiiPp x pPe与编码规则有关n例例 信源符号等概分布，信道矩阵为信源符号等概分布，信道矩阵为n如果不经过编码直接传输，译码规则为如果不经过编码直接传输，译码规则为00、11n则平均错误译码概率为则平均错误译码概率为
5、0.01n如果引入冗余，将如果引入冗余，将“0”编码为编码为“000”，“1”编码为编码为“111”，译码规则为，译码规则为000,001,010,1000、111,110,101,0111n则平均错误译码概率为则平均错误译码概率为0.990.010.010.99P3211()20.013 0.010.990.00032sejejjPp bp 8.2 译码规则译码规则n定义定义8-2 选择译码函数选择译码函数F(y)=x*，使之满足，使之满足np(y|x*)p(x*)=p(y|xi)p(xi)n则称为极大似然译码规则。则称为极大似然译码规则。n信道矩阵，输入等概信道矩阵，输入等概n则极大似然译
6、码则极大似然译码216131312161613121P332211)()()(xyFxyFxyF8.3 信道编码定理n定理定理8-1 有噪信道编码定理（香农第二定理）有噪信道编码定理（香农第二定理）n对于一个给定的离散无记忆信道，信道容量为对于一个给定的离散无记忆信道，信道容量为C，如果信息传输率如果信息传输率Rt)个错码，则要求个错码，则要求最小码距为最小码距为dmine+t+18.4.4 生成矩阵和监督矩阵n接前例 即n设C=(c6,c5,c4,c3,c2,c1,c0)，M=(c6,c5,c4)，即C是码字，M是信息，则编码规则可以表示为n即C=MG，其中n称为生成矩阵生成矩阵c3=c6+
7、c4c2=c6+c5+c4c1=c6+c5c0=c5+c4 c6=c6c5=c5c4=c4c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4 6543210654100111001001110011101cccccccccc100111001001110011101G生成矩阵n在(n,k)线性分组码中,每个码字C都可以表示为CMGn则G是该(n,k)线性分组码的生成矩阵，即n生成矩阵G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用n生成矩阵的每一行都是一个码子111212122212nnkkknggggggGggg生成矩阵不惟一n不同的生成矩阵可能生成相同的码字空
8、间12101011100110110101,010011111000001101GG这两个码的检错和这两个码的检错和纠错能力一样纠错能力一样但是但是G2是系统码，是系统码，G1是非系统码是非系统码系统码的编译比较系统码的编译比较简单，而性能与非简单，而性能与非系统码一样，因此系统码一样，因此系统码得到了广泛系统码得到了广泛的应用和研究的应用和研究系统码的生成矩阵系统码的生成矩阵可以表示为可以表示为GIk PIk-kk阶单位方阶单位方阵阵监督矩阵n在线性分组码在线性分组码(n,k)中，如果中，如果矩阵矩阵H使得对使得对任意码子任意码子C都有下式成立都有下式成立n则则H称为称为(n,k)线性码的线
9、性码的一致监督矩阵一致监督矩阵(或或校验矩阵校验矩阵)n其中其中TTT00HCCH111212122212nnrrrnhhhhhhHhhh监督矩阵的标准形式n对H各行实行初等变换，将后r列化为单位子阵:nHQ Irn这种形式的 H称为监督矩阵H的标准形式n例：(7,3)分组码，监督矩阵的标准形式为1011000111010011000100110001H生成矩阵与监督矩阵的关系生成矩阵与监督矩阵的关系n一般关系：HGT 0T 或 GHT 0n例n系统码的生成矩阵与监督矩阵标准形之间的关系（G=Ik P、H=Q Ir）：nPQT 或 Q=PTn例100111001001110011101GT10
10、00101011000000001111010000010111000100001110110001000110011HG1011000111010011000100110001H8.4.5 对偶码n对一个(n,k)线性码CI，由于 HGT 0T，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CJnCJ是一个(n,n-k)线性码，称为 CI的对偶码n例：(7,3)码的生成矩阵和监督矩阵为n则将两个矩阵的作用对换，得到对偶码(7,4)码的生成矩阵和监督矩阵为n经过变换后为(7,3)100111001001110011101G(7,3)1011000111010011000100110001
11、H(7,4)100111001001110011101H(7,4)1011000111010011000100110001G(7,4)111010001110101101001H(7,4)1000101010011100101100001011G(7,3)码和(7,4)码6.3.3 伴随式及错误检测n伴随式（监督子，校验子）对接收码字R，用监督矩阵H来检验R是否满足监督方程，即HRT0T是否成立若HRT0T成立，则认为R是一个码字，否则判为码字在传输中发生了错误把SRHT或或STHRT，称为接收码字R的伴随式(或监督子，或校验子)n伴随式的错误图样表示设发送码字C(cn-1，cn-2，c0)，
12、而接收到的码子为R(rn-1,rn-2,r0)，则定义E(en1，en2，e0)=R-C，为信道的错误图样错误图样 若ei0，表示第i位无错，若ei1，则表示第i位有错则此时伴随式为ST HRT H(CE)T HCT+HET HET h1en1h2en2+hne0，这叫做伴随式的错误图样表示n由此可以得出结论伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定伴随式是错误的判别式：若S0，则判没有出错，接收字是一个码字，若S0，则判有错二元码伴随式是二元码伴随式是H阵中与错误码元对应列之和阵中与错误码元对应列之和伴随式译码的基本过程例n设(7，3)码的监督矩阵为 ，可纠1位
13、错n发送码字 C(1010011)1011000111010011000100110001H接收到的码子R(1010011)接收码字 R的伴随式为译码器判接收字无错，即传输中没有发生错误101011000111101000011000100011000111TTTSHR 接收到的码子R(1110011)接收码字 R的伴随式为ST0，译码器判为有错(7，3)码是纠单个错误的码，且ST等于H的第二列，因此判定接收码字R的第二位是错的，因此译码为(1010011)由于接收字中错误码元数与码的纠错能力相符，所以译码正确111011000011110100101100010100110001111TTS
14、HR 伴随式例（续）n接收码字 R(0011011)码元错误多于1个n其伴随式为nST不等于0，但与H阵的任何一列都不相同，无法判定错误出在哪些位上，即此时只能发现有错001011000011110100111100010100110001011TTSHR 伴随式例2n(15,7)码的生成矩阵和监督矩阵分别为n该码可以纠正2位错n发送码字C(101001100101110)n接收码字R=(111101100101110)nST不等于0，H阵的第2、4列的和相同，因此错误出现在第2、4位上，码字可以纠正为(101001100101110)10001011100010111000101110001
15、011100010111000101110001011100010111000101111001111111011010111011110110001010110010010110100010111H111110001011001100111111111011011101110111001011000110010110010100101101000001011111110TTSHR 111010001111010001111010001111010001111010001111010001111010001G8.4.7 汉明码n汉明码是1950年由汉明提出的一种能纠正单个错误的线性分组码n它不
16、仅性能好而且编译码电路非常简单，易于工程实现，因此是工程中常用的一种纠错码n二元汉明码的参数n，k和d分别为码长：n=2r-1信息位数：k=2r-r-1监督位数：r=n-k最小码距：dmin=3n由于dmin=3，因此能纠正1个随机错误或检测2个错误汉明码的构造n汉明码的监督矩阵H的列为所有非零的列为所有非零的r维向量维向量组成，所以一旦r给定，就可构造出具体的(n，k)汉明码n例：构造一个二元的（7,4,3）汉明码由于r=7-4=3因此H中共有23-1=7列将该监督矩阵进行行列交换行列交换，得到监督矩阵的标准形式HQ Ir这种行列交换，对码的性能没有影响。此时得到的汉明码为系统汉明码系统汉明
17、码。000111101100111010101H011110010110101101001H8.5 循环码n循环码是一类最主要、最有用的线性分组码n1957年普朗格(Prange)首先开始研究循环码n循环码具有许多优良的性质，在理论和实践中都是十分重要的8.5.1 循环码的基本概念n设设C是一个是一个(n,k)线性码线性码n如果如果C中的中的任意一个码字经任意循环移位之后仍任意一个码字经任意循环移位之后仍然是然是C中的一个码字中的一个码字，那么就称此码是一个循环，那么就称此码是一个循环码码n循环左移与循环右移是等价的循环左移与循环右移是等价的n循环左移循环左移i位等于循环右移位等于循环右移n-
18、i位位n因此可以默认循环移位为循环左移因此可以默认循环移位为循环左移n码字码字C=(cn1,cn2,c1,c0)循环移位循环移位i位之后为位之后为nC(i)(cni1,cni2,c0,cn1,cni1,cni)循环码例8.5.2 循环码的生成多项式和监督多项式n码字的多项式设码字C=(cn1,cn2,c1,c0)，用各个分量作为系数，可以写出一个多项式C(x)=cn-1xn1cn-2xn2c1xc0则C(x)就是相应码字的多项式码字的多项式码字C与多项式C(x)是一一对应的n码字循环移位之后，码字多项式的变化：C1的多项式C1(x)=x5+x4+x3+xC2的多项式C2(x)=x6+x5+x4
19、+x2C3的多项式C3(x)=x6+x5+x3+1三者的关系为C2(x)=xC1(x)=C1(1)(x)，C3(x)=x2C1(x)mod(x7+1)=C1(2)(x)n这表明C(i)C(i)(x)C(i)(x)xiC(x)mod(xn1)左移左移循环循环循环码的多项式举例循环码的多项式举例n(7，3)循环码可由任一个码字，比如循环码可由任一个码字，比如0011101经过循经过循环移位，得到其他环移位，得到其他6个非个非0码字码字n(7，3)循环码也可由码多项式循环码也可由码多项式x4+x3x21，乘以，乘以xi，再再模模x71得到其他得到其他6个非个非0码多项式码多项式生成多项式n循环码可由
20、一个非零码字经过循环移位得到其他非0码字n因此在(n，k)循环码的2k个码多项式中，只要给出一个就可以推得其它n选择其中前k-1位皆为0的码多项式g(x)(次数rn-k)，这个多项式叫做(n，k)循环码的生成多项式生成多项式g(x)gnk xnkgnk1xnk1 g1xg0生成多项式的构造n分解xn+1，其中次数为n-k的因式就是生成多项式n例（7,3）循环码的生成多项式nx7+1=(x+1)(x3+x2+1)(x3+x+1)n因此生成多项式为：ng(x)=(x+1)(x3+x2+1)=x4+x2+x+1n或者ng(x)=(x+1)(x3+x+1)=x4+x3+x2+1监督多项式监督多项式n如
21、果g(x)为(n，k)循环码的生成多项式，则必为xn1的因式，因此xn1h(x)g(x)n如果多项式h(x)满足xn1h(x)g(x)，且hk1,h0，则称h(x)为(n，k)循环码的监督多项式监督多项式nh(x)hkxkhkxkh1xh0n对偶码以n-k次多项式g(x)为生成多项式，则生成一个(n，k)循环码以h(x)为生成多项式，则生成(n，n-k)循环码这两个循环码互为对偶码生成矩阵生成矩阵n(n,k)循环码的生成多项式循环码的生成多项式g(x)经经k-1次循环移位次循环移位，共得到共得到k个码多项式：个码多项式：n g(x)，xg(x)，xk1g(x)n这这k个码多项式的系数可作为个码
22、多项式的系数可作为生成矩阵生成矩阵G(x)的的k行行，即即110200().().().().1()knn kkn kn kxg xggxxg xggG xxxg xggg x生成矩阵举例生成矩阵举例3643253242365432654326543265432()()()()()1101100001011000010110000011x g xxxxx g xxxxG xxg xxxxg xxxxxxxxxxxxxxxxxxxxxxxxxxxn设设(7,4)循环码循环码的生成多项式的生成多项式g(x)x3x1，求其生成矩阵求其生成矩阵G及生成的码字及生成的码字1011000010110000
23、101100001011G监督矩阵监督矩阵n(n，k)循环码的监督多项式为循环码的监督多项式为nh(x)hkxkhkxkh1xh0n则则(n，k)循环码的循环码的监督矩阵监督矩阵为为011011011000000kkkkkkhhhhhhhhHhhhh 循环码的监督矩阵举例循环码的监督矩阵举例n(7，3)码：x71(x3x1)(x4x2x1)n4次多项式为生成多项式：ng(x)x4x2x1g4x4g3x3g2x2g1xg0n3次多项式则是监督多项式：nh(x)x3x1h3x3h2x2h1xh0n则生成矩阵和监督矩阵分别为(7,3)101110001011100010111G(7,3)000110
24、1001101001101001101000H8.5.3 循环码的译码n循环码的译码包括三个步骤计算伴随式求伴随式对应的错误图样用错误图样纠错（译码）n相比于一般线形分组码，循环码的译码更加简单易行伴随式n一般线性分组码的伴随式（矩阵形式）：S=RHT或ST=HRTn这对循环码也是适用的n循环码伴随式的特殊求法（多项式形式）(P157)nS(x)R(x)mod g(x)n即循环码的伴随式是接收多项式R(x)除以g(x)的余式循环码译码例n设设(7,4)循环码循环码的生成多项式的生成多项式g(x)x3x1，一，一个码字为个码字为0001011，若接收到的码字为，若接收到的码字为1001011，则
25、则nR(x)=x6+x3+x+1nS(x)R(x)mod g(x)=x2+1，即S=1 0 1Tn而而h(x)=x4+x2+x+1，即，即n因此码字的第因此码字的第1位出错，译码为位出错，译码为0001011，正确译，正确译码码001110111010010111010011101011101001110100H8.5.4 BCH码nBCH码是迄今为止所发现的一类性能较优的码n是纠随机错误的循环码nBCH码的纠错能力很强，且构造方便，对它的分析研究也很透彻nBCH的历史1959年霍昆格姆(Hocgenghem)和1960年博斯(Bose)及查德胡里(Chaudhuri)分别提出的纠正多个随机错
26、误的循环码，称为BCH码1960年彼得森(Pelerson)找到了二元BCH码的第一个有效算法，后经多人的推广和改进1967年由伯利坎普(Berlekamp)提出了BCH码译码的迭代算法，从而将BCH码由理论研究推向实际应用阶段，使它成为应用广泛而有效的一类线性码BCH码的基本参数码的基本参数n对任何正整数m(3)和t(2m-1)，存在一个二元BCH码，具有下面的参数码长：n=2m-1一致校验位的数目：n-kmt最小码距：dmin2t+1能纠正n=2m-1个码元中任意不超过t个错误n即给定符合条件m3、t2m-1的m和t之后，总能设计出一个二元BCH，满足码长为2m-1，并能纠正t个随机错误。
27、BCH码的定义ng(x)是一个循环码的生成多项式，如果g(x)=0的根中包括2t个连续根,2,3,2t，则由g(x)生成的循环码叫做BCH码。n此时g(x)=(x-)(x-2)(x-2t)=0n如何构造出满足该条件的生成多项式g(x)是比较困难的，有兴趣的同学可以自学部分常用BCH码的生成多项式nktg(x)（八进制）74113151112315727211553246731261453121235513116310765731115542332531673133650473126175635711031011000010110000101100001011G10001010100111001
28、01100001011G111010001110101101001H如果信息元为如果信息元为1101，则对应的，则对应的码字为码字为1101001如果接收到的码字为如果接收到的码字为1101000，则伴随式为则伴随式为001，是监督矩阵的，是监督矩阵的最后一列，则译码结果为最后一列，则译码结果为11010018.5.5 RS码n里德-索罗蒙（Reed-Solomon）码，简称RS码nRS码是q元BCH码编码方式类似RS码是以数据块进行编码n例如如果q=4，数据块的长度就是2如果q=8，数据块的长度就是3nRS码即可以纠随机错误，又可以纠突发错误8.6 卷积码n1955年埃里亚斯(Elias)最
29、早提出卷积码的概念n卷积码(又称连环码)指的是 在任意给定时刻，编码器输出的 n0个码元中，每一个码元不仅和此时刻 输入的k0个信息元有关，还与前面连续m0个时刻输入的信息元有关，可以用（n0,k0,m0）表示n典型的卷积码一般选较小的n0和k0(k0n0)，但存储器数m0则取较大的值(m010)n卷积码的编码效率为Rk0/n0n在同样的编码效率R下，卷积码的性能优于分组码，至少不低于分组码n但是卷积码不像分组码有严格的代数结构，至今没有严密的数学手段将纠错能力与码的结构十分有规律的联系起来。8.6.2 卷积码的编码n设卷积码编码器输入码序列为nU=u0(1)u0(2)u0(k0)u1(1)u
30、1(2)u1(k0)us(1)us(2)us(k0)n编码器输出码序列为nC=c0(1)c0(2)c0(n0)c1(1)c1(2)c1(n0)cs(1)cs(2)cs(n0)n则非系统码的编码为n系统码的编码为 即前k0*k0个n其中g(i,j)=g0(i,j)g1(i,j)gm0(i,j)是卷积码的生成序列，共有k0*n0个生成序列，每个序列的长度为m0+1比特，它的作用与线性分组码中的生成矩阵类似，表明如何由信息元构成校验元。000001001()()(,)()(,),1,2,kmmkss tts ttittiCjui g i jui g i jjn00000100001()(),1,2,
31、()()(,)()(,),1,sskmss ttitmks ttticjujjkcjui g i jui g i jjkn001(,),(,)0,00tijkg i jg i jtij卷积码编码例n(3,1,2)系统卷积码n则n0=3，k0=1，m0=2nU=us-2(1)us-1(1)us(1)n因此它有3个生成序列g(1,1)、g(1,2)、g(1,3)，他们的值分别为ng(1,1)=100ng(1,2)=110ng(1,3)=101n则编码方法为210220(1)(1)(2)(1)(1,2)(1)(1)(3)(1)(1,3)(1)(1)ssss ttsstss ttsstcucuguuc
32、uguu卷积码编码例n(3,2,2)系统卷积码n则n0=3，k0=2，m0=2nU=us-2(1)us-2(2)us-1(1)us-1(2)us(1)us(2)n因此它有6个生成序列g(1,1)、g(1,2)、g(1,3)、g(2,1)、g(2,2)、g(2,3)，他们的值分别为ng(1,1)=100，g(2,2)=100 ng(1,2)=000，g(2,1)000ng(1,3)=g0(1,3)g1(1,3)g2(1,3)=101ng(2,3)=g0(2,3)g1(2,3)g2(2,3)=110n该码的任一子码Cs为222110(1)(1)(2)(2)(3)()(,3)(1)(1)(2)(2)
33、ssssss ttssssitcucucui g iuuuu8.6.3 卷积码的矩阵表述n生成矩阵n其中 叫做基本生成矩阵n例 （3,1,2）卷积码，g0=111，g1=010，g2=001，则n若信息序列为nU=1011010100n则输出码字序列为n111 010 110 101 011 000012012012000000mmmggggggggGgggg00120mggggg111010001000000111010001000111010001111010111G例n（3,2,1）卷积码，n则n若信息序列为nU=1011010100n则输出码字序列为n101 110 010 011 0
34、01 01101001,010001gg101001000000010001000000101001000010001000101001010001G 与gt(i,j)的关系00120mggggg000000(1,1)(1,2)(1,)(2,1)(2,2)(2,)(,1)(,2)(,)ttttttttttgggngggngg kg kg k n8.7 突发错误的纠正n错误长度b：连续错误的比特数nb1=7、b2=6、b3=3n检纠错能力与错误长度的关系：检测长度不大于b的突发错误：n-kb纠正长度不大于b的突发错误：n-k2bn纠突发错误的码法尔（Fire）码伯顿（Burton）码8.7.2
35、级连码n目的：同时纠正随机错误和突发错误n它们并不是新构造的编码方法，而是已有编码方法的组合或者对已有编码方法的改进级联码n外码：非二进制的码，一般采用RS码n内码：二进制码，既可以采用分组码，也可以采用卷积码n内码和外码的功能内码纠随机错误，外码就突发错误内码检错，外码纠错交织码n交织的本质：置换；作用：突发错误变随机错误n如何置换按列写入，按行读出25201510524191494231813832217127221161161xxxxxxxxxxxxxxxxxxxxxxxxx0510152025010 5 101520250 1 8.7.4 Turbo码nTurbo码是目前最主要的一种卷积码，在工程实践中得到了广泛应用。nTurbo码又称并行级联卷积码8.8 本章小结n理论部分重点在于建立信道编码的基本概念，包括编码和译码规则、检错和纠错能力、平均错误译码概率、有噪信道编码定理（香农第二定理）。n方法部分主要包括线性分组码和卷积码两部分，还简单介绍了突发错误的纠正。在线性分组码中还着重介绍了循环码。
