信道编码数学与计算机科学学院 朱西平
(xpzhu188@163.com )
信息传送与编码通信的目的是要把对方不知道的消息及时可靠地（有时是秘密地）传送给对方。
11000 信道消息 11100 错误消息作一个规定：在传送端消息元后加一个检错元，传送端的消息元相加模 2都是 0
这就是 奇偶校验码
11000 信道 111000 0
校验元重复码传的消息,0,1
0 00 1 11
校验元若传 000,收到误传为 100,010,001中的任一种,
则认为是传的 000，实现了纠错。
v?c?m信息 发送码字 接收分组 译码码字 译码消息 译码状态
0
0
0
0
1
1
1
1
000
000
000
000
111
111
111
111
000
001
010
011
100
101
110
111
000
000
000
111
000
111
111
111
0
0
0
1
0
1
1
1
正确译码正确译码正确译码错误译码错误译码正确译码正确译码正确译码
m c
“0”个数多，就认为发送的是,000”
“1”个数多，就认为发送的是,111”
m?mtstr
发信机 收信机安全编码信源编码信源信道编码信道信道译码信源译码安全译码信宿
ECC编码 编码信道 ECC译码一般性编码通信模型简化的纠错编码通信模型离散信道编码问题设信道是一个 D元字母输入 / D元字母输出的 DMC信道，字母表为 {0,1,…,D-1}。其信道转移概率矩阵为 D× D矩阵如下。
这是一个对称信道。信道传输错误的概率定义为
P(输出不等于 k|输入为 k)= p,k∈ {0,1,…,D-1}。此处 p<(1-p)。
p
D
p
D
p
D
p
p
D
p
D
p
D
p
p
1
11
1
1
1
11
1
离散信道编码问题设信源消息序列经过 D元 信源编码（ 等长编码或不等长编码 ）
后变成了如下的随机变量序列
… X-2X-1X0X1X2…,
其中每个随机变量 Xl的事件全体都是 D元字母表
{0,1,…,D-1}。
将此随机变量序列切割成 L维随机向量准备输入信道：
(X1X2… XL),(XL+1XL+2… X2L),… 。
如果直接将 (X1X2… XL)输入信道，信道的输出为 (X1’X2’… XL’)，则
①当信道传输错误时无法检测到（即接收方无法确知是否正确接收）。
②正确接收的概率为 P((X1’X2’… XL’)=(X1X2… XL))
=P(X1’=X1)P(X2’=X2)… P(XL’=XL)=(1-p)L。
离散信道编码问题将 (X1X2… XL)进行变换：
C(X1X2… XL)=(U1U2… UN)，
其中 (U1U2… UN)为 N维随机向量,N>L，且变换是单射（即
(X1X2… XL)的不同事件映射到 (U1U2… UN)的不同事件）。
将 (U1U2… UN)输入信道；
信道的输出为 (Y1Y2… YN)；
再 根据 (Y1Y2… YN)的值猜测出输入信道的值 (U1’U2’… UN’)，
并根据变换式
(U1’U2’… UN’)=C(X1’X2’… XL’)
将 (U1’U2’… UN’)反变换为 (X1’X2’… XL’)。
如果 (X1’X2’… XL’)=(X1X2… XL)，则正确接收。
离散信道编码问题
（ 1） (X1X2… XL)的事件共有 DL个，因此 (U1U2… UN)的事件共有 DL个，占 N维向量值的份额为 DL/DN=1/DN-L。因此当信道传输错误时，有可能使输出值 (Y1Y2… YN)不在这 1/DN-L份额之内。这就是说，信道传输错误有可能被检测到。
（ 2）如果精心地设计变换 C(X1X2… XL)=(U1U2… UN)和猜测规则 (Y1Y2… YN)→ (U1’U2’… UN’)，则正确接收的概率远远大于
(1-p)L。
（ 3）变换
(X1X2… XL)→ (U1U2… UN)=C(X1X2… XL)
称为 信道编码,又称为 (N,L)码 。一个事件的变换值称为该事件的 码字 。 L称为信息长,N称为码长。
离散信道编码问题
（ 4）过程
(Y1Y2… YN)→ (U1’U2’… UN’)→ (X1’X2’… XL’)
称为 纠错译码 。当 (X1’X2’… XL’)=(X1X2… XL)时称为正确译码
（实际上就是正确接收）。
（ 5） N比 L大得越多,1/DN-L份额越小，信道传输错误不在这
1/DN-L份额之内的可能性越大，即信道传输错误越容易被检测到。但 N比 L大得越多，信道传输的浪费越大。
（ 6）称 R=L/N为编码速率，也称为信息率。（似乎与信源编码相互倒置？）
离散信道编码问题关于译码准则当信道的输出值为 y时，将其译为哪个码字 u最合理？
最大后验概率准则简记 b(u|y)=P((U1U2… UN)=u|(Y1Y2… YN)=y)。称 b(u|y)为后验概率。
最大后验概率准则：
。译为码字将输出值时，当跑遍所有码字
)0(
)0( )|(m ax)|(
uy
yubyub
u
离散信道编码问题后验概率的计算：记
q(u)=P((U1U2… UN)=u)，称 q(u)为先验概率；
pN(y|u)=P( (Y1Y2… YN)=y|(U1U2… UN)=u)，我们知道 p(y|u)是信道响应特性，而且
pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)… P(YN=yN|UN=uN)
=(p/D)d(1-p)N-d，
其中 d是 (y1y2… yN)与 (u1u2… uN)对应位置值不相同的位数；
（以后将称 d为 Hamming距离）
离散信道编码问题记 w(y)=P((Y1Y2… YN)=y)。我们知道
（贝叶斯公式）；
（全概率公式）；
跑遍所有的码字跑遍所有的码字
c
N
NN
u
N
cypcq
uypuq
yw
uypuq
yub
uypuqyw
)|()(
)|()(
)(
)|()(
)|(
)|()()(
离散信道编码问题最大似然概率准则最小距离准则（最小错误准则）
y与 u的 Hamming距离定义为 (y1y2… yN)与 (u1u2… uN)对应位置值不相同的位数，记为 d(y,u)。
。译为码字将输出值时，当跑遍所有码字
)0(
)0( )|(m ax)|(
uy
uypuyp N
uN
。译为码字将输出值时，当跑遍所有码字
)0(
)0( ),(m i n),(
uy
uyduyd
u
离散信道编码问题命题 最大似然概率准则等价于最小距离准则。
证明
pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)… P(YN=yN|UN=uN)
=(p/D)d(1-p)N-d，
其中 d是 y与 u的 Hamming距离。
注意到 p/D<(1-p)。所以
pN(y|u)达到最大，当且仅当 y与 u的 Hamming距离达到最小。
得证。
离散信道编码问题命题 如果每个码字是等概出现的，则最大后验概率准则等价于最大似然概率准则。
证明
)|(m a x
)(
)(
)(
)|()(
m a x)|(m a x
)0(
uyp
yw
uq
yw
uypuq
yub
N
u
N
uu
跑遍所有码字跑遍所有码字跑遍所有码字
离散信道编码问题对两种译码准则的评述最大后验概率准则具有很好的直观合理性。收到 y的条件下，
最可能发送的是哪个码字，就认为发送的是哪个码字,。
最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到 y，就认为发送的是哪个码字。
最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：前者只需要看哪个码字与 y的 Hamming
距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。
两种准则都可以用在没有编码（直接发送）情况下的纠错译码。
离散信道编码问题例 BSC信道的转移概率矩阵为取 L=1。如果直接将 X1输入信道，信道的输出为 X1’，则
①当信道传输错误时无法检测到。
②正确接收的概率为 P(X1’=X1)=1-p。
今取 L=1,N=4，二元 (4,1)码如下：
0→ 0000，
1→ 1111。
pp
pp
1
1
离散信道编码问题译码规则如下：
当 (Y1Y2Y3Y4)中 1的个数为 3或 4时,(Y1Y2Y3Y4)→ (1111)→ 1；
当 (Y1Y2Y3Y4)中 1的个数为 0或 1时,(Y1Y2Y3Y4)→ (0000)→ 0；
当 (Y1Y2Y3Y4)中 1的个数为 2时，
(0011),(1100),(1001)→ (0000)→ 0，
(0101),(1010),(0110)→ (1111)→ 1。
译码规则显然是 最小距离准则。
离散信道编码问题何时检测到信道传输错误？当 (Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。
换句话说,(Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离
≥1且 ≤3时，检测到信道传输错误。
因此，信道传输有错误但能检测出错误的概率为
133422243114 )1()1()1( ppCppCppC
离散信道编码问题何时正确译码（正确接收）？
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 ≤1时，正确译码；
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 =2时，一半能正确译码，另一半不能正确译码；
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 ≥3时，不能正确译码。
正确译码（正确接收）的概率为
222
4
311
4
400
4 )1(2
1)1()1( ppCppCppC
离散信道编码问题
。
时：当
9.01;9 7 2.0)1(
2
1
)1()1(
1.0
222
4
311
4
400
4
p
ppCppCppC
p
。
时：当
99.01;9 9 9 7 0 2.0)1(
2
1
)1()1(
01.0
222
4
311
4
400
4
p
ppCppCppC
p
离散信道编码定理首先需要说明，上述离散信道编码的编码速率（信息率 R ）
本来是设备所确定的。当信源每秒产生 ns个字母，信道编码所使用的设备每秒产生 nc个字母，则设备所确定的编码速率就是 R = ns/nc。
其次，实际编码速率（实际信息率 L/N ）必须不小于设备所确定的编码速率：
L/N ≥R。
于是对离散信道编码有了以下两条相互矛盾的要求：
（ 1）实际编码速率 L/N 尽可能小以便使正确译码（正确接收）
的概率尽可能接近 1。
（ 2）实际编码速率不小于设备所确定的编码速率 L/N ≥R。
离散信道编码定理设信源序列经过信源编码后变成了如下的序列
… X-2X-1X0X1X2… 。
设各随机变量独立同分布。记 H(X)为 X0的熵,C为信道容量。
如果设备所确定的编码速率 R<C/H(X)，则能够同时满足以下两条要求：
（ 1） L/N使正确译码（正确接收）的概率尽可能接近 1。
（ 2） L/N ≥R。
如果设备所确定的编码速率 R>C/H(X)，则不能够同时满足这两条要求。
（如果设备所确定的编码速率 R=C/H(X)，则情况如何？很复杂，属于边界情况，没有简单整齐的结论。 ）
离散信道编码定理
Shannon信道编码定理如果设备所确定的编码速率 R<C/H(X)，则对任何正整数
L（ L=1,2,… ），存在 D元 (N,L)码和对应的译码方法，
使
）。（实际上； RNLLRNL Llim,2,1?
1)),((lim 码被正确译码LNPL
(xpzhu188@163.com )
信息传送与编码通信的目的是要把对方不知道的消息及时可靠地（有时是秘密地）传送给对方。
11000 信道消息 11100 错误消息作一个规定：在传送端消息元后加一个检错元，传送端的消息元相加模 2都是 0
这就是 奇偶校验码
11000 信道 111000 0
校验元重复码传的消息,0,1
0 00 1 11
校验元若传 000,收到误传为 100,010,001中的任一种,
则认为是传的 000，实现了纠错。
v?c?m信息 发送码字 接收分组 译码码字 译码消息 译码状态
0
0
0
0
1
1
1
1
000
000
000
000
111
111
111
111
000
001
010
011
100
101
110
111
000
000
000
111
000
111
111
111
0
0
0
1
0
1
1
1
正确译码正确译码正确译码错误译码错误译码正确译码正确译码正确译码
m c
“0”个数多，就认为发送的是,000”
“1”个数多，就认为发送的是,111”
m?mtstr
发信机 收信机安全编码信源编码信源信道编码信道信道译码信源译码安全译码信宿
ECC编码 编码信道 ECC译码一般性编码通信模型简化的纠错编码通信模型离散信道编码问题设信道是一个 D元字母输入 / D元字母输出的 DMC信道，字母表为 {0,1,…,D-1}。其信道转移概率矩阵为 D× D矩阵如下。
这是一个对称信道。信道传输错误的概率定义为
P(输出不等于 k|输入为 k)= p,k∈ {0,1,…,D-1}。此处 p<(1-p)。
p
D
p
D
p
D
p
p
D
p
D
p
D
p
p
1
11
1
1
1
11
1
离散信道编码问题设信源消息序列经过 D元 信源编码（ 等长编码或不等长编码 ）
后变成了如下的随机变量序列
… X-2X-1X0X1X2…,
其中每个随机变量 Xl的事件全体都是 D元字母表
{0,1,…,D-1}。
将此随机变量序列切割成 L维随机向量准备输入信道：
(X1X2… XL),(XL+1XL+2… X2L),… 。
如果直接将 (X1X2… XL)输入信道，信道的输出为 (X1’X2’… XL’)，则
①当信道传输错误时无法检测到（即接收方无法确知是否正确接收）。
②正确接收的概率为 P((X1’X2’… XL’)=(X1X2… XL))
=P(X1’=X1)P(X2’=X2)… P(XL’=XL)=(1-p)L。
离散信道编码问题将 (X1X2… XL)进行变换：
C(X1X2… XL)=(U1U2… UN)，
其中 (U1U2… UN)为 N维随机向量,N>L，且变换是单射（即
(X1X2… XL)的不同事件映射到 (U1U2… UN)的不同事件）。
将 (U1U2… UN)输入信道；
信道的输出为 (Y1Y2… YN)；
再 根据 (Y1Y2… YN)的值猜测出输入信道的值 (U1’U2’… UN’)，
并根据变换式
(U1’U2’… UN’)=C(X1’X2’… XL’)
将 (U1’U2’… UN’)反变换为 (X1’X2’… XL’)。
如果 (X1’X2’… XL’)=(X1X2… XL)，则正确接收。
离散信道编码问题
（ 1） (X1X2… XL)的事件共有 DL个，因此 (U1U2… UN)的事件共有 DL个，占 N维向量值的份额为 DL/DN=1/DN-L。因此当信道传输错误时，有可能使输出值 (Y1Y2… YN)不在这 1/DN-L份额之内。这就是说，信道传输错误有可能被检测到。
（ 2）如果精心地设计变换 C(X1X2… XL)=(U1U2… UN)和猜测规则 (Y1Y2… YN)→ (U1’U2’… UN’)，则正确接收的概率远远大于
(1-p)L。
（ 3）变换
(X1X2… XL)→ (U1U2… UN)=C(X1X2… XL)
称为 信道编码,又称为 (N,L)码 。一个事件的变换值称为该事件的 码字 。 L称为信息长,N称为码长。
离散信道编码问题
（ 4）过程
(Y1Y2… YN)→ (U1’U2’… UN’)→ (X1’X2’… XL’)
称为 纠错译码 。当 (X1’X2’… XL’)=(X1X2… XL)时称为正确译码
（实际上就是正确接收）。
（ 5） N比 L大得越多,1/DN-L份额越小，信道传输错误不在这
1/DN-L份额之内的可能性越大，即信道传输错误越容易被检测到。但 N比 L大得越多，信道传输的浪费越大。
（ 6）称 R=L/N为编码速率，也称为信息率。（似乎与信源编码相互倒置？）
离散信道编码问题关于译码准则当信道的输出值为 y时，将其译为哪个码字 u最合理？
最大后验概率准则简记 b(u|y)=P((U1U2… UN)=u|(Y1Y2… YN)=y)。称 b(u|y)为后验概率。
最大后验概率准则：
。译为码字将输出值时，当跑遍所有码字
)0(
)0( )|(m ax)|(
uy
yubyub
u
离散信道编码问题后验概率的计算：记
q(u)=P((U1U2… UN)=u)，称 q(u)为先验概率；
pN(y|u)=P( (Y1Y2… YN)=y|(U1U2… UN)=u)，我们知道 p(y|u)是信道响应特性，而且
pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)… P(YN=yN|UN=uN)
=(p/D)d(1-p)N-d，
其中 d是 (y1y2… yN)与 (u1u2… uN)对应位置值不相同的位数；
（以后将称 d为 Hamming距离）
离散信道编码问题记 w(y)=P((Y1Y2… YN)=y)。我们知道
（贝叶斯公式）；
（全概率公式）；
跑遍所有的码字跑遍所有的码字
c
N
NN
u
N
cypcq
uypuq
yw
uypuq
yub
uypuqyw
)|()(
)|()(
)(
)|()(
)|(
)|()()(
离散信道编码问题最大似然概率准则最小距离准则（最小错误准则）
y与 u的 Hamming距离定义为 (y1y2… yN)与 (u1u2… uN)对应位置值不相同的位数，记为 d(y,u)。
。译为码字将输出值时，当跑遍所有码字
)0(
)0( )|(m ax)|(
uy
uypuyp N
uN
。译为码字将输出值时，当跑遍所有码字
)0(
)0( ),(m i n),(
uy
uyduyd
u
离散信道编码问题命题 最大似然概率准则等价于最小距离准则。
证明
pN(y|u)=P(Y1=y1|U1=u1)P(Y2=y2|U2=u2)… P(YN=yN|UN=uN)
=(p/D)d(1-p)N-d，
其中 d是 y与 u的 Hamming距离。
注意到 p/D<(1-p)。所以
pN(y|u)达到最大，当且仅当 y与 u的 Hamming距离达到最小。
得证。
离散信道编码问题命题 如果每个码字是等概出现的，则最大后验概率准则等价于最大似然概率准则。
证明
)|(m a x
)(
)(
)(
)|()(
m a x)|(m a x
)0(
uyp
yw
uq
yw
uypuq
yub
N
u
N
uu
跑遍所有码字跑遍所有码字跑遍所有码字
离散信道编码问题对两种译码准则的评述最大后验概率准则具有很好的直观合理性。收到 y的条件下，
最可能发送的是哪个码字，就认为发送的是哪个码字,。
最大似然概率准则（最小距离准则）所具有的直观合理性弱一些。发送哪个码字的条件下，最可能收到 y，就认为发送的是哪个码字。
最大似然概率准则（最小距离准则）的实现比最大后验概率准则的实现更简单：前者只需要看哪个码字与 y的 Hamming
距离最小；后者需要知道各码字的概率分布，然后用贝叶斯公式计算并比较后验概率。
两种准则都可以用在没有编码（直接发送）情况下的纠错译码。
离散信道编码问题例 BSC信道的转移概率矩阵为取 L=1。如果直接将 X1输入信道，信道的输出为 X1’，则
①当信道传输错误时无法检测到。
②正确接收的概率为 P(X1’=X1)=1-p。
今取 L=1,N=4，二元 (4,1)码如下：
0→ 0000，
1→ 1111。
pp
pp
1
1
离散信道编码问题译码规则如下：
当 (Y1Y2Y3Y4)中 1的个数为 3或 4时,(Y1Y2Y3Y4)→ (1111)→ 1；
当 (Y1Y2Y3Y4)中 1的个数为 0或 1时,(Y1Y2Y3Y4)→ (0000)→ 0；
当 (Y1Y2Y3Y4)中 1的个数为 2时，
(0011),(1100),(1001)→ (0000)→ 0，
(0101),(1010),(0110)→ (1111)→ 1。
译码规则显然是 最小距离准则。
离散信道编码问题何时检测到信道传输错误？当 (Y1Y2Y3Y4)不是一个码字时，检测到信道传输错误。
换句话说,(Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离
≥1且 ≤3时，检测到信道传输错误。
因此，信道传输有错误但能检测出错误的概率为
133422243114 )1()1()1( ppCppCppC
离散信道编码问题何时正确译码（正确接收）？
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 ≤1时，正确译码；
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 =2时，一半能正确译码，另一半不能正确译码；
当 (Y1Y2Y3Y4)与原发码字 (U1U2U3U4) 的 Hamming距离 ≥3时，不能正确译码。
正确译码（正确接收）的概率为
222
4
311
4
400
4 )1(2
1)1()1( ppCppCppC
离散信道编码问题
。
时：当
9.01;9 7 2.0)1(
2
1
)1()1(
1.0
222
4
311
4
400
4
p
ppCppCppC
p
。
时：当
99.01;9 9 9 7 0 2.0)1(
2
1
)1()1(
01.0
222
4
311
4
400
4
p
ppCppCppC
p
离散信道编码定理首先需要说明，上述离散信道编码的编码速率（信息率 R ）
本来是设备所确定的。当信源每秒产生 ns个字母，信道编码所使用的设备每秒产生 nc个字母，则设备所确定的编码速率就是 R = ns/nc。
其次，实际编码速率（实际信息率 L/N ）必须不小于设备所确定的编码速率：
L/N ≥R。
于是对离散信道编码有了以下两条相互矛盾的要求：
（ 1）实际编码速率 L/N 尽可能小以便使正确译码（正确接收）
的概率尽可能接近 1。
（ 2）实际编码速率不小于设备所确定的编码速率 L/N ≥R。
离散信道编码定理设信源序列经过信源编码后变成了如下的序列
… X-2X-1X0X1X2… 。
设各随机变量独立同分布。记 H(X)为 X0的熵,C为信道容量。
如果设备所确定的编码速率 R<C/H(X)，则能够同时满足以下两条要求：
（ 1） L/N使正确译码（正确接收）的概率尽可能接近 1。
（ 2） L/N ≥R。
如果设备所确定的编码速率 R>C/H(X)，则不能够同时满足这两条要求。
（如果设备所确定的编码速率 R=C/H(X)，则情况如何？很复杂，属于边界情况，没有简单整齐的结论。 ）
离散信道编码定理
Shannon信道编码定理如果设备所确定的编码速率 R<C/H(X)，则对任何正整数
L（ L=1,2,… ），存在 D元 (N,L)码和对应的译码方法，
使
）。（实际上； RNLLRNL Llim,2,1?
1)),((lim 码被正确译码LNPL
