I was wondering if anyone has ever seen, written, or used any 6502 code which implemented any kind of Forward Error Correction?

I vaguely remember thinking that it wouldn't be too hard to compute and send row and column parity for a block of data bytes: if there was then exactly one row and one column parity error, that gives a single bit to flip back to fix it. (If there was exactly one parity error in total, it can also be treated as a single bit error.)

But I never wrote any code.

(Mentioned recently in this thread about floppy formats)

I've thought about it from time to time over the years, but never done it.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

The only concrete example I know of is the stock C64 tape format, which simply repeats every block and header twice. If there's a read error somewhere, it gets a second chance. Each byte is parity-checked, so a form of erasure coding may be possible - ie. only re-read the bytes that failed to decode - but I somehow doubt that the C64 KERNAL routines are that smart.

Of course, there are many implementations of checksums to detect errors. The topic here is correcting those errors, up to some limit, without needing to re-read the data; on a tape, the latter option would require asking the user to manually rewind the tape to go over the bad block. There's a number of well-known techniques for this, with varying tradeoffs of space, speed, and effectiveness. Space and speed are traditionally at something of a premium on a 6502… It should be reasonably straightforward to implement Hamming codes, though.

If we assume the Acorn block format, which has 28 bytes of meaningful overhead (from filename field to data CRC inclusive) and use 192-byte data blocks, then we have 220 meaningful bytes to operate on. Adding 9 further bytes of selective parity information, and inserting them strategically into the byte sequence, gives us an "extended Hamming code" capable of correcting any one-byte error in that block (strictly, any one-bit error in any one byte-wise bit position), and detecting any two-byte error. Since the total number of bytes in the block at most 256, these 9 bytes are adequate for the purpose, and we can efficiently index over the block on our 6502. Indeed we can accommodate up to 247 payload bytes alongside the 9 parity bytes in a 255-byte block, before we have to enlarge the code.

In this extended Hamming code, bytes within the block are numbered starting from 0. The parity bytes are inserted at positions 0, 1, 2, 4, 8, 16, 32, 64, 128; the payload bytes occupy the other positions. It will be necessary to rearrange the bytes in the input so that they conform to this format, and restore them after decoding. The eight latter parity bytes are calculated as the exclusive-OR of all the bytes in positions whose addresses AND the parity-byte's own position are non-zero. The parity byte in position 0 is calculated as the exclusive-OR over all bytes in the block, including the other parity bytes. So, generating the parity bytes is very straightforward.

Decoding is also fairly easy if you assume that a complete byte has been corrupted, rather than random bits possibly scattered across several bytes. The principle can be extended to cover the latter case, with some complication in the code.

Start by generating a fresh copy of the parity bytes from the received data, and storing them separately. Ensure that they are exclusive-ORed with their corresponding parity bytes as received (which is easy to arrange for as part of the recalculation). If they are all zero, then there are no errors to correct. If they are all either zero or some common value (and, in particular, the 0 parity is this common value), then this common value indicates which bits are wrong in the errored byte, and the OR function over the non-zero parity bytes' positions gives the position of the byte in error (which, let's not forget, might actually be one of the parity bytes). A simple exclusive-OR operation is then sufficient to correct that byte. But if neither of these conditions hold, then more than two bytes are in error.

The Hamming code is much less powerful than, say, a Reed-Solomon code. The latter would be able to correct any 4 byte-errors using the same 9 bytes of added parity information, assuming no erasure information was available. But implementing a Reed-Solomon code is considerably more difficult - something of a project in its own right.

I'm sure there are more efficient ways to implement this, but sometimes the most straightforward way is the correct one.

Splendid! Dare I ask if this is tested? Do you think you might use this approach?

Completely untested so far, but it's potentially useful due to its simplicity and speed, and indeed it's so conceptually simple that it's hard to get wrong (barring implementation bugs). It's likely to have the most value for cases where the alignment of bytes is reliable but the value of an individual byte might be lost. Once the basic scheme is implemented with confidence, it can be extended to larger block sizes with proportionately greater corrective power, by interleaving - for example, using five interleaved 205-byte payloads to cover a 1024-byte block, requiring 45 additional bytes of parity, and being able to correct a 5-byte burst error.

And then there is the possibility of cross-interleaving for greater corrective power; CDs use cross-interleaved Reed-Solomon codes. One way of doing that is to treat entire blocks as elements of the code, much as I'm using bytes as elements in the above. On the other hand, a different sort of code might be more efficient for that purpose.

I've also just come across Golay codes, which may be a useful middle ground between Hamming and Reed-Solomon codes. Golay codes require as much parity data as payload, but they are more powerful than Hamming codes while still being tolerably easy to understand and decode. They come in a fixed size - 12 bits payload expanding to 24 bits with the parity data - so would need to be used in interleaved form. But I have a feeling this is a code type better suited to communication than storage.

Some good news, I've finally wrapped my head sufficiently far around Galois Field arithmetic to understand how to implement a Reed-Solomon encoder on 8-bit symbols using the 6502. There doesn't seem to be any particular difficulty introduced by the 6502's capabilities for that half of the operation, though to run it efficiently will require about 1KB of RAM to be set aside - half for buffers, the other half for lookup tables (which could be in ROM).

The algorithms needed for Reed-Solomon decoding are considerably more complex. However I have some hope that they are also reasonably implementable on the 6502. Verifying that there are no errors, however, is simply a matter of generating the parity symbols from the received data, and comparing them to the received parity symbols. So the complex decoding only needs to be run in the case where that verification fails, and hence there is an error to correct.

> the complex decoding only needs to be run in the case where that verification fails, and hence there is an error to correct.

That's hopeful!

It's not in 6502, but nearly 20 years ago I designed a synthesisable Reed-Solomon encoder/decoder in Verilog. This was a heavily pipelined parallel implemetation, where the code could be specified as a parameter.

There are a couple of HP Labs Tech Reports that describe this work in quite a lot of detail:

Design of a Synthesisable Reed-Solomon ECC Core

Verification of a Synthesisable Reed-Solomon ECC Core

These might be of some use to you, as they cover the both the encoder and decoder implementations at quite a low level.

As part of the verification, this was synthesised to a Xilinx Vertex-E XCV1000E-6 FPGA, and took about 80% of the available space, including all the text fixtures. This device is similar in size to a XC6SLX25. The code we used was a RS(160,128,t=16) code.

I still have all the text books as well.

It would be great to see some 6502 code for Reed Solomon coding.

Dave

What's the net effect of this R-S coding for 8 bit symbols: how many bits in an input chunk get transformed into how many bits of output chunk?

One of the quirks of Reed-Solomon is that there are quite a few different methods of decoding it. I'll probably go for some of the more conceptually simple decoding algorithms at each step, even if they turn out a bit slower. The aim is to recover from a medium error somewhat gracefully, and it doesn't have to be in realtime (unlike say a CD-ROM drive). With any luck it should be practical to build into the firmware of a standalone drive controller, which could in principle be attached to a variety of SBCs or micros.

For example, I've seen papers which recommend using Cramer's rule (involving finding the determinant of matrices) to solve the linear equation system that comes right at the end of the decoding process. As soon as you have more than two symbols to correct, you have to recurse into the determinant function because the direct rule only works for 2x2 matrices, and that sounds like it would be awkward on the 6502. So I'm more comfortable with applying the Gauss-Jordan method, which is mainly iterative rather than recursive.

With that said, I think I have the concepts lined up reasonably well now, even with no actual code written. What I need next is to adapt my 65C02 simulator (long overdue) so that I can efficiently use it as a unit test rig.


R-S works on block of symbols, some of which are allocated to data and some to parity (conceptually similar to the Hamming code I posted above). The maximum block size is one less symbol than the size of the alphabet in each symbol - in this case, 255 bytes. You need one parity byte per erasure (known-bad byte) or two per error (bad byte whose location is unknown). So a direct analogue to the Hamming code, using 9 parity bytes, would be able to correct 4 errors plus one erasure, or nine erasures, or something in between.

So one could rig up something that dealt in, say 64 byte data + 7 parity bytes?

(Thanks for the links to your previous work Dave - very impressive!)

That's right. CD-ROM uses a cross-interleaved RS code in which the primary (outer) code has 28 data bytes and 4 parity bytes, then the secondary (inner) code has 24 data bytes and also 4 parity bytes. The two codes are essentially at right-angles to each other, forming a 28x32 byte rectangle, and decoding failures in the outer code are processed as erasures in the inner code, increasing the effective decoding power dramatically.

A slightly more space-efficient scheme could interleave 17 RS blocks, each with 241 data bytes and 14 parity bytes, to form a 4096-byte payload block. This would be able to correct 7 errors in each sub-block; properly interleaved, that could be up to 119 consecutive byte errors corrected without erasure information.

Oh right, so a natural level to apply RS is about the length of a floppy track? And you wouldn't have to decode too deeply if all had gone well. And less than 10% overhead.

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: 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: 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. 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.

If you get the Reed Solomon decoding working then I have around 200 'DiskOnChip' (early flash) devices that I bought thinking they might make nice storage devices for small micros. They have a built in encoder that calculates the checksum as bytes are written but you have to decode and fix the errors in software.

If I can't find a use for them then they are going to be upcycled as an art project.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs