廣泛式分段整數對映的算術編碼及其整合式訊源/通道解碼

Generalized Piecewise Integer Mapping Based Arithmetic Coding and its Joint Source-Channel Decoding

張育豪(Yu-Hao Chang)

指導教授 ： 黃育銘

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

https://doi.org/10.6837/NCNU.2013.00131

摘要

算術碼是一種在資料壓縮方面有著較高效能的技術，所以被廣泛地採用在影像或視訊壓縮標準上。然而，較高的計算複雜度往往是算術碼所必須克服的瓶頸。分段整數對映算術碼是在編碼器與解碼器中消除所有的乘法運算，取而代之利用加法運算與比較的方式，雖然壓縮效能降了些，但可大大降低計算複雜度以提高編解碼速率。本論文首先提出廣泛式分段整數對映算術碼，增加了對映條件，進而提供較高的壓縮效能且維持幾乎相同編解碼速率。
　　接者探討分段整數對映算術碼及廣泛式分段整數對映算術碼本身的錯誤更正效能，及加入冗餘符號後的錯誤更正效能。其後連結著遞迴系統迴旋通道碼，探討疊代式解碼。整個系統架構採用低複雜度之SISO(soft-input soft-output)技術，其中算術碼是利用有限狀態機模式來描述，並使用格狀結構做解碼，且配合算術碼輸出位元長度會隨著輸入符號不同而有所改變，則使用了修改版SOVA演算法。
　　實驗結果顯示，分段整數對映算術碼及廣泛式分段整數對映算術碼不僅能消除所有乘法運算，使得計算複雜度能夠降低外，並具有些許錯誤更正能力，此外檔案壓縮效能有時反而會比整數型算術碼要來得好。加入冗餘符號的算術碼其錯誤更正效能明顯比沒有加入冗餘符號的算術碼來得高。此外對疊代式解碼作了EXIT chart分析。

關鍵字

算術碼 ； 分段整數對映 ； 廣泛式分段整數對映 ； 整合式訊源/通道解碼 ； 有限狀態機 ； SOVA演算法 ； EXIT chart

並列摘要

Arithmetic coding (AC) is an efficient data compression technique and widely adopted in image and video compression standards. However, the high complexity of arithmetic coding in computation is the bottleneck that many researchers endeavor to overcome. Piecewise integer mapping based arithmetic coding can eliminate all multiplicative operations in both encoder and decoder by the technique of replacing them with the operations of comparison and addition. It can reduce the computational complexity with a little penalty of compression loss. A generalized piecewise integer mapping arithmetic coding can provide higher compression efficiency with maintaining almost the same coding speed.
　　The iterative decoding to a communication scheme of which an arithmetic code with forbidden symbol is used for source coding and a recursive systematic convolutional code is used for channel coding. In this system, it adopts a low complexity SISO technique (called modified SOVA algorithm) for arithmetic coding, where arithmetic code can be modeled as a finite state machine and then can be decoded by using a trellis structure.
　　Experimental results show that the piecewise integer mapping based AC or the generalized piecewise integer mapping based AC can not only eliminate all multiplicative operations to lower down the computational complexity, but also owns a little capability of error correcting. Besides, the compression efficiency of it sometime becomes better than that of the traditional integer AC. In general, the integer AC with forbidden symbol will outperform the integer AC without forbidden symbol in terms of the error correcting performance.Furthermore, the EXIT chart is also presented for analyzing the iterative decoding.

並列關鍵字

Arithmetic coding ； Piecewise integer mapping ； A generalized piecewise integer mapping ； Joint Source/Channel Decoding ； Finite state machine ； Soft Output Viterbi Algorithm ； EXIT chart

參考文獻

[1] L. Stuiver, A. Moffat, “Piecewise Integer Mapping for Arithmetic Coding,” Proc. IEEE Data Compression Conference, 1998, pp. 3-12.

[2] Y.-M. Huang, C.-W. Chiou, “An Efficient Piecewise Integer Mapping Based Technique for Arithmetic Coding,” in Proc. International Conference on Informatics, Cybernetics, and Systems, Kaohsiung, IEEE Taipei Section, Dec. 2003.

[3] I. H.Witten, R. M.Neal, and J. G.Cleary, “Arithmetic Coding for Data Compression,” Communication of the ACM, Vol. 30, Jun. 1987.

[4] C. Boyd, J. Cleary, S. Irvine, I. Rinsma-Melchert, and I. Witten, “Integrating Error Detection into Arithmetic Coding,” IEEE Transactions on Communications, Vol. 45, pp. 1-3, Jan. 1997.

[5] A. Zribi, S. Zaibi, R. Pyndiah, and A. Bouallegue, “Low-complexity Joint Source/Channel Turbo Decoding of Arithmetic Codes,” Proceedings of 5th International Symposium on Turbo Codes and Related Topics, pp. 385-389, Sept. 2008.