CS计算机代考程序代写第6章信道编码

第6章信道编码

信道传输导致接收信号发生差错，信道编码的目的是提高传输可靠性，可分为两个层次上的问题：：
如何正确接收载有信息的信号

——线路编码（通信原理）
如何避免少量差错信号对信息内容的影响

——纠错编码
通过增加相关度，使接收端能够发现错误，纠正错误，叫做差错控制编码或纠错编码。

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
第6章信道编码

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
本章内容
有扰离散信道的编码定理
纠错编译码的基本原理与分析方法
线性分组码
卷积码

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1 有扰离散信道的编码定理
差错和差错控制系统分类
矢量空间与码空间
随机编码
信道编码定理
联合信源信道编码定理

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
差错类型：
差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示
差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示
对于二进制传输系统，符号差错等效于比特差错；
对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。

6.1.1 差错和差错控制系统分类

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
差错图样（error pattern）
定量地描述信号的差错，收、发码之“差” ：

差错图样E＝发码C－收码R （模M）
例：8进制(M=8)码元，

若发码 C=（0,2,5,4,7,5,2）
收码变为 R=（0,1,5,4,7,5,4）
差错图样 E=C－R=（0,1,0,0,0,0,6）（模8）
二进制码：E=C  R 或 C = R  E ，差错图样中的“１”既是符号差错也是比特差错，差错的个数叫汉明距离。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
差错图样类型
随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；
突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
纠错码分类
从功能角度：检错码、纠错码
对信息序列的处理方法：分组码、卷积码
码元与原始信息位的关系：线性码、非线性码
差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。
构码理论：代数码、几何码、算术码、组合码等

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
差错控制系统分类
前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错
反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码
混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1.2矢量空间与码空间
F表示码元所在的数域，对于二进制码，F代表二元域{0,1}
设n重有序元素的集合V= {Vi },

若满足条件：
V中矢量元素在矢量加运算下构成加群；
V中矢量元素与数域F元素的标乘封闭在V中；
分配律、结合律成立，

则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
矢量空间中矢量的关系
对于域F上的若干矢量
线性组合：

线性相关：

　　　　　　　　
其中任一矢量可表示为其它矢量的线性组合
线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
矢量空间与基底
一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。
n维矢量空间应包含n个基底
基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
二元域GF(2)上三重矢量空间
以（100）为基底可张成一维三重子空间V1，含21 =2 个元素，即

以(010)(001)为基底可张成二维三重子空间V2，含 22 =4个元素，即

以(100)(010)(001)为基底可张成三维三重空间V,含 23 =8个元素，V1和V2都是V的子空间。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
矢量空间
每个矢量空间或子空间中必然包含零矢量
两个矢量正交：V1V2＝ 0
两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交
正交的两个子空间V1、V2互为对偶空间 (Dual Space)，其中一个空间是另一个空间的零空间（null space，也称零化空间）。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
码空间

消息k长 (n , k) 码字n长
qk 种分组编码器 qn种
k维k重矢量 n维n重矢量

通常qn>> qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
分组编码的任务
选择一个ｋ维n重子空间作为码空间。
确定由k维k重信息空间到ｋ维n重码空间的映射方法。

码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1.3随机编码
运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。
用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1.3随机编码
在(N,K)分组编码器中随机选定的码集有qNM种
第m个码集(记作{c}m )被随机选中的概率是

设与这种选择相对应的条件差错概率是Pe({c}m)

全部码集的平均差错概率是

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1.3随机编码
必定存在某些码集

某些码集

若，就必然存在一批码集

即差错概率趋于零的好码一定存在

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.1.3随机编码
码集点数M=qK占N维矢量空间总点数qN的比例是 F =qK / qN = q-(N-K)
当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。
当F0 即(N-K)时，能否让平均差错概率？
Gallager在1965年推导了的上边界，并证明这个上边界是按指数规律收敛的。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
E(R)为可靠性函数，也叫误差指数
码率：R =( lbM) / N
M是可能的信息组合数，M=qK
N是每码字的码元数，
R表示每码元携带的信息量，单位是每符号比特（bit / symbol）

6.1.4信道编码定理

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
R在[0,R0]区间时E(R)~R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。

6.1.4信道编码定理

E(R)



C R
0 R0 -45

E(R)和R的关系曲线

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。
逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R >C，就不可能有任何一种编码能使差错概率任意小。

6.1.4信道编码定理

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

6.1.5 联合信源信道编码定理
传统的通信系统设计将信源编码和信道编码分成二部分进行：
针对各自信源的不同特点，进行不同的数据压缩，用最有效的二元码来表达这些不同的信源。
对于共同传输的数字信道来言，输入端只看成是一系列二元码。信道编码只针对信道特性来进行，不考虑不同信源的不同特性。
这种分两步编码处理的方法，其信源压缩编码只考虑信源的统计特性；而信道编码只考虑信道的统计特性。

优点是设计简单、通用性好，可以分别形成标准。
缺点是没有充分利用各自的优势，因而不是最佳的。
将信源编码和信道编码综合考虑，可进一步优化系统的整体性能。
如：可根据信源中信息的重要性不同采用不均等的错误保护等级(UEP)；将不好的信道容量分配给不敏感的信息，将容量利用到极致等等。

6.1.5 联合信源信道编码定理

信源－信道编码定理：

若信源S极限熵H小于信道容量C，则存在信源信道编码，使得Pe→0。
反之，对于任意平稳随机序列，若极限熵H >C，则错误概率远离零，即不可能在信道中以任意小的错误概率发送这随机序列。
6.1.5 联合信源信道编码定理

由此可见，当且仅当信源极限熵小于信道容量，在信道上能够无错误地传输平稳遍历信源。HR(D)，则在信源和信道处用足够复杂的处理后，总能以失真度D+再现信源的消息。

6.1.5 联合信源信道编码定理

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.2 纠错编译码的基本原理与分析
纠错编码的基本思路
译码方法－最优译码与最大似然译码

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
6.2.1纠错编码的基本思路
R不变，信道容量大者其可靠性函数E(R)也大；
C不变，码率减小时其可靠性函数E(R)增大

E(R)

R
0 R1 < R2 C1 < C2 增大E(R)的途径普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.2.1纠错编码的基本思路增大信道容量C 扩展带宽加大功率降低噪声减小码率R Q、N不变而减小K Q、K不变而增大N N、K不变而减小Q 增大码长N 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.2.2最优译码与最大似然译码译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列{r}, r=(r1,r2,…,rN) 发端所采用的编码算法和该算法产生的码集XN, 满足信道模型及信道参数。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著最佳译码，也叫最大后验概率译码(MAP) 最大似然译码( MLD) 6.2.2最优译码与最大似然译码消息组mi 码字ci 接收码r 估值消息编码器信道译码消息还原普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著如果构成码集的2K个码字以相同概率发送，满足P(ci ) = 1/2K ， i=1,2,…,2K P(r)对于任何r都有相同的值，满足P(r) = 1/2K 则P(ci /r)最大等效于P(r / ci)的最大，在此前提下最佳译码等效于最大似然译码。 6.2.2最优译码与最大似然译码普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著对于无记忆信道，例：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。 6.2.2最优译码与最大似然译码普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3 线性分组码消息m (n , k) 码字c m=(mk-1,…,m1,m0) 分组编码器 c=(cn-1,…,c1,c0) qk < qn 码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最佳的码空间？ qk个信息元组以什么算法一一对应映射到码空间。码率－－编码效率：Rc =k/n 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3.1 生成矩阵和校验矩阵 c ＝ m G 1×n 1×k k×n 码字消息生成矩阵 G＝[gk-1…g1g0]T，有k个(1×n)行矢量，如何选择呢？普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著线性分组码的形成 c = mk-1 gk-1+…+ m1 g1+m0 g0 码空间的所有元素（即码字）都可以写成k个基底的线性组合由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。当信息元确定后，码字仅由G矩阵决定，因此我们称这k×n 矩阵G为该(n,k)线性分组码的生成矩阵。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著生成矩阵G(k×n)的特点想要保证 (n,k)线性分组码能够构成k维n重子空间，G 的k个行矢量gk-1,…, g1, g0必须是线性无关的，只有这样才符合作为基底的条件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著系统形式的生成矩阵 (n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式” 。 G = [Ik  P ] = Ik是k×k单位矩阵，P是k×(n-k)矩阵。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著生成的码字C 前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著系统码若通过行运算和列置换能将两个生成矩阵G互等，则称这两个G等效。非系统码的G可通过运算转变为系统码的G。等效的两个G生成的两个(n,k)线性码也是等效的。因此，每个(n,k)线性码都可以和一个系统的(n,k)线性码等效。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著空间构成 n维n重空间有相互正交的n个基底选择k个基底构成码空间C 选择另外的(n-k)个基底构成空间H C和H是对偶的 CHT＝0, GHT=0 n维n重空间V k维k重 k维n重 n-k维信息组码空间 n重H 空间m C 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著校验矩阵将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的； G是(n,k)码的生成矩阵，H是它的校验矩阵； H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。 G则是它的校验矩阵。 GHT=0 ，H＝[－ PT In-k ]，二进制时，负号可省略。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-2 (6,3)线性分组码，其生成矩阵是 G= 求： (1)计算码集，列出信息组与码字的映射关系。 (2)将该码系统化处理后，计算系统码码集并列出映射关系。 (3)计算系统码的校验矩阵H。若收码r = [100110], 检验它是否码字？ (4)根据系统码生成矩阵画出编码器电原理图。 1 1 1 0 1 0 ① 1 1 0 0 0 1 ② 0 1 1 1 0 1 ③ 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-2 码集与映射关系信息码字系统码字 000 000000 000000 001 011101 001011 010 110001 010110 011 101100 011101 100 111010 100111 101 100111 101100 110 001011 110001 111 010110 111010 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-2 二元(6,3)线性分组码编码器 m0 m1 m2 输入输出    c0 c1 c2 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3.2 伴随式与标准阵列译码 m C=(cn-1,…,c1,c0) R=(rn-1,…,r1,r0) (n,k) 信道定义差错图案E E＝(en－1,…,e1,e0)＝ R－C ＝(rn-1－cn-1,…,r1－c1,r0－c0) 二进制码中模2加与模2减是等同的，因此有 E = R ＋ C 及 R = C ＋ E 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著伴随式S的定义因为CHT = 0 所以RHT＝(C＋E)HT＝CHT＋EHT= EHT 如果收码无误：必有R＝C即E＝0，则EHT= 0 RHT = 0。如果收码有误：即E  0，则RHT = EHT 0。在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S S = (sn-k-1,…,s1,s0) = RHT = EHT  普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。接收端收到R后，因为已知HT，可求出 S＝RHT；如果能知道对应的E，则通过C = R＋E而求得C。 RHT = S ? C = R＋E R S E C 只要E正确，译出的码也就是正确的。伴随式S的意义普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著差错图案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 h10 s0 = en-1h0(n-1) +… + e1 h01 + e0 h00 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著上述方程组中有n个未知数en－1,… e1,e0 ，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-( n-k) = k个方程导致每个未知数有2k个解。因此，由上述方程组解出的E可以有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。差错图案E的求解(2) 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著依据：若BSC信道的差错概率是p，则长度n的码中错误概率： 0个错 1个错 2个错 … n个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于p<< 1, >> >> >> … >>
出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
标准阵列译码表
上述的概率译码，如每接收一个码R就要解一次线性方程，那就太麻烦了。好在伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
表中所列码字是接收到的码字R；
将没有任何差错时的收码R放在第一行，收码等于发码R=C(CCi,i =0,1,…2k-1), 差错图案为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。
在第2到第n+1的n行中差错图案的所有重量为1 (共n个)。
如果(1+ n)<2n-k，再在下面行写出全部带有2个差错的图案 (共个)。如果总行数(1+n + )仍然小于2n-k，再列出带有3个差错的图案，以此类推，直到放满2n-k行，每行一个Ej, 对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。标准阵列译码表的构成普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 S0 E0 S1 E1  Sj Ej  标准阵列译码表 E1+C1  E0+C0= 0+0= 0 E0+C1= C1  E0+Ci= Ci  E1+C0= E1  E1+Ci        Ej+C0= Ej Ej+C1  Ej+Ci          普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著陪集和子集译码表中有2n-k行，每行是一个陪集，每陪集的第一个元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零差错图案E0(无差错)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的差错图案Ej (C0=0, Rj=Ej)。译码表中有2k列，每列是一个子集，每子集的第一个元素(位于第一行)叫子集头。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是码字Ci (E0=0, Ri=Ci) 。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6-3 一个(5,2)系统线性码的生成矩阵是G = 设收码R = (10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m= (00)、(01) 、(10)、(11)及已知的G求得4个许用码字为 C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校验矩阵： H = [ PT  I3 ] = 列出方程组：普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著伴随式有2n-k＝23＝8种组合，差错图案中代表无差错的有一种，代表一个差错的图案有种，已有6种。代表两个差错的图案有种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。例 6-3 译码表的构成普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6-3 标准阵列译码表 S0=000 E0+C0=00000 C1=10111 C2=01101 C3=11010 S1=111 E1=10000 00111 11101 01010 S2=101 E2=01000 11111 00101 10010 S3=100 E3=00100 10011 01001 11110 S4=010 E4=00010 10101 01111 11000 S5=001 E5=00001 10110 01100 11011 S6=011 E6=00011 10100 01110 11001 S7=110 E7=00110 10001 01011 11100 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6-3 将接收码R＝10101译码可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT = (10101) HT = (010) = S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101), 最后顺着所在列向上找出码字(10111)。先求出伴随式RHT = (010) = S4并确定S4所对应的陪集首（差错图案）E4=(00010)，再将陪集首与收码相加得到码字C= R+ E4= (10101)+ (00010)= (10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著对上例作进一步分析，还可以看到，该(5,2)码的dmin=3, 纠错能力是t = INT[(3-1)/2] = 1。因此，译码阵列中只有前6行具有唯一性、可靠性，真正体现了最大似然译码准则，而第7、8行的差错图案(00011)和(00110)中包含两个“1”，已超出了t= 1的纠错能力，译码已不可靠。比如，当收码R＝(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个差错图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。对例 6-3的分析普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3.3码距、纠错能力、MDC码及重量谱 N重码矢c = (cn-1,c n-2,…c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集发码一定在这个子集里，传输无误时的收码也一定位于该子集当出现差错时，接收的N重矢量: 对应到子集外空间某一点对应到该子集，却对应到该子集的另一点上普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 t d=7 dmin=3 d=5 C1 C2 C3 C4 C5 码集各码字间的距离是不同的，码距最小者决定码的特性，称之为最小距离dmin 这里dmin=3，纠错能力是1，检错能力是2 6.3.3码距、纠错能力、MDC码及重量谱普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著定理6.1 任何最小距离dmin的线性分组码，其检错能力为（dmin-1）, 纠错能力t为定理6.2 线性分组码的最小距离等于码集中非零码字的最小重量 dmin = min {w (C i )} C iC 及C i  0 6.3.3码距、纠错能力、MDC码及重量谱普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著定理6.3 (n,k) 线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4 (n,k) 线性分组码的最小距离必定小于等于 (n-k+1) dmin  (n-k+1) 6.3.3码距、纠错能力、MDC码及重量谱普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例： H＝ (7，4)线性码各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k +1＝4。 6.3.3码距、纠错能力、MDC码及重量谱普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著（n,k）线性码最小距离dmin的上边界是n-k +1。如果我们设计的（n,k）线性码的dmin达到了n-k +1，就是达到了设计性能的极点。因此，dmin＝ n-k +1的码称为极大最小距离码 (MDC – Maximized minimum Distance Code)。总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。 6.3.3码距、纠错能力、MDC码及重量谱普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件上式称作汉明限，任何一个纠t码都应满足上述条件。 6.3.4 完备码(Perfect code) 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3.4 完备码某二元(n,k)线性分组码能使等式成立，即该码的伴随式数目不多不少恰好和不大于t个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著汉明码(Hamming Code) 汉明码不是指一个码，而是代表一类码。汉明码的纠错能力t = 1，既有二进制的，也有非二进制的。二进制时，汉明码码长n和信息位k服从以下规律： (n,k)=(2m-1, 2m-1-m) 其中m= n-k，是正整数。当m＝3、4、5、6、7、8…时，有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)…。汉明码是完备码，因为它满足上述等式。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著汉明码校验矩阵的构成汉明码的校验矩阵H具有特殊的性质，能使构造方法简化。一个(n,k)码的校验矩阵有n－k行和n列，二进制时n-k个码元所能组成的列矢量总数是2n-k-1, 恰好和校验矩阵的列数n =2m-1相等。只要排列所有列，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6.4 构造一个m=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式： 0 0 0 1 1 1 1 列置换 1 1 1 0 1 0 0 H = 0 1 1 0 0 1 1  0 1 1 1 0 1 0 = [PT  I3] 1 0 1 0 1 0 1 1 1 0 1 0 0 1 再得生成矩阵G为 1 0 0 0 1 0 1 G = [I4  P] = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著高莱（Golay）码是二进制（23，12）线性码，其最小距离dmin＝7，纠错能力t =3。是完备码，因为满足等式 223-12 = 2048 = 在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin＝8。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3.5 循环码循环码是线性码的一个子类；满足下列循环移位特性：码集C中任何一个码字的循环移位仍是码字。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著循环码的多项式描述一般(n,k)线性分组码的k个基底之间不存在规则的联系，因此需用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就足以表示一个码的特征。既然只有一个基底，就无需矩阵，只要用多项式作为数学工具就足够了。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著把码字C＝[cn-1cn-2 …c1c0] 与一个不大于n-1次的码多项式C (x)对应起来。码多项式C (x)定义为： C(x) = cn-1xn-1+ cn-2 xn-2 +…+c1x +c0 对于二进制码，ci{0,1}, i = 0,…，n-1。循环码的多项式定义普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著循环移一位：(cn-1cn-2 …c1c0) (cn-2 …c1c0 cn-1) 循环移一位：C0(x) =cn-1 xn-1+cn-2 xn-2+…+c1x +c0 C1(x) = cn-2 xn-1+cn-3 xn-2+…+c0 x +cn-1 比较循环移位的前后，可用如下的多项式运算来表达循环移位移1位： C1(x) = xC0(x) mod(xn +1) 移2位： C2(x) = xC1(x) = x2C0(x) mod(xn +1)  移n-1位：Cn-1(x) = xCn-2(x) = xn-1C0(x) mod(xn +1) 循环码的循环移位普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著码字的组成根据码空间的封闭性，码字的线性组合仍是码字。 C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x) =(a0+a1x + a2x2+…+ an-1xn-1)C0(x) =A(x)C0(x) mod(xn +1) 其中C0(x)是一个码多项式，而A(x)是次数不大于n-1的任意多项式。对于二进制码，ai{0,1}, i = 0,…，n-1。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著生成多项式 C(x) =m(x) g(x) 码多信息生成项式多项式多项式生成多项式不是唯一的； g(x)＝x n-k + gn-k-1 x n-k-1+…+ g2 x2+ g1 x +1 是(n-k)次的首一码多项式，即(n-k)次项的系数为1 。 g(x)一定是(xn+1)的因子。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著校验多项式多项式xn+1可因式分解为xn+1＝g(x)h(x)的形式；如果g(x)代表(n，k)循环码的生成多项式，则h(x)代表该循环码的一致校验多项式，其阶次为k。 h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0。 C(x)h(x) = m(x)g(x)h(x) = m(x)( xn+1) = 0 mod(xn+1) 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6.5 研究一个长度n=7的循环码的构成方法 (1) 对(x7+1)作分解，找出n-k次因式。 x7+1＝(x+1)(x3+x2+1)(x3+x+1)， n-k 因式g(x) 对偶式h(x) 循环码 1 (x+1) (x3+x2+1)(x3+x+1) (7,6) 3 (x3+x2+1) (x+1)(x3+x+1) (7,4) 3 (x3+x+1) (x+1)(x3+x2+1) (7,4) 4 (x+1)( x3+x2+1) (x3+x+1) (7,3) 4 (x+1)(x3+x+1) (x3+x2+1) (7,3) 6 (x3+x2+1)(x3+x+1) (x+1) (7,1) 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著构成(7,3)循环码：选g(x) =(x+1) (x3+x+1) = (x4+x3+x2+1)，则C(x)=m(x)g(x)= (m2x2+m1x+m0) (x4+x3+x2+1)。当输入信息m=(011)时，m(x)=(x+1)，C(x)=( x+ 1)(x4＋x3＋x2＋1) = x5+ x2+ x1+ 1，对应码矢C = (0100111)。例 6.5 研究一个长度n=7的循环码的构成方法普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例 6.5 研究一个长度n=7的循环码的构成方法信息矢量m(m2 m1 m0) 码矢C(c6c5c4c3c2c1c0) 000 001 010 011 100 101 110 111 0000000 0011101 0111010 0100111 1110100 1101001 1001110 1010011 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著系统循环码码字的前k位原封不动照搬信息位而后面(n－k)位为校验位：C(x) = xn-k m(x) + r(x) 产生系统循环码的方法：将信息多项式m(x)预乘xn-k，即右移（n-k）位；将xn-k m(x)除以g(x)，得余式r(x)；得系统循环码的码多项式：C(x) = xn-k m(x) + r(x) 。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6.6 (7,3)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解：先以输入信息m=(011)即m(x) = ( x +1)为例， ①. xn-k m(x) = x4( x +1) = x5+ x4 ②. ( x5+ x4)除以(x4+ x3+ x2+ 1)，得余式(x3+ x) ③. C(x) = xn-k m(x) + r (x)＝( x5+ x4)+ (x3+ x), 对应码矢(0111010)。依次将(000)…(111)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.4 卷积码卷积码的产生分组码以孤立码块为单位编译码信息流割裂为孤立块后丧失了分组间的相关信息分组码长n越大越好，但译码运算量随n指数上升本节内容卷积码的基本概念和描述方法卷积码的最大似然译码维特比算法卷积码的性能限与距离特点普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著将信息序列分隔成长度k的一个个分组某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组。称L＋1为约束长度最重要的三个参数 (n,k,L) 6.4.1 卷积码的基本概念和描述方法普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 (n,k,L)卷积编码示意第i分组第i-1分组第i-2分组 …… 第i-L分组 m0i m1i … mk-1i m0i-1 … mk-1i-1 m0i-2 … mk-1i-2 … … … m0i-L m1i-L … mk-1i-L 输入 … … … …… … 卷积编码器（线性组合器） c0i c1i … cn-2i cn-1i 编码输出C i 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-11 二进制(3,2,1)卷积编码器本时刻m0=(m00,m10)=(01),上一时刻m1=(m01,m11)= (10) gknl表示记忆阵列第k行(k=0,1) 第l列(l =0,1)对第n个( n =0,1,2)码元的影响,共N×K×(L+1)= 3×2×2个系数： g000 = 1, g001 = 1, g010 = 0, g011 = 1,g020 = 1, g021 = 1, g100 = 0, g101 = 1, g110 = 1, g111 = 0,g120 = 1, g121 = 0。用矩阵表示  c0i 信号入 m  c1i C i 编码输出  c2i m0i m0i-1 m1i m1i-1 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著本时刻编码输出： C0=(c00, c10, c20 )= m0G0+m1G1 =(01) + (10) = (011)+(111) =(100) 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著卷积码名称的由来设编码器的初始状态为零（记忆阵列全体清0），随着时刻i的递推和k比特信息组(m0, m1,…, mL, mL+1,…)源源不断地输入，码字(C0, C1,…, CL, CL+1,…)源源不断地输出。在时刻i = 0 时，C0 = m0G0 i = 1 时，C1= m1G0 + m0G1   i = L 时，CL= mLG0 + mL-1G1…m0GL i=L+1时，CL+1= mL+1G0 + mLG1…m1GL 于是任何时刻i的输出码字：Ci = mi -l Gl 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著多项式表示 G(D)= G0+ G1D+…+ GLDL = gkn(D)=gkn0+gkn1D+gkn2D2+…+gknLDL= gknl Dl 例6-11中普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-8 二元(3,1,2)卷积码的转移函数矩阵G(D)=(1,1+D, 1+D+D2 )，根据转移函数矩阵， g00(D) = g000+ g001D + g002 D2 = 1 g01(D) = g010+ g011D + g012 D2 = 1＋D g02(D)= g020+g021D +g022 D2 = 1+D+D2 得 g000 = 1, g001 = 0, g002 = 0, g010 = 1, g011 = 1, g012 = 0, g020 = 1, g021 = 1, g022 = 1。  c0i 信号入 m  c1i 输出C i  c2i m0i m0i-1 m0i-2 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-9 图6-19 (3,1,2)卷积码状态流图假如输入信息序列是10110…， S0 1/111 S2 0/011 S11/110 S2 1/100 S3 0/010 S1…… 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著例6-10 卷积码网格图 S0(00)         1/111 0/001 0/001 S1(01)   1/111       S2(10)      0/010  1/110  S3(11)         t =0 T 2T 3T 4T 5T 6T 1/110 0/011 0/010 1/101 0/000 1/100 0/000 0/000 0/000 0/000 0/000 0/000 0/011 1/110 1/100 输入信息序列是10110…，输出码字是111，011，110，100，010… 第一部分：网格图第二部分：编码轨迹（路径）图普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著纠错能力分析分组码的纠错能力取决于码的最小距离，分组码的最大似然译码实际上就是最小距离译码；对于卷积码，不同之处仅在于，分组码考虑的是孤立码字间的距离，而卷积码考虑的是码字序列间的距离。卷积码序列间距离用自由距离df表示，其计算方法有：简单的卷积码可直接在网格图上推得；较复杂的卷积码可采用信号流图法，最具理论价值；最实用的方法是靠编程利用计算机来搜索。 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著第6章信道编码复习 6.1有扰离散信道的编码定理 6.1.1 差错和差错控制系统分类 6.1.2 矢量空间与码空间 6.1.3 随机编码 6.1.4 信道编码定理 6.1.5 联合信源信道编码定理 6.2 纠错编译码的基本原理与分析方法 6.2.1 纠错编码的基本思路 6.2.2 译码方法－最优译码与最大似然译码普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 6.3 线性分组码 6.3.1 线性分组码的生成矩阵和校验矩阵 6.3.2 伴随式与标准阵列译码 6.3.3 码距、纠错能力、MDC码及重量谱 6.3.4 完备码 6.3.5 循环码 6.4卷积码 6.4.1 卷积码的基本概念和描述方法第6章信道编码复习普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著概念：差错符号、差错比特差错图样：随机差错、突发差错纠错码分类：检和纠错码、分组码和卷积码、线性码与非线性码、纠随机差错码和纠突发差错码第6章信道编码复习普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著矢量空间与码空间 n维n重空间有相互正交的n个基底选择k个基底构成k维n重码空间C 选择另外的(n-k)个基底构成空间H C和H是对偶的，正交的 CHT＝0, GHT=0 n维n重空间V k维k重 k维n重 n-k维信息组码空间 n重H 空间m C 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著 * 普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著有扰离散信道的编码定理若传信率RC，就不可能有任何一种编码能使差错概率任意小。

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
差错控制的途径
从公式
增大码长N
增大可靠性函数E(R)：加大信道容量C

减小码率(传信率)R。
从概念上
利用冗余度（增强相关性）
噪声均化(随机化)

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
最优译码与最大似然译码
最佳译码＝ Max P(ci /r)，性能优，实现难
最大似然译码＝ Max P(r / ci)，性能次优，实现容易
最佳译码等同最大似然译码：
码集的码字以相同概率发送
接收码等概分布

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
线性分组码
线性分组码基本概念
码元、码字、码集
重量、重量分布、恒重码
线性码（封闭性）
基底、矢量正交、矢量空间正交、对偶空间、线性相关、线性无关

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
生成矩阵和校验矩阵
生成矩阵G：C＝mG
校验矩阵H：CHT＝0
系统形式：G＝[Ik|P]，H＝[PT|In-k]
差错图案E=R-C，伴随式S＝RHT＝EHT
标准阵列译码表

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
码距与纠、检错能力
码的总体性能取决于码距的分布特性（重量谱），而纠、检错能力取决于其中的最小者dmin ，dmin = min {w (C i )
检、纠错能力：
可检dmin–1个差错
可纠t= INT[(dmin–1)/2]个差错
校验矩阵H中有（dmin-1)列线性无关
dmin  (n-k+1)，极大最小距离码

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
特殊的线性分组码
完备码
汉明码： t=1，(2m-1，2m-1-m)
高莱（Golay）码：二进制（23，12）线性码，其最小距离dmin＝7，纠错能力t=3

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
循环码
循环码用多项式表示： C(x)=m(x)g(x)
生成多项式： xn+1＝g(x)h(x)
校验多项式：C(x)h(x)=0 mod(xn+1)
g(x)＝x n-k + gn-k-1 x n-k-1+…+ g1 x +1
系统循环码：C(x) = xn-k m(x) + r (x)，

r (x) = xn-k m(x) mod g(x)

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著
卷积码
(n,k,L)
表示：矩阵、多项式、结构图、状态图、网格图

普通高等教育“十五”国家级规划教材《信息论与编码》曹雪虹等编著

01(1)
(,,,,,),
iiiijinij
VVVVVVF
–
=Î
LL

12
,,,
ik
VVVV
L
及

1122
,()
kiii
VaVaVaVaF
=++Î
L

1122
0,()
iii
aVaVaVaF
++=Î
L
且
不
全
为
零

12
,,,
n
VVV
L

1
{(000),(100)}
=
V

2
{(000),(001),(010),(011)}
=
V

()
({})
NM
m
Pq
–
=
c

11
({})({})({})
NMNM
qq
NM
eemmem
mm
PPPqP
–
==
==
åå
ccc

({})
eme
PP
>
c

({})
eme
PP
< c 0 e P ® ({})0 em P ® c e P () NER e Pe - < () NER e Pe - < 12 (,,,) N iiiiN ccc =Î cX L ˆ i c ˆ i m ˆ max(/) ii P = ccr ˆ max(/) ii P = crc ()(/) (/),1,2,,2 () K ii i PP Pi P == crc cr r L 1 (/)(/) N ijij j MaxPMaxPrc = = Õ rc (1)(1)(1)1(1)0 1(1)1110 0(1)0100 100 010 0001 knkkk nk nk ppp ppp ppp ----- -- -- éù êú êú êú êú ëû L L MOMM M L MMOM L (1)(1)(1)1(1)0 1(1)1110 0(1)0100 T nknnknk n n hhh hhh hhh ------- - - éù êú êú êú êú ëû L MOMM L L 2 n æö ç÷ èø 2 n æö ç÷ èø 1 1 0 2 2 nk nk -- -- + = EC E 11 22 nknk ---- Þ SE 1 1 2 nk -- + EC 1 2 nk i -- + EC 1 221 nkk -- - + EC 21 k j - + EC 1 21 k - + EC 0 2121 kk -- += ECC ú û ù ê ë é 1 0 1 1 0 1 1 1 0 1 i c ˆ 2423222120 1413121110 0403020100 11100 10010 11001 hhhhh hhhhh hhhhh éùéù êúêú êúêú êúêú ëûëû ＝ 2424323222121020432 141431321211101041 0404303202101000430 seheheheheheee sehehehehehee seheheheheheee =++++=++ =++++=+ =++++=++ 5 5 1 æö ç÷ èø ＝ 5 10 2 æö ç÷ èø ＝ min 1 2 d tINT - éù = êú ëû 1110100 0111010 1101001 éù êú êú êú ëû 0 2 012 t nk i nnnnn ti - = æöæöæöæöæö ³++++= ç÷ç÷ç÷ç÷ç÷ èøèøèøèøèø å L 0 2 t nk i n i - = æö = ç÷ èø å 1 0 11(21)22 mmnk i n n i - = æö =+=+-== ç÷ èø å 232323 1 123 æöæöæö +++ ç÷ç÷ç÷ èøèøèø 000 0 000102 000 101112 101 011 ggg G ggg éù éù = êú êú ëû ëû ＝ 111 1 000102 111 101112 111 100 ggg G ggg éù éù = êú êú ëû ëû ＝ 101 011 éù êú ëû 111 100 éù êú ëû 0 L l = å 00010(1) 10111(1) (1)0(1)1(1)(1) ()()() ()()() ()()() N N KKKN gDgDgD gDgDgD gDgDgD - - ---- éù êú êú êú êú ëû L L MMOM L 11 () 11 DDD D D ++ éù = êú ëû G 0 L l = å () NER e Pe - < () NER e Pe - < ˆ i c ˆ i c 0 2 t nk i n i - = æö = ç÷ èø å

Related Posts