BCH-21,31 implementation for 6502

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
lidnariq
Posts: 11430
Joined: Sun Apr 13, 2008 11:12 am

BCH-21,31 implementation for 6502

Post by lidnariq »

I got around to porting the BCH-21,31 forward-error-correction routines I have to the NES.

Included is a trivial demonstration of both generation and correction working.

FEC let you detect when data corruption has happened, and to a limited extent lets you repair that damage. BCH-21,31 is specifically used in a wide variety of radio protocols (including POCSAG, FLEX, and the GameCube's WaveBird). In the NES, this might be useful in passwords, or perhaps for storage on audio cassette.

Because calculating BCH involves a lot of work on just one bit at a time, I've stored all the numbers in "transposed" manner, one bit per byte, big-endian. However, my routines correctly let you pack multiple bits into those 31 bytes. Note that because this FEC can correct at most two bits, you'll want to plan based on the specific kind of data corruption you anticipate; in RF contexts this transposed layout is beneficial because it distributes single bits of noise over multiple protected words.

Hopefully someone finds this useful.
Attachments
BCH2131.zip
(7.17 KiB) Downloaded 163 times
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: BCH-21,31 implementation for 6502

Post by tepples »

In my opinion, passwords should be short enough for error detection alone. An 8-character password over a 32-character alphabet holds 32 bits of payload and 8 bits of message authentication. Forward error correction on passwords would mean more randomly guessed passwords would be correctable to valid code words. If we set it to correct up to 1 bit flip, how many errors can BCH 21 of 31 detect?

I guess it could be used for ensuring transients at power-off don't corrupt saved games in battery RAM, or for a 2D barcode to upload your high score to a server. I imagine the FEC used in Denso's QR Code (the most commonly seen 2D barcode) is a bit more complex though.
lidnariq
Posts: 11430
Joined: Sun Apr 13, 2008 11:12 am

Re: BCH-21,31 implementation for 6502

Post by lidnariq »

tepples wrote:If we set it to correct up to 1 bit flip, how many errors can BCH 21 of 31 detect?
Either you edited this, or I simply failed at reading when you replied...

BCH-21,31 can do any one of:
Correct 0 and detect 5 bits of error
Correct 1 and detect 4 bits of error
Correct 2 and detect 3 bits of error

(The hamming distance between any two valid words is at least 6 bits)

Alternatively, you could specifically consume one bit worth of error correction to store an additional 5 bits. (The correction algorithm specifically finds which bits have errors and toggles them, so one could intentionally add an error to store more state: toggle any of of 31 bits or don't toggle any). The "correct 2" state doesn't let you know which bit error was the one that was supposed to be data, so you can't correct additional errors in this case.
Post Reply