Forney Factor Graph – Simple FEC (part 2)

by allenlu2007

前文用 FFG 來 decode FEC,主要重點

1. forward and backward message passing to compute 所有 marginal probability

2. Iterative the message passing: probability 可以收歛 (desire case: probability 收歛到 0 or 1. 但也有可能收歛到 0.5!

為什麼需要 iteration? 如果是 Y=(0, 0, 1, 0), 一次的 message passing 就相當正確判斷 codeword 是 (0, 0, 0, 0). 其實可以不用 iteration.  但在某些 initial condition (e.g. Y=(0, 0, 1, 1) 或是 graph structure (loop?), 一次的 message passing 無法判斷valid codeword, 更不用說收歛。藉著 iteration, 可以讓 probability 收歛。

3. 如果有必要,initial probability 加上 perturbation 可以破壞對稱性而幫助 probability 收歛。

最大的問題是不管 max-product 或 sum-product with iteration 即使收歛也並不保証收歛到 valid codeword!

因此是否有其他的 algorithm 可以保確收歛到 valid codeword.  答案是肯定的,就是用 state transition graph or trellis graph/diagram.  

 

State Transition Graph

以 Hamming code (7, 4) 為例。對應的 parity check matrix 如下。

NewImage

H 對應的 valid trellis diagram and sequence state transition graph 如下圖。暫時先不管下圖如何產生。

NewImage

State transition graph 也是一個 FFG.  Variables 包含 X1, X2, .. X7, and S1, .. S6.

S1, S2, … S6 代表 states:  S1 and S6 只有兩個 states {0, 1}, S2/S3/S4 有四個 states {0, 1, 2, 3} (由下而上編號)

Factors 包含 f(X1, S1), f(S1, X4, S2), f(S2, X3, S3), f(S3, X2, X5, S4), f(S4, X6, S6), f(S6, X7).

f(X1, S1) = 1 if (X1, S1) = (0, 0) or (1, 1);  else 0

f(S1, X4, S2) = 1 if (S1, X4, S2) = (0,0,0), (0,1,2), (1,0,3), (1,1,1); else 0

f(S2, X3, S3) = 1 if (S2, X3, S3) = (0,0,0), (0,1,1), (1,0,1), (1,1,0), (2,0,2), (2,1,3), (3,0,3),(3,1,2); else 0

f(S3, X2, X5, S4) = 1 if (S3, X2, X5, S4) = (0,0,0,0),(0,1,1,2),(1,0,1,1),(1,1,0,3),(2,0,0,2),(2,1,1,0),(3,1,0,1),(3,0,1,3); else 0

f(S4, X6, S6) = 1 if (S4, X6, S6) = (0,0,0), (1,1,0), (2,1,1), (3,0,1); else 0

f(S6, X7) =1 if (0,0) or (1,1); else 0

Total branches = 8+8 = 16 = 2^4 matches with 2^4 codeword space! 

In summary,  state transition graph 的 FFG 是 chain structure; 和前文由 H generation matrix 直接產生的 web structure FFG (Tanner graph?) 不同。目的是 always decode valid codeword.   How to do it?

 

Channel Model

Chanel model 的方式和前文相同,分為 memoryless 或同樣有 state-space channel models 如下圖。

 NewImage

NewImage

很明顯如果是 memoryless channel, 結合 FEC state transition graph 和 memoryless channel graph 的 combined FFG 變成一個 Hidden Markov Chain (HMM).

如果是 state-space channel model (e.g. partial response channel or ISI), 則變成 dual chain 的 FFG.  BTW, dual chain 存在 loop, 只有近似解。

本文只考慮 memoryless channel. 理論上 HMM 的 algorithm 都可以用在解 state transition graph/trellis graph.

最終是要算出 P(branch | Y1, Y2, ..Yn) = P(b|y) 而得到 valid codeword.  

It is proved by Wiberg that:

Using sum-product to compute trellis graph P(b|y):  BCJR algorithm

Using max-product to compute trellis graph P(b|y): soft output Viterbi algorithm (SOVA)

 

Recap Baum Welch Algorithm (1963)

NewImage

Baum Welch algorithm 是一種 EM (expectation maximization) algorithm.  在 (A, B, Pi) unknown 情況下,given Y1, Y2, .. Yt, 找出最有可能的 (A, B, Pi).   EM algorithm 的 iteration, 就是在增加 likelihood.

表面上 Baum Welch algorithm 和 trellis decode 不同。在 trellis graph, A 是 given by trellis structure (如上圖), either 0 or 1.  BCJR 卻發現 Baum Welch algorithm 其實可以用在 trellis decoding.  

Iterative decoding 就如同 EM 的 iteration (?)  似乎 No!

EM algorithm is equivalent to Iterative decoding?  似乎No!

BCJR and Baum-Welch algorithm 相同嗎? 似乎 No!

 

Algorithm summary (from Wiki)

NewImage

 

 

BCJR Algorithm Review (1974)

BCJR 是用於 trellis code decoding, 主要是 convolution code, trellis code modulation, 但如前文討論,也可用在 linear block code decoding.  For practical reason, BCJR never have been adopted as widely as Viterbi algorithm (VA).

Con:

* Lots of computation (product and sum) compared with VA.  VA only needs to add-compare-select (ACS).

* VA only need “forward only” and store a path history of each survivor.  This is particularly useful for real-time communication purpose.

* VA does not need to know the SNR.  BCJR needs to know SNR a prior.  

* Linear block code decoding 一般是用 linear algebra based computation (syndrome calculation, etc.) 而不用 trellis based algorithm.  

 

以下節自 Abrantes’s “From BCJR to Turbo Decoding

首先 encoder/channel/decoder model

NewImage

再來是 prior and post probability

NewImage

NewImage

NewImage 

Key 是 log-likelihood ratio L.  可以証明 (by using Markovian property) 

NewImage

NewImage

NewImage

NewImage

NewImage

比較 BCJR and Baum-Welch

Alpha

BCJR: alpha(k-1)(s’) = P(s’, y<k)

BW: alpha(t)(i) = P(Xt=i, Y1, … Yt)

基本上相同,但 BCJR 往前一個 time step

 

Beta

BCJR:  beta(k)(s) = P(y>k | s)  

BW:  beta(t)(i) = P(Yt+1, … YT | Xt = i)

相同的定義

 

Gamma

BCJR: r(k)(s’, s) = P(yk, s | s’)

BW: P(Xt=i | Y)  

gamma 在 BCJR 和 BW 的定義完全不同。

BCJR 基本上把 Y1, Y2, … YT 拆成三份: 1.. (k-1) (Alpha), k (Gamma), (k+1), … T (Beta)  是 branch metrics.

BW 基本上把 Y1, Y2, …, YT 拆成兩份: 1..t (Alpha), and t+1, …, T (Beta); Gamma 比較像 temporary variable.

 

 

NewImage

注意只有 recursive (traverse the Markov chain), 並沒有像 EM 的 iteratively update!

 

Numerical Examples

Convolution code with code rate 1/2, 4 states, and the trellis graph shown below.

NewImage

NewImage

Ec/No = 1dB (SNR).  

順序是先 forward pass, 用 Gamma 來算 Alpha, 等到 forward pass is done, start backward pass for Beta.

NewImage

 

NewImage 

NewImage 

NewImage 

計算完所有的 P, 下一步就是算 L(uk | y).

NewImage

 

 

BCJR (or MAP) Summary

1. BCJR is strictly based on the trellis graph.  因此不會 decode 出 invalid codeword!

2. BCJR needs to know the SNR to compute Lc (?) 如果 SNR  is unknown 會有問題嗎?

3. BCJR needs lots of product and summation computation.

4. BCJR needs to do forward and backward, cannot be used for real-time computing.

NewImage

因些很少用在實際應用上。Solutons:

Use log to replace product -> log-MAP algorithm

NewImage

 

Use max function to approximate ->  max-log-MAP algorithm (Viterbi? Some yes, some No)

NewImage

Use max-product (and log) instead of sum-product (MAP) -> Viterbi algorithm (VA)

Store forward pass and not use backward -> VA

Without the need of SNR, maximizes r*v -> VA

VA 完勝 BCJR on the trellis decoding!

 

Q: Difference between VA and SOVA

A: VA is only forward and store.  SOVA does both forward and backward.  Reference

 

Q: Why BCJR?  

A: The MAP (per bit) for trellis decode.  Performance 會比 VA or SOVA 好? Reference 

傳統的 turbo decoding 的演算法則是由 Bahl,Cocke,Jelinek,及 Raviv 所提出之
所謂 BCJR 演算法。BCJR 演算法主要觀念在解一個最大事後機率(MAP)檢測問
題,因此基本上 BCJR 演算法就是一個 MAP decoder。BCJR 演算法運用到 turbo
decoding 的運作方法是利用事後機率來判斷個別 bit 應該隸屬於 0 或是 1,然後
再重建整個原來的資料序列,這一點與 Viterbi decoding 找一條最相似的的資料
序列作為原來的資料序列的解碼方式不同,由於 BCJR 演算法是找一個最佳 bit
的解碼方式,因此就平均的位元錯誤率(BER)來講 BCJR 演算法會比 Viterbi
decoding 來的好。然而,由於 BCJR 演算法的複雜度太高(詳細 BCJR 演算法請看
參考文獻一)不利於硬體實現,因此一些化簡的動作是必須的。
最常的化簡的動作可以歸納成以下 5 個規則如下:

1. 使用 likelihood ratio 取代在 trellis 中的機率值。
2. 分別在 likelihood ratio 或是機率值上取”log”值,如此一來

NewImage

3. 只考慮最鄰近的 trellis path。也就是 max* –> max
4. 在計算時只考慮部分的 trellis path。
5. 因為 BCJR 演算法必須全部的 codeword 接收後才能進行解碼,可以設定 window長度來解碼。

 

規則 1 與規則 2 並不會傷害 soft-information,然而規則 3、規則 4
與規則 5 可能就會降低整個系統效能。

如果我們採用規則 2 與規則 5 來簡化 BCJR 演算法則稱為 MAP 演算法,若我們
更進一步加入規則 3 來簡化 MAP 演算法則我們可以得到 Max-Log-MAP 演算法。

 

 

 

 

 

 

 

 

 

Advertisements