×

The adjacency graphs of FSRs with a class of affine characteristic functions. (English) Zbl 1422.94023

Summary: In the past decades, the construction of de Bruijn sequences has been extensively studied. Let \(\phi\) be the one-to-one map from \(\mathbb{F}_2 [x]\) to the set of all linear Boolean functions and the symbol “\(\ast\)” denote the product of two Boolean functions \(f(x_0, x_1, \dots, x_n)\) and \(g(x_0, x_1, \dots, x_m)\) given by \[ f(g(x_0, x_1, \dots, x_m), g(x_1, x_2, \dots, x_{m + 1}), \dots, g(x_n, x_{n + 1}, \dots, x_{n + m})) . \] Then in this paper, a feedback shift register (FSR) with the characteristic function \((l + 1) \ast \phi(p(x))\) is considered to construct de Bruijn sequences for the first time, where \((l + 1)\) is an affine Boolean function and \(p(x)\) is a primitive polynomial over \(\mathbb{F}_2\) of degree \(n > 2\) with \(\phi^{- 1}(l)\) not divisible by \(p(x)\). In specific, we determine the cycle structure and the adjacency graphs of this type of FSRs. As an example, we present the adjacency graph of FSRs with characteristic functions of the form \(((x_0 + x_1 + x_2 + x_3 + 1) \ast \phi(p(x)))\) and calculate the total number of de Bruijn sequences constructed from these FSRs. Note that it is the first time that the FSRs with affine characteristic functions are considered to construct de Bruijn sequences, and thus a new class of de Bruijn sequences are derived.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Golomb, S. W., Shift register sequences, (1967), Holden-Day San Francisco · Zbl 0267.94022
[2] Fredricksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM Rev., 24, 195-221, (1982) · Zbl 0482.68033
[3] Hauge, E. R.; Mykkeltveit, J., On the classification of debruijn sequences, Discrete Math., 148, 65-83, (1996) · Zbl 0843.05049
[4] Etzion, T.; Lempel, A., Algorithms for the generation of full-length shift-register sequences, IEEE Trans. Inf. Theory, 30, 480-484, (1984) · Zbl 0546.68056
[5] Fredricksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM Rev., 24, 195-221, (1982) · Zbl 0482.68033
[6] Li, C.; Zeng, X.; Helleseth, T., The properties of a class of linear FSRs and their applications to the construction of nonlinear fsrs, IEEE Trans. Inf. Theory, 60, 3052-3061, (2014) · Zbl 1360.94281
[7] Li, C.; Zeng, X.; Li, C.; Helleseth, T., A class of de Bruijn sequences, IEEE Trans. Inf. Theory, 60, 7955-7969, (2014) · Zbl 1359.94553
[8] Li, M.; Lin, D., The adjacency graphs of linear feedback shift registers with primitive-like characteristic polynomials, IEEE Trans. Inf. Theory, 63, 1325-1335, (2017) · Zbl 1364.94819
[9] Li, C.; Zeng, X.; Li, C.; Helleseth, T.; Li, M., Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials, IEEE Trans. Inf. Theory, 62, 610-624, (2016) · Zbl 1359.94554
[10] Lempel, A., On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers, IEEE Comput. Soc., 19, 1204-1209, (1970) · Zbl 0225.94028
[11] Alhakim, A.; Akinwande, M., A recursive construction of nonbinary de Bruijn sequences, Des. Codes Cryptogr., 60, 155-169, (2011) · Zbl 1227.68080
[12] Berge, C., The theory of graphs and its applications, (1962), Methuen Co Ltd London · Zbl 0097.38903
[13] Mykkeltveit, J.; Siu, M. K.; Tong, P., On the cycle structure of some nonlinear shift register sequences, Inf. Control, 43, 202-215, (1979) · Zbl 0431.68059
[14] Li, M.; Lin, D., De Bruijn sequences, adjacency graphs and cyclotomy, IEEE Trans. Inf. Theory, 64, 2941-2952, (2018) · Zbl 1392.94908
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.