Good–de Bruijn diagram

Related Overviews


'Good–de Bruijn diagram' can also refer to...


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

A directed graph illustrating the possible succession of states of a shift register. Each possible state of the shift register (indicated by its contents) is represented by a node in the graph; from each node a set of arcs lead to all its possible immediate successors. (Succession involves one clocking of the shift register, with some serial input.) If there are n cells in a q-ary shift register, there will be qn nodes, each with q arcs leading from it, and thus qn-1 arcs altogether.

When the serial input is some function of the current state, the behavior of the shift register is described by a Good-de Bruijn graph with some arcs deleted: such subgraphs are used in the study of feedback registers.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.