第六章信道编码1

信息论与编码技术展爱云Zayscj@通信工程教研室CodingandInformationTheroy本课程的相关要求课程基础（概率论）上课要求学习要求实验要求（C\C++)本课程的重点信息的基本概念信息量的计算典型的几种信源编码方法典型的几种信道编码方法无失真信源编码定理-香农第一定理信道编码定理-香农第二定理限失真信源编码定理-香农第三定理差错控制系统分类可纠正错误的码发收FEC能够发现错误的码发收ARQ应答信号能够发现和纠正错误的码发收HEC应答信号信道编码一、引言思考：信道编码的目的是什么？通信系统模型信道编码：从消息到信道波形或矢量的映射从两个方面引入信道编码检错和纠错：对付信道引入的差错直观的译码准则：最小距离译码Shannon第二定理当信息速率R小于信道容量C时，总存在一种编码方式使差错率低于任一给定值e接近信道容量信道编码的作用信道编码的作用：在资源、可靠性和传信量之间选择一个好的工作点（有时还要考虑延时）。资源指的提供信息传输所付出的代价包括频率、时间、空间、功率等等。但不包括实现复杂度一个好的编码就是要充分利用资源，传递尽可能多的信息三种情形：给定资源和可靠性要求，通过信道编码尽量提高传输速率给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销给定资源和传输速率，通过编码提高可靠性编码的实质

——利用冗余降低差错概率将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。几种常用的离散信道编码分组码将一个有限(k)维输入矢量映射到一个（n维）矢量的编码，记为(n,k)分组码卷积码输入为一个无限长序列，每个节拍有k个符号送入编码器，同时有n个符号向输出至信道，但每节拍的输出不仅与本节拍的输入有关，还与之前L-1个节拍的输入有关，记为(n,k,L)卷积码级联码两个以上的编码器按一定方式组合而成的编码器信道编码的分类编码与译码对二进制(n,k)码，信息数量（或合法码字数）为2k，可用编码空间的点数为2n个。任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n,k)码。因此总共可能的编码方案有种。如，共有1029种(100,50)码。译码运算量：如果直接用最大似然序列译码，对一般性的编码而言，正比于n*2k，对(100,50)码，则为1017。几乎是不可能译码的。为什么要引入线性码发现或构造好码是信道编码研究的主要问题编码方案太多，以至全局搜索是不可能的现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优这种约束即要能包含尽可能好的码，又要便于分析，便于译码目前对线性系统的研究远比非线性系统充分线性码的定义码字集中的元之间的任意线性组合仍是合法码字，即对线性组合运算封闭的码字集，称为线性码因此，为了构成线性空间，必须首先定义运算群——定义了一种运算的集合群运算封闭有恒等元有逆元满足结合律交换群满足交换律的群环——定义了两种运算的集合按第一种运算（不妨称为加法）构成交换群第二种运算（不妨称为乘法）满足以下条件封闭性结合律与加法间满足分配律域——一种特殊的环乘法有恒等元（称为1元），且除了加法的恒等元（称为0元）以外有逆的环除0元外，对乘法构成交换群无限域和有限域有理数、实数和复数都是无限域信道编码中用到的是有限域，GF(q)两者在空间意义上有很强的可类比性纠错码的发展概况通信的数学理论，Shannon(1948)汉明码，Hamming(1950)级连码，Forney(1966)卷积码及有效译码,(60年代)RS码及BCH码的有效译码(60年代)TCM，Ungerboeck(1982),Forney(1984)Turbo码，Berrou(1993)LDPC码，Gallager(1963),Macky(1996)空时编码,Tarokh(2000)重复码00…0011…11若将每个比特重复n次，则构成一个码长为n，信息位长度为1的(n,1)重复码,且编码效率(码率)R=1/n许用码字0.9010BSC信道n=2时许用码组：00，11禁用码组：01，10能够发现一个错误，但不能纠正错误n=3时许用码组：000，111禁用码组：001,010,100,011,101,110能够纠正一个错误，发现两个错误n=4时许用码组：0000，1111禁用码组：0001,0010,0100,1000,0011,0101,0110,1100,1001,1010,0111,1101,1110,1011能够纠正一个错误同时发现两个错误译码正确译码失败译码错误发现三个错误纠错码如何纠正错误？在信息序列之后按照一定的规则添加一定长度的保护比特(校验比特或监督比特)信道编码二、基本概念(p193)1、汉明码重(hammingweight)码字中码元“1”的个数。例如：100110的码重是3w(1100110)=？信道编码2、汉明码距(hammingdistance)两个码字相对应位不同的个数。例如：d(1011,0110)=3d(0011,1011)=?思考：码距和码重的关系？信道编码结论：码距是两个码字异或的结果的码重例如：d(10101,01011)101010101111110信道编码3、最小汉明码距dmin在码组中所有码字相互之间距离的最小值。例如：码组{10010，11010，01100}d(10010,11010)=1d(10010,01100)=4d(11010,01100)=3dmin(10010,11010,01100)=1

信道编码三、检纠错能力(p194)结论：检纠能力与最小码距有关。任一(n,k)分组码，若要在码字内：1、检错能力(e位)d>=e+1例如：码组{1001，0110，0101}e=?

信道编码2、纠错能力（t)d>=2*t+1例如：码组{100101，000101，100001}的纠错能力？3、纠正t个随机错误，同时检测e(e>=t)个错误，则要求d>=e+t+1信道编码译码器的任务是从受损的信息序列中尽可能正确的恢复出原信息。作为译码器的输入，译码算法的已知条件是：1）实际接收到的码字序列2）发端所采用的编码算法和该算法产生的码集3）信道模型和信道参数如何译码呢？几种基本的译码方法问题：M®C®R如何根据接收信号R估计发送序列C’,进而估计信息序列M’？设计译码算法的原则：使译码错误概率最小最大后验概率译码

（MaximumAposteriorProbability）

在已知接受的码字序列R条件下，找出可能性最大的发码Ci作为译码估值C’,C’=maxp(Ci/R)信道编码信道编码收码推测发码.但在实际中,后验概率的定量确定是很困难的.最大似然译码

(MaximumLikelihoodDecode)在已知r的条件下,使先验概率最大的译码算法.c’=maxp(r/ci)信道编码信道编码译码失败：译码器根据接收到的信号无法作出明确判断译码错误：译码器根据接收到的信号作出错误判断不完备译码(p199)完备译码：根据接收信号，译码器一定能作出是哪一组信息的判断(p200)信道编码信道编码四、简单的信道编码方法1、奇偶校验（在消息序列后加上一位的冗余位，使整个序列的“1”的个数为奇数个或偶数个。）奇校验：数“1”的个数，在消息序列后加上一位的冗余位，使整个序列的“1”的个数为奇数个偶校验：数“1”的个数，在消息序列后加上一位的冗余位，使整个序列的“1”的个数为偶数个信道编码例如：消息序列1000111010101奇校验：10001110101010偶校验：10001110101011思考：这种方法是否能够纠错？信道编码2、定比码在码字中，“1”和“0”的比例为确定值。应用于数据通信和工业控制中。在我国原来的电传机上使用的就是五单位定比码。国际ARQ电报通信系统中使用的是七单位定比码。信道编码3、群计数码数码字中“1”的个数，在码字后加上用二进制表示的“1”的个数。例如：1100101100思考：能不能加0100？信道编码4、模p法在实际生活中，有时侯“1”和“I”很相似。p=37(符号的个数）数字“0”-“9”和字母“A”-“Z”和空格共37种符号。“0”0“1”1¨“A”10“B”11

设有某消息的符号序列为X=X1X2X3X4,用下表的方式来求它们的和及累加和，然后加上适当的监督元，使累加和是模37的倍数。消息符号和累加和X1X1X1X2X1+X22*X1+X2X3X1+X2+X33*X1+2*X2+X3X4X1+X2+X3+X44*X1+3*X2+2*X3+X4ψX1+X2+X3+X4+ψ5*X1+4*X2+3*X3+2*X4+ψ信道编码信道编码例如：AS9R符号值和累加和A101010S283848994795R2774169监督元ΨΨ+74Ψ+243（Ψ+243）/37=整数Ψ=16监督元G

AS9RG信道编码5、正反码在某些电气化铁道运动系统和电报系统中采用。监督元与信息元相同或者相反。例：10110监督元1011010100监督元01011信道编码的实质就是在信息元后加上合适的监督元,这样起到检错和纠错的作用简单的信道编码方法最小码距和检纠错能力之间的关系介绍了线性码的基本代数知识那么到底在线行码的约束条件之下,如何能够起到检错和纠错的能力呢?信道编码五、监督矩阵与生成矩阵——从线性方程组的角度描述分组码为了进行差错控制，我们按线性代数的关系来添加监督元序列。这种就叫做线性码。信道编码n-k（r)个校验位可用k个已知的信息位表示出来1、监督矩阵信道编码Examples信道编码信道编码信道编码校验矩阵H与任意一个码字之积为零，因此有(P197/p176)信道编码信道编码例：一个（7，3）码的信息元[x1x2x3]和监督元[x4x5x6x7]间的监督方程组为：

信道编码信道编码信息元监督元编成码字0000000000000000111010011101010011101001110111010011101010011101001110101001110100111101001110100111101001110100信道编码结论(P196-198/p176-177)1)上表中的八个码字是许用码字.2)任意两个码字逐位模二相加，可以得到另外一个码字。这种性质叫做封闭性。3）由于封闭性，可知两个码字的码距就是另外一个码字的重量。一组码字中码的最小重量（除全0）就是该码组的最小码距。

4）监督矩阵由两部分组成其中A为r×k矩阵，In-k为r=n-k阶单位方阵。

信道编码信道编码信道编码5）每个码字必须满足监督方程。例如：检验0011101是否是码字？信道编码所以0011101是码字所以0011001不是码字信道编码信道编码6）在线性码组中，如果有一个码字的码重为W，则，在H中必有与之相应的W列相加为0，故称W列线性相关。如果要求码组的最小码距为d，则表示H中至少有d列相加之和为0。这就要求在码的监督矩阵中，任意少于或等于d-1列相加之和均不应等于0，即任意d-1列线性无关。（P198/p177)信道编码2、生成矩阵

信道编码或者信道编码设有一个待编码的消息序列为M=[m1m2….mk]将它表示为信息元序列[x1x2…xk]用矩阵关系可以表示两者的关系：

信道编码信道编码信道编码G为生成矩阵信道编码例：一个（7，3）码的信息元[x1x2x3]和监督元[x4x5x6x7]间的监督方程组为：信道编码信道编码设一信息元组为m1m2m3=101,则通过这种方法，能够计算出所有的码字信道编码结论：生成矩阵的三行实际上均是码字。这三个码字组成的生成矩阵，能够使得得出的码字中，信息元在前，监督元在后，即构成系统码。如选其他的码字来构成生成矩阵，得出的码字中信息元与监督元将是交错排列，称为非系统码。信道编码六：线性分组码的译码（P199/p177)1、伴随式发送的码字是C,接受的码字是RE=R-C成为错误图样或者差错序列。当用监督矩阵来校验接收到的码字，有

信道编码由于C是一个码字，所以S被称为伴随式或者校验子，用它来检查接收码字中的错误。S是校验矩阵H中某几列数据的线性组合

线性分组码的基本译码步骤

Step1:由接收到的序列R，计算伴随式S=RHT；

Step2:若S=0，正确接收；若S不为零，寻找错误图样；

Step3:由错误图样解出码字C=R-E。信道编码2、标准矩阵（StandardArray)设有一个（n,k)线性码，它共有2k个码字c0,c1,c2…..c2k-1

将他们排列。根据许用码字将禁用码字进行分类，分类的依据是错误图样。信道编码C0C1C2C3……C2k-1伴随式SE2C1+E2C2+E2C3+E2

C2k-1+E2S2E3C1+E3C2+E3C3+E3

C2k-1E3

S3………..……………………

E2n-kC1+E2n-kC2+E2n-kC3+E2n-k

C2k-1E2n-kS2r码字错误图样陪集首信道编码标准阵列的构造方法：1）选择所用的码字构成第0行。2）选择差错图样作为第0列。3）阵列中的I行J列元素为Cj+Ei

信道编码例：信道编码00000000011101010011101110101001110101001111010011110100S(0000)

00000010011100

0001

00000100011111

0010

0000011

0011

0000100

0100

0011000

0101

0000110

0110

0100000

0111

0001000

1000

0001001

1001

0001010

1010

0001011

1011

0001100

1100

0010000

1101

1000000

1110

1000001

1111

信道编码应当指出，当（n,k)码的码长n较大时，即使只存储陪集首及伴随式，译码器所需内存仍然很大。两个概念（p201)

完备译码限定距离译码译码失败：译码器根据接收到的信号无法作出明确判断译码错误：译码器根据接收到的信号作出错误判断不完备译码完备译码：根据接收信号，译码器一定能作出是哪一组信息的判断在纠错编码实现上总希望在尽可能小的n和r条件下获得尽可能大的k，d或t对于一个(n,k,d)二元线性码存在如下码限。（p204)信道编码

Singleton信道编码七、汉明码(p205)定义：能够纠正一位错误的一组线性码。二元（n,k,d)汉明码是一种d=3的完备码，满足：校验矩阵有m行，2m-1列，取互不相同的m重构成GF(2)上的[7,4,3]汉明码，001,010,011,100,101,110,111,000。校验矩阵为：Examples:信道编码八、由已知码构造新码的方法（p210)扩展码删余码增广码(增信删余码)增余删信码延长码1、扩展码[n+1,k,d]或[n+1,k,d+1]增加一个全校验位2、删余码(打孔)在原码基础上删去一个校验元。[n-1,k]3、增广码在原码基础上，增加一个信息元，删去一个校验元[n,k+1,d]d*=min{d,n-maxw(c)}4、增余删信码删去一个信息元，增加一个校验元若[n,k,d]码的最小汉明距离d为奇数，则挑选所有偶数重量的码字，即可构成[n,k-1,d+1]增余删信码5、延长码对增广码再填加一个全校验位。[n+1,k+1]信道编码九循环码１、特点:1)码的结构参数可以用有限域的代数方法来表示、分析和构造。２）利用循环特性，可以用循环反馈移位寄存器来构造较为简单方便的编码器和译码器。信道编码２、定义（p215)定义1：设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。信道编码定义2：设是n维空间的一个k维子空间，若对任一恒有则称Vn,k为循环子空间或循环码信道编码3、几个概念１）多项式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，该多项式称为域Fp上的多项式2)多项式次数degf(x)

系数不为零的x的最高次数称为多项式f(x)的次数3)首一多项式最高次数的系数为1的多项式信道编码4)既约多项式设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式

多项式的因式分解问题、根的问题f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gnxn+gn-1xn-1+…+g1x+g0若对所有i,fi=gi,则f(x)=g(x)5)多项式加法（p213)f(x)+g(x)=(fn+

gn)xn+(fn-1

+

gn-1)xn-1+…+(f1

+

g1)x+(f0

+

g0)6)多项式乘法(p213)结论：按上述定义的加法和乘法运算，Fp[x]构成一个具有单位元、无零因子的可换环信道编码7)多项式同余（长除法）两个多项式同余８）剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用Examples1、GF(2)上的多项式f(x)=x2+1的剩余类全体为：信道编码问题一

如何寻找k维循环子空间？

如何设计[n,k]循环码？——利用多项式和有限域的概念信道编码问题一转化为

如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？如何寻找生成多项式g(x)？循环码模多项式xn-1剩余类线性结合代数中的理想生成多项式信道编码９）生成多项式定理1(p215):GF(q)(q为素数或素数的幂)上的[n,k]循环码中，存在唯一的n-k次首一多项式g(x)，每一个码多项式C(x)必是g(x)的倍式，每一个小于等于(n-1)次的g(x)的倍式一定是码多项式信道编码定理2(p216):GF(q)(q为素数或素数的幂)上[n,k]循环码的生成多项式g(x)一定是xn-1的n-k次因式：xn-1=g(x)h(x)。反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个[n,k]循环码信道编码两个结论

结论1:找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。结论2:若C(x)是一个码多项式，则反之，若则C(x)必是一个码多项式信道编码ExamplesGF(2)上，x7+1=(x+1)(x3+x+1)(x3+x2+1)试求一个[7,4]循环码。g(x)、xg(x)、x2

g(x)、x3g(x)、g(x)决定生成矩阵，h(x)决定校验矩阵４、循环码的生成矩阵和校验矩阵循环码的编码原理基本步骤([n,k])1、分解多项式xn-1=g(x)h(x)2、选择其中的n-k次多项式g(x)为生成多项式3、由g(x)可得到k个多项式g(x),xg(x),…xk-1g(x)4、取上述k个多项式的系数即可构成相应的生成矩阵5、取h(x)的互反多项式h*(x),取h*(x),xh*(x),…xn-k-1h*(x)

的系数即可构成相应的校验矩阵信道编码5系统循环码——模g(x)的除法问题m(x)是消息多项式信道编码循环码的系统码构造的步骤为：1）消息多项式乘xn-k2)xn-km(x)/g(x)=q(x)+r(x)/g(x)其中：q(x)是商，r(x)是余数3）C(x)=xn-km(x)+r(x)信道编码例：信息元m=1011g(x)=1+x+x3

xn-km(x)=x3(x3+x2+1)信道编码r(x)=1C(x)=xn-km(x)+r(x)=x6+x5+x3+1所以，码字是1001011b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,…ak

乘B(x)运算电路(利用校验多项式h(x)编码时会用到)6、多项式的乘法电路（p222)b0b1b2br-2b1br-1b1br输出C(x)输入A(x)a0,a1,…ak乘B(x)运算电路akb0akb1akbr-2akbr-16、多项式的乘法电路（p222)h0h1h2hr-2b1hr-1b1hr输入A(x)a0,a1,…ak-g1gr-1输出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)运算电路7、多项式的除法电路（p225)缩减信源循环码（n-I,k-I),循环码编码电路g0g1g2gn-k-2b1gn-k-1b1gn-k输出C(x)输入m(x)m0,m1,…mk乘g(x)运算电路mk-1gn-k-1mk-1

gn-k输入m(x)是信息序列，g(x)为生成多项式mk-1g0mk-1g1循环码编码电路（p225)信道编码十、BCH码(p230)能纠正多位错误的循环码。码长：n=2m-1监督元位数：n-k<=mt最小码距：dmin>=2t+1信道编码十一：卷积码（ConvolutionalCode）Encoding：1955，EliasDecoding：ThresholdDecoding——Massey(1963)ListDecoding——Wozencraft(1961)

ViterbiDecoding——Viterbi(1967)信道编码编码约束度N=m+1（m编码的存储级数）编码约束比特长度NA=n*N编码速率k/nk输入的数据比特，n输出比特数。1、几个基本概念(p234)信道编码2、编码电路mipi2pi1输入D1D2(3,1,2)卷积编码器信道编码3、监督矩阵监督方程组：信道编码输入信息元：输出码字：Ci，Ci+1等称为子码。CiCi+1Ci+2