信息论与编码--第6章课件.ppt

1、信息论基础B第第6章章 信道编码信道编码 信道编码信道编码是以信息在信道上的正确传输为目标的是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：编码，可分为两个层次上的问题：如何正确接收载有信息的信号如何正确接收载有信息的信号线路编码线路编码如何避免少量差错信号对信息内容的影响如何避免少量差错信号对信息内容的影响纠错编码纠错编码信息论基础B本章内容本章内容n有扰离散信道的编码定理有扰离散信道的编码定理 n纠错编译码的基本原理与分析方法纠错编译码的基本原理与分析方法n线性分组码线性分组码 n卷积码卷积码n编码与调制的结合编码与调制的结合TCM码码n运用级联、分集与信息迭代概念的纠错码

2、运用级联、分集与信息迭代概念的纠错码信息论基础B6.1 信道编码的基本概念信道编码的基本概念 一、差错图样（一、差错图样（error pattern）定量地描述信号的差错，收、发码之定量地描述信号的差错，收、发码之“差差”：差错图样差错图样E发码发码C 收码收码R（模（模M）信息论基础B差错类型差错类型n差错符号差错符号：由符号发生差错引起，也叫：由符号发生差错引起，也叫信号差信号差错错，信号差错概率用，信号差错概率用误码元率误码元率表示表示n差错比特差错比特：由信息比特发生差错引起，也叫：由信息比特发生差错引起，也叫信信息差错息差错，信息差错概率用，信息差错概率用误比特率误比特率表示表示n对

3、于对于二进制二进制传输系统，符号差错等效于比特差传输系统，符号差错等效于比特差错；错；n对于对于多进制多进制系统，一个符号差错到底对应多少系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比比特差错却难以确定。因为一个符号由多个比特组成。特组成。信息论基础B差错图样类型差错图样类型 n随机差错随机差错：若差错图样上各码位的取值既与前：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；的概率独立发生于各码字、各码元、各比特；n突发差错：突发差错：前后相关、成堆出现。突发差错总前后

4、相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超间并不是每个码元都错，而是码元差错概率超过了某个额定值。过了某个额定值。信息论基础B二、纠错码分类二、纠错码分类 n从功能角度从功能角度：检错码：检错码、纠错码、纠错码 n码元与原始信息位的关系码元与原始信息位的关系：线性码、非线性码：线性码、非线性码 n对信息序列的处理方法对信息序列的处理方法：分组码、卷积码：分组码、卷积码n差错类型差错类型：纠随机差错码、纠突发差错码、介：纠随机差错码、纠突发差错码、介于中间的纠随机于中间的纠随机/突发差错码。突

5、发差错码。n构码理论构码理论：代数码、几何码、算术码、组合码：代数码、几何码、算术码、组合码等等 信息论基础B三、差错控制系统分类三、差错控制系统分类 n前向纠错（前向纠错（FEC）：发端信息经纠错编码后传：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的送，收端通过纠错译码自动纠正传递过程中的差错差错 n反馈重发（反馈重发（ARQ）：）：收端通过检测接收码是收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码通过反向信道通知发端重发该码 n混合纠错（混合纠错（HEC）：）：前向纠错和反馈重发的结前向纠错

6、和反馈重发的结合，发端发送的码兼有检错和纠错两种能力合，发端发送的码兼有检错和纠错两种能力 信息论基础B6.1.2矢量空间与码空间矢量空间与码空间 nF表示码元所在的数域，对于二进制码，表示码元所在的数域，对于二进制码，F代表二代表二元域元域0,1，设，设n重有序元素的集合重有序元素的集合V=Vi,若满足条件：若满足条件：1、V中矢量元素在矢量加运算下构成加群；中矢量元素在矢量加运算下构成加群；2、V中矢量元素与数域中矢量元素与数域F元素的标乘封闭在元素的标乘封闭在V中；中；3、分配律、结合律成立，、分配律、结合律成立，则称集合则称集合V是数域是数域F上的上的n维维矢量空间矢量空间，或称，或称

7、n维维线性空间线性空间，n维矢量又称维矢量又称n重重(n-tuples)。01(1)(,),iiiiji nijVVVVVVF 信息论基础B矢量空间与基底矢量空间与基底注意：注意：1、n维矢量空间一定包含维矢量空间一定包含0矢量矢量2、n维矢量空间中的各矢量可能线性无关，也维矢量空间中的各矢量可能线性无关，也可能线性相关可能线性相关信息论基础B矢量空间中矢量的关系矢量空间中矢量的关系 对于域对于域F上的若干矢量上的若干矢量线性组合线性组合：线性相关线性相关：其中任一矢量可表示为其它矢量的线性组合其中任一矢量可表示为其它矢量的线性组合线性无关线性无关或或线性独立线性独立：一组矢量中的任意一个都：

8、一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。不可能用其它矢量的线性组合来代替。12,ikVVVV及及1122,()kiiiVaVa VaVaF11220,(iiiaVa VaVaF且且不不全全是是零零)信息论基础B矢量空间与基底矢量空间与基底3、一组线性无关的矢量、一组线性无关的矢量 ，线性组合的，线性组合的集集合合就构成了一个就构成了一个矢量空间矢量空间V，这组矢量，这组矢量 就是就是这个矢量空间的这个矢量空间的基底基底。n维矢量空间应包含维矢量空间应包含n个基底个基底 基底不唯一基底不唯一12,nV VV信息论基础B二元域二元域GF(2)上三重矢量空间上三重矢量空间 n以（以（

9、100）为基底可张成）为基底可张成一维三重一维三重子空间子空间V1，含，含21=2 个元素，即个元素，即n以以(010)(001)为基底可张成为基底可张成二维三重二维三重子空间子空间V2，含含 22=4个元素，即个元素，即n以以(100)(010)(001)为基底可张成为基底可张成三维三重三维三重空间空间V,含含 23=8个元素，个元素，V1和和V2都是都是V的子空间。的子空间。)100(),000(1V)011(),010(),001(),000(2V信息论基础B矢量空间矢量空间n两个两个矢量正交矢量正交：V1 V2 0 n两个两个矢量空间正交矢量空间正交：某矢量空间中的任意元素：某矢量空间

10、中的任意元素与另一矢量空间中的任意元素正交与另一矢量空间中的任意元素正交 n两个矢量空间的两个矢量空间的基底正交基底正交，则两个，则两个矢量空间正矢量空间正交交n正交的两个子空间正交的两个子空间V1、V2互为互为对偶空间对偶空间(Dual Space)，其中一个空间是另一个空间的，其中一个空间是另一个空间的零空零空间间（null space，也称零化空间）。，也称零化空间）。信息论基础B码空间码空间 消息消息k长长 (n,k)码字码字n长长 qk 种种 分组编码器分组编码器 qn种种 k维维k重矢量重矢量 n维维n重矢量重矢量 通常通常qn qk，分组编码的任务是，分组编码的任务是要在要在n维

11、维n重矢量空间的重矢量空间的qn种可能组种可能组合中选择其中的合中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。信息论基础B分组编码的任务分组编码的任务 n选择一个选择一个维维n重子空间作为码空间。重子空间作为码空间。n确定由确定由k维维k重信息空间到重信息空间到维维n重码空间的映重码空间的映射方法。射方法。码空间的不同码空间的不同选择方法，以及信息组与码选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。组的不同映射算法，就构成了不同的分组码。信息论基础B6.1.3随机编码随机编码n运用概率统计方法在特定信道条件下对编码信运用概率统

12、计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界限边界，其中最优码所能达到的差错概率上界称作称作随机码界随机码界。n用这种方法不能得知最优码是如何具体编出来用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。码技术具有特别重要的理论价值。信息论基础BShannon method for proving one baby

13、 weighs less than 10 kg信息论基础Bn在在(N,K)分组编码器中随机选定的码集有分组编码器中随机选定的码集有qNM种种 n第第m个码集个码集(记作记作cm)被随机选中的概率是被随机选中的概率是n设与这种选择相对应的条件差错概率是设与这种选择相对应的条件差错概率是Pe(cm)n全部码集的平均差错概率是全部码集的平均差错概率是()(c)NMmPq 11(c)(c)(c)NMNMqqNMeemmemmmPPPqP 信息论基础Bn必定存在某些码集必定存在某些码集n某些码集某些码集n若若 ，就必然存在一批码集，就必然存在一批码集 即差错概率趋于零的好码一定存在即差错概率趋于零的好码

14、一定存在 11(c)(c)(c)NMNMqqNMeemmemmmPPPqP(c)emePP(c)emePP 0eP 0)(mePc信息论基础Bn码集点数码集点数M=qK占占N维矢量空间总点数维矢量空间总点数qN的比例是的比例是F=qK/qN =q-(N-K)n当当K和和N的差值拉大即冗余的空间点数增加时，平的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。离将变大，平均差错概率将变小。n当当F0 即即(N-K)时，能否让平均差错概率时，能否让平均差错概率？nGallager在在1965年推导了年

15、推导了 的上边界，并证明的上边界，并证明这个上边界是按指数规律收敛的。这个上边界是按指数规律收敛的。0eP eP信息论基础BnE(R)为为可靠性函数可靠性函数，也叫误差指数，也叫误差指数 n码率码率：R=(lbM)/N qM是可能的信息组合数，是可能的信息组合数，M=qKqN是每码字的码元数，是每码字的码元数，qR表示每码元携带的信息量，单位是每符号比特表示每码元携带的信息量，单位是每符号比特（bit/symbol）)(RNEeeP信息论基础BnR在在0,R0区间时区间时E(R)R曲线是斜率曲线是斜率为为-1（-45）的直线，）的直线，E(R)反比于反比于R；而当；而当R=C时时E(R)=0即

16、可即可靠性为零。靠性为零。E(R)C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线信息论基础B6.1.4信道编码定理信道编码定理n正定理正定理：只要传信率：只要传信率R小于信道容量小于信道容量C，总存，总存在一种信道码（及解码器），可以以所要求的在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。任意小的差错概率实现可靠的通信。n逆定理逆定理：信道容量：信道容量C是可靠通信系统传信率是可靠通信系统传信率R的上边界，如果的上边界，如果R C，就不可能有任何一种，就不可能有任何一种编码能使差错概率任意小。编码能使差错概率任意小。信息论基础B6.2 纠错编译码的基本原

17、理与分析纠错编译码的基本原理与分析n纠错编码的基本思路纠错编码的基本思路 n译码方法最优译码与最大似然译码译码方法最优译码与最大似然译码 信息论基础B6.2.1纠错编码的基本思路纠错编码的基本思路nR不变不变，信道容量大者，信道容量大者其可靠性函数其可靠性函数E(R)也也大；大；nC不变不变，码率减小时其，码率减小时其可靠性函数可靠性函数E(R)增大增大()NE RePe E(R)R0 R1 R2 C1 C2 增大增大E(R)的途径的途径信息论基础B6.2.1纠错编码的基本思路纠错编码的基本思路n增大信道容量增大信道容量C q扩展带宽扩展带宽q加大功率加大功率q降低噪声降低噪声n减小码率减小码

18、率R qQ、N不变而减小不变而减小K qQ、K不变而增大不变而增大NqN、K不变而减小不变而减小Qn增大码长增大码长N 信息论基础B6.2.2最优译码与最大似然译码最优译码与最大似然译码n译码器的任务译码器的任务是从受损的信息序列中是从受损的信息序列中尽可能正确地恢复出原信息。尽可能正确地恢复出原信息。n译码算法的已知条件是：译码算法的已知条件是：q实际实际接收到的码字序列接收到的码字序列r,r=(r1,r2,rN)q发端所采用的编码算法和该算法产生的发端所采用的编码算法和该算法产生的码集码集XN,满足满足 q信道模型及信道参数。信道模型及信道参数。12c(,)XiiiiNNccc信息论基础B

19、6.2.2最优译码与最大似然译码最优译码与最大似然译码n最佳译码最佳译码，也叫最大后验概率译码，也叫最大后验概率译码(MAP)n最大似然译码最大似然译码(MLD)cmax(c/r)iiP cmax(r/c)iiP 编码器编码器 消息组消息组mi 码字码字ci 接收码接收码r 估值估值 消息消息 ic im 信道信道译码译码 消息还原消息还原信息论基础Bn如果如果q构成码集的构成码集的2K个码字以相同概率发送，满足个码字以相同概率发送，满足P(ci)=1/2K，i=1,2,2K qP(r)对于任何对于任何r都有相同的值，满足都有相同的值，满足P(r)=1/2K n则则P(ci/r)最大等效于最大

20、等效于P(r/ci)的最大，在此前提的最大，在此前提下最佳译码等效于最大似然译码。下最佳译码等效于最大似然译码。(c)(r/c)(c/r),1,2,2(r)KiiiPPPiP 信息论基础Bn对于无记忆信道，对于无记忆信道，n例：例：BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最小最小汉明距离译码汉明距离译码。n汉明距离译码是一种硬判决译码。由于汉明距离译码是一种硬判决译码。由于BSC信信道是对称的，只要发送的码字独立、等概，汉道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。明距离译码也就是最佳译码。1(r/c)(/)NijijjMaxPMaxP rc 信息论

21、基础B6.3 线性分组码线性分组码n码集码集C能否构成能否构成n维维n重矢量空间的一个重矢量空间的一个k维维n重重子空间？子空间？n如何寻找最佳的码空间？如何寻找最佳的码空间？nqk个信息元组以什么算法一一对应映射到码空间。个信息元组以什么算法一一对应映射到码空间。n码率编码效率：码率编码效率：Rc=k/n 消息消息m (n,k)码字码字c m=(mk-1,m1,m0)分组编码器分组编码器 c=(cn-1,c1,c0)qk qn信息论基础B6.3.1生成矩阵和校验矩阵生成矩阵和校验矩阵 c m G 1n 1k kn 码字码字 消息消息 生成矩阵生成矩阵 Ggk-1g1g0T，有，有k个个(1n

22、)行矢量，如行矢量，如何选择呢？何选择呢？信息论基础B线性分组码的形成线性分组码的形成 c=mk-1 gk-1+m1 g1+m0 g0 码空间的所有元素（即码字）都可以写成码空间的所有元素（即码字）都可以写成k个基底个基底的线性组合的线性组合由于由于k个基底即个基底即G的的k个行矢量线性无关，矩阵个行矢量线性无关，矩阵G的的秩一定等于秩一定等于k。当信息元确定后，码字仅由当信息元确定后，码字仅由G矩阵决定，因此我矩阵决定，因此我们称这们称这kn 矩阵矩阵G为该为该(n,k)线性分组码的生成矩线性分组码的生成矩阵。阵。信息论基础B生成矩阵生成矩阵G(kn)的特点的特点n想要保证想要保证(n,k)

23、线性分组码能够构成线性分组码能够构成k维维n重子重子空间，空间，G 的的k个行矢量个行矢量gk-1,g1,g0必须是线性必须是线性无关的，只有这样才符合作为基底的条件。无关的，只有这样才符合作为基底的条件。n由于基底不是唯一的，所以由于基底不是唯一的，所以G也就不是唯一的。也就不是唯一的。n不同的基底有可能生成同一码集，但因编码不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。方法不同也不能说是同样的码。信息论基础B系统形式的生成矩阵系统形式的生成矩阵 (n,k)码的任何生成矩阵都可以通过行运算码的任何

24、生成矩阵都可以通过行运算（以及列置换）简化成（以及列置换）简化成“系统形式系统形式”。G=Ik P =Ik是是kk单位矩阵，单位矩阵，P是是k(n-k)矩阵。矩阵。(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 信息论基础B生成的码字生成的码字Cn前前k位由单位矩阵位由单位矩阵Ik决定，等于把信息组决定，等于把信息组m原封不原封不动搬到码字的前动搬到码字的前k位；位；n其余的其余的n-k位叫冗余位或位叫冗余位或一致校验位一致校验位，是前，是前k个信个信息位的线性组合。息位的线性组合。n这样生成的（这样生成的（n,k）码

25、叫做）码叫做系统码系统码。n若生成矩阵若生成矩阵G不具备系统形式，则生成的码叫做不具备系统形式，则生成的码叫做非系统码非系统码。n系统化不改变码集，只是改变了映射规则。系统化不改变码集，只是改变了映射规则。信息论基础B系统码系统码n若通过行运算和列置换能将两个生成矩阵若通过行运算和列置换能将两个生成矩阵G互等，互等，则称这两个则称这两个G等效等效。n非系统码的非系统码的G可通过运算转变为系统码的可通过运算转变为系统码的G。n等效的两个等效的两个G生成的两个生成的两个(n,k)线性码也是等效的。线性码也是等效的。n因此，每个因此，每个(n,k)线性码都可以和一个系统的线性码都可以和一个系统的(n

26、,k)线性码等效。线性码等效。信息论基础B空间构成空间构成nn维维n重空间有相互重空间有相互正交的正交的n个基底个基底n选择选择k个基底构成码个基底构成码空间空间Cn选择另外的选择另外的(n-k)个个基底构成空间基底构成空间HnC和和H是对偶的是对偶的 CHT0,GHT=0 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重H 空间空间m C信息论基础B校验矩阵校验矩阵n将将H空间的空间的n-k个基底排列起来可构成一个个基底排列起来可构成一个(n-k)n矩阵，称为矩阵，称为校验矩阵校验矩阵H。用来校验接收到。用来校验接收到的码字是否是正确的；的码

27、字是否是正确的；nG是是(n,k)码的生成矩阵，码的生成矩阵，H是它的校验矩阵；是它的校验矩阵；nH是是(n,n-k)对偶码的生成矩阵，它的每一行是对偶码的生成矩阵，它的每一行是一个基底。一个基底。G则是它的校验矩阵。则是它的校验矩阵。nGHT=0，H PT In-k，二进制时，负号可，二进制时，负号可省略。省略。信息论基础Bn例例6-2(6,3)线性分组码，其生成矩阵是线性分组码，其生成矩阵是 G=求：求：(1)计算码集，列出信息组与码字的映射关系。计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出将该码系统化处理后，计算系统码码集并列出映射关系。映射关系。

28、(3)计算系统码的校验矩阵计算系统码的校验矩阵H。若收码。若收码r=100110,检验它是否码字？检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。根据系统码生成矩阵画出编码器电原理图。1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 信息论基础B例例6-2 码集与映射关系码集与映射关系信息信息 码字码字 系统码字系统码字000 000000 000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010

29、信息论基础B例例6-2 二元二元(6,3)线性分组码编码器线性分组码编码器 m0m1m2 输入输入 输出输出 c0c1c2信息论基础Bn例例(6,3)线性分组码，其生成矩阵是线性分组码，其生成矩阵是G1=G2=H=C=mG1C=mG21 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 信息论基础B码集与映射关系码集与映射关系信息信息m2-0 c5-0 系统码字系统码字c5-0 000 000000 00000000111100000

30、1101010110101010011011001101011110100101011100110101010011101011110011110110101111100110111000信息论基础B二元二元(6,3)线性分组码编码器线性分组码编码器信息论基础B二元二元(6,3)线性分组码编码器线性分组码编码器信息论基础B6.3.2 伴随式与标准阵列译码伴随式与标准阵列译码 m C=(cn-1,c1,c0)R=(rn-1,r1,r0)(n,k)信道信道定义定义差错图案差错图案E E(en1,e1,e0)RC (rn-1cn-1,r1c1,r0c0)二进制码中模二进制码中模2加与模加与模2减是等

31、同的，因此有减是等同的，因此有E=R C 及及R=C E 信息论基础B伴随式伴随式S的定义的定义因为因为CHT=0 所以所以RHT(CE)HTCHTEHT=EHT如果收码无误：必有如果收码无误：必有RC即即E0，则则EHT=0 RHT=0。如果收码有误：即如果收码有误：即E 0，则则RHT=EHT 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差错仅仅与差错图案图案E有关，而与发送码有关，而与发送码C无关。定义无关。定义伴随伴随式式S S=(sn-k-1,s1,s0)=RHT=EHT 信息论基础B伴随式伴随式S的意义的意义n从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字

32、是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。n差错图案差错图案E是是n重矢量，共有重矢量，共有2n个可能的组合，而个可能的组合，而伴随式伴随式S是是(n-k)重矢量，只有重矢量，只有2n-k个可能的组合，个可能的组合，因此不同的差错图案可能有相同的伴随式。因此不同的差错图案可能有相同的伴随式。n接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT；如果能知道对应的如果能知道对应的E，则通过，则通过C=RE而求得而求得C。RHT=S?C=RE R S E C 只要只要E正确，译出的码也就是正确的。正确，译出的码

33、也就是正确的。信息论基础B差错图案差错图案E的求解的求解(1)可以通过解线性方程求解可以通过解线性方程求解E：S=(sn-k-1,s1,s0)=EHT =(en-1,e1,e0)得到线性方程组：得到线性方程组：sn-k-1=en-1h(n-k-1)(n-1)+e1h(n-k-1)1+e0 h(n-k-1)0 s1 =en-1h1(n-1)+e1 h11+e0 h10s0 =en-1h0(n-1)+e1 h01+e0 h00(1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 信息论基础B差错图案差错图案E的求解的求解(2)n上述方程组中有上述

34、方程组中有n个未知数个未知数en1,e1,e0，却只，却只有有n-k个方程，可知方程组有多解。个方程，可知方程组有多解。n在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有个方程导致每个未知数有2k个解。个解。n因此，由上述方程组解出的因此，由上述方程组解出的E可以有可以有2k个解。个解。到底取哪一个作为附加在收码到底取哪一个作为附加在收码R上的差错图案上的差错图案E的估

35、值呢？的估值呢？n概率译码：概率译码：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个数的个数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估的估值。该方法概念上很简单但计算效率不高。值。该方法概念上很简单但计算效率不高。信息论基础B依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率：0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻，所以该译码方法实际上体现

36、了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。信息论基础B标准阵列译码表标准阵列译码表 上述的概率译码，如每接收一个码上述的概率译码，如每接收一个码R就就要解一次线性方程，那就太麻烦了。好在要解一次线性方程，那就太麻烦了。好在伴随式伴随式S的数目是有限的的数目是有限的2n-k个，如果个，如果n-k不不太大，我们可以预先把不同太大，我们可以预先把不同S下的方程组解下的方程组解出来，把各种情况下的最大概率译码输出出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那

37、样查一必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做下码表就可以了。这样构造的表格叫做标标准阵列译码表准阵列译码表。信息论基础B标准阵列译码表的构成标准阵列译码表的构成 n表中所列码字是接收到的码字表中所列码字是接收到的码字R；n将没有任何差错时的收码将没有任何差错时的收码R放在第一行，收码等于发码放在第一行，收码等于发码R=C(C Ci,i=0,1,2k-1),差错图案为全零差错图案为全零E0=(0,00)，伴随式为全零伴随式为全零S0=(0,00)。由于有。由于有2k个码字，码表有个码字，码表有2k列。列。n在第在第2到第到第n+1的的n行中差错图案的所有重量为行中

38、差错图案的所有重量为1(共共n个个)。n如果如果(1+n)17的单个突发差错的单个突发差错6.所有长度所有长度2的两个突发差错的两个突发差错1.所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2.所有所有3个的随机差错个的随机差错3.所有长度所有长度16的单个突发差错的单个突发差错4.以以(1-2-17)的概率检出长度的概率检出长度17的单个突发差错的单个突发差错5.以以(1-2-16)的概率检出长度的概率检出长度17的单个突发差错的单个突发差错6.所有长度各所有长度各2的两个突发差错的两个突发差错同上同上CRC-ITU-T1.所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为

39、偶数）2.所有所有14个的随机差错个的随机差错3.所有长度所有长度32的单个突发差错的单个突发差错4.以以(1-2-33)的概率检出长度的概率检出长度33的单个突发差错的单个突发差错5.以以(1-2-32)的概率检出长度的概率检出长度33的单个突发差错的单个突发差错6.所有长度各所有长度各2的两个突发差错的两个突发差错CRCITU-T信息论基础B例例6.10 某某CRC码的生成多项式码的生成多项式 g(x)=x4+x+1。如果。如果想发送一串信息想发送一串信息110001的前的前6位并加上位并加上CRC校验，校验，发码应如何安排？收码又如何检验？发码应如何安排？收码又如何检验？解：解：本题信息

40、多项式本题信息多项式 m(x)=x5+x4+1,即即k=6，因此，因此n=10，degg(x)=4=n-k。将将xn-k m(x)除以除以g(x),得余式得余式 r(x)=xn-k m(x)mod g(x)=x4(x5+x4+1)mod g(x)=(x9+x8+x4)mod g(x)=x3+x2 于是发码于是发码C(x)=xn-k m(x)+r(x)=x9+x8+x4+x3+x2，对应的码字是对应的码字是(1100011100)。接收端的接收端的CRC校验实际上就是做除法。如果收校验实际上就是做除法。如果收码无误，码无误，R(x)除以除以g(x)应得余式应得余式0；反之，如果余式；反之，如果余式不等于零就说明一定有差错。不等于零就说明一定有差错。