Research On Some Problems Of Generalized Reed-muller Codes And Sequence Ciphers Over Finite Chain Rings

Reed-Muller codes are a very important family of algebraic codes, since they have very nice algebraic and combinatorial properties. Reed-Muller codes over finite rings can be used to construct some good codes, such as Kerdock codes、 Preparata codes、Goethals codes and so on, so they have important research value. De Bruijn sequences, which have high linear complexity and good pseudorandom-ness, most satisfy the requirements of key sequences, so they are always hot topics. Because of their special structure, research on Reed-Muller codes and de Bruijn sequences over finite chain rings will greatly promote the development of coding theory and theory of steam ciphers. In this thesis, Reed-Muller codes over ring Fp+uFp, as well as isomorphisms of de Bruijn-Good graphs over ring F2+uF2and F2+uF2+…+uk-1F2, are mainly studied. The construction of de Bruijn sequences over ring F2+uF2is also considered. The details are given as follows:(1) We construct a class of linear codes over F2+uF2, which is denoted by URM(r,m), and proves that its Gray image is the binary Reed-Muller codes R(r,m) when r=0,1,2,m-1and m.(2) We introduce the concept of the Reed-Muller codes into ring Fp+uFp, which is denoted by URM(p,r,m). Its trace representation is given. Moreover, its dual code and the relationship between them are studied. Especially, some better properties are obtained when p=2.(3) We define several automorphisms of de Bruijn-Good graphs over ring F2+uF2, and give a necessary and sufficient condition for the shift register over ring F2+uF2to be nonsingular, as well as the expression of nonsingular feedback functions and its automorphic functions. Then we generalize all the results in ring F2+uF2+…+uk-1F2.(4) We give a fast and efficient algorithm to generate de Bruijn sequences over ring F2+uF2.