Error correction in short packet....

[server]

On Fri, 20 May 2022 10:58:45 -0700 (PDT), whit3rd <whit3rd@gmail.com>
wrote:

On Friday, May 20, 2022 at 7:28:54 AM UTC-7, jla...@highlandsniptechnology.com wrote:
On Thu, 19 May 2022 20:38:24 -0700 (PDT), whit3rd <whi...@gmail.com
wrote:

On Thursday, May 19, 2022 at 1:59:08 PM UTC-7, John Larkin wrote:

Oh, lots of people are reflexively hostile to new or unconventional
ideas. Those personalities poison brainstorming sessions.

For those of us who haven\'t experienced poisoned brainstorming sessions,
describe the \'hostility\'.

Some people, especially ones with grey hair, immediately find fault
with ideas instead of riffing on them. That intimidates some
contributors, especially young ones. Sometimes they have sufficient
gravity that they kill a promising discussion.

Swift fault analysis isn\'t hostility, it is effective argument.

It is hostility and it kills ideas in their infancy. \"Argument\" says
it all. Right and wrong is a zero-sum game, or usually less than zero.





--

Anybody can count to one.

- Robert Widlar

 

[whit3rd]

On Friday, May 20, 2022 at 6:14:08 PM UTC-7, jla...@highlandsniptechnology.com wrote:

On Fri, 20 May 2022 10:58:45 -0700 (PDT), whit3rd <whi...@gmail.com
wrote:

On Friday, May 20, 2022 at 7:28:54 AM UTC-7, jla...@highlandsniptechnology.com wrote:

Some people, especially ones with grey hair, immediately find fault
with ideas instead of riffing on them. That intimidates some
contributors, especially young ones. Sometimes they have sufficient
gravity that they kill a promising discussion.

Swift fault analysis isn\'t hostility, it is effective argument.

It is hostility and it kills ideas in their infancy. \"Argument\" says
it all. Right and wrong is a zero-sum game, or usually less than zero.

No, the term for a negative-sum argument is \'sophistry\'.
Sophistries are not valid arguments.
Valid arguments are VALUABLE contributions.

Some folk are timid, will prefer small incremental changes (that\'s
a good strategy against uncerainty).

Some folk are conservative, will reject novel, untried approaches (that\'s
useful if you have a time or material budget).

Some folk are insightful, will foresee an awkward or impossible step
in advance.

So, an immediate finding of fault can have lots of causes, none of which
are \'hostile to ideas\' in nature. And, occasionally (Boeing\'s 737Max comes to mind)
a NO is the right design answer; why delay putting it on the table?

 

[Flyguy]

On Friday, May 20, 2022 at 8:17:35 PM UTC-7, whit3rd wrote:

On Friday, May 20, 2022 at 6:14:08 PM UTC-7, jla...@highlandsniptechnology.com wrote:
On Fri, 20 May 2022 10:58:45 -0700 (PDT), whit3rd <whi...@gmail.com
wrote:

On Friday, May 20, 2022 at 7:28:54 AM UTC-7, jla...@highlandsniptechnology.com wrote:

Some people, especially ones with grey hair, immediately find fault
with ideas instead of riffing on them. That intimidates some
contributors, especially young ones. Sometimes they have sufficient
gravity that they kill a promising discussion.

Swift fault analysis isn\'t hostility, it is effective argument.

It is hostility and it kills ideas in their infancy. \"Argument\" says
it all. Right and wrong is a zero-sum game, or usually less than zero.
No, the term for a negative-sum argument is \'sophistry\'.
Sophistries are not valid arguments.
Valid arguments are VALUABLE contributions.

Some folk are timid, will prefer small incremental changes (that\'s
a good strategy against uncerainty).

Some folk are conservative, will reject novel, untried approaches (that\'s
useful if you have a time or material budget).

Some folk are insightful, will foresee an awkward or impossible step
in advance.

So, an immediate finding of fault can have lots of causes, none of which
are \'hostile to ideas\' in nature. And, occasionally (Boeing\'s 737Max comes to mind)
a NO is the right design answer; why delay putting it on the table?

I vote for Golay codes. Here is a short writeup:
https://en.wikipedia.org/wiki/Binary_Golay_code

 

[Flyguy]

On Friday, May 20, 2022 at 9:01:12 PM UTC-7, Flyguy wrote:

On Friday, May 20, 2022 at 8:17:35 PM UTC-7, whit3rd wrote:
On Friday, May 20, 2022 at 6:14:08 PM UTC-7, jla...@highlandsniptechnology.com wrote:
On Fri, 20 May 2022 10:58:45 -0700 (PDT), whit3rd <whi...@gmail.com
wrote:

On Friday, May 20, 2022 at 7:28:54 AM UTC-7, jla...@highlandsniptechnology.com wrote:

Some people, especially ones with grey hair, immediately find fault
with ideas instead of riffing on them. That intimidates some
contributors, especially young ones. Sometimes they have sufficient
gravity that they kill a promising discussion.

Swift fault analysis isn\'t hostility, it is effective argument.

It is hostility and it kills ideas in their infancy. \"Argument\" says
it all. Right and wrong is a zero-sum game, or usually less than zero.
No, the term for a negative-sum argument is \'sophistry\'.
Sophistries are not valid arguments.
Valid arguments are VALUABLE contributions.

Some folk are timid, will prefer small incremental changes (that\'s
a good strategy against uncerainty).

Some folk are conservative, will reject novel, untried approaches (that\'s
useful if you have a time or material budget).

Some folk are insightful, will foresee an awkward or impossible step
in advance.

So, an immediate finding of fault can have lots of causes, none of which
are \'hostile to ideas\' in nature. And, occasionally (Boeing\'s 737Max comes to mind)
a NO is the right design answer; why delay putting it on the table?
I vote for Golay codes. Here is a short writeup:
https://en.wikipedia.org/wiki/Binary_Golay_code

And here is the actual code to implement it:
https://github.com/pkdoshinji/Golay/blob/master/Golay.py

 

[server]

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

 

[Lasse Langwadt Christensen]

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

 

[John Walliker]

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.

 

[Martin Rid]

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

 

[John Larkin]

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

 

[Gerhard Hoffmann]

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

 

[Don Y]

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

 

[Martin Brown]

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

 

[David Eather]

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.

 

[John Larkin]

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

 

[Sylvia Else]

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.

 

[whit3rd]

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.

 

[Martin Brown]

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

 

[Clive Arthur]

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

 

[Clive Arthur]

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

 

[Martin Brown]

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