Open AccessOn Characteristic Functions of De Bruijn Sequences
Author(s) -
Tang Zhenwei,
Qi Wenfeng,
Tian Tian
Publication year - 2016
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2016.03.017
Subject(s) - de bruijn sequence , de bruijn graph , table (database) , mathematics , upper and lower bounds , truth table , combinatorics , discrete mathematics , computer science , algorithm , mathematical analysis , data mining
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.