Do you have a question? Post it now! No Registration Necessary
- Subject
- Posted on
- bit error detection
- 07-22-2004
posted on
July 22, 2004, 2:05 pm
July 22, 2004, 2:05 pm
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
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
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.
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
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
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
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
- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming
- » MMC specification
- — Previous thread in » Embedded Programming
- » A new benchmark suitable for small systems: stdcbench
- — Newest thread in » Embedded Programming
- » How to use while loop to detect one of two events, event a, or event b
- — The site's Newest Thread. Posted in » Raspberry Pi Group