When I originally wrote my Reed-Solomon encoder, I used the basic polynomial long division method directly. This made a lot of sense at the time. It turns out that there is actually a slightly better method.
The issue with my encoder is that it took 16 cycles to shift in data. This led to the data buffer and parity buffer, as well as the need for some extra control logic to allow the user to have expected input cadences. It turns out that there is actually a related structure that can calculate the remainder without needed these initial shift stages. This somewhat simplifies the logic, and also reduces the latency.
As before, the goal is to compute 
New Encoder
This new method directly computes the value by shifting the input into the MSB, instead of the LSB. This generates the structure shown on the left. This method will generate the correct remainder in the end, but intermediate states of the lfsr will not be the same as when the LFSR had values shifted in from the left.
Conceptually, this new method can be seen more along the lines of the following relation:
And by this, I mean that the effect of the most significant coefficient on the remainder is computed, and added to the effect of the next most significant coefficient, and so on. By virtue of being a linear system, all of these can be performed efficiently in the same registers. For the encoder, the most significant coefficient’s effect can be computed in N-K cycles, then next’s in N-K-1 cycles, and so on.
One issue is that it is a bit harder to follow, as intermediate states are sums of partially complete processes. For the long division method, it is fairly easy to see how and why the next state is determined. Below is an example of division of 1011000 by 1101 in GF2[x]. Remember that this is not 2’s complement math.
- init state = 000
- step 1, input = 1, fb = 1, state = 101
- step 2, input = 0, fb = 1, state = 111
- step 3, input = 1, fb= 0, state = 110
- step 4, input = 1, fb = 0, state = 100
As a quick check, here is the long division which arrives at the same result:
- 1011000 – 1101000 = 0110000
- 0110000 – 0110100 = 0000100
The long division in this case seems shorter. That is mainly because I didn’t show the leading or trailing “subtract 0” lines.
And finally, these are the effects of each input bit on the remainder:
- 1000000 mod 1101 = 110
- 0010000 mod 1101 = 111
- 0001000 mod 1101 = 101
The summation of these is 100, which is the same as the remainder.
The conclusion is that the encoder is now a bit smaller. The encoder was already very small though, and the logic that was removed was already compact. From a space savings perspective, the changes to the code certainly were not worth it, even though the changes literally only took an hour to write and test. The main advantages would be in porting the code to an ASIC, or in cases where the slightly lower latency is important.
The files updated are here:
- rs_gen.py – the code generator for rs_encode_logic.vhd
- rs_encode_logic.vhd – the generated code.
- rs_encoder.vhd – the top level.
- rs_encoder_pkg.vhd – a package.