Is there such thing as a 4 bit CRC ?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View



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.

Thanks
boB



Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it


Looks like there are some answers on the web.  DuH !

Useful experience still welcomed !

boB

Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it


A simple 16 nibble array would work just fine.  Of course.

Getting close so I am feeling a bit dumb even asking :)



Re: Is there such thing as a 4 bit CRC ?



Quoted text here. Click to load it


Looks like  x4 + x1 + 1   is used but that won't fit into 4 bottom
bits.  Maybe what I am really looking for is just a bastardization of
the 4 bits I am tryng to hash ?  Not sure how smart that table has to
be.




Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it


Nevermind...   I'm just stoopid.

Created an array of 15 randome numbers...
That should work.







Re: Is there such thing as a 4 bit CRC ?
On 2/21/2021 5:14 PM, boB wrote:
Quoted text here. Click to load it

You want the "distance" (i.e., number of bits that must change in order
to convert one valid code into another valid -- but, now, INCORRECT -- code
to be as long as possible.  FOR EVERY POSSIBLE VALID CODE.

Once can *detect* N errors in codes if the distance between valid codes is N+1.

So, if you have to flip a minimum of 2 bits to be able to convert one code
word into another valid (but incorrect) code word, then you can obviously
detect any code that has *only* ONE flipped bit.

You can *correct* M errors in a code word if the minimum distance between code
words is 2M+1.

Note that you need to understand the nature of your error sources in order
to understand the protection any code will present.  If each bit stands an
equal chance of flipping -- but, the chance of multiple bits flipping is
lessened due to the independence of those events -- then you want a
different sort of code than if, for example, one flip *tends* to result in
other flips.

E.g., if you are sending data down a communication channel and noise
can blot out large chunks of the data stream, then your code needs
to address the likeliness of multiple bits being affected in the
same corruption event.

[Google "Hamming Distance"]


Re: Is there such thing as a 4 bit CRC ?
On Sun, 21 Feb 2021 17:43:23 -0700, Don Y

Quoted text here. Click to load it

I will Google Hamming Distance.  I think I understand that but
possibly not.

This system does have the possibility of having quite a bit of noise
actually. I probably should  not have too small of error detection at
least.   I hadn't thought of using error correction but sending
multiple times instead for this one.  I think I have more time to
resend rather than processor time for decoding.

Thank all of you for making me think more about this.








Re: Is there such thing as a 4 bit CRC ?
On 2/21/2021 10:18 PM, boB wrote:
Quoted text here. Click to load it

If you make up some examples, you can see how this translates to
Real World.  Note that there are always assumptions in coding;
e.g., you *assume* the "nearest" code word is the RIGHT codeword
(because it has the least number of "errors/flips") -- but, that's
not guaranteed!  (i.e., there is some probability that more bits
have flipped than you were expecting so correcting to the "nearest"
may be wrong!)

[This is why you have to understand the nature of the "error signal"
that is present in your system.  You might find that code words
like 111111 and 000000 are really bad because the system might be
able to EASILY create such errors!]

Quoted text here. Click to load it

The problem you will face is how you deal with discrepancies between
the multiple copies (messages) that you then receive.  I.e., if you
decide the first one is bad (based on some criteria), are you more
certain that the next is *good* -- even if it APPEARS to be good?

A common flaw in this sort of approach is using multiple copies
in the hope that you can get a majority concensus (i.e., best
two out of three).  But, if you look at coding theory, you
can see that three copies of a datum wastes lots of bits but
gives considerably less redundancy than you would expect!

BNPF was used with PPT, ages ago.  It encodes an 8bit value into
*10* ASCII characters (i.e., 70 bits to encode 8).  But, it
allowed each of the 8 bits to be durably encoded.  (other
encodings would have been smarter but BNPF had the advantage of
being easily decoded/encoded by humans)

You might benefit from adding some heuristics ("common sense")
to your implementation.  E.g., if the messages (commands) are
intended to control a motor and you've already decided that
the motor SHOULD be "on", how might you handle a series of
messages that say "off", "on", "off", "on"... in rapid succession?

I.e., is it likely that the motor is *actually* being commanded
on and off that frequently?  Or, is it more likely that you are
incorrectly decoding messages??  So, you might, instead, deduce that
your communication channel is unreliable and bring the motor to a
"safe" state given that you're not sure what state it REALLY
should be in.

YMMV



Re: Is there such thing as a 4 bit CRC ?
On 2/21/21 6:10 PM, boB wrote:
Quoted text here. Click to load it


IF I am doing my math right 8 bits is good enough for 4 data bits, 3
syndrome bits, and a parity bit to give you 1 bit error correction, 2
bit error detection. That might be better than a 4 bit CRC.

Re: Is there such thing as a 4 bit CRC ?
On Sun, 21 Feb 2021 19:17:02 -0500, Richard Damon

Quoted text here. Click to load it


Thanks.  I think I may just do 8 bit CRC for the short command.

I will be re-transmitting often enough I think for the messages to get
through.  




Re: Is there such thing as a 4 bit CRC ?
On 22/02/2021 01:17, Richard Damon wrote:
Quoted text here. Click to load it

Your maths is good enough.

Given 4 data bits a, b, c, and d, you can calculate the parity bits

    p = a ^ b ^ c
    q = a ^ b ^ d
    r = a ^ c ^ d
    s = b ^ c ^ d

and send these.

On reception, you then calculate:

    P = p ^ a ^ b ^ c
    Q = q ^ a ^ b ^ d
    R = r ^ a ^ c ^ d
    S = s ^ b ^ c ^ d

Correct transmission will give zero for all of these.  For one error,
any three can be used to give the error bit - for two errors, those
results will be inconsistent.





Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it

Use some Hamming code, which can correct one bit error and
additionally detect odd number of bit errors. Used e.g. in Teletext
page numbers, 4 bits of data (actually BCD) in an 8 bit octet (byte).  


Re: Is there such thing as a 4 bit CRC ?
On Mon, 22 Feb 2021 06:05:16 +0200, snipped-for-privacy@downunder.com wrote:

Quoted text here. Click to load it


I had thought of Hamming (I think that's what I was thinking of ?)

Thanks.

Next, I do have to see exactly how much noise I will be dealing with
here.   It will be RS485 at not very high of data rate so I should
have Shannon on my side.  I hope.

boB




Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it


Theoretically RS-485 should be capable of 115200 bit/s up to 1 km, but
requires good twisted pairs, proper termination and in practice also
galvanic isolation.

I would be more worried about the short single byte messages
especially on 2 wire RS-485, since during data direction changes
(Rx/Tx switching) all drives are in tri-state and only the "fail safe"
termination will keep the line in IDLE state.

If "fail-safe" termination is not used, turn on the Tx driver into
IDLE ("1") state for a few character times. before sending the actual
command byte.  Keeping the Tx in IDLE state for a while, will get rid
of any reflections on the bus, reducing the risk of bit errors.


Re: Is there such thing as a 4 bit CRC ?
On 22/02/2021 06:22, boB wrote:
Quoted text here. Click to load it

Some kinds of noise or problems are related to data rates (and helped by
low rates), but many are not.  Don't blindly assume that lower rates are
always better - sometimes it is better with higher rates and more
expressive telegrams.



Re: Is there such thing as a 4 bit CRC ?
On Mon, 22 Feb 2021 10:00:19 +0100, David Brown

Quoted text here. Click to load it

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)




Re: Is there such thing as a 4 bit CRC ?
On 02/22/2021 04:58 PM, boB wrote:
Quoted text here. Click to load it

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.



Re: Is there such thing as a 4 bit CRC ?
On Mon, 22 Feb 2021 17:49:04 +0100, Johann Klammer

Quoted text here. Click to load it


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 !

Re: Is there such thing as a 4 bit CRC ?

Quoted text here. Click to load it

If this is a unidirectional system with just the master transmitting,
keep the Tx always active. No need for "fail safe" DC biasing.

If the bus is just within a single PCB backplane, not much
interference is expected at slow data rates. I would not expect much
problems with low data rates (300-1200 bits/s) and single byte
commands.



Re: Is there such thing as a 4 bit CRC ?
On 22.2.21 20.36, boB wrote:
Quoted text here. Click to load it


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.

The 100 to 150 ohm resistance is a suitable termination for common
twisted-pair line.

--  

-TV

Site Timeline