BigEd on Thu 21 Jul 2022 wrote:
People sometimes try to flip a data bit or two to make the thing match, but I think it's rarely successful, so it's not practical error correction.
I had similar belief about 10 years ago. With further research, I found more effective techniques. Tape warble and bit-slip are lost causes but more advanced cases are surprisingly resilient.
I have 256 bit cell networking running on Auduino Due (84MHz Atmel SAM3E ARMv6) and this has been a good prototype for 8 bit implementation. Decoded cells are 24 byte. The wire format is unusual but allows multiple decode strategies. It can also be adapted for magnetic storage. In particular, payloads per marker can be increased or interleaved. The cells have 6854 style, 16 bit frame marker and 3*80 bit payloads which each use a standard Hamming code. This allows multiple bit flips per marker and one bit flip in each 80 bit payload. The test suite uses Unix pipelines to simulate, for example, drop-out and mains triac noise at different frequencies. The results are encouraging.
For 6502 tape storage, it is possible to convey 256 bytes as 16 sets of 128 bits. If the 16 bit-streams are interleaved then it is possible for any sequential run of 16 bit errors to be recovered - or any fortuitous arrangement where there is a maximum of one error per stripe. If bits are skewed towards zero and we always guess that a dropped bit is zero then we are more likely than average to not require error correction. A matching guess doesn't count as error. It is only *conflicting* bits which are errors. In AndersNielsen's case, that is the most problematic double wave. Therefore, we can fix one double wave per stripe and, optimistically, a maximum of 16 double waves per packet.
If additional bits are sent in each packet then it is possible to convey CRC32 with each page. CRC32 guarantees that three further bit flips will always be rejected while a greater number are improbable. The CRC is itself subject to Hamming correction. Therefore, in the most perverse case, everything in a packet may be sent correctly with the exception that 16 ones in the CRC are set to zero. This packet will be decoded correctly and the CRC will be valid. If block numbers are conveyed in the additional bits then it is possible to implement FEC [Forward Error Correction] and send redundant blocks. In the most trivial case, this works like RAID5 where N+1 blocks convey N blocks of data. In the most trivial case, bytes can be re-constructed in the manner that a total can be use to deduce a missing figure. In a more advanced case, the same Hamming correction algorithm can be applied longitudinally across bits in 128 pages. And then the same CRC32 can be applied to detect failure of the Hamming correction with high confidence. Most notably, data can be conveyed with more confidence than MicroSD.
Hamming encode requires more processing power than decode. However, it is not a problem if encode is slightly slower. Pauses in the bit-stream always occur in the correct places and packets will not be dropped due to poor timing.
Obviously, there is a catch to all of this (in addition to writing mind-bending, interrupt driven software). The algorithm is *huge*. A table for CRC32 is 1KB. The ARM implementation is approximately 5.5KB and I spent disproportionate effort to make the bit stuffing wire format work only with 32 bit left shift operations. This is guaranteed to be larger and slower on 6502. For reference, the first revision of the Commodore peripheral protocol was approximately 600 bytes. This covers floppy disk, hard disk, printer and plotter. Atari SIO is less than 400 bytes and is similarly flexible. 6000 bytes or more for tape is unacceptably large. That is why Hamming codes and similar were restricted to turbo tape loaders. The operating system's standard tape loading algorithm could be used to read the turbo loader and that could read the remainder of the tape faster and more reliably. The faster mechanism isn't default because it would require another 8KB ROM.
This isn't unique to 6502. The Z80 Galaksija is a very parsimonious Eastern European system. It looks as varied as the COSMAC ELF and has display similar to early Apple II text mode. Indeed, to reduce cost, the optional second ROM contains floating point and lower case ASCII. Like the Z80 Sinclair computers, it updates display in software. However, to reduce ROM, spare bits in display NOP operations hold the keymap. Unfortunately, to make everything fit into the base ROM, the developers had to drop their preferred tape encoding. Instead, it used a slower, inferior algorithm.
Login
Register
FAQ
Search
