The Error Correcting Codes (ECC) Page

Established in 1996

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. Some of these programs I have found over the years (since 1988), while I was a Ph.D. student in Hawaii. Other programs were either "hacked" or authored by me.

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!

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 applications of ECC and possibly to offer my advice. Implementations of algorithms for ECC in C/C++, to be shared with the world, can be emailed to me. Pointers to them are added in this page on a regular basis.

I recommend the following 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, Prentice Hall: Englewood Cliffs, NJ, 1983.

  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.

I also recommend my new book, for a gentle hands-on introduction to the basic principles and applications of error correcting codes:


As of May 16, 2002, the ECC page has a new permanent home, after many years living in exile. I welcome your comments and suggestions on how to improve the presentation and content of this page. Have fun!

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


PROGRAMS

  1. The Ubiquitous Reed-Solomon Codes
    2. by Barry A. Cipra, Reprinted from SIAM News, Volume 26-1, January 1993
  2. Reed-Solomon (RS) codes
    3. Decoding the Berlekamp-Masssey (BM) algorithm, with error evaluation as explained in Lin and Costello's book.
    (Simon Rockliff, 1989)
  3. Reed-Solomon errors-and-erasures decoder
    4. 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)
  4. Another Reed-Solomon errors-and-erasures decoder
    5. 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, 2002).
  5. BCH codes
    6. 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).
  6. Binary (48,36,5) BCH code.
    7. 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).
  7. Binary (31,21,5) BCH code.
    8. 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).
  8. Golay (23,12,7) code
    9. 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).
  9. A Goppa code
    10. 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)
  10. CRC-32
    11. Computes the CRC value of a file, as used in ZMODEM or PKZIP.
    (Craig Bruce, 1994)
  11. ecc-1.2.1.tar (106496 bytes)
    12. Routines to encode and decode a file using a (255,249,7) RS code.
    (Paul Flaherty, 1993)
  12. Turbo-codes home page at JPL
  13. TURBO decoder archive: BCJR_turbo.tar
    14. An implementation of the BCJR algorithm, based on the pseudocode in W.E.Ryan's tutorial paper (PS file).
    (Mathys Walma, 1998)
  14. Viterbi decoding
    15. 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, 2002)
  15. galois.tar
    16. Encoding/decoding for BCH/RS codes.
    (Bart De Canne, 1994)
  16. Simulate a BCH, Reed-Solomon or Reed-Muller Code on the Web!
    17. This one comes from The Netherlands. It needs some work, but it is nice if, say, you need to know the generator polynomial of a BCH or RS code, without programming/compiling, etc.
    (Richie B, 1996)
  17. A block coded QPSK modulation for unequal error protection (UEP)
    18. 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)
  18. Linear code bound
    19. 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)
  19. Erasure-correcting codes
    20. 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)
  20. Finite Field Calculator and Reed-Solomon Simulator
    21. Java applet of GF calculator and an RS encoder/decoder
    (Emina Soljanin, 1997)
  21. A Windows 95/NT program to do Galois Field math
    22. (Andrew Lin, 1997)
  22. Properties of binary linear codes
    23. 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)
  23. Maximal LFSR program
    24. A program to find primitive polynomials of maximum cycle length
    (Steve Ungstad, 1999)
  24. A Tutorial on Convolutional Coding with Viterbi Decoding
    25. 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)
  25. David MacKay's Gallager low density parity-check (LDPC) code resources.
    26. An excellent reference for iterative decoding. Papers on Gallager codes. Matrices for codes. Source code for decoding.
    (David MacKay, 1997)
  26. MATLAB routines for LDPC codes over GF(q), q=2^m.
    27. A few MATLAB routines for encoding/decoding low density parity check codes.
    (Igor Kozintsev, 1999)
  27. Perl script for a type-C2 algebraic interleaver.
    28. 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)
  28. Computing algebraic codes.
    29. Compute code parameters for "small" linear Binary Algebraic codes and their extensions. Written in java, it lets you compute the minimum distance of a code given its length, dimension and generator matrix. It also computes other parameters of interest, such as its covering radius and trellis state complexity.
    (trachten@uiuc.edu, 1999)
  29. Irregular Low-Density Parity-Check (LDPC) code design
    30. This is a demo version of the irregular low-density parity-check (LDPC) code optimizer for additive white Gaussian noise (AWGN) channel with binary antipodal signaling. This program does the optimization for a given rate and complexity assuming 1) infinite block length, 2) random interleaver and 3) Gaussian approximation (GA) for message densities.
    (sychung@alum.mit.edu, 2001)
  30. Forward Error Correction (FEC) Page
    31. 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)
  31. A fast and accurate degree distribution optimizer for ldpc code ensembles
    32. The tool ldpcopt was developed in Switzerland, to search for optimized LDPC degree distributions for various channels.
    (Abdelaziz AMRAOUI, 2001.)
  32. Tc_Ds_Analysis.exe 
    33. 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.)


LINKS (in alphabetical order)

Adrian Barbulescu's book on turbo codes
Coding Research Group, U. Notre Dame
Efficient Channel Coding, Inc.
Flarion's LDPC IP core is a scalable and programmable architecture for LDPC encoding and decoding
4i2i
iCODING Technology, Inc.
International Page on Error Control Coding
IT++ is a library of mathematical, signal processing and communication system routines/functions
J. Bierbrauer's home page
LSI LOGIC Corp.
Onion Networks' Java FEC library with file I/O routines
PCS, Ltd
Small World Communications
SourceForge: RS decoder
TurboConcept
UHM Coding Group of Prof. Marc Fossorier
USA Turbo Code page

This page was last updated on February 1, 2004. Robert Morelos-Zaragoza.