ˆ= argmax{P(ci | y )} c
c i ∈C
最大似然译码
ML (Max. Likelihood) 译码
v 后验概率与似然函数 P(y | ci ) 的关系是：
P (ci , y ) P(ci ) P (ci | y ) = = P (y | ci ) P(y ) P (y )
v 当编码器的输出先验等概，即P(ci )是一个与 ci 无 关的常数时，给定y条件下，使 P(ci | y ) 最大的ci ∈ C 也必然使 P(y | ci ) 最大。
生成序列
g1(1) = (11) , g1(2) = ( 01) , g1(3) = (11) g
(1) 2
= ( 01) , g
(2) 2
= (10 ) , g
(3) 2
= (10 )
（3，2，2）卷积码
故有
g1(1) = (11) , g1(2) = ( 01) , g1(3) = (11)
(1) (2) (3) g2 = ( 01) , g2 = (10 ) , g2 = (10 )
卷积码编码
ci( n −1)
ci( n − 2)
并 串 变 换
编码输出 速率为 Rc =Rb×n /k
ui
串 信息序列输入 并 速率为 Rb 变 换
( k −1)
ui
( k − 2)
…
ci = f ( ui , ui −1 ,L , ui − m )
…
ui
k −1)
( 0)
ci
k −2)
( 0)
ui = ui(
最大似然译码
因此，最佳的译码方法也可以是译为似然函数 最大者，这一原则叫ML准则。 ML译码可以表示为：
ˆ= argmax { P ( y | ci )} = argmax {ln P ( y | ci )} c
ci ∈C ci ∈C
离散无记忆信道中，ML准则变为对数似然函 数累加值最大
v 卷积码上如何用？
树根
a
11 11 10
a
c
00
b
01
01
b
11 01 01
c d
11
a b
c
00 01
d
10
d
10
树图
优点：
v 时序关系清楚； v 对于每个不同的信息输入序列都有一个唯一的不重 复的树枝结构相对应；
缺点：
v 进行到一定时序后，状态将产生重复且树图越来越 复杂。
网格图
综合了树图和状态图的优点：
v 状态图：结构简单； v 树图：时序关系清晰。
c (1) = (1 + x 2 + x 3 + x 4 )(1 + x 2 + x 3 ) c (2) = (1 + x 2 + x 3 + x 4 )(1 + x + x 2 + x3 ) = 1 + x + x3 + x 4 + x 5 + x 7 = (11011101) = 1 + x = (10000001)
(
, ui(
,L , ui(
0)
)
ci = ci( n −1) , ci( n − 2) ,L , ci( 0)
(
)
卷积码的表示方法
解析表示法
v 离散卷积法 v 生成矩阵法 v 码多项式法
图形表示法
v 状态图法 v 树图法 v 网格图法
卷积码的解析表示法
（2,1,4）
(1) g0
ci(1)
g1(1)
101 011 c = u gG = (110110 ) = (110 000 001 111)
111 100 101 111 011 100 101 011
111 100
生成矩阵的构成规律
每一行的分组数，即码组数，取决于记忆单元 数，即移位器节数加1； 每一码组中的码元数取决于并行输出位数； 矩阵中并行的行数取决于并行输入的位数； 矩阵中的总行数取决于输入位置序列的长度；
提纲
概念 卷积码编码
v 解析 v 图形
卷积码译码 纠正突发错误
有记忆与无记忆编码
无记忆编码
v 输出ci只取决于第i个输入ui，而与以前的输入 {L, ui −2 , ui −1} 无关；
有记忆编码
v 编码器的输出不仅和现在的输入有关，还和过去的 m个(寄存器个数)输入有关； v 有记忆编码记作(n,k,N)码，称N为记忆深度(约束长 度)； （是否有记忆是相对的概念） v 卷积码是有记忆编码。
g1(1) g1(2) (1) (2) g0 g0
L
L
L
(1) (2) g3 g3 L L
生成矩阵
编码方程写为矩阵形式
c = u gG
若 u = (10111) , g (1) = (1011) , g (2) = (1111)
生成矩阵
得到编码输出为
11 01 11 11 11 01 11 11 c = u gG = (10111) 11 01 11 11 11 01 11 11 11 01 11 11 = (11 01 00 01 01 01 00 11)
状态图
状态转移图：
11 01 01
状态之间带箭头的连线 叫一个分支或者叫一个 支路，代表状态的迁移。
11 10
00
00
10
00
实线分支表示输入“ 0” 引 起的状态迁移； 虚线分支表示输入“ 1” 引 起的状态迁移。 分支旁边的数字表示这 个分支对应的编码输出。
11
10
01
输入1 输入0
树图
卷积码编码器的状态变化过程也可以用树图来 描述。 树图中的每个节点代表编码器的状态； 连接两个节点的一段树枝表示一个分支； 编码器的初始状态对应图中的“ 树根” ； 每个时刻到来时，编码器的状态将根据信息比 特是“ 1” 还是“ 0” 沿这颗树向下或者向上移动 树枝上标注的数字是编码器对应的输出。
一般结构
１ 输入 １ ｋ ２ Ｎ-1
输出
１
ｎ
卷积码编码器
包括
v 一个由N-1段组成的输入移位寄存器； v 每段有k个，共(N-1) k个寄存器； v 一组n个模2和相加器； v 一个由n级组成的输出移位寄存器； v 对应于每段k个比特的输入序列，输出n个比特； v 当k=1时，N-1（或K-1）就是寄存器的个数 。
最大似然译码
在BSC信道中
( v 信道的正确率是 P ( y
v 信道无记忆：
i i v 信道的错误率是 P yl ≠ cl | cl = p（p<1/2）； l i l i l
状态图
以（2，1，3）为例
ci1
ui
si1
输入速率为Rb
(ui )
(s )
1 i −1
si2
(s )
2 i −1
T D M
ci2
输出速率为Rc＝２Rb
状态图
共有4种不同的状态：00、01、10、11 。 如果初始状态给定，那么随着输入的变化，状 态也在不断变化。 例如：在编码器的状态是00的时候，若输入比 特“ 1” ，则状态将转移到10，同时编码器将输 出11。
树图
00 00
a b c d a b c d a b c d a b c d
10
a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d
a
11 10
a
00 11
b
01 11
a
11 00 10
c
00 01
b
01
d
10 00 11 10
最大似然译码
最大后验概率（MAP）准则
v 后验概率 P (ci | y ) ：在观察到y的情况下时，所判断 的发端发送 ci的概率。 v 第i个译码器译错的概率为：
1 − P ( ci | y )
v 给定y后错误率最小的方法就是总选择后验概率最 大的那个，这一原则叫MAP（Max. A Posteriori） 准则；
离散卷积
编码方程
c
(1)
=u*g
(0)
(1)
c (0) = u * g (0) c = (c , c )
(1)
其中“ *” 表示卷积运算
ci = ∑ ui − j g j
j =0 m
离散卷积
脉冲冲激响应至多可维持到
K = m + 1 = 3 + 1 = 4 位；
冲激响应可以写为：
g (1) = (1011) g (0) = (1111)
用实线表示输入为“ 0” 时所走的分支； 用虚线表示输入为“ 1” 时所走的分支； 尾比特
网格图
a a b a b c d a b c d
00 11 10 01 11 01 11 10 10 01 11 00
a b c d
a b c d
a
a
c
a b c d
00
输入0 输入1
00
01
例：u=1011100
若输入序列为
u = (1011100 )
写成多项式形式
u = 1 + x2 + x3 + x4
由图可知码生成多项式为
g (1) = 1 + x + x 2 g ( 2) = 1 + x 2
（2，1，3）卷积码
则输出码序列可写成
c(1) = (1 + x 2 + x 3 + x 4 )(1 + x + x 2 ) = 1 + x + x4 + x6 c( ) = (1 + x 2 + x 3 + x 4 )(1 + x 2 )