Error correction in short packet....

[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

 

[Don Y]

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

 

[Keegan Major]

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?

 

[Clive Arthur]

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

 

[server]

On Thu, 19 May 2022 12:58:33 -0000 (UTC), Keegan Major
<keegan.major@hotmail.com> wrote:

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?

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



--

Anybody can count to one.

- Robert Widlar

 

[Lasse Langwadt Christensen]

torsdag den 19. maj 2022 kl. 16.36.23 UTC+2 skrev jla...@highlandsniptechnology.com:

On Thu, 19 May 2022 12:58:33 -0000 (UTC), Keegan Major
keegan...@hotmail.com> wrote:

Clive Arthur <cl...@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?


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

https://xyproblem.info/

 

[server]

On Thu, 19 May 2022 07:40:45 -0700 (PDT), Lasse Langwadt Christensen
<langwadt@fonz.dk> wrote:

torsdag den 19. maj 2022 kl. 16.36.23 UTC+2 skrev jla...@highlandsniptechnology.com:
On Thu, 19 May 2022 12:58:33 -0000 (UTC), Keegan Major
keegan...@hotmail.com> wrote:

Clive Arthur <cl...@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?


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

https://xyproblem.info/

Underspecified problems do encourage lots of lateral/goofy thinking.

Of course, some people are hostile to ideas. Their career path is more
McDonalds than electronic design.



--

Anybody can count to one.

- Robert Widlar

 

[John S]

On 5/20/2022 1:48 AM, David Eather wrote:

On 19/05/2022 8:46 am, 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.





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.


I\'m being helpful - if he had such a limit on packet size he probably
has a limit on how much he can send. What he wants is not possible with
the limits he has described. It is helpful to let him know he has to
reassess his limits rather than just assume he can do what you want -
and there are more efficient ways than just send it three times.

you were just being noise.

And you left your filter at home, eh?

 

[David Eather]

On 27/05/2022 11:20 am, John S wrote:

On 5/20/2022 1:48 AM, David Eather wrote:
On 19/05/2022 8:46 am, 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.





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.


I\'m being helpful - if he had such a limit on packet size he probably
has a limit on how much he can send. What he wants is not possible
with the limits he has described. It is helpful to let him know he has
to reassess his limits rather than just assume he can do what you want
- and there are more efficient ways than just send it three times.

you were just being noise.

And you left your filter at home, eh?

the same as JL did

 

[boB]

On Mon, 23 May 2022 06:49:39 -0700, jlarkin@highlandsniptechnology.com
wrote:

On Sun, 22 May 2022 22:54:04 -0700, boB <boB@K7IQ.com> wrote:

On Sun, 22 May 2022 20:49:08 -0700, jlarkin@highlandsniptechnology.com
wrote:

On Sun, 22 May 2022 19:28:39 -0700, Don Y
blockedofcourse@foo.invalid> wrote:

On 5/19/2022 12:24 PM, whit3rd wrote:
On Thursday, May 19, 2022 at 8:03:55 AM UTC-7, jla...@highlandsniptechnology.com wrote:
On Thu, 19 May 2022 07:40:45 -0700 (PDT), Lasse Langwadt Christensen
lang...@fonz.dk> wrote:

torsdag den 19. maj 2022 kl. 16.36.23 UTC+2 skrev jla...@highlandsniptechnology.com:
On Thu, 19 May 2022 12:58:33 -0000 (UTC), Keegan Major

Of course, some people are hostile to ideas. Their career path is more
McDonalds than electronic design.

Again with the goofy personality theories! Everyone is hostile to ideas
for a few minutes in the evening, when it\'s time to sleep.

That\'s normal, and has nothing to do with a career path.

That\'s *cranky*. I have little patience for distractions (of any kind)
when I\'m over tired (and focused on getting things in order so I can
*rest*) or \"overloaded\" -- and need to get things off my plate so I can
concentrate on something \"new\".

No sane conscious mind is \'hostile to ideas\' in any more general sense; that
would be pathological, like being hostile to one\'s own body parts.

People aren\'t hostile to ideas (JL sees *everything* as some aspect of
hostility; an entirely passive-aggressive outlook on life).

Not at all. I\'m cheerful and helpful. But there are a lot of nasty
people here who don\'t design electronics.

You sure got that right !

boB




Playing with circuits is fun. Endless ritual squabbling is boring and
bad for you. So why do they do it here?

Not sure ?

This may be a place where they can \"identify\" somehow. Kind of like
flat earthers and those who follow an alternative existence.

They feel that they \"belong\" somehow.

If I were a psychologist, I might be able to find a name for SED.

boB

 

[server]

On Mon, 23 May 2022 21:00:41 -0700, boB <boB@K7IQ.com> wrote:

On Mon, 23 May 2022 06:49:39 -0700, jlarkin@highlandsniptechnology.com
wrote:

On Sun, 22 May 2022 22:54:04 -0700, boB <boB@K7IQ.com> wrote:

On Sun, 22 May 2022 20:49:08 -0700, jlarkin@highlandsniptechnology.com
wrote:

On Sun, 22 May 2022 19:28:39 -0700, Don Y
blockedofcourse@foo.invalid> wrote:

On 5/19/2022 12:24 PM, whit3rd wrote:
On Thursday, May 19, 2022 at 8:03:55 AM UTC-7, jla...@highlandsniptechnology.com wrote:
On Thu, 19 May 2022 07:40:45 -0700 (PDT), Lasse Langwadt Christensen
lang...@fonz.dk> wrote:

torsdag den 19. maj 2022 kl. 16.36.23 UTC+2 skrev jla...@highlandsniptechnology.com:
On Thu, 19 May 2022 12:58:33 -0000 (UTC), Keegan Major

Of course, some people are hostile to ideas. Their career path is more
McDonalds than electronic design.

Again with the goofy personality theories! Everyone is hostile to ideas
for a few minutes in the evening, when it\'s time to sleep.

That\'s normal, and has nothing to do with a career path.

That\'s *cranky*. I have little patience for distractions (of any kind)
when I\'m over tired (and focused on getting things in order so I can
*rest*) or \"overloaded\" -- and need to get things off my plate so I can
concentrate on something \"new\".

No sane conscious mind is \'hostile to ideas\' in any more general sense; that
would be pathological, like being hostile to one\'s own body parts.

People aren\'t hostile to ideas (JL sees *everything* as some aspect of
hostility; an entirely passive-aggressive outlook on life).

Not at all. I\'m cheerful and helpful. But there are a lot of nasty
people here who don\'t design electronics.

You sure got that right !

boB




Playing with circuits is fun. Endless ritual squabbling is boring and
bad for you. So why do they do it here?

Not sure ?

This may be a place where they can \"identify\" somehow. Kind of like
flat earthers and those who follow an alternative existence.

They feel that they \"belong\" somehow.

The subject here is electronics. The old hens don\'t belong.

If I were a psychologist, I might be able to find a name for SED.

boB

If people want to discuss their feelings, they should go to Facebook
or Grindr.



--

Anybody can count to one.

- Robert Widlar

 

[Martin Brown]

On 20/05/2022 18:46, whit3rd wrote:

On Thursday, May 19, 2022 at 3:31:23 PM UTC-7, John Larkin wrote:

Yes, I work more by instinct and simulation. But my world is largely
nonlinear, where the math is basically impossible.

Identifying a problem as nonlinear IS math; it\'s obviously useful info,
and the only deficiency is in the non-utility of common approximations.
The math is not impossible, just... more difficult.

Quadratics are non-linear and taught as high school algebra. Cubics and
their closed form solutions are seldom taught even at degree level.

A few other non-linear closed form solutions are known up to quartics.
After that it is what Pade approximations are designed for.

They cause pure mathematicians to cross themselves and run out of the
room. That aside on a good day you can get a workable and insightful
approximations for real problems that are good enough for engineering.

Their first serious use was in taming highly divergent and hard won
series expansions for high Mach number turbulent flow in aerospace.

The crucial point is that they are neither provably right nor exact but
over some moderate range of your choosing can be made good enough for
all practical purposes (or used as a guess for NR/Halley refinement).

--
Regards,
Martin Brown