An efficient implementation of the D-homomorphism for generation of de Bruijn sequences

In this correspondence, an efficient implementation of the D-homomorphism f or generating de Bruijn sequences is presented. The number of exclusive-or operations required to generate the next bit for de Bruijn sequences of ord er n from a de Bruijn function of order k is shown to be approximately k(2( W(n-k))- 1), where W(r) is the number of one's in the binary representation of r: therefore, the number of required operations can be reduced to k if the de Bruijn function is selected appropriately. As an application, the st ream cipher is indicated.