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). The circuit shown below is traced through all possible states. Maximum length sequences are identified. The autocorrelation of each sequence can also be checked (maximum 1023 bits).

Fibonacci Implementation
* alternate configuration
Fibonacci 
Circuit based on P(x) = x8+x7+x6+x5+x4+x3+1

The circuit taps correspond to P(x) = (111111001).
Taps: (111111001) (prime)
Sequence #1 (Starting with 0)
States: 0 ⇒ 0, forever...

Sequence #2 (Starting with 1)
States: 1 ⇒ 128 ⇒ 192 ⇒ 96 ⇒ 48 ⇒ 24 ⇒ 12 ⇒ 134 ⇒ 195 ⇒ 225 ⇒ 112 ⇒ 184 ⇒ 92 ⇒ 174 ⇒ 215 ⇒ 107 ⇒ 53 ⇒ 154 ⇒ 205 ⇒ 102 ⇒ 51 ⇒ 153 ⇒ 76 ⇒ 38 ⇒ 147 ⇒ 201 ⇒ 100 ⇒ 50 ⇒ 25 ⇒ 140 ⇒ 70 ⇒ 163 ⇒ 209 ⇒ 104 ⇒ 180 ⇒ 218 ⇒ 109 ⇒ 54 ⇒ 27 ⇒ 141 ⇒ 198 ⇒ 99 ⇒ 177 ⇒ 88 ⇒ 172 ⇒ 214 ⇒ 235 ⇒ 245 ⇒ 250 ⇒ 253 ⇒ 126 ⇒ 63 ⇒ 31 ⇒ 143 ⇒ 199 ⇒ 227 ⇒ 113 ⇒ 56 ⇒ 156 ⇒ 206 ⇒ 231 ⇒ 115 ⇒ 57 ⇒ 28 ⇒ 14 ⇒ 135 ⇒ 67 ⇒ 33 ⇒ 16 ⇒ 136 ⇒ 68 ⇒ 162 ⇒ 81 ⇒ 168 ⇒ 212 ⇒ 234 ⇒ 117 ⇒ 58 ⇒ 157 ⇒ 78 ⇒ 39 ⇒ 19 ⇒ 9 ⇒ 4 ⇒ 2 ⇒ 1
Period = 85 (autocorrelation)
Output =
1000000011000011101011001100100110001011011000110101111110001110
011100001000101011100...

Sequence #3 (Starting with 3)
States: 3 ⇒ 129 ⇒ 64 ⇒ 160 ⇒ 80 ⇒ 40 ⇒ 20 ⇒ 138 ⇒ 69 ⇒ 34 ⇒ 145 ⇒ 200 ⇒ 228 ⇒ 242 ⇒ 121 ⇒ 188 ⇒ 94 ⇒ 175 ⇒ 87 ⇒ 171 ⇒ 85 ⇒ 170 ⇒ 213 ⇒ 106 ⇒ 181 ⇒ 90 ⇒ 173 ⇒ 86 ⇒ 43 ⇒ 149 ⇒ 202 ⇒ 229 ⇒ 114 ⇒ 185 ⇒ 220 ⇒ 110 ⇒ 183 ⇒ 91 ⇒ 45 ⇒ 150 ⇒ 75 ⇒ 165 ⇒ 210 ⇒ 233 ⇒ 244 ⇒ 122 ⇒ 61 ⇒ 30 ⇒ 15 ⇒ 7 ⇒ 131 ⇒ 65 ⇒ 32 ⇒ 144 ⇒ 72 ⇒ 36 ⇒ 146 ⇒ 73 ⇒ 164 ⇒ 82 ⇒ 41 ⇒ 148 ⇒ 74 ⇒ 37 ⇒ 18 ⇒ 137 ⇒ 196 ⇒ 98 ⇒ 49 ⇒ 152 ⇒ 204 ⇒ 230 ⇒ 243 ⇒ 249 ⇒ 124 ⇒ 62 ⇒ 159 ⇒ 79 ⇒ 167 ⇒ 211 ⇒ 105 ⇒ 52 ⇒ 26 ⇒ 13 ⇒ 6 ⇒ 3
Period = 85 (autocorrelation)
Output =
1100000010100010011110101010110101001110110100101111000001001001
010010001100111110010...

Sequence #4 (Starting with 5)
States: 5 ⇒ 130 ⇒ 193 ⇒ 224 ⇒ 240 ⇒ 120 ⇒ 60 ⇒ 158 ⇒ 207 ⇒ 103 ⇒ 179 ⇒ 89 ⇒ 44 ⇒ 22 ⇒ 139 ⇒ 197 ⇒ 226 ⇒ 241 ⇒ 248 ⇒ 252 ⇒ 254 ⇒ 255 ⇒ 127 ⇒ 191 ⇒ 223 ⇒ 239 ⇒ 247 ⇒ 251 ⇒ 125 ⇒ 190 ⇒ 95 ⇒ 47 ⇒ 151 ⇒ 203 ⇒ 101 ⇒ 178 ⇒ 217 ⇒ 236 ⇒ 118 ⇒ 187 ⇒ 221 ⇒ 238 ⇒ 119 ⇒ 59 ⇒ 29 ⇒ 142 ⇒ 71 ⇒ 35 ⇒ 17 ⇒ 8 ⇒ 132 ⇒ 194 ⇒ 97 ⇒ 176 ⇒ 216 ⇒ 108 ⇒ 182 ⇒ 219 ⇒ 237 ⇒ 246 ⇒ 123 ⇒ 189 ⇒ 222 ⇒ 111 ⇒ 55 ⇒ 155 ⇒ 77 ⇒ 166 ⇒ 83 ⇒ 169 ⇒ 84 ⇒ 42 ⇒ 21 ⇒ 10 ⇒ 133 ⇒ 66 ⇒ 161 ⇒ 208 ⇒ 232 ⇒ 116 ⇒ 186 ⇒ 93 ⇒ 46 ⇒ 23 ⇒ 11 ⇒ 5
Period = 85 (autocorrelation)
Output =
1010000011110011010001111111101111101001101110111000100001101101
111011001010100001011...

In this example, a prime polynomial failed to give a maximum length sequence. For this polynomial of degree 8, the maximum length sequence would have a period of 28-1 states. Use of a prime polynomial is a necessary but not sufficient condition for a maximum length sequence. Only "primitive primes" give maximum length sequences.

See a detailed analysis and State Table for this circuit.
Specify the taps for your sequence
Binary Value:    Reversed
Modulo 2 addition is shown schematically equivalent to Exclusive-OR gates.

dot
Thu May 23 19:01:02 ADT 2013
Last Updated: 28 NOV 98 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...
dot