Research On Some Problems Of Error-correcting Codes And Sequence Ciphers Over Finite Rings

At present, with the successive development of production technique and the successive deep-going researches on error-correcting coding theory and theory of stream ciphers over finite rings have not only important theoretical significance but also important practical value.In recent decade, researches on error-correcting coding theory over finite rings have drawn intensive attention in the field of error-correcting coding theory. The ring F₂+uF₂ is a four-element ring which shares some good properties of both Z₄ and F₄.The ring F_p+uF_p+...+u^k-1F_p , which is the general case of ring F₂+uF₂, has already been used in the construction of optimal frequency-hopping sequence by P. Udaya. Coding theory over these rings has recently received a great deal of interest among coding theorists. This dissertation makes a deep-going research for various properties of linear codes and cyclic codes over these rings F_p+uF_p+ ...+u^k-1F_p. Research on algorithms for generating de Bruijn sequences is always a key problem in the study field of stream ciphers in the past several decades. Although numbers of effective algorithms for generating binary de Bruijn sequences have been given, there is still a considerably big gap between algorithms for generating de Bruijn sequences over finite rings, and the practical requirement due to the complexity of operations over finite rings. In this dissertation, we give an efficient algorithm for generating de Bruijn sequences by raising stage over Z₄ and F₂+uF₂, respectively. The details are given as follows:1. We give the theory of Galois ring over F₂+uF₂, and show that the automorphism group of this Galois ring is different from the corresponding group over Z4. Trace code and subring subcode over this Galois ring are defined, and it is prove that the trace code of dual code of a linear code is the dual code of subring subcode.2. We give the structure of cyclic codes over F₂+uF₂ for arbitrary even length, and determine the number of cyclic codes for a given length.3. The concepts of Kerdock code and Preparata code are introduced into the ring Fp+uF_p, the trace representation of Kerdock code is given. In the case p=2, we give the relations of these two codes with binary Reed-Muller codes;and we provethe one order Reed-Muller code is the Gray image of a linear subcode of Kerdock code.4. A Gray map from (F_p+uF_p+...+u^k-lF_p)" to F_p^pkn is defined, and somepropositions of the map are given. A sufficient and necessary condition about cyclic code over F_p+uF_p+... +u^k-lF_p is given.5. The generator matrixes of linear codes and their dual codes over F_p+uF_p+...+u^k-lF_p and Mac Williams identities between linear codes and their duals are given.6. We give an efficient algorithm for generating arbitrary higher stage de Bruijn sequences from a given feedback function of lower stage de Bruijn sequencesby raising stage over Z₄ and F₂+uF₂, respectively.