On Characteristic Functions of De Bruijn Sequences

TANG Zhenwei; QI Wenfeng; TIAN Tian

doi:10.1049/cje.2016.03.017

Volume 25 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(2): 304-311

TANG Zhenwei, QI Wenfeng, TIAN Tian, “On Characteristic Functions of De Bruijn Sequences,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 304-311, 2016, doi: 10.1049/cje.2016.03.017

Citation:

TANG Zhenwei, QI Wenfeng, TIAN Tian, “On Characteristic Functions of De Bruijn Sequences,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 304-311, 2016, doi: 10.1049/cje.2016.03.017

TANG Zhenwei, QI Wenfeng, TIAN Tian, “On Characteristic Functions of De Bruijn Sequences,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 304-311, 2016, doi: 10.1049/cje.2016.03.017

Citation:

TANG Zhenwei, QI Wenfeng, TIAN Tian, “On Characteristic Functions of De Bruijn Sequences,” Chinese Journal of Electronics, vol. 25, no. 2, pp. 304-311, 2016, doi: 10.1049/cje.2016.03.017

PDF( 168 KB)

On Characteristic Functions of De Bruijn Sequences

doi: 10.1049/cje.2016.03.017

Department of Applied Mathematics, Zhengzhou Information Science and Technology Institute, Zhengzhou 450001, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61272042, No.61100202).

Received Date: 2014-03-19
Rev Recd Date: 2014-09-25
Publish Date: 2016-03-10

Abstract

Abstract

In 1982, H. Fredricksen presented the upper and lower bounds of the number of ones in the truth table of characteristic functions of de Bruijn sequences. In this paper, the distribution of ones in the truth table of characteristic functions of de Bruijn sequences is further studied. We provide the upper and lower bounds of the number of ones in the partial truth table of characteristic functions of de Bruijn sequences. Furthermore, the two bounds are tight.
- Nonlinear feedback shift registers,
- De Bruijn sequences,
- Weight of the truth table

FullText(HTML)

References(13)

References

N. Courtois and W. Meier, "Algebraic attacks on stream ciphers with linear feedback", EUROCRYPT 2003, Warsaw, Poland, pp.346-359, 2003.

N. Courtois, "Fast algebraic attacks on stream ciphers with linear feedback", CRYPTO 2003, Santa Barbara, California, USA, pp.176-194, 2003.

W. Meier and O. Staffelbach, "Fast correlation attacks on certain stream ciphers", J. Crypt., Vol.1, No.3, pp.159-176, 1989.

A. Canteaut and M. Trabbia, "Improved fast correlation attacks using parity-check equations of weight 4 and 5", EUROCRYPT 2000, Bruges, Belgium, pp.573-588, 2000.

M. Hell and T. Johansson, "The Grain family of stream ciphers", LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.179-190, 2008.

C. De Cannière and B. Preneel, "Trivium", LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.244-266, 2008.

S. Babbage and M. Dodd, "The MICKEY stream ciphers", LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.191-209, 2008.

N. G. de Bruijn, "A combinatorial problem", Koninkl. Ned. Akad. Wetenschappen, Vol.49, No.7, pp.758-764, 1946.

E. A. Walker, "Non-linear recursive sequences", Canadian J. Math., Vol.11, No.3, pp.370-378, 1959.

Ç. Çalik, M. S. Turan and F. Özbudak, "On feedback functions of maximum length nonlinear feedback shift registers", IEICE Trans. Fundamentals, Vol.E93-A, No.6, pp.1226-1231, 2010.

H. Fredricksen, "A survey of full length nonlinear shift register cycle algorithms", SIAM Review, Vol.24, No.2, pp.195-221, 1982.

S. W. Golomb, Shift Register Sequences, Aegean Park Press, New York, USA, 1982.

Z.X.Wang, H. Xu and W.F. Qi, "On the cycle structure of some nonlinear feedback shift registers", Chinese Journal of Electronics, Vol.23, No.4, pp.801-804, 2014.

Relative Articles

Supplements(0)

Cited By

Proportional views