Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/83380
Title: Construction of de Bruijn sequences from product of two irreducible polynomials
Authors: Chang, Zuling
Ezerman, Martianus Frederic
Ling, San
Wang, Huaxiong
Keywords: Binary periodic sequence
De Bruijn sequence
Issue Date: 2017
Source: Chang, Z., Ezerman, M. F., Ling, S., & Wang, H. (2017). Construction of de Bruijn sequences from product of two irreducible polynomials. Cryptography and Communications, 10(2), 251-275.
Series/Report no.: Cryptography and Communications
Abstract: We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly.
URI: https://hdl.handle.net/10356/83380
http://hdl.handle.net/10220/43538
ISSN: 1936-2447
DOI: 10.1007/s12095-017-0219-8
Rights: © 2017 Springer Science+Business Media New York. This is the author created version of a work that has been peer reviewed and accepted for publication by Cryptography and Communications, Springer Science+Business Media New York. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1007/s12095-017-0219-8].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Construction of de Bruijn sequences from product of two irreducible polynomials.pdf211.4 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.