Arndt - Algorithms for Programmers (523138), страница 43
Текст из файла (страница 43)
This can be seen more easily when displayed together with the words corresponding to the position (dots for zeros):111.11..1......1..1..1..1..1..11.11.11.11.1..1.11.11.1111111111.11..1......1..1..1.....1..11.1.1111...1..The words to the left are obtained by combining the current bit and the n − 1 = 3 bits left of it.The sequence can be obtained by computing Ak = xk , k = 0, 1, . . . , 2n − 1 modulo the polynomial C =x4 + x + 1 and setting bit k of the SRS to the least significant bit of (equivalently: constant term of) Ak .This is demonstrated in [FXT: file demo/lfsr-demo.cc], which for n = 4 gives the output:poly = 1..11 == 0x130a= ...1 w=1a= ..1. w=2a= .1..
w=3a= 1... w=4a= ..11 w=5a= .11. w=6a= 11.. w=7a= 1.11 w=8a= .1.1 w=9a= 1.1. w=10a= .111 w=11a= 111. w=12a= 1111 w=13a= 11.1 w=14a= 1..1 w=== 191111 =111. =11.. =1... =...1 =..1. =.1.. =1..1 =..11 =.11. =11.1 =1.1. =.1.1 =1.11 =.111 =(deg = 4)151412812493613105117253CHAPTER 12. SHIFT REGISTER SEQUENCES12.2254Generation of binary shift register sequencesWe restrict our attention to binary polynomials (that is, polynomials over Z/2Z) as computations areespecially easy with those: when represented as binary words (bits as coefficients) both addition andsubtraction are XOR, multiplication by x is just a shift to the left.Consider the sequence of successive (polynomial) values Ak := A0 xk modulo C for A0 6= 0, k =0, 1, 2, 3 . . ..
Here is id a polynomial over GF (2), that is, with coefficients modulo two. Note thatthe computations are modulo a polynomial with coefficients modulo two.The multiplication (of Ak ) be x modulo C is easily done by shifting to the left, then, if coefficient n of Ais non-zero, subtract C (that is, XOR it).The utility class that can be used is [FXT: class lfsr in auxbit/lfsr.h], where the crucial computationis implemented asulong next(){ulong s = a_ & h_;a_ <<= 1;w_ <<= 1;if ( 0!=s ){a_ ^= c_;w_ |= 1;}w_ &= m_;return w_;}This needs about 10 cycles per call. The underlying mechanism (shifting and feeding back the bit justshifted out) is called a linear feedback shift register (LFSR).Using n = 5 and c = x5 + x2 + 1 we findk1234567891011121314151617181920212223242526272829303132a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=a=A(k)..1.1.1.1.1.1...11.111.1.1...1..111.111.111..111.11111111.111..11...11..11..11..11...1.1.1.11111111.11..11.111.1.111.11..1..11..1.....1...1...1...1...1......1.1 == A(1)The sequence Ak is periodic with period 31 = 25 − 1.
In fact m = 2n − 1 is the maximal possible periodfor a polynomial C of degree n as there are just m non-zero binary polynomials at all. The choice of C isnot arbitrary, with ‘bad’ polynomials C one gets sequences with a period less than 2n − 1 and thereforeonly a subset of the binary words.First, the polynomials must be irreducible: A polynomial C = c0 + c1 x + c2 x2 + . .
. + cn xn is calledirreducible if it has no non-trivial factorization.Consider only polynomials with a constant term (else x would be a factor and the polynomial would not beCHAPTER 12. SHIFT REGISTER SEQUENCES255irreducible). Then the period is determined by the minimal m for which C divides Q(m) := xm −1 (whichis equal to xm + 1 for binary polynomials). Polynomials that give maximal period are called primitive.We’ll abbreviate primitive polynomials as PP. PP are always irreducible, irreducible polynomials are notnecessarily primitive.Lists of primitive binary polynomials look like2,1,03,2,04,3,0 // == x^4 + x^3 + 15,3,2,1,06,5,07,6,3,1,08,6,5,3,09,5,3,2,010,8,4,3,011,10,8,7,6,4,2,1,012,11,10,9,4,3,0...31,29,23,21,19,17,15,12,10,8,7,5,4,2,032,31,29,28,26,24,23,18,10,9,8,7,6,5,4,1,033,31,29,28,27,25,20,19,17,13,11,10,8,6,5,1,034,33,31,27,25,24,22,18,16,15,14,12,11,10,9,8,7,6,4,2,0...Each line consists of those powers of x where C has a non-zero coefficient.
The coefficients c0 and cnare never zero so the first entry in each line gives the degree. In fact the above list gives ‘random’ PPsthat where created by testing random binary words for primitivity when used as a binary polynomial; cf.[FXT: file data/rand-primpoly.txt].The SRS generated with all PPs for degree 2 ≤ n ≤ 8 are computed with [FXT: filedemo/allprimpoly-demo.cc]. For n = 6 there are 6 different PPs and the output is:degree = 6c= 1....11c= 1.11.11c= 11....1c= 11..111c= 11.11.1c= 111..11srs=.....1....11...1.1..1111.1...111..1..1.11.111.11..11.1.1.111111srs=.....1.111111..1.1.1...11..1111.111.1.11.1..11.11...1..1....111srs=.....111111.1.1.11..11.111.11.1..1..111...1.1111..1.1...11....1srs=.....1111..1..1.1.1..11.1....1...1.11.111111.1.111...11..111.11srs=.....111....1..1...11.11..1.11.1.111.1111..11...1.1.1..111111.1srs=.....11.111..11...111.1.111111.11.1...1....1.11..1.1.1..1..1111These are not all possible SRS for n = 6, there are much more of them.
67,108,864 to be exact.An exhaustive search for all SRS of given length L = 2n is possible only for tiny n. [FXT: filedemo/allsrs-demo.cc] finds all SRS for n = 3, 4, 5. Its output with n = 4 isn = 4 nn = 16....1111.11..1.1....1111.1.11..1....1111.1..1.11....1111..1.11.1....11.1111..1.1....11.1.1111..1....11.1..1.1111....11..1.1111.1....1.1111.1..11....1.1111..11.1....1.11.1..1111....1.11..1111.1....1.1..1111.11....1.1..11.1111....1..1111.1.11....1..11.1.1111total # of SRS found = 16The last SRS is the one that is produced by the algorithm given by Knuth ([12], 2A: ”Generating alln-tuples”) which is implemented in [FXT: file comb/binarydebruijn.h]. Similarly for n = 5, which givesn = 5 nn = 32.....11111.111..11.1.11...1.1..1.....11111.111..11.1.11...1..1.1.....11111.111..11.1.1..1.11...1.....11111.111..11.1.1..1...1.11.....11111.111..11.1.1...1..1.11[-snip-].....1...11..1.1.11.1..111.11111.....1...11..1.1..11111.11.1.111.....1...11..1.1..11111.1.11.111.....1...11..1.1..111.11.1.11111.....1...11..1.1..111.1.11.11111total # of SRS found = 2048CHAPTER 12.
SHIFT REGISTER SEQUENCES256For the search only the cyclic minima of the sequences are considered. The bit-combinations are generatedwith the functions for bit-reversed combination in lexicographic¡ ¢ order given on page 169. The run forn = 5 completes in a few seconds, with the algorithm used 25400 bit-patterns are tested. For14 = 4, 457,¡56¢n = 6 the number of bit-combinations to check would already equal 30 = 6, 646, 448, 384, 109, 072.The total number of SRSs is Sn = 2x where x = 2n−1 − n:n12345678Ln = 2 n248163264128256x0014112657120Sn = 2 x112162048671088641441151880758558721329227995784915872903807060280344576The second column gives the length of the SRSs.
One has Sn+1 = Sn2 Ln−1 , equivalently xn+1 =2 xn + n − 1.The two SRSs for n = 3 are [...111.1] and [...1.111], reversed sequences are considered differentn−1with the above formula. The general formula for the number of base-m SRSs is Sn = m!m /mn , asgiven in [12].
A graph theoretical proof for the case m = 2 can be found in [14], p.56.12.2.1Searching primitive polynomialsWhile computer algebra systems and number-theoretic libraries usually have a built-in function for testingirreducibility a routine for checking primality is most often lacking. The methods sometimes given such aschecking that mod(xk , c) ≡ 1 for all divisors of the maximal order that are greater than n get impracticalquickly as n grows. Already with n = 144 one has m = 2144 − 1 (which has 262144 divisors of which262112 have to be tested) so the computation gets expensive.A better solution is a modification of the algorithm to determine the oder in a finite field given on page72. The implementation given here uses the pari/gp (entry [75] in the bibliography) language:nn = 0; /* max order = 2^n-1 */np = 0; /* number of primes in factorization */vp = []; /* vector of primes */vf = []; /* vector of factors (prime powers) */vx = []; /* vector of exponents */polorder(p) =/* order of the polynomial p */{local(g, g1);local(te);local(tp, tf, tx);g = x;te = nn;for(i=1, np,tf = vf[i]; tp = vp[i]; tx = vx[i];te = te / tf;g1 = Mod(g, p)^te;while ( 1!=g1,g1 = g1^tp;te = te * tp;););return( te );}As given, the algorithm will do np exponentiations modulo p where np is the number of different primesCHAPTER 12.
SHIFT REGISTER SEQUENCES257in the factorization in m. For n = 144 one has np = 17. Note that for prime m = 2n − 1 (that is, m aMersenne prime) irreducibility suffices for primality1 .A shortcut that makes the algorithm terminate as soon as the computed order drops below maximum ispolmaxorder_q(p) =/* early-out variant */{local(g, g1);local(te);local(tp, tf, tx);local(ct);g = x;te = nn;for(i=1, np,tf = vf[i]; tp = vp[i]; tx = vx[i];te = te / tf;g1 = Mod(g, p)^te;ct = 0;while ( 1!=g1,g1 = g1^tp;te = te * tp;ct = ct + 1;);if ( ct<tx, return(0) ););return(1);}Using polmaxorder_q() and pari’s built-in polisirreducible() the search for the lowest-bit PPs up todegree n = 400 was a matter of 90 minutes on a 1,333MHz machine (AMD Athlon).
Note that a table[FXT: file data/mersenne-factorizations-400.txt] of precomputed factorizations taken from [26] wasused in order to save computation time.The data in [FXT: file data/minweight-primpoly.txt] (and the corresponding [FXT: ulongminweight primpoly in auxbit/minweightprimpoly.h]) lists minimal weight PPs where the coefficients/bits (apart from the constant and the leading term) are as close to the low end as possible.For n ≤ 400 the entries where the second coefficient is bigger than in all prior lines are:2,1,05,2,08,4,3,2,012,6,4,1,018,7,033,13,055,24,073,25,089,38,0134,57,0178,87,0212,105,0284,119,0316,135,0370,139,0Primitive polynomials where the weight (that is, the number of nonzero coefficients is minimal) are givenin [FXT: file data/minweight-primpoly.txt]. For many n there exist PPs with just three non-zerocoefficients, these are called trinomials.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
