植基於位元/格狀結構之整合式霍夫曼及迴旋循序解碼演算法

Bit- and Trellis- Based Joint Huffman and Convolutional Sequential Decoding Algorithms

吳威怡(Wei-I Wu)

指導教授 ： 黃育銘

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

摘要

Shannon的分離理論(separation theory)指出，若訊源編碼與通道編碼都分別最佳化之下，整體系統效能可達到最佳。然而，由於系統複雜度(complexity)與系統延遲(delay)時間的限制，分離式解碼的效能往往無法達到理論上的最佳值。為改善分離式解碼的效能，在解碼過程中，可有效善用壓縮過後所殘留的剩餘資訊(residual redundancy)，並且利用訊源(source)事前資訊與通道(channel)的統計資訊，僅用單一解碼器，即能同時進行訊源解碼及通道解碼，這種解碼技術文獻上稱作整合式訊源/通道解碼(Joint Source -Channel Decoding; JSCD)。
傳統Viterbi解碼演算法所採用之格狀圖(trellis)，當所有可用之訊源或通道資訊均予以考量時，往往所建構出的格狀圖相當龐大。雖然解碼效能可達到最佳，但其解碼複雜度相當高，因此顯得非常不實用。本論文?堙A首先推導出新的最大事後機率(maximum a posteriori probability; MAP)衡量值(metric)以簡化衡量值的計算，接著提出一個植基於位元/格狀結構之最佳整合式循序解碼演算法及一個次佳的方法。根據實驗顯示，該次佳方法不僅明顯降低了解碼的複雜度，同時其解碼效能與最佳方法幾近相同。

關鍵字

整合式訊源通道解碼 ； 霍夫曼碼 ； 迴旋碼 ； 格狀圖 ； 循序式解碼

並列摘要

According to the Shannon’s separation theory, the performance of the overall system is optimal while the source coding and the channel coding are separately optimized. However, due to the constraints on complexity and delay, the performance of separate decoding is usually not optimal. In the past, in order to further improve the performance of separate decoding, the residual redundancy left after compression, the source priori information, and the channel statictical information are exploited and fully utilized for presenting a so-called joint source-channel decoding (JSCD) scheme.
In tradition, the trellis adopted in Viterbi decoding algorithm will become tremendously large while all the source and channel information are utilized. Although the decoding performance is optimal, the decoding complexity becomes quite expensive. Therefore, it is not practical. In this work, a new maximum a posteriori probability (MAP) metric with lower computational complexity is derived first, and then we propose a bit- and trellis- based jointly sequential decoding algorithm along with a suboptimal solution. Simulation results indicate the suboptimal method can provide nearly the same performance as optimal scheme while exhibiting a significantly lower complexity.

並列關鍵字

joint source-channel decoding ； Huffman code ； convolutional code ； trellis ； sequential decoding

參考文獻

[1] C. E. Shannon, “A mathematical theory of communication,” Bell Sys. Tech. J., vol. 27, pp. 379–423, July 1948.

[2] J. L. Massey, “Joint source and channel coding,” in Communication System and Random Process Theory, NATO Advanced Studies Institutes Series E25, pp. 279-293. Sijthoff & Noordhoff, Alphen aan den Rijn, The Netherlands, 1978.

[3] J. Hagenauer, “Source-controlled channel decoding,” IEEE Trans. Commun., vol. 43, pp. 2449-2457, Sept. 1995.

[4] K. Lakovic, J.Villasenor, and R. Wesel, “Robust joint huffman and convolutional decoding,” in Proc. of the IEEE VTC, Sep. 1999, pp. 2551–2555.

[5] A. H. Murad and T. E. Fuja, “Joint source-channel decoding of variable-length encoded sources,” in Proc. ITW, Killarney, Ireland, Jun. 1998, pp. 94–95.