
	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) = (101011111) in reversed order as (111110101).

Taps: (111110101) (prime)

Sequence #1 (Starting with 0)

States: 0 ⇒ 0, forever...

Sequence #2 (Starting with 1)

States: 1 ⇒ 250 ⇒ 125 ⇒ 196 ⇒ 98 ⇒ 49 ⇒ 226 ⇒ 113 ⇒ 194 ⇒ 97 ⇒ 202 ⇒ 101 ⇒ 200 ⇒ 100 ⇒ 50 ⇒ 25 ⇒ 246 ⇒ 123 ⇒ 199 ⇒ 153 ⇒ 182 ⇒ 91 ⇒ 215 ⇒ 145 ⇒ 178 ⇒ 89 ⇒ 214 ⇒ 107 ⇒ 207 ⇒ 157 ⇒ 180 ⇒ 90 ⇒ 45 ⇒ 236 ⇒ 118 ⇒ 59 ⇒ 231 ⇒ 137 ⇒ 190 ⇒ 95 ⇒ 213 ⇒ 144 ⇒ 72 ⇒ 36 ⇒ 18 ⇒ 9 ⇒ 254 ⇒ 127 ⇒ 197 ⇒ 152 ⇒ 76 ⇒ 38 ⇒ 19 ⇒ 243 ⇒ 131 ⇒ 187 ⇒ 167 ⇒ 169 ⇒ 174 ⇒ 87 ⇒ 209 ⇒ 146 ⇒ 73 ⇒ 222 ⇒ 111 ⇒ 205 ⇒ 156 ⇒ 78 ⇒ 39 ⇒ 233 ⇒ 142 ⇒ 71 ⇒ 217 ⇒ 150 ⇒ 75 ⇒ 223 ⇒ 149 ⇒ 176 ⇒ 88 ⇒ 44 ⇒ 22 ⇒ 11 ⇒ 255 ⇒ 133 ⇒ 184 ⇒ 92 ⇒ 46 ⇒ 23 ⇒ 241 ⇒ 130 ⇒ 65 ⇒ 218 ⇒ 109 ⇒ 204 ⇒ 102 ⇒ 51 ⇒ 227 ⇒ 139 ⇒ 191 ⇒ 165 ⇒ 168 ⇒ 84 ⇒ 42 ⇒ 21 ⇒ 240 ⇒ 120 ⇒ 60 ⇒ 30 ⇒ 15 ⇒ 253 ⇒ 132 ⇒ 66 ⇒ 33 ⇒ 234 ⇒ 117 ⇒ 192 ⇒ 96 ⇒ 48 ⇒ 24 ⇒ 12 ⇒ 6 ⇒ 3 ⇒ 251 ⇒ 135 ⇒ 185 ⇒ 166 ⇒ 83 ⇒ 211 ⇒ 147 ⇒ 179 ⇒ 163 ⇒ 171 ⇒ 175 ⇒ 173 ⇒ 172 ⇒ 86 ⇒ 43 ⇒ 239 ⇒ 141 ⇒ 188 ⇒ 94 ⇒ 47 ⇒ 237 ⇒ 140 ⇒ 70 ⇒ 35 ⇒ 235 ⇒ 143 ⇒ 189 ⇒ 164 ⇒ 82 ⇒ 41 ⇒ 238 ⇒ 119 ⇒ 193 ⇒ 154 ⇒ 77 ⇒ 220 ⇒ 110 ⇒ 55 ⇒ 225 ⇒ 138 ⇒ 69 ⇒ 216 ⇒ 108 ⇒ 54 ⇒ 27 ⇒ 247 ⇒ 129 ⇒ 186 ⇒ 93 ⇒ 212 ⇒ 106 ⇒ 53 ⇒ 224 ⇒ 112 ⇒ 56 ⇒ 28 ⇒ 14 ⇒ 7 ⇒ 249 ⇒ 134 ⇒ 67 ⇒ 219 ⇒ 151 ⇒ 177 ⇒ 162 ⇒ 81 ⇒ 210 ⇒ 105 ⇒ 206 ⇒ 103 ⇒ 201 ⇒ 158 ⇒ 79 ⇒ 221 ⇒ 148 ⇒ 74 ⇒ 37 ⇒ 232 ⇒ 116 ⇒ 58 ⇒ 29 ⇒ 244 ⇒ 122 ⇒ 61 ⇒ 228 ⇒ 114 ⇒ 57 ⇒ 230 ⇒ 115 ⇒ 195 ⇒ 155 ⇒ 183 ⇒ 161 ⇒ 170 ⇒ 85 ⇒ 208 ⇒ 104 ⇒ 52 ⇒ 26 ⇒ 13 ⇒ 252 ⇒ 126 ⇒ 63 ⇒ 229 ⇒ 136 ⇒ 68 ⇒ 34 ⇒ 17 ⇒ 242 ⇒ 121 ⇒ 198 ⇒ 99 ⇒ 203 ⇒ 159 ⇒ 181 ⇒ 160 ⇒ 80 ⇒ 40 ⇒ 20 ⇒ 10 ⇒ 5 ⇒ 248 ⇒ 124 ⇒ 62 ⇒ 31 ⇒ 245 ⇒ 128 ⇒ 64 ⇒ 32 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1

Period = 255 (Maximum Length Sequence) (autocorrelation)
Output =
1010010101010001011101110101110010011101100001011000111111011010
1100110110111000011100011010100111110001000011001010000001111011
1111110011100110011110010110100110100011101001000001101111010101
101100100010010010111110100001001100010101111000001000110000000...

A maximum length sequence was found. For this polynomial of degree 8, the maximum length sequence has a period of 2⁸-1 states. This only happens when the characteristic polynomial is prime, as in this case. Use of a prime polynomial is a necessary but not sufficient condition for a maximum length sequence. For example, try 1010111 which is prime, but does not give a maximum length sequence.

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-15 19:22:02 ADT Last Updated: 04-09-25	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...