The Error Correcting Codes (ECC) Page
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!
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:
Copyright (c) 1996-2008. Robert Morelos-Zaragoza. All
by Barry A. Cipra, Reprinted from SIAM News, Volume 26-1, January 1993
Decoding the Berlekamp-Masssey (BM) algorithm, with error evaluation as explained in Lin and Costello's book.
(Simon Rockliff, 1989)
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.
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).
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.
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.
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.
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.
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)
Computes the CRC value of a file, as used in ZMODEM or PKZIP.
(Craig Bruce, 1994)
Routines to encode and decode a file using a (255,249,7) RS code.
(Paul Flaherty, 1993)
An implementation of the BCJR algorithm, based on the pseudocode in W.E.Ryan's tutorial paper (PS file).
(Mathys Walma, 1998)
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)
Encoding/decoding for BCH/RS codes.
(Bart De Canne, 1994)
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.
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! (firstname.lastname@example.org, 1995). Also try: http://www.codetables.de/ maintained by Markus Grassl (Thanks to Axel Kohnert for the pointer).
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)
Java applet of GF calculator and an RS encoder/decoder
(Emina Soljanin, 1997)
(Andrew Lin, 1997)
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)
A program to find primitive polynomials of maximum cycle length
(Steve Ungstad, 1999)
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)
An excellent reference for iterative decoding. Papers on Gallager codes. Matrices for codes. Source code for decoding.
(David MacKay, 1997)
A few MATLAB routines for encoding/decoding low density parity check codes.
(Igor Kozintsev, 1999)
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)
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)
The tool ldpcopt was developed in Switzerland, to search for optimized LDPC degree distributions for various channels.
(Abdelaziz AMRAOUI, 2001.)
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.)