信息论与编码(第三版) 第6章 信道编码理论

原始
数
符号
信息
据
信源
X
信源编码
Y
差错控制 编码
Z
调制
信息错误
数据错 误一定
物理信道
条件：实
信宿
重建 符号
Xˆ
信源译码
Yˆ 差错控制 Zˆ
接收 信息
译码
接收 数据
解调
注
际信息传 输速率不 大于信道
容量，
意 1.信道一定，数据出现差错的概率一定，这是无
法改变的，与差错控制编码/译码方式无关
2.数据出现差错的概率不可改变，但是可以通过引 入差错控制编码/译码，降低信息传递中的错误
错时，才会造成无法识别的错误，所以错误译码概率为
pe2 102
能发现传输中的一个错误,但不能自动纠正。
❖ (3,1)重复码。 ❖ 两个码字是（000）和（111），R=1/3 d0=2。 ❖ 设发送端发送码字是（000），若收到的是（001）或（010）
或（100），则根据大数译码准则正确地判断为（000）， 信息组为0； ❖ 若收到的是(011)，(101 ) ，(110 ) ，(111) 中之一，则造成 错误译码，错判为信息组是”1”. ❖ 正确译码的概率为
两种不同译码方法(控制方式)，得出的译码错误概 率不同
定理6.1 任意(n,k)分组码，如果要在码字内
(1) 检测e个随机错误，则要求码的最小距离满足d0 ≥ e+1
(2) 纠正t个随机错误，则要求码的最小距离满足d0 ≥ 2t+1
(3) 纠正t个随机错误，检测e(e>t)个随机错误,则要求码的 最小距离满足d0 ≥ e+t+1
正错误，
将信息序列划分为
二、信息
分组码
卷积码
组，但当前码组的编
序列处理 方法
将信息序列划分为位 为一组，然后对各个
信息组分别进行编码，
形成对应的一个码字
译码不仅与当前信息
卷积 组有关，而且与前面
要素 移位、 相加
若干码组的编译码有 关，可以利用码组的
相关性进行译码
三、码元 与原始信 息之间的 关系
对于分组码而言，码率R和最小距离d0是两个最重 要的参数。
纠错码的基本任务就是构造码率R一定，最小距离 d0尽可能大的码； 或者d0一定，码率R尽可能高的码。
❖ 例6.2 讨论(n,1)重复码的检错能力和错误译码概率，假设码 元错误概率为 pe =0.1.
❖ (2,1)重复码。 ❖ 两个码字是（00）和（11） ,R=1/2,d0=2. ❖ 出错(1)0011 或者1100 ❖ 若用不完备译码（并与ARQ结合），只有当两个码元同时出
主要适合随机错 误信道，纠正其 中可能产生的随 机错误
纠突发错误码
主要用于纠正 信息传输过程 中的突发错误
码元错误成串 出现，山区运 行的列车，高 速移动的汽车， 城市某些区域
五、码 元取值
二进制码 M进制码
纠错码
线性码
分组码
循环码
非循环码
非线性码 卷积码
纠随机 错误码
纠突发 错误码
纠随机与突 发错误元都是原始信息元 的线性组合
非线性码的码元不是 信息元的线性组合
线性码的特点：任意 两个线性码字的线性 组合仍然是一个码字
当前许多好码都是线性码
四、构 造码字 的理论
代数码
近世 代数
几何码
投影 几何
算术码 数论
组合码
排列组 合+数论
五、差 错的类 型
高斯信道
随机纠错码
信号传输过程中出现大的 信号波形畸变，导致信号 检错时发生错误，进而出 现 码元错误
叠加强的干扰 或者噪声
信号传输过程 中出现线性或 者非线性失真
线性失真
信号传输过程中不同的频率 分量增益不同，或者由于非
线性相位引起的延时不同
非线性 失真
系统的非线性引起的， 会产生新的频率分量
线性失真可以通过均 衡来解决
(4) 纠正t个随机错误, ρ个删除,则要求码的最小距离满足 d0 ≥ ρ +2t+1
分组码的最小汉明距离满足下列关系
d0 n k 1
奇偶校验码是只有一个检验元的分组码 最小汉明距离为2，只能检测一个错误， 不能纠错。
是不等式， 不能用于计
算d0
差错 控制 译码 已知 条件
任务
6.3 译码规则
❖ 差错图样中的1就是符号差错，同时也是比特差错，而差错 的个数就是汉明距离。
C (1010)
R (0011)
E C R (1001)
一、功能
纠错码的分类
检测码
纠错码
只检测信息传输是否出现错 误，本身没有纠错的能力
不仅能够检测信 息传输中的错误，
并且能够自动纠
循环冗余校验码、 奇偶校验码等
Q (1 pe )3 3 pe (1 pe )2
❖ 该码能纠正序列中的一个错误，此时错误译码概率
p 1 Q 1 (1 pe )3 3pe (1 pe )2 2.8102
若该码不用作纠错，而采用不完备译码进行检错，则可以 发现两个错误，与ARQ系统结合后，错误译码概率减至
p3e 103
d0
min {d(x,
x, y(n,k )
y)}
计算最小汉明距离方法1 将所有许用码字进行比较，记录每次比较的 汉明距离，最后取汉明距离的最小值即可
总的比较次数为 1 2 3 L 2k 1 (2k 1)2k
2
无论是否 线性分组
码
这种方法 都有效
特点：计算量很 大但是很简洁
❖ 例6.1 （3,2）码共有四个码字，分别为000，011，101， 110，显然d0 =2。 最小汉明距离d0是分组码的重要参数之一，表明 了该分组码抗干扰能力的大小，与码字的检错、 纠在错相能同力的有译关码，规则d0下越，大错，误码译的码抗的干概扰率能越力小越。强，
6.3.1两种译码规则
最大概率译码(MAP) 错误译码的概率最小，也称最小错误概率译码
最大似然译码(MLD)
MAP的简化形式
单个符号传输情况(二元信道)
信道
输入X
0 1 pe
信道 输出Y
0
根据接收符号y来估计 发送符号x是0还是1
计算后验概率p(xi|y)
估值准则
x$ max P(xi | y)
结果是译码错误最 小，所以也称最小
检测纠正 数据错误
制定规则 引入冗余 提供检错纠 错的可能
线性分组 码还是卷 积码，或 者其组合
差错编码 差错译码
共同完成
根据已知的规则， 利用引入冗余
按照某种原则(译 码方法)进行检错、
纠错
硬判决译码、软判 决译码； 最大似然译码还是 最小错误概率译码 等等
6.1 差错、差错控制系统分类
差错的 本质
错误概率译码
pe pe
1
1 pe
1
使用后验概率最大 为准则，所以称为 最大后验概率译码， 简称最大概率译码
❖ 根据贝叶斯公式
P(0 | y) p( y | 0) p(x 0) p( y | 0) p
p( y)
p( y)
P(1| y) p( y |1) p(x 1) (1 p) p( y |1)
第六章 信道编码理论
信息论研 究问题
无失真 编码
限失真 编码 香农第 3定理
可靠性
本章和后续章节
有效性
等长编码 变长编码
无失真编码 限失真编码
第4、5章讨论
信息率受到熵的限制，平均码长 不小于熵
香农第1定理
平均码长受到信息 率失真函数限制
在平均失真一定条 件下，编码输出码 率不小于平均失真 所对应信息率
信号无失真传 输条件：通频 带内系统增益 为常数；相位 为线性(群延时
相等)
❖ 信号差错的指标通常用概率大小表征，符号差错概率 也称为误码元率，是指信号差错的概率；
❖ 误比特率则是表示信息差错概率的一种方法 ；
❖ 对于M进制码元，差错图样E为
E (C R)(mod M )
❖ 二进制码而言 E CR
本章讨论通信中的另外一个问题——通信的可靠性问题：
即如何选择 译码规则和 编码方法
减少信道传 输中的信息 差错
由于信道噪声或者干扰的存在， 会产生数据传输错误。
信道编码定理，也 称为香农第二定理
通信原理告诉我们，信 道一定，数据传递错误 一定
以二进制调幅+高斯白噪声为例， 介绍虚警概率、漏报概率，以及 计算错误概率的过程和方法
6.2 纠错码的基本概念
定义6.1 分组码就是对每个k位长的信息组，按照一定规则
增加r=n-k位校验码元，构成长度为n的序列(Cn-1Cn-2….C1C0) 该序列称为码字（或者码组、码矢）。
信息组排列数(二元数据)2k
经过编码后相应码字数(二元数据)2k
分组码就是确定某种规则从2n种排列中挑选2k个码字
不同的编码规则产生不同的码字， 称被选中的2k个n重为许用码组
其余的2 n-2k个n重为禁用码组
编码不会出现，许用 码字经过信道后，可 能会出现，一旦出现， 数据传输出错（检测 的依据）
分组码的码率为 R k / n
是衡量分组码编码有效性的基本 参数，表示了信息位在码字中所 占的比例。
在纠错能力相同情况下，码率 越大效率越高，有利于提高信息 传输的效率。
根据规则
检测错误
反馈 信道
检测 结果
优点
1编译码设备比较简单
2冗余一定，检错码的检错能力比纠错码的 纠错能力要高的多，所以系统具有极强的 纠错能力
3能获得极低的误码率
不足
1信道质量不好时， 数据不同重发，导 致效率下降
由于检错码的检错能力 与信道干扰的变化基本 无关，因此这种系统的 适应性很强，特别适应 于短波、散射、有线等 干扰情况特别复杂的信 道中
定义6.2 卷积码(n0,k0,m)是对每段长度为k0的信息组， 按照一定的规则增加增加r0=n0-k0位校验码元，构成长度 为n0的码段，r0个校验元不仅与当前本段的信息元有关， 而且与前m段的信息元有关
当信息元不断输入时，输出码序列为半无限长
❖ 工作过程分析:
❖ 假设移位寄存器的初始状态为 00，输入信息序列（1 1 0 1 0 0）＝>编码输出为（11， 10，10，00，01，11，00 ）。 码率为 R k0 / n0
❖ 为了获得合适的误码率，往往按照信道最差的情况设计纠错 码，增加的冗余码元比检错码要多，编码效率一般较低。
❖ 随着编码理论的发展和大规模集成技术的发展，复杂算法的 译码设备越来越简单，成本越来越低，所以在实际中这种方 式得到广泛应用
二、混合纠错方式(HEC)
该编码方式是前两种方式的折中 发送的码不仅具有检错功能，而且具有一定的纠错能力。 接收端接收到码序列后，首先检测出现错误 如果序列错误在码的纠错能力内则自动纠正错误； 如果超出码的纠错能力，则接收端通过反馈信道将出错信 息发送给发送端，要求发送端重发码该码字序列。 由于该方式避免了FEC要求的复杂设备和ARQ方式的信息 连贯性差的缺点，并且可以达到较低的误码率，所以在实际 中得到广泛应用
差错控制方式
重传反馈方式 (ARQ)
前向纠错方式 (FEC)
混合纠错方式 (HEC)
❖ 一、重传反馈方式（ARQ）
信源
检错码 编码器
存储器
前向信道 噪声源
检错码 解码器
信宿
判决检测器 控制器
反馈信道
反馈 控制器
工作方式描述
发送端 发送检测码
前向 接收端
信道
接收码字
发送 后续 数据
Y N
重新发送
出错
(2,1,2)卷积码编码器
定义6.3两个n重(x，y)之间对应码元取值不同的个数， 称为这两个重之间的汉明距离，记做d(x,y)
定义6.4 n重x非零码元的个数称为汉明重量，简称重 量,用w(x)表示
X:(10101) y:(00111)
w(x)=3 w(y)=3 d(x,y)=2
定义6.5 （n,k）分组码中，任意两个码字x、y之间的 汉明距离的最小值，称为该分组码的最小汉明距离， 简称为最小距离，用d0表示
p( y)
p( y)
﹝ ❖ 考虑y的取值 两者之间比较
P(0 | y 0)
(1 pe ) p
p(1 pe ) (1 p) pe
P(1| y 0)
(1 p) pe
p(1 pe ) (1 p) pe
﹝ 两者之间比较
P(0 | y 1)
pe p
(1 p)(1 pe ) ppe
编码规则
发送端所采用的编码算法及其 对应的码集合是已知的
接收到的码 字序列
信道模型及 先验概率为信道转移矩阵和发
参数
送符号的统计规律
确定译码规 则，对接收
最合理规则是译码错误概率最小
到的码字译
码
接受到
的码字
本质：
信号估值问题
许用码字 禁用码字
认为是正确的， 所以不可能没 有译码错误
出错了， 需要纠错
2需要反馈信道， 占用额外频率资源
二、前向纠错方式（FEC）
检测 结果
发送端
信道
接收端
发送
纠错码
接收码字
根据编译 码规则
Y 错误
N
译码 规则 纠错
纠错能力足够好，能够纠 正信道引入的数据错误
输出信息
优点 不足
1.不需要反馈信道，能够实现一对多的同 步广播通信 2.译码实时性好，控制电路比ARQ也简 单 由于假设纠错码的纠错能力足够纠正信息序 列传输中的错误，也就是纠错码与信道的干 扰是相匹配的，所以对信道的适应性较差