bit error detection

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

Translate This Thread From English to

Threaded View
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?

Thanks in advance,
Bruce

Re: bit error detection
Quoted text here. Click to load it


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
Quoted text here. Click to load it

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
Quoted text here. Click to load it
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)

Quoted text here. Click to load it

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
your original transmitted bytes XORing the transmitted and received
byte will show any differing bits that can then be counted. Assuming
that the bit errors are quite rare and thus, only those result bytes
that are non-zero after XORing needs to be processed bit by bit. If
the likely error rate is very large (> 10 %), it would make sense to
use table look-up to get the number of bits in a byte.

Paul
  

Site Timeline