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

Taps: (101111011) (prime)

Sequence #1 (Starting with 0)

States: 0 0 forever...

Sequence #2 (Starting with 1)

States: 1 128 64 160 208 104 180 90 45 150 75 37 18 9 4 2 129 192 224 112 184 220 238 119 187 221 110 55 27 13 6 131 65 32 144 200 100 50 153 204 102 179 89 44 22 11 133 194 97 176 88 172 86 171 85 170 213 234 117 58 29 142 71 163 209 232 244 250 253 254 255 127 63 159 79 39 147 201 228 114 57 28 14 7 3 1

Period = 85 (autocorrelation)
Output =
1000000010110100100000011101110110000010011001101000011010101011
100010111111110010011...

Sequence #3 (Starting with 5)

States: 5 130 193 96 48 24 12 134 195 225 240 248 124 62 31 15 135 67 161 80 40 20 138 69 34 17 8 132 66 33 16 136 196 226 241 120 60 158 207 103 51 25 140 198 99 49 152 76 38 19 137 68 162 81 168 84 42 149 74 165 82 169 212 106 53 154 205 230 243 249 252 126 191 223 239 247 251 125 190 95 175 87 43 21 10 5

Period = 85 (autocorrelation)
Output =
1010000011000011111000010100010000100011110011000110010001010100
101011001111110111110...

Sequence #4 (Starting with 23)

States: 23 139 197 98 177 216 236 246 123 61 30 143 199 227 113 56 156 78 167 211 105 52 26 141 70 35 145 72 36 146 73 164 210 233 116 186 93 46 151 203 101 178 217 108 182 219 237 118 59 157 206 231 115 185 92 174 215 107 181 218 109 54 155 77 166 83 41 148 202 229 242 121 188 222 111 183 91 173 214 235 245 122 189 94 47 23

Period = 85 (autocorrelation)
Output =
1110100011011110001110010110001001001011101001101101110011101011
011001010011110110101...

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