solidot新版网站常见问题,请点击这里查看。

Binary de Bruijn Sequences via Zech's Logarithms. (arXiv:1705.03150v2 [cs.IT] UPDATED)

来源于:arXiv
The cycle joining method and the cross-join pairing are two main construction techniques for de Bruijn sequences. This work shows how to combine Zech's logarithms and each of the two techniques to efficiently construct binary de Bruijn sequences of large orders. A basic implementation is supplied as a proof-of-concept. In the cycle joining method, the cycles are generated by an LFSR with a chosen period. We prove that determining Zech's logarithms is equivalent to identifying conjugate pairs shared by any pair of cycles. The approach quickly finds enough number of conjugate pairs between any two cycles to ensure the existence of trees containing all vertices in the adjacency graph of the LFSR. When the characteristic polynomial of the LFSR is a product of distinct irreducible polynomials, the approach via Zech's logarithms combines nicely with a recently proposed method to determine the conjugate pairs. This allows us to efficiently generate de Bruijn sequences with larger orders. Alon 查看全文>>