Forward Error Correction Using Walsh Functions
Phil Pilgrim (PhiPi)
Posts: 23,514
In another thread, I introduced Walsh functions. These are digital orthogonal basis functions. By "orthogonal" I mean that any two functions multiplied together (as a dot product) will always yield zero.
Walsh functions take two values: -1 and 1. If we replace the -1 with 0, we can define a function in terms of a binary value. For example, W(3,6) from the above link could be defined as %10010110. And its inverse can be defined as %01101001. If you XOR any two Walsh functions defined this way, you will always get a result with exactly four 1's and four 0's (except when you XOR a function with its inverse, you get zero 1's and eight 0's).
Why is this? Remember that when you multiply two Walsh functions together, you always get zero. That means that four parts of the product have to equal -1, and four, +1. That translates to four 0's and four 1's.
But what does this have to do with error correction? Suppose you have a keypad with 16 keys. Each key can be assigned to one binary Walsh number or its inverse. Suppose the "1" key is assigned the value %10010110, and that this value gets transmitted over a noisy line when the key is pressed, in which one of its bits could get changed. Say the receiver sees %11010110. There's no other Walsh number that could yield this with a single bit change. So it's easy to map back to the correct number.
In practice, this mapping can be done using a 256-byte look-up table. In this table. Each index to the table is the potential value of a received byte. Each entry in the table is the corrected value, or a distinct error code if there is no corrected value. The table is filled with the error codes to start with. Then, for each Walsh number, its position in the table is filled with that number. Next, each bit of the Walsh number is changed, and the entry for that number is filled with the correct Walsh number. So when a character is received, the real result (or the error code) can be obtained by looking it up in the table.
Now, what happens if two bits get changed during transmission? In this case, the table will map to an error code, not to another Walsh number. This is because it takes at least four changes to get from one Walsh number to another, or three to get to another Walsh's correction code. But two Walsh numbers could map to the same table location if the same two bits were changed in transmission. So it's not possible to say which Walsh number was the one being transmitted, only that an error occurred.
Here's an example of Walsh numbers created for a 12-key keypad:
CON ONE = %00001111 TWO = %11000011 THREE = %00111100 FOUR = %11001100 FIVE = %00110011 SIX = %10011001 SEVEN = %01100110 EIGHT = %10101010 NINE = %01010101 STAR = %10010110 ZERO = %01101001 HASH = %10100101 NONE = 0
Here's the correction table produced from those numbers:
DAT CORR00000 byte %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00001111 CORR00001 byte %00000000, %00000000, %00000000, %00001111, %00000000, %00001111, %00001111, %00001111 CORR00010 byte %00000000, %00000000, %00000000, %00110011, %00000000, %01010101, %10010110, %00000000 CORR00011 byte %00000000, %10011001, %00000000, %00000000, %00111100, %00000000, %00000000, %00001111 CORR00100 byte %00000000, %00000000, %00000000, %00110011, %00000000, %10100101, %01100110, %00000000 CORR00101 byte %00000000, %01101001, %10101010, %00000000, %00111100, %00000000, %00000000, %00001111 CORR00110 byte %00000000, %00110011, %00110011, %00110011, %00111100, %00000000, %00000000, %00110011 CORR00111 byte %00111100, %00000000, %00000000, %00110011, %00111100, %00111100, %00111100, %00000000 CORR01000 byte %00000000, %00000000, %00000000, %11000011, %00000000, %01010101, %01100110, %00000000 CORR01001 byte %00000000, %01101001, %00000000, %00000000, %11001100, %00000000, %00000000, %00001111 CORR01010 byte %00000000, %01010101, %00000000, %00000000, %01010101, %01010101, %00000000, %01010101 CORR01011 byte %00000000, %00000000, %00000000, %00000000, %00000000, %01010101, %00000000, %00000000 CORR01100 byte %00000000, %01101001, %01100110, %00000000, %01100110, %00000000, %01100110, %01100110 CORR01101 byte %01101001, %01101001, %00000000, %01101001, %00000000, %01101001, %01100110, %00000000 CORR01110 byte %00000000, %00000000, %00000000, %00110011, %00000000, %01010101, %01100110, %00000000 CORR01111 byte %00000000, %01101001, %00000000, %00000000, %00111100, %00000000, %00000000, %00000000 CORR10000 byte %00000000, %00000000, %00000000, %11000011, %00000000, %10100101, %10010110, %00000000 CORR10001 byte %00000000, %10011001, %10101010, %00000000, %11001100, %00000000, %00000000, %00001111 CORR10010 byte %00000000, %10011001, %10010110, %00000000, %10010110, %00000000, %10010110, %10010110 CORR10011 byte %10011001, %10011001, %00000000, %10011001, %00000000, %10011001, %10010110, %00000000 CORR10100 byte %00000000, %10100101, %10101010, %00000000, %10100101, %10100101, %00000000, %10100101 CORR10101 byte %10101010, %00000000, %10101010, %10101010, %00000000, %10100101, %10101010, %00000000 CORR10110 byte %00000000, %00000000, %00000000, %00110011, %00000000, %10100101, %10010110, %00000000 CORR10111 byte %00000000, %10011001, %10101010, %00000000, %00111100, %00000000, %00000000, %00000000 CORR11000 byte %00000000, %11000011, %11000011, %11000011, %11001100, %00000000, %00000000, %11000011 CORR11001 byte %11001100, %00000000, %00000000, %11000011, %11001100, %11001100, %11001100, %00000000 CORR11010 byte %00000000, %00000000, %00000000, %11000011, %00000000, %01010101, %10010110, %00000000 CORR11011 byte %00000000, %10011001, %00000000, %00000000, %11001100, %00000000, %00000000, %00000000 CORR11100 byte %00000000, %00000000, %00000000, %11000011, %00000000, %10100101, %01100110, %00000000 CORR11101 byte %00000000, %01101001, %10101010, %00000000, %11001100, %00000000, %00000000, %00000000 CORR11110 byte %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00000000 CORR11111 byte %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00000000, %00000000
-Phil
Comments
This is one of those threads that make me feel like I oughta be flipping burgers or something
I’ll handle the fry machine.
On a serious note, these “out of the blue” threads are great for expanding my knowledge base. Keep ‘ em coming!
Oh shoot, I ain't knocking it, I even read @Wuerfel_21 posts and have yet to comprehend a single one
Still better than BS TV that I refuse to own/watch.
Craig
I own 5 or so televisions. Too many one might say. But I can't help but contribute to a good cause.
Every day, thousands of innocent TVs are abandoned by their owners. A domesticated TV can not survive in the wild and will often fall prey to copper poachers. With your donation of even just one dollar, you can help save these cute tubers. Call 0-900-CRITICALRACETHEORY. Every dollar helps.
The programming really has declined though. Same shit on every channel. I hate that show with the black and white dots.
;P
@Wuerfel_21 Shut up and take my money
I love using my 49" 4k dumb tv as a monitor. 200% scale and keep it 2 meters away to reduce eyestrain.
And nice post @"Phil Pilgrim (PhiPi)"
I probably should have laid a better foundation for this thread, so I'll try to do it here.
Originally, my keypad driver just returned the ASCII values of the figures printed on the keys: "0", "1", "2", "3", etc. But, in binary, these are:
%00110000, %00110001, %00110010, %00110011, . . .
You can see that between "0" and "1", there is only one bit change; same, between "2" and "3". If I'm sending a "2", and bit 0 gets clobbered en route and changes to a 1, the receiver will see a "3", which is a valid value. This is not good.
The idea with forward error correction is to keep the valid codes as far apart as possible, so that you have to change the maximum number of bits to get from one to another. The distances between codes are called "Hamming distances" and are just a measure of how many bits between two codes are different. That way, when one bit changes, you don't land on another code and should be able to tell which bit it was and repair it.
The reason for going to Walsh functions is that they provide a means for assigning codes with Hamming distances of 4 or 8 between any pair of 8-bit codes in a 16-code set.
In my case, I also had to avoid sending a DLE (data link escape == %00010000), since that carries special significance to my XBee driver receiver. So I could not use the Walsh number %00000000, as a single bit change could result in a DLE being received.
I hope this helps,
-Phil
So the CRC isn't enough?
https://digi.com/support/knowledge-base/error-detection-and-correction
Craig
A CRC doesn't correct anything; it just tells you that an error occurred. I didn't want two-way communication between the remote keypad and the LED controller, which is why I chose to use FEC instead. But the link that you cite indicates that FEC was probably a waste of effort on my part, since the receiving unit would never see a byte in error to begin with. What's implied is that after a number of retries, the XBee transmitter simply gives up.
I tried to configure the XBee to make 8 retries, but it didn't stick. So my backup plan of sending the keypad code four times with gaps in between may be what saves me. The LED controller was already programmed to ignore duplicate codes so that was a simple thing to add.
-Phil
I have found that if an XBee message gets through, it tends to be good. Have you run the spectrum analyzer tool in XCTU to see if there is channel with less traffic that you could operate on?
Thanks for the tip, Jon. That would be a good thing to do, certainly. But for good data I would have to do it during an actual performance, with crew using headsets and a (hopefully) packed house full of cellphones on silence but not turned off.
Thankfully, the director declined an upgrade to bluetooth-controlled stage lighting fixtures. But I'm betting that something like that will soon obsolesce DMX. And no more halogens, just LEDs.
Anyway, the director is aware of potential issues and has trained the assistant stage manager to take over in case of an RF glitch.
The last run-through before opening night on Friday is a dress rehearsal on Thursday presented to the seventh-grade students. We'll see what happens then . . .
-Phil