Error correction in short packet.

Send it three times and compare.

onsdag den 18. maj 2022 kl. 18.32.15 UTC+2 skrev snipped-for-privacy@highlandsniptechnology.com:

but then you need three times the bandwidth which may not be an option

It may not be, but bandwidth is much cheaper than it used to be. I have some international VPN links subject to fairly severe packet loss. Every packet is sent four times by different routes and the first one to arrive intact gets passed on and the others are discarded (if they ever arrive). This all works very nicely at tens of Mbit/s. The improvement in performance is much more than a factor of four when packet loss is severe and the waste is only a factor of four when there is no packet loss.

Well Reed-Solomon would do what you want. Problem is the crc can not fix the errors.

Cheers

One could send three copies of the packet and majority-vote each bit.

Am 18.05.22 um 20:20 schrieb John Walliker:

That works as long as there is a lot of channel capacity and as long as at least some packets get though without error.

When barely a packet gets through without error, then it's time for forward error correction. That is, sending it once with enough redundancy.

cheers, Gerhard

Do you know the *nature* of the interference that is (potentially) corrupting your transmission? Is it periodic? Burst-y? Or, does each bit-time have an equal AND INDEPENDANT probability of encountering an error?

E.g., does one error event have any effect on the next bit datum?

(Wombats!)

As you are receiving the bit STREAM serially, compute the checksum/syndrome similarly. Presumably you have enough storage (14 bytes) to hold an entire completed message; a "correction cycle" (some number of clocks) can then toggle the appropriate bits in the accumulator.

I worked on a project where the previous developer naively tried to improve data integrity by storing three copies of a 16-byte quantity -- and hoping to "compare them" to determine what the CORRECT value should be.

Of course, this only works as good as simple bit-wise parity (in general) as two errors can conspire to convince you that THEY reflect the correct value: xxxxxxx1xxxxxxxx yyyyyyy1yyyyyyyy zzzzzzz0zzzzzzzz in which each of the x, y and z represent correct values, in agreement with the redundant copies. The third value being correct, the previous two reflecting single bit errors in each.

Conclusion: -------1-------- I.e., you can't correct *any* errors (of a certain type). You've wasted lots of "check digits" (in this case, 256 bits of check digits on a 128 bit value!) with little to show for it!

I'm wondering if you could just compute two *different* syndromes (i.e., two different polynomials) over the same data and treat it as two single-bit correcting codes. In which case, about 2 bytes of check digit overhead. (112 bits is ~7b, +1 for parity yields 8 -- for each possible check digit)

But, I've not yet had my breakfast...

You don't have space to even reliably detect single bit errors without making assumptions about the error rate (or hoping that it is only ever a single bit error and enumerating every possibility).

Sending 256 bits of data with 16 of them for error checking in a perfect world would allow you to decode the location of that single bit error.

When I have needed to do that (and a very long time ago) we used a Hamming code 7,4 to deal with a somewhat unreliable punchtape machine and a single chance to grab the raw data. Correct any single bit error, detect any two bit error. Overhead for the simplest useful one is 100%.

The error rate turned out to be low enough that it never actually saw a

2 bit error in what was about 32kb of data (64k chars on tape). But we only discovered that later when it was decoded on the mainframe.

Hadamard convolutional codes might be a better choice now but the overheads are going to be significant in time and code space.

Space probes use Golay codes these days but you may not have enough horsepower for that either. The lookup tables for Hamming might be OK...

you didn't read the 2 byte limit he said he had? The answer is it can't be done with the constraints he has specified.

Even if you had a 16 bit value that told you which two bits were wrong, you'd then have to make use of that information to flip the incorrect bits. That doesn't sound like small number of LUTs.

Is your channel really that noisy that you cannot just discard bad packets?

Sylvia.

Or, send one copy with checksum, then a second copy with checksum, then a third copy. Take the first one that has a correct checksum, or... just stick with copy 3, you're out of time.

Majority-vote takes (on average) longer because it always waits for three copies. Checksum, one hopes, is more reassuring per extra bit than voting.

I don't have control over the transmission path, it may be noisy, it may not - it's not a fixed installation. I want to get the best shot at correcting errors within my fixed constraints, even a single bit EDC would be useful. I can't request a resend, and sending multiple copies restricts bandwidth too much.

Of course, there comes a point when it just won't/can't work.

I do know that a CRC approach is easy to implement from the POV of error detection. I also know that this could detect and correct at least a single bit error, but I don't know if there's a quick and easy way of finding the bad bit.

And to be honest, much of the maths associated with EDC is beyond me at the moment.

<snip>

I can't resend packets.

I've looked at 8,4 Hamming codes, easy to implement (and understand!) to correct a single bit error in a data nibble and detect two bit errors. It may be the way to go, but it's quite an overhead. Still, with the ability to switch it in only when needed it might be an answer if nothing better shows up.

Yes 255,223 Reed-Solomon is used elsewhere, but too 'expensive' here.

What do you do then if you receive a packet with a detected 2 bit error?

I think it is probably your best bet. Hadamard might be another one to look at but harder to understand and implement efficiently.

It will really hinge on how noisy the data channel is. Can you not subvert a V90 modem chip at each end and send the data that way?

I vaguely recall a trick using parity over an orthogonal basis set of Walsh functions (much like Hadamard) that could be designed so that the computed signature of the data received gave you the index of the bad bit. Described in more detail here.

It seems Hamming(127,120) is what you want. Now just a SMOP! Or 2x Hamming(63,57) applied to 64 bits (one bit left hanging).

It would be wasteful to encode each byte individually -- though it gives greater detection/correction "at the byte level" -- due to the excess overhead it introduces.

Instead, treat the entire 14-byte message as a 112 bit datum. Add 7 parity bits and you can correct a single bit error in the resulting 119 bit "augmented message". Use the remaining (8th) bit -- assuming the underlying protocol is byte-based and not bit-oriented -- and you can detect two errors.

Hamming can be decoded with a polynomial-per-parity-bit (i.e., 8 in this case) all "watching" the same deserializer. The syndrome then "points" to the bit that is in error (if only one) and, as bits are only bivalued, you just have to toggle that bit to fix it.

Detecting a *second* error is where it gets a bit trickier...

Hmm, 17 messages in to the thread, and the group finally is told some of the critical unstated requirements that *should* have been part of the initial message, and would have avoided about 14 "can't you resend" or "can't you send multiple" messages.

Don't you think this above should have been in your initial post so that the rest of us, who can't read your mind to divine unstated limitations, were appraised of some rather critical limitations?

<snip>

CRCs can be used to correct one error provided there's not too much data. The brute force method involves changing one bit at a time until the CRC is correct; I don't know if there's a quicker way or if more errors could be corrected using a suitable CRC.

It's normal here to get underspecified problems. Details usually emerge, but some people do refuse to explain their top-secret projects.