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

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