On prefer-one sequences. (English) Zbl 07926039
Summary: We study the sequences generated by prefer-one rule with different initial vectors. Firstly, we give upper bounds of their periods and for initial vectors with Hamming weight one, we prove that the generated sequences are modified de Bruijn sequences. Moreover, for two of them, we give the truth tables of their feedback functions. We also investigate the feedback functions of prefer-one de Bruijn sequences. For order \(n\) prefer-one de Bruijn sequence, we give linear and quadratic terms in its feedback function and prove that the number of degree \(n-2\) terms has the same parity as \(n\). The statistical result for small \(n\) shows that about half of all terms occur in the feedback functions.
MSC:
| 94A55 | Shift register sequences and sequences over finite alphabets in information and communication theory |
| 68W32 | Algorithms on strings |
| 68R15 | Combinatorics on words |
References:
| [1] | Alhakim, AM, A simple combinatorial algorithm for de Bruijn sequences, Am. Math. Mon., 117, 728-732, 2010 · Zbl 1232.05006 · doi:10.4169/000298910x515794 |
| [2] | Claude, C., Boolean Functions for Cryptography and Coding Theory, 2021, Cambridge: Cambridge University Press, Cambridge · Zbl 1512.94001 |
| [3] | Chang, Z.; Ezerman, MF; Fahreza, AA, On greedy algorithms for binary de Bruijn sequences, Appl. Algebra Eng. Commun. Comput., 33, 5, 523-550, 2022 · Zbl 1519.94019 · doi:10.1007/s00200-020-00459-3 |
| [4] | Fredricksen, H., The lexicographically least de Bruijn cycle, J. Comb. Theory, 9, 1, 1-5, 1970 · Zbl 0199.31702 · doi:10.1016/S0021-9800(70)80050-3 |
| [5] | Fredricksen, H., Generation of the ford sequence of length \(2^n, n\) large, J. Comb. Theory Ser. A, 12, 1, 153-154, 1972 · Zbl 0229.05004 · doi:10.1016/0097-3165(72)90091-X |
| [6] | Fredricksen, H., A class of nonlinear de Bruijn cycles, J. Comb. Theory Ser. A, 19, 2, 192-199, 1975 · Zbl 0311.05007 · doi:10.1016/S0097-3165(75)80007-0 |
| [7] | Fredricksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM Rev., 24, 2, 195-221, 1982 · Zbl 0482.68033 · doi:10.1137/1024041 |
| [8] | Golomb, SW, Shift Register Sequences, 1967, San Francisco: Holden-Day, San Francisco · Zbl 0267.94022 |
| [9] | Martin, MH, A problem in arrangements, Bull. Am. Math. Soc., 40, 12, 859-864, 1934 · Zbl 0010.28901 · doi:10.1090/S0002-9904-1934-05988-3 |
| [10] | Mossige, S., Constructive theorems for the truth table of the ford sequence, J. Comb. Theory Ser. A, 11, 1, 106-110, 1971 · Zbl 0217.30901 · doi:10.1016/0097-3165(71)90012-4 |
| [11] | Wang X.F., Wong D., Zhang W.G.: A simple greedy de bruijn sequence construction. In: Sequences and Their Applications (SETA) (2018). |
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.
