Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
| |
|
|
EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada |
| |
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).
alternate configuration
Circuit based on P(x) = x8+x7+x5+x4+x3+x2+1
| 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... |
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 28-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. |
| Modulo 2 addition is shown schematically equivalent to Exclusive-OR gates. | 
|
| ||
|
Wed May 22 16:53:25 ADT 2013
Last Updated: 28 NOV 98 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |
| ||