On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
- 1 December 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-19 (12), 1204-1209
- https://doi.org/10.1109/t-c.1970.222859
Abstract
A homomorphism of the de Bruijn graph that maps a graph of order n onto one of order n-1 and its applications to the design of nonsingular feedback shift registers are discussed. The properties preserved under this mapping suggest a new design technique whose main advantage is due to the fact that the problem of designing a desired n-stage shift register may be reduced to a problem of order n-1 or less. Among the results obtained is a recursive formula for a feedback function that generates a cycle of maximum length.This publication has 8 references indexed in Scilit:
- On extremal factors of the de Bruijn graphJournal of Combinatorial Theory, Series B, 1971
- m-ary closed sequencesJournal of Combinatorial Theory, Series A, 1971
- The Decomposition of the States of a Linear Feedback Shift Register Into Cycles of Equal LengthIEEE Transactions on Computers, 1970
- Counting with Nonlinear Binary Feedback Shift RegistersIEEE Transactions on Electronic Computers, 1963
- Counting with Feedback Shift Registers by Means of a Jump TechniqueIEEE Transactions on Electronic Computers, 1962
- Regular sequences and frequency distributionsProceedings of the American Mathematical Society, 1960
- The Theory of Autonomous Linear Sequential NetworksIRE Transactions on Circuit Theory, 1959
- Shifting countersTransactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 1958