
	ECE4253 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). 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) = x⁸+x⁶+x⁵+x⁴+x²+x+1

The circuit taps correspond to P(x) = (101110111).

Taps: (101110111) (prime)

Sequence #1 (Starting with 0)

States: 0 0 forever...

Sequence #2 (Starting with 1)

States: 1 128 64 160 208 104 52 154 77 166 211 105 180 218 237 118 187 93 46 151 75 165 210 233 244 122 61 30 143 199 99 49 152 204 102 51 25 12 134 67 161 80 40 148 74 37 146 73 36 18 9 132 194 97 176 88 44 22 139 69 162 81 168 212 234 245 250 125 190 95 175 87 171 213 106 181 90 173 214 107 53 26 13 6 3 1

Period = 85 (autocorrelation)
Output =
1000000010110010110111010010111100011001100001010010010000110100
010101111101010110101...

Sequence #3 (Starting with 2)

States: 2 129 192 224 112 184 92 174 215 235 117 186 221 110 55 155 205 230 115 185 220 238 119 59 29 142 71 35 145 72 164 82 169 84 170 85 42 21 138 197 226 241 120 188 222 111 183 219 109 54 27 141 70 163 209 232 116 58 157 206 231 243 249 124 62 31 15 135 195 225 240 248 252 126 191 223 239 247 123 189 94 47 23 11 5 2

Period = 85 (autocorrelation)
Output =
0100000011101011101100111011100010010101010001111011011000101110
011111000011111101111...

Sequence #4 (Starting with 4)

States: 4 130 193 96 48 24 140 198 227 113 56 28 14 7 131 65 32 144 200 228 242 121 60 158 207 103 179 89 172 86 43 149 202 101 50 153 76 38 147 201 100 178 217 236 246 251 253 254 255 127 63 159 79 39 19 137 196 98 177 216 108 182 91 45 150 203 229 114 57 156 78 167 83 41 20 10 133 66 33 16 136 68 34 17 8 4

Period = 85 (autocorrelation)
Output =
0010000011000111000001001111001101010011001001101111111100100011
011010011100101000010...

See a detailed analysis and State Table for this circuit.

Specify the taps for your sequence

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


2024-04-28 16:36:59 ADT Last Updated: 2014-01-13	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...