viterbi-readme.txt

一些纠错编码算法的源代码

KA9Q Viterbi decoder V3.0
Copyright 1999 Phil Karn, KA9Q
May be used under the terms of the GNU Public License

This package provides encoders and fast Viterbi decoders for the NASA
standard rate 1/2 and rate 1/3 constraint length 7 convolutional codes.

Two versions of these encoder and decoder are provided, one for
blocked data (with user specified initial and terminal encoder states)
and another for continuous streams. The former is a C subroutine, the
latter runs as a UNIX pipeline filter, closely emulating commercially
available hardware Viterbi decoders.

Another encoder and Viterbi decoder is also provided for an arbitrary
blocked convolutional code. This version attains generality at the
expense of performance. It has been tested with the Mars Pathfinder
r=1/6 K=15 code. It's slow, but it works. (389 bps on a 166MHz
Ultrasparc, 655 bps on a 400 MHz Pentium-II.) Of course, it's *much*
faster on shorter codes, though it's not as fast on the k=7 codes as
the decoders optimized for them.

An experimental Perl script is also provided that generates a
optimized blocked encoder and Viterbi decoder in C for an arbitrary
convolutional code. As this script uses agressive loop unrolling, it
should not be used for large constraint lengths.

Also included are support routines to generate metric tables that are
optimized for gaussian noise with a specified Eb/N0 ratio, and a test
driver that exercises the encoder/decoder routines and keeps statistics.

The following files are included:

Makefile	
README		this file
viterbi27.h	header file for rate 1/2 K=7 code
viterbi37.h	header file for rate 1/3 K=7 code

encode27.c	stream encoder for rate 1/2 K=7 code
encode37.c	stream encoder for rate 1/3 K=7 code

vitfilt27.c	stream decoder for rate 1/2 K=7 code
vitfilt37.c	stream decoder for rate 1/3 K=7 code

viterbi27.c	block encoder/decoder for rate 1/2 K=7 code
viterbi37.c	block encoder/decoder for rate 1/3 K=7 code

viterbi.c	block encoder/decoder for arbitrary code
genviterbi.pl	perl script for generating encoder/decoders

vittest.c	driver program for testing the subroutine versions
metrics.c	generate soft-decision metrics for AWGN channel
sim.c		transmitter/channel simulator (including gaussian noise gen)
tab.c		lookup table for parity generation

The stream mode encoder and decoder may be demonstrated as follows:

$ encode27 < input_file | vitfilt27	(rate 1/2 code)
$ encode37 < input_file | vitfilt37	(rate 1/3 code)

The test program in vittest.c creates a test frame, encodes it, adds
gaussian noise and decodes it with the blocked version of the Viterbi
decoder. It then repeats a specified number of times, keeping count of
bit errors and errored frames (frames with at least one error).

The files sim.c and metrics.c are also in my Fano decoder package. See
the readme for that package for further comments on these two files,
including math library performance issues for the gaussian random
number generator in sim.c.

Unlike a sequential decoder, a Viterbi decoder runs at a constant
speed regardless of Eb/N0 ratio. It is also more tolerant of metric
table inaccuracies.

The blocked version of the k=7 r=1/2 decoder when compiled with gcc
version 2.7.2.3 and the -O9 flag runs at about 757 kilobits/sec on a
400 MHz Pentium-II under Linux 2.2.7.  Although the code should be
portable, it is very heavily optimized for 32-bit machines and will
probably perform poorly on machines with smaller words.

Phil Karn
March 18, 1995 (version 1.0)

August 5, 1995 (version 1.1)
Changes for version 1.1:
 improved butterfly performance (thanks to N6NKF)
 fixed bug in computation of esn0; changed calling convention to gen_met()

October 17, 1996 (version 2.0)
Changes for version 2.0:
 Switched decoder from register exchange mode to traceback mode
 Continued performance tuning (about 50% faster than version 1.1)
 Added stream-mode decoder as alternative to existing packet-mode decoder

October 27, 1997 (version 2.1)
Changes for version 2.1:
 Added rate 1/3 K=7 encoder/decoder in both stream and block mode
 Added general purpose blocked mode encoder/decoder
 Added perl script for blocked mode encoder/decoder generation
 Stream decoders now normalize metrics periodically to prevent overflow
 Fixed fencepost problem in vittest.c.

May 11, 1999 (version 3.0):
 Updated timings for a more modern CPU (400 MHz PII vs 133 MHz Pentium!)
 Support for non-zero starting and ending states ("pinned state" decoding):
 Added startstate and endstate args to blocked mode decoder param lists
 Fixed logic in tail decoding to handle non-zero tails
 NB: additional two args (start and end state) to the convolutional encoder
 and Viterbi decoder routines