臺灣博碩士論文加值系統

中文摘要


我們研究比較有組合性質的碼，如 super imposed codes, Reed-Muller Codes, Punctured Reed-Muller Codes, Hexacode, Extended Golay Code 和 Convolutional Codes等。我們探討這些碼和投影空間(projective geometries), 仿射空間(affine geometries),甚至一般的 ranked poset 的關係。

Abstract

We study codes with more combinatorial properties involved than algebraic properties. These include super imposed codes, Reed-Muller Codes, Punctured Reed-Muller Codes, Hexacode, Extended Golay Code and Convolutional Codes, most of them are related to the incidence structure on the projective geometries, affine geometries, or some ranked posets.

Contents
1 Introduction 1
2 Super imposed Codes 3
2.1 Definition . . . . . . . . . . . . . . . . . . . . 3
2.2 Disjunct matrices . . . . . . . . . . . . . . . . 4
2.3 Decoding . . . . . . . . . . . . . . . . . . . . . 5
2.4 Remarks . . . . . . . . . . . . . . . . . . . . . 7
3 Pooling spaces 8
3.1 Preliminaries . . . . . . . . . . . . . . . . . . 8
3.2 Definitions .. . . . . . . . . . . . . . . . . . . 11
3.3 The contractions of a graph . . . . . . . . . . . 12
3.4 Finite fields . . . . . .. . . . . . . . . . . . . 14
3.5 Projective and affine geometries . . . . . . . . . 15
3.6 Codes on projective and affine geometries. . . . . 22
3.7 Sperner's theorem and EKR theorem . . . . . . . . 23
3.8 Remarks . . . . . . . . . . . . . . . . . . . . . 24
4 Reed-Muller Codes 26
4.1 Linear Codes . . . . . . . . . . . . . . . . . . . 26
4.2 Reed-Muller Codes . . . . . . . . . . . . . . . . 27
4.3 Decoding . . . . . . . . . . . . . . . . . . . . . 33
4.4 Recursive construction of RM(1;m) . . . . . . . . 38
4.5 Covering radius . . . . . . . . . . . . . . . . . 39
5 Punctured Reed-Muller Codes 42
5.1 Definition . . . . . . . . . . . . . . . . . . . . 42
5.2 Cyclic Codes . . . . . . . . . . . . . . . . . . . 44
5.3 Lucas Theorem . . . . . . . . . . . . . . . . . . 47
5.4 Evaluation f(a) for f 2 PRM(r;m) . . . . . . . . . 49
5.5 The dimension of PRM(r;m) . . . . . . . . . . . . 53
5.6 Remarks . . . . . . . . . . . . . . . . . . . . . 55
6 Hadamard matrices and bent functions 56
6.1 Hadamard matrices . . . . . . . . . . . . . . . . 56
6.2 Bent functions . . . . . . . . . . . . . . . . . 60
7 Hexacode and Extended Binary Golay Code 66
7.1 Hexacode . . . . . . . . . . . . . . . . . . . . 66
7.2 Extended Binary Golay Code . . . . . . . . . . . . 70
7.3 Decoding in Extended Binary Golay Code . . . . . . 73
7.4 Remarks . . . . . . . . . . . . . . . . . . . . . 75
8 Convolutional Codes 76
8.1 Definition . . . . . . . . . . . . . . . . . . . . 76
8.2 Convolutional Code . . . . . . . . . . . . . . . . 77
8.3 Elementary rows and columns operations on G(x) . . 78
8.4 Forney Sequence and Free Distance . . . . . . . . 93
8.5 Wyner-Ash Convolutional Code . . . . . . . . . . . 96

Bibliography
[1] Richard E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, Cambridge, 2003.
[2] R. A. Brualdi, Introductory Combinatorics, 4th Ed., Pearson Prentics Hall, New
Jersey, 2004.
[3] D. Du and F. K. Hwang, Combinatorial Group Testing and Its Applications, 2nd
Ed., World Scientific, Singapore, 2000.
[4] A. G. D'yachkov, F. K. Hwang, A. J. Macula, P. A. Vilenkin, C. Weng, A
Construction of Pooling Designs with Some Happy Surprises, Journal of Com-
putational Biology, 12(8), 1127-1134, 2005.
[5] P. ErdÄos, P. Frankl and D. FÄuredi, Families of ‾nite sets in which no set is
covered by the union of r others. Israel J. Math. 51:79{89, 1985.
[6] T. Huang and C. Weng, A note on decoding of superimposed codes, Journal of
Combinatorial Optimization, 7, 381-384, 2003.
[7] T. Huang and C. Weng, Pooling spaces and non-adaptive designs. Discrete
Mathematics 282:163{169, 2004.
[8] H. Huang, Y. Huang and C. Weng, More on Pooling Spaces, preprint.
[9] W. H. Kautz and R. C. Singleton. Nonadaptive binary superimposed codes.
IEEE Trans. Inform. Theory, 10:363{377, 1964.
103
104 BIBLIOGRAPHY
[10] J. H. van Lint and R. M. Wilson, A Course in Combinatorics. Cambridge,
Victoria, 1992.
[11] A, J. Macula, A simple construction of d-disjunct matrices with certain constant
weights. Discrete Math. 162:311{312, 1996.
[12] A. J. Macula, Error-correcting nonadaptive group testing with de-disjunct matrices. Discrete Appl. Math. 80:217-222, 1997.
[13] H. Ngo and D. Du, New Constructions of Non-Adaptive and Error-Tolerance
Pooling Designs, Discrete Math., 243:161{170, 2002.
[14] Vera Pless, Introduction to the Theory of Error-Correcting Codes John Wiley &
Sons, Inc, New York, 1998.