對於固定組成碼的有效率解碼演算法之研究

Efficient decoding algorithms for constant composition code

蔡議德(I-te Tsai)

指導教授 ： 張仁俊 ； 吳信龍

國立臺北大學/電機資訊學院/資訊工程學系/碩士(2010年)

摘要

在這篇論文，我們探討一種被稱為固定組成碼的編碼方式，為了將其應用於通道編碼，我們需要找出一個解碼技術以便於偵測或者更正資料在通道傳輸時產生的錯誤。
在2006年Chu、Colbourn、和Dukes 提供了一種利用保距映射(DPM)的方式建造固定組成碼的方式。在2009年Chang和Wu也提出了一個利用增距映射(DIM)的方式建造
固定組成碼的方式。
這些建造方式指利用一個已經存在的二進位碼映射出一個固定組成碼。利用保距映射所建造的固定組成碼，其漢明距離不會減少。而利用增距映射建立的固定組成碼，其漢明距離則會至少增加1或是達到碼句(codeword)的長度。
在這篇論文中我們分別對上面兩種方式建立的固定組成碼提出了有效率的解碼演算法。而且針對增距映射(DIM)的特點，另外提出了一個針對特定二進位碼建造的固定組成碼的解碼演算法。

關鍵字

固定組成碼 ； 保距映射 ； 增距映射 ； 編碼理論 ； 解碼

並列摘要

In this thesis, we study the code called constant composition code(CCC). For the purpose of application in channel coding, we need an algorithm to detect errors or correct errors.
In 2006, Chu, Colbourn, and Dukes propose a construction of CCC through a distance-preserving mapping(DPM).
In 2009, Chang and Wu propose a construction of CCC through a distance-increasing mapping(DIM).
These constructions use an existed binary code to construct a CCC. We can get a CCC with distance equal to the binary code through DPM or a CCC with distance increasing 1 through DIM.
In this thesis, we propose efficient decoding algorithms for the construction above. And propose another algorithm for the CCC through DIM from specific binary code.

並列關鍵字

constant composition code ； distance-preserving mapping ； distance-increasing mapping ； coding theory ； decoding

參考文獻

[1].Ryoh Fuji-Hara, Ying Miao, and Miwako Mishima, ”Optimal Frequency Hopping Sequences: A Combinatorial Approach”, IEEE Trans. on Inform. Theory, vol. 50, pp.2408–2420, Oct. 2004.

[2].N. Pavlidou, A.J.H. Vinck, J. Yazdani and B.Honary, ”Power line communications: state of the art and future trends”, IEEE Comm. Magazine, pp. 34–40, Apr, 2003.

[3].C. Ding, J. Yin, “Algebraic Constructions of Constant Composition Codes”, IEEE Trans. on Inform. Theory, vol. 51, no. 4, pp. 1585–1589, Apr. 2005.

[4].J. Yan, J. Yin, “Constructions of optimal GDRP s’ of type ”, Discr. Appl. Math., vol. 156, pp. 2666–2678, 2008.

[5].J.C. Chang, ”New algorithms for distance-increasing mappings from binary vectors to permutations by swaps”, Designs, Codes and Cryptography, vol. 39, pp. 335–345, Jan. 2006.