Canonical form of the Universal Circuits Matrix of Feedback Functions

Abstract

This paper deals with a connection between the universal circuits matrix \([10]\) and the crossing relation \([1,5]\). The value of the universal circuits matrix obtained for \(\overline{\omega}\), where \(\omega\) is an arbitrary feedback function that generates de Bruijn sequences, forms the binary matrix that represents the crossing relation of \(\omega\). This result simplifies the design and study of the feedback functions that generate the de Bruijn sequences and allows us to decipher many inforrnations about the adjacency graphs of another feedback functions. For example, we apply these results to analyze the Hauge-Mykkeltveit classification of a family of de Bruijn sequences \([4]\).