Good–de Bruijn diagram

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