具錯誤更正能力之二元算數碼其植基於格狀結構之疊代型循序式解碼

Trellis-Based Iterative Sequential Decoding of Error-Correcting Binary Arithmetic Codes

蔡承廷(Cheng-Ting Tsai)

指導教授 ： 黃育銘

國立暨南國際大學/科技學院/資訊工程學系/碩士(2009年)

摘要

具錯誤偵測/更正能力的算數碼(Error-Correcting Arithmetic Codes：ECAC)其編碼過程可用一個有限狀態機(Finite State Machines：FSM)來描述，並且定義出其相對應的格狀結構(trellis structure)。
文獻上，通常使用Viterbi演算法(Viterbi Algorithm：VA)，在格狀結構上對ECAC進行解碼。為了提升解碼效能，可以善用所有傳送端給予的額外資訊(side information)，但是所建構之格狀結構會變得相當龐大，造成解碼複雜度(Complexity)變高。為了降低解碼複雜度，我們延續[1]的結果提出ㄧ個植基於格狀結構之軟式決定循序式解碼(soft-decision sequential decoding)演算法，且利用文獻[2]蒙特•卡羅方法(Monte-Carlo Method：MC Method)的觀念，繼續改良我們所提出之解碼演算法，進而提出疊代型循序式解碼(Iterative Sequential Decoding)演算法。實驗結果顯示，我們所提出的解碼演算法，在通道環境不要太差的情況下，可以改善解碼效能，並且額外增加的複雜度也在可以容忍的範圍內。

關鍵字

具錯誤偵測/更正能力的算數碼 ； 簡化的有限狀態機 ； 蒙特•卡羅方法 ； 疊代型循序式解碼演算法

並列摘要

The encoding process of an error correction arithmetic code (ECAC) can be modeled as a finite state machine (FSM) and the corresponding trellis can be derived immediately from the FSM.
Viterbi algorithm (VA) is a common trellis-based decoding approach used to decode the ECAC. For increasing the performance, all possible side information, such as the number of totally transmitted symbols provided by the transmitter, must be taken into consideration for the construction of the corresponding trellis. However, the decoding complexity will become quite high due to the enormous number of trellis states. In order to decrease the decoding complexity, a low-complexity soft-decision sequential decoding algorithm was proposed in [1]. Continue on the study of this previous work and based on the Monte-Carlo concept of [2], we further propose an iterative soft-decision sequential decoding algorithm. For higher SNR, experimental results show that the proposed scheme has some significant improvements on performance while the increased complexity is insignificant.

並列關鍵字

ECAC ； Reduced FSM ； MC Method ； Iterative Sequential Decoding

參考文獻

[1] 蔡景竑, “A Study of Trellis-based Sequential MAP Decoding Schemes,” 國立暨南國際大學資訊工程研究所,碩士論文, Jul. 2008.

[2] L. Xu, M. W. Hoffman, and K. Sayood, “Hard decision and iterative joint source-channel coding using arithmetic codes,” DCC05, pp. 203-212, 2005.

[3] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Comm. ACM 30, Jun. 1987.

[4] C. Boyd, J. G. Cleary, S. A. Irvine, I. Rinsma-Melchert, and I. H. Witten, “Integrating error detection into arithmetic coding,” IEEE Trans. Comm. Vol. 45, pp. 1-3, Jan. 1997.

[5] M. Grangetto, P. Cosman, and G. Olmo, “Joint source/channel coding and MAP decoding of arithmetic codes,” IEEE Trans. Comm. Vol. 53, no. 6, pp. 1007-1016, Jun. 2005.