Provided by: libfec-dev_1.0-26-gc5d935f-1_amd64 
NAME
create_viterbi27, set_viterbi27_polynomial, init_viterbi27, update_viterbi27_blk,
chainback_viterbi27, delete_viterbi27, create_viterbi29, set_viterbi_29_polynomial,
init_viterbi29, update_viterbi29_blk, chainback_viterbi29, delete_viterbi29,
create_viterbi39, set_viterbi_39_polynomial, init_viterbi39, update_viterbi39_blk,
chainback_viterbi39, delete_viterbi39, create_viterbi615, set_viterbi615_polynomial,
init_viterbi615, update_viterbi615_blk, chainback_viterbi615, delete_viterbi615 - IA32
SIMD-assisted Viterbi decoders
SYNOPSIS
#include "fec.h"
void *create_viterbi27(int blocklen);
void set_viterbi27_polynomial(int polys[2]);
int init_viterbi27(void *vp,int starting_state);
int update_viterbi27_blk(void *vp,unsigned char syms[],int nbits);
int chainback_viterbi27(void *vp, unsigned char *data,unsigned int nbits,unsigned int endstate);
void delete_viterbi27(void *vp);
void *create_viterbi29(int blocklen);
void set_viterbi29_polynomial(int polys[2]);
int init_viterbi29(void *vp,int starting_state);
int update_viterbi29_blk(void *vp,unsigned char syms[],int nbits);
int chainback_viterbi29(void *vp, unsigned char *data,unsigned int nbits,unsigned int endstate);
void delete_viterbi29(void *vp);
void *create_viterbi39(int blocklen);
void set_viterbi39_polynomial(int polys[3]);
int init_viterbi39(void *vp,int starting_state);
int update_viterbi39_blk(void *vp,unsigned char syms[],int nbits);
int chainback_viterbi39(void *vp, unsigned char *data,unsigned int nbits,unsigned int endstate);
void delete_viterbi39(void *vp);
void *create_viterbi615(int blocklen);
void set_viterbi615_polynomial(int polys[6]);
int init_viterbi615(void *vp,int starting_state);
int update_viterbi615_blk(void *vp,unsigned char syms[],int nbits);
int chainback_viterbi615(void *vp, unsigned char *data,unsigned int nbits,unsigned int endstate);
void delete_viterbi615(void *vp);
DESCRIPTION
These functions implement high performance Viterbi decoders for four convolutional codes:
a rate 1/2 constraint length 7 (k=7) code ("viterbi27"), a rate 1/2 k=9 code
("viterbi29"), a rate 1/3 k=9 code ("viterbi39") and a rate 1/6 k=15 code ("viterbi615").
The decoders use the Intel IA32 or PowerPC SIMD instruction sets, if available, to improve
decoding speed.
On the IA32 there are three different SIMD instruction sets. The first and most common is
MMX, introduced on later Intel Pentiums and then on the Intel Pentium II and most Intel
clones (AMD K6, Transmeta Crusoe, etc). SSE was introduced on the Pentium III and later
implemented in the AMD Athlon 4 (AMD calls it "3D Now! Professional"). Most recently,
SSE2 was introduced in the Intel Pentium 4, and has been adopted by more recent AMD CPUs.
The presence of SSE2 implies the existence of SSE, which in turn implies MMX.
Altivec is the PowerPC SIMD instruction set. It is roughly comparable to SSE2. Altivec was
introduced to the general public in the Apple Macintosh G4; it is also present in the G5.
Altivec is actually a Motorola trademark; Apple calls it "Velocity Engine" and IBM calls
it "VMX". All refer to the same thing.
When built for the IA32 or PPC architectures, the functions automatically use the most
powerful SIMD instruction set available. If no SIMD instructions are available, or if the
library is built for a non-IA32, non-PPC machine, a portable C version is executed
instead.
USAGE
Four versions of each function are provided, one for each code. In the following
discussion, change "viterbi" to "viterbi27", "viterbi29", "viterbi39" or "viterbi615" as
desired.
Before Viterbi decoding can begin, an instance must first be created with
create_viterbi(). This function creates and returns a pointer to an internal control
structure containing the path metrics and the branch decisions. create_viterbi() takes one
argument that gives the length of the data block in bits. You must not attempt to decode a
block longer than the length given to create_viterbi().
Before decoding a new frame, init_viterbi() must be called to reset the decoder state. It
accepts the instance pointer returned by create_viterbi() and the initial starting state
of the convolutional encoder (usually 0). If the initial starting state is unknown or
incorrect, the decoder will still function but the decoded data may be incorrect at the
start of the block.
Blocks of received symbols are processed with calls to update_viterbi_blk(). The nbits
parameter specifies the number of data bits (not channel symbols) represented by the syms
buffer. (For rate 1/2 codes, the number of symbols in syms is twice nbits, and so on.)
Each symbol is expected to range from 0 through 255, with 0 corresponding to a "strong 0"
and 255 corresponding to a "strong 1". The caller is responsible for determining the
proper pairing of input symbols (commonly known as decoder symbol phasing).
At the end of the block, the data is recovered with a call to chainback_viterbi(). The
arguments are the pointer to the decoder instance, a pointer to a user-supplied buffer
into which the decoded data is to be written, the number of data bits (not bytes) that are
to be decoded, and the terminal state of the convolutional encoder at the end of the frame
(usually 0). If the terminal state is incorrect or unknown, the decoded data bits at the
end of the frame may be unreliable. The decoded data is written in big-endian order, i.e.,
the first bit in the frame is written into the high order bit of the first byte in the
buffer. If the frame is not an integral number of bytes long, the low order bits of the
last byte in the frame will be unused.
Note that the decoders assume the use of a tail, i.e., the encoding and transmission of a
sufficient number of padding bits beyond the end of the user data to force the
convolutional encoder into the known terminal state given to chainback_viterbi(). The tail
is always one bit less than the constraint length of the code, so the k=7 code uses 6 tail
bits (12 tail symbols), the k=9 code uses 8 tail bits (16 tail symbols) and the k=15 code
uses 14 tail bits (84 tail symbols).
The tail bits are not included in the length arguments to create_viterbi() and
chainback_viterbi(). For example, if the block contains 1000 user bits, then this would be
the length parameter given to create_viterbi27() and chainback_viterbi27(), and
update_viterbi27_blk() would be called with a total of 2012 symbols - the last 12 encoded
symbols representing the tail bits.
After the call to chainback_viterbi(), the decoder may be reset with a call to
init_viterbi() and another block can be decoded. Alternatively, delete_viterbi() can be
called to free all resources used by the Viterbi decoder.
The set_viterbi_polynomial() function allows use of other than the default code generator
polynomials. Although only one set of polynomials are generally used with each code, there
can are different conventions as to their order and symbol polarity, and these functions
simplifies their use.
The default polynomials for the viterbi27 routes are those of the NASA-JPL convention
without symbol inversion. The NASA-JPL convention normally inverts the first symbol. The
CCSDS/NASA-GSFC convention swaps the two symbols and inverts the second.
To set the NASA-JPL convention with symbol inversion:
int polys[2] = { -V27POLYA,V27POLYB };
set_viterbi27_polynomial(polys);
and to set the CCSDS convention with symbol inversion:
int polys[2] = { V27POLYB,-V27POLYA };
set_viterbi27_polynomial(polys);
The default polynomials for the viterbi615 routines are those used by the Cassini
spacecraft without symbol inversion. Mars Pathfinder (MPF) and STEREO swap the third and
fourth polynomials. Both conventions invert the first, third and fifth symbols. Refer to
fec.h for the polynomial constant definitions.
To set the Cassini convention with symbol inversion, do the following:
int polys[6] = { -V615POLYA,V615POLYB,-V615POLYC,V615POLYD,-V615POLYE,V615POLYF };
set_viterbi615_polynomial(polys);
and to set the MPF/STEREO convention with symbol inversion:
int polys[6] = { -V615POLYA,V615POLYB,-V615POLYD,V615POLYC,-V615POLYE,V615POLYF };
set_viterbi615_polynomial(polys);
For performance reasons, calling this function changes the code generator polynomials for
all instances of corresponding Viterbi decoder, including those already created.
ERROR PERFORMANCE
These decoders have all been extensively tested and found to provide performance
consistent with that expected for soft-decision Viterbi decoding with 8-bit symbols.
Due to internal differences, the implementations vary slightly in error performance. In
general, the portable C versions exhibit the best error performance because they use full-
sized branch metrics, and the MMX versions exhibit the worst because they use 8-bit branch
metrics with modulo comparisons. The SSE, SSE2 and Altivec implementations of the r=1/2
k=7 and r=1/2 k=9 codes use unsigned 8-bit branch metrics, and are almost as good as the C
versions. The r=1/3 k=9 and r=1/6 k=15 codes are implemented with 16-bit path metrics in
all SIMD versions.
DIRECT ACCESS TO SPECIFIC FUNCTION VERSIONS
Calling the functions listed above automatically calls the appropriate version of the
function depending on the CPU type and available SIMD instructions. A particular version
can also be called directly by appending the appropriate suffix to the function name. The
available suffixes are "_mmx", "_sse", "_sse2", "_av" and "_port", for the MMX, SSE, SSE2,
Altivec and portable versions, respectively. For example, the SSE2 version of the
update_viterbi27_blk() function can be invoked as update_viterbi27_blk_sse2().
Naturally, the _av functions are only available on the PowerPC and the _mmx, _sse and
_sse2 versions are only available on IA-32. Calling a SIMD-enabled function on a CPU that
doesn't support the appropriate set of instructions will result in an illegal instruction
exception.
RETURN VALUES
create_viterbi returns a pointer to the structure containing the decoder state. The other
functions return -1 on error, 0 otherwise.
AUTHOR & COPYRIGHT
Phil Karn, KA9Q (karn@ka9q.net)
LICENSE
This software may be used under the terms of the GNU Limited General Public License
(LGPL).
SIMD-VITERBI(3)