The Error Correcting Codes (ECC) Page

Tanner graph

Welcome!

This page contains several computer programs, written in C/C++ language (and some Matlab scripts), 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. Note that no effort has been made to `optimize' most of the algorithms used in the programs below. The algorithms work well, but by no means should be used as a basis for an implementation. All these programs are free to use for academic and personal purposes only. Use them at your own discretion. Enjoy!

If you have an interest in digital communication or storage system design and implementation that involves (and believe me, it will!) error control coding, drop me a line, I will be happy to learn more about novel applications of ECC and also to offer my advice.

I still recommend the following best textbooks to learn more about the fascinating topic of error correcting codes:

  1. S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, second edition, Prentice Hall: Englewood Cliffs, NJ, 2004.
  2. W.W. Peterson and E.J. Weldon, Jr., Error-Correcting Codes, 2nd edition, MIT Press: Cambridge, Mass., 1972.
  3. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland: New York, NY, 1977.

My textbook, now in its second edition, offers a gentle and hands-on (with a companion website containing more C and Matlab programs) introduction to the basic principles and applications of error correcting codes:

bookcover


Copyright (c) 1996-2008. Robert Morelos-Zaragoza. All rights reserved.



  1. The Ubiquitous Reed-Solomon Codes
  2. by Barry A. Cipra, Reprinted from SIAM News, Volume 26-1, January 1993
  3. Reed-Solomon (RS) codes
  4. Decoding the Berlekamp-Masssey (BM) algorithm, with error evaluation as explained in Lin and Costello's book.
    (Simon Rockliff, 1989)
  5. Reed-Solomon errors-and-erasures decoder
  6. Based on the above program to handle errors and erasures, plus other features. Note: The program does not work with shortened codes and codes over GF(2^m), m<8 ... it gives good ideas though.
    (Thirumoorthy, 1995)
  7. Another Reed-Solomon errors-and-erasures decoder
  8. Nicely written, greatly improved version of the program above. It now lets the user create multiple encoders at run time with specified parameters You can get the latest package here. Check also Phil's home page.
    (Phil Karn, 2006).
  9. BCH codes
  10. Enter only the length and error correcting capability. The program computes the generator polynomial of any binary BCH code, plus encoding and decoding using the BM algorithm.
    (Morelos-Zaragoza, 1994).
  11. Binary (48,36,5) BCH code.
  12. This BCH code is used in control channels for cellular TDMA in the U.S. Since this code has only two-error correcting capability, fast decoding is done by pre-solving a system of two equations (the syndromes) in two unknowns (the error positions), see MacWilliams and Slone's book, chapter 3. NOTE: There was a "bug" in this program, fixed on 8/27/97.
    (Morelos-Zaragoza, 1994).
  13. Binary (31,21,5) BCH code.
  14. This BCH code is used in the POCSAG protocol specification for pagers. The program is identical to the one above, except for the parameters. NOTE: There was a "bug" in this program. It was fixed 8/27/97.
    (Morelos-Zaragoza, 1997).
  15. Golay (23,12,7) code
  16. Fast encoding and decoding by software with look-up tables. The program uses a 16K-by-16 bit encoding table and an 8K-by-32 bit decoding table.
    (Morelos-Zaragoza, 1994).
  17. A Goppa code
  18. Encoding/Decoding of a (1024,654,75) Goppa code (originally written with a public key cryptographic scheme in mind). This program is a compact implementation of Goppa codes with parameters m=10, t=37 for 32-bit machines. Decoding method due to N. Patterson, ``Algebraic Decoding of Goppa Codes,'' IEEE Trans. Info.Theory, 21 (1975), 203-207.
    (Anonymous, as far as I know)
  19. CRC-32
  20. Computes the CRC value of a file, as used in ZMODEM or PKZIP.
    (Craig Bruce, 1994)
  21. ecc-1.2.1.tar (106496 bytes)
  22. Routines to encode and decode a file using a (255,249,7) RS code.
    (Paul Flaherty, 1993)
  23. Turbo-codes home page at JPL
  24. TURBO decoder archive: BCJR_turbo.tar
  25. An implementation of the BCJR algorithm, based on the pseudocode in W.E.Ryan's tutorial paper (PS file).
    (Mathys Walma, 1998)
  26. Viterbi decoding
  27. Package viterbi-3.0.1.tar contains programs to implement Viterbi decoding of (de-facto standard) rate-1/2 and rate-1/3 m=7 convolutional codes. Package simd-viterbi-2.0.1.tar contains programs to implement Viterbi decoders for r=1/2 k=7 and k=9 codes that use the Intel/AMD SIMD instruction sets (MMX/SSE/SSE2). Check also Phil's home page.
    (Phil Karn, 2006)
  28. galois.tar
  29. Encoding/decoding for BCH/RS codes.
    (Bart De Canne, 1994)
  30. A block coded QPSK modulation for unequal error protection (UEP)
  31. This program was used to simulate the performance of a coding scheme proposed in my Ph.D. thesis for UEP over an AWGN channel. For more details, see R.H. Morelos-Zaragoza and S. Lin, ``QPSK Block Modulation Codes for Unequal Error Protection,'' IEEE Transactions on Information Theory, Vol. 41, No. 2, pp. 576-581, March 1995.
    (Morelos-Zaragoza, 1993)
  32. Linear code bound
  33. How good is a code? What are the lower and upper bounds on the minimum distance of a linear block code given its length and dimension? The answer to this question may be found on-line! (remkor@win.tue.nl, 1995). Also try: http://www.codetables.de/ maintained by Markus Grassl (Thanks to Axel Kohnert for the pointer).
  34. Erasure-correcting codes
  35. An implementation of a block code for erasure correction in network communication protocols. The encoder/decoder runs quite fast (up to several MB/s on a Pentium).
    (Luigi Rizzo, 1996)
  36. Finite Field Calculator and Reed-Solomon Simulator
  37. Java applet of GF calculator and an RS encoder/decoder
    (Emina Soljanin, 1997)
  38. A Windows 95/NT program to do Galois Field math
  39. (Andrew Lin, 1997)
  40. Properties of binary linear codes
  41. This is a C++ program (compiled for Sparcs) that computes properties of binary codes, from more basic items such as minimum distance and dimension to more complicated properties such as trellis decoding complexity and whether the Tanner graph of the code is cycle-free.
    (Ari Trachtenberg, 1998)
  42. Maximal LFSR program
  43. A program to find primitive polynomials of maximum cycle length
    (Steve Ungstad, 1999)
  44. A Tutorial on Convolutional Coding with Viterbi Decoding
  45. The purpose of this tutorial is to introduce the reader to a forward error correction technique known as convolutional coding with Viterbi decoding. More particularly, this tutorial will focus primarily on the Viterbi decoding algorithm itself. The intended audience is anyone interested in designing or understanding wireless digital communications systems.
    (Chip Fleming, 1999)
  46. David MacKay's Gallager low density parity-check (LDPC) code resources.
  47. An excellent reference for iterative decoding. Papers on Gallager codes. Matrices for codes. Source code for decoding.
    (David MacKay, 1997)
  48. MATLAB routines for LDPC codes over GF(q), q=2^m.
  49. A few MATLAB routines for encoding/decoding low density parity check codes.
    (Igor Kozintsev, 1999)
  50. Perl script for a type-C2 algebraic interleaver.
  51. Generates a sequence of distinct numbers such that the length of the sequence can be any power of 2. A particular characteristic of the generated sequence is that it is symmetric in the sense that an entry j in row i implies that the entry in row j is i. (Interleaver and deinterleaver are identical!)
    (Oscar Takeshita, 1997)
  52. Forward Error Correction (FEC) Page
  53. This site contains some examples of Forward Error Correction (FEC) software and hardware. You will find software and hardware examples for free download, which are available as 'C' source code, VHDL source code or as 'VHDL' code generators for SUN/Solaris.
    (Christian Schuler, 1998. Updated 2001)
  54. A fast and accurate degree distribution optimizer for ldpc code ensembles
  55. The tool ldpcopt was developed in Switzerland, to search for optimized LDPC degree distributions for various channels.
    (Abdelaziz AMRAOUI, 2001.)
  56. Tc_Ds_Analysis.exe 
  57. Windows program to compute the distance spectrum of a turbo code and the union bound on the BER. See the read_me file
    (Seokhyun Yoon, 2002.)


This page was last updated on August 6, 2008. Robert Morelos-Zaragoza