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:
S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall: Englewood Cliffs, NJ, 1983.
W.W. Peterson and E.J. Weldon, Jr., Error-Correcting Codes, 2nd edition, MIT Press: Cambridge, Mass., 1972.
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
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.
(Thirumoorthy, 1995)
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).
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).
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).
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).
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).
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, 2002)
Encoding/decoding for BCH/RS codes.
(Bart De Canne, 1994)
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)
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)
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)
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)
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)
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)
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.)
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