Multi-rate Representation And Linear Complexity Analysis Of Generalized Cyclotomic Sequences

Pseudo-random sequences are widely used in spread spectrum communication systems, code division multiple access systems, global positioning systems, and stream ciphers etc. In these applications, especially in stream ciphers, there is a strong need for pseudo-random sequences of high linear complexity and good k-error linear complexity property. Due to good randomness properties and algebraic structure, cyclotomic and generalized cyclotomic sequences are extensively studied. This dissertation first gives a unified def-inition of generalized cyclotomy, and gives that every generalized cyclotmic sequence is shown to be a sum of some d-residue sequences. This dissertation then constructs sever-al generalized cyclotomic sequences and investigates their linear complexity and k-error linear complexity. Finally, new developments in q-polynomial codes are presented.The main results are shown as follows:1. A unified definition of generalized cyclotomy modular p1e1p2e2…prer is proposed. This definition is a generalization of both Whiteman’s generalized cyclotomy of length pq and Ding-Helleseth’s generalized cyclotomy. Based on this definition, every generalized cyclotmic sequence of order d over Zp1e1p2e2…prer is shown to be a sum of some d-residue sequences. Especially if d=2, generalized cyclotomic sequences is shown to be a sum of some Legendre sequences. For periods pe and p1e1p2e2…prer, new generalized cyclotomic sequences are constructed. Then by studying their muti-rate representations, the linear complexity properties are analyzed.2. A new class of generalized cyclotomic sequence over Zp1p2…pr (generalized Jacobi sequence) is constructed with its linear complexity properties studied. For r=2, the generalized Jocobi sequence is Whiteman’s generalized sequence of length pq. By using some reference sequence, we give some upper bounds of κ-error linear complexity for generalized Jocobi sequence of order 2. For r=3,4, by selecting different support set in Zn\Zn*, several generalized Jocobi sequences are constructed. The linear complexity of each sequence is also determined by the factoring of polynomials theory and the roots of its characteristic polynomial. The result shows that the linear complexity is at least nearly half of its period. By B-M algorithm, these sequences are considered to be good from the viewpoint of linear complexity.3. A new view on cyclic codes based on q-polynomials has been introduced by Ding and Ling. Here a concern on new developments in cyclic codes from q-polynomials is proposed by using the properties of q-polynomial. Firstly, the properties of the q-polynomial codes via the fundamental relations between q-polynomial codes and generator polynomials are proposed. A new design of t-error correcting codes (q-BCH codes) is then introduced and analyzed. Finally several constructions of new q-polynomial codes from old ones are presented.