dot
UNB EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
dot
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
Fibonacci 
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.

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