THE FEEDBACK SHIFT REGISTER BASED DE BRUIJN SEQUENCES

Abstract

In this dissertation, a method of producing a large number of the Feedback Shift Register (FSR) based de Bruijn sequences is examined. The r-ary de Bruijn sequences is generated by combining many short period sequences generated from linear equations as an intial map. The number of de Bruijn sequences obtained by using our algorithm is presented for any span. The de Bruijn sequences, dB(r;k), are generalized using finite field theory which can be useful for obtaining long and random sequences. Moreover, the de Bruijn sequence is also generated by introducing quadratic term in the initial map. A binary m-sequence with period 2n􀀀1 is a maximal sequence of zeros and ones generated by linear feedback shift registers (LFSRs) and contains every non-zero binary n-tuple exactly once in a period of the sequence. Despite long period and good statistical properties, they are very susceptible to a plaintext attack. In order to mitigate these drawbacks, non-linearities have to be introduced using nonlinear feedback shift registers (NFSRs). Since there is no general method available in literature to construct all maximum period NFSR sequences, this dissertation considers an exhaustive search method to examine them directly. We inspect the question as to whether m-sequences can have quadratic, cubic or quartic span. The advance technique of parallel computing has been used to search for maximum period NFSRs having feedback function in simple algebraic normal form (ANF). The golay correlation functions (GCFs) are also studied as a measure of similarity among the sequences generated by our approach. When a zero is added to these NFSR based m-sequences, we can also obtain de Bruijn sequences. We have also studied some of the cryptographic properties of these sequences