CPCWiki forum

General Category => Programming => Topic started by: cpcitor on 16:11, 10 November 17

Title: Tape with error-correcting code ?
Post by: cpcitor on 16:11, 10 November 17
The firmware tape loading system is very robust.  It adapts automatically to signal inversion, changing speed between blocks, and not-too-important speed variation within a block.

We all know that we can just bump up the speed until reliability degrades too much.

Now, we live in a post-"breaking baud" world.  More progress is possible.

What now?

How about a somehow generic loader that starts with a very short program, then loads main payload really quickly and reliably even on a real imperfect tape?

Okay, but how?

Non-critical transfer

Data can be sent or marked somehow as non-cricital.  For example, loading screens are nice, but in most case glitches in one while loading a game is not a showstopper. 

(1) in simple cases, the data is corrupt but its length is known. Just write whatever was decoded or even 0 until we decode something again.

(2) Still, garbled data might confuse about the estimated length. The write pointer in RAM can become misaligned... for how long? To handle that, some checkpoints can be inserted regularly (e.g. every 80 bytes) to make sure RAM write pointer is correctly positioned. 
Let's call that "start codes" by imitation of the term used in some encodings (e.g. digital video streams).
I let you guess why I consider 80 bytes alignment in a CPC image loading program. ;-)

Error-correcting codes

What if we send data at a speed so high that transfer is less reliable?  Then, by definition errors will happen. There exist error correcting codes that can take care of that.  Hamming, Reed-Solomon, Convolutional codes, Turbo codes, Viterbi, LDPC...

You might think "What's the point? Go too fast and you crash and get nowhere!"

Since those code are widely used, I guess their benefits outweight the transfer speed reduction due to their overhead.

At first sight, they seem too complicated for the CPC, but people have use such codes in hardware for decades (e.g. reading CD audio and CD-ROM, space communication)... and also in modern 8bit microcontrollers.

A number of complicated codes can be simplified at run-time by using lookup tables.  For example, http://www.robotroom.com/Hamming-Error-Correcting-Code-1.html receives data using a table that can be stored in 128 bytes, and includes sample C code with several routines to encode and decode, depending on memory/CPU/complexity trade-off.

Append redundant blocks

If loading was fine, the loader has finished. Showtime!

What if it hasn't? What if some blocks were incorrect?

On the CPC firmware, there is the "rewind tape" message. Rewind and retry.

Other possibilities?  If that isn't enough, one can add redundant blocks.

If loading was perfect, program just runs and ignore redundant blocks.  If it wasn't enough, redundant blocks acting similar to parity check are used to find and correct the rest.  A number of schemes are possible, under the general principles of Fountain codes https://en.wikipedia.org/wiki/Fountain_code .

LT code might be a good candidate. To summarize, after sending blocks that are equal to the actual data, one sends additional blocks that are XOR combinations of the initial blocks.  Those additional blocks allow to detect and correct errors in the initial blocks.  As soon as the data is completed, the loader can stop and ignore the remainder of the tape.

Net result

A loading system that is so fast that it's just initially barely reliable, but with the help of extra redundant blocks achieves reliability.

Sure this needs custom loading routines from the lowest level!  But we're in a post-"Breaking Baud" world aren't we?

When/who?

I remember having disassembled the speech routine of "Orphée" https://youtu.be/cWBuC71PaVc?t=18 and written an audio digitizer (in about 1990).

Recent history shows that I tend to be active on CPC for a period every two years. But I share my achievements, e.g. here and on https://github.com/cpcitor/ . Let's discuss what we can, feel free to experiment, we'll see how it goes.

Cheers!  ;)