臺灣博碩士論文加值系統

利用準循環碼 (quasi-cyclic codes)和卷積碼 (convolutional codes)能具有相同最小(自由)距離，與里德-所羅門碼 (Reed-Solomon codes)可以設計最小距離的特性，構造出不易發生解碼錯誤的卷積碼 (convolutional codes)。

According to that quasi-cyclic codes and convolutional codes can have the same minimum (free) distance, and that Reed-Solomon codes can be designed minimum distance, we can construct convolutional codes with lower error probability of decoding.

Contents
1 Introduction 3
1.1 Background of coding theory . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 The difference codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Research motives and purposes . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Structure of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Background 4
2.1 Convolutional codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Viterbi decoding algorithm . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Decoding error probability on a binary symmetric channel (BSC). . 15
2.2 Block codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Cyclic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1.1 BCH codes . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1.2 Reed-Solomon codes . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Quasi-cyclic codes (QC codes) . . . . . . . . . . . . . . . . . . . . . 21
3 A link between convolutional codes and quasi-cyclic codes 24
4 Construct 1-generator quasi-cyclic codes 26
5 A lower bound of the minimum distances of quasi-cyclic codes which are
associated with Reed-Solomon codes 37
6 Conclusion 39
7 Appendix 41
7.1 GAP : find wight enumerations of quasi-cyclic codes . . . . . . . . . . . . . 41
7.1.1 Generator polynomial ˜ g(x) = (x 14 + x 13 + x 11 + x 7 + 1,0,0). . . . . 41
7.1.2 Generator polynomial ˜ g(x) = (x 14 +x 13 +x 12 +x 11 +x 10 +x 8 +x 6 +x 5 +
x 4 +x 2 ,x 13 +x 12 +x 10 +x 4 +x 3 +x+1,x 13 +x 12 +x 10 +x 5 +x 4 +x 3 +x 2 ). 41
7.2 The cyclotomic cosets modulo 7, 73 and 273 . . . . . . . . . . . . . . . . . 42

[1] R. C. Bose and D. K. Ray-Chaudhuri, “On a Class of Error Correcting Binary Group
Codes, Inform. Control, 3: 68-79, March 1960.
[2] P. Elias, “Coding for Noisy Channels, IRS Conv. Rec., p.4:37-47,1955.
[3] M. Esmaeli, T.A. Gulliver, N. P. Secord, and S. A. Mahmoud, “A link betwwen
quasi-cyclic codes and convolutional codes, IEEE Trans. Inform. Theory, vol. 44,
pp.431-435, Jan. 1998.
[4] R. W. Hamming, “Error Detecting and Error Correcting Codes, Bell Syst. Tech. J.,
29: 147-60, April 1950.
[5] A. Hocquenghem, “Codes corecteurs d’erreurs, Chiffres, 2: 147-56, 1959.
[6] R. Johannesson and K.S. Zigangirov, Fundamental of convolutional coding, IEEE
Press, Piscataway, NJ, 1999.
[7] Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applicati-
ons, Cambridge University Press, 1994.
[8] K. Lally and P. Fitzpatrick, “Algebraic structure of quasi-cyclic codes, Discr. Appl.
Math., vol. 111, p.157-175, 2001.
[9] S. Ling and P. Sole’, On the algebraic structure of quasi-cyclic codes I: finite fields,
IEEE Trans. Inform. Thery, vol.47, pp.2751-2760, Nov. 2001.
[10] Shu Lin, Daniel J. Costello, Jr., Error Control Coding: Fundamental and Application.
Pearson, 2004.
[11] J. L. Messey, Threshold Decoding. MIT Press, Cambridge, 1963.
[12] J. L. Massey and M. K. Sain, “Inverses of linear sequential circuits, IEEE Trans.
Comput., C-17:330-337, 1968.
[13] F. J. MacWilliams and N. J. A Sloane, The Theory Of Error Correcting Codes,
North-Holland Mathematical Library; 16, 1996.
[14] E. Prange, “Cyclic Error-Correcting Codes in Two Symols, AFCRC-TN-57, 103, Air
Force Camridge Research Center, Cambridge, Mass., September 1957.
[15] I. S. Reed and G. Solomon, “Polynomial codes over Certain Finit Fields. J. Soc. Ind.
Appl. Math., 8:300-304, June 1960.
[16] C. E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J.,
pp.379-423(Part1), July 1948.
[17] Ge’rald E. Se’guin, “A class of 1-generator quasi-cyclic codes, IEEE Trans. Inform.
Theory, vol. 50, No.8, Aug. 2004.
[18] A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Opti-
mum Decoding Algorithm, IEEE Tran. Inform. Theory, IT-13:260-69, April 1967.
[19] A. J. Viterbi,Convolutional codes and their performance in a communication sys-
tems, IEEE Trans. Commun. Technol., COM-19:751-772, 1971.
[20] J. M. Wozencraft and B. Reiffen, Sequential Decoding, MIT Press, Cambridge,1961.