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

Taps: (110111101) (prime)

Sequence #1 (Starting with 0)

States: 0 0 forever...

Sequence #2 (Starting with 1)

States: 1 128 192 224 112 56 156 78 39 147 201 228 242 249 252 254 255 127 191 95 47 23 139 197 226 113 184 92 174 87 171 85 170 213 106 53 26 13 134 67 161 208 104 52 154 205 102 51 153 76 38 19 9 4 130 193 96 176 216 236 118 187 221 238 119 59 29 14 7 3 129 64 32 144 72 164 210 105 180 90 45 22 11 5 2 1

Period = 85 (autocorrelation)
Output =
1000000011100100111111110100011101010101100001011001100100000110
111011100000010010110...

Sequence #3 (Starting with 6)

States: 6 131 65 160 80 168 212 234 245 250 125 190 223 239 247 251 253 126 63 159 207 103 179 89 172 86 43 149 74 165 82 169 84 42 21 138 69 34 145 200 100 50 25 140 198 99 49 152 204 230 243 121 60 30 143 71 35 17 8 132 66 33 16 136 68 162 81 40 20 10 133 194 225 240 248 124 62 31 15 135 195 97 48 24 12 6

Period = 85 (autocorrelation)
Output =
0110000010101111101111110011010100101010001001100011001111000100
001000101000011111000...

Sequence #4 (Starting with 18)

States: 18 137 196 98 177 88 44 150 203 229 114 57 28 142 199 227 241 120 188 222 111 55 27 141 70 163 209 232 244 122 189 94 175 215 107 181 218 237 246 123 61 158 79 167 83 41 148 202 101 178 217 108 182 91 173 214 235 117 58 157 206 231 115 185 220 110 183 219 109 54 155 77 166 211 233 116 186 93 46 151 75 37 146 73 36 18

Period = 85 (autocorrelation)
Output =
0100100011010011100011110110001011110101101111001010011011010111
001110110110010111010...

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