As mentioned in the three-bit shift register article, one of the applications for non-maximal length LFSRs/NLFSRs is in angle sensors. I had read an article on generating LFSRs of a given length. For the 360 element case, it came up with a 15b LFSR as the smallest case. Using my NLFSR python app, I found a 10b, 3 input function NLFSR that had 360 elements.
The first attempts to get a 360 element shift register involved attempting to see if a 3 input function would work with 9b or 10b. 10b did work.
Next, I decided to try 4 input functions. There are exponentially more 4 input functions (64k) than 3 input functions (256). So while the 3 input function apps took a few minutes to complete for 9b or 10b NLFSRs, the 4 input version would take hours.
So I decided to look only for one case — the 360 element case. This meant that, for a given NLFSR, once I had seen cycles containing 
The next optimization was made by realizing that each NLFSR is an automorphism of one other NLFSR. A mapping that swaps 1’s and 0’s will give the same sequence where a 0 is shifted in instead of a 1, and a 1 instead of a 0. Thus half of the search space could be ignored if a simple check is done before attempting the feedback function for any other NLFSR parameters.
For the 9b case, no 360 element sequences were found. As a result, the code ran for about 45 minutes and finished. Thus, if a 9b NLFSR exists with 360 elements, it isn’t based on 2, 3, or 4 input functions. The number of 5-input functions is quite large.
The resulting 10b NLFSR and its automorphism are shown below:
- C = b9, B = b8, A = b2. S = !B!A + !C!A + CBA. init = 73.
- C = b9, B = b8, A = b2. S = B!A + C!A + !C!BA, init = 950
Again, not an elegant feedback function, but it does work. The sequence uses a smaller number of bits compared to the smallest LFSR, and does so by 5 bits. The sequence generated, in hex, is:
049 092 124 249 093 126 24d 09b 136 26d 0db 1b6 36d 2da 1b5 36b 2d7 1af 35f 2be 17d 2fb 1f7 3ef 3de 3bc 378 2f1 1e3 3c6 38c 318 231 063 0c6 18c 319 233 067 0ce 19c 339 273 0e7 1ce 39d 33a 275 0eb 1d6 3ad 35a 2b5 16b 2d6 1ad 35b 2b7 16f 2df 1bf 37f 2fe 1fd 3fb 3f7 3ee 3dc 3b8 371 2e3 1c7 38f 31e 23c 079 0f2 1e4 3c9 393 327 24e 09d 13a 274 0e9 1d2 3a4 348 291 123 246 08d 11a 234 069 0d2 1a4 349 293 127 24f 09f 13e 27d 0fb 1f6 3ed 3da 3b5 36a 2d5 1ab 356 2ac 159 2b2 165 2cb 197 32f 25e 0bd 17a 2f4 1e9 3d2 3a5 34a 295 12b 256 0ad 15a 2b4 169 2d2 1a5 34b 297 12f 25f 0bf 17e 2fd 1fb 3f6 3ec 3d8 3b1 363 2c7 18f 31f 23e 07d 0fa 1f4 3e9 3d3 3a7 34e 29c 139 272 0e5 1ca 394 328 251 0a3 146 28d 11b 236 06d 0da 1b4 369 2d3 1a7 34f 29e 13d 27b 0f7 1ee 3dd 3ba 375 2ea 1d5 3ab 357 2ae 15d 2bb 177 2ef 1df 3bf 37e 2fc 1f9 3f2 3e5 3ca 395 32a 255 0ab 156 2ad 15b 2b6 16d 2db 1b7 36f 2de 1bd 37b 2f7 1ef 3df 3be 37c 2f8 1f1 3e2 3c5 38a 315 22a 055 0aa 154 2a9 153 2a6 14d 29b 137 26f 0df 1be 37d 2fa 1f5 3eb 3d7 3ae 35c 2b8 171 2e2 1c5 38b 317 22e 05d 0ba 174 2e9 1d3 3a6 34c 298 131 262 0c5 18a 314 228 051 0a2 144 289 113 226 04d 09a 134 269 0d3 1a6 34d 29a 135 26b 0d7 1ae 35d 2ba 175 2eb 1d7 3af 35e 2bc 179 2f2 1e5 3cb 397 32e 25c 0b9 172 2e4 1c9 392 325 24a 095 12a 254 0a9 152 2a4 149 292 125 24b 097 12e 25d 0bb 176 2ed 1db 3b6 36c 2d8 1b1 362 2c5 18b 316 22c 059 0b2 164 2c9 193 326 24c 099 132 264 0c9 192 324 248 091 122 244 089 112 224 END 049
Thus, a 10b NLFSR can be generated for the 360 element case, but the shorter 9b version is still elusive.