Forward Error Correction Using Walsh Functions — Parallax Forums

# Forward Error Correction Using Walsh Functions

Posts: 23,493
edited 2022-10-28 05:25

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

• Posts: 2,309

This is one of those threads that make me feel like I oughta be flipping burgers or something

• Posts: 1,148

@Mickster said:
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!

• Posts: 2,309

@JRoark said:

@Mickster said:
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

• Posts: 3,310
edited 2022-10-27 23:05

@Mickster said:
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.

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 s‌hit on every channel. I hate that show with the black and white dots.

;P

• Posts: 411

@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)"

• Posts: 23,493
edited 2022-10-28 18:42

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

• Posts: 23,493

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

• Posts: 8,314

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?

• Posts: 23,493

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