βk-1(s)≡P(Y/sk?1?s?)=?P(sk?s,Yk/sk?1?s?)
sNkN
=?P(sk?s,Yk,Yk?1/sk?1?s?)
sN =?P(Yk,sk?s/sk?1?s?)P(Yk?1/sk?s,sk?1?s?,Yk)
sN =?P(Yk,sk?s/sk?1?s?)P(YsNk?1/sk?s)（由马尔克夫性）
=??k(s)?k(s?,s)
sd) 联合概率的推导
???P(uk?1,YN)??p(sk?1?s,sk?s,YN)
s?,suk?1
??N=?p(sk?1?s?,sk?s,Yk?1,Yk,Yk?1)
s?,suk?1???N????=?p(sk?1?s,Yk?1)p(sk?s,Yk/sk?1?s,Yk?1)p(Yk?1/sk?s,Yk,sk?1?s,Yk?1)
s?,suk?1??N=?p(sk?1?s?,Yk?1)p(sk?s,Yk/sk?1?s?)p(Yk?1/sk?s) （由马尔克夫性）
s?,suk?1
=??k?1(s?)?k(s?,s)?k(s)
s?,suk?1e) 后验概率的推导 L(uk/YN)≡ln
P(uk?1/YN)P(uk?1,YN)? ?=ln
P(uk??1,YN)P(uk??1/YN)s?,suk?1??k?1(s?)?k(s?,s)?k(s)
= ln
s?,suk??1??k?1(s?)?k(s?,s)?k(s)f) α0(s)、βN(s)的初始化问题 因为卷积码编码的初态为零，所以
??0(0)?1 s0?0???(s)?0,?s?0?0??(0)?1若卷积码归零，则sN?0??N
??N(s)?0,?s?0
若卷积码不一定归零，则sN任意??N(s)?state_num表示卷积码的状态数。
g) 信息的输出 软判决输出：Lk(uk)output1?s
state_num??Lk(uk/YN)?Lcyks?Lk(uk)in，
用于本解码器的外信息输出，经过交织或者反交织传递给下一个解码器，并作为下一个解码器的先验信息的输入。
?硬判决输出：uk=sign(Lk(uk/YN)) 是硬判决的双极性比特，其中sign表示取符号。
从MAP算法的推导可知，马尔可夫性是其算法成立的前提和核心。对于任何满足马尔可夫性的编码方法，MAP算法都可以适用。MAP算法又称为BCJR算法（BCJR是四个算法发现者名字的首字母）或者前向-后向（Forward-Backward）算法。 4.1.2
Log_MAP算法：
与MAP算法等效，只是将α、β、γ转移到对数域中计算，并将乘法运算映射为加法运算，加法运算映射为E运算，便于硬件实现。
(1) 引入映射f: y=lnx
f(2) ?,?,?????L,?L,?L
(3) ×→＋ (4) ＋→E (5) E运算的定义：
a E b≡ln(ea+eb)=max(a,b)+ln(1+e?a?b)
E运算与加法运算一样满足交换律和结合律，所以： 分支转移概率为： γk (s’, s)=ukL(uk)/2?Lc(ukyks?xkpykp) 2前向概率的递推为：
αk(s)=E(?k?1(s?)??k(s?,s))
s?后向概率的递推为： βk-1(s’)= E(?k(s)??k(s?,s))
s?后验概率为：
L(uk/YN)≡E(?k?1(s?)??k(s?,s)??k(s))?E(?k?1(s?)??k(s?,s)??k(s))
s?,suk?1s?,suk??1 4.1.3 运算。
a E b≡ln(ea+eb)=max(a,b)+ln(1+e所以，定义a E b = max(a,b)。
Max运算与加法运算一样满足交换律和结合律，用它取代Log_MAP算法中的E运算即改造成Max_Log_MAP算法。
所以，
分支转移概率为： γk (s’, s)=ukL(uk)/2?Lc(ukyks?xkpykp) 2?a?bMax_Log_MAP算法：
Max_Log_MAP算法是Log_MAP算法的简化，原理完全相同，仅仅简化了E
?? a E b ≈ max(a,b) )???a?b??0前向概率的递推为： αk(s)=max(?k?1(s?)??k(s?,s))
s?后向概率的递推为： βk-1(s’)= max(?k(s)??k(s?,s))
s?后验概率为：
L(uk/YN)≡max(?k?1(s?)??k(s?,s)??k(s))?max(?k?1(s?)??k(s?,s)??k(s))
s?,suk?1s?,suk??1软判决（外信息）输出为：
?sLk(uk)?Lk(uk/YN)?Lcyk?Lk(uk)in
Max_Log_MAP解码算法的计算复杂度降低了，但差错性能（误码率和误块率）也变差了。这是由于Max_Log_MAP解码算法的外信息存在高估（over_estimate）问题，亦即Max_Log_MAP的外信息的绝对值通常高于Log_MAP的外信息的绝对值。为了缓解这一问题，可以将上述的外信息乘以一个常数η，
0<η<1，所以：
Lk(uk)new=ηLk(uk)
通过仿真，我们发现一个合适的η推荐值为3/4，这个值特别适用于二进制的硬件实现：
Lk(uk)new=Lk(uk)- Lk(uk)/4
除4可以用二进制的右移两位操作来实现，这样多增加一个简单的加减法操作就可以很好地改善Max_Log_MAP算法的性能。
4.2 SOVA算法
4.2.1
SOVA算法推导：
Lc(ukyks?xkpykp)) 2a) 转移概率的推导（同上文）
?k(s?,s)?exp(ukL(uk)/2)exp(b) 度量概率的推导 ??P(Yk,s?,s)?P(Yk?1,s?)P(Yk,s/s?)
?Mks?(s)?Mk?1(s)?ln?k(s?,s)?Mk?1(s)?ukL(uk)/2?Lc(ukyks?xkpykp) 2c) 度量概率的选择
如图2-6所示，k时刻s状态的度量概率为Mk(s)?max{Mks?(s),Mks??(s)}, 其中，度量最大者称为幸存路径，余者称为伴随路径。
计算度量差?sk?Mks?(s)?Mks??(s)
那么对k时刻s状态正确选择幸存路径的概率为:
??max{P(Yk,s?,s),P(Yk,s??,s)}?? Pks(right)?P(Yk,s?,s)?P(Yk,s??,s)?Pks(right)?exp(?sk)/(1?exp(?sk))
计算k时刻s状态的后验概率为：
?sLk(uk/Yk)?uk?sk （uk为幸存路径的编码比特） d) 后验概率的更新策略
采用维特比解码通过回溯找到ML(最大似然路径)，设其k时刻的状态为sk，编码比特为uk，则k时刻的后验对数似然比概率为：
?Lk(uk/Yk)?uk?skk
但是上式的判断过于乐观，存在似然值高估的问题。 因而采用如图所示的更新策略。
?Lk(uk/YN)?uk?i?k,k?1,,?,k??iuk?ukmin?sii
其中，δ是解码延时窗。从i时刻(i∈[k+1,k+δ])的最大似然路径上的伴随路径
i分支分别问题回溯，如果得到的k时刻的编码比特uk与k时刻最大似然路径上的信
?息比特uk不同，则取其中度量差的最小值更新Lk(uk/YN)。
sk sk+1 sk+2 sk+3 ?0k ?0k?1 ?0k?2 ?0k?3 ?1k?3 ?3k?3
sksk+1sk+2sk+3?0k?0k?1?0k?2?0k?3?1k?3?3k?3
图2-8 更新策略图
以图2-8为例，假设最大似然路径为全零路径，解码延时窗δ=3 ，网格图上的实线表示输入信息比特为-1，虚线表示信息比特为1。从k+1时刻最大输入路径的伴随式路径回溯到k时刻的信息比特是1，与k时刻的最大似然路径上的信息比特-1不同，所以相应的度量差是?0k?1需要进行比较：而从k+2时刻最大似然路径的伴随路径回溯到k时刻的信息比特是1，与k时刻的信息比特相同，所以不需比较。同理，从k+3时刻回溯的信息比特是1，也不相同，所以相应的度量差?0k?3也需要进行比较。综上上述，更新的度量差应取{?0k,?0k?1,?0k?3}中的最小值，后验
?概率的输出似然比Lk(uk/YN)为：
?Lk(uk/YN)?ukmin{?0k,?0k?1,?0k?3}??min{?0k,?0k?1,?0k?3} SOVA软判决（外信息）输出为：
?sLk(uk)?Lk(uk/YN)?Lcyk?Lk(uk)in