The adjacency graphs of some feedback shift registers

详细信息    查看全文

• 作者：Ming Li ; Yupeng Jiang ; Dongdai Lin
• 关键词：Feedback shift register ; Adjacency graph ; De Bruijn sequence
• 刊名：Designs, Codes and Cryptography
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：82
• 期：3
• 页码：695-713
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
• 出版者：Springer US
• ISSN：1573-7586
• 卷排序：82

文摘

In this paper, we consider the adjacency graphs of some feedback shift registers (FSRs), namely, the FSRs with characteristic functions of the form \(g=(x_0+x_1)*f\). Firstly, we give some properties about these FSRs. We prove that these FSRs generate only prime cycles, and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. For example, it is shown that, when f contains an odd number of terms, the adjacency graph of \({\mathrm {FSR}}((x_0+x_1)*f)\) can be determined directly from the adjacency graph of \({\mathrm {FSR}}(f)\). Then, as an application of these results, we continue the work of Li et al. (IEEE Trans Inf Theory 60(5):3052–3061, 2014) to determine the adjacency graphs of \({\mathrm {FSR}}((1+x)^4p(x))\) and \({\mathrm {FSR}}((1+x)^5p(x))\), where p(x) is a primitive polynomial, and construct a large class of De Bruijn sequences from them.