
	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) = (100111111).

Taps: (100111111) (prime)

Sequence #1 (Starting with 0)

States: 0 0 forever...

Sequence #2 (Starting with 1)

States: 1 128 64 32 144 200 228 114 185 92 174 87 43 21 138 69 34 17 8 132 194 225 112 56 156 206 231 115 57 28 142 199 227 241 248 252 126 191 95 175 215 107 53 26 141 198 99 177 216 108 182 91 45 22 139 197 98 49 152 76 38 147 201 100 50 153 204 102 179 89 172 214 235 117 58 29 14 135 195 97 48 24 12 6 3 1

Period = 85 (autocorrelation)
Output =
1000000010011101010001000011100111000111111010110001101101000110
010011001101011100001...

Sequence #3 (Starting with 2)

States: 2 129 192 96 176 88 44 150 203 229 242 249 124 62 159 207 103 51 25 140 70 35 145 72 164 82 41 148 74 37 146 73 36 18 9 4 130 193 224 240 120 188 94 47 151 75 165 210 105 180 218 237 118 59 157 78 167 83 169 212 106 181 90 173 86 171 85 170 213 234 245 122 61 158 79 39 19 137 68 162 81 40 20 10 5 2

Period = 85 (autocorrelation)
Output =
0100000011010011111001100010010100100100000111101001011011100101
011010101011110010001...

Sequence #4 (Starting with 7)

States: 7 131 65 160 208 232 116 186 93 46 23 11 133 66 161 80 168 84 42 149 202 101 178 217 236 246 123 189 222 111 183 219 109 54 27 13 134 67 33 16 136 196 226 113 184 220 238 119 187 221 110 55 155 77 166 211 233 244 250 125 190 223 239 247 251 253 254 255 127 63 31 143 71 163 209 104 52 154 205 230 243 121 60 30 15 7

Period = 85 (autocorrelation)
Output =
1110000010111010000101010011011110110110000100011101110110010111
110111111110001011001...

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 20:57:59 ADT Last Updated: 2014-01-13	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...