# bit error detection

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

Translate This Thread From English to

•  Subject
• Author
• Posted on
Can any one point me to some information on detecting bit errors and C
or C++ algorithms that do this.  I am familiar with CRC algorithms and
have used the 16 and 32 bit routines that are in Michael Barr's
Oreilly book on Embedded Programming but what I am trying to do a bit
different.  Here's an example:

Let's say I send a bit stream (it could be 10 bits or 10,000 bits) out
a communication channel (in this case over an RF link).  The other
side echos this stream back and I want to get a quick count of the
number of bits that are wrong.

E.g. I send 0xA5A5 and get back 0xA5A4 which I want to yield the
number 1 indicating that one bit is off.  This could also apply to a
10,000 bit stream where if 900 bits were off I get 900.

I know  how to do this brute force but am looking for some more
efficient techniques/algorithms that are available.

Any thoughts or pointer on this?

Bruce

Re: bit error detection

That's simple.  XOR the echo with what it should have been, and count
1 bits.  Do this in packets of bytes or 16-bit integers and you can do
the 'count number of one bits in this' step by a table, reducing the
algorithm to a trivial

error count <- 0
while echo byte E arriving
increase error count by count_one_bits[E XOR expected]

--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: bit error detection

A while ago I found the following simple algorithm for counting "1" bits in
a dataword:

errorcount := 0
while dataword <> 0 do begin
inc(errorcount)
dataword := dataword and (dataword - 1)
end

which is more efficient than shifting through carry, especially when few
errors are expected. The loop is only executed as many times as there are
"1" bits. I like this!
The shifting method may also be ended when the result is zero, but the "Law
of Conservation of Misery" dictates that the error is always at the wrong
end of the word. :-(
HTH

Steven

Re: bit error detection
I think counting bits is even covered as an exercise in K&R.
If memory is available I would XOR and then use a 256 byte table
on every byte of the dataword and add the results.
Calculating hamming-distance was actually an opcode
in the ( bit-slice ) communications-processor of the
space-shuttle, needed for error-correcting codes.

MfG  JRD

Re: bit error detection

Testing old modems up to 1200 baud was done with a LFSR counter that
repeated after 511 bits ( 9 bit counter ). Polynomial:
x^8 + x^4 + 1   ( CCITT V.52 )
Faster transmission requires longer sequences / counters.
Sometimes used in telecom testing:
x^15 + x^14 + 1  ( 16 bit counter )
x^23 + x^18 + 1  ( 24 bit counter )
There are many other polynomials that are better, especially
ones that have 50% taps connected.
Donīt use the value 0000h to start a LFSR.

Obviously one has to synch before one can compare the bitstreams.
But as the receiver knows what is coming no loop-back is
strictly necessary.

Implementing a LFSR in software: in http://www.embeddedFORTH.de issue 6
page 16 is a flowchart ( picture 4, picture 3 ) for
x^16 + x^15 + x^13 + x^4 + 1
The XOR-mask would be D008h for that polynomial.

MfG  JRD

Re: bit error detection
On 22 Jul 2004 07:05:40 -0700, snipped-for-privacy@baesystems.com (Bruce)

This must be a homework, since I would not expect anyone to use this
kind of error correction in any real RF system :-). For instance the
synchronisation can be quite an issue, if you have a lot of dropouts.

Anyway, if you manage to pack the received bytes in the same way as