
	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+1

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

Taps: (110100011) (prime)

Sequence #1 (Starting with 0)

States: 0 0 forever...

Sequence #2 (Starting with 1)

States: 1 128 192 224 112 184 92 46 23 11 5 130 65 160 80 40 148 202 101 50 25 140 198 99 177 216 236 118 59 157 78 167 83 41 20 10 133 66 161 208 232 116 186 221 110 55 155 205 102 51 153 76 38 19 9 132 194 97 48 152 204 230 243 121 60 158 79 39 147 201 100 178 217 108 182 219 237 246 251 125 62 31 15 7 3 1

Period = 85 (autocorrelation)
Output =
1000000011101000001010011000110111001010000101110110011001000011
001111001001101101111...

Sequence #3 (Starting with 2)

States: 2 129 64 32 144 200 228 114 57 28 14 135 195 225 240 120 188 94 175 87 43 149 74 165 210 105 52 154 77 166 211 233 244 122 61 30 143 199 227 113 56 156 206 103 179 89 172 86 171 85 170 213 106 53 26 141 70 163 81 168 84 42 21 138 69 162 209 104 180 90 173 214 107 181 218 109 54 27 13 134 67 33 16 8 4 2

Period = 85 (autocorrelation)
Output =
0100000010011100001111010100101100101111000111001101010101100010
101000101101011011000...

Sequence #4 (Starting with 6)

States: 6 131 193 96 176 88 44 150 75 37 18 137 68 34 17 136 196 226 241 248 124 190 223 239 119 187 93 174 215 235 117 58 29 142 71 35 145 72 36 146 73 164 82 169 212 234 245 250 253 254 255 127 191 95 47 151 203 229 242 249 252 126 63 159 207 231 115 185 220 238 247 123 189 222 111 183 91 45 22 139 197 98 49 24 12 6

Period = 85 (autocorrelation)
Output =
0110000011010010001000111110111010111000100100101011111111010011
111100111011110110100...

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