You might want to convince yourself that you can divide a polynomial f by its leading coefficient a_k to get another polynomial that generates a sequence that's just a multiple of that of the first.Golomb S W, Shift Register Sequences, Holden-Day, Laguna Hills, CA, USA, 1967. (The expression cf is the key to understand the part of the Wikipedia article that confounded you. So the remainder is g - cf, which is a polynomial with degree k-1. For a field (as I'm assuming), that's some number c. , then the first step in long division is computing b_k / a_k. , and the new state g looks like b_k X^k +. If the divisor polynomial f looks like a_k X^k +.
If you're using rings of coefficients other than bits, you need to think about what one step of long division looks like. The shift operation is the multiplication and the taps are the long division.
Each cycle in an LFSR is equivalent multiplying by X and then one step of long division. The first state of an LFSR is 1, and the second is X. The state of an LFSR in this model is some polynomial of degree less than the degree of f. These remainders are computed with Euclid's algorithm, just like computing remainders for integers.
The most fundamental problem you seem to be having is that you're trying to mimic a binary shift register too closely, not fully understanding what's going on when you view it as a discrete dynamical system, rather than as a circuit.īinary shift registers are a clever circuits that compute the remainders of X^N when divided by f(X), where all the coefficients of f are in the ring Z/2Z, the ring containing only 0 and 1. I'd recommend you acquaint yourself with the concept of polynomial rings (though that Wikipedia article is rather too technical to make the best introduction). This is what I came up with but instead of giving a cyclic sequence, the output quickly deteriorates to all 0s: # Multiplication table for GF(4) This part doesn't make sense to me: "the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value which is constant for each specific tap point." How can a single output bit be multiplied by values for each tap point? What I would like to do now is write a generalised version that could handle Galois fields other than GF(2) but I don't understand the section about non-binary LFSRs. Return ^state) for i in range(len(state)) ] I used the instructions on Wikipedia to write a Galois linear feedback shift register in Python: def lfsr(coefficients, state):
0 kommentar(er)
