Summary

Proceedings of the 2012 International Symposium on Nonlinear Theory and its Applications

2012

Session Number:D3L-A

Session:

Number:883

On Cross-Correlation Values of de Bruijn Sequences

Hiroshi Fujisaki,  Daisuke Yoshikawa,  

pp.883-886

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.1.883

PDF download (314KB)

Summary:
We show that the worst cases of the cross-correlation functions for pairs of de Bruijn sequences are characterized by the auto-correlation functions for sequences of the worst pairs. Then we give upper and lower bounds of the normalized cross-correlation functions not only for the worst pairs but also for all other pairs of de Bruijn sequences of length N = 2n (n ≥ 3). These bounds are tight in the sense that the equalities hold for n = 4. For n = 4, we experimentally characterize a good family of de Bruijn sequences in terms of the both normalized auto- and cross-correlation functions.

References:

[1] N. Masuda and K. Aihara, “Chaotic cipher by finite-state baker's map,” Trans. of IEICE, vol. 82-A, pp.1038-1046, 1999 (in Japanese).

[2] A. Tsuneda, Y. Kuga, and T. Inoue, “New Maximal-Period Sequences Using Extended Nonlinear Feedback Shift Registers Based on Chaotic Maps,” IEICE Trans. on Fundamentals, vol. E85-A, pp.1327-1332, 2002.

[3] H. Fujisaki, “Discretized Markov Transformations—An Example of Ultradiscrete Dynamical Systems—,” IEICE Trans. Fundamentals, vol. E88-A, pp.2684-2691, 2005.

[4] R. Hirota and D. Takahashi, Discrete and Ultradiscrete Systems, Kyoritsu Shuppan, 2003 (in Japanese).

[5] H. Fujisaki, “An Algorithm For Generating All Full-Length Sequences Which Are Based On Discretized Markov Transformations,” NOLTA, IEICE, vol. 1, pp. 166-175, 2010.

[6] Z. Zhang and W. Chen, “Correlation properties of de Bruijn sequences,” Systems Science and Mathematical Sciences, vol. 2, pp. 170-183, 1989.

[7] H. Fujisaki and Y. Nabeshima, “On Auto-Correlation Values of de Bruijn Sequences,” NOLTA, IEICE, vol. 3, pp. 400-408, 2011.

[8] N. G. de Bruijn, “A Combinatorial Problem,” Nederl. Akad. Wetensch. Proc., vol. 49, pp. 758-764, 1946.

[9] C. Flye Sainte-Marie, “Solution to problem number 58,” L'Intermediare des Mathematiciens,, vol. 1, pp. 107-110, 1894.