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

Galois Implementation

alternate configuration Galois

Circuit based on P(x) = x⁸+x⁵+x⁴+x³+x²+x+1

The circuit taps correspond to P(x) = (100111111) in reversed order as (111111001).

Taps: (111111001) (prime)

Sequence #1 (Starting with 0)

States: 0 ⇒ 0, forever...

Sequence #2 (Starting with 1)

States: 1 ⇒ 252 ⇒ 126 ⇒ 63 ⇒ 227 ⇒ 141 ⇒ 186 ⇒ 93 ⇒ 210 ⇒ 105 ⇒ 200 ⇒ 100 ⇒ 50 ⇒ 25 ⇒ 240 ⇒ 120 ⇒ 60 ⇒ 30 ⇒ 15 ⇒ 251 ⇒ 129 ⇒ 188 ⇒ 94 ⇒ 47 ⇒ 235 ⇒ 137 ⇒ 184 ⇒ 92 ⇒ 46 ⇒ 23 ⇒ 247 ⇒ 135 ⇒ 191 ⇒ 163 ⇒ 173 ⇒ 170 ⇒ 85 ⇒ 214 ⇒ 107 ⇒ 201 ⇒ 152 ⇒ 76 ⇒ 38 ⇒ 19 ⇒ 245 ⇒ 134 ⇒ 67 ⇒ 221 ⇒ 146 ⇒ 73 ⇒ 216 ⇒ 108 ⇒ 54 ⇒ 27 ⇒ 241 ⇒ 132 ⇒ 66 ⇒ 33 ⇒ 236 ⇒ 118 ⇒ 59 ⇒ 225 ⇒ 140 ⇒ 70 ⇒ 35 ⇒ 237 ⇒ 138 ⇒ 69 ⇒ 222 ⇒ 111 ⇒ 203 ⇒ 153 ⇒ 176 ⇒ 88 ⇒ 44 ⇒ 22 ⇒ 11 ⇒ 249 ⇒ 128 ⇒ 64 ⇒ 32 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1

Period = 85 (autocorrelation)
Output =
1001110101000100001110011100011111101011000110110100011001001100
110101110000110000000...

Sequence #3 (Starting with 3)

States: 3 ⇒ 253 ⇒ 130 ⇒ 65 ⇒ 220 ⇒ 110 ⇒ 55 ⇒ 231 ⇒ 143 ⇒ 187 ⇒ 161 ⇒ 172 ⇒ 86 ⇒ 43 ⇒ 233 ⇒ 136 ⇒ 68 ⇒ 34 ⇒ 17 ⇒ 244 ⇒ 122 ⇒ 61 ⇒ 226 ⇒ 113 ⇒ 196 ⇒ 98 ⇒ 49 ⇒ 228 ⇒ 114 ⇒ 57 ⇒ 224 ⇒ 112 ⇒ 56 ⇒ 28 ⇒ 14 ⇒ 7 ⇒ 255 ⇒ 131 ⇒ 189 ⇒ 162 ⇒ 81 ⇒ 212 ⇒ 106 ⇒ 53 ⇒ 230 ⇒ 115 ⇒ 197 ⇒ 158 ⇒ 79 ⇒ 219 ⇒ 145 ⇒ 180 ⇒ 90 ⇒ 45 ⇒ 234 ⇒ 117 ⇒ 198 ⇒ 99 ⇒ 205 ⇒ 154 ⇒ 77 ⇒ 218 ⇒ 109 ⇒ 202 ⇒ 101 ⇒ 206 ⇒ 103 ⇒ 207 ⇒ 155 ⇒ 177 ⇒ 164 ⇒ 82 ⇒ 41 ⇒ 232 ⇒ 116 ⇒ 58 ⇒ 29 ⇒ 242 ⇒ 121 ⇒ 192 ⇒ 96 ⇒ 48 ⇒ 24 ⇒ 12 ⇒ 6 ⇒ 3

Period = 85 (autocorrelation)
Output =
1101001111100110001001010010010000011110100101101110010101101010
101111001000101000000...

Sequence #4 (Starting with 5)

States: 5 ⇒ 254 ⇒ 127 ⇒ 195 ⇒ 157 ⇒ 178 ⇒ 89 ⇒ 208 ⇒ 104 ⇒ 52 ⇒ 26 ⇒ 13 ⇒ 250 ⇒ 125 ⇒ 194 ⇒ 97 ⇒ 204 ⇒ 102 ⇒ 51 ⇒ 229 ⇒ 142 ⇒ 71 ⇒ 223 ⇒ 147 ⇒ 181 ⇒ 166 ⇒ 83 ⇒ 213 ⇒ 150 ⇒ 75 ⇒ 217 ⇒ 144 ⇒ 72 ⇒ 36 ⇒ 18 ⇒ 9 ⇒ 248 ⇒ 124 ⇒ 62 ⇒ 31 ⇒ 243 ⇒ 133 ⇒ 190 ⇒ 95 ⇒ 211 ⇒ 149 ⇒ 182 ⇒ 91 ⇒ 209 ⇒ 148 ⇒ 74 ⇒ 37 ⇒ 238 ⇒ 119 ⇒ 199 ⇒ 159 ⇒ 179 ⇒ 165 ⇒ 174 ⇒ 87 ⇒ 215 ⇒ 151 ⇒ 183 ⇒ 167 ⇒ 175 ⇒ 171 ⇒ 169 ⇒ 168 ⇒ 84 ⇒ 42 ⇒ 21 ⇒ 246 ⇒ 123 ⇒ 193 ⇒ 156 ⇒ 78 ⇒ 39 ⇒ 239 ⇒ 139 ⇒ 185 ⇒ 160 ⇒ 80 ⇒ 40 ⇒ 20 ⇒ 10 ⇒ 5

Period = 85 (autocorrelation)
Output =
1011101000010101001101111011011000010001110111011001011111011111
111000101100111100000...

In this example, a prime polynomial failed to give a maximum length sequence. For this polynomial of degree 8, the maximum length sequence would have a period of 2⁸-1 states. Use of a prime polynomial is a necessary but not sufficient condition for a maximum length sequence. Only "primitive primes" give maximum length sequences.

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-05-14 18:33:40 ADT Last Updated: 04-09-25	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...