So first, let's get the basics of Galois Field arithmetic out of the way. Galois Fields support addition, subtraction, multiplication, and division - but the rules for doing so are very different from those for ordinary integers. Understanding these rules is fundamental for understanding the algorithms involved in Reed-Solomon codes.
A Reed-Solomon code (as usually applied over 8-bit bytes) is based on
discrete polynomials over two different Galois Fields: GF(2) and GF(256). One of these polynomials is used to generate GF(256) from GF(2); the other is used to generate the parity symbols of a message block. Decoding the received message involves solving the roots of this polynomial in a particular way.
GF(2) is simply a binary digit. GF(256) is derived from it by grouping eight GF(2) fields together - which is of course convenient to do on a byte-oriented CPU like the 6502. The trick is that there are two different representations of a GF(256) value, one most suited to multiplication, and one most suited to addition. We convert between the two by computing what amounts to the
discrete logarithm and
discrete exponent. If you've studied cryptography to any extent, at least one of those terms should be familiar. To make this efficient, we can build a pair of lookup tables, and this doesn't take very much memory.
Addition in GF(2) and GF(256) is straightforward - it is the exclusive-OR function. The 6502 has this operation natively. This also means that subtraction is identical to addition.
To multiply in GF(256), we first check whether either operand is zero - if so, the result is also zero. Otherwise, we look up the discrete logarithm of each operand, add them modulo 255 (avoiding zero), and then take the discrete exponent. The following code should suffice:
Code:
; On entry, X and Y contain the values to multiply. On exit, A contains the result. X is clobbered.
GF_Mult:
TXA
BEQ @exit
TYA
BEQ @exit
; neither argument is zero
LDA logTable,Y
DEC A
CLC
ADC logTable,X
ADC #0 ; modulo 255, avoiding zero
TAX
LDA expTable,X
@exit:
RTS
This presupposes we have filled 256-entry logTable and expTable with appropriate values; it is possible to precompute these and stick them in ROM, or to generate them dynamically in RAM. Doing so requires repeatedly evaluating the
generator polynomial of GF(256) over GF(2), which requires some explanation. In effect we are computing successive powers of 2, modulo the generator polynomial, using GF arithmetic - and this generates a repeating sequence of length 255 within GF(256).
There are several generator polynomials which satisfy this property, but Reed-Solomon coders usually take the numerically smallest one, which is often quoted in the literature as X^8 + X^4 + X^3 + X + 1. But X is 2 in this context - since the base Galois Field involved is GF(2) - and it is convenient to write this as the 9-bit value $11B. Obtaining the next power of two is then as simple as multiplying by two (ie. shifting left one place), then if the most significant bit of the result matches the most-significant bit of the polynomial, subtract the polynomial. Note that the usual sense of "greater" or "lesser" doesn't apply here, since we are in a modular number system. And the 6502 makes this operation easy for us, even though it briefly involves a 9-bit value:
Code:
; Generate logTable and expTable for GF(256) over $11B
GF_Init:
; For consistency, both logarithm and exponent of zero are taken as zeroes; really this is 0 == a^(-inf).
; The real tables begin with entry 1 == a^0, both at index 1.
STZ logTable
STZ expTable
LDA #1
TAX
@loop:
; store matching pair of entries
TAY
STA expTable,X
STX logTable,Y
; calculate next exponent
ASL A
BCC :+
EOR #$1B
; and the next index
: INX
BNE @loop
; A should now contain 1 again
CMP #1
BEQ :+
BRK ; oops
: RTS
This method of taking the remainder of a division by the generator polynomial works because a polynomial over GF(2) can have coefficients only of 0 or 1, so we only have a binary decision as to whether to keep or subtract, and don't need to worry about multiplying the generator polynomial by anything. But when we start dealing with polynomials over GF(256), that convenience goes away, as the coefficients can take many values. When calculating by hand, we can use a form of long division, but the notation quickly gets confusing due to the need to refer to the discrete logarithm tables every time we switch between multiplying (to match the values of the leftmost digits) and subtracting.
But this is a good time to establish the correct method of dividing two values in GF(256). In effect, we do this by multiplying the dividend by the reciprocal of the divisor, a process which leaves no remainder. We can use the logarithm table to discover the reciprocal, by observing that we only need to negate the logarithm, and then adjust the resulting table index for the wrap-around of the exponentiation sequence. It probably helps to observe that the reciprocal of zero is undefined (we can take it as zero) and the reciprocal of 1 (== a^0) is also 1 (== a^-0). But the reciprocal of 2 (== a^1) is a^-1 which is also a^254, to be found at offset 255 in the exponent table. Generally, for values other than 0 and 1, subtracting the logarithm from 256 will give the correct logarithm of the reciprocal, to which the multiplication method seen above can be applied.
Code:
; On entry, X is dividend, Y is divisor; on exit, A is quotient.
GF_Div:
TXA
BEQ @exit
CPY #1
BEQ @exit
TYA
BEQ @exit
; neither argument is zero and the divisor is not 1
LDA logTable,X
CLC
SBC logTable,Y
ADC #0
TAX
LDA expTable,X
@exit:
RTS
The above code includes a rather counter-intuitive optimisation resulting from combining the negation of one operand, the decrement of the other, and the addition of the results. I will need to verify that it actually does the right thing, but it
is awfully convenient.
I'll save the problem of calculating the remainder over a polynomial of GF(256) for another post, as that's the fundamental operation for generating the parity symbols of a Reed-Solomon block.