Post by walker7 on Mar 23, 2008 12:25:24 GMT -5
Linear Feedback Shift Registers (LFSR's) are a good way to achieve random numbers in your programs, especially if you use them every VBlank. For a 16-bit LFSR, you might use this piece of code:
move.w #__INTEGER_LFSR,a0
move.w (a0),d0
move.w d0,d1
and.w #$B400,d1
move.w d1,d2
lsr.w #1,d2
eor.w d2,d1
move.w d1,d2
lsr.w #2,d2
eor.w d2,d1
move.w d1,d2
lsr.w #4,d2
eor.w d2,d1
move.w d1,d2
lsr.w #8,d2
eor.w d2,d1
lsr.w #1,d1
roxl.w #1,d0
move.w d0,(a0)
The line in green represents the "taps," that is, the bits that are summed (or XORed) to produce the new output bit that is shifted left into the LFSR. The pink lines compute the parity of the LFSR ANDed with the tapped bits in the least significant bit of the value. The blue lines carry the parity bit into the new value.
A word of caution, do not start the LFSR value at zero. This is because the XOR of all zeros is 0, therefore, the LFSR becomes stuck there. This means that the 16-bit LFSR will cycle through 65,535 states.
You must use an even number of taps. There are four in the example above. 0xB400 becomes 1011010000000000 in binary. The taps are at bits 10, 12, 13, and 15. There is a corresponding polynomial on the ring of integers Z/2Z (mod 2), which is x16 + x14 + x13 + x11 + 1. In an n-bit LFSR, the xn and 1 terms will always be present.
The polynomial mentioned above is a primitive polynomial, because it does not factor into any smaller polynomials on the integer ring Z/2Z (mod 2). The powers in the polynomial are relatively prime (i.e. 11, 13, 14, and 16 have no factors in common except 1). And there are an even number of taps, as mentioned earlier. If all three of these conditions are true, the LFSR's period will be maximal.
To test whether or not a polynomial is primitive on the integer ring Z/2Z (mod 2), go to www.quickmath.com/webMathematica3/quickmath/page.jsp?s1=algebra&s2=factor&s3=advanced and type "2" in the "Modulo" box, and make sure that box is checked. Then type the polynomial in the big "EXPRESSION" box, then click the "Factor" button at the lower-right to test it.
But then, what if you wanted to divide a more-than-32-bit value by a more-than-16-bit value (e.g. a 128-bit value by a 32-bit value)? What would be the best (fastest) way to do that?
move.w #__INTEGER_LFSR,a0
move.w (a0),d0
move.w d0,d1
and.w #$B400,d1
move.w d1,d2
lsr.w #1,d2
eor.w d2,d1
move.w d1,d2
lsr.w #2,d2
eor.w d2,d1
move.w d1,d2
lsr.w #4,d2
eor.w d2,d1
move.w d1,d2
lsr.w #8,d2
eor.w d2,d1
lsr.w #1,d1
roxl.w #1,d0
move.w d0,(a0)
The line in green represents the "taps," that is, the bits that are summed (or XORed) to produce the new output bit that is shifted left into the LFSR. The pink lines compute the parity of the LFSR ANDed with the tapped bits in the least significant bit of the value. The blue lines carry the parity bit into the new value.
A word of caution, do not start the LFSR value at zero. This is because the XOR of all zeros is 0, therefore, the LFSR becomes stuck there. This means that the 16-bit LFSR will cycle through 65,535 states.
You must use an even number of taps. There are four in the example above. 0xB400 becomes 1011010000000000 in binary. The taps are at bits 10, 12, 13, and 15. There is a corresponding polynomial on the ring of integers Z/2Z (mod 2), which is x16 + x14 + x13 + x11 + 1. In an n-bit LFSR, the xn and 1 terms will always be present.
The polynomial mentioned above is a primitive polynomial, because it does not factor into any smaller polynomials on the integer ring Z/2Z (mod 2). The powers in the polynomial are relatively prime (i.e. 11, 13, 14, and 16 have no factors in common except 1). And there are an even number of taps, as mentioned earlier. If all three of these conditions are true, the LFSR's period will be maximal.
To test whether or not a polynomial is primitive on the integer ring Z/2Z (mod 2), go to www.quickmath.com/webMathematica3/quickmath/page.jsp?s1=algebra&s2=factor&s3=advanced and type "2" in the "Modulo" box, and make sure that box is checked. Then type the polynomial in the big "EXPRESSION" box, then click the "Factor" button at the lower-right to test it.
But then, what if you wanted to divide a more-than-32-bit value by a more-than-16-bit value (e.g. a 128-bit value by a 32-bit value)? What would be the best (fastest) way to do that?