香农三大定理
信息论与编码基础
香农三大定理 简介
总结：
信源编码器模型
性能指标 平均码长、信息传输率、编码效率
香农第一定理（无失真信源编码定理）
0
0
Yt 1
1
Y
3
4
4
5 a(t)={1010010110000011001110151}
6 b = {0012424251243666750136666}
P(R)
P(R)
信息论与编码基础
香农三大定理 简介
2、常用判决准则
a、MAP准则（Maximum a Posteriori）
P(R | C*) P(C) P(R | C) P(C*)
似然比
b、ML准则（Maximum Likelihood）
若输入符号等概时 P(C) 1 r
P(R | C*) P(R | C)
二进代码
10
1110
000
香农三大定理 简介
单词间隔 ——————
000000
{A,B,…,Z}
信源编码器I
二进符号
信源编码器II
码符号集{点/划/字母间隔/单词间隔}
码符号集{0，1}
信息论与编码基础
1、信源编码器 b、举例
3）中文电报信源编码器
“中”
“0022”
香农三大定理 简介
“01101 01101 11001 11001”
信息论与编码基础
一、香农第一定理 二、香农第二定理
三、香农第三定理
香农三大定理 简介
信息论与编码基础
一、香农第一定理 二、香农第二定理 三、香农第三定理
香农三大定理 简介
信息论与编码基础
1、信源编码器 a、模型
香农三大定理 简介
S : s {a1,..., aq} 编码器
C : c {W1,...,Wq} 码字
bit/code
信息论与编码基础
1、信源编码器
d、指标
3) 编码效率
实际编码的信息传输率
最大编码的信息传输率
H(S) LN log r N
香农三大定理 简介
信息论与编码基础
香农三大定理 简介
例：二元DMS进行无失真编码
S P( s)
s1
3
4
s2
1
s1
3
4
s2
1
4
H(S) = H(3/4,1/4) = 0.811(bit/sign) {0,10,110,111}
N=2 L2 1.688 (code/2-sign)
R2
H (S) L2 / 2
0.961
(bit/code)
2
L2
H (S ) / 2 log 2
N=3
R3
H (S ) L3 / 3
0.985
(bit/code)
N=4 R4 0.991(bit/code)
3
L3
H (S ) / 3 log
2
0.985
4 0.991
信息论与编码基础
香农三大定理 简介
2、香农第一定理（可变长无失真信源编码定理）
定理4.1 设S N {1,2,...,qN }为q元离散无记忆信源S的N次扩展
Wi {xi1 , xi2 ..., xili }
码长
X : x {x1,..., xr} 码符号
单符号信源无失真编码器
信息论与编码基础
1、信源编码器 a、模型
香农三大定理 简介
S N (S1,..., SN )
Si {a1,..., aq} i 1, 2,..., N
编码器
Wi {xi1 , xi2 ..., xili } i 1, 2,..., qN
X : x {x1,..., xr}
N次扩展信源无失真编码器
信息论与编码基础
1、信源编码器 b、举例
1）ASCII信源编码器
香农三大定理 简介
{英文字母/符号/命令}
二进代码
ASCII编码器
码符号集{0，1}
信息论与编码基础
1、信源编码器
b符、b号、举举例例点 划
字母间隔
2电）2平）摩摩尔+尔斯—斯信电源+ +码编+ —码器 — — —
信息论与编码基础
香农三大定理 简介
1、失真度与信息率失真函数
b、失真测度
1）单符号失真测度 d (u, v) 设u U,v V
定义失真矩阵 d (u1, v1) ... d (u1, vs ) d d (u2, v1) ... d (u2, vs ) . ... . d (ur , v1) ... d (ur , vs ) d (ui , v j ) 0
说明：
1）通过对扩展信源进行可变长编码，可以使平均码长无限趋近 于极限熵值，但这是以编码复杂性为代价的。
2）无失真信源编码的实质：对离散信源进行适当的变换，使变换 后新的符号序列信源尽可能为等概率分布，从而使新信源的每个码 符号平均所含的信息量达到最大。
3）香农第一定理仅是一个存在性定理，没有给出更有效的信源 编码的实现方法。
信息论与编码基础
香农三大定理 简介
1、失真度与信息率失真函数
b、失真测度
如果规定
d
(ui
,
v
j
)
0, ui 1, ui
vj vj
，那么失真矩阵为
0 1 ... 1 d 1 0 ... 1
. . . . 1 1 ... 0
N=3时，失真度如图
U
V
信息论与编码基础
信息论与编码基础
香农三大定理 简介
例1 重复编码 (n,1)
PE p3 C31 pp2 3104 p 0.01
R = logM/n bit/code
n=5 PE ≈10-5 n=7 PE ≈4×10-7
R = logM/5 R = logM/7
n=9 PE ≈10-8
R = logM/9
信息论与编码基础
香农三大定理 简介
例1 重复编码 (n,1)
1 000 2 111
BSC的三次 扩展信道
000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 8
PE p3 C31 pp2 3104 p 0.01
香农三大定理 简介
不大于一定编码速率的条件下，使平均失真限 制到最小；
在平均失真不大于某个值的条件下，使编码 速率限制到最小
信息率失真理论
信息论与编码基础
香农三大定理 简介
1、失真度与信息率失真函数
a、系统模型
U
V
信源
信源编码器 无噪信道 信源编码器
信宿
试验信道
U符号集A {u1,..., ur} V符号集B {v1,..., vs}
香农三大定理 简介
1) 平均码长
q
L P(si )li
i 1
LN
qN
r P(si
)i
i1
code/sign code/N-sign
信息论与编码基础
1、信源编码器
d、指标
2) 编码后的信息传输率
R H(S) / L
香农三大定理 简介
bit/code
RN
H (S ) LN / N
7
7
信息论与编码基础
一、香农第一定理
香农三大定理 简介
二、香农第二定理 有效性 可靠性 矛X盾
三、香农第三定理
信息论与编码基础
香农三大定理 简介
1、错误概率
p = 0.01
误码率
a1=0 p(a1) = ω
1-p p
b1=0
误字率
错误概率与那些因素相关？
a2=1 p(a2) = 1-ω
p
b2=1
概率任意小。
信息论与编码基础
香农三大定理 简介
3、香农第二定理（有噪信道编码定理） 说明：
1、定理纠正了人们传统固有的可靠性和有效性矛盾的观点，
为信A道W编G码N理论和技术的研究指明了方向。 1)Tu证rb明o基码本：条1/2件码：率1，）B随PS机K编，码65536随机交织，
2、定18理次仅迭指代出，编码Pe的=1存0在-5,性2E），b/N未码0给长=出→0.编7∞d码B的具体方法。 2)非规则LDPC码：3N）=最10大7, 似1/2然码译率码，
00000 01101 10111 11010
信道
00000 00010 01000 10001
01101 01111 00101 11100
10111 10101 11111 00110
11010 11000 10010 01011
香农三大定理 简介
00001 00100 10000 00011
01100 01001 11101 01110
找到M个码字（代表M个等可能的消息，且 M 2n(C ) , 为任
意小的正数）组成一个码，并存在相应的译码规则，使信道
输出的错误概率任意小。
信息论与编码基础
香农三大定理 简介
3、香农第二定理（有噪信道编码定理）
表述二：
若在信息传输率R不大于信道容量C（即R≤C），则 存在一种编码，当码长n足够大时，它可以使信道输 出端的错误概率任意小，而信息传输率无限接近C； 如果R>C，则不可能找到一种编码，使输出端错误
