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.
Error correction in short packet.
Started by ●May 18, 2022
Reply by ●May 20, 20222022-05-20
Reply by ●May 20, 20222022-05-20
On 19/05/2022 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. >this one shouldn't be thousands of compute cycles and only a small look up table or maybe even none. This one is out of the box: take the 14 bytes and append to bytes of a known pattern 0x00 or 0xFF will work as well as anything else. Use a 128-bit (16 bytes) encryption algorithm and send that. On the receiving end, decrypt. If the last two bytes are the same as the two you added then all good. if not then you have to brute force the data. All possible single bit errors, all 2 bit errors etc until you get the answer or run out of time. The good news is that this will pick up multiple bit errors 99.8% of all possible 1 bit errors - 128 in total 87.6% of all possible 2 bit errors - 8128 in total each and every bit error has a ((2^16)-1)/2^16 chance to be detected. that is a 99.999% chance. Since you are not using the encryption algorithm as a cryptographic device but just a randomizing device you can probably chop it length down in half to double its speed.
Reply by ●May 20, 20222022-05-20
On 20/5/22 07:10, Phil Hobbs wrote:> Martin Brown wrote: >> On 19/05/2022 16:14, Jeroen Belleman wrote: >>> On 2022-05-19 17:03, jlarkin@highlandsniptechnology.com wrote: >>>> 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. >> >> Almost all of which is completely wasted. Your proposal of send it >> three times and vote best out of three being amongst them. >> >> There is just about enough space to do what the OP wants but whether >> or not they have the mathematical sophistication and programming >> skills to implement it quickly enough to be useful is still an open >> question. >> >>>> Of course, some people are hostile to ideas. Their career path is more >>>> McDonalds than electronic design. >> >> You have that *EXACTLY* backwards. >> >> If you cannot adequately describe the exact problem that you are >> trying to solve then you will spend vast amounts of effort solving the >> wrong problem(s) again and again. I have seen it happen many times. >> >>> Goofy ideas aren't really welcome if they upset a sizable fraction >>> of effort already invested. Ideas are cheap. Realizing them is costly. >>> You'll want to be selective. >> >> +1 >> >> Half the battle is specifying the problem and any hard constraints so >> that proposed solutions will actually stand a chance of working on the >> available hardware and quickly enough to be useful. >> > > I'm way more in JL's camp, although not 100%. (I do more math than he > does.) > > Of course you don't want to take the first thing that comes into your > head and build that--nobody's advocating that here AFAICT. I've seen it > a lot in the wild, though. In fact, one outfit I had to deal with (a CE > in Orange County CA) kept ignoring advice that was backed up with > detailed mathematical analysis and a _working_prototype_ of what they > were supposed to build. (That transcutaneous blood glucose thing again.) > > They just trying things randomly until they ran through the client's > money and then quit. One time when I pinged them about it, a bright lad > smiled and said, "That's engineering!" > > Riiighhhtt. > > But a lot, a lot of people seem to have very little emotional tolerance > for being in a state of uncertainty. I can't prove that, but over and > over I've seen folks spend far too little time turning the problem over > in their minds, talking at the white board, and so on, and just charging > in and doing the first thing that seemed plausible. > > That's super dumb. At the beginning of the process, you have to > cultivate offbeat ideas, because (at least in the sort of gizmos I > build) there's usually some way to do the task much better and/or > cheaper than what's out there. > > In general you should spend something like 10% of the time figuring out > what you should build, and the rest designing and building it. Skimping > on the one very often leads to poor results on the other. > > Cheers > > Phil Hobbs >archived -- Marty
Reply by ●May 20, 20222022-05-20
On 2022-05-20, Jasen Betts <usenet@revmaps.no-ip.org> wrote:> On 2022-05-18, 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?Actually no there's 128 bits so there's 128 single bit errors and 127*128/2 two bit errors, and one zero-bit error possibility that all need to be dealt with. total 8257 cases> a look-up table. how much resources do you have?You say in another message less than several kilobytes. create a CRC to single-bit error table (use a hash table, because it's O(1) for lookups) Now you can explit the fact that CRC is a linear code, so the CRC for bits m and n wrong is the XOR of the crcs for bit m wrong and the crc of bit n wrong, (the CRC for all bits correct is of course zero after feeding the data and CRC into the CRC algorithm.) If you get a non-zero CRC on a packet look it up in the table If you don't find a match speculativly xor it with the first CRC in the table then look up the result, if it's not found, try xoring the next instead. CRC might not be the best hash to use for this task, you want something that gives distinct codes for all 1 and 2 bit errors, I haven't checked if CRC-16 has that property. there's 341376 three bit errors, so it's probably not going to be possible to even detect them using CRC-16. Using a 15 bit CRC code (or other linear hash code) in combination with a parity bit should make 3 bit errors detectable however. This should be do-able in 4000 or so instuction steps - not vastly worse than the CRC computation itself - especially if you can get perfect hashing in your LUT. -- Jasen.
Reply by ●May 20, 20222022-05-20
On 20/05/2022 12:10, Jasen Betts wrote: <snip>> > Actually no there's 128 bits so there's 128 single bit errors and > 127*128/2 two bit errors, and one zero-bit error possibility that all > need to be dealt with. > > total 8257 cases > >> a look-up table. how much resources do you have? > > You say in another message less than several kilobytes. > > create a CRC to single-bit error table (use a hash table, because it's > O(1) for lookups) > > Now you can explit the fact that CRC is a linear code, so the CRC for > bits m and n wrong is the XOR of the crcs for bit m wrong and the crc > of bit n wrong, (the CRC for all bits correct is of course zero after > feeding the data and CRC into the CRC algorithm.) > > If you get a non-zero CRC on a packet look it up in the table > > If you don't find a match speculativly xor it with the first CRC in > the table then look up the result, if it's not found, try xoring the > next instead. > > CRC might not be the best hash to use for this task, you want > something that gives distinct codes for all 1 and 2 bit errors, I > haven't checked if CRC-16 has that property. > > there's 341376 three bit errors, so it's probably not going to be > possible to even detect them using CRC-16. > > Using a 15 bit CRC code (or other linear hash code) in combination > with a parity bit should make 3 bit errors detectable however. > > This should be do-able in 4000 or so instuction steps - not vastly worse > than the CRC computation itself - especially if you can get perfect > hashing in your LUT. >Thank you, that's very useful. Just one point - my CRC calculation uses a 512 byte LUT and is done on-the-fly taking only a few instructions for each byte. -- Cheers Clive
Reply by ●May 20, 20222022-05-20
On Thu, 19 May 2022 20:38:24 -0700 (PDT), whit3rd <whit3rd@gmail.com> wrote:>On Thursday, May 19, 2022 at 1:59:08 PM UTC-7, John Larkin wrote: >> On Thu, 19 May 2022 12:24:46 -0700 (PDT), whit3rd <whi...@gmail.com> >> wrote: >> >On Thursday, May 19, 2022 at 8:03:55 AM UTC-7, jla...@highlandsniptechnology.com wrote: > > >> >> Of course, some people are hostile to ideas. > >> >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. > >> 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. I have to be careful that my status doesn't make people assume that I'm right; I don't want to be the poison. I have grey hair, but cannot recall ever meeting>someone who was 'hostile to ideas' in general.Sounds like you haven't brainstormed a lot. -- Anybody can count to one. - Robert Widlar
Reply by ●May 20, 20222022-05-20
whit3rd wrote:> On Thursday, May 19, 2022 at 1:59:08 PM UTC-7, John Larkin wrote: >> On Thu, 19 May 2022 12:24:46 -0700 (PDT), whit3rd <whi...@gmail.com> >> wrote: >>> On Thursday, May 19, 2022 at 8:03:55 AM UTC-7, jla...@highlandsniptechnology.com wrote: > > >>>> Of course, some people are hostile to ideas. > >>> 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. > >> 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'. I have grey hair, but cannot recall ever meeting > someone who was 'hostile to ideas' in general. >You've lived a sheltered life. Back in my early days at IBM Research, I was in the Manufacturing Research department. It was pretty much a gizmo-builder's paradise--an apparently endless series of hard, interesting, and economically important problems that needed custom instruments to solve, pleasant and very smart colleagues, smart and patient management, and very few budget constraints. A pal of mine from back then, the estimable Clayton Williams (now flourishing at BYU) needed a new lock-in amplifier. He was thinking out loud one day, "It's stupid to buy just one. I probably don't need five, so let's order two." Two shiny new lock-ins arrived in a few days. If he had needed five, five would have come instead. We were entirely self-governed--our budget came out of a big pot at Corporate, so the folks we were nominally serving couldn't really tell us what to do. Not that doing stuff randomly was encouraged, you understand, but we didn't have the product divisions cracking any whips that we had to care about. As I said, a great place to build gizmos. While the customers couldn't tell us what to do, there was a certain contingent of folks who seemed to resent this--apparently they were happier being able to make vendors dance to their tune. Thus they chose to throw rocks and tell the folks trying to do stuff that it would never work, that progress was unacceptable, that the instrument concept was all wrong, and so on and so forth. Those folks, you absolutely had to keep out of the planning stage of the project, or they'd trash you to their management and often succeed in killing the effort. There were also folks who wanted to swoop in once the project was on rails and steal the credit. There was even a select demographic that habitually did both. When IBM had its near-death experience in 1992, all those folks were gone, which was great, but so of course were the lush budgets, which wasn't that great. My time at IBM was like the perfect 21-year vacation--I was excited to start and excited to leave (as well as scared). Cheers Phil Hobbs -- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC / Hobbs ElectroOptics Optics, Electro-optics, Photonics, Analog Electronics Briarcliff Manor NY 10510 http://electrooptical.net http://hobbs-eo.com
Reply by ●May 20, 20222022-05-20
On Fri, 20 May 2022 12:11:23 -0400, Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> wrote:>whit3rd wrote: >> On Thursday, May 19, 2022 at 1:59:08 PM UTC-7, John Larkin wrote: >>> On Thu, 19 May 2022 12:24:46 -0700 (PDT), whit3rd <whi...@gmail.com> >>> wrote: >>>> On Thursday, May 19, 2022 at 8:03:55 AM UTC-7, jla...@highlandsniptechnology.com wrote: >> >> >>>>> Of course, some people are hostile to ideas. >> >>>> 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. >> >>> 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'. I have grey hair, but cannot recall ever meeting >> someone who was 'hostile to ideas' in general. >> > >You've lived a sheltered life. Back in my early days at IBM Research, I >was in the Manufacturing Research department. It was pretty much a >gizmo-builder's paradise--an apparently endless series of hard, >interesting, and economically important problems that needed custom >instruments to solve, pleasant and very smart colleagues, smart and >patient management, and very few budget constraints. A pal of mine from >back then, the estimable Clayton Williams (now flourishing at BYU) >needed a new lock-in amplifier. He was thinking out loud one day, "It's >stupid to buy just one. I probably don't need five, so let's order >two." Two shiny new lock-ins arrived in a few days. If he had needed >five, five would have come instead. > >We were entirely self-governed--our budget came out of a big pot at >Corporate, so the folks we were nominally serving couldn't really tell >us what to do. Not that doing stuff randomly was encouraged, you >understand, but we didn't have the product divisions cracking any whips >that we had to care about. As I said, a great place to build gizmos. > >While the customers couldn't tell us what to do, there was a certain >contingent of folks who seemed to resent this--apparently they were >happier being able to make vendors dance to their tune. Thus they chose >to throw rocks and tell the folks trying to do stuff that it would never >work, that progress was unacceptable, that the instrument concept was >all wrong, and so on and so forth. Those folks, you absolutely had to >keep out of the planning stage of the project, or they'd trash you to >their management and often succeed in killing the effort. > >There were also folks who wanted to swoop in once the project was on >rails and steal the credit. There was even a select demographic that >habitually did both. > >When IBM had its near-death experience in 1992, all those folks were >gone, which was great, but so of course were the lush budgets, which >wasn't that great. My time at IBM was like the perfect 21-year >vacation--I was excited to start and excited to leave (as well as scared). > >Cheers > >Phil HobbsIt's interesting that none of the giant tube companies were long-term successful in semiconductors. Garage shops killed GE, RCA, Motorola, Sylvania, and many others. Efinix will be interesting to watch, against Xilinx and Altera. -- Anybody can count to one. - Robert Widlar
Reply by ●May 20, 20222022-05-20
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.
Reply by ●May 20, 20222022-05-20
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. Brainstorming is a formal procedure that eliminates the scenario you describe; there are no immediate judgments. Competent individuals will foresee problems, and avoid them, but that is NOT hostility in any sense of the word. Ideas aren't opponents.
