Research On Error-Correcting Codes And Sequence Ciphers Over Finite Rings In Information Safety

Error-correcting coding theory and Cryptography are the theoretical bases of information safety. Theory of stream ciphers, namely theory of sequence ciphers, is one of the two component parts of cryptography. At present, error-correcting coding theory and theory of stream ciphers over finite fields have been not only developed perfectly but also applied widely to the productive practice. With the successive development of production technique and the successive deepgoing researches on theory, researches on error-correting coding theory and theory of stream ciphers over finite rings have not only important theoretial significance but also important practical value.During the past several decades, research on algorithms for generating de Bruijn sequences is always a key problem in the study field of stream ciphers. 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 ring Z_k and the practical requirement due to the complexity of operations over finite rings. In this dissertation are presented different algorithms for generating de Bruijn sequences over finite rings Z_k from various aspects. In recent decade, researches on error-correcting coding theory over finite rings have drawn intensive attention in the field of error-correcting coding theory. This dissertation makes a deepgoing research for various properties of linear codes and cyclic codes over finite rings. The details are given as follows.1. Theory of shift-register sequences over finite ring Z_k, is established. This dissertation defines k-ary shift register and k-ary de Bruijn-Good graph, studies properties of the state graph of shift register and the structure of self-isomorphisms of n-stage de Bruijn-Good graph; analyzes structure of cycles in state graphs of two class of special k-ary shift registers. By using k-1 D-homomorphic mappings from n-stage k-ary de Bruijn-Good graph onto (n-1)-stage k-ary de Bruijn-Good graph, a structure theorem of k-ary self-dual cycles and quasi-self-dual cycles is given.2. The homogeneous complexity of degree k of de Bruijn sequences is studied. The complexity is a standard which measures complexity of de Bruijn sequences. This dissertation defines the homogeneous complexity of degree k of de Bruijn sequences, studies properties of the homogeneous complexity of degree k of de Bruijn sequences by using linearization method of nonlinear problem, gives its upper bound..3. Various algorithms for generating k-ary de Bruijn sequences are studied systematically. This dissertation establishes principles of method of joining cycles for generating k-ary de Bruijn sequences, gives a recursive algorithm for the generation of k-ary de Bruijn sequences by joining all cycles in the state graph of pure cycling register on the principles. An operator for generating all necklaces is defined, and a memoryless algorithm for the generation of k-ary de Bruijnsequences is given by juxtaposing the periodic reductions of the necklaces, and then an innoiatory algorithm of raising elements is yielded from the memoryless algorithm. Each operational step of the two algorithms produces a string of elements instead of one element. The two algorithms are effective for generating k-ary de Bruijn sequences since they reduce the times of operation, and accelerate the speed of generation. By using properties of D-homomorphic mappings from n-stage k-ary de Bruijn-Good graph to (n- 1)-stage k-ary de Bruijn-Good graph, we give three algorithms of derivation and an algorithm of raising stage for generating feedback functions of k-ary de Bruijn sequences, where the three algorithms of derivation can produce k- 1 ,k(k— I)2 andkn-1 new feedback functions seperately from a given feed back function of k-ary de Bruijnsequences.4. Theory of depth distribution of codes over a finite ring Z4 is established. This dissertation defines the depth of a codeword and the depth distribution of codes over a finite ring Z4, gi...