On Mon, 22 Feb 2021 21:21:59 +0200, Tauno Voipio <tauno.voipio@notused.fi.invalid> wrote:>On 22.2.21 20.36, boB wrote: >> On Mon, 22 Feb 2021 17:49:04 +0100, Johann Klammer >> <klammerj@NOSPAM.a1.net> wrote: >> >>> On 02/22/2021 04:58 PM, boB wrote: >>>> Thanks guys ! >>>> >>>> It is great to get some good dialog on this newsgroup :) >>>> Although I have seen some very good chat in the past. >>>> >>>> This RS485 is on a back-plane and so is a short line at least. >>>> >>>> Communications will mainly be from one master to maybe 4 slaves. >>>> >>>> These are inverter modules so that is where the noise comes from. >>>> >>>> I had one PWM line that was being interfereed with on the bus and what >>>> I did to fix it was to R-C low pass filter at the receiving logic end >>>> in the module. Worked wonderfully ! >>>> >>>> I am also designing in this R-C Low Pass Filter between the RS485 RX >>>> output and the microcontroller (ST) UART input. >>>> >>>> Now, UARTS have up to a 16X sample and I have known this for many >>>> years (decades actually) but I have never looked into how that >>>> sampling actually works. Lower baud rate, I would imagine, should >>>> separate these samples by more time and help the data integrity. >>>> Any insight into this aspect ? >>>> >>>> boB (in Phoenix AZ this week) >>>> >>>> >>>> >>> >>> You seem to be expecting interference from the inverters. >>> undriven differential lines like 485 might be susceptible >>> to that. I believe there are biasing contraptions to set a >>> defined output level in Hiz. use those. >>> An rc filter on output might be a good idea, but by itself >>> won't keep a Hiz line from toggling. >>> Driving to a defined level before going Hiz is also a good >>> idea to increase slew rates. >>> >> >> >> Ya know... We did that at another company several years ago on >> RS485... It got way out of hand. I'm not sure how biasing up the A >> and B lines might screw up any common mode rejection that is built >> into these receivers ? >> >> I think that with good rejection of bad packets, using a CRC at the >> end of the packet, this should not be an issue. Also, the noise that >> gets into the lines is VERY fast and not long lasting at all (luckily) >> >> The master transmit can certainly bring the transmitter active long >> before the actual data is transmitted. In fact, I'm not so sure I >> can't just keep the master holding the RS485 bus active all the time ? >> >> For this application, I have not considered two-way communications yet >> as I don't think it will be necessary. Yet. >> >> But we will see. Biasing may very well help. >> >> Thank you for this input ! > > >The classical way of biasing is at the ends of the bus line, with >100 - 150 ohm resistor between the A and B lines, and suitable >resistors from one line to ground and the other resistor from the >other line to power supply. With equal biasing resistors the >common-mode is not spoiled. > >There is considerable confusion which line is A and which is B. >The bias polarity must be set so that the output of a receiver >stays at the UART idle level (usually up) when no transmitter is >active.There is no confusion which line is A and which is B. Unfortunately, there is a great confusion which line is Tx+ and which is Tx- or D+ or D-, since some manufacturers have these mixed up. Due to this mess, I have recommended using A/B nomenclature for RS-485 as well as for the RS422 for the Tx pair (and A'/B' for the receiving RS-422 pair).>The 100 to 150 ohm resistance is a suitable termination for common >twisted-pair line.100-120 ohms sounds about right, 150 ohms is a bit too much for ordinal twisted pairs.
Is there such thing as a 4 bit CRC ?
Started by ●February 21, 2021
Reply by ●February 22, 20212021-02-22
Reply by ●February 23, 20212021-02-23
boB <boB@k7iq.com> wrote:> > > > If I create a 1 byte command that only uses 4 bits for 16 different > functions, and there were NO following bytes (there might be folling > bytes for some CMDs), I was thinking that the lower 4 bits could be > used for error detection. > > Could of course just truncate an 8 bit CRC I suppose and place it > there. > > Just thought I would ask. Never thought of only 4 bits before but > sometimes a single byte could be efficient, bandwidth wise.CRC is build from a polynomial with specific properties. Such polynomials exist for any number of bits. With low number of bit CRC have limited detection capability: 1-bit CRC is essentially the same as parity, 4-bit CRC is not very good. OTOH with only 4 data bits 4 (or 8) bit CRC is trivial: essentially you just get back your bits. So it is the same as transmiting two copies of your command: if they match then command is hopefully OK, is not you have error. That will catch single bit errors and most two bit errors, but will miss case when both command bit and corresponding bit in the copy is togled. As other pointed out Hamming code can do better, that is discover all 2 bit errors and correct one bit errors. Or alternatively, detect up to 3 bit errors. -- Waldek Hebisch
Reply by ●February 23, 20212021-02-23
On 2/23/2021 3:53 PM, antispam@math.uni.wroc.pl wrote:> boB <boB@k7iq.com> wrote: >> >> >> >> If I create a 1 byte command that only uses 4 bits for 16 different >> functions, and there were NO following bytes (there might be folling >> bytes for some CMDs), I was thinking that the lower 4 bits could be >> used for error detection. >> >> Could of course just truncate an 8 bit CRC I suppose and place it >> there. >> >> Just thought I would ask. Never thought of only 4 bits before but >> sometimes a single byte could be efficient, bandwidth wise. > > CRC is build from a polynomial with specific properties. Such > polynomials exist for any number of bits. With low number of > bit CRC have limited detection capability: 1-bit CRC is essentially > the same as parity, 4-bit CRC is not very good. OTOH with > only 4 data bits 4 (or 8) bit CRC is trivial: essentially > you just get back your bits. So it is the same as transmiting > two copies of your command: if they match then command is > hopefully OK, is not you have error. That will catch > single bit errors and most two bit errors, but will miss > case when both command bit and corresponding bit in the > copy is togled. As other pointed out Hamming code can > do better, that is discover all 2 bit errors and correct > one bit errors. Or alternatively, detect up to 3 bit > errors.No. Two copies will only ALERT you to a bit error; it will not allow you to recover (correct) that error. 1010 1011 leaves you unsure as to whether the intended command was 1010 *or* 1011 (along with any number of less likely corruptions). So, simple duplication wastes bits. You can get better coverage with other encodings.
Reply by ●February 24, 20212021-02-24
On 23/02/2021 22:53, antispam@math.uni.wroc.pl wrote:> boB <boB@k7iq.com> wrote: >> >> >> >> If I create a 1 byte command that only uses 4 bits for 16 different >> functions, and there were NO following bytes (there might be folling >> bytes for some CMDs), I was thinking that the lower 4 bits could be >> used for error detection. >> >> Could of course just truncate an 8 bit CRC I suppose and place it >> there. >> >> Just thought I would ask. Never thought of only 4 bits before but >> sometimes a single byte could be efficient, bandwidth wise. > > CRC is build from a polynomial with specific properties. Such > polynomials exist for any number of bits. With low number of > bit CRC have limited detection capability: 1-bit CRC is essentially > the same as parity, 4-bit CRC is not very good. OTOH with > only 4 data bits 4 (or 8) bit CRC is trivial: essentially > you just get back your bits. So it is the same as transmiting > two copies of your command: if they match then command is > hopefully OK, is not you have error. That will catch > single bit errors and most two bit errors, but will miss > case when both command bit and corresponding bit in the > copy is togled. As other pointed out Hamming code can > do better, that is discover all 2 bit errors and correct > one bit errors. Or alternatively, detect up to 3 bit > errors....or correct 2 bit errors. Hamming has been used for 2 bit correcting EDACs for years (at least 20): http://microelectronics.esa.int/core/ipdoc/EDAC8Cyclic.pdf Hans www.ht-lab.com>
Reply by ●February 24, 20212021-02-24
On 2/24/2021 7:54 AM, HT-Lab wrote:> On 23/02/2021 22:53, antispam@math.uni.wroc.pl wrote: >> boB <boB@k7iq.com> wrote: >>> >>> >>> >>> If I create a 1 byte command that only uses 4 bits for 16 different >>> functions, and there were NO following bytes (there might be folling >>> bytes for some CMDs), I was thinking that the lower 4 bits could be >>> used for error detection. >>> >>> Could of course just truncate an 8 bit CRC I suppose and place it >>> there. >>> >>> Just thought I would ask. Never thought of only 4 bits before but >>> sometimes a single byte could be efficient, bandwidth wise. >> >> CRC is build from a polynomial with specific properties. Such >> polynomials exist for any number of bits. With low number of >> bit CRC have limited detection capability: 1-bit CRC is essentially >> the same as parity, 4-bit CRC is not very good. OTOH with >> only 4 data bits 4 (or 8) bit CRC is trivial: essentially >> you just get back your bits. So it is the same as transmiting >> two copies of your command: if they match then command is >> hopefully OK, is not you have error. That will catch >> single bit errors and most two bit errors, but will miss >> case when both command bit and corresponding bit in the >> copy is togled. As other pointed out Hamming code can >> do better, that is discover all 2 bit errors and correct >> one bit errors. Or alternatively, detect up to 3 bit >> errors. > > ...or correct 2 bit errors.With 4 syndrome bits on a 4 bit datum?? (as the OP suggested)> Hamming has been used for 2 bit correcting EDACs for years (at least 20): > > http://microelectronics.esa.int/core/ipdoc/EDAC8Cyclic.pdf > > Hans > www.ht-lab.com > > > >> >
Reply by ●February 24, 20212021-02-24
On 24/02/2021 16:12, Don Y wrote:> On 2/24/2021 7:54 AM, HT-Lab wrote: >> On 23/02/2021 22:53, antispam@math.uni.wroc.pl wrote: >>> boB <boB@k7iq.com> wrote: >>>> >>>> >>>> >>>> If I create a 1 byte command that only uses 4 bits for 16 different >>>> functions, and there were NO following bytes (there might be folling >>>> bytes for some CMDs), I was thinking that the lower 4 bits could be >>>> used for error detection. >>>> >>>> Could of course just truncate an 8 bit CRC I suppose and place it >>>> there. >>>> >>>> Just thought I would ask. Never thought of only 4 bits before but >>>> sometimes a single byte could be efficient, bandwidth wise. >>> >>> CRC is build from a polynomial with specific properties. Such >>> polynomials exist for any number of bits. With low number of >>> bit CRC have limited detection capability: 1-bit CRC is essentially >>> the same as parity, 4-bit CRC is not very good. OTOH with >>> only 4 data bits 4 (or 8) bit CRC is trivial: essentially >>> you just get back your bits. So it is the same as transmiting >>> two copies of your command: if they match then command is >>> hopefully OK, is not you have error. That will catch >>> single bit errors and most two bit errors, but will miss >>> case when both command bit and corresponding bit in the >>> copy is togled. As other pointed out Hamming code can >>> do better, that is discover all 2 bit errors and correct >>> one bit errors. Or alternatively, detect up to 3 bit >>> errors. >> >> ...or correct 2 bit errors. > > With 4 syndrome bits on a 4 bit datum?? (as the OP suggested) >That would be "no". (This post is not really a direct follow up to Don's post, that's just a place to put it.) It's easy to do the calculations. If you have 8 bits of total transferred data, to correct 1 bit of error you need to distinguish 9 cases - 1 case of all bits correct, and 8 cases of single bit errors. This means 4 bits need to be syndrome, leaving 4 bits for data. If you want to correct 2 bit errors, you need another (8 * 7) / 2 = 28 cases, or 37 cases in total. That takes 6 bits, leaving 2 bits for data. Good sizes for single-bit correction are thus: 4-bit data, 3-bit syndrome 11-bit data, 4-bit syndrome 26-bit data, 5-bit syndrome (You can use an extra bit as parity, giving 1 bit correction and 2 bit detection without correction.) For double-bit correction, you can have: 2-bit data, 5 bit syndrome 8-bit data, 7 bit syndrome 22-bit data, 9 bit syndrome 52-bit data, 11 bit syndrome For triple-bit correction, you can have: 1-bit data, 6 bit syndrome 5-bit data, 10 bit syndrome 19-bit data, 13 bit syndrome 48-bit data, 16 bit syndrome Bigger sizes give greater efficiency. But it's not always easy to get good Hamming code algorithms for bigger sizes, and it is of course not necessarily the most sensible way to handle error detection and correction. For advanced algorithms you might be interested in the distribution of possible errors (is it more likely to have multiple errors in a row, rather than completely independent errors?), and at your receiver end you might have additional information about the signal quality. If you know a particular part of a received message is untrustworthy, it gets far easier to do the correction. (You can correct a missing bit of an arbitrarily long message with just one parity bit.)
Reply by ●February 24, 20212021-02-24
Don Y <blockedofcourse@foo.invalid> wrote:> On 2/23/2021 3:53 PM, antispam@math.uni.wroc.pl wrote: > > boB <boB@k7iq.com> wrote: > >> > >> > >> > >> If I create a 1 byte command that only uses 4 bits for 16 different > >> functions, and there were NO following bytes (there might be folling > >> bytes for some CMDs), I was thinking that the lower 4 bits could be > >> used for error detection. > >> > >> Could of course just truncate an 8 bit CRC I suppose and place it > >> there. > >> > >> Just thought I would ask. Never thought of only 4 bits before but > >> sometimes a single byte could be efficient, bandwidth wise. > > > > CRC is build from a polynomial with specific properties. Such > > polynomials exist for any number of bits. With low number of > > bit CRC have limited detection capability: 1-bit CRC is essentially > > the same as parity, 4-bit CRC is not very good. OTOH with > > only 4 data bits 4 (or 8) bit CRC is trivial: essentially > > you just get back your bits. So it is the same as transmiting > > two copies of your command: if they match then command is > > hopefully OK, is not you have error. That will catch > > single bit errors and most two bit errors, but will miss > > case when both command bit and corresponding bit in the > > copy is togled. As other pointed out Hamming code can > > do better, that is discover all 2 bit errors and correct > > one bit errors. Or alternatively, detect up to 3 bit > > errors. > > No. Two copies will only ALERT you to a bit error; > it will not allow you to recover (correct) that error. > > 1010 1011 leaves you unsure as to whether the intended > command was 1010 *or* 1011 (along with any number of less > likely corruptions).You are reading something that I not wrote: where you find claim that CRC can correct errors?> So, simple duplication wastes bits. You can get better > coverage with other encodings.As I wrote above (with better = Hamming). -- Waldek Hebisch
Reply by ●February 24, 20212021-02-24
On 2/24/2021 4:32 PM, antispam@math.uni.wroc.pl wrote:> Don Y <blockedofcourse@foo.invalid> wrote: >> On 2/23/2021 3:53 PM, antispam@math.uni.wroc.pl wrote: >>> boB <boB@k7iq.com> wrote: >>>> >>>> >>>> >>>> If I create a 1 byte command that only uses 4 bits for 16 different >>>> functions, and there were NO following bytes (there might be folling >>>> bytes for some CMDs), I was thinking that the lower 4 bits could be >>>> used for error detection. >>>> >>>> Could of course just truncate an 8 bit CRC I suppose and place it >>>> there. >>>> >>>> Just thought I would ask. Never thought of only 4 bits before but >>>> sometimes a single byte could be efficient, bandwidth wise. >>> >>> CRC is build from a polynomial with specific properties. Such >>> polynomials exist for any number of bits. With low number of >>> bit CRC have limited detection capability: 1-bit CRC is essentially >>> the same as parity, 4-bit CRC is not very good. OTOH with >>> only 4 data bits 4 (or 8) bit CRC is trivial: essentially >>> you just get back your bits. So it is the same as transmiting >>> two copies of your command: if they match then command is >>> hopefully OK, is not you have error. That will catch >>> single bit errors and most two bit errors, but will miss >>> case when both command bit and corresponding bit in the >>> copy is togled. As other pointed out Hamming code can >>> do better, that is discover all 2 bit errors and correct >>> one bit errors. Or alternatively, detect up to 3 bit >>> errors. >> >> No. Two copies will only ALERT you to a bit error; >> it will not allow you to recover (correct) that error. >> >> 1010 1011 leaves you unsure as to whether the intended >> command was 1010 *or* 1011 (along with any number of less >> likely corruptions). > > You are reading something that I not wrote: where you find > claim that CRC can correct errors?I didn't say that YOU had said it could correct. I stated that duplicating the data only lets you DETECT errors. So, you've "spent" 4 bits and have only the ability to detect *some* types of errors. (see below) The same applies to transmitting two copies (if the two copies differ, all you know is that AT LEAST one copy is incorrect; so, should you then transmit a THIRD copy???)>> So, simple duplication wastes bits. You can get better >> coverage with other encodings. > > As I wrote above (with better = Hamming). >
Reply by ●February 25, 20212021-02-25
On Wed, 24 Feb 2021 23:32:34 +0000 (UTC), antispam@math.uni.wroc.pl wrote:>Don Y <blockedofcourse@foo.invalid> wrote: >> On 2/23/2021 3:53 PM, antispam@math.uni.wroc.pl wrote: >> > boB <boB@k7iq.com> wrote: >> >> >> >> >> >> >> >> If I create a 1 byte command that only uses 4 bits for 16 different >> >> functions, and there were NO following bytes (there might be folling >> >> bytes for some CMDs), I was thinking that the lower 4 bits could be >> >> used for error detection. >> >> >> >> Could of course just truncate an 8 bit CRC I suppose and place it >> >> there. >> >> >> >> Just thought I would ask. Never thought of only 4 bits before but >> >> sometimes a single byte could be efficient, bandwidth wise. >> > >> > CRC is build from a polynomial with specific properties. Such >> > polynomials exist for any number of bits. With low number of >> > bit CRC have limited detection capability: 1-bit CRC is essentially >> > the same as parity, 4-bit CRC is not very good. OTOH with >> > only 4 data bits 4 (or 8) bit CRC is trivial: essentially >> > you just get back your bits. So it is the same as transmiting >> > two copies of your command: if they match then command is >> > hopefully OK, is not you have error. That will catch >> > single bit errors and most two bit errors, but will miss >> > case when both command bit and corresponding bit in the >> > copy is togled. As other pointed out Hamming code can >> > do better, that is discover all 2 bit errors and correct >> > one bit errors. Or alternatively, detect up to 3 bit >> > errors. >> >> No. Two copies will only ALERT you to a bit error; >> it will not allow you to recover (correct) that error.If duplicating data, at least complement / negate the copy, so it will help in detecting some types of errors.>> >> 1010 1011 leaves you unsure as to whether the intended >> command was 1010 *or* 1011 (along with any number of less >> likely corruptions). > >You are reading something that I not wrote: where you find >claim that CRC can correct errors?With short data+CRC after a CRC error is detected, you could flip individual bits at a time and recalculate CRC. If CRC matches, there is a candidate for correct message. If no other matches occur, we most likely have the corrected message. With longer messages, the computational load will be too high.>> So, simple duplication wastes bits. You can get better >> coverage with other encodings. > >As I wrote above (with better = Hamming).Indeed.
Reply by ●February 25, 20212021-02-25
On 25/02/2021 07:47, upsidedown@downunder.com wrote:> On Wed, 24 Feb 2021 23:32:34 +0000 (UTC), antispam@math.uni.wroc.pl > wrote: > >> Don Y <blockedofcourse@foo.invalid> wrote: >>> On 2/23/2021 3:53 PM, antispam@math.uni.wroc.pl wrote: >>>> boB <boB@k7iq.com> wrote: >>>>> >>>>> >>>>> >>>>> If I create a 1 byte command that only uses 4 bits for 16 different >>>>> functions, and there were NO following bytes (there might be folling >>>>> bytes for some CMDs), I was thinking that the lower 4 bits could be >>>>> used for error detection. >>>>> >>>>> Could of course just truncate an 8 bit CRC I suppose and place it >>>>> there. >>>>> >>>>> Just thought I would ask. Never thought of only 4 bits before but >>>>> sometimes a single byte could be efficient, bandwidth wise. >>>> >>>> CRC is build from a polynomial with specific properties. Such >>>> polynomials exist for any number of bits. With low number of >>>> bit CRC have limited detection capability: 1-bit CRC is essentially >>>> the same as parity, 4-bit CRC is not very good. OTOH with >>>> only 4 data bits 4 (or 8) bit CRC is trivial: essentially >>>> you just get back your bits. So it is the same as transmiting >>>> two copies of your command: if they match then command is >>>> hopefully OK, is not you have error. That will catch >>>> single bit errors and most two bit errors, but will miss >>>> case when both command bit and corresponding bit in the >>>> copy is togled. As other pointed out Hamming code can >>>> do better, that is discover all 2 bit errors and correct >>>> one bit errors. Or alternatively, detect up to 3 bit >>>> errors. >>> >>> No. Two copies will only ALERT you to a bit error; >>> it will not allow you to recover (correct) that error. > > If duplicating data, at least complement / negate the copy, so it will > help in detecting some types of errors. > >>> >>> 1010 1011 leaves you unsure as to whether the intended >>> command was 1010 *or* 1011 (along with any number of less >>> likely corruptions). >> >> You are reading something that I not wrote: where you find >> claim that CRC can correct errors? > > With short data+CRC after a CRC error is detected, you could flip > individual bits at a time and recalculate CRC. If CRC matches, there > is a candidate for correct message. If no other matches occur, we most > likely have the corrected message. With longer messages, the > computational load will be too high. >For some values of "likely", that might be acceptable. The trouble you face is that a CRC does not guarantee that it will let you do that in practice - you might find that there is more than one candidate bit that could be flipped in order to get a matching CRC. (Remember also that the incorrect bit might be in the CRC itself.)>>> So, simple duplication wastes bits. You can get better >>> coverage with other encodings. >> >> As I wrote above (with better = Hamming). > > Indeed. >
