Error correction in short packet.

On 19-May-22 1:54 am, Clive Arthur wrote:
> Hi all
> 
> I have serial data in 14 byte packets on which I'd like to detect and 
> correct errors.  Two bit errors would be nice.  I can put 2 extra EDC 
> bytes on the end to make a 16 byte packet.
> 
> I don't have the resources for Reed-Solomon.  I could use a 16 bit CRC, 
> these are easy to generate with a small/moderate LUT.
> 
> In the past, I've used a CRC16 for single bit error detection and 
> correction on a longer packet, but I didn't do the error detection part. 
>   Errors were very rare, time was not critical, and I understand that 
> this was simply done by changing each message bit in turn then 
> recalculating the CRC till it all worked out.  That's far to slow for my 
> current needs.
> 
> If I'm lucky, a 16 bit CRC might be able to detect and correct 2 bit 
> errors in 14 bytes (112 * 111 possibilities?), but is there a way of 
> quickly finding out which bits are wrong?
> 
> Or maybe a completely different approach? This has to be done on the 
> fly, and multi-kilobyte LUTs or thousands of clock cycles are out of the 
> question.
> 

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.

On Wednesday, May 18, 2022 at 12:07:43 PM UTC-7, John Larkin wrote:
> On Wed, 18 May 2022 11:20:33 -0700 (PDT), John Walliker 
> <jrwal...@gmail.com> wrote: 
> 
> >On Wednesday, 18 May 2022 at 17:40:22 UTC+1, lang...@fonz.dk wrote: 
> >> onsdag den 18. maj 2022 kl. 18.32.15 UTC+2 skrev jla...@highlandsniptechnology.com: 
> >> > On Wed, 18 May 2022 16:54:32 +0100, Clive Arthur 

> >> > >I have serial data in 14 byte packets on which I'd like to detect and 
> >> > >correct errors. Two bit errors would be nice. 

> >> > Send it three times and compare. 

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

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.

On 18/05/2022 23:46, John Larkin wrote:
> On Thu, 19 May 2022 08:06:25 +1000, David Eather
> <eatREMOVEher@tpg.com.au> wrote:
> 
>> On 19/05/2022 2:32 am, jlarkin@highlandsniptechnology.com wrote:
>>> On Wed, 18 May 2022 16:54:32 +0100, Clive Arthur
>>> <clive@nowaytoday.co.uk> wrote:
>>>
>>>> Hi all
>>>>
>>>> I have serial data in 14 byte packets on which I'd like to detect and
>>>> correct errors.  Two bit errors would be nice.  I can put 2 extra EDC
>>>> bytes on the end to make a 16 byte packet.
>>>>
>>>> I don't have the resources for Reed-Solomon.  I could use a 16 bit CRC,
>>>> these are easy to generate with a small/moderate LUT.
>>>>
>>>> In the past, I've used a CRC16 for single bit error detection and
>>>> correction on a longer packet, but I didn't do the error detection part.
>>>>    Errors were very rare, time was not critical, and I understand that
>>>> this was simply done by changing each message bit in turn then
>>>> recalculating the CRC till it all worked out.  That's far to slow for my
>>>> current needs.
>>>>
>>>> If I'm lucky, a 16 bit CRC might be able to detect and correct 2 bit
>>>> errors in 14 bytes (112 * 111 possibilities?), but is there a way of
>>>> quickly finding out which bits are wrong?
>>>>
>>>> Or maybe a completely different approach? This has to be done on the
>>>> fly, and multi-kilobyte LUTs or thousands of clock cycles are out of the
>>>> question.
>>>
>>>
>>> Send it three times and compare.

What do you do when all three are different?
>>
>> 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.
> 
> He specified a packet length limit, but didn't say he couldn't send it
> multiple times.

The best bet under his specified constraints is send it with a crc in 
the extra 2 bytes and keep on sending it until you get an ack back from 
the other end that one has decoded OK. Or if you insist on a simple 
voting algorithm until you get two the same. It all depends on the bit 
error rate. If it is low enough then detecting a fail by quick crc and 
sending a "say again" msg back to the sender would be least invasive.

If the channel is noisy in both directions then it requires a bit more 
thought since the conversation could go on forever at very bad SNR.

It should be possible to correct any single bit error and detect any 
double bit error in the data stream with just 75% overhead even with a 
simple Hamming code - just under double the size of the raw data.

Better EC encodings exist but they require more horsepower.

-- 
Regards,
Martin Brown

On 19/05/2022 04:27, Sylvia Else wrote:
> On 19-May-22 1:54 am, Clive Arthur wrote:
>> Hi all
>>
>> I have serial data in 14 byte packets on which I'd like to detect and 
>> correct errors.  Two bit errors would be nice.  I can put 2 extra EDC 
>> bytes on the end to make a 16 byte packet.
>>
>> I don't have the resources for Reed-Solomon.  I could use a 16 bit 
>> CRC, these are easy to generate with a small/moderate LUT.
>>
>> In the past, I've used a CRC16 for single bit error detection and 
>> correction on a longer packet, but I didn't do the error detection 
>> part.   Errors were very rare, time was not critical, and I understand 
>> that this was simply done by changing each message bit in turn then 
>> recalculating the CRC till it all worked out.  That's far to slow for 
>> my current needs.
>>
>> If I'm lucky, a 16 bit CRC might be able to detect and correct 2 bit 
>> errors in 14 bytes (112 * 111 possibilities?), but is there a way of 
>> quickly finding out which bits are wrong?
>>
>> Or maybe a completely different approach? This has to be done on the 
>> fly, and multi-kilobyte LUTs or thousands of clock cycles are out of 
>> the question.
>>
> 
> 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.

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.

-- 
Cheers
Clive

On 19/05/2022 09:52, Martin Brown wrote:

<snip>

> The best bet under his specified constraints is send it with a crc in 
> the extra 2 bytes and keep on sending it until you get an ack back from 
> the other end that one has decoded OK. Or if you insist on a simple 
> voting algorithm until you get two the same. It all depends on the bit 
> error rate. If it is low enough then detecting a fail by quick crc and 
> sending a "say again" msg back to the sender would be least invasive.
> 
> If the channel is noisy in both directions then it requires a bit more 
> thought since the conversation could go on forever at very bad SNR.
> 
> It should be possible to correct any single bit error and detect any 
> double bit error in the data stream with just 75% overhead even with a 
> simple Hamming code - just under double the size of the raw data.

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.
> 
> Better EC encodings exist but they require more horsepower.
> 
Yes 255,223 Reed-Solomon is used elsewhere, but too 'expensive' here.

-- 
Cheers
Clive

On 19/05/2022 10:13, Clive Arthur wrote:
> On 19/05/2022 09:52, Martin Brown wrote:
> 
> <snip>
> 
>> The best bet under his specified constraints is send it with a crc in 
>> the extra 2 bytes and keep on sending it until you get an ack back 
>> from the other end that one has decoded OK. Or if you insist on a 
>> simple voting algorithm until you get two the same. It all depends on 
>> the bit error rate. If it is low enough then detecting a fail by quick 
>> crc and sending a "say again" msg back to the sender would be least 
>> invasive.
>>
>> If the channel is noisy in both directions then it requires a bit more 
>> thought since the conversation could go on forever at very bad SNR.
>>
>> It should be possible to correct any single bit error and detect any 
>> double bit error in the data stream with just 75% overhead even with a 
>> simple Hamming code - just under double the size of the raw data.
> 
> I can't resend packets.

What do you do then if you receive a packet with a detected 2 bit error?
> 
> 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.&nbsp; Still, with the 
> ability to switch it in only when needed it might be an answer if 
> nothing better shows up.

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?

-- 
Regards,
Martin Brown

On 19/05/2022 09:58, Clive Arthur wrote:
> On 19/05/2022 04:27, Sylvia Else wrote:
>> On 19-May-22 1:54 am, Clive Arthur wrote:
>>> Hi all
>>>
>>> I have serial data in 14 byte packets on which I'd like to detect and 
>>> correct errors.  Two bit errors would be nice.  I can put 2 extra EDC 
>>> bytes on the end to make a 16 byte packet.
>>>
>>> I don't have the resources for Reed-Solomon.  I could use a 16 bit 
>>> CRC, these are easy to generate with a small/moderate LUT.
>>>
>>> In the past, I've used a CRC16 for single bit error detection and 
>>> correction on a longer packet, but I didn't do the error detection 
>>> part.   Errors were very rare, time was not critical, and I 
>>> understand that this was simply done by changing each message bit in 
>>> turn then recalculating the CRC till it all worked out.  That's far 
>>> to slow for my current needs.
>>>
>>> If I'm lucky, a 16 bit CRC might be able to detect and correct 2 bit 
>>> errors in 14 bytes (112 * 111 possibilities?), but is there a way of 
>>> quickly finding out which bits are wrong?
>>>
>>> Or maybe a completely different approach? This has to be done on the 
>>> fly, and multi-kilobyte LUTs or thousands of clock cycles are out of 
>>> the question.
>>>
>>
>> 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.
> 
> 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.

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.

https://en.wikipedia.org/wiki/Hamming_code#General_algorithm

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).

-- 
Regards,
Martin Brown

On 5/19/2022 1:52 AM, Martin Brown wrote:

> It should be possible to correct any single bit error and detect any double bit 
> error in the data stream with just 75% overhead even with a simple Hamming code 
> - just under double the size of the raw data.

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.

> Better EC encodings exist but they require more horsepower.

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...

Clive Arthur <clive@nowaytoday.co.uk> wrote:
> On 19/05/2022 04:27, Sylvia Else wrote:
>> 
>> Is your channel really that noisy that you cannot just discard bad 
>> packets?
> 
> I don't have control over the transmission path, it may be noisy, it 
> may not - it's not a fixed installation. [snip...] I can't request a 
> resend, and sending multiple copies restricts bandwidth too much.

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?

 

On 18/05/2022 19:29, Martin Rid wrote:

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

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.

-- 
Cheers
Clive