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+x6+x4+x3+x2+x+1

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

Sequence #2 (Starting with 1)
States: 1 ⇒ 128 ⇒ 64 ⇒ 160 ⇒ 80 ⇒ 40 ⇒ 148 ⇒ 74 ⇒ 165 ⇒ 82 ⇒ 169 ⇒ 84 ⇒ 170 ⇒ 85 ⇒ 42 ⇒ 21 ⇒ 138 ⇒ 69 ⇒ 162 ⇒ 209 ⇒ 232 ⇒ 116 ⇒ 186 ⇒ 221 ⇒ 238 ⇒ 119 ⇒ 187 ⇒ 93 ⇒ 174 ⇒ 215 ⇒ 235 ⇒ 117 ⇒ 58 ⇒ 157 ⇒ 78 ⇒ 39 ⇒ 147 ⇒ 201 ⇒ 228 ⇒ 114 ⇒ 185 ⇒ 220 ⇒ 110 ⇒ 55 ⇒ 27 ⇒ 13 ⇒ 134 ⇒ 67 ⇒ 161 ⇒ 208 ⇒ 104 ⇒ 52 ⇒ 26 ⇒ 141 ⇒ 198 ⇒ 227 ⇒ 241 ⇒ 248 ⇒ 252 ⇒ 126 ⇒ 191 ⇒ 223 ⇒ 111 ⇒ 183 ⇒ 91 ⇒ 173 ⇒ 214 ⇒ 107 ⇒ 53 ⇒ 154 ⇒ 205 ⇒ 102 ⇒ 179 ⇒ 217 ⇒ 108 ⇒ 182 ⇒ 219 ⇒ 237 ⇒ 118 ⇒ 59 ⇒ 29 ⇒ 14 ⇒ 135 ⇒ 195 ⇒ 225 ⇒ 112 ⇒ 56 ⇒ 28 ⇒ 142 ⇒ 199 ⇒ 99 ⇒ 177 ⇒ 88 ⇒ 172 ⇒ 86 ⇒ 43 ⇒ 149 ⇒ 202 ⇒ 229 ⇒ 242 ⇒ 249 ⇒ 124 ⇒ 62 ⇒ 31 ⇒ 143 ⇒ 71 ⇒ 35 ⇒ 17 ⇒ 8 ⇒ 132 ⇒ 194 ⇒ 97 ⇒ 48 ⇒ 152 ⇒ 76 ⇒ 166 ⇒ 83 ⇒ 41 ⇒ 20 ⇒ 10 ⇒ 5 ⇒ 2 ⇒ 129 ⇒ 192 ⇒ 224 ⇒ 240 ⇒ 120 ⇒ 188 ⇒ 222 ⇒ 239 ⇒ 247 ⇒ 251 ⇒ 253 ⇒ 254 ⇒ 255 ⇒ 127 ⇒ 63 ⇒ 159 ⇒ 207 ⇒ 231 ⇒ 115 ⇒ 57 ⇒ 156 ⇒ 206 ⇒ 103 ⇒ 51 ⇒ 153 ⇒ 204 ⇒ 230 ⇒ 243 ⇒ 121 ⇒ 60 ⇒ 158 ⇒ 79 ⇒ 167 ⇒ 211 ⇒ 105 ⇒ 180 ⇒ 90 ⇒ 45 ⇒ 150 ⇒ 203 ⇒ 101 ⇒ 178 ⇒ 89 ⇒ 44 ⇒ 22 ⇒ 139 ⇒ 197 ⇒ 226 ⇒ 113 ⇒ 184 ⇒ 92 ⇒ 46 ⇒ 151 ⇒ 75 ⇒ 37 ⇒ 18 ⇒ 9 ⇒ 4 ⇒ 130 ⇒ 193 ⇒ 96 ⇒ 176 ⇒ 216 ⇒ 236 ⇒ 246 ⇒ 123 ⇒ 189 ⇒ 94 ⇒ 175 ⇒ 87 ⇒ 171 ⇒ 213 ⇒ 106 ⇒ 181 ⇒ 218 ⇒ 109 ⇒ 54 ⇒ 155 ⇒ 77 ⇒ 38 ⇒ 19 ⇒ 137 ⇒ 68 ⇒ 34 ⇒ 145 ⇒ 72 ⇒ 36 ⇒ 146 ⇒ 73 ⇒ 164 ⇒ 210 ⇒ 233 ⇒ 244 ⇒ 250 ⇒ 125 ⇒ 190 ⇒ 95 ⇒ 47 ⇒ 23 ⇒ 11 ⇒ 133 ⇒ 66 ⇒ 33 ⇒ 144 ⇒ 200 ⇒ 100 ⇒ 50 ⇒ 25 ⇒ 140 ⇒ 70 ⇒ 163 ⇒ 81 ⇒ 168 ⇒ 212 ⇒ 234 ⇒ 245 ⇒ 122 ⇒ 61 ⇒ 30 ⇒ 15 ⇒ 7 ⇒ 131 ⇒ 65 ⇒ 32 ⇒ 16 ⇒ 136 ⇒ 196 ⇒ 98 ⇒ 49 ⇒ 24 ⇒ 12 ⇒ 6 ⇒ 3 ⇒ 1
Period = 255 (Maximum Length Sequence) (autocorrelation)
Output =
1000000010100101010100010111011101011100100111011000010110001111
1101101011001101101110000111000110101001111100010000110010100000
0111101111111100111001100111100101101001101000111010010000011011
110101011011001000100100101111101000010011000101011110000010001...

A maximum length sequence was found. For this polynomial of degree 8, the maximum length sequence has a period of 28-1 states. This only happens when the characteristic polynomial is prime, as in this case. Use of a prime polynomial is a necessary but not sufficient condition for a maximum length sequence. For example, try 1001001 which is prime, but does not give a maximum length sequence.

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
Mon May 20 13:12:02 ADT 2013
Last Updated: 28 NOV 98 		Richard Tervo [ tervo@unb.ca ] Back to the course homepage...
dot