[<<][math][>>][..]Sun Aug 8 08:44:55 CEST 2010

A binary LFSR sequence ultimately comes from a cycle in the multiplicative group of a finite field GF(2^n). This is a unique mathematical structure with a bunch of representatives that are all isomorphic. So, what does the automorphism group of a finite field look like? One place to look for some intuition is in Gold Codes[1]. This is the only practical application I know where two sequences with different generator polynomials are combined to form a new sequence with useful properties. Interesting properties of Gold codes: * Low autocorrelation (this is a "meaningless" property, as they are selected * The XOR (+) operation is closed PROOF: Say s1(n) and s2(n) are LFSR sequences of the same lenght. A gold code is constructed as g(n) = s1(0) + s2(n). We then have g(a) + g(b) = s1(0) + s2(a) + s1(0) + s2(b) = s2(a) + s2(b) = ... ??? (hmm... it seemed obvious - not awake yet) A link I found about finite field automorphisms[3]. Time to finally get into Galois Theory[4]. But what do I know? It has to do with the structure of the multiplicative group. I would think that the symmetry group gets larger if the multiplicative group is very composite. So, which GF(2^n) have prime order multiplicative groups? Are there primes that look like 2^n-1? Mersenne primes[7]. But is it really primes we're looking for, not maximally composite numbers? [1] http://en.wikipedia.org/wiki/Gold_code [2] http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1054048 [3] http://everything2.com/title/automorphisms+of+finite+fields [4] http://en.wikipedia.org/wiki/Galois_theory [5] http://en.wikipedia.org/wiki/Safe_prime [6] http://en.wikipedia.org/wiki/Strong_prime [7] http://en.wikipedia.org/wiki/Mersenne_prime

[Reply][About]

[<<][math][>>][..]