第8章 信道编码

信息论与编码理论

第8章信道编码8.1信道编码的基本概念

8.1.1编译码规则、检纠错能力信源编码信道编码目的压缩，通过去除信源冗余实现纠错，通过引入冗余实现主要指标平均码长平均错误译码概率影响主要指标的因素编码方法编码方法、译码方法编译码之间的关系一个编码方法对应一个译码方法，译码是编码的逆过程一个编码方法可能对应多个译码方法，在这多个译码方法中有一个能使平均错误译码概率最小例子例8-1：奇偶校验码具有检错能力例8-2：要传送A和B两个消息例8-2-1：Ａ-0、B-1此时没有冗余当接收到010011时译码为ABAABB无法发现接收到的字符串中是否有错误例8-2续例8-2-2：Ａ-00、B-11此时有1位冗余，称为监督位（监督元、校验元）当接收到010011时会发现无法译码（01）具有检错能力“01”和“10”称为禁用码字，而“00”和“11”称为许用码字例8-2-3：Ａ-000、B-111此时有2位冗余当接收到010011时，会发现出现了禁用码子（010、011）具有检错能力无论000010，还是111010，均可判断出现错误因此可以检2位错如果按照“大数法则”译码则译码结果为AB具有纠错能力如果000010，可正确译码为A；如果111010，不能正确译码，即该错误不能被正确纠正过来因此只能纠1位错8.1.2平均错误译码概率例：二进制对称信道传递矩阵，先不考虑编码如果译码规则为00、11，则0和1被正确译码的概率均为1/4，即系统的平均正确译码概率为1/40和1被错误译码的概率均为3/4，即系统的平均错误译码概率为3/4如果译码规则为01、10，则0和1被正确译码的概率均为3/4，即系统的平均正确译码概率为3/40和1被错误译码的概率均为1/4，即系统的平均错误译码概率为1/4由此可见，译码规则的设计也是非常重要的平均错误译码概率Pe为错误译码概率的均值Pe是衡量译码方法好坏的一个重要指标，所选择的译码规则应该使Pe尽可能小。Pe与编码规则有关例

信源符号等概分布，信道矩阵为如果不经过编码直接传输，译码规则为00、11则平均错误译码概率为0.01如果引入冗余，将“0”编码为“000”，“1”编码为“111”，译码规则为000,001,010,1000、111,110,101,0111则平均错误译码概率为8.2译码规则定义8-2选择译码函数F(y)=x*，使之满足p(y|x*)p(x*)>=p(y|xi)p(xi)则称为极大似然译码规则。信道矩阵，输入等概则极大似然译码8.3信道编码定理定理8-1有噪信道编码定理（香农第二定理）对于一个给定的离散无记忆信道，信道容量为C，如果信息传输率R<C，只要码长足够长，则一定存在一种编码方法，使译码的错误概率随着码长的增加，按指数下降到任意小这就是说，可以通过编码（增加码长，即引入更多的冗余），使通信过程实际上不发生错误，或者使错误控制在允许范围之内这一定理为通信差错控制奠定了理论基础8.4线性分组码

8.4.1基本概念分组线性：校验元与信息元之间是线性关系称为(n,k)线性分组码(n,k)线性码的每个码字C可以表示为C=(cn-1,cn-2,…,c1,c0)，其中前k位是信息位线性分组码的例(7,3)线性分组码码字C=(c6,c5,c4,c3,c2,c1,c0)，其中c6、c5、c4为信息元，c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”编码规则（监督方程、校验方程）c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

8.4.2线性分组码的性质设二元线性分组码CI

，若X和Y为其中的任意两个码字，则X+Y也是CI中的一个码字。封闭性：线性码任意两个码字之和仍是一个码字。一定包含全0码字8.4.3两个重要参数编码效率：R=k/n，衡量有效性最小汉明距离，衡量抗干扰能力用(n,k,d)表示距离为d，码率为R=k/n的线性分组码纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码码的重量和码的距离汉明重量：在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming）重量，简称码重“010”码字的码重为1“011”码字的码重为2最小汉明重量：在非零码字中，重量最小者称为最小汉明重量汉明距离汉明距离：码字x和y之间，对应位取值不同的个数，简称码距，用d(x,y)表示。例如：x=(101)，y=(111)则d(x,y)=1汉明距离有以下三个性质：(1)对称性：d(C1,C2)＝d(C2,C1)(2)非负性：d(C1,C2)≥0(3)三角不等式：d(C1,C2)≤d(C1,C3)＋d(C3,C2)最小汉明距离：(n,k)分组码中任意两个码字之间汉明距离的最小值，用dmin表示最小汉明距离与最小汉明重量的关系线性分组码的最小距离等于码中码字的最小重量。证明：用(X)表示码X的重量因为dmin=min{d(X,Y)|XY}=min{(X+Y)|XY}而X+Y也是码子所以dmin=min{(X)|X0}码的检错及纠错能力检测e个错码，则要求最小码距：dmin≥e+1纠正t个错码，则要求最小码距为：dmin≥2t+1纠正t个错码，同时能检测e(e>t)个错码，则要求最小码距为dmin≥e+t+18.4.4生成矩阵和监督矩阵接前例即设C=(c6,c5,c4,c3,c2,c1,c0)，M=(c6,c5,c4)，即C是码字，M是信息，则编码规则可以表示为即C=MG，其中称为生成矩阵c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

c6=c6c5=c5c4=c4c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4

生成矩阵在(n,k)线性分组码中,每个码字C都可以表示为C＝MG则G是该(n,k)线性分组码的生成矩阵，即生成矩阵G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用生成矩阵的每一行都是一个码子生成矩阵不惟一不同的生成矩阵可能生成相同的码字空间这两个码的检错和纠错能力一样但是G2是系统码，G1是非系统码系统码的编译比较简单，而性能与非系统码一样，因此系统码得到了广泛的应用和研究系统码的生成矩阵可以表示为G＝[IkP]Ik---k×k阶单位方阵监督矩阵在线性分组码(n,k)中，如果矩阵H使得对任意码子C都有下式成立则H称为(n,k)线性码的一致监督矩阵(或校验矩阵)其中监督矩阵的标准形式对H各行实行初等变换，将后r列化为单位子阵:H＝[QIr]这种形式的H称为监督矩阵H的标准形式例：(7,3)分组码，监督矩阵的标准形式为生成矩阵与监督矩阵的关系一般关系：HGT＝0T

或GHT＝0例系统码的生成矩阵与监督矩阵标准形之间的关系（G=[IkP]、H=[QIr]）：P＝QT

或Q=PT例8.4.5对偶码对一个(n,k)线性码CI，由于HGT＝0T，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CJCJ是一个(n,n-k)线性码，称为CI的对偶码例：(7,3)码的生成矩阵和监督矩阵为则将两个矩阵的作用对换，得到对偶码(7,4)码的生成矩阵和监督矩阵为经过变换后为(7,3)码和(7,4)码6.3.3伴随式及错误检测伴随式（监督子，校验子）对接收码字R，用监督矩阵H来检验R是否满足监督方程，即HRT＝0T是否成立若HRT＝0T成立，则认为R是一个码字，否则判为码字在传输中发生了错误把S＝RHT或ST＝HRT，称为接收码字R的伴随式(或监督子，或校验子)伴随式的错误图样表示设发送码字C＝(cn-1，cn-2，…，c0)，而接收到的码子为R＝(rn-1,rn-2,…,r0)，则定义E＝(en－1，en－2，…，e0)=R-C，为信道的错误图样

若ei＝0，表示第i位无错，若ei＝1，则表示第i位有错则此时伴随式为ST＝HRT＝H(C＋E)T＝HCT+HET＝HET＝h1en－1＋h2en－2＋…+hne0，这叫做伴随式的错误图样表示由此可以得出结论伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定伴随式是错误的判别式：若S＝0，则判没有出错，接收字是一个码字，若S≠0，则判有错二元码伴随式是H阵中与错误码元对应列之和伴随式译码的基本过程例设(7，3)码的监督矩阵为，可纠1位错发送码字C＝(1010011)接收到的码子R＝(1010011)接收码字R的伴随式为译码器判接收字无错，即传输中没有发生错误接收到的码子R＝(1110011)接收码字R的伴随式为ST≠0，译码器判为有错(7，3)码是纠单个错误的码，且ST等于H的第二列，因此判定接收码字R的第二位是错的，因此译码为(1010011)由于接收字中错误码元数与码的纠错能力相符，所以译码正确伴随式例（续）接收码字R＝(0011011)码元错误多于1个其伴随式为ST不等于0，但与H阵的任何一列都不相同，无法判定错误出在哪些位上，即此时只能发现有错伴随式例2(15,7)码的生成矩阵和监督矩阵分别为该码可以纠正2位错发送码字C＝(101001100101110)接收码字R=(111101100101110)ST不等于0，H阵的第2、4列的和相同，因此错误出现在第2、4位上，码字可以纠正为(101001100101110)8.4.7汉明码汉明码是1950年由汉明提出的一种能纠正单个错误的线性分组码它不仅性能好而且编译码电路非常简单，易于工程实现，因此是工程中常用的一种纠错码二元汉明码的参数n，k和d分别为码长：n=2r-1信息位数：k=2r-r-1监督位数：r=n-k最小码距：dmin=3由于dmin=3，因此能纠正1个随机错误或检测2个错误汉明码的构造汉明码的监督矩阵H的列为所有非零的r维向量组成，所以一旦r给定，就可构造出具体的(n，k)汉明码例：构造一个二元的（7,4,3）汉明码由于r=7-4=3因此H中共有23-1=7列将该监督矩阵进行行列交换，得到监督矩阵的标准形式H＝[QIr]这种行列交换，对码的性能没有影响。此时得到的汉明码为系统汉明码。8.5循环码循环码是一类最主要、最有用的线性分组码1957年普朗格(Prange)首先开始研究循环码循环码具有许多优良的性质，在理论和实践中都是十分重要的8.5.1循环码的基本概念设C是一个(n,k)线性码如果C中的任意一个码字经任意循环移位之后仍然是C中的一个码字，那么就称此码是一个循环码循环左移与循环右移是等价的循环左移i位等于循环右移n-i位因此可以默认循环移位为循环左移码字C=(cn－1,cn－2,…,c1,c0)循环移位i位之后为C(i)＝(cn－i－1,cn－i－2,…,c0,cn－1,…,cn－i＋1,cn－i)循环码例8.5.2循环码的生成多项式和监督多项式码字的多项式设码字C=(cn－1,cn－2,…,c1,c0)，用各个分量作为系数，可以写出一个多项式C(x)=cn-1xn－1＋cn-2xn－2＋…＋c1x＋c0则C(x)就是相应码字的多项式码字C与多项式C(x)是一一对应的码字循环移位之后，码字多项式的变化：C1的多项式C1(x)=x5+x4+x3+xC2的多项式C2(x)=x6+x5+x4+x2C3的多项式C3(x)=x6+x5+x3+1三者的关系为C2(x)=xC1(x)=C1(1)(x)，C3(x)=x2C1(x)mod(x7+1)=C1(2)(x)这表明C(i)C(i)(x)C(i)(x)≡xiC(x)mod(xn＋1)左移循环循环码的多项式举例(7，3)循环码可由任一个码字，比如0011101经过循环移位，得到其他6个非0码字(7，3)循环码也可由码多项式x4+x3＋x2＋1，乘以xi，再模x7＋1得到其他6个非0码多项式生成多项式循环码可由一个非零码字经过循环移位得到其他非0码字因此在(n，k)循环码的2k个码多项式中，只要给出一个就可以推得其它选择其中前k-1位皆为0的码多项式g(x)(次数r＝n-k)，这个多项式叫做(n，k)循环码的生成多项式g(x)＝gn－kxn－k＋gn－k－1xn－k－1＋…＋g1x＋g0生成多项式的构造分解xn+1，其中次数为n-k的因式就是生成多项式例（7,3）循环码的生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)因此生成多项式为：g(x)=(x+1)(x3+x2+1)=x4+x2+x+1或者g(x)=(x+1)(x3+x+1)=x4+x3+x2+1监督多项式如果g(x)为(n，k)循环码的生成多项式，则必为xn＋1的因式，因此xn＋1＝h(x)·g(x)如果多项式h(x)满足xn＋1＝h(x)·g(x)，且hk＝1,h0＝１，则称h(x)为(n，k)循环码的监督多项式h(x)＝hkxk＋hk－１xk－１＋…＋h1x＋h0对偶码以n-k次多项式g(x)为生成多项式，则生成一个(n，k)循环码以h(x)为生成多项式，则生成(n，n-k)循环码这两个循环码互为对偶码生成矩阵(n,k)循环码的生成多项式g(x)经k-1次循环移位，共得到k个码多项式：

g(x)，xg(x)，…，xk－1g(x)这k个码多项式的系数可作为生成矩阵G(x)的k行，即生成矩阵举例设(7,4)循环码的生成多项式g(x)＝x3＋x＋1，求其生成矩阵G及生成的码字监督矩阵(n，k)循环码的监督多项式为h(x)＝hkxk＋hk－１xk－１＋…＋h1x＋h0则(n，k)循环码的监督矩阵为循环码的监督矩阵举例(7，3)码：x7＋1＝(x3＋x＋1)(x4＋x2＋x＋1)4次多项式为生成多项式：g(x)＝x4＋x2＋x＋1＝g4x4＋g3x3＋g2x2＋g1x＋g03次多项式则是监督多项式：h(x)＝x3＋x＋1＝h3x3＋h2x2＋h1x＋h0则生成矩阵和监督矩阵分别为8.5.3循环码的译码循环码的译码包括三个步骤计算伴随式求伴随式对应的错误图样用错误图样纠错（译码）相比于一般线形分组码，循环码的译码更加简单易行伴随式一般线性分组码的伴随式（矩阵形式）：S=RHT或ST=HRT这对循环码也是适用的循环码伴随式的特殊求法（多项式形式）(P157)S(x)≡R(x)modg(x)即循环码的伴随式是接收多项式R(x)除以g(x)的余式循环码译码例设(7,4)循环码的生成多项式g(x)＝x3＋x＋1，一个码字为0001011，若接收到的码字为1001011，则R(x)=x6+x3+x+1S(x)≡R(x)modg(x)=x2+1，即S=[101]T而h(x)=x4+x2+x+1，即因此码字的第1位出错，译码为0001011，正确译码8.5.4BCH码BCH码是迄今为止所发现的一类性能较优的码是纠随机错误的循环码BCH码的纠错能力很强，且构造方便，对它的分析研究也很透彻BCH的历史1959年霍昆格姆(Hocgenghem)和1960年博斯(Bose)及查德胡里(Chaudhuri)分别提出的纠正多个随机错误的循环码，称为BCH码1960年彼得森(Pelerson)找到了二元BCH码的第一个有效算法，后经多人的推广和改进1967年由伯利坎普(Berlekamp)提出了BCH码译码的迭代算法，从而将BCH码由理论研究推向实际应用阶段，使它成为应用广泛而有效的一类线性码BCH码的基本参数对任何正整数m(3)和t(<2m-1)，存在一个二元BCH码，具有下面的参数码长：n=2m-1一致校验位的数目：n-kmt最小码距：dmin2t+1能纠正n=2m-1个码元中任意不超过t个错误即给定符合条件m3、t<2m-1的m和t之后，总能设计出一个二元BCH，满足码长为2m-1，并能纠正t个随机错误。BCH码的定义g(x)是一个循环码的生成多项式，如果g(x)=0的根中包括2t个连续根,2,3,…,2t，则由g(x)生成的循环码叫做BCH码。此时g(x)=(x-)(x-2)…(x-2t)=0如何构造出满足该条件的生成多项式g(x)是比较困难的，有兴趣的同学可以自学部分常用BCH码的生成多项式nktg(x)（八进制）7411315111231572721155324673126145312123551311631076573111554233253167313365047312617563571103如果信息元为1101，则对应的码字为1101001如果接收到的码字为1101000，则伴随式为001，是监督矩阵的最后一列，则译码结果为11010018.5.5RS码里德-索罗蒙（Reed-Solomon）码，简称RS码RS码是q元BCH码编码方式类似RS码是以数据块进行编码例如如果q=4，数据块的长度就是2如果q=8，数据块的长度就是3RS码即可以纠随机错误，又可以纠突发错误8.6卷积码1955年埃里亚斯(Elias)最早提出卷积码的概念卷积码(又称连环码)指的是在任意给定时刻，编码器输出的

n0个码元中，每一个码元不仅和此时刻输入的k0个信息元有关，还与前面连续m0个时刻输入的信息元有关，可以用（n0,k0,m0）表示典型的卷积码一般选较小的n0和k0(k0<n0)，但存储器数m0则取较大的值(m0<10)卷积码的编码效率为R＝k0/n0在同样的编码效率R下，卷积码的性能优于分组码，至少不低于分组码但是卷积码不像分组码有严格的代数结构，至今没有严密的数学手段将纠错能力与码的结构十分有规律的联系起来。8.6.2卷积码的编码设卷积码编码器输入码序列为U=[u0(1)u0(2)…u0(k0)u1(1)u1(2)…u1(k0)…us(1)us(2)…us(k0)…]编码器输出码序列为C=[c0(1)c0(2)…c0(n0)c1(1)c1(2)…c1(n0)…cs(1)cs(2)…cs(n0)…]则非系统码的编码为系统码的编码为即前k0*k0个其中g(i,j)=[g0(i,j)g1(i,j)…gm0(i,j)]是卷积码的生成序列，共有k0*n0个生成序列，每个序列的长度为m0+1比特，它的作用与线性分组码中的生成矩阵类似，表明如何由信息元构成校验元。卷积码编码例(3,1,2)系统卷积码则n0=3，k0=1，m0=2U=[us-2(1)us-1(1)us(1)]因此它有3个生成序列g(1,1)、g(1,2)、g(1,3)，他们的值分别为g(1,1)=[100]g(1,2)=[110]g(1,3)=[101]则编码方法为卷积码编码例(3,2,2)系统卷积码则n0=3，k0=2，m0=2U=[us-2(1)us-2(2)us-1(1)us-1(2)u