Arndt - Algorithms for Programmers (523138), страница 46
Текст из файла (страница 46)
It corresponds to the so-called Galois setup of the shift register. For a comparison ofGalois- and Fibonacci- setup see [68].A demo can be found in [FXT: file demo/fcsr-demo.cc], using c = 37 one getsc = 1..1.1 = 370 :a= .....11 :a= ....1.2 :a= ...1..3 :a= ..1...4 :a= .1....5 :a= 1.....6 :a= .11.117 :a= .1...18 :a= 1...1.9 :a= .1111110 :a= .11..111 :a= ..11.112 :a= .11.1.13 :a= ..111114 :a= .1111.15 :a= .1.11116 :a= ..1..117 :a= .1..1.18 :a= 1..1..19 :a= 1...1120 :a= 1....121 :a= .111.122 :a= .1.1.123 :a= ...1.124 :a= ..1.1.25 :a= .1.1..26 :a= ....1127 :a= ...11.28 :a= ..11..29 :a= .11...30 :a= ..1.1131 :a= .1.11.32 :a= ...11133 :a= ..111.34 :a= .111..35 :a= .1..1136 :a= .....137 :a= ....1.38 :a= ...1..39 :a= ..1...40 :a= .1....41 :a= 1.....42 :a= .11.11===========================================1248163227173431251326153023918363533292151020361224112271428191248163227w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=w=.1..111..11...11...11...11....1..........1....11...11...11.1.11.1111.1111.111..111.1111.1.11.1.11.1.11.1.11.1.11...11..111..111..111..1111.1111111111.1111..111..111..1.1..1....1....1...11...1....1.1..1.1..1.1..1.1..1.1..111..11...11...11...11....1..........1===========================================19381224483213613275546295853432244255139153162605750368173451020411938122448321Note that the w do not run through all values < c.The primitive polynomials are replaced by the ‘primitive’ primes (those primes where 2 is a primitiveroot).
The following list is complete for c < 2048:x:1:2:3:4:5:6:7:8:9:10:p prime with 2 a primitive root, 2**x <3511 1319 2937 53 59 6167 83 101 107131 139 149 163 173 179 181 197 211 227269 293 317 347 349 373 379 389 419 421523 541 547 557 563 587 613 619 653 659773 787 797 821 827 829 853 859 877 8831061 1091 1109 1117 1123 1171 1187 12131283 1291 1301 1307 1373 1381 1427 14511523 1531 1549 1571 1619 1621 1637 16671747 1787 1861 1867 1877 1901 1907 19311997 2027 2029p < 2**(x+1)443 461 467 491 509661 677 701 709 757907 941 947 10191229 1237 1259 12771453 1483 1493 14991669 1693 1733 17411949 1973 1979 1987For the correspondence between LFSR and CFSR see [67].CHAPTER 12.
SHIFT REGISTER SEQUENCES12.5270Linear hybrid cellular automata (LHCA)Consider 1-dimensional linear cellular automata (with 0 and 1 the only possible states) where two differentrules are applied dependent2 of the position:inline ulong lhca_next(ulong x, ulong r, ulong m)// return next state (after x) of the// lhcr with rule defined by r, length defined by m:// Rule 150 is applied for cells where r is one, rule 90 else.// Rule 150 := next(x) = x + leftbit(x) + rightbit(x)// Rule 90 := next(x) = leftbit(x) + rightbit(x)// m has to be a burst of the n lowest bits (n: length of automaton){r &= x;ulong t = (x>>1) ^ (x<<1);t ^= r;t &= m;return t;}[FXT: lhca next in auxbit/lhca.h]The naming convention for the rules is as follows: draw a table of the eight possible states of a celltogether with its neighbors then draw the new states below:XXX0XX0XX0X0X00X0XXX0X0000XX0000Now read the lower row as a binary number, the result is 90, so this is rule 90.
Rule 150 isXXXXXX00X0X0X00X0XX00X0X00XX0000It turns out that for certain r the successive states x have the maximal period m = 2n − 1, all non-zerovalues occur. This is demonstrated in [FXT: file demo/lhca-demo.cc], which for n = 5 (and rule r = 1)gives:rule = ....11....12...113..11.4.1111511...6111..71.11.8..1119.11..101111.111..1112.111.1311.111411.1.1511..11611111171....18.1...191.1..20...1.21..1.122.1..1231.11124..1..25.1.1.261...127.1.11281..1.29.11.130111.1311.1.1== 0x1length=5There is an intimate connection between linear hybrid cellular automata (LHCA) and the linear feedbackshift registers (LFSR, see also section 12.2 on page 254).
This is nicely pointed out in the very readablepaper [65] which is recommended for further studies.Rule sets (with minimal weight) that lead to maximal period can be found in [66]. The list [FXT: ulongminweight lhca rule in auxbit/minweightlhcarule.h] was generated from that source:2 thereforethe ‘hybrid’.CHAPTER 12.
SHIFT REGISTER SEQUENCES271#define R1(n,s1)(1UL<<s1)#define R2(n,s1,s2) (1UL<<s1) | (1UL<<s2)extern const ulong minweight_lhca_rule[]=// LHCA rules of minimum weight that lead to maximal period.{0, // (empty)R1( 1, 0),R1( 2, 0),R1( 3, 0),R2( 4, 0, 2),R1( 5, 0),R1( 6, 0),R1( 7, 2),R2( 8, 1, 2),R1( 9, 0),R2( 10, 1, 6),R1( 11, 0),R2( 12, 2, 6),R1( 13, 4),...};Up to n = 500 there is always a rule with weight at most 2. Quite pretty patterns emerge with LHCA,the following is the beginning part of the run for n = 27:rule = .......1..................11..........................12.........................113........................11.4.......................11115......................11...6.....................1111..7....................11..11.8...................111111119..................11.......10.................1111......11................11..11.....12...............11111111....13..............11......11...14.............1111....1111..15............11..11..11..11.16...........111111111111111117..........11...............18.........1111..............19........11..11.............20.......11111111............21......1.......11...........22.....1.1.....1111..........23....1..11...11..11.........24...1.11.11.11111111........25..1..11.11.1......11.......26.1.1111.11..1....1111......271..1..1.1111.1..11..11.....28.11.11..1..1..111111111....29111.1111.11.111.......11...301.1.1....11.1.11.....1111..31.....1..111...111...11..11.32....1.111.11.11.11.1111111133...1..111.11.11.11.1.......34..1.11111.11.11.11..1......35.1..1..11.11.11.1111.1.....361.11.11.1.11.11.1..1..1....37..11.11...11.11..11.11.1...38.111.111.111.111111.11..1..3911.1.1...1.1.1....1.1111.1.4011....1.1.....1..1..1..1..141111..1...1...1.11.11.11.111421.111.1.1.1.1..11.11.11.1..43..1.1........1111.11.11..1.12.6== 0x80001length=27NecklacesA sequence that is minimal among all its cyclic rotations is called a necklace.
When there are k possiblevalues for each element one talks about an n-bead, k-color (or k-ary length-n) necklaces. We restrict ourattention to the case were only two sorts of beads are allowed and represent them by 0 and 1.Scanning all binary words of length n as to whether they are necklaces can easily be achieved by testingwhether x==bit_cyclic_min(x,n) (see section 8.14). For n = 7 one gets the sequence of binary necklacesof length n (see [FXT: file demo/necklace-demo.cc]):.............1= 0= 1CHAPTER 12. SHIFT REGISTER SEQUENCES.....11....1.1....111...1..1...1.11...11.1...1111..1..11..1.1.1..1.111..11.11..111.1..11111.1.1.11.1.1111.11.111.1111111111111n = 7:272= 3= 5= 7= 9= 11= 13= 15= 19= 21= 23= 27= 29= 31= 43= 47= 55= 63= 12720 necklacesThe number of binary necklaces of length n isNn=1 Xϕ(d) 2n/dnd\n=n1 X gcd(j,n)2n j=1(12.5)Replace 2 by r to get the number for r different sorts of beads (possible values at each digit),see [13], pp.139-141.n12345678910Nn2346814203660108n11121314151617181920Nn1883526321182219241167712146022759652488n21222324252627282930Nn9988019074636472469925213421842581428497106895875801851279235792568For prime n = p we havep−1 µ ¶2p − 21 X p=2+(12.6)ppkk=2¡ ¢The latter form transpires that there are exactly kp /p necklaces with k elements for 2 ≤ k ≤ p − 1 plusthe two elements that consist of all zeros or ones.Not all necklaces are created equal: all can be considered periodic with a period that is a divisor of thelength.
The necklaces of length n = 6 together with their periods areNp...........1....11...1.1...111..1..1..1.11..11.1..1111.1.1.1.1.111.11.11.11111111111= 2+16666366626361For n prime the only periodic necklaces are those two that contain all ones or zeros. Aperiodic (oreqivalently, period equals length) necklaces are also called Lyndon words.
The number of aperiodicnecklaces is1 X1 XMn =µ(d) 2n/d =µ(n/d) 2d(12.7)nnd\nd\nCHAPTER 12. SHIFT REGISTER SEQUENCESn12345678910Mn21236918305699n11121314151617181920Mn1863356301161218240807710145322759452377273n21222324252627282930Mn9985819055736472269887013421762580795497100895863951851279035790267The number of of degree-n irreducible polynomials with coefficient modulo two is also Mn .
The exceptionis n = 1 where there is just one polynomial. The entry for n = 1 is special anyway because both ’0’ and’1’ are of the maximal period. For the equivalence between necklaces and irreducible polynomials overGF(2) see [71]. The same source gives a constant amortized time (CAT) algorithm to generate all k-arylength-m necklaces:longlonglongvoid{////*a; // data in a[1..m],m; // lengthk; // k-arycrsms_print(long p)a[0] = 0long mm = m;// no condition: pre-necklaceif ( p!=m ) return; // Lyndon wordsif ( 0!=(m%p) ) return; // necklacesif ( 0!=(m%p) ) return; else mm = p; // de Bruijn seqfor (long j=1; j<=mm; ++j) cout<< " " << a[j];cout << endl;}void crsms_gen(long n, long p){if ( n > m ) crsms_print(p);else{a[n] = a[n-p];crsms_gen(n+1, p);for (long j=a[n-p]+1; j<k; ++j){a[n] = j;crsms_gen(n+1, n);}}}int main(int argc, char **argv){m = 4; // lengthif ( argc>1 ) m = atol(argv[1]);k = 2; // k-aryif ( argc>2 ) k = atol(argv[2]);long aa[m+1];a = aa;a[0] = 0;crsms_gen(1, 1);return 0;}Depending the function crsms_print one can also generate pre-necklaces, Lyndon words or a de Bruijnsequence.The binary necklaces of length n can be used as cycle leaders in the length-2n zip-permutation (and itsinverse) that is presented in section 7.5.CHAPTER 12.
SHIFT REGISTER SEQUENCES274The length-n necklaces for n an exponent of a Mersenne prime m = 2n − 1 can be generated efficientlyby simply going through the powers of a primitive root r of m until the second word with just one bit isreached. With n = 7, m = 127 and the primitive root r = 3 we get0 :1 :2 :3 :4 :5 :6 :7 :8 :9 :10 :11 :12 :13 :14 :15 :16 :17 :18 :19 :20 :21 :22 :23 :24 :25 :[...]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=......1.....11...1..1..11.111.1...1111.1..1.1111...111..1.1.1..11111.11111..111.11.11..1..11.111....1.11.1....1.1...1111.1.11.....1.....11...1..1..11.11..1...11.1.1..111111.1.111....==========================1392781116942884125121109739222667186412361087083122112=^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^==^=......1.....11...1..1..11.11...11.1..111.1.1.1111....111..1.1.1.111111..11111.11.111..1..11..1.111...1.11....1.1...1111.1.1.11......1.....11...1..1..11.11...11.1..111.1.1.1111....111The two words of all ones/zeros have to be added.12.7Necklaces and Gray codes *There are 8 binary necklaces of length 5:.........1...11..1.1..111.1.11.111111111Discard the first and last necklace (those with all zeros/ones) and create a Gray code of the remainingwords by hand.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
