Convolutional Error Codes
by Hugo Lyppens



Listing One
template<int N_IN, int K_IN, int CL_IN, int NMSGGRPSYMBOLS_IN>
void
ConvolutionalCodec<N_IN, K_IN, CL_IN, NMSGGRPSYMBOLS_IN>::encode(
    const UBYTE * const  message,
    UBYTE *         encoded,
    ULONG           len ) const
{
    ULONG            state         = 0;
    int              messageBitPos = 0;
    int              encodedBitPos = 0;
    const int        msgbits       = len*BITSPERBYTE;
    const UBYTE      *messagePtr   = message;

    memset( encoded, 0, getEncodedLength( len ));

    // read NMSGGRPBITS at a time but avoid reading past end of message by
    // ensuring there are at least this many bits remaining
    while( messageBitPos < msgbits-(NMSGGRPBITS-1) )
    {
        ULONG   inbits  = getMsgGroupBits( messagePtr, messageBitPos );
        ULONG       outbits = encodingTable[ inbits ][ state ].bits;
        if( NSTATEBITS > NMSGGRPBITS )
           state = ((state>>NMSGGRPBITS)|(inbits<<(NSTATEBITS-NMSGGRPBITS)));
        else
            state = inbits >> (NMSGGRPBITS-NSTATEBITS);
        writeEncodedGroupBits( encoded, encodedBitPos, outbits );
    }
    // read remaining bits if the preceding loop did not process all the bits
    // this happens if the number of message bits is not a multiple of the
    // number of bits per symbol.
    if( messageBitPos < msgbits )
    {
        ULONG  inbits=(*(messagePtr+(messageBitPos >> 3)) >>
                                (messageBitPos&7)) & ((1<<NMSGGRPBITS)-1);
        ULONG  outbits = encodingTable[ inbits ][ state ].bits;
        if( NSTATEBITS > NMSGGRPBITS )
            state = ((state >> NMSGGRPBITS) | (inbits << 
                               (NSTATEBITS-NMSGGRPBITS)));
        else
            state = inbits >> (NMSGGRPBITS-NSTATEBITS);
        writeEncodedGroupBits( encoded, encodedBitPos, outbits );
    }
    // return encoder back to all-zero state
    while( state )
    {
        ULONG  outbits = encodingTable[ 0 ][ state ].bits;
        state >>= NMSGGRPBITS;
        writeEncodedGroupBits( encoded, encodedBitPos, outbits );
    }
}

Listing Two
template<int N_IN, int K_IN, int CL_IN, int NMSGGRPSYMBOLS_IN>
void
ConvolutionalCodec<N_IN, K_IN, CL_IN, NMSGGRPSYMBOLS_IN>::decode(
    const UBYTE     *encoded,
    UBYTE           *decoded,
    ULONG           len ) const
{
    ULONG           pathDistance[2][ NSTATES ];
    ULONG           *oldPathDist;
    ULONG           *newPathDist;

    UBYTE           trellis[ TAU ][ NSTATES ];

    ULONG           trans, state;
    ULONG           minStatePathDist;

    newPathDist = &pathDistance[0][0];
    oldPathDist = &pathDistance[1][0];

    // Comments refer to algorithm steps in Figure 6
    // Step 1
    newPathDist[ 0 ] = 0;
    for( state = 1; state < NSTATES; state++ )
    {
        newPathDist[state] = ~0;
    }
    const  ULONG  nmsgsymbols   = (len*BITSPERBYTE+K-1)/K;
    const  UBYTE  *encodedPtr   = encoded;
    int           encodedBitPos = 0;
    UBYTE         *decodedPtr   = decoded;
    int           decodedBitPos = 0;

    memset( decoded, 0, len );
    // Step 2
    for( ULONG t = 0; t<nmsgsymbols+TAU; t++ )
    {
        ULONG        trelliscol  = t % TAU;
        UBYTE       *trelliscolp = &trellis[ trelliscol ][ 0 ];

        ULONG       encbits = 0;
        if(t < nmsgsymbols + M)
            encbits = getEncodedSymbolBits( encodedPtr, encodedBitPos );
      ULONG *tmp = newPathDist; newPathDist = oldPathDist; oldPathDist = tmp;
        // Step 3
        minStatePathDist = ~0;
        ULONG  bestState = ~0;
        // Step 5-13
        for( state = 0; state < NSTATES; state++ )
        {
            ULONG mind = ~0U;
            UBYTE minprev = ~0;
            // Steps 7-10
            for( ULONG prev = 0; prev < (1<<K); prev++ )
            {
                const ULONG oldState = ((state << K) | prev) & STATEMASK;
                const ULONG trans    = state >> (NSTATEBITS-K);
                ULONG sd = oldPathDist[oldState];
                if( ~sd ) // test whether sd != ~0
                {
                    // Step 8
                   sd += UBYTEWeight[getTransition(trans,oldState)^encbits ];
                    if( sd < mind )
                    {
                        mind = sd; minprev = prev;
                    }
                }
            }
            newPathDist[ state ] = mind;
            trelliscolp[ state ] = minprev;
            if( mind < minStatePathDist )
            {
                minStatePathDist = mind;
                bestState        = state;
            }
            ULONG os = (((state << K) | minprev) & STATEMASK);
        }
        // Steps 15-23
        if( t >= TAU )
        {
            UBYTE *tp;
            UBYTE * const tpe = &trellis[trelliscol][0];
            // Step 17
            state = bestState;
            // Steps 18-21. Divided over 2 loops because the trellis
            // is represented in the trellis array from
            // (t-(TAU-1)) modulo TAU through t modulo TAU.
            for( tp = tpe; tp >= &trellis[0][0]; tp-=NSTATES )
            {
                state = ((state << K) | tp[ state ]) & STATEMASK;
            }
            for( tp = &trellis[TAU-1][0]; tp > tpe; tp-=NSTATES )
            {
                state = ((state << K) | tp[ state ]) & STATEMASK;
            }
            UBYTE dec = state >> (NSTATEBITS-K);
            // Step 23
            writeDecodedSymbolBits( decodedPtr, decodedBitPos, dec);
        }
    }
}

Listing Three
static const ULONG figure2 [ 3 ][ 2 ] =
    {
        { 3, 0 }, // = 110, 000 where leftmost is least significant bit
        { 1, 3 }, // = 100, 110
        { 0, 7 }  // = 000, 111
    };
    ConvolutionalCodec<3,2,3,1> codec(figure2);
    char        decoded[4];
    char        *encoded = new char[ codec.getEncodedLength(4) ];
    cout << "Minimum free distance: " << codec.getMinFreeDistance() << endl;
    codec.encode("test", encoded, 4);
    codec.decode(encoded, decoded, 4);
    delete[] encoded;



4


