信道编码杨杰本章节达到的目的
理解信道编码在通信系统中的作用
了解信道编码的的基本分类
了解信道编码性能评价的基本方法
了解汉明码的编译码原理
了解信道容量 /容量代价函数在信道编码定理中的作用
理解香农第二定理又称有噪信道编码定理的物理意义
了解信道编码理论与实际应用的差距本章研究内容
信道编码概述
错误概率与译码准则、编码方法
信道编码定理与联合典型序列
信道编码的性能界限
信道编码举例－汉明码
关于信道编码理论的若干评注
§ 6.1:信道编码概述
问题引出
什么是信道编码
信道编码的作用
信道编码的三种情形
信道编码的实质
§ 6.1:信道编码概述－ 问题引出
互信息能告诉我们什么？
– 随机变量 X,Y统计意义上的依存程度
– 可以获得的信息量
– 不能：所得信息能否可靠地确定信道输入？
无噪信道编码能告诉我们什么？
– 无噪无损信道，只要对信源输出进行适当编码，总能以最大信息传输率，
无差错的传输信息。
– 但是：一般信道总存在噪声或干扰，信息传输会造成损失
实际通信中人们对传输要求什么？
– 传输信息量大
– 传输可靠
提出的与信道传输有关的问题：
– 如何能使信息传输后发生的错误最少？
错误概率与那些因素有关？
有无办法控制？
能控制到什么程度？
– 无误传输可达的最大信息率是多少？
§ 6.1:信道编码概述－ 什么是信道编码
通信系统模型
信道编码,从消息到信道波形或矢量的映射希望通信系统与信道统计特性相匹配的编码信源编码信道编码信道信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素
§ 6.1:信道编码概述－ 什么是信道编码
复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于 广义的信道编码 范畴
注意,信道译码可以不是离散信道译码。只有当解调为硬判决输出时才是离散信道和离散信道译码信源编码离散信道编码信道调制信道译码解调信源译码广义信道或离散信道
§ 6.1:信道编码概述－ 信道编码的作用
信道编码的作用,在资源、可靠性和传信量 之间选择一个好的工作点（有时还要考虑延时）。
资源 指的提供信息传输所付出的代价
– 包括频率、时间、空间、功率等等。但不包括实现复杂度
– 一个好的编码就是要充分利用资源，传递尽可能多的信息
§ 6.1:信道编码概述－ 三种情形,
– 给定资源和可靠性要求，通过信道编码尽量提高传输速率（例：多电平编码）
– 给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销（例：扰乱编码）
– 给定资源和传输速率，通过编码提高可靠性
（例：检、纠错编码）
§ 6.1:信道编码概述－ 编码的实质
利用冗余降低差错概率
将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。
§ 6.1:信道编码概述－ 信道编码的基本分类
按码的结构分,
– 线性码
线性分组码（群码）
卷积码（线性树码）
– 非线性码
按抗干扰模式分
– 抗随机差错码
– 抗突发差错码
按编译码理论所用数学工具分
– 代数码
– 几何码
– 组合码
按对错误的处理方式分
– 检错码
– 纠错码
§ 6.2:错误概率与译码准则、编码方法－ 1
错误概率与译码规则
– 错误概率 Pe与什么有关
信道的统计特性
译码规则
– 译码规则的选择依据
最大后验概率准则－－理想
最大似然准则－－实用编码
C
A
B
2
1
4
3
5
发送波形集合接收波形集合
P
A2
P
A1
P
A3
P
A4
P
A5
C
A
B
2
1
3
消息集合编码集合译码
§ 6.2:错误概率与译码准则、编码方法－ 2
信道 译码
An
1
2
4
3
w4
w3
w1
w2
x
x
x
An 是接收空 间
w1,w2,… 是 发 送的 码 子
围绕每 个 码 子有一个 译码 域?i
如果接收的 码 子在?i中,就 认为发 送的是 码 子 wi
发 生 错误
一般,An中 存在一些不属于任何
i的区域
有 时 接收 码 子会被映射到 错误 的
i，进 而被 译 成 错误 的 wi
正确 译码不知如何 译码译码错误
§ 6.2:错误概率与译码准则、编码方法－ 3
问题：
– 在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分
划分接收矢量空间的准则－－译码器的译码准则
§ 6.2:错误概率与译码准则、编码方法－ 4
§ 6.2:错误概率与译码准则、编码方法－ 5
准则一：平均错误概率最小译码准则
计算平均错误概率：
m
m
Yymygg
MmYMY
当表示成译码函数个不相交的子集
,)((,)
1,...2,1,0,}{
C
A
B
2
1
4
3
5
发送波形集合接收波形集合
P
A2
P
A1
P
A3
P
A4
P
A5
YX
)()|()()|(),(
)|(
ypyxpxpxypxyp
yxxyp
mmmm
mm
则按全概率公式有：
的概率，条件下接收矢量取是发送码字设若码字 Xm经传输后在接收端所得的接收矢量不落在 Ym子集中，则译码发生错误
1
0
)(
)()|(
)|()()(
)|(
M
m
mm
yp
xpxyp
m
xypxpyp
yxp mm
其中：
§ 6.2:错误概率与译码准则、编码方法－ 6
§ 6.2:错误概率与译码准则、编码方法－ 7
理想的译码器应使平均译码差错概率最小
)|( yxp m 是译码正确的概率，则译码发生错误的概率为：
)|(1| yxpp mye
译码器 平均 的译码差错概率为：
)|()(1
))|(1()()( |
yxpyp
yxpyppypP
y
m
m
yy
yee
m a x)|( yxp m
§ 6.2:错误概率与译码准则、编码方法－ 8
最小错误概率准则（最大后验概率准则）：
特点：
– 优点：理想
– 缺点,1、后验概率不易得到
2、后验概率依赖于输入分布
)|(m a x)|)(( yxpyygp mm?
§ 6.2:错误概率与译码准则、编码方法－ 9
准则二：最大似然译码准则
此时译码差错概率为：
平均的译码差错概率为：
)|(m a x))(|( mm xypygyp?
mYy
mme xypp )|(|
m
meme
m
me pmppxpP || )()(
§ 6.2:错误概率与译码准则、编码方法－ 10
最大后验概率译码准则 &最大似然译码准则
– 输入等概时－－二者是一致的此时：
)|()|( )(1 myMpm xypyxp?
)|(m a x)|(m a x )(1 myMpmmm xypyxp?
)|(m a x)(1 mmyMp xyp?
§ 6.2:错误概率与译码准则、编码方法－ 11
错误概率与编码
– 如何在信息传输率一定的前提下使 Pe?0
– 实际经验：重复发送可以使 Pe减小
重复次数 N很大时，可以使 Pe?0
但：信息传输率降低
– 信道编码定理,R一定时，可以找到一种编码方法使 Pe相当低
– 引入概念：码字距离
§ 6.2:错误概率与译码准则、编码方法－ 12
码字距离－汉明距离
– 长度为 n的两个符号序列 (码字 )αi和 βj之间的 距离 是指 αi
和 βj之间对应位置上不同码元的个数，用符号 D(αi,βj)
表示。这种码字距离通常称为 汉明距离例如,两个二元序列
αi=101111
βj=111100
则得 D(αi,βj)=3
又例如,两个四元序列
αi=1320120
βj=1220310
则得 D(αi,βj)
§ 6.2:错误概率与译码准则、编码方法－ 13
对于二元信道，即对于二元码，汉明距离可表达成下述若令 αi＝（ａ i1ａ i２ … ａ in） ａ ik∈ ｛ 0,1
βj＝（ bj1 bj2 … b jn） βjk∈ ｛ 0,1
则 αi和 βj的汉明距离为
D(αi,βj)＝
在某一码书 C中，任意两个码字的汉明距离的最小值称为该码 C的最小距离，即
dmin＝ min｛ D(Ci,Cj)｝ Ci≠Cj Ci,Cj∈ C
在任一码书中，码的最小距离 dmin与该码的译码错误概率有关。
jk
n
k
ik ba
1
§ 6.2:错误概率与译码准则、编码方法－ 14
与码字距离有关的结论
– 最小距离译码准则
– 在二进制对称信道中：
最小距离译码准则＝最大似然译码准则
),(m in))(,( mm xydygyd?
§ 6.3:信道编码定理与联合典型序列 -1
信道编码定理引出
– 问题,在有噪信道中，使平均误码率 Pe尽可能小的情况下，可达到的信息传输率是多少？
– 答案,信道容量 C
信道编码定理
信道编码定理的证明
– 证明思路
– 随机编码方法
– 联合典型序列
§ 6.3:信道编码定理与联合典型序列 -2
信道编码定理：
– 设 R是信息传输的速率,C是离散无记忆信道的信道容量,ε >0是任意小的数，则只要 R<C就总存在码字长为 N，码字数为 M=2NR的分组码使译码的平均差错概率 Pe<ε 。
§ 6.3:信道编码定理与联合典型序列 -3
信道编码定理的证明
思路：
– 通常思路,先构造一个理想的好码，并定义一种译码准则，计算该好码经过译码后的误码率
– 问题,构建极其复杂且无具体方法
N值很大时，误码率计算困难
– 香农采取的方法,
用 随机编码方法 得到所有可能码的集合
在其中随机选择一个码作为信道码
利用大数定理计算在集合平均意义上的该码性能
利用 联合典型序列 译码
– 香农采取的方法评价：
不很严格，不是最优，但便于理论分析
随机编码方法在后来严格的证明中一直被采用
§ 6.3:信道编码定理与联合典型序列 -4
随机编码方法：
– 对每一个消息 m,(m=0,1,…M -1),
编码为 xm=(xm1xm2…x mn)
其中,xmi (i=1,2,…n) 是按照输入字母的概率随机选取，从而得到全部 M=2NR个码字，组成码集 C＝（ x1x2….x M-1)
随机编码方法产生某一特定码字的概率 P(Xm)是：
1
0 1
)()(
M
m
N
i
imm XpXP
§ 6.3:信道编码定理与联合典型序列 -5
联合 ε 典型序列
– ε 典型序列,信源输出的随机序列－奠定了信源编码的基础
– 联合 ε 典型序列,两个随机变量的自然扩展，是信道编码的基础
– 联合 ε 典型序列定义：
– 联合 AEP定理
– 定理解释：
§ 6.3:信道编码定理与联合典型序列 -6
联合 ε 典型序列定义,
– 设（ X,Y）是长为 N的随机序列对，
则在这些随机序列对中满足下列条件的序列对被称为联合典型序列式中 δ 是任意小的数，联合典型序列的全体构成联合典型序列集，记做 G
),(),(
1
n
N
n
n yxpp?
yx
|)()(lo g| 1 XHxpN
|)()(lo g| 1 YHypN
|)()(lo g| 1 XYHxypN
§ 6.3:信道编码定理与联合典型序列 -7
联合 AEP定理,
– 设随机序列对（ X,Y)的,则对任意小的数 δ >0，我们总能找到足够大的 N使全体序列对的集合能被分成满足下述条件的集合 G及其补集 Gc：
（ 1）
（ 2）
（ 3）设（ X’,Y’）是相互独立的随机序列对，但它与
（ X,Y）有相同的边缘分布，即：
则：
),(),(
1 n
N
n n
yxpp?
yx
1}),{(
}),{(
GYXP
GYXP c
))((
))((
2)1(||
2||
XYHN
XYHN
G
G
)()()},(),{( ypxpyxYXP
]3);([
]3);([
2)1(}),{(
2}),{(
YXIN
YXIN
GYXP
GYXP
§ 6.3:信道编码定理与联合典型序列 -8
联合 AEP定理的解释：
– 两个随机变量情况下，序列 Xn,Yn及其联合序列 XnYn都具有 AEP
特性
– 联合典型序列对是高概率序列对
– 联合典型序列对出现概率接近相等，且其和接近于 1
– 联合典型序列对是一些密切关联的序列对
– 一般与 X对应的 Y可能是 Y空间的任一个，该定理说明：随 N的增大，对应 X的 Y只能是（ X,Y)典型序列对的 Y，取其他 Y的概率?0
– 联合典型序列数目为 2NH(XY)，
典型 x,典型 Y随机组合的空间为 2N[H(X)+H(Y)]，
联合典型序列占其中约 1/ 2NI(X;Y)，只是很小的一部分故：当 X的数目 < 2NI(X;Y)时，，可使 Pe?0
– 给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。
Input
sequence
Output
sequence…
……
…
……
y
wi
wi+1
2nH(XY)
sequences
that can
map to y
M = 2nR
code words
t h e n 0enPRCneP 2
§ 6.3:信道编码定理与联合典型序列 -9
信道编码定理证明的几点说明
– 香农只是证明了码的存在性，未给出构造方法
– 随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；而且即使找到，码字也是毫无结构的，只能采用查表译码方法，当
N很大时，码表的存储量也很难接受
§ 6.4:信道编码的性能界限－ 1
理论性能极限－－存在性
– 香农信道编码定理
– 作用：理论极限、渐进性能
工程实现上的界限－－构造性
– 最小距离界限
– 作用：构造新码、估计新码性能时，说明新码与最好性能的码接近的程度
香农理论极限,R<C； 存在编译码方法使 Pe?0
给定 Pe；存在编译码方法使 R?C
RCneP 2
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
误码率
p
b
信噪比E
b
/N
0
(dB)
s
h
a
n
n
o
限仅内码
（
4
，
1
，
1
5
）
未编码仅内码
（
2
，
1
，
7
）
码级连级连
－ 1.59dB
0 1,5 9
bEN dB
§ 6.4:信道编码的性能界限－ 2
实际信道编码理论研究内容：
– 最佳码性能有多好？
– 如何设计好码？
– 如何译码？
最小距离限
– 在码长和最小距离给定时，具有最大可能的码字数
A(n,dmin)的码为好码。
– 完备码 A(n,dmin)的上下限
近半个世纪以来，上限不断改进，并逐步向下限靠近，但下限保持不变
未证明的看法：上下限会逐步会合成为一条限。
§ 6.5:信道编码举例－汉明码－ 1
汉明码的编码
汉明码的译码
§ 6.5:信道编码举例－汉明码－ 2
汉明码
– 第一个具有系统的编译码方法的信道码
（ 7,4）汉明码
– 码长 n=7,信息元 k=4，检验元 r=n-k=3。长为 3的二元序列共有 23＝８个。我们将其中 7个非全零序列按列排成如下矩阵
– H矩阵称为：一致监督矩阵。
1010101
1100110
1111000
)4,7(H
§ 6.5:信道编码举例－汉明码－ 3
设码字 C=（ c6c5c4c3c2c1c0),有：
H× CT=0T
其中,0＝（ 0 0 0）,0T是 0矢量的转置，即满足：
c3+c2+c1+c0=0
c5+c4+c1+c0=0
c6+c4+c2+c0=0
0000000 0100101 1000011 1100110
0001111 0101010 1001100 1101001
0010110 0110011 1010101 1110000
0011001 0111100 1011010 1111111
§ 6.5:信道编码举例－汉明码－ 4
给出生成矩阵
满足：
1111000
0110100
1010010
1100001
)4,7(G
cGm ][
0HG T
§ 6.5:信道编码举例－汉明码－ 5
（ 7,4）汉明码特点：
– 16个码字是所有码长为 7的二元序列中的一个封闭子集。
– 码的最小距离等于非零码字的最小重量＝ 3
能检 2个错，纠一个错。
d>=s+1 （检错时）
d>=2s+1 （纠错时）
§ 6.5:信道编码举例－汉明码－ 6
汉明码译码：
– 伴随式译码
– 错误图样 E?R=C+E
– 伴随式 S
TTTTT 0EHEHCHRH
TT SEH
0
1
2
s
s
s
TS
110
101
011
111
001
010
100
000
S
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000000
Z
伴随式 错误图样
假设接收到码矢 y=(0010010)
有 7个可能的错误位置,如 Z矩阵所示
伴随式是,ST= H RT
)10 0(
100
010
001
111
011
101
110
)00 100 10(?
S
Y 不是一个正确的码子，因为 S? 000
(100) 对应的错误图样是
z=(0000100)
将 y 和 z 进行矢量模二加得到正确的码子为,
x=(0010110)
§ 6.6:关于信道编码理论的若干评注
代数信道编码理论
– 概念,基于代数的信道编码构造方法发展成的系统理论
– 特点,运算基于有限域，距离度量使用汉明距离
– 问题,与实际信道信号差距大，
实际物理信道：信号是时间的实函数或复函数
高斯信道：信号之间用欧氏距离度量
香农信道编码理论
– 特点－－存在性
– 问题－－如何构造－－寻找香农意义好码的任务远未完成
当前发展,TCM码作业
1,设有一离散信道，其信道传递矩阵为并设 试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。
2,设无记忆二元对称信道的正确传递概率为，错误传递概率为 p＜ 1/2。
对于 (7,4)汉明码
(1)
(2) 在接收端,128个接收的二元序列应该对应译成什么码字。并说明其能
(3) 在最佳译码规则下，计算此码的平均错误概率 Pe
(4) 若 p=0.01，计算 Pe和码率 R.
2
1
6
1
3
1
3
1
2
1
6
1
6
1
3
1
2
1
4132211 )()(,)( xpxpxp
理解信道编码在通信系统中的作用
了解信道编码的的基本分类
了解信道编码性能评价的基本方法
了解汉明码的编译码原理
了解信道容量 /容量代价函数在信道编码定理中的作用
理解香农第二定理又称有噪信道编码定理的物理意义
了解信道编码理论与实际应用的差距本章研究内容
信道编码概述
错误概率与译码准则、编码方法
信道编码定理与联合典型序列
信道编码的性能界限
信道编码举例－汉明码
关于信道编码理论的若干评注
§ 6.1:信道编码概述
问题引出
什么是信道编码
信道编码的作用
信道编码的三种情形
信道编码的实质
§ 6.1:信道编码概述－ 问题引出
互信息能告诉我们什么？
– 随机变量 X,Y统计意义上的依存程度
– 可以获得的信息量
– 不能：所得信息能否可靠地确定信道输入？
无噪信道编码能告诉我们什么？
– 无噪无损信道，只要对信源输出进行适当编码，总能以最大信息传输率，
无差错的传输信息。
– 但是：一般信道总存在噪声或干扰，信息传输会造成损失
实际通信中人们对传输要求什么？
– 传输信息量大
– 传输可靠
提出的与信道传输有关的问题：
– 如何能使信息传输后发生的错误最少？
错误概率与那些因素有关？
有无办法控制？
能控制到什么程度？
– 无误传输可达的最大信息率是多少？
§ 6.1:信道编码概述－ 什么是信道编码
通信系统模型
信道编码,从消息到信道波形或矢量的映射希望通信系统与信道统计特性相匹配的编码信源编码信道编码信道信道译码信源译码消息集中一个元素信道波形空间中的一个点失真后的波形恢复的消息引入失真消息到波形的映射判断是消息集中的哪个元素
§ 6.1:信道编码概述－ 什么是信道编码
复接、代数编码、调制、成形滤波、扩频、上下变频等等都属于 广义的信道编码 范畴
注意,信道译码可以不是离散信道译码。只有当解调为硬判决输出时才是离散信道和离散信道译码信源编码离散信道编码信道调制信道译码解调信源译码广义信道或离散信道
§ 6.1:信道编码概述－ 信道编码的作用
信道编码的作用,在资源、可靠性和传信量 之间选择一个好的工作点（有时还要考虑延时）。
资源 指的提供信息传输所付出的代价
– 包括频率、时间、空间、功率等等。但不包括实现复杂度
– 一个好的编码就是要充分利用资源，传递尽可能多的信息
§ 6.1:信道编码概述－ 三种情形,
– 给定资源和可靠性要求，通过信道编码尽量提高传输速率（例：多电平编码）
– 给定对信息传输的速率和可靠性要求，通过信道编码尽量减少资源开销（例：扰乱编码）
– 给定资源和传输速率，通过编码提高可靠性
（例：检、纠错编码）
§ 6.1:信道编码概述－ 编码的实质
利用冗余降低差错概率
将所有可能的输入信息（消息）映射到信道符号（波形）空间的点，而这个点的集合要小于（包含于）全信道空间中。
§ 6.1:信道编码概述－ 信道编码的基本分类
按码的结构分,
– 线性码
线性分组码（群码）
卷积码（线性树码）
– 非线性码
按抗干扰模式分
– 抗随机差错码
– 抗突发差错码
按编译码理论所用数学工具分
– 代数码
– 几何码
– 组合码
按对错误的处理方式分
– 检错码
– 纠错码
§ 6.2:错误概率与译码准则、编码方法－ 1
错误概率与译码规则
– 错误概率 Pe与什么有关
信道的统计特性
译码规则
– 译码规则的选择依据
最大后验概率准则－－理想
最大似然准则－－实用编码
C
A
B
2
1
4
3
5
发送波形集合接收波形集合
P
A2
P
A1
P
A3
P
A4
P
A5
C
A
B
2
1
3
消息集合编码集合译码
§ 6.2:错误概率与译码准则、编码方法－ 2
信道 译码
An
1
2
4
3
w4
w3
w1
w2
x
x
x
An 是接收空 间
w1,w2,… 是 发 送的 码 子
围绕每 个 码 子有一个 译码 域?i
如果接收的 码 子在?i中,就 认为发 送的是 码 子 wi
发 生 错误
一般,An中 存在一些不属于任何
i的区域
有 时 接收 码 子会被映射到 错误 的
i，进 而被 译 成 错误 的 wi
正确 译码不知如何 译码译码错误
§ 6.2:错误概率与译码准则、编码方法－ 3
问题：
– 在输入和信道特性给定的条件下，差错概率将取决于接收矢量空间按什么样的划分准则进行划分
划分接收矢量空间的准则－－译码器的译码准则
§ 6.2:错误概率与译码准则、编码方法－ 4
§ 6.2:错误概率与译码准则、编码方法－ 5
准则一：平均错误概率最小译码准则
计算平均错误概率：
m
m
Yymygg
MmYMY
当表示成译码函数个不相交的子集
,)((,)
1,...2,1,0,}{
C
A
B
2
1
4
3
5
发送波形集合接收波形集合
P
A2
P
A1
P
A3
P
A4
P
A5
YX
)()|()()|(),(
)|(
ypyxpxpxypxyp
yxxyp
mmmm
mm
则按全概率公式有：
的概率，条件下接收矢量取是发送码字设若码字 Xm经传输后在接收端所得的接收矢量不落在 Ym子集中，则译码发生错误
1
0
)(
)()|(
)|()()(
)|(
M
m
mm
yp
xpxyp
m
xypxpyp
yxp mm
其中：
§ 6.2:错误概率与译码准则、编码方法－ 6
§ 6.2:错误概率与译码准则、编码方法－ 7
理想的译码器应使平均译码差错概率最小
)|( yxp m 是译码正确的概率，则译码发生错误的概率为：
)|(1| yxpp mye
译码器 平均 的译码差错概率为：
)|()(1
))|(1()()( |
yxpyp
yxpyppypP
y
m
m
yy
yee
m a x)|( yxp m
§ 6.2:错误概率与译码准则、编码方法－ 8
最小错误概率准则（最大后验概率准则）：
特点：
– 优点：理想
– 缺点,1、后验概率不易得到
2、后验概率依赖于输入分布
)|(m a x)|)(( yxpyygp mm?
§ 6.2:错误概率与译码准则、编码方法－ 9
准则二：最大似然译码准则
此时译码差错概率为：
平均的译码差错概率为：
)|(m a x))(|( mm xypygyp?
mYy
mme xypp )|(|
m
meme
m
me pmppxpP || )()(
§ 6.2:错误概率与译码准则、编码方法－ 10
最大后验概率译码准则 &最大似然译码准则
– 输入等概时－－二者是一致的此时：
)|()|( )(1 myMpm xypyxp?
)|(m a x)|(m a x )(1 myMpmmm xypyxp?
)|(m a x)(1 mmyMp xyp?
§ 6.2:错误概率与译码准则、编码方法－ 11
错误概率与编码
– 如何在信息传输率一定的前提下使 Pe?0
– 实际经验：重复发送可以使 Pe减小
重复次数 N很大时，可以使 Pe?0
但：信息传输率降低
– 信道编码定理,R一定时，可以找到一种编码方法使 Pe相当低
– 引入概念：码字距离
§ 6.2:错误概率与译码准则、编码方法－ 12
码字距离－汉明距离
– 长度为 n的两个符号序列 (码字 )αi和 βj之间的 距离 是指 αi
和 βj之间对应位置上不同码元的个数，用符号 D(αi,βj)
表示。这种码字距离通常称为 汉明距离例如,两个二元序列
αi=101111
βj=111100
则得 D(αi,βj)=3
又例如,两个四元序列
αi=1320120
βj=1220310
则得 D(αi,βj)
§ 6.2:错误概率与译码准则、编码方法－ 13
对于二元信道，即对于二元码，汉明距离可表达成下述若令 αi＝（ａ i1ａ i２ … ａ in） ａ ik∈ ｛ 0,1
βj＝（ bj1 bj2 … b jn） βjk∈ ｛ 0,1
则 αi和 βj的汉明距离为
D(αi,βj)＝
在某一码书 C中，任意两个码字的汉明距离的最小值称为该码 C的最小距离，即
dmin＝ min｛ D(Ci,Cj)｝ Ci≠Cj Ci,Cj∈ C
在任一码书中，码的最小距离 dmin与该码的译码错误概率有关。
jk
n
k
ik ba
1
§ 6.2:错误概率与译码准则、编码方法－ 14
与码字距离有关的结论
– 最小距离译码准则
– 在二进制对称信道中：
最小距离译码准则＝最大似然译码准则
),(m in))(,( mm xydygyd?
§ 6.3:信道编码定理与联合典型序列 -1
信道编码定理引出
– 问题,在有噪信道中，使平均误码率 Pe尽可能小的情况下，可达到的信息传输率是多少？
– 答案,信道容量 C
信道编码定理
信道编码定理的证明
– 证明思路
– 随机编码方法
– 联合典型序列
§ 6.3:信道编码定理与联合典型序列 -2
信道编码定理：
– 设 R是信息传输的速率,C是离散无记忆信道的信道容量,ε >0是任意小的数，则只要 R<C就总存在码字长为 N，码字数为 M=2NR的分组码使译码的平均差错概率 Pe<ε 。
§ 6.3:信道编码定理与联合典型序列 -3
信道编码定理的证明
思路：
– 通常思路,先构造一个理想的好码，并定义一种译码准则，计算该好码经过译码后的误码率
– 问题,构建极其复杂且无具体方法
N值很大时，误码率计算困难
– 香农采取的方法,
用 随机编码方法 得到所有可能码的集合
在其中随机选择一个码作为信道码
利用大数定理计算在集合平均意义上的该码性能
利用 联合典型序列 译码
– 香农采取的方法评价：
不很严格，不是最优，但便于理论分析
随机编码方法在后来严格的证明中一直被采用
§ 6.3:信道编码定理与联合典型序列 -4
随机编码方法：
– 对每一个消息 m,(m=0,1,…M -1),
编码为 xm=(xm1xm2…x mn)
其中,xmi (i=1,2,…n) 是按照输入字母的概率随机选取，从而得到全部 M=2NR个码字，组成码集 C＝（ x1x2….x M-1)
随机编码方法产生某一特定码字的概率 P(Xm)是：
1
0 1
)()(
M
m
N
i
imm XpXP
§ 6.3:信道编码定理与联合典型序列 -5
联合 ε 典型序列
– ε 典型序列,信源输出的随机序列－奠定了信源编码的基础
– 联合 ε 典型序列,两个随机变量的自然扩展，是信道编码的基础
– 联合 ε 典型序列定义：
– 联合 AEP定理
– 定理解释：
§ 6.3:信道编码定理与联合典型序列 -6
联合 ε 典型序列定义,
– 设（ X,Y）是长为 N的随机序列对，
则在这些随机序列对中满足下列条件的序列对被称为联合典型序列式中 δ 是任意小的数，联合典型序列的全体构成联合典型序列集，记做 G
),(),(
1
n
N
n
n yxpp?
yx
|)()(lo g| 1 XHxpN
|)()(lo g| 1 YHypN
|)()(lo g| 1 XYHxypN
§ 6.3:信道编码定理与联合典型序列 -7
联合 AEP定理,
– 设随机序列对（ X,Y)的,则对任意小的数 δ >0，我们总能找到足够大的 N使全体序列对的集合能被分成满足下述条件的集合 G及其补集 Gc：
（ 1）
（ 2）
（ 3）设（ X’,Y’）是相互独立的随机序列对，但它与
（ X,Y）有相同的边缘分布，即：
则：
),(),(
1 n
N
n n
yxpp?
yx
1}),{(
}),{(
GYXP
GYXP c
))((
))((
2)1(||
2||
XYHN
XYHN
G
G
)()()},(),{( ypxpyxYXP
]3);([
]3);([
2)1(}),{(
2}),{(
YXIN
YXIN
GYXP
GYXP
§ 6.3:信道编码定理与联合典型序列 -8
联合 AEP定理的解释：
– 两个随机变量情况下，序列 Xn,Yn及其联合序列 XnYn都具有 AEP
特性
– 联合典型序列对是高概率序列对
– 联合典型序列对出现概率接近相等，且其和接近于 1
– 联合典型序列对是一些密切关联的序列对
– 一般与 X对应的 Y可能是 Y空间的任一个，该定理说明：随 N的增大，对应 X的 Y只能是（ X,Y)典型序列对的 Y，取其他 Y的概率?0
– 联合典型序列数目为 2NH(XY)，
典型 x,典型 Y随机组合的空间为 2N[H(X)+H(Y)]，
联合典型序列占其中约 1/ 2NI(X;Y)，只是很小的一部分故：当 X的数目 < 2NI(X;Y)时，，可使 Pe?0
– 给出一种译码方法：译码时，取与接收矢量联合典型的码字作为输出，这种译码方法可以保证得到很低的误码率。
Input
sequence
Output
sequence…
……
…
……
y
wi
wi+1
2nH(XY)
sequences
that can
map to y
M = 2nR
code words
t h e n 0enPRCneP 2
§ 6.3:信道编码定理与联合典型序列 -9
信道编码定理证明的几点说明
– 香农只是证明了码的存在性，未给出构造方法
– 随机编码所得的码集很大，通过搜索得到好码的方法实际上很难实现；而且即使找到，码字也是毫无结构的，只能采用查表译码方法，当
N很大时，码表的存储量也很难接受
§ 6.4:信道编码的性能界限－ 1
理论性能极限－－存在性
– 香农信道编码定理
– 作用：理论极限、渐进性能
工程实现上的界限－－构造性
– 最小距离界限
– 作用：构造新码、估计新码性能时，说明新码与最好性能的码接近的程度
香农理论极限,R<C； 存在编译码方法使 Pe?0
给定 Pe；存在编译码方法使 R?C
RCneP 2
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
误码率
p
b
信噪比E
b
/N
0
(dB)
s
h
a
n
n
o
限仅内码
（
4
，
1
，
1
5
）
未编码仅内码
（
2
，
1
，
7
）
码级连级连
－ 1.59dB
0 1,5 9
bEN dB
§ 6.4:信道编码的性能界限－ 2
实际信道编码理论研究内容：
– 最佳码性能有多好？
– 如何设计好码？
– 如何译码？
最小距离限
– 在码长和最小距离给定时，具有最大可能的码字数
A(n,dmin)的码为好码。
– 完备码 A(n,dmin)的上下限
近半个世纪以来，上限不断改进，并逐步向下限靠近，但下限保持不变
未证明的看法：上下限会逐步会合成为一条限。
§ 6.5:信道编码举例－汉明码－ 1
汉明码的编码
汉明码的译码
§ 6.5:信道编码举例－汉明码－ 2
汉明码
– 第一个具有系统的编译码方法的信道码
（ 7,4）汉明码
– 码长 n=7,信息元 k=4，检验元 r=n-k=3。长为 3的二元序列共有 23＝８个。我们将其中 7个非全零序列按列排成如下矩阵
– H矩阵称为：一致监督矩阵。
1010101
1100110
1111000
)4,7(H
§ 6.5:信道编码举例－汉明码－ 3
设码字 C=（ c6c5c4c3c2c1c0),有：
H× CT=0T
其中,0＝（ 0 0 0）,0T是 0矢量的转置，即满足：
c3+c2+c1+c0=0
c5+c4+c1+c0=0
c6+c4+c2+c0=0
0000000 0100101 1000011 1100110
0001111 0101010 1001100 1101001
0010110 0110011 1010101 1110000
0011001 0111100 1011010 1111111
§ 6.5:信道编码举例－汉明码－ 4
给出生成矩阵
满足：
1111000
0110100
1010010
1100001
)4,7(G
cGm ][
0HG T
§ 6.5:信道编码举例－汉明码－ 5
（ 7,4）汉明码特点：
– 16个码字是所有码长为 7的二元序列中的一个封闭子集。
– 码的最小距离等于非零码字的最小重量＝ 3
能检 2个错，纠一个错。
d>=s+1 （检错时）
d>=2s+1 （纠错时）
§ 6.5:信道编码举例－汉明码－ 6
汉明码译码：
– 伴随式译码
– 错误图样 E?R=C+E
– 伴随式 S
TTTTT 0EHEHCHRH
TT SEH
0
1
2
s
s
s
TS
110
101
011
111
001
010
100
000
S
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000000
Z
伴随式 错误图样
假设接收到码矢 y=(0010010)
有 7个可能的错误位置,如 Z矩阵所示
伴随式是,ST= H RT
)10 0(
100
010
001
111
011
101
110
)00 100 10(?
S
Y 不是一个正确的码子，因为 S? 000
(100) 对应的错误图样是
z=(0000100)
将 y 和 z 进行矢量模二加得到正确的码子为,
x=(0010110)
§ 6.6:关于信道编码理论的若干评注
代数信道编码理论
– 概念,基于代数的信道编码构造方法发展成的系统理论
– 特点,运算基于有限域，距离度量使用汉明距离
– 问题,与实际信道信号差距大，
实际物理信道：信号是时间的实函数或复函数
高斯信道：信号之间用欧氏距离度量
香农信道编码理论
– 特点－－存在性
– 问题－－如何构造－－寻找香农意义好码的任务远未完成
当前发展,TCM码作业
1,设有一离散信道，其信道传递矩阵为并设 试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。
2,设无记忆二元对称信道的正确传递概率为，错误传递概率为 p＜ 1/2。
对于 (7,4)汉明码
(1)
(2) 在接收端,128个接收的二元序列应该对应译成什么码字。并说明其能
(3) 在最佳译码规则下，计算此码的平均错误概率 Pe
(4) 若 p=0.01，计算 Pe和码率 R.
2
1
6
1
3
1
3
1
2
1
6
1
6
1
3
1
2
1
4132211 )()(,)( xpxpxp
