无线通信工程姚彦教授清华大学微波与数字通信国家重点实验室
2001年 12月 1日第七讲无线通信的信道编码引言基本概念
仙侬定理指出带宽和功率的互换性。当带宽为无限大时,Eb/N0趋于 -1.6dB,这就是仙侬极限。
如何实现带宽和功率的互换，仙侬定理本身没有指明。
能否用扩频技术实现带宽与功率的互换？不能！
在高斯白噪声信道上，扩频技术没有任何功率增益。
要实现带宽和功率的互换，可以采用纠错技术。
纠错属于一种信道编码。
基本概念
信道编码的目的信道编码是为了保证信息传输的可靠性、提高传输质量而设计的一种编码。它是在信息码中增加一定数量的多余码元，使码字具有一定的抗干扰能力。
信道编码的实质信道编码的实质就是在信息码中增加一定数量的多余码元（称为监督码元），使它们满足一定的约束关系，这样由信息码元和监督码元共同组成一个由信道传输的码字。
举例而言，欲传输 k位信息，经过编码得到长为 n(n>k)的码字，则增加了 n - k = r 位多余码元，我们定义 R = k
/ n 为编码效率。
基本概念
信道编码公式令信息速率为 fb,经过编码以后的速率为 ft,定义,R＝
fb/ft为编码率。则对于任何一个信道，总存在一个截止速率 R0,只要 R?R0,总可以达到,BER?CR2-nR0,其中 CR为某个常数,n为编码的约束长度。
对于等概二进码,AWGN信道，有：
)1(l o g1 00 /20 NER beR
12
1ln1
)1(
00
0?
Rb RNE
基本概念频带扩展 d B
0 1 2 3 4 5 6
1
2
3
4
5
6
7
E
b
/
N
o
(
d
B
)
1 7/8 3/4 2/3 1/2 1/4
R 0 1 0 l o g 1 / R 0
基本概念
从图可以看出：当带宽,R0?0，得到
Eb/N0?1.4dB,信道编码所能达到的极限比仙侬极限差 3dB。
从图可以看出,若 R0?1,即不加任何信道编码，这时 Eb/N0，说明在有限信噪比情况下无法达到无差错传输。
从图可以看出：对于一定的 R0,相当于一定的带宽扩展率，存在一个有限的 Eb/N0,这时可以通过选择适当的 n达到任意低的差错率。
性能指标
编码率、编码效率、码率
编码增益
编码延时
编译码器的复杂度分类
根据码的规律性可分为：正交编码和检、纠错码
根据监督元与信息组之间关系可分为：分组码和卷积码
根据监督元与信息元之间关系可分为：线性码和非线性码
根据码的功能可分为：检错码和纠错码分类（续）
信道编码检纠错码正交编码分组码卷积码
m 序列
L 序列非线性码线性码恒比码群计数码非循环码循环码非系统卷积码系统卷积码正交码
W-A码岩垂码扩散码奇偶校验码汉明码
BCH码
RS码分组码
k k k k
k k k k
n
工作原理
图中,n? k,R＝ k/n,称为编码率。
分组码的基本原理是将信息码分成 K比特一组，然后将每组的比特数扩展成 n（ n? k）,也就是说在信息比特中插入 n-k个比特。
另一种看法：将 2k矢量空间映射到 2n矢量空间。
工作原理（续）
定义几个参数：
码重：一组二进制码中,1”的个数码距 d,二组二进制码之间,0”或,1”不同的位数
定理：
（ 1） 为检查出 e个错误，要求,dmin? e+1
（ 2） 为纠正 t个错误，要求,dmin? 2t+1
（ 3） 为纠正 t个错误，同时检查出 e个错误，要求：
dmin? e+t+1 （ e? t）
用图说明
A AB B
线性分组码 ----举例
奇偶监督码
汉明码
BCH码
RS码
CRC码奇偶监督码
采用奇偶校验原理。
只能检错，不能纠错。
只能检查出某一分组的单个错误或奇数个错误，
而不能发现偶数个错误。
最小码距为 2。
水平奇偶监督码
水平垂直奇偶监督码。
汉明 码
（ Hamming码）
是一种纠正单个错误的线性分组码。
特点,码长 n = 2m-1
信息码位 k = 2n-m-1
监督码位 r = n-k = m
最小码距 d = 3
纠错能力 t = 1
扩展的汉明码：将监督码位由 m增至 m+1,信息位不变，这时最小码距增加到 d = 4,能纠正 1位错误同时检查出 2位错误。
BCH码
（ Bose-Chaudhuri-Hocquenghem码）
是线性分组码中循环码的一种重要子类，有严密的代数结构，是目前研究较多、应用较广的一种线性分组码。
具有纠正多个随机错误的能力。
根据对纠错能力的要求，选择参数，并根据代数结构构造编译码算法。
如,n = 7,k = 4,t = 1;
n = 15,k = 7,t = 2;
n = 31,k = 16,t = 3;
n = 127,k = 50,t = 13。
RS码
（ Reed-Solomon码）
是一种非二进制的 BCH码。即：在（ n,k） RS码中，输入信息被分成 km比特一组，每组包括 k个符号，每个符号由 m比特组成。
纠正 t个符号错误的 RS码参数如下：
码长 n = 2m-1符号,或 m(2m-1)比特信息段 k符号,或 km比特监督段 n-k=2t符号,或 m(n-k)比特最小码距 d=2t+1符号,或 m(2t+1)比特
CRC码
（循环冗余校验码）
是一种循环码，用于检错。
具有很强的检错能力，而且编码器及译码器都很容易实现。因而在数据通信中得到广泛应用。
可以检测出的错误如下：
（ 1）突发长度?n-k的突发错误；
（ 2）大部分突发长度＝ n-k+1的错误；
（ 3）大部分突发长度?n-k+1的错误；
（ 4）所有与许用码组的码距?dmin-1的错误；
（ 5）所有奇数个随机错误。
卷积码概述
分组码?卷积码
固定窗型?滑动窗型
k k k k k k k k
n n n n n n n n
k k k k k k k k
n n n n n n n n
概述（续）
例,R＝ 1/2卷积码
k k k k k k k k
＋
＋
Ik
ak
bk
编码原理
原理图映射
u j0
u j1
u j,k-1
u j-m,k-1
u j-m,1
u j-m,0
x j0
x j1
x j,n-1
...
...
...
...
...
...
...
m stage delay
编码原理（续）
几个例子
+
+
u j
x j0
x j1
u j
x j0
x j1
(4)
(1)
+
(2)
x j0
x j1
u j
+
+
+
x j0
x j1
x j2
u j0
u j1
(3)
返回编码原理（续）
卷积码的参数
– 约束长度 N，
– 输入比特 k，
– 输出比特 n，
– 编码率 R＝ k/n
编码原理（续）
状态转移图和 trellis图表示
0110
11
00
1 ；1 0
1 ；0 1 0 ；0 1
0 ；1 0
1 ；0 0
1 ；1 1 0 ；1 1
0 ；0 0
0/00
1/11
0/00 0/00 0/00
1/11
1/11 1/11
1/01
0/10
1/10 1/10
0/01 0/01
1/00 1/00
0/11
0/11 1/00
0/100/10
00
10
01
11
1/00
译码原理 ----方法分类
代数译码：纠错译码的经典方法。利用纠错码的代数结构，经过一定的代数运算，消除误差，恢复正确的信息。常用的有：大数译码逻辑。特点：电路简单，
编码增益低。
概率译码：纠错译码的新方法。考虑到信道的统计特性。常用的有：序列译码、
维特比译码。特点：电路复杂，编码增益高。
译码原理 ----序列译码
原理,在码树图中每向前走一步，在决定走哪一个分支时根据该分支子码与该时刻接收子码之间的相似程度来判断。
亦称为逐分支译码。
一般采用对数似然值度量该相似程度
log P(R|C)=log?iP(ri|ci)=?ilog(p(ri|ci))
堆栈译码和费诺译码译码原理 ----序列译码（续）
优点
– 运算量和约束长度无关。
缺点
– 运算量和信道质量有关。
– 没有利用卷积码的记忆特性，不是最优算法。
译码原理 ----维特比译码
最大后验与最大似然译码
MAP:
ML:
硬判决和软判决硬判决：解调器直接判 0,1
软判决：解调器对输出进行量化
)|(m a xa r g~ iiSi SrfPS
i
)|(m a xa r g~ iSi SrfS
i
译码原理 ----维特比译码（续）
Viterbi译码原理
– Viterbi译码是建立在最大似然译码基础上的译码方法
– 在译码过程中只需考虑整个路径集合中那些能使似然函数最大的路径
– 最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾
1
0
)(~ )(~ ),(),( mL
j
i
jj
i
i xrxr
译码原理 ----维特比译码（续）
Viterbi译码举例
– 设对于编码前信息比特为 (0,0,0,0,0,0)的接收序列为则硬判结果为基于软判决时，采用如下路径度量
9.0,2.15.0,2.06.0,5.03.1,5.09.0,1.03.0,1.1~r
0,01,10,00,00,11,0~?r
)1()1(,)0()0(,,),( jpijpipij rxrxxr
译码原理 ----维特比译码（续）
1
1
1
2
2
3
2
1
3
3
2
2
3
3
2
3
2
2
2
3
3
3
00
10
01
11
基于硬判决的Viterbi译码
Trellis图译码原理 ----维特比译码（续）
0.8
0.2
0
1.6
-1.8
3.4
2.0
0.8
-0.8
3.8
5.2
2.2
2.6
4.5
2.3
2.1
1.9
5.9
4.3
4.9
5.5
00
10
01
11
-0.8
基于软判决的Vite rbi译码
Trellis图译码原理 ----维特比译码（续）
Viterbi译码的特点
– 维特比算法是最大似然的序列译码算法
– 译码复杂度与信道质量无关
– 运算量和存贮量都与码长呈线性关系
– 运算量和存贮量都与状态数呈线性关系
– 状态数随 k及 m呈指数关系
Turbo码产生背景
交织
– 块交织：行写入，列读出
– 卷积交织,L
L L
L L L
LL L L
LL L L L
0
1
2
3
W-2
W-1
入 出产生背景（续）
串行级联码
优点：性能较一般短码有很大改善
缺点：编码效率低；当 R/C → 1时性能迅速恶化外 码编 码内 码编 码 交 织 器信 息 数 据 编 码 输 出编 码 器内 码译 码外 码译 码 解 交 织接 收 信 号 译 码 输 出译 码 器产生背景（续）
软输入软输出和迭代译码对数似然比 LLR
)()()()()()(
)()()()|(
)1(
)1(
l o g
)1|(
)1|(
l o g
)|1(
)|1(
l o g)|()(
^^^
'
^
^
'
dLdLxLdLdLdL
dLxLdLdxL
dP
dP
dxP
dxP
xdP
xdP
xdLdL
ece
c
产生背景（续）
软输入软输出和迭代译码
Soft-in
soft-out
decoder
feedback for the next iteration
L e (d)
L' (d)L c (x)
L (d)
L(d),priori values
L c (x),channel values
L e (d),extrinsic values
L'(d),posterori values
output LLR = L e (d)+ L'(d)
返回编译码原理
编码原理编 码 器 1
编 码 器 2 交 织 器开 关单 元复接器编 码 输 出信 息 数 据编译码原理（续）
译码原理软 输出 译码 器
1
软 输出 译码 器
2
外 信 息 Z
1k
交 织交 织似然值L
1k
解交织信 息 符号 序 列校验序列y
2k
校验序列 y
1k
判决器译码输出似然值L
2k
外信息Z
2k
x
k
迭代译码几点说明
Turbo码具有优越性能的原因
寻找构造好码的规律（分量码构造，交织器构造等）
译码延时大，译码算法复杂
广泛应用于移动通信、军事通信、深空及卫星通信等
2001年 12月 1日第七讲无线通信的信道编码引言基本概念
仙侬定理指出带宽和功率的互换性。当带宽为无限大时,Eb/N0趋于 -1.6dB,这就是仙侬极限。
如何实现带宽和功率的互换，仙侬定理本身没有指明。
能否用扩频技术实现带宽与功率的互换？不能！
在高斯白噪声信道上，扩频技术没有任何功率增益。
要实现带宽和功率的互换，可以采用纠错技术。
纠错属于一种信道编码。
基本概念
信道编码的目的信道编码是为了保证信息传输的可靠性、提高传输质量而设计的一种编码。它是在信息码中增加一定数量的多余码元，使码字具有一定的抗干扰能力。
信道编码的实质信道编码的实质就是在信息码中增加一定数量的多余码元（称为监督码元），使它们满足一定的约束关系，这样由信息码元和监督码元共同组成一个由信道传输的码字。
举例而言，欲传输 k位信息，经过编码得到长为 n(n>k)的码字，则增加了 n - k = r 位多余码元，我们定义 R = k
/ n 为编码效率。
基本概念
信道编码公式令信息速率为 fb,经过编码以后的速率为 ft,定义,R＝
fb/ft为编码率。则对于任何一个信道，总存在一个截止速率 R0,只要 R?R0,总可以达到,BER?CR2-nR0,其中 CR为某个常数,n为编码的约束长度。
对于等概二进码,AWGN信道，有：
)1(l o g1 00 /20 NER beR
12
1ln1
)1(
00
0?
Rb RNE
基本概念频带扩展 d B
0 1 2 3 4 5 6
1
2
3
4
5
6
7
E
b
/
N
o
(
d
B
)
1 7/8 3/4 2/3 1/2 1/4
R 0 1 0 l o g 1 / R 0
基本概念
从图可以看出：当带宽,R0?0，得到
Eb/N0?1.4dB,信道编码所能达到的极限比仙侬极限差 3dB。
从图可以看出,若 R0?1,即不加任何信道编码，这时 Eb/N0，说明在有限信噪比情况下无法达到无差错传输。
从图可以看出：对于一定的 R0,相当于一定的带宽扩展率，存在一个有限的 Eb/N0,这时可以通过选择适当的 n达到任意低的差错率。
性能指标
编码率、编码效率、码率
编码增益
编码延时
编译码器的复杂度分类
根据码的规律性可分为：正交编码和检、纠错码
根据监督元与信息组之间关系可分为：分组码和卷积码
根据监督元与信息元之间关系可分为：线性码和非线性码
根据码的功能可分为：检错码和纠错码分类（续）
信道编码检纠错码正交编码分组码卷积码
m 序列
L 序列非线性码线性码恒比码群计数码非循环码循环码非系统卷积码系统卷积码正交码
W-A码岩垂码扩散码奇偶校验码汉明码
BCH码
RS码分组码
k k k k
k k k k
n
工作原理
图中,n? k,R＝ k/n,称为编码率。
分组码的基本原理是将信息码分成 K比特一组，然后将每组的比特数扩展成 n（ n? k）,也就是说在信息比特中插入 n-k个比特。
另一种看法：将 2k矢量空间映射到 2n矢量空间。
工作原理（续）
定义几个参数：
码重：一组二进制码中,1”的个数码距 d,二组二进制码之间,0”或,1”不同的位数
定理：
（ 1） 为检查出 e个错误，要求,dmin? e+1
（ 2） 为纠正 t个错误，要求,dmin? 2t+1
（ 3） 为纠正 t个错误，同时检查出 e个错误，要求：
dmin? e+t+1 （ e? t）
用图说明
A AB B
线性分组码 ----举例
奇偶监督码
汉明码
BCH码
RS码
CRC码奇偶监督码
采用奇偶校验原理。
只能检错，不能纠错。
只能检查出某一分组的单个错误或奇数个错误，
而不能发现偶数个错误。
最小码距为 2。
水平奇偶监督码
水平垂直奇偶监督码。
汉明 码
（ Hamming码）
是一种纠正单个错误的线性分组码。
特点,码长 n = 2m-1
信息码位 k = 2n-m-1
监督码位 r = n-k = m
最小码距 d = 3
纠错能力 t = 1
扩展的汉明码：将监督码位由 m增至 m+1,信息位不变，这时最小码距增加到 d = 4,能纠正 1位错误同时检查出 2位错误。
BCH码
（ Bose-Chaudhuri-Hocquenghem码）
是线性分组码中循环码的一种重要子类，有严密的代数结构，是目前研究较多、应用较广的一种线性分组码。
具有纠正多个随机错误的能力。
根据对纠错能力的要求，选择参数，并根据代数结构构造编译码算法。
如,n = 7,k = 4,t = 1;
n = 15,k = 7,t = 2;
n = 31,k = 16,t = 3;
n = 127,k = 50,t = 13。
RS码
（ Reed-Solomon码）
是一种非二进制的 BCH码。即：在（ n,k） RS码中，输入信息被分成 km比特一组，每组包括 k个符号，每个符号由 m比特组成。
纠正 t个符号错误的 RS码参数如下：
码长 n = 2m-1符号,或 m(2m-1)比特信息段 k符号,或 km比特监督段 n-k=2t符号,或 m(n-k)比特最小码距 d=2t+1符号,或 m(2t+1)比特
CRC码
（循环冗余校验码）
是一种循环码，用于检错。
具有很强的检错能力，而且编码器及译码器都很容易实现。因而在数据通信中得到广泛应用。
可以检测出的错误如下：
（ 1）突发长度?n-k的突发错误；
（ 2）大部分突发长度＝ n-k+1的错误；
（ 3）大部分突发长度?n-k+1的错误；
（ 4）所有与许用码组的码距?dmin-1的错误；
（ 5）所有奇数个随机错误。
卷积码概述
分组码?卷积码
固定窗型?滑动窗型
k k k k k k k k
n n n n n n n n
k k k k k k k k
n n n n n n n n
概述（续）
例,R＝ 1/2卷积码
k k k k k k k k
＋
＋
Ik
ak
bk
编码原理
原理图映射
u j0
u j1
u j,k-1
u j-m,k-1
u j-m,1
u j-m,0
x j0
x j1
x j,n-1
...
...
...
...
...
...
...
m stage delay
编码原理（续）
几个例子
+
+
u j
x j0
x j1
u j
x j0
x j1
(4)
(1)
+
(2)
x j0
x j1
u j
+
+
+
x j0
x j1
x j2
u j0
u j1
(3)
返回编码原理（续）
卷积码的参数
– 约束长度 N，
– 输入比特 k，
– 输出比特 n，
– 编码率 R＝ k/n
编码原理（续）
状态转移图和 trellis图表示
0110
11
00
1 ；1 0
1 ；0 1 0 ；0 1
0 ；1 0
1 ；0 0
1 ；1 1 0 ；1 1
0 ；0 0
0/00
1/11
0/00 0/00 0/00
1/11
1/11 1/11
1/01
0/10
1/10 1/10
0/01 0/01
1/00 1/00
0/11
0/11 1/00
0/100/10
00
10
01
11
1/00
译码原理 ----方法分类
代数译码：纠错译码的经典方法。利用纠错码的代数结构，经过一定的代数运算，消除误差，恢复正确的信息。常用的有：大数译码逻辑。特点：电路简单，
编码增益低。
概率译码：纠错译码的新方法。考虑到信道的统计特性。常用的有：序列译码、
维特比译码。特点：电路复杂，编码增益高。
译码原理 ----序列译码
原理,在码树图中每向前走一步，在决定走哪一个分支时根据该分支子码与该时刻接收子码之间的相似程度来判断。
亦称为逐分支译码。
一般采用对数似然值度量该相似程度
log P(R|C)=log?iP(ri|ci)=?ilog(p(ri|ci))
堆栈译码和费诺译码译码原理 ----序列译码（续）
优点
– 运算量和约束长度无关。
缺点
– 运算量和信道质量有关。
– 没有利用卷积码的记忆特性，不是最优算法。
译码原理 ----维特比译码
最大后验与最大似然译码
MAP:
ML:
硬判决和软判决硬判决：解调器直接判 0,1
软判决：解调器对输出进行量化
)|(m a xa r g~ iiSi SrfPS
i
)|(m a xa r g~ iSi SrfS
i
译码原理 ----维特比译码（续）
Viterbi译码原理
– Viterbi译码是建立在最大似然译码基础上的译码方法
– 在译码过程中只需考虑整个路径集合中那些能使似然函数最大的路径
– 最大似然序列译码要求序列有限，因此对卷积码来说，要求能收尾
1
0
)(~ )(~ ),(),( mL
j
i
jj
i
i xrxr
译码原理 ----维特比译码（续）
Viterbi译码举例
– 设对于编码前信息比特为 (0,0,0,0,0,0)的接收序列为则硬判结果为基于软判决时，采用如下路径度量
9.0,2.15.0,2.06.0,5.03.1,5.09.0,1.03.0,1.1~r
0,01,10,00,00,11,0~?r
)1()1(,)0()0(,,),( jpijpipij rxrxxr
译码原理 ----维特比译码（续）
1
1
1
2
2
3
2
1
3
3
2
2
3
3
2
3
2
2
2
3
3
3
00
10
01
11
基于硬判决的Viterbi译码
Trellis图译码原理 ----维特比译码（续）
0.8
0.2
0
1.6
-1.8
3.4
2.0
0.8
-0.8
3.8
5.2
2.2
2.6
4.5
2.3
2.1
1.9
5.9
4.3
4.9
5.5
00
10
01
11
-0.8
基于软判决的Vite rbi译码
Trellis图译码原理 ----维特比译码（续）
Viterbi译码的特点
– 维特比算法是最大似然的序列译码算法
– 译码复杂度与信道质量无关
– 运算量和存贮量都与码长呈线性关系
– 运算量和存贮量都与状态数呈线性关系
– 状态数随 k及 m呈指数关系
Turbo码产生背景
交织
– 块交织：行写入，列读出
– 卷积交织,L
L L
L L L
LL L L
LL L L L
0
1
2
3
W-2
W-1
入 出产生背景（续）
串行级联码
优点：性能较一般短码有很大改善
缺点：编码效率低；当 R/C → 1时性能迅速恶化外 码编 码内 码编 码 交 织 器信 息 数 据 编 码 输 出编 码 器内 码译 码外 码译 码 解 交 织接 收 信 号 译 码 输 出译 码 器产生背景（续）
软输入软输出和迭代译码对数似然比 LLR
)()()()()()(
)()()()|(
)1(
)1(
l o g
)1|(
)1|(
l o g
)|1(
)|1(
l o g)|()(
^^^
'
^
^
'
dLdLxLdLdLdL
dLxLdLdxL
dP
dP
dxP
dxP
xdP
xdP
xdLdL
ece
c
产生背景（续）
软输入软输出和迭代译码
Soft-in
soft-out
decoder
feedback for the next iteration
L e (d)
L' (d)L c (x)
L (d)
L(d),priori values
L c (x),channel values
L e (d),extrinsic values
L'(d),posterori values
output LLR = L e (d)+ L'(d)
返回编译码原理
编码原理编 码 器 1
编 码 器 2 交 织 器开 关单 元复接器编 码 输 出信 息 数 据编译码原理（续）
译码原理软 输出 译码 器
1
软 输出 译码 器
2
外 信 息 Z
1k
交 织交 织似然值L
1k
解交织信 息 符号 序 列校验序列y
2k
校验序列 y
1k
判决器译码输出似然值L
2k
外信息Z
2k
x
k
迭代译码几点说明
Turbo码具有优越性能的原因
寻找构造好码的规律（分量码构造，交织器构造等）
译码延时大，译码算法复杂
广泛应用于移动通信、军事通信、深空及卫星通信等
