臺灣博碩士論文加值系統

本論文將探討如何從循環碼(cyclic code)中建構循環置換碼(cyclically permutable code, CPC)。近年來循環置換碼越來越重要，它可應用於通信網絡，光纖通訊與影像處理中，例如多重存取碰撞於無反饋渠道，跳頻擴頻通信通道，光正交碼與數位浮水印等。循環碼是區塊碼且滿足任何碼字(codeword)經由循環位移(cyclic shift)所產生的碼字仍然是此循環碼的碼字。而長度 的循環置換碼的定義就是那些擁有循環階數(cyclic order)為 的字碼且碼字循環位移後所產生的這些 個碼字只能在循環置換碼中出現一次。本論文之精神將探討如何透過循環碼之特性與有限場傅立葉轉換(Galois field Fourier transform, GFFT)，從循環碼中有效地建構出循環置換碼。我們提出了使用伽諾瓦場傅立葉轉換的兩個概念:共軛特性和位移特性，使用頻域編碼的方法來建構循環置換碼。我們已經分析從(7,4,3)與(17,9,5)循環碼去建構循環置換碼，藉由此將建構出任何長度為質數之循環置換碼。也將以(15,11,3)與(21,12,5)循環碼建構出循環置換碼為例，建構出任何長度為合成數之循環置換碼。我們的目標是希望在循環碼中，利用頻域編碼或時域編碼中找出一套有效且快速的方法來建構循環置換碼並且將此碼應用於通信網絡，光纖通訊與影像處理中。

In this study, we investigates the construction of cyclically permutable code (CPC) from a cyclic code. In recent years, the cyclically permutable codes have become increasingly important and have been applied in the communication network, optical communication, and image processing, such as multiple access collision channels without feedback, frequency-hopping spread spectrum communication channels, optical orthogonal codes, and digital watermarking. A cyclic code C is a linear block code such that any cyclic shift of a codeword in C is another codeword in C. A CPC of length n is a block code such that each codeword has full cyclic order n and all codewords are cyclically distinct.
The main theme of this stydy is to construct a CPC from a cyclic code using the Galois field Fourier transform (GFFT).we used the conjugate property and translation property of GFFT, and then use the frequency-domain encoding of a cyclic code to find a CPC. In this study, the results of the construction of a CPC from the cyclic codes (7,4,3) and (17,9,5) will be used to show how to construct a CPC with prime length. Similarly, the results of the construction of a CPC from the cyclic codes (15,11,3) and (21,12,5) will be used to show how to construct a CPC with non-prime length. Our main goal of this study is to find a systematic and efficient algorithm to find a CPC from a cyclic code, and then apply these CPCs to the communication network, optical communication, and image processing.

目錄
摘要 ii
Abstract iii
圖目錄 vi
Chapter 1 前言 1
Chapter 2 簡介 3
2.1 線性區塊碼 4
2.1.1線性區塊碼介紹和圖解 4
2.2 漢明距離及漢明權重 7
2.2.1最小漢明距離 7
2.2.2 漢明權重 8
2.2.3 錯誤更正與偵錯能力 10
2.3循環碼與循環置換碼 12
2.3.1循環碼 12
2.3.2循環置換碼 13
Chapter 3 伽諾瓦場傅立葉轉換 15
3.1伽諾瓦場 15
3.1.1 質數伽諾瓦場 16
3.1.2 擴張伽諾瓦場 17
3.2 共軛組與循環碼造碼 18
3.2.1 共軛組 18
3.2.2 藉由共軛組建構循環碼 21
3.3伽諾瓦場傅立葉轉換 23
Chapter 4 於循環碼中提出循環置換碼 26
4.1利用伽諾瓦場傅立葉轉換造循環碼 27
4.2 使用伽諾瓦場傅立葉轉換於循環碼中提出循環置換碼 29
4.2.1方法一、當循環碼長n為質數且為原始長度 29
4.2.2方法二、當循環碼長n為質數且為非原始長度 31
4.2.3方法三、當循環碼長n為非質數且為原始長度 34
4.2.4方法四、當循環碼長n為非質數且為非原始長度 37
Chapter 5 結論 40
參考文獻 41

[1] L. Gyorfi, I. Vajda. “Constructions of protocol sequence for multiple access collision channel without feedback,” IEEE Trans, on Inform. Theory, 1993, 39(5): 1762-1765.
[2] W. W. Peterson and E. J.Weldon, Jr., Error-Correcting Codes. Cambridge, MA: MIT Press, 1972.
[3] I. Cox, M. Miller, J. Bloom, J. Fridrich, and T. Kalker, Digital Watermarking and Steganography, 2nd ed. San Mateo, CA: Morgan Kaufmann, 2007.
[4] Mitekin, V.A., Timbay, E.I., ``A New Watermarking Sequence Generation Algorithm for Collision-free Digital Watermarking,' emph{Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2012 Eighth International Conference on}, pp. 256-260 ,2012.
[5] E. N. Gillbert, “Cyclically permutable error-correcting codes,” IEEE Trans. Inform, Theory, vol. 9, pp. 175--182, Jul. 1963.
[6] M. Kuribayashi and H. Tanaka, “How to Generate Cyclically Permutable Codes from Cyclic Codes,” IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4660–4663, oct. 2006.
[7] Massey, “Constructions of binary constant weight cyclic codes and cyclically permutable codes,” IEEE Trans. Inf. Theory, vol. 38,no. 3, pp. 940–949, May 1992.
[8]S. Bitan and T. Etzion, “Constructions for optimal constant weight cyclically permutable codes and difference families,” IEEE Trans. Inf. Theory, vol. 41, no. 1, pp. 77–87, Jan. 1995.
[9] W.C. Kwong, P.A. Perrier, and P.R. Prucnal, “Performance comparisonof asynchronous and synchronous code-division multiple-access techniquesfor fiber-optic local area networks,” IEEE Trans. Commun., vol.39, no. 11, pp. 1625–1634, Nov. 1991.
[10] L. Tan˘cevski and I. Andonovic, “Hybrid wavelength hopping/timespreading schemes for use in massive optical networks with increasedsecurity,” J. Lightw. Technol., vol. 14, no. 12, pp. 2636–2647, Dec.1996.
[11] F.R.K. Chung, J.A. Salehi, and V.K. Wei, “Optical orthogonal codes: Design, analysis,and applications,” IEEE Trans. Info. Theory, vol. 35.no. 3, pp. 595–604, May 1989.
[12] R. Fuji-Hara and Y. Miao, “Optical orthogonal codes: Their bounds and new optimal constructions,” IEEE Trans. Info. Theory, vol. 46, no.7, pp. 2396–2406, Jul. 2000.
[13] O. Moreno, R. Omrani, P.V. Kumar, and H.-F. Lu, “A generalized Bose-Chowla family of optical orthogonal codes and distinct difference sets,”IEEE Trans. Info. Theory, vol. 53, no. 5, pp. 1907–1910, May 2007.
[14] G.-C. Yang and W.C. Kwong, “Performance comparison of multiwavelength CDMA and WDMA+CDMA for fiber-optic networks,” IEEE Trans. Commun., vol. 45, no. 11, pp. 1426–1434, Nov. 1997.
[15] G.-C. Yang and W.C. Kwong, Prime Codes with Applications to CDMA Optical and Wireless Networks, Norwood, MA: Artech House, 2002.
[16] W.C. Kwong, G.-C. Yang, V. Baby, C.-S. Br`es, and P.R. Prucnal,“Multiple-wavelength optical orthogonal codes under prime-sequence permutations for optical CDMA,” IEEE Trans. Commun., vol. 53, no.1, pp. 117–123, Jan. 2005.
[17] C.-Y. Chang, G.-C. Yang, and W.C. Kwong, “Wavelength-time codes with maximum cross-correlation function of two for multicode-keying optical CDMA,” J. Lightw. Technol., vol. 24, no. 3, pp. 1093–1100,Mar. 2006.
[18] Liu, J.-C., Yang, G.-C., Chen, H.-S., Chen, Y.-R., Chang, C.-Y. and Kwong, W. C., “New Tree-Structured Optical Codes for Incoherent Optical-CDMA Applications,” IEEE/OSA Journal of Lightwave Technology, vol.33, no.19, pp.3968-3979, October 2015.