It is currently Fri Oct 19, 2018 2:28 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Wed Apr 11, 2018 3:10 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7669
Location: Seattle
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 85 times
Top
 Profile  
 
PostPosted: Wed Apr 11, 2018 3:18 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20672
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Wed Apr 18, 2018 10:50 am 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7669
Location: Seattle
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: koitsu and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group