信息论基础教程课程论文

信道编码的发展与应用摘要：在有扰离散信道上，只要信息传输速率不大于信道容量，就总可以找到一种信道编码方式来实现无误传输。这就是信息论的开创者香农在1948年提出的信道编码定理。信道编码定理给信道编码的研究指出了明确的方向。本文介绍了几种主要的信道编码、译码原理，分析了他们的实现方法和性能，并对各种编码的优缺点进行了总结，在给出信道编码的应用实例的基础上对信道编码的未来进行了展望。关键词：信道编码；分组码；卷积码；级联码；Turbo码信息与通信系统中的编码有4种形式：信源编码、信道编码、密码编码和多址编码。信源编码解决了通信系统的有效性问题，通过压缩信源冗余信息来提高通信的效率；信道编码则是通过增加冗余位来达到保证通信系统的可靠性（通过牺牲宽带或传输速率来换取可靠性），其基本思想是根据相关性来检测和纠正传输过程中产生的差错；密码编码则是保证了系统的安全性；多址编码主要是解决多用户通信问题。香农第二编码定理证明，用任意接近信道容量C的传输速率R传送并且传输的差错率可以任意小的编码方法是存在的。香农还从理论上证明了，即使是随机编码，只要码组长度无限，就可以找到一种信道编码方式来实现无误传输。信道编码的任务就是寻找这种编码的。1信道编码的分类1.1分组码把信息序列以每k个码元分组，然后把每组k个信息元按一定规

律产生r个多余的校验元，输出序列每组长为n=k+r。每一码字的r个校验元只与本组的k个信息元有关，与别的信息位无关，记为分组码（n,k）。线性分组码是最有实用价值的一类码，比如汉明码、Golay码、RS码、BCH码等都属于线性分组码。分组码线性是指码组中码元的约束关系是线性的，而分组则是对编码而言。线性分组码的编码方式是将信源输出序列分组，每组是长为k的信息序列，然后按照一定的编码规则插入n-k位的校验位，校验位是所有信息位的线性组合，组成n长的码字序列。线性分组码可以用近世代数理论中有限维有限域的矩阵来描述。线性分组码生成矩阵为G，信息矢量为u=(七，…，七)，则编码输出为：c=uXkG如果生成的是系统码，即原始的信息出现在编码中，则生成矩阵Gkxn可改写为:G=(/k:Q)其中：1k表示k阶单位阵，Q为kx(n-k)阶阵。线性分组码用于译码的校验矩阵为H,满足HcT=0和hGt=0。n-kn-k为n-k阶单位阵。由此可知线性分组码的生成矩阵和校验矩阵的行矢对于系统码而言,其校验矩阵为H=(Q:I)，Qn-kn-k为n-k阶单位阵。由此可知线性分组码的生成矩阵和校验矩阵的行矢线性分组码的性质是:

码中任意两个码字之和仍为一码字；任意码字是G的行向量G,G,...,G的线性组合；零向量0=（0,0，…，0）是一个码字，称为零码字；线性分组码的最小距离等于非零码字的最小重量（即汉明重量，即对于一个非零码字而言，非零元素的个数即为汉明重量）。-1001110-0011101【例1】已知生成矩阵为G=0100111，求生成的线性分组码及由h生成的线性分组码。0011101111001111101解由于G=（IP）则有P=1011000111010011000100110001又因为Q=P广则H=1110011111011011000111010011000100110001mC00000000000010011101010010011101101110101001001110101101001111011010011111110100把校验矩阵h当作生成矩阵，可生成（7,4）线性分组码:mC00000000000000101100010010110001000111010011010011101000101100010101100010110011101001111000101100010011101001101001110101011000101111000101100110100111011110100111011111111111这样生成的C和cT是互相正交的。1.1.1循环码一个(n,k)线性分组码，如果每个码字经过任意循环移位后仍然是一个线性分组码，那么此码就是一个循环码。循环码是线性分组码中最主要、最有用的一个子类，它具有完整的代数结构，编译和译码可以用具有反馈联级的移位寄存器来实现。它满足循环移位特性：码C中任何一个码字的循环移位仍是码C中的一个码字。一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此我们需用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就可以表示一个码的特征。我们可以用不大于(n-1)次的码多项式C(x)来唯一表示一个码字：C(x)=cXn-1+・..+cx2+Cx+c根据循环码的定义，与一般的线性分组码相比，循环码的生成矩阵结构更加简化，生成矩阵由生成多项式g(x)决定：Gt=\Xk-1g(x),•..,xg(x),g(x)g(x)必为E+1的因子，根据线性分组码的产生原理，则(n,k)循环码有下面的关系式：V(x)=u(x)g(x)，编码器的实现框图如图1所示。图1编码器的实现g(x)h(x)三0mod(1+xn)，其中：h(x)为相应的校验多项式，最高次数为n—k。构造(n,k)循环码的步骤：对(1+Xn)作因式分解，找出(n—k)此因式。以该(〃—k)此因式作为生成多项式，与不高于(k-1)次的信息多项式相乘得码多项式C(x)=m(x)g(x)。C(x)的次数不高于(k—1)+(n—k)=(n—1)次。【例2】构造一个(7,4)循环码。解(1)对(1+X7)作因式分解得:1+X7=(x+1)(X3+X2+1)(X3+x+1)。3次因式有两个(X3+X2+1)和(X3+x+1)，均可以作为(7,4)循环码的生成多项式，选择不同的g(x)会得到不同的(7,4)循环码。(2)选g(x)=X3+X2+1，信息多项式共有2k=16种可能的组合，对应16个码字。利用c(x)=m(x)g(x)可得到16个码字。例如，m=(0110)对应码字：c(x)=m(x)g(x)=(mx3+mx2+mx+m)g(x)=x5+x3+x2+xT(0101110)表1是该(7,4)循环码的码字。可以看出，任何码字的循环仍然是码字，整个码组有4组码字的循环，但都是g(x)=x3+x2+1的线性组合。表1(7,4)循环码信息比特码字(循环1)信息比特码字(循环2)信息比特码字(循环3和4)mmmmcccccccmmmmcccccccmmmmccccccc321065432103210654321032106543210000100011010011001011100000000000001000110100110010111011111111111010001101001100101110010001101000010101110011101101000110101110010011101000111001110010111101000110111110010111.1.2BCH码如果a是有限域GF(qm)上的一个非零元素，存在整数b>1，则码长为n最小汉明距离为2t+1的BCH码在GF(q)域上的生成多项式g(x)必以ab,ab+1,...,aq1为根。如果gfq)上的非零元素a是gf(q)域上最小多项式m(x)的根，则BCH码的生成多项式可以用下面的公式来描述：g(x)=LCM[mb(x),mb](x),...,mb2](x)]当b=1时称为狭义BCH码，当n=Qm_1时称为本原BCH码，当q=2时称为二元BCH码。BCH码家族最重要的码就是狭义本原二元码。他的生成多项式可改写为：g(x)=LCM[m1(x),m3(x),...,m2t1(x)]这里t为纠错个数，m（x）为不可约多项式，LCM为取最小公倍式。由该生成多项式产生的最小码距d>d=2t+1（d为设计码距）。可纠t个错误的BCH码的生成多项式可按下面的步骤求解：⑴选择GF（2m）域上的一个本原元素以；⑵根据设计的纠错能力t，确定由本原多项式决定的a的最下多项式；⑶计算g（x）=LCM[m（x）,m（x）,...,m（x）]，其中a，以3,...,aw均为根。bch码是一类重要的循环码，能纠正多个随机错误（汉明码只能纠单个错误）。由于具有纠错能力强、编码简单、译码较容易实现等优点而被广泛采用。1.2卷积码编码器在某个时间段产生的〃个码元，不但取决于该时间段进入编码器的.个信息位，而且也与前面的N-1个时间段内的信息组有关，这就是树码或称链码。卷积码是树码中最重要的一类，是一种非线性码，其编码器中有记忆器件存在。它的码字与N个时间段的信息组的映射关系是时不变的线性关系，卷积码与分组码相似，具有纠正随机错误、突发错误或同时纠正这两类错误的能力。通常卷积码更适用于前向纠错。一般的卷积码选取较小的n,k和较大的N，可以获得既简单又有高性能的信道编码。卷积码的描述方式有很多种：生成矩阵、生成多项式、D变换，以及主要用于译码的树图、trellis图和状态转移图等。卷积码的生成矩阵与分组码不同，他是一个半无限矩阵。这就导致了卷积码在编码上的输出是有头无尾的，即每个信息段的输出都是无穷的。实际中，通过在信息段的后面增加k个0来分割，因为在连续输入k个0后输出也是0O卷积码的译码算法有多种，主要包括：序列译码、迭代译码、list译码以及维特比译码等。其中维特比译码用的较多，他是一种基于trellis图最大似然译码，因此也是一种最佳译码算法。维特比译码的缺点主要有2个：⑴要等全部接收的数据进入译码器后才能最后算出译码的结果，因此时延长。⑵共有2贝k1)条幸存路径的全部历史数据需要保存，所以存储量很大。1.3级联码串行级联码由两个短码(内码和外码)串接而成。其分组长度是内、外码分组长度的乘积，码率是两种码率的乘积。外码的作用是纠正经内码译码后遗留下来的一些差错。根据各种编码的特性，典型的串行级联码方案采用特别适合于纠突发错误的RS(Reed-Soloman)码为外码，纠随机错误能力很强的卷积码为内码，信息数据经RS编码、交织和卷积编码后发送出去，接收信号后经卷积译码、去交织和RS译码后输出。串行级联码与单一码相比更易获得高的编码增益，设备不太复杂，费用相对较低，运用于对编码效率要求不高的通信系统可获得优异的性能。在加性高斯白噪声(AWGN)信道中，若要系统误码率不大于105，那么，不编码的最佳相于PSK系统要求比特能量与噪声密度之比（Eb/No）为9.5dB，采用卷积码-序列译码的系统要求Eb/No为3-5Db,采用串行级联码的系统要求Eb/No为0.2dB，这与香农容量极限（-1.6dB）仅差1.8dB。串行级联码的问题在于它仍然没有摆脱短码的束缚，因而在信息传输速率接近信道容限时，其译码过程不但不会减少错误，而且还可能使错误增加。于是人们继续寻找性能更优异的可译码结构，其重要成果是1992年申请专利、1993年在ICC会议上以论文形式公开的Turbo-code。1.4Turbo码Turbo码是1993年由C.Berrou等提出的一种并联的卷积码编码方案。他巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想；同时，采用软输出迭代译码来逼近最大似然译码。仿真结果表明:在AWGN信道下，码率为1/2的Turbo码在达到误比特率（BER）W105时，Eb/N0仅为约0.7dB（这种情况下达到信道容量的理想Eb/N0值为0db），远远超过了其他编码方式，一时在信息和编码理论界引起了轰动°Turb。码由于其近Shannon界的突出纠错能力，成为近年信道编码理论研究的热点问题。其编码器由两个（或多个）带反馈的系统卷积码器经一交织器并行级联而成，接收端采用逐位最大后验概率译码器通过反复迭代循环来译码。编码器结构如图2所示。

图2Turbo码编码器结构Turbo码有一重要特点是其译码较为复杂，比常规的卷积码要复杂的多，这种复杂不仅在于其译码要采用迭代的过程，而且采用的算法本身也比较复杂。这些算法的关键是不但要能够对每比特进行译码，而且还要伴随着译码给出每比特译出的可靠性信息，有了这些信息，迭代才能进行下去。用于Turbo码译码的具体算法有：标准算法（对BJCR算法的修正）、对数域算法、最大值算法及软输出维特比译码算法（SOVA）。他的结构图可以用流水线的形式来描述，每个单元表示一次迭代，如图3所示。姓代数据公用宿道白有信道数耀自有信__道数据介译码器2解文织姓代数据公用宿道白有信道数耀自有信__道数据介译码器2解文织译码单元I图3迭代算法结构图由于充分利用了码间的附加信息，Turbo码获得了很好的编码增益。Turbo码不仅在信道信噪比很低的高噪声环境下性能优越，而且还具有很强的抗衰落、抗干扰能力，因此它在信道条件差的移动通信系统中有很大的应用潜力，在第三代移动通信系统(IMT-2000)中己经将Turbo码作为其传输高速数据的信道编码标准。2信道编码的应用2.1纠错码在数字音频/视频传输中的应用2.1.1数字音频广播(DAB)：在FM多路复用DAB中采用(n,k,d)=(273,191,18)循环码，传文本文件时用(273,190)码。欧洲DAB标准：采用rate-compatiblepuncturedconvolutional(RCPC)codingscheme:UnequalandAdaptiveErrorProtectionwithRCPCCodes;TheRCPCCodingSchemefortheEuropeanDABSystem;2.1.2数字视频广播(DAB)：第一个标准(90年代)：(514,493)BCH码，d=6；采用级连码：(204,188)RS码+(2,1,7)卷积码欧洲最近的DVB标准(2005)：BCH+LDPC码组成的级连码2.2纠错码在移动通信中的应用2.2.1Turbo码在第三代移动通信中的应用⑴编码原理图4Turbo码编码器框图⑵3G数字移动通信中的Turbo码编码器结构2.3纠错码在光纤通信中的应用纠错码在光纤通信中的应用是近几年才提出的，基本原因在于，一是光纤本身具有较强的抗干扰能力，二是在光纤通信初期对速率的要求不高，一条光纤只须传输一个波长的信号。随着Internet的普及与迅速发展，通信业务量大增，因而需要采用波分复用，甚至密集波分复用技术。在长距离或超长距离、大容量DWDM光纤通信系统中，光纤的色散、长距离传输引起的信号衰减、信道噪声以及一根光纤中多个波长之间的干扰会使系统的性能大大下降，为此，在光纤干线上每隔大约80公里就必须进行一次光中继，每隔400公里左右则必须进行一次电信号的再生，从而使建网和运营的成本剧增。解决上述问题的关键是在光纤通信中引入前向纠错编码（EorwardError-Correction，简称为FEC）技术。采用FEC所获得的编码增益，可用于降低误码率、以提高通信的可靠性，也可用于增大传输距离，还可用于减小所需的发射功率，或综合加以利用。2.3.1带内FEC方案带内FEC方案是ITU-T在2000年10月通过的G.707建议中提出的。所谓带内，是指将FEC的冗余监督位置于SONET/SDH原有帧格式开销中的未定义位上，无须增加额外的带宽。该方案适用于4路OC-48/STM-16，或单路OC-192/STM-64信号，线路速率为10Gb/s,速率低于OC-48/STM-16时不使用FEC，高于此速率时须在此方案基础上加上交织技术。该方案的优点是，加上FEC后不会影响SONET/SDH原有的帧格式，线路速率保持不变，而且与不采用用FEC的网络兼容。（n,k）BCH码是一类可纠正多个随机错误的线性分组码。带内FEC方案采用可纠3个比特错误的二元（4359,4320）BCH码（简称为BCH-3），该码是本原（8119，8152）BCH码的一种缩短码，其生成多项式为g（x）=X16+X12+X5+1按照SDH-16帧结构，取比特用户数据，加上39个冗余监督元，便构成的一个码长为n=4359的（4359,4320）BCH码的码字，其最小距离为7，故最多可纠正3比特错误。这39个冗余监督元充填于SDH-16帧结构开销中未定义的空闲比特位中，所以，采用带内FEC既不影响原来的帧格式，也不改变线路的传输速率。由于SDH-16帧结构由9行组成，每行有字节（每字节8比特），于是每行可编成8个BCH（4320，4359）码的码字。每个BCH（4320，4359）码的码字可纠正3个比特错误。若采用交织技术，即将8个码字排成一个阵列，每行一个码字（4320比特），共有8行、4320列，传输时按顺序逐列传输，在接收端再按此方式排成阵列，然后逐行译码，如果在传输过程中连续有3列（24比特）发生错误，每个接收码组中也只有3比特错误，因而译码器可自动加以纠正。可见，经过交织处理后，带内FEC可纠正单个接收码组中的任意3比特错误，同时可纠正SDH-16帧中长度多达24比特的突发错误。2.3.2带外FEC方案带内FEC的优点是不用改变SONET/SDH的帧格式、无须提高线路速率，但其纠错能力非常有限，已不能满足更高速率的远程网络的质量要求。因而ITU-T在2001年制定的G.709标准中便提出了适合DWDM光传输网（OTN）2.5、10、40Gb/s速率的带外FEC方案，而G.795提出的带外FEC方案则主要用于2.5Gb/s以及更高的速率海底光纤传输网络。这两种带外FEC方案基本相同，不同点是G.975采用的交织技术未形成标准，G.709则有统一的标准。所谓带外，是指FEC为了实现纠错所增加的冗余校验位不是象带内FEC那样插入原有帧格式的空闲位中，而是附加在数据帧之后，需要增加额外的带宽，即使用带外FEC后线路速率会提高。以上两种带外FEC均采用Reed-Solomob码（简称RS码）。RS码是一类具有很强的既能纠随机错误又能纠突发错误的最大距离非二元码，在各种通信及计算机、光盘存储系统中具有广泛应用。FEC采用RS（255，239）码，简称RS-8，即在k=239数据字节（每个字节为一个码元符号）后加上16个校验字节便构成长为n=255字节的码字，其编码效率为93.7%。RS（255，239）码生多项式为：g（x）=x8+x4+x3+X2+1该码可纠正接收码组中任意8字节的随机错误，纠单个突发错误的最大长度为64比特。117i1i1日行［码字，行11Ilb.,.■1531Lt-——255f〉—一—一—123口学节偿,既缶16丰节兀刽□TU2:FF销OTU2有效焚淅CCimO字节］OTU2FEC£文56字节〉0TU2并销CTU2有敦华荷了3口咨自宇节、OT