solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看5166次
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 查看全文>>