EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Linear Recursive Sequence Generator

Shift registers with feedback essentially divide polynomials to create distinctive binary sequences.

This online tool draws and analyzes digital circuits which generate Linear Recursive Sequences (LRS) based on a defining polynomial P(x). A complete state table is derived for the sequential circuit shown below.

Fibonacci Implementation
alternate configuration
`Circuit based on P(x) = x7+x4+1`

The circuit taps correspond to P(x) = (10010001).
State Table

This circuit may be analyzed by considering what would happen when the shift register is clocked for each possible state of the circuit. In the state table below, the shift register is filled with each possible value and the contents after the next clock are computed. Results are shown in binary and in decimal. A sequence of states may be traced by following the states from any starting value. The least significant bit is shifted out to create a bitstream output sequence.

Taps: (10010001) (prime)
 THIS STATE ⇒ NEXT STATE 0 0 0 0 0 0 0 0 ⇒ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ⇒ 1 0 0 0 0 0 0 64 0 0 0 0 0 1 0 2 ⇒ 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 3 ⇒ 1 0 0 0 0 0 1 65 0 0 0 0 1 0 0 4 ⇒ 0 0 0 0 0 1 0 2 0 0 0 0 1 0 1 5 ⇒ 1 0 0 0 0 1 0 66 0 0 0 0 1 1 0 6 ⇒ 0 0 0 0 0 1 1 3 0 0 0 0 1 1 1 7 ⇒ 1 0 0 0 0 1 1 67 0 0 0 1 0 0 0 8 ⇒ 0 0 0 0 1 0 0 4 0 0 0 1 0 0 1 9 ⇒ 1 0 0 0 1 0 0 68 0 0 0 1 0 1 0 10 ⇒ 0 0 0 0 1 0 1 5 0 0 0 1 0 1 1 11 ⇒ 1 0 0 0 1 0 1 69 0 0 0 1 1 0 0 12 ⇒ 0 0 0 0 1 1 0 6 0 0 0 1 1 0 1 13 ⇒ 1 0 0 0 1 1 0 70 0 0 0 1 1 1 0 14 ⇒ 0 0 0 0 1 1 1 7 0 0 0 1 1 1 1 15 ⇒ 1 0 0 0 1 1 1 71 0 0 1 0 0 0 0 16 ⇒ 1 0 0 1 0 0 0 72 0 0 1 0 0 0 1 17 ⇒ 0 0 0 1 0 0 0 8 0 0 1 0 0 1 0 18 ⇒ 1 0 0 1 0 0 1 73 0 0 1 0 0 1 1 19 ⇒ 0 0 0 1 0 0 1 9 0 0 1 0 1 0 0 20 ⇒ 1 0 0 1 0 1 0 74 0 0 1 0 1 0 1 21 ⇒ 0 0 0 1 0 1 0 10 0 0 1 0 1 1 0 22 ⇒ 1 0 0 1 0 1 1 75 0 0 1 0 1 1 1 23 ⇒ 0 0 0 1 0 1 1 11 0 0 1 1 0 0 0 24 ⇒ 1 0 0 1 1 0 0 76 0 0 1 1 0 0 1 25 ⇒ 0 0 0 1 1 0 0 12 0 0 1 1 0 1 0 26 ⇒ 1 0 0 1 1 0 1 77 0 0 1 1 0 1 1 27 ⇒ 0 0 0 1 1 0 1 13 0 0 1 1 1 0 0 28 ⇒ 1 0 0 1 1 1 0 78 0 0 1 1 1 0 1 29 ⇒ 0 0 0 1 1 1 0 14 0 0 1 1 1 1 0 30 ⇒ 1 0 0 1 1 1 1 79 0 0 1 1 1 1 1 31 ⇒ 0 0 0 1 1 1 1 15 0 1 0 0 0 0 0 32 ⇒ 0 0 1 0 0 0 0 16 0 1 0 0 0 0 1 33 ⇒ 1 0 1 0 0 0 0 80 0 1 0 0 0 1 0 34 ⇒ 0 0 1 0 0 0 1 17 0 1 0 0 0 1 1 35 ⇒ 1 0 1 0 0 0 1 81 0 1 0 0 1 0 0 36 ⇒ 0 0 1 0 0 1 0 18 0 1 0 0 1 0 1 37 ⇒ 1 0 1 0 0 1 0 82 0 1 0 0 1 1 0 38 ⇒ 0 0 1 0 0 1 1 19 0 1 0 0 1 1 1 39 ⇒ 1 0 1 0 0 1 1 83 0 1 0 1 0 0 0 40 ⇒ 0 0 1 0 1 0 0 20 0 1 0 1 0 0 1 41 ⇒ 1 0 1 0 1 0 0 84 0 1 0 1 0 1 0 42 ⇒ 0 0 1 0 1 0 1 21 0 1 0 1 0 1 1 43 ⇒ 1 0 1 0 1 0 1 85 0 1 0 1 1 0 0 44 ⇒ 0 0 1 0 1 1 0 22 0 1 0 1 1 0 1 45 ⇒ 1 0 1 0 1 1 0 86 0 1 0 1 1 1 0 46 ⇒ 0 0 1 0 1 1 1 23 0 1 0 1 1 1 1 47 ⇒ 1 0 1 0 1 1 1 87 0 1 1 0 0 0 0 48 ⇒ 1 0 1 1 0 0 0 88 0 1 1 0 0 0 1 49 ⇒ 0 0 1 1 0 0 0 24 0 1 1 0 0 1 0 50 ⇒ 1 0 1 1 0 0 1 89 0 1 1 0 0 1 1 51 ⇒ 0 0 1 1 0 0 1 25 0 1 1 0 1 0 0 52 ⇒ 1 0 1 1 0 1 0 90 0 1 1 0 1 0 1 53 ⇒ 0 0 1 1 0 1 0 26 0 1 1 0 1 1 0 54 ⇒ 1 0 1 1 0 1 1 91 0 1 1 0 1 1 1 55 ⇒ 0 0 1 1 0 1 1 27 0 1 1 1 0 0 0 56 ⇒ 1 0 1 1 1 0 0 92 0 1 1 1 0 0 1 57 ⇒ 0 0 1 1 1 0 0 28 0 1 1 1 0 1 0 58 ⇒ 1 0 1 1 1 0 1 93 0 1 1 1 0 1 1 59 ⇒ 0 0 1 1 1 0 1 29 0 1 1 1 1 0 0 60 ⇒ 1 0 1 1 1 1 0 94 0 1 1 1 1 0 1 61 ⇒ 0 0 1 1 1 1 0 30 0 1 1 1 1 1 0 62 ⇒ 1 0 1 1 1 1 1 95 0 1 1 1 1 1 1 63 ⇒ 0 0 1 1 1 1 1 31 1 0 0 0 0 0 0 64 ⇒ 0 1 0 0 0 0 0 32 1 0 0 0 0 0 1 65 ⇒ 1 1 0 0 0 0 0 96 1 0 0 0 0 1 0 66 ⇒ 0 1 0 0 0 0 1 33 1 0 0 0 0 1 1 67 ⇒ 1 1 0 0 0 0 1 97 1 0 0 0 1 0 0 68 ⇒ 0 1 0 0 0 1 0 34 1 0 0 0 1 0 1 69 ⇒ 1 1 0 0 0 1 0 98 1 0 0 0 1 1 0 70 ⇒ 0 1 0 0 0 1 1 35 1 0 0 0 1 1 1 71 ⇒ 1 1 0 0 0 1 1 99 1 0 0 1 0 0 0 72 ⇒ 0 1 0 0 1 0 0 36 1 0 0 1 0 0 1 73 ⇒ 1 1 0 0 1 0 0 100 1 0 0 1 0 1 0 74 ⇒ 0 1 0 0 1 0 1 37 1 0 0 1 0 1 1 75 ⇒ 1 1 0 0 1 0 1 101 1 0 0 1 1 0 0 76 ⇒ 0 1 0 0 1 1 0 38 1 0 0 1 1 0 1 77 ⇒ 1 1 0 0 1 1 0 102 1 0 0 1 1 1 0 78 ⇒ 0 1 0 0 1 1 1 39 1 0 0 1 1 1 1 79 ⇒ 1 1 0 0 1 1 1 103 1 0 1 0 0 0 0 80 ⇒ 1 1 0 1 0 0 0 104 1 0 1 0 0 0 1 81 ⇒ 0 1 0 1 0 0 0 40 1 0 1 0 0 1 0 82 ⇒ 1 1 0 1 0 0 1 105 1 0 1 0 0 1 1 83 ⇒ 0 1 0 1 0 0 1 41 1 0 1 0 1 0 0 84 ⇒ 1 1 0 1 0 1 0 106 1 0 1 0 1 0 1 85 ⇒ 0 1 0 1 0 1 0 42 1 0 1 0 1 1 0 86 ⇒ 1 1 0 1 0 1 1 107 1 0 1 0 1 1 1 87 ⇒ 0 1 0 1 0 1 1 43 1 0 1 1 0 0 0 88 ⇒ 1 1 0 1 1 0 0 108 1 0 1 1 0 0 1 89 ⇒ 0 1 0 1 1 0 0 44 1 0 1 1 0 1 0 90 ⇒ 1 1 0 1 1 0 1 109 1 0 1 1 0 1 1 91 ⇒ 0 1 0 1 1 0 1 45 1 0 1 1 1 0 0 92 ⇒ 1 1 0 1 1 1 0 110 1 0 1 1 1 0 1 93 ⇒ 0 1 0 1 1 1 0 46 1 0 1 1 1 1 0 94 ⇒ 1 1 0 1 1 1 1 111 1 0 1 1 1 1 1 95 ⇒ 0 1 0 1 1 1 1 47 1 1 0 0 0 0 0 96 ⇒ 0 1 1 0 0 0 0 48 1 1 0 0 0 0 1 97 ⇒ 1 1 1 0 0 0 0 112 1 1 0 0 0 1 0 98 ⇒ 0 1 1 0 0 0 1 49 1 1 0 0 0 1 1 99 ⇒ 1 1 1 0 0 0 1 113 1 1 0 0 1 0 0 100 ⇒ 0 1 1 0 0 1 0 50 1 1 0 0 1 0 1 101 ⇒ 1 1 1 0 0 1 0 114 1 1 0 0 1 1 0 102 ⇒ 0 1 1 0 0 1 1 51 1 1 0 0 1 1 1 103 ⇒ 1 1 1 0 0 1 1 115 1 1 0 1 0 0 0 104 ⇒ 0 1 1 0 1 0 0 52 1 1 0 1 0 0 1 105 ⇒ 1 1 1 0 1 0 0 116 1 1 0 1 0 1 0 106 ⇒ 0 1 1 0 1 0 1 53 1 1 0 1 0 1 1 107 ⇒ 1 1 1 0 1 0 1 117 1 1 0 1 1 0 0 108 ⇒ 0 1 1 0 1 1 0 54 1 1 0 1 1 0 1 109 ⇒ 1 1 1 0 1 1 0 118 1 1 0 1 1 1 0 110 ⇒ 0 1 1 0 1 1 1 55 1 1 0 1 1 1 1 111 ⇒ 1 1 1 0 1 1 1 119 1 1 1 0 0 0 0 112 ⇒ 1 1 1 1 0 0 0 120 1 1 1 0 0 0 1 113 ⇒ 0 1 1 1 0 0 0 56 1 1 1 0 0 1 0 114 ⇒ 1 1 1 1 0 0 1 121 1 1 1 0 0 1 1 115 ⇒ 0 1 1 1 0 0 1 57 1 1 1 0 1 0 0 116 ⇒ 1 1 1 1 0 1 0 122 1 1 1 0 1 0 1 117 ⇒ 0 1 1 1 0 1 0 58 1 1 1 0 1 1 0 118 ⇒ 1 1 1 1 0 1 1 123 1 1 1 0 1 1 1 119 ⇒ 0 1 1 1 0 1 1 59 1 1 1 1 0 0 0 120 ⇒ 1 1 1 1 1 0 0 124 1 1 1 1 0 0 1 121 ⇒ 0 1 1 1 1 0 0 60 1 1 1 1 0 1 0 122 ⇒ 1 1 1 1 1 0 1 125 1 1 1 1 0 1 1 123 ⇒ 0 1 1 1 1 0 1 61 1 1 1 1 1 0 0 124 ⇒ 1 1 1 1 1 1 0 126 1 1 1 1 1 0 1 125 ⇒ 0 1 1 1 1 1 0 62 1 1 1 1 1 1 0 126 ⇒ 1 1 1 1 1 1 1 127 1 1 1 1 1 1 1 127 ⇒ 0 1 1 1 1 1 1 63

See the various output sequences for this circuit.

Specify the taps for your sequence
Binary Value:    Reversed

 Modulo 2 addition is shown schematically equivalent to Exclusive-OR gates.

 Tue May 21 05:43:02 ADT 2013 Last Updated: 28 NOV 98 Richard Tervo [ tervo@unb.ca ] Back to the course homepage...