Linear Feedback Shift Registers for the Uninitiated, Part X: Counters and Encoders
Last time we looked at LFSR output decimation and the computation of trace parity.
Today we are starting to look in detail at some applications of LFSRs, namely counters and encoders.
Counters
I mentioned counters briefly in the article on easy discrete logarithms. The idea here is that the propagation delay in an LFSR is smaller than in a counter, since the logic to compute the next LFSR state is simpler than in an ordinary counter. All you need to construct an LFSR is a bunch of flip-flops and a couple of XORs, one for each nonzero term in the characteristic polynomial. If the polynomial is a primitive polynomial, then the LFSR cycles through all nonzero patterns, for a total of \( 2^ N-1 \) states in an \( N \)-bit LFSR, after which the same series repeats, having a period of \( 2^N-1 \).
The challenge in this sort of application is not implementing an LFSR, but rather in decoding the count from the LFSR state, which amounts to a discrete logarithm. It is therefore advantageous to use an LFSR with a period that is smooth — that is, it consists of the product of a bunch of small factors, so that the Silver-Pohlig-Hellman algorithm can be used to decode the count. (Again, see that article on easy discrete logarithms for details.)
The primitive polynomials generating periods that are smooth are somewhat limited; beyond a degree of 60, there are no maximal-length LFSRs with a period having factors no larger than 2500. We can list the factors of the periods for small-degree LFSRs:
import primefac
def factors_to_string(factoring):
return ', '.join(
'%d'%f if factoring[f] == 1
else '%d^%d' % (f,factoring[f])
for f in sorted(factoring.keys(), reverse=True))
for n in xrange(2,72):
factoring = primefac.factorint((1<<n) - 1)
factors = factoring.keys()
if all(k<2500 for k in factors):
print '%2d: [%s]' % (n, factors_to_string(factoring))2: [3] 3: [7] 4: [5, 3] 5: [31] 6: [7, 3^2] 7: [127] 8: [17, 5, 3] 9: [73, 7] 10: [31, 11, 3] 11: [89, 23] 12: [13, 7, 5, 3^2] 14: [127, 43, 3] 15: [151, 31, 7] 16: [257, 17, 5, 3] 18: [73, 19, 7, 3^3] 20: [41, 31, 11, 5^2, 3] 21: [337, 127, 7^2] 22: [683, 89, 23, 3] 24: [241, 17, 13, 7, 5, 3^2] 25: [1801, 601, 31] 28: [127, 113, 43, 29, 5, 3] 29: [2089, 1103, 233] 30: [331, 151, 31, 11, 7, 3^2] 36: [109, 73, 37, 19, 13, 7, 5, 3^3] 44: [2113, 683, 397, 89, 23, 5, 3] 48: [673, 257, 241, 97, 17, 13, 7, 5, 3^2] 60: [1321, 331, 151, 61, 41, 31, 13, 11, 7, 5^2, 3^2]
A maximal-length LFSR with degree 48 is particularly well-suited for the counter application of LFSRs:
- its period has a largest factor of 673, making the calculation of discrete logarithms very fast with modest-size tables
- it is a multiple of 16, so it “plays well” with software
- \( 2^{48} - 1 \approx 2.815 \times 10^{14} \) ticks is a fairly long duration:
- 3.26 days at 1 nanosecond per tick
- 8.92 years at 1 microsecond per tick
- 272 years at a 32.768kHz tick rate
If that’s not long enough, a degree-60 LFSR would roll over at \( 2^{60} - 1 \approx 1.153 \times 10^{18} \) ticks, which is
- 36.56 years at 1 nanosecond per tick
- 36559 years at 1 microsecond per tick
- 1.1 million years at a 32.768kHz tick rate
A paper by Clark and Weng discusses the application of nonprimitive polynomials for LFSR-based counters; these are not maximal-length LFSRs, but they can be made “almost-maximum”. The way to do this is fairly straightforward:
- take primitive polynomials of smaller degrees with periods that have no common factors
- use a characteristic polynomial which is the product of the polynomials in the previous step.
Here’s a simple example of that; suppose we have the primitive polynomials \( x^2+x+1 \) and \( x^3 + x + 1 \). These have periods 3 and 7, respectively:
from libgf2.gf2 import GF2QuotientRing, checkPeriod
f2 = GF2QuotientRing(7)
f3 = GF2QuotientRing(11)
def poly_to_str(bitvector):
terms = []
if bitvector & 1:
terms.append('1')
if bitvector & 2:
terms.append('x')
bitvector >>= 2
k = 2
while bitvector > 0:
if bitvector & 1:
terms.append('x^%d' % k)
k += 1
bitvector >>= 1
return ' + '.join(terms[::-1])
def demonstrate_period(f, expwidth=1):
e = f.wrap(1)
print 'LFSR with p(x) =', poly_to_str(f.coeffs)
for k in xrange(1 << f.degree):
print 'x^{0:<{d}d}: {1:0{n}b}'.format(k, e.coeffs,
n=f.degree,
d=expwidth)
if e.coeffs == 1 and k > 1:
break
e <<= 1
for f in [f2,f3]:
demonstrate_period(f)
print ''LFSR with p(x) = x^2 + x + 1 x^0: 01 x^1: 10 x^2: 11 x^3: 01 LFSR with p(x) = x^3 + x + 1 x^0: 001 x^1: 010 x^2: 100 x^3: 011 x^4: 110 x^5: 111 x^6: 101 x^7: 001
Since 3 and 7 have no common factors, the LFSR with characteristic polynomial that is their product, namely \( x^5 + x^4 + 1 \), has a period of \( 3\times 7 = 21 \):
demonstrate_period(GF2QuotientRing(0b110001), expwidth=2)
LFSR with p(x) = x^5 + x^4 + 1 x^0 : 00001 x^1 : 00010 x^2 : 00100 x^3 : 01000 x^4 : 10000 x^5 : 10001 x^6 : 10011 x^7 : 10111 x^8 : 11111 x^9 : 01111 x^10: 11110 x^11: 01101 x^12: 11010 x^13: 00101 x^14: 01010 x^15: 10100 x^16: 11001 x^17: 00011 x^18: 00110 x^19: 01100 x^20: 11000 x^21: 00001
In other words, we constructed a 5-bit LFSR by partitioning the bit count as 5 = 2+3, and the resulting period is \( (2^2 - 1)(2^3 - 1) = 21 \) which is less than the maximal length of 31, but the maximum factor size is 7 rather than 31.
Below is a list of various partitions that can be used to construct an LFSR with periods having largest factor at most 2000:
def partition(fmap, n, max_n=None, min_n=0, used_factors=()):
if max_n is None:
max_n = n
used_factors=set(used_factors)
allowed = [k for k,v in fmap.iteritems()
if k <= max_n and k >= min_n
and all(f not in used_factors for f in v.keys())]
allowed.sort(reverse=True)
for m in allowed:
mfactors = fmap[m]
mfactor_max = max(mfactors.keys())
if m == n:
yield (mfactor_max, (m,), dict(mfactors))
elif m < n:
uf2 = used_factors | set(fmap[m].keys())
for factor_max, degrees, factors in partition(
fmap, n-m, max_n=m, min_n=min_n, used_factors=uf2):
degrees = (m,)+degrees
mfactors2 = dict(mfactors)
mfactors2.update(factors)
yield max(mfactor_max, factor_max), degrees, mfactors2
# Make a map from bit size to factoring, where factors are at most 2000
fmap = {}
for k in xrange(2,61):
factoring = primefac.factorint((1<<k)-1)
if max(factoring.keys()) <= 2000:
fmap[k] = factoring
for n in xrange(2,150):
for max_factor, degrees, factor_map in partition(fmap, n, min_n=3):
factors_str = factors_to_string(factor_map)
print 'n=%2d%-13s%sfactors=[%s]' % (
n, ' (primitive)' if len(degrees) == 1
else '='+ '+'.join('%d'%d for d in degrees),
' 'if len(factors_str)<50 else '\n ', factors_str)
n= 3 (primitive) factors=[7]
n= 4 (primitive) factors=[5, 3]
n= 5 (primitive) factors=[31]
n= 6 (primitive) factors=[7, 3^2]
n= 7 (primitive) factors=[127]
n= 7=4+3 factors=[7, 5, 3]
n= 8 (primitive) factors=[17, 5, 3]
n= 8=5+3 factors=[31, 7]
n= 9 (primitive) factors=[73, 7]
n= 9=5+4 factors=[31, 5, 3]
n=10 (primitive) factors=[31, 11, 3]
n=10=7+3 factors=[127, 7]
n=11 (primitive) factors=[89, 23]
n=11=8+3 factors=[17, 7, 5, 3]
n=11=7+4 factors=[127, 5, 3]
n=11=6+5 factors=[31, 7, 3^2]
n=12 (primitive) factors=[13, 7, 5, 3^2]
n=12=7+5 factors=[127, 31]
n=12=5+4+3 factors=[31, 7, 5, 3]
n=13=10+3 factors=[31, 11, 7, 3]
n=13=9+4 factors=[73, 7, 5, 3]
n=13=8+5 factors=[31, 17, 5, 3]
n=13=7+6 factors=[127, 7, 3^2]
n=14 (primitive) factors=[127, 43, 3]
n=14=11+3 factors=[89, 23, 7]
n=14=9+5 factors=[73, 31, 7]
n=14=7+4+3 factors=[127, 7, 5, 3]
n=15 (primitive) factors=[151, 31, 7]
n=15=11+4 factors=[89, 23, 5, 3]
n=15=8+7 factors=[127, 17, 5, 3]
n=15=7+5+3 factors=[127, 31, 7]
n=16 (primitive) factors=[257, 17, 5, 3]
n=16=11+5 factors=[89, 31, 23]
n=16=9+7 factors=[127, 73, 7]
n=16=8+5+3 factors=[31, 17, 7, 5, 3]
n=16=7+5+4 factors=[127, 31, 5, 3]
n=17=14+3 factors=[127, 43, 7, 3]
n=17=12+5 factors=[31, 13, 7, 5, 3^2]
n=17=11+6 factors=[89, 23, 7, 3^2]
n=17=10+7 factors=[127, 31, 11, 3]
n=17=9+8 factors=[73, 17, 7, 5, 3]
n=18 (primitive) factors=[73, 19, 7, 3^3]
n=18=11+7 factors=[127, 89, 23]
n=18=11+4+3 factors=[89, 23, 7, 5, 3]
n=18=9+5+4 factors=[73, 31, 7, 5, 3]
n=18=8+7+3 factors=[127, 17, 7, 5, 3]
n=18=7+6+5 factors=[127, 31, 7, 3^2]
n=19=16+3 factors=[257, 17, 7, 5, 3]
n=19=15+4 factors=[151, 31, 7, 5, 3]
n=19=14+5 factors=[127, 43, 31, 3]
n=19=12+7 factors=[127, 13, 7, 5, 3^2]
n=19=11+8 factors=[89, 23, 17, 5, 3]
n=19=11+5+3 factors=[89, 31, 23, 7]
n=19=10+9 factors=[73, 31, 11, 7, 3]
n=19=7+5+4+3 factors=[127, 31, 7, 5, 3]
n=20 (primitive) factors=[41, 31, 11, 5^2, 3]
n=20=11+9 factors=[89, 73, 23, 7]
n=20=11+5+4 factors=[89, 31, 23, 5, 3]
n=20=10+7+3 factors=[127, 31, 11, 7, 3]
n=20=9+7+4 factors=[127, 73, 7, 5, 3]
n=20=8+7+5 factors=[127, 31, 17, 5, 3]
n=21 (primitive) factors=[337, 127, 7^2]
n=21=16+5 factors=[257, 31, 17, 5, 3]
n=21=11+10 factors=[89, 31, 23, 11, 3]
n=21=11+7+3 factors=[127, 89, 23, 7]
n=21=9+7+5 factors=[127, 73, 31, 7]
n=22 (primitive) factors=[683, 89, 23, 3]
n=22=15+7 factors=[151, 127, 31, 7]
n=22=14+5+3 factors=[127, 43, 31, 7, 3]
n=22=11+8+3 factors=[89, 23, 17, 7, 5, 3]
n=22=11+7+4 factors=[127, 89, 23, 5, 3]
n=22=11+6+5 factors=[89, 31, 23, 7, 3^2]
n=22=9+8+5 factors=[73, 31, 17, 7, 5, 3]
n=23=20+3 factors=[41, 31, 11, 7, 5^2, 3]
n=23=18+5 factors=[73, 31, 19, 7, 3^3]
n=23=16+7 factors=[257, 127, 17, 5, 3]
n=23=15+8 factors=[151, 31, 17, 7, 5, 3]
n=23=14+9 factors=[127, 73, 43, 7, 3]
n=23=12+11 factors=[89, 23, 13, 7, 5, 3^2]
n=23=11+7+5 factors=[127, 89, 31, 23]
n=23=11+5+4+3 factors=[89, 31, 23, 7, 5, 3]
n=23=8+7+5+3 factors=[127, 31, 17, 7, 5, 3]
n=24 (primitive) factors=[241, 17, 13, 7, 5, 3^2]
n=24=16+5+3 factors=[257, 31, 17, 7, 5, 3]
n=24=12+7+5 factors=[127, 31, 13, 7, 5, 3^2]
n=24=11+10+3 factors=[89, 31, 23, 11, 7, 3]
n=24=11+9+4 factors=[89, 73, 23, 7, 5, 3]
n=24=11+8+5 factors=[89, 31, 23, 17, 5, 3]
n=24=11+7+6 factors=[127, 89, 23, 7, 3^2]
n=24=9+8+7 factors=[127, 73, 17, 7, 5, 3]
n=25 (primitive) factors=[1801, 601, 31]
n=25=22+3 factors=[683, 89, 23, 7, 3]
n=25=21+4 factors=[337, 127, 7^2, 5, 3]
n=25=18+7 factors=[127, 73, 19, 7, 3^3]
n=25=16+9 factors=[257, 73, 17, 7, 5, 3]
n=25=14+11 factors=[127, 89, 43, 23, 3]
n=25=11+9+5 factors=[89, 73, 31, 23, 7]
n=25=11+7+4+3 factors=[127, 89, 23, 7, 5, 3]
n=25=9+7+5+4 factors=[127, 73, 31, 7, 5, 3]
n=26=21+5 factors=[337, 127, 31, 7^2]
n=26=16+7+3 factors=[257, 127, 17, 7, 5, 3]
n=26=15+11 factors=[151, 89, 31, 23, 7]
n=26=15+7+4 factors=[151, 127, 31, 7, 5, 3]
n=26=11+8+7 factors=[127, 89, 23, 17, 5, 3]
n=26=11+7+5+3 factors=[127, 89, 31, 23, 7]
n=26=10+9+7 factors=[127, 73, 31, 11, 7, 3]
n=27=22+5 factors=[683, 89, 31, 23, 3]
n=27=20+7 factors=[127, 41, 31, 11, 5^2, 3]
n=27=16+11 factors=[257, 89, 23, 17, 5, 3]
n=27=11+9+7 factors=[127, 89, 73, 23, 7]
n=27=11+8+5+3 factors=[89, 31, 23, 17, 7, 5, 3]
n=27=11+7+5+4 factors=[127, 89, 31, 23, 5, 3]
n=28 (primitive) factors=[127, 113, 43, 29, 5, 3]
n=28=25+3 factors=[1801, 601, 31, 7]
n=28=16+7+5 factors=[257, 127, 31, 17, 5, 3]
n=28=14+11+3 factors=[127, 89, 43, 23, 7, 3]
n=28=14+9+5 factors=[127, 73, 43, 31, 7, 3]
n=28=12+11+5 factors=[89, 31, 23, 13, 7, 5, 3^2]
n=28=11+10+7 factors=[127, 89, 31, 23, 11, 3]
n=28=11+9+8 factors=[89, 73, 23, 17, 7, 5, 3]
n=29=25+4 factors=[1801, 601, 31, 5, 3]
n=29=24+5 factors=[241, 31, 17, 13, 7, 5, 3^2]
n=29=22+7 factors=[683, 127, 89, 23, 3]
n=29=21+8 factors=[337, 127, 17, 7^2, 5, 3]
n=29=20+9 factors=[73, 41, 31, 11, 7, 5^2, 3]
n=29=18+11 factors=[89, 73, 23, 19, 7, 3^3]
n=29=15+14 factors=[151, 127, 43, 31, 7, 3]
n=29=11+9+5+4 factors=[89, 73, 31, 23, 7, 5, 3]
n=29=11+8+7+3 factors=[127, 89, 23, 17, 7, 5, 3]
n=29=11+7+6+5 factors=[127, 89, 31, 23, 7, 3^2]
n=29=9+8+7+5 factors=[127, 73, 31, 17, 7, 5, 3]
n=30 (primitive) factors=[331, 151, 31, 11, 7, 3^2]
n=30=22+5+3 factors=[683, 89, 31, 23, 7, 3]
n=30=21+5+4 factors=[337, 127, 31, 7^2, 5, 3]
n=30=20+7+3 factors=[127, 41, 31, 11, 7, 5^2, 3]
n=30=18+7+5 factors=[127, 73, 31, 19, 7, 3^3]
n=30=16+11+3 factors=[257, 89, 23, 17, 7, 5, 3]
n=30=16+9+5 factors=[257, 73, 31, 17, 7, 5, 3]
n=30=15+11+4 factors=[151, 89, 31, 23, 7, 5, 3]
n=30=15+8+7 factors=[151, 127, 31, 17, 7, 5, 3]
n=30=14+11+5 factors=[127, 89, 43, 31, 23, 3]
n=30=12+11+7 factors=[127, 89, 23, 13, 7, 5, 3^2]
n=30=11+10+9 factors=[89, 73, 31, 23, 11, 7, 3]
n=30=11+7+5+4+3 factors=[127, 89, 31, 23, 7, 5, 3]
n=31=28+3 factors=[127, 113, 43, 29, 7, 5, 3]
n=31=25+6 factors=[1801, 601, 31, 7, 3^2]
n=31=24+7 factors=[241, 127, 17, 13, 7, 5, 3^2]
n=31=22+9 factors=[683, 89, 73, 23, 7, 3]
n=31=21+10 factors=[337, 127, 31, 11, 7^2, 3]
n=31=20+11 factors=[89, 41, 31, 23, 11, 5^2, 3]
n=31=16+15 factors=[257, 151, 31, 17, 7, 5, 3]
n=31=16+7+5+3 factors=[257, 127, 31, 17, 7, 5, 3]
n=31=11+10+7+3 factors=[127, 89, 31, 23, 11, 7, 3]
n=31=11+9+7+4 factors=[127, 89, 73, 23, 7, 5, 3]
n=31=11+8+7+5 factors=[127, 89, 31, 23, 17, 5, 3]
n=32=25+7 factors=[1801, 601, 127, 31]
n=32=25+4+3 factors=[1801, 601, 31, 7, 5, 3]
n=32=22+7+3 factors=[683, 127, 89, 23, 7, 3]
n=32=21+11 factors=[337, 127, 89, 23, 7^2]
n=32=16+11+5 factors=[257, 89, 31, 23, 17, 5, 3]
n=32=16+9+7 factors=[257, 127, 73, 17, 7, 5, 3]
n=32=11+9+7+5 factors=[127, 89, 73, 31, 23, 7]
n=33=28+5 factors=[127, 113, 43, 31, 29, 5, 3]
n=33=25+8 factors=[1801, 601, 31, 17, 5, 3]
n=33=15+11+7 factors=[151, 127, 89, 31, 23, 7]
n=33=14+11+5+3 factors=[127, 89, 43, 31, 23, 7, 3]
n=33=11+9+8+5 factors=[89, 73, 31, 23, 17, 7, 5, 3]
n=34=25+9 factors=[1801, 601, 73, 31, 7]
n=34=22+7+5 factors=[683, 127, 89, 31, 23, 3]
n=34=21+8+5 factors=[337, 127, 31, 17, 7^2, 5, 3]
n=34=20+11+3 factors=[89, 41, 31, 23, 11, 7, 5^2, 3]
n=34=18+11+5 factors=[89, 73, 31, 23, 19, 7, 3^3]
n=34=16+11+7 factors=[257, 127, 89, 23, 17, 5, 3]
n=34=15+11+8 factors=[151, 89, 31, 23, 17, 7, 5, 3]
n=34=14+11+9 factors=[127, 89, 73, 43, 23, 7, 3]
n=34=11+8+7+5+3 factors=[127, 89, 31, 23, 17, 7, 5, 3]
n=35=25+7+3 factors=[1801, 601, 127, 31, 7]
n=35=24+11 factors=[241, 89, 23, 17, 13, 7, 5, 3^2]
n=35=16+11+5+3 factors=[257, 89, 31, 23, 17, 7, 5, 3]
n=35=12+11+7+5 factors=[127, 89, 31, 23, 13, 7, 5, 3^2]
n=35=11+9+8+7 factors=[127, 89, 73, 23, 17, 7, 5, 3]
n=36 (primitive) factors=[109, 73, 37, 19, 13, 7, 5, 3^3]
n=36=28+5+3 factors=[127, 113, 43, 31, 29, 7, 5, 3]
n=36=25+11 factors=[1801, 601, 89, 31, 23]
n=36=25+8+3 factors=[1801, 601, 31, 17, 7, 5, 3]
n=36=25+7+4 factors=[1801, 601, 127, 31, 5, 3]
n=36=24+7+5 factors=[241, 127, 31, 17, 13, 7, 5, 3^2]
n=36=22+9+5 factors=[683, 89, 73, 31, 23, 7, 3]
n=36=21+11+4 factors=[337, 127, 89, 23, 7^2, 5, 3]
n=36=20+9+7 factors=[127, 73, 41, 31, 11, 7, 5^2, 3]
n=36=18+11+7 factors=[127, 89, 73, 23, 19, 7, 3^3]
n=36=16+11+9 factors=[257, 89, 73, 23, 17, 7, 5, 3]
n=36=11+9+7+5+4 factors=[127, 89, 73, 31, 23, 7, 5, 3]
n=37=30+7 factors=[331, 151, 127, 31, 11, 7, 3^2]
n=37=28+9 factors=[127, 113, 73, 43, 29, 7, 5, 3]
n=37=25+12 factors=[1801, 601, 31, 13, 7, 5, 3^2]
n=37=22+15 factors=[683, 151, 89, 31, 23, 7, 3]
n=37=22+7+5+3 factors=[683, 127, 89, 31, 23, 7, 3]
n=37=21+16 factors=[337, 257, 127, 17, 7^2, 5, 3]
n=37=21+11+5 factors=[337, 127, 89, 31, 23, 7^2]
n=37=16+11+7+3 factors=[257, 127, 89, 23, 17, 7, 5, 3]
n=37=16+9+7+5 factors=[257, 127, 73, 31, 17, 7, 5, 3]
n=37=15+11+7+4 factors=[151, 127, 89, 31, 23, 7, 5, 3]
n=37=11+10+9+7 factors=[127, 89, 73, 31, 23, 11, 7, 3]
n=38=25+9+4 factors=[1801, 601, 73, 31, 7, 5, 3]
n=38=25+7+6 factors=[1801, 601, 127, 31, 7, 3^2]
n=38=22+9+7 factors=[683, 127, 89, 73, 23, 7, 3]
n=38=20+11+7 factors=[127, 89, 41, 31, 23, 11, 5^2, 3]
n=38=16+15+7 factors=[257, 151, 127, 31, 17, 7, 5, 3]
n=39=28+11 factors=[127, 113, 89, 43, 29, 23, 5, 3]
n=39=25+14 factors=[1801, 601, 127, 43, 31, 3]
n=39=25+11+3 factors=[1801, 601, 89, 31, 23, 7]
n=39=25+7+4+3 factors=[1801, 601, 127, 31, 7, 5, 3]
n=39=16+11+7+5 factors=[257, 127, 89, 31, 23, 17, 5, 3]
n=39=14+11+9+5 factors=[127, 89, 73, 43, 31, 23, 7, 3]
n=40=25+11+4 factors=[1801, 601, 89, 31, 23, 5, 3]
n=40=25+8+7 factors=[1801, 601, 127, 31, 17, 5, 3]
n=40=24+11+5 factors=[241, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=40=21+11+8 factors=[337, 127, 89, 23, 17, 7^2, 5, 3]
n=40=20+11+9 factors=[89, 73, 41, 31, 23, 11, 7, 5^2, 3]
n=40=15+14+11 factors=[151, 127, 89, 43, 31, 23, 7, 3]
n=40=11+9+8+7+5 factors=[127, 89, 73, 31, 23, 17, 7, 5, 3]
n=41=36+5 factors=[109, 73, 37, 31, 19, 13, 7, 5, 3^3]
n=41=30+11 factors=[331, 151, 89, 31, 23, 11, 7, 3^2]
n=41=25+16 factors=[1801, 601, 257, 31, 17, 5, 3]
n=41=25+9+7 factors=[1801, 601, 127, 73, 31, 7]
n=41=21+20 factors=[337, 127, 41, 31, 11, 7^2, 5^2, 3]
n=41=21+11+5+4 factors=[337, 127, 89, 31, 23, 7^2, 5, 3]
n=41=20+11+7+3 factors=[127, 89, 41, 31, 23, 11, 7, 5^2, 3]
n=41=18+11+7+5 factors=[127, 89, 73, 31, 23, 19, 7, 3^3]
n=41=16+11+9+5 factors=[257, 89, 73, 31, 23, 17, 7, 5, 3]
n=41=15+11+8+7 factors=[151, 127, 89, 31, 23, 17, 7, 5, 3]
n=42=28+11+3 factors=[127, 113, 89, 43, 29, 23, 7, 5, 3]
n=42=28+9+5 factors=[127, 113, 73, 43, 31, 29, 7, 5, 3]
n=42=25+14+3 factors=[1801, 601, 127, 43, 31, 7, 3]
n=42=25+11+6 factors=[1801, 601, 89, 31, 23, 7, 3^2]
n=42=25+9+8 factors=[1801, 601, 73, 31, 17, 7, 5, 3]
n=42=24+11+7 factors=[241, 127, 89, 23, 17, 13, 7, 5, 3^2]
n=42=21+16+5 factors=[337, 257, 127, 31, 17, 7^2, 5, 3]
n=42=21+11+10 factors=[337, 127, 89, 31, 23, 11, 7^2, 3]
n=42=16+15+11 factors=[257, 151, 89, 31, 23, 17, 7, 5, 3]
n=42=16+11+7+5+3 factors=[257, 127, 89, 31, 23, 17, 7, 5, 3]
n=43=36+7 factors=[127, 109, 73, 37, 19, 13, 7, 5, 3^3]
n=43=28+15 factors=[151, 127, 113, 43, 31, 29, 7, 5, 3]
n=43=25+18 factors=[1801, 601, 73, 31, 19, 7, 3^3]
n=43=25+11+7 factors=[1801, 601, 127, 89, 31, 23]
n=43=25+11+4+3 factors=[1801, 601, 89, 31, 23, 7, 5, 3]
n=43=25+8+7+3 factors=[1801, 601, 127, 31, 17, 7, 5, 3]
n=43=22+21 factors=[683, 337, 127, 89, 23, 7^2, 3]
n=43=22+9+7+5 factors=[683, 127, 89, 73, 31, 23, 7, 3]
n=43=16+11+9+7 factors=[257, 127, 89, 73, 23, 17, 7, 5, 3]
n=44=28+11+5 factors=[127, 113, 89, 43, 31, 29, 23, 5, 3]
n=44=25+16+3 factors=[1801, 601, 257, 31, 17, 7, 5, 3]
n=44=25+12+7 factors=[1801, 601, 127, 31, 13, 7, 5, 3^2]
n=44=25+11+8 factors=[1801, 601, 89, 31, 23, 17, 5, 3]
n=44=22+15+7 factors=[683, 151, 127, 89, 31, 23, 7, 3]
n=45=25+11+9 factors=[1801, 601, 89, 73, 31, 23, 7]
n=45=25+9+7+4 factors=[1801, 601, 127, 73, 31, 7, 5, 3]
n=45=21+11+8+5 factors=[337, 127, 89, 31, 23, 17, 7^2, 5, 3]
n=46=25+21 factors=[1801, 601, 337, 127, 31, 7^2]
n=46=25+11+7+3 factors=[1801, 601, 127, 89, 31, 23, 7]
n=47=36+11 factors=[109, 89, 73, 37, 23, 19, 13, 7, 5, 3^3]
n=47=28+11+5+3 factors=[127, 113, 89, 43, 31, 29, 23, 7, 5, 3]
n=47=25+22 factors=[1801, 683, 601, 89, 31, 23, 3]
n=47=25+11+8+3 factors=[1801, 601, 89, 31, 23, 17, 7, 5, 3]
n=47=25+11+7+4 factors=[1801, 601, 127, 89, 31, 23, 5, 3]
n=47=24+11+7+5 factors=[241, 127, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=47=20+11+9+7 factors=[127, 89, 73, 41, 31, 23, 11, 7, 5^2, 3]
n=48 (primitive) factors=[673, 257, 241, 97, 17, 13, 7, 5, 3^2]
n=48=36+7+5 factors=[127, 109, 73, 37, 31, 19, 13, 7, 5, 3^3]
n=48=30+11+7 factors=[331, 151, 127, 89, 31, 23, 11, 7, 3^2]
n=48=28+11+9 factors=[127, 113, 89, 73, 43, 29, 23, 7, 5, 3]
n=48=25+16+7 factors=[1801, 601, 257, 127, 31, 17, 5, 3]
n=48=25+14+9 factors=[1801, 601, 127, 73, 43, 31, 7, 3]
n=48=25+12+11 factors=[1801, 601, 89, 31, 23, 13, 7, 5, 3^2]
n=48=22+21+5 factors=[683, 337, 127, 89, 31, 23, 7^2, 3]
n=48=21+16+11 factors=[337, 257, 127, 89, 23, 17, 7^2, 5, 3]
n=48=16+11+9+7+5 factors=[257, 127, 89, 73, 31, 23, 17, 7, 5, 3]
n=49=25+24 factors=[1801, 601, 241, 31, 17, 13, 7, 5, 3^2]
n=49=25+11+9+4 factors=[1801, 601, 89, 73, 31, 23, 7, 5, 3]
n=49=25+11+7+6 factors=[1801, 601, 127, 89, 31, 23, 7, 3^2]
n=49=25+9+8+7 factors=[1801, 601, 127, 73, 31, 17, 7, 5, 3]
n=49=16+15+11+7 factors=[257, 151, 127, 89, 31, 23, 17, 7, 5, 3]
n=50=25+22+3 factors=[1801, 683, 601, 89, 31, 23, 7, 3]
n=50=25+21+4 factors=[1801, 601, 337, 127, 31, 7^2, 5, 3]
n=50=25+18+7 factors=[1801, 601, 127, 73, 31, 19, 7, 3^3]
n=50=25+16+9 factors=[1801, 601, 257, 73, 31, 17, 7, 5, 3]
n=50=25+14+11 factors=[1801, 601, 127, 89, 43, 31, 23, 3]
n=50=25+11+7+4+3 factors=[1801, 601, 127, 89, 31, 23, 7, 5, 3]
n=51=25+16+7+3 factors=[1801, 601, 257, 127, 31, 17, 7, 5, 3]
n=51=25+11+8+7 factors=[1801, 601, 127, 89, 31, 23, 17, 5, 3]
n=52=36+11+5 factors=[109, 89, 73, 37, 31, 23, 19, 13, 7, 5, 3^3]
n=52=25+16+11 factors=[1801, 601, 257, 89, 31, 23, 17, 5, 3]
n=52=25+11+9+7 factors=[1801, 601, 127, 89, 73, 31, 23, 7]
n=52=21+20+11 factors=[337, 127, 89, 41, 31, 23, 11, 7^2, 5^2, 3]
n=53=48+5 factors=[673, 257, 241, 97, 31, 17, 13, 7, 5, 3^2]
n=53=28+25 factors=[1801, 601, 127, 113, 43, 31, 29, 5, 3]
n=53=28+11+9+5 factors=[127, 113, 89, 73, 43, 31, 29, 23, 7, 5, 3]
n=53=25+14+11+3 factors=[1801, 601, 127, 89, 43, 31, 23, 7, 3]
n=53=25+11+9+8 factors=[1801, 601, 89, 73, 31, 23, 17, 7, 5, 3]
n=53=21+16+11+5 factors=[337, 257, 127, 89, 31, 23, 17, 7^2, 5, 3]
n=54=36+11+7 factors=[127, 109, 89, 73, 37, 23, 19, 13, 7, 5, 3^3]
n=54=28+15+11 factors=[151, 127, 113, 89, 43, 31, 29, 23, 7, 5, 3]
n=54=25+22+7 factors=[1801, 683, 601, 127, 89, 31, 23, 3]
n=54=25+21+8 factors=[1801, 601, 337, 127, 31, 17, 7^2, 5, 3]
n=54=25+18+11 factors=[1801, 601, 89, 73, 31, 23, 19, 7, 3^3]
n=54=25+11+8+7+3 factors=[1801, 601, 127, 89, 31, 23, 17, 7, 5, 3]
n=55=48+7 factors=[673, 257, 241, 127, 97, 17, 13, 7, 5, 3^2]
n=55=25+16+11+3 factors=[1801, 601, 257, 89, 31, 23, 17, 7, 5, 3]
n=55=25+12+11+7 factors=[1801, 601, 127, 89, 31, 23, 13, 7, 5, 3^2]
n=56=28+25+3 factors=[1801, 601, 127, 113, 43, 31, 29, 7, 5, 3]
n=56=25+24+7 factors=[1801, 601, 241, 127, 31, 17, 13, 7, 5, 3^2]
n=56=25+22+9 factors=[1801, 683, 601, 89, 73, 31, 23, 7, 3]
n=56=25+11+9+7+4 factors=[1801, 601, 127, 89, 73, 31, 23, 7, 5, 3]
n=57=25+22+7+3 factors=[1801, 683, 601, 127, 89, 31, 23, 7, 3]
n=57=25+21+11 factors=[1801, 601, 337, 127, 89, 31, 23, 7^2]
n=57=25+16+9+7 factors=[1801, 601, 257, 127, 73, 31, 17, 7, 5, 3]
n=59=48+11 factors=[673, 257, 241, 97, 89, 23, 17, 13, 7, 5, 3^2]
n=59=36+11+7+5 factors=[127, 109, 89, 73, 37, 31, 23, 19, 13, 7, 5, 3^3]
n=59=25+16+11+7 factors=[1801, 601, 257, 127, 89, 31, 23, 17, 5, 3]
n=59=25+14+11+9 factors=[1801, 601, 127, 89, 73, 43, 31, 23, 7, 3]
n=60 (primitive) factors=[1321, 331, 151, 61, 41, 31, 13, 11, 7, 5^2, 3^2]
n=60=48+7+5 factors=[673, 257, 241, 127, 97, 31, 17, 13, 7, 5, 3^2]
n=60=25+24+11 factors=[1801, 601, 241, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=60=25+11+9+8+7 factors=[1801, 601, 127, 89, 73, 31, 23, 17, 7, 5, 3]
n=61=36+25 factors=[1801, 601, 109, 73, 37, 31, 19, 13, 7, 5, 3^3]
n=61=25+21+11+4 factors=[1801, 601, 337, 127, 89, 31, 23, 7^2, 5, 3]
n=61=25+18+11+7 factors=[1801, 601, 127, 89, 73, 31, 23, 19, 7, 3^3]
n=61=25+16+11+9 factors=[1801, 601, 257, 89, 73, 31, 23, 17, 7, 5, 3]
n=62=28+25+9 factors=[1801, 601, 127, 113, 73, 43, 31, 29, 7, 5, 3]
n=62=25+21+16 factors=[1801, 601, 337, 257, 127, 31, 17, 7^2, 5, 3]
n=62=25+16+11+7+3 factors=[1801, 601, 257, 127, 89, 31, 23, 17, 7, 5, 3]
n=63=25+22+9+7 factors=[1801, 683, 601, 127, 89, 73, 31, 23, 7, 3]
n=64=48+11+5 factors=[673, 257, 241, 97, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=64=28+25+11 factors=[1801, 601, 127, 113, 89, 43, 31, 29, 23, 5, 3]
n=65=25+21+11+8 factors=[1801, 601, 337, 127, 89, 31, 23, 17, 7^2, 5, 3]
n=66=48+11+7 factors=[673, 257, 241, 127, 97, 89, 23, 17, 13, 7, 5, 3^2]
n=67=60+7
factors=[1321, 331, 151, 127, 61, 41, 31, 13, 11, 7, 5^2, 3^2]
n=67=28+25+11+3 factors=[1801, 601, 127, 113, 89, 43, 31, 29, 23, 7, 5, 3]
n=67=25+24+11+7
factors=[1801, 601, 241, 127, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=68=36+25+7
factors=[1801, 601, 127, 109, 73, 37, 31, 19, 13, 7, 5, 3^3]
n=68=25+22+21 factors=[1801, 683, 601, 337, 127, 89, 31, 23, 7^2, 3]
n=68=25+16+11+9+7 factors=[1801, 601, 257, 127, 89, 73, 31, 23, 17, 7, 5, 3]
n=71=60+11
factors=[1321, 331, 151, 89, 61, 41, 31, 23, 13, 11, 7, 5^2, 3^2]
n=71=48+11+7+5
factors=[673, 257, 241, 127, 97, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=72=36+25+11
factors=[1801, 601, 109, 89, 73, 37, 31, 23, 19, 13, 7, 5, 3^3]
n=73=48+25
factors=[1801, 673, 601, 257, 241, 97, 31, 17, 13, 7, 5, 3^2]
n=73=28+25+11+9
factors=[1801, 601, 127, 113, 89, 73, 43, 31, 29, 23, 7, 5, 3]
n=73=25+21+16+11
factors=[1801, 601, 337, 257, 127, 89, 31, 23, 17, 7^2, 5, 3]
n=78=60+11+7
factors=[1321, 331, 151, 127, 89, 61, 41, 31, 23, 13, 11, 7, 5^2, 3^2]
n=79=36+25+11+7
factors=[1801, 601, 127, 109, 89, 73, 37, 31, 23, 19, 13, 7, 5, 3^3]
n=80=48+25+7
factors=[1801, 673, 601, 257, 241, 127, 97, 31, 17, 13, 7, 5, 3^2]
n=84=48+25+11
factors=[1801, 673, 601, 257, 241, 97, 89, 31, 23, 17, 13, 7, 5, 3^2]
n=91=48+25+11+7
factors=[1801, 673, 601, 257, 241, 127, 97, 89, 31, 23, 17, 13, 7, 5, 3^2]
It looks like the largest possible “composite” LFSR with period that is a product of factors no larger than 2000 is a 91-bit LFSR. (It also looks like the partitioned degrees cannot have any common factor; for example, in \( 67=28+25+11+3 \) all of the values \( (28,25,11,3) \) are pairwise relatively prime.)
Anyway, let’s say we wanted to construct a 64-bit LFSR with period \( P=(2^{48}-1)(2^{11}-5)(2^5-1) \approx 0.9683 \cdot (2^{64} - 1) \). There are two ways to do it:
- find primitive polynomials of degrees 48, 11, and 5, and multiply them together
- find a nonprimitive polynomial with period P by trial and error
Both are possible using libgf2.gf2.checkPeriod:
from libgf2.gf2 import checkPeriod, _gf2mul, _gf2divmod
from libgf2.util import parity
import time
def find_polynomial_with_period(start, offsetrange, period):
# help out checkPeriod
f = primefac.factorint(period)
cofactors = [P/k for k in f]
for k in offsetrange:
poly = start+k
# test for odd parity
# (all irreducible polynomials except for x+1 have an odd number of 1s)
if parity(poly) == 0:
continue
# skip if divisible by irreducible polynomials from degrees 2-4
r=1
for d in [7, 11, 13, 19, 25, 31]:
_,r = _gf2divmod(poly, d)
if r == 0:
break
if r == 0:
continue
if checkPeriod(poly,period,cofactors) == period:
return poly
polyproduct = 1
P = 1
polylist = []
for n in [48, 11, 5]:
# look for primitive polynomials
period = (1<<n) - 1
P *= period
poly = find_polynomial_with_period(1<<n, xrange(1,10000,2), period)
if poly is None:
raise ValueError('Failed to find any of degree %d' % n)
polylist.append((n,poly))
polyproduct = _gf2mul(polyproduct, poly)
print "degree %d: polynomial = 0x%x, period=%d" % (n,poly,period)
print "product (degree 64) = 0x%x, period=%d" % (polyproduct, P)
print "verify period:", checkPeriod(polyproduct, P)
print ""
print "direct search for polynomials with period=%d:" % P
t0 = time.time()
poly2 = find_polynomial_with_period(1<<64, xrange(1,60000,2),P)
t1 = time.time()
print "0x%x (%.2f s)" % (poly2, t1-t0) degree 48: polynomial = 0x10000000000b7, period=281474976710655 degree 11: polynomial = 0x805, period=2047 degree 5: polynomial = 0x25, period=31 product (degree 64) = 0x128b1000000a41ea7, period=17861557597128034335 verify period: 17861557597128034335 direct search for polynomials with period=17861557597128034335: 0x10000000000006861 (16.41 s)
The second method above is much slower, but it has an advantage that we can look for polynomials in a specific range; aside from the coefficient of \( x^{64} \), the one we found has all its nonzero coefficients in the bottom 16 bits, which has some advantages for software implementations.
Once we have such a nonprimitive polynomial \( p(x) \) that corresponds to a near-maximum length LFSR, we can use it essentially the same way as a primitive polynomial. Note that because it is a product of primitive polynomials of smaller degree, it is therefore a reducible polynomial. (As a refresher: all primitive polynomials are irreducible, but not all irreducible polynomials are primitive; irreducible polynomials in \( GF(2)[x] \) are also primitive if they generate maximum-length LFSRs.) Some examples of these kind of polynomials are
- \( p _ {31}(x) = x^5 + x^4 + 1 = (x^2 + x + 1)(x^3 + x + 1) \) (degrees 2 and 3)
- \( p _ {E3}(x) = x^7 + x^6 + x^5 + x + 1 = (x^3 + x + 1)(x^4 + x^3 + 1) \) (degrees 3 and 4)
- \( p_ {389}(x) = x^9 + x^8 + x^7 + x^3 + 1 = (x^7 + x + 1)(x^2 + x + 1) \) (degrees 2 and 7)
Below are a few of the ways in which a reducible polynomial that is the product of primitive polynomials behaves differently or the same as a primitive polynomial:
- LFSR works the same: XOR taps based on nonzero coefficients; LFSR state \( S[k] \) represents \( x^k \) in the quotient ring \( GF(2)[x]/p(x) \)
- shorter period than primitive polynomial
- quotient ring \( GF(2)[x]/p(x) \) is not a field, which means there are other elements besides \( 0 \) that do not have a multiplicative inverse. These elements are polynomials that have some common factor with \( p(x) \).
- more initial states that are “degenerate” — for primitive polynomials this is only the all-zero state, but for nonprimitive polynomials it includes other states which correspond to elements in the quotient ring which do not have a multiplicative inverse
- discrete logarithm algorithms are valid on any element that has an inverse, unless the algorithm makes some assumption that all elements in the quotient ring have inverses, or takes advantage of some other identity that is valid for fields but not rings
- the Berlekamp-Massey algorithm will still find \( p(x) \) given its output
- LFSR time shifts by \( d \) steps are still equivalent to multiplying state by \( x^{-d} \)
- LFSR state recovery works the same way as for LFSRs based on primitive polynomials
- LFSR output decimation appears to work mostly the same way we as for LFSRs based on primitive polynomials:
- decimating by powers of two produces the same sequence, but shifted
- decimation ratios are partitioned into what look like cyclotomic cosets the way they are for LFSRs based on primitive polynomials; for example, the quotient ring \( GF(2)[x]/p_{E3}(x) \) has a period of 105, and decimating by ratios \( 1, 2, 4, 8, 16, 32, 64, 128 \equiv 23, 46, 92, 184 \equiv 79, 158 \equiv 53, 106 \equiv 1 \) all produce the same repeating sequence but shifted; similarly, decimating by ratios of \( 21, 42, 84, 168 \equiv 63, 126 \equiv 21 \) also produce the same repeating sequence but shifted. These appear to behave like cyclotomic cosets in that they have elements that represent a sequence of powers of two, modulo the LFSR period, but here we have 12 elements rather than 7 for a 7-bit LFSR… presumably because here the smallest value of \( t \) for which 105 divides \( 2^t-1 \) is \( t=12 \).
- decimating by -1 produces the same output as an LFSR with the reflected polynomial
- The trace function \( \operatorname{Tr}(u) = u + u^2 + u^4 + u^8 + \ldots + u^{2^{N-1}} \) is well-defined, but its value is not confined to 0 or 1, and the identity \( \operatorname{Tr}(u) = \operatorname{Tr}(u^2) \) is no longer still true since \( u^{2^N} \neq u \).
- It looks like we can, however, create a “pseudo-trace” function \( \operatorname{Trp}(u) = (u + u^2 + u^4 + u^8 + \ldots + u^{2^{t-1}})/v \) for \( t = \operatorname{lcm}(N_1,N_2,N_3,\ldots) \) where \( N_1, N_2, N_3, \ldots \) are the degrees of the primitive polynomials that are the factors of the characteristic polynomial \( p(x) \), and \( v \) is some characteristic element that always divides \( \operatorname{Trp}(u) \). For example, with \( p_{E3}(x) \), the primitive polynomial factors are of degree 3 and 4, so their LCM is \( t=12 \); with \( p_{31}(x) \), the partitioned degrees are 2 and 3, with LCM \( t=6 \). The resulting value \( \operatorname{Trp}(u) \) appears to be always 0 or 1 for some \( v \neq 1 \) which has a common factor with \( p(x) \). (Again, for example, with \( p_{E3}(x), v = x^6 + x^3 + x^2 + x = x(x+1)^2(x^3 + x + 1) \); for \( p_{31}(x), v = x^4 + x^3 + x^2 + 1 = (x+1)(x^3 + x + 1) \); for \( p_{389}(x), v = x^7 + x + 1 \).)
Anyway, there you have it; count away!
Position Encoders
Counters are more of an abstract digital system: we have a state machine that encodes a count value that increments sequentially upon various events. A position encoder is something different; it is a special type of position transducer that translates linear or rotary position into a discrete count that can be read and processed. The common type of position encoder is an incremental encoder that uses a pair of A and B signals which, for constant velocity, are square waves 90° out of phase.
The changes in these signals allow unambiguous determination of relative position in either direction — that is, if I know the starting position of an object, and I can sense all the transitions in the A and B signals, then I can know for certain the change in position relative to the starting position, regardless of what trajectory it took to get there; it may have gone 10 counts forward and 99 counts backward and then 36 counts forward, for a net change of 53 counts backward. Some incremental encoders have an index pulse that indicates an absolute reference position; without such an absolute reference, there is no way to know the absolute position of the object.
There are also absolute encoders which provide a count output directly as N bits in parallel. The traditional method of this is to use multitrack optical encoders with a Gray code encoding so that only one bit of the encoding changes at a time; this prevents glitches in the count output. Want a 10-bit absolute encoder? Fine, then you need 10 tracks. More recently, magnetic encoders have been developed which rely on a rotating magnetized code wheel and an integrated circuit that contains a pair of Hall sensors to detect orthogonal components \( B_x \) and \( B_y \) of the magnet field, which can be used to derive a position output that is transmitted digitally. Assuming these components vary sinusoidally with angle, and any gain and offset errors are negligible, then the atan2 function can be used to convert from Cartesian coordinates \( (B_x, B_y) \) to an angle. There are several ICs of this type made by ams AG — formerly austriamicrosystems, whose marketing department appears to be, like e e cummings, averse to the use of uppercase letters. These components include the Hall sensors, the signal conditioning, digital logic to determine the angle, and some kind of communications port to transmit the angle in serial form. (I suppose a parallel-output version is possible, but most of these use SPI or I2C to save on I/O pin count.)
The type of encoder I want to talk about is an obscure one, that uses something called a chain code, described in US Patent 3531798, invented by M. Gabriel Henri Leon Dureau and granted to Alcatel in September 1970 — so the patent has expired now, and anyone can use this technique. (This patent also references the 1948 French patent #969942; if anyone out there knows how to get a copy, please let me know, as I am curious to see the first known public implementation.)
Essentially, the idea is to use a series of bit patterns that differ by one place, so that to get from one to the next, you shift left or shift right and a new bit comes in that provides a unique code.
For example, Figure 3 in Patent 3531798 shows the repeating sequence 000100110101111, which contains the following 15 4-bit patterns in various slices:
0001(0:4)0010(1:5)0100(2:6)1001(3:7)0011(4:8)0110(5:9)1101(6:10)1010(7:11)0101(8:12)1011(9:13)0111(10:14)1111(11:15)1110(12:16)1100(13:17)1000(14:18)
Look familiar? It should; this is the state of a Fibonacci LFSR using the polynomial \( x^4 + x^3 + 1 \Longleftrightarrow \) 11001, or equivalently, 4 successive output bits of a Galois LFSR using the reflected polynomial \( x^4 + x + 1 \Longleftrightarrow \) 10011. The Alcatel patent inserts the all-zero sequence to form a complete set of all N-bit patterns, called a De Bruijn sequence — sequences derived from LFSRs are only one example of De Bruijn sequences.
The idea is that as long as you can look at N successive bits of the pattern, you can know exactly where the sensor is. For a sequence based on LFSR outputs, this involves converting to Galois LFSR state and then taking a discrete logarithm to recover the count.
This means, for example, that you could create a 10-bit position encoder using only one single track (magnetic or optical) and 10 digital sensors in nearby positions to detect successive bits. In practice, this would be difficult to construct so that all the bits changed synchronously. Another possible method of encoding is a 3-track 3-sensor approach that uses two tracks as a standard AB incremental encoder, and then a chain code (Y) track that has transitions in the middle of each incremental position. Below is a 5-bit, 32-count encoder based on this principle, using \( H_{25}(x) = x^5 + x^2 + 1 \):
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
H25 = GF2QuotientRing(0x25)
def gather_insert0(field, k, ofs=0):
u = field.wrap(1) << ofs
while k > 0:
# extra 0
if u.coeffs == 1:
k -= 1
yield 0
if k == 0:
break
yield u.coeffs >> (field.degree - 1)
u <<= 1
k -= 1
tmax = 40
t1 = np.arange(-1,tmax+2)
track_A = ((t1) & 2) >> 1
track_B = ((t1-1) & 2) >> 1
track_Y = np.array(list(gather_insert0(H25, len(t1), ofs=-1)))
def plot_ABY(tmax, t1, A, B, Y, tY=None, tYtextofs=0.5):
fig = plt.figure(figsize=(7.5,2))
ax = fig.add_subplot(1,1,1)
ymarg = 0.2
ycmarg = 1-ymarg
ax.set_ylim(-ymarg,3+ymarg)
ax.set_yticks(ycmarg/2 + np.arange(3))
ax.set_yticklabels('ABY')
ax.yaxis.set_ticks_position('none')
if tY is None:
tY = t1
for k, b in enumerate(track_Y):
tk = tY[k]
if tk >= 0 and tk <= tmax:
ax.text(tk,ycmarg/2 + 2,'1' if b else '0',
horizontalalignment='center', verticalalignment='center')
ax.plot(t1,A * (1-ymarg), 'k', drawstyle='steps')
ax.plot(t1,B * (1-ymarg) + 1, 'k', drawstyle='steps')
ax.plot(tY+tYtextofs,Y * (1-ymarg) + 2, 'k', drawstyle='steps')
ax.set_xticks(t1, minor=True)
ax.set_xticks(np.arange(0,tmax+1,5))
ax.set_xlim(-0.5,tmax+0.5)
ax.grid(True, axis='x', which='minor', linestyle='-', color='gray')
plot_ABY(tmax, t1, track_A, track_B, track_Y)
Each time an edge is encountered in the AB tracks, a new chain code bit can be read. Then, after traveling over 5 counts of the incremental encoder, it would be possible to determine the chain code stretching over those 5 counts, and then a discrete logarithm could be used to determine absolute position. On initial power-up, there is no way to tell absolute position, but the required travel distance is much less than a traditional ABZ incremental encoder with index pulse, which requires a worst-case travel of one rotation before it hits the index.
Alternatively, the LFSR update could occur every 2 AB counts; this adds another bit (6-bit, 64-count in our example using \( x^5 + x^2 + 1 \)) and allows the Y track to have the same minimum pulse width as the A and B tracks, at the cost of twice the worst-case travel before an absolute position resync is possible. Here instead of using the AB edges to sample the Y track, a pair of “distinguished” states AB = 00 and AB = 11 can be used to designate sampling instants, with edges in the Y track located in the other two non-distinguished states:
tmax = 72 t1 = np.arange(-1,tmax+2) track_A = ((t1) & 2) >> 1 track_B = ((t1-1) & 2) >> 1 tY = np.arange(-2,tmax+2,2)+0.5 track_Y = np.array(list(gather_insert0(H25, len(tY), ofs=-1))) plot_ABY(tmax, t1, track_A, track_B, track_Y, tY, tYtextofs=1)
Either of these schemes would also increase robustness; although AB incremental encoders have some noise immunity, if the right pattern of glitches occurs in the AB tracks, the decoded count can become off by 4. An index pulse track allows correction of this count, but only after an entire rotation has occurred, whereas a chain-code index track can correct the encoder count after a few counts.
The odd thing is that there should be little to no cost increase over a traditional ABZ incremental encoder: same number of tracks and sensors, just a Y track for a chain code instead of a Z track with a single pulse per revolution. Of course the decoding is more complicated, but with today’s microcontrollers that’s not a big deal. I guess dealing with finite fields just scares people.
References
- D. W. Clark and Lih-Jyh Weng, Maximal and near-maximal shift register sequences: efficient event counters and easy discrete logarithms. IEEE Transactions on Computers, vol. 43, no. 5, pp. 560-568, May 1994.
- U.S. Patent 3531798, Numerical coding, invented by Gabriel Henri Leon Dureau, assigned to Alcatel SA, September 1970.
Wrapup
Today we looked at counters and encoders using LFSRs:
- counters can be made using LFSRs with either a primitive polynomial or a carefully-selected product of primitive polynomials
- in an LFSR-based counter, the count can be recovered with discrete logarithms
- absolute encoders can be made using chain codes based on LFSR output, so that any successive \( N \) bits of the chain code can be used to recover an absolute position using discrete logarithms
The next article will explore the use of LFSRs in pseudorandom number generation.
© 2017 Jason M. Sachs, all rights reserved.
- Comments
- Write a Comment Select to add a comment
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Please login (on the right) if you already have an account on this platform.
Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers:
