无失真信源编码定理-香农第一定理 信道编码定理-香农第二定理 限失真信源编码定理-香农第三定理
差错控制编码（信道编码）在通信系统中的地位：
调制信道
x信源
编码
调制
信道
解调
解码
信宿
编码信道
差错控制系统分类
FEC ARQ HEC
发
收
可纠正错误的码
发 能够发现错误的码 收 应答信号
发 能够发现和纠正错误的码 收 应答信号
• 级联码
– 两个以上的编码器按一定方式组合而成的编码器
信道编码的分类
信道编码
分组码
卷积码
线性分组码
非线性分组码
线性卷积码
非线性卷积码
汉明码 循环码
编码与译码
• 对 二进制(n, k)码，信息数量（或合法码字数） 为2k，可用编码空间的点数为2n个。
• 任一种2k信息集合到二进制序列集合(2n)的映射 都种是。一 如种 ，(共n有, k1)0码29。种因(1此0总0,共50可)码能。的编码方案有22kn
– 满足交换律的群
环——定义了两种运算的集 合
• 按第一种运算（不妨称为加法）构成交换群 • 第二种运算（不妨称为乘法）满足以下条件
– 封闭性 – 结合律 – 与加法间满足分配律
域——一种特殊的环
• 乘法有恒等元（称为1元），且除了加法的恒 等元（称为0元）以外有逆的环
• 除0元外，对乘法构成交换群 • 无限域和有限域
便于译码 • 目前对线性系统的研究远比非线性系统充分
线性码的定义
• 码字集中的元之间的任意线性组合仍是合法码 字，即对线性组合运算封闭的码字集，称为线 性码
• 因此，为了构成线性空间，必须首先定义运算
群——定义了一种运算的集 合
•群
– 运算封闭 – 有恒等元 – 有逆元 – 满足结合律
• 交换群
– 直观的译码准则：最小距离译码
• Shannon第二定理
– 当信息速率R小于信道容量C时，总存在一种编码 方式使差错率低于任一给定值e
• 接近信道容量
信道编码的作用
• 信道编码的作用：在资源、可靠性和传信量之 间选择一个好的工作点（有时还要考虑延时）。
• 资源指的提供信息传输所付出的代价
– 包括频率、时间、空间、功率等等。但不包括实 现复杂度
重复码
• 00…00 • 11…11
许用码字
• 若将每个比特重复n次，则构成一个码长为n， 信息位长度为1的(n,1)重复码,且编码效率(码 率)R=1/n
n=2时 0
许用码组：00，11 禁用码组：01，10 能够发现一个错误，但不能纠正错误 1
n=3时 许用码组：000，111 禁用码组：001, 010, 100, 011, 101, 110 能够纠正一个错误，发现两个错误
• 译码运算量：如果直接用最大似然序列译码，对 一般性的编码而言，正比于n* 2k ，对(100,50) 码，则为1017。几乎是不可能译码的。
为什么要引入线性码
• 发现或构造好码是信道编码研究的主要问题 • 编码方案太多，以至全局搜索是不可能的 • 现实的做法是对编码方案加以一定的约束，在一个
子集中寻找局部最优 • 这种约束即要能包含尽可能好的码，又要便于分析，
– 一个好的编码就是要充分利用资源，传递尽可能 多的信息
Hale Waihona Puke 三种情形：– 给定资源和可靠性要求，通过信道编码尽量提高 传输速率
– 给定对信息传输的速率和可靠性要求，通过信道 编码尽量减少资源开销
– 给定资源和传输速率，通过编码提高可靠性
编码的实质 ——利用冗余降低差错概率
• 将所有可能的输入信息（消息）映射到信道符 号（波形）空间的点，而这个点的集合要小于 （包含于）全信道空间中。
发现三个错误
纠错码如何纠正错误？
在信息序列之后按照一定的规则添加一 定长度的保护比特(校验比特或监督比特)
信道编码
二、基本概念(p193) 1、汉明码重(hamming weight) 码字中码元“1”的个数。 例如： 100110 的码重是 3
w( 1100110)= ？
信道编码
2、汉明码距(hamming distance) 两个码字相对应位不同的个数。 例如：d(1011,0110)=3 d(0011,1011)=? 思考：码距和码重的关系？
– 有理数、实数和复数都是无限域
– 信道编码中用到的是有限域，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)
Coding and Information Theroy
信息论与编码技术
展爱云 Zayscj@
通信工程教研室
本课程的相关要求
• 课程基础（概率论） • 上课要求 • 学习要求 • 实验要求（C\C++)
本课程的重点
• 信息的基本概念 • 信息量的计算 • 典型的几种信源编码方法 • 典型的几种信道编码方法
几种常用的离散信道编码
• 分组码
– 将一个有限(k)维输入矢量映射到一个（n维）矢量的编码， 记为(n, k)分组码
• 卷积码
– 输入为一个无限长序列，每个节拍有k个符号送入编码器， 同时有n个符号向输出至信道，但每节拍的输出不仅与本 节拍的输入有关，还与之前L-1个节拍的输入有关，记为 (n, k, L)卷积码
信道编码
一、引言 思考：信道编码的目的是什么？
通信系统模型
• 信道编码：从消息到信道波形或矢量的映射
消息集中 一个元素
信道波形 空间中的
一个点
失真后 的波形
恢复的 消息
信源 编码
信道 编码
信道
信道 译码
信源 译码
消息到波 形的映射
引入失真
判断是消 息集中的 哪个元素
从两个方面引入信道编码
• 检错和纠错：对付信道引入的差错
0.9
0
0.1
0.1
0.9
1
BSC信道
n=4时 许用码组：0000，1111
禁用码组：0001, 0010, 0100, 1000, 0011, 0101, 0110, 1100, 1001, 1010, 0111, 1101, 1110, 1011
能够纠正一个错误同时发现两个错误
译码正确 译码失败 译码错误