1. Home
  2. Embedded Programming
  3. bit error detection

bit error detection

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

Reply to
Bruce
Loading thread data ...

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

Reply to
Hans-Bernhard Broeker

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

Reply to
steven

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

formatting link
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

Reply to
Rafael Deliano

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

Reply to
Rafael Deliano

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

Reply to
Paul Keinanen

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.