Data Link Error Detection / Correction Methods

• LRC Longitudinal Redundancy Check

• CRC Cyclic Redundancy Check

• FC Fire codes

• BCH Bose-Chaudhuri-Hocquenghem

• RS Reed-Solomon

• HC Hamming codes

• VCC Virerbi Convilutional Coding for Forward Error Correction (FEC)

• Golay

Compression@

See also:

• http://imailab-www.iis.u-tokyo.ac.jp/~robert/codes.html This page contains free programs written in C language that implement encoding and decoding routines of popular error correcting codes (ECC), such as Reed-Solomon codes, BCH codes, the binary Golay code, a binary Goppa code, a Viterbi decoder and more.
• ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt
• Keywords: Reed-Solomon forward error-correcting coder/decoder Error Detection and Correction Units Hamming Error Control Coding Techniques convolutional coding Viterbi decoding Parity ECC
• DDJ January 1997 - Encryption, Error Correction & Compression
• Heaps can also be used to construct optimal binary trees for Huffman compression, as shown in Mark Nelson's article "Priority Queues and the STL" (Dr. Dobb's Journal, January 1996).
• http://www.iversoft.com/piclist/9803/1368.shtml
• http://www.ednmag.com/reg/1997/110697/23df_06.htm In picking ECCs, the key is bit-error location--not rate
• http://www.iet.unipi.it/~luigi/fec.html Software FEC in computer communications

Books

• S. Haykin. Communications Systems. Wiley, 3rd edition, 1994.
• W. G. Chambers. Basics of Communications and Coding. Oxford Science Publications. Clarendon Press Oxford, 1985.
• P. Sweeney. Error Control Coding: An Introduction. Prentice-Hall, 1991.
• R. E. Blahut. The theory and practice of error control codes. Addison-Wesley, 1983.
• Roger L. Freeman. Telecommunication Transmission Handbook, 3rd Edition. John Wiley and Sons, Inc., 1991
• E. Schooler, J. Gemmel "Using Multicast FEC to Solve the Midnight Madness Problem", Microsoft Research Tech. Report MSR-TR-97-25

Patents

• US04829526
• US05220568
• US06052812

Scott Dattalo

How to measure linearity error.

1) Collect a whole bunch of data and record a) the voltage applied and b) and the converted digital value. You also should collect several samples at each voltage value and use the mean of the digital values to represent converted digital value. There's another test for measuring the spread.

2) Find the least square's curve fit of the data. In other words, find the line that best fits the data.

3) Find the sample that most deviates from this line.

The line found by the least square's curve fit is of the form:

   y = m*x + b

where
 x = true value of the input signal (the applied voltage)

 y = expected value when the true value is applied (the actual value is
     what you measure)

 m & b are the slope and intercept of the line and are calculated:


m = [s(x) * s(x * d) - s(x*x) s(d)] / den

b = [s(x) * s(d) - n * s(x * d) ] / den

den = s(x)*s(x) - n * s(x*x)

where,

d = digitized value
n = total number of samples

and
          n
        -----
        \
s( ) =  /     (   )
        -----
         i=1

Once you have m and b, you can perform step 3 by running the applied voltage through the line representing the data and comparing the expected value output with the value you actually measured. The Linearity Error is then:

L = max( ( d - y ) / x_fr ) * 100%

where x_fr is the full range of the data, or 4096 for a 12-bit A/D.

Like I said earlier, I've got an octave program to do this. If anyone wants it, drop me a line. You probably can find a lsf function in excel too.

See also:

• http://rcs.ee.washington.edu/compression/amohr/papers/dcc99/

Questions:

• KILLspamdinadina2001 at STOPspamyahoo.com asks: "which of the following is a live coding?
  1. )block coding
  2. )HDB-3 coding
  3. )BCH coding
  4. )convolution coding"

See:

• /techref/microchip/math/bit/parity.htm PIC Microcontoller Bit Math Method Parity+
• /techref/microchip/memerr.htm PIC Microcontoller Memory Methods for Error Detection and Correction+

Code:

Archive:

• PICList post "Hamming codes" +

Comments:

  .