最大似然译码( MLD)
cˆ i = max P(r / ci )
信息论基础
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
信源
信源 编码
加密
信道 编码
信宿
信源 译码
解密
信道 译码
干扰 信道
噪声
通信系统三项性能指标： 传输的有效性(Efficiency) 传输的可靠性(Reliability) 传输的安全性
信息论基础
第2章 信源与信息熵
离散单符号信源熵、条件熵、联合熵 平均互信息量 马尔可夫信源极限熵 熵及平均互信息量的性质 连续信源相对熵及最大熵定理 冗余度的概念 数据处理中信息不增加性原理
信源消息符 号ai a1 a2 a3 a4 a5 a6 a7
符号概 率(ai) 0.20 0.19 0.18 0.17 0.15 0.10 0.01
累加概 率Pi 0 0.2
0.39 0.57 0.74 0.89 0.99
-log p(ai)
2.32 2.39 2.47 2.56 2.74 3.32 6.64
信息论基础
准对称的DMC信道容量
将转移概率矩阵划分成若干个互不相交的对称的子集
r
∑ C
=
log
n
−
H(
p1 ' ,
p2
'
,
ps ' )
−
N k log Mk
k =1
n为输入符号集个数；p1’，p2’，…ps’是转移概率矩阵P 中一行的元素，即H(p1’，p2’，…ps’)＝H(Y/ai)；Nk是第 k个子矩阵中行元素之和，Mk是第k个子矩阵中列元素之 和，r是互不相交的子集个数
信息论基础
•互信息量与熵的关系
All Together Now
H(X,Y)
H(X|Y) I(X;Y) H(Y|X)
H(X)
信息论基础
H(Y)
2.4连续信源的熵与互信息
最大熵定理
限峰功率最大熵定理：对于定义域有限的随机 变量X，当它是均匀分布时，具有最大熵
限平均功率最大熵定理：对于相关矩阵一定随机 变量X，当它是正态分布时具有最大熵
失真 D ≤ D的条件下，选择一种编码方法使信息率R尽可能小。信息
率R就是所需输出的有关信源X的信息量。将此问题对应到信道，即 为接收端Y需要获得的有关X的信息量，也就是互信息I(X;Y)。这样， 选择信源编码方法的问题就变成了选择假想信道的问题，符号转移 概率p(yj/xi)就对应信道转移概率。
信息论基础
信息论基础 C 总复习
任课老师：干宗良 博士（讲师） 江苏省图像处理与图像通信重点实验室
考试时间和内容
考试时间： 2011年1月8日 出题方式： 考教分离 所以大家不要问我类似于考什么的话题
以前考试形式 填空 20 判断 10 计算题 70
主要是信息论的基本概念，基本方法
信息论基础
第一章 通信系统模型方框图:
掌握线性分组码的码距，纠错能力、MDC码； 掌握循环码的基本概念、生成多项式、校验多
项式，及其对应的生成矩阵和校验矩阵
信息论基础
差错类型
差错符号：由符号发生差错引起，也叫信号差 错，信号差错概率用误码元率表示
差错比特：由信息比特发生差错引起，也叫信 息差错，信息差错概率用误比特率表示
对于二进制传输系统，符号差错等效于比特差 错；
逆定理：信道容量C是可靠通信系统传信率R 的上边界，如果R >C，就不可能有任何一种 编码能使差错概率任意小。
信息论基础
6.2.2最优译码与最大似然译码
消息组mi
码字ci
接收码r
估值 cˆ i
消息 mˆ i
编码器 信道
译码
消息还原
最佳译码，也叫最大后验概率译码(MAP)
cˆi = max P(ci / r)
信息论基础
应用方法三
0.5 0.3 0.2 P = 0.3 0.5 0.2
0.5 0.3 0.2 0.3 0.5, 0.2
C = log2 2 − H (0.5,0.3,0.2) − 0.8log2 0.8 − 0.2log2 0.4 = 0.036bit / 符号
信息论基础
信道容量
信息论基础
反馈重发（ARQ）：收端通过检测接收码是否 符合编码规律来判断，如判定码组有错，则通 过反向信道通知发端重发该码
混合纠错（HEC）：前向纠错和反馈重发的结 合，发端发送的码兼有检错和纠错两种能力
信息论基础
信道编码定理
正定理：只要传信率R小于信道容量C，总存 在一种信道码（及解码器），可以以所要求的 任意小的差错概率实现可靠的通信。
信息论基础
3.2离散单个符号信道及其容量
信息传输率
信道在单位时间内平均传输的信息量定义为信息 传输速率
R=I(X;Y)=H(X)－H(X/Y) 比特/符号
Rt=I(X;Y)/t
比特/秒
信道容量 比特/符号（bits/symbol或
bits/channel use）
C = max I ( X ;Y )
信息论基础
2.5冗余度
冗余度，表示给定信源在实际发出消息时所包含的 多余信息。 它来自两个方面: 一是信源符号间的相关性； 二是信源符号分布的不均匀性
信息论基础
定义信息效率 :
η = H∞(X)
Hm (X ) 定义冗余度 :
γ = 1−η = 1− H∞(X)
Hm (X )
信息论基础
马尔可夫极限熵
信息论基础
3.2离散单个符号信道及其容量
♦ X、Y一一对应
C＝maxI(X;Y)＝log n
♦ 多个输入变成一个输出
C＝maxI(X;Y)＝maxH(Y)
♦ 一个输入对应多个输出
C＝maxI(X;Y)＝maxH(X)
信息论基础
3.2离散单个符号信道及其容量
对称信道容量
C＝max I( X;Y ) = max[H ( X ) − H ( X | Y )]
0 1 0
1
第三次 分组
0 1
0 1
第四次 分组
0 1
二元 码字
00 010 011
10 110 1110 1111
码长Ki
2 3 3 2 3 4 4
信息论基础
信息论基础
第6章 信道编码
掌握纠错编码的分类、差错控制系统分类、信 道编码定理；
了解纠错编码的基本思路、最优译码与最大似 然译码；
掌握线性分组码的生成矩阵和校验矩阵、伴随 式的基本概念；
R(D) = min I( X ;Y ) PD
信息论基础
4.1.4 信息率失真函数的性质
1. R(D)函数的定义域 ⑴ Dmin和R(Dmin) Dmin＝0
R(D= min ) R= (0) H ( X )
对于连续信源
R(Dmin ) = R(0) = Hc ( x) = ∞
信息论基础
(2) Dmax和R(Dmax)
p(ai )
p(ai )
= max[H (Y ) − H (Y | X )] 将平均互信息量
p(ai )
的最大值问题转
= max H (Y ) − H (Y / X ) p(ai )
换成输出熵的最
大值问题。
m
∑ C = log m − H (Y | ai ) = log m + pij log pij j =1
由于k个基底即G的k个行矢量线性无关，矩阵G的秩一 定等于k。
当信息元确定后，码字仅由G矩阵决定，因此我们称 这k×n 矩阵G为该(n,k)线性分组码的生成矩阵。
信息论基础
二、纠错码分类
从功能角度：检错码 、纠错码 码元与原始信息位的关系：线性码、非线性码 对信息序列的处理方法：分组码、卷积码 差错类型：纠随机差错码、纠突发差错码、介
于中间的纠随机/突发差错码。 构码理论：代数码、几何码、算术码、组合码
等
信息论基础
三、差错控制系统分类
前向纠错（FEC）：发端信息经纠错编码后传 送，收端通过纠错译码自动纠正传递过程中的 差错
对于多进制系统，一个符号差错到底对应多少 比特差错却难以确定。因为一个符号由多个比 特组成。
信息论基础
差错图样类型
随机差错：若差错图样上各码位的取值既与前 后位置无关又与时间无关，即差错始终以相等 的概率独立发生于各码字、各码元、各比特；
突发差错：前后相关、成堆出现。突发差错总 是以差错码元开头、以差错码元结尾，头尾之 间并不是每个码元都错，而是码元差错概率超 过了某个额定值。
选择所有满足R(D)＝0中D的最小值，定义为R(D)定义域
的上限Dmax，即
Dmax
=
min
R( D )=0
D
因此可以得到R(D)的定义域为
D ∈ 0, Dmax
n
∑ Dmax
=
min
j =1,2,,m
i =1
pi dij
信息论基础
信息论基础
第5章
无失真信源编码定理（定长编码定理、变长编 码定理）；
信息论基础
6.3.1 生成矩阵和校验矩阵
c＝ m G
1×n 1×k k×n 码字 消息 生成矩阵 G＝[gk-1…g1g0]T，有k个(1×n)行矢量，如 何选择呢？
信息论基础