Error correction in short packet.

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.

-- 
Cheers
Clive

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.



-- 

Anybody can count to one.

- Robert Widlar

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

Clive Arthur <clive@nowaytoday.co.uk> Wrote in message:r
> Hi allI 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.-- CheersClive

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

Cheers
-- 


----Android NewsGroup Reader----
https://piaohong.s3-us-west-2.amazonaws.com/usenet/index.html

On Wed, 18 May 2022 11:20:33 -0700 (PDT), John Walliker
<jrwalliker@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 
>> > <cl...@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.
>> 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. 

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

-- 

If a man will begin with certainties, he shall end with doubts, 
but if he will be content to begin with doubts he shall end in certainties.
Francis Bacon

Am 18.05.22 um 20:20 schrieb John Walliker:

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

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

On 5/18/2022 8:54 AM, Clive Arthur wrote:
> 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.

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

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

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.

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

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

On 18/05/2022 17:40, Lasse Langwadt Christensen 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
>> <cl...@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.

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.

>>> 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.
> but then you need three times the bandwidth which may not be an option

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

https://en.wikipedia.org/wiki/Hamming_code#[7,4]_Hamming_code

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

-- 
Regards,
Martin Brown

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


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.

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

I'm trying to be helpful, you are trying to be obnoxious. Do whatever
you are best at.

-- 

If a man will begin with certainties, he shall end with doubts, 
but if he will be content to begin with doubts he shall end in certainties.
Francis Bacon