turbo_enc.c

3GPP WCDMA turbo encoder 3GPP WCDMA turbo encoder 3GPP WCDMA turbo encoder 3GPP WCDMA turbo encod

#include <stdio.h>
#include <math.h>
#include "turbo_enc.h"


/* turbo internal interleaver memory */
static short til_mem[TURBO_MAX_TRCH_BLK_LEN];


/* memory to hold permutation pattern */
static int   U[TURBO_MAX_ROW][TURBO_MAX_COL]; 


/* prime number table */
static const int prime_num[82] = {          /*  index  */
     1,  2,  3,  5,  7, 11, 13,             /*  0 -  6 */
    17, 19, 23, 29, 31, 37, 41, 43, 47, 53, /*  7 - 16 */
    59, 61, 67, 71, 73, 79, 83, 89, 97,101, /* 17 - 26 */
   103,107,109,113,127,131,137,139,149,151, /* 27 - 36 */
   157,163,167,173,179,181,191,193,197,199, /* 37 - 46 */
   211,223,227,229,233,239,241,251,257,263, /* 47 - 56 */
   269,271,277,281,283,293,307,311,313,317, /* 57 - 66 */
   331,337,347,349,353,359,367,373,379,383, /* 67 - 76 */
   389,397,401,409,  0                      /* 77 - 81 */
};


/* primitive root table */
static const int prim_root[82] = {          /*  index  */
     0,  0,  0,  0,  3,  2,  2,             /*  0 -  6 */
     3,  2,  5,  2,  3,  2,  6,  3,  5,  2, /*  7 - 16 */
     2,  2,  2,  7,  5,  3,  2,  3,  5,  2, /* 17 - 26 */
     5,  2,  6,  3,  3,  2,  3,  2,  2,  6, /* 27 - 36 */
     5,  2,  5,  2,  2,  2, 19,  5,  2,  3, /* 37 - 46 */
     2,  3,  2,  6,  3,  7,  7,  6,  3,  5, /* 47 - 56 */
     2,  6,  5,  3,  3,  2,  5, 17, 10,  2, /* 57 - 66 */
     3, 10,  2,  2,  3,  7,  6,  2,  2,  5, /* 67 - 76 */
     2,  5,  3, 21,  0                      /* 77 - 81 */
};


/* inter-row permutation patterns */
static const int T[4][TURBO_MAX_ROW] = {
    { 4, 3, 2, 1, 0,-1,-1,-1,-1,-1, 
     -1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, /* Pattern A */
    { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 
     -1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, /* Pattern B */
    {19, 9,14, 4, 0, 2, 5, 7,12,18,
     16,13,17,15, 3, 1, 6,11, 8,10}, /* Pattern C */
    {19, 9,14, 4, 0, 2, 5, 7,12,18,
     10, 8,13,17, 3, 1,16, 6,15,11}  /* Pattern D */
};


/* 3GPP turbo internal interleaver/de-interleaver */
static void til_3gpp
(
    short   il_sel,     /* interleave/de-interleave selection(0=interleave)*/
    long    length,     /* Trch block length */
    short   *input,     /* points to input buffer */
    short   *output     /* points to output buffer */
)
{
    int     R;          /* number of rows */
    int     C;          /* number of columns */
    int     p;          /* prime number */
    int     p_idx;
    int     v;          /* primitive root associate with p */

    int     i;
    int     j;
    int     inter_type;
    int     temp;
    int     pos;
    int     s[TURBO_MAX_COL];       /* base sequence */
    int     q[TURBO_MAX_ROW];       /* minimum prime integer set */
    int     r[TURBO_MAX_ROW];       /* inter-row permuted q sequence */
  
    
    /* Determine number of rows */
    if (length<=159)
    {
        R = 5;
    }
    else if ((length>=160 && length<=200) || 
             (length>=481 && length<=530))
    {
        R = 10;
    }
    else
    {
        R = TURBO_MAX_ROW;
    }

    /* Determine prime number to be used in intra-permutation 
     * Determine number of columns of interleaver block */
    if (length>=481 && length<=530)
    {
        p = 53;
        C = p;
    }
    else
    {
        /********** (i) **********/
        p_idx = 4;     /* p = 7 */
        while (R * (prime_num[p_idx]+1) < length)
        {
            p_idx++;
        }
        p = prime_num[p_idx];
        v = prim_root[p_idx];

        /********** (ii) **********/
        if (length <= R * (p-1))
        {
            C = p - 1;
        }
        else if (length <= R * p)
        {
            C = p;
        }
        else
        {
            C = p + 1;
        }
    }

    /* ii) Construct base sequence s[j] */
    s[0] = 1;
    for (j=1; j<=p-2; j++)
    {
        s[j] = (v * s[j-1]) % p;
    }

    /* iii) Select the minimum prime integer set {qj} */
    q[0] = 1;

    j = 1;
    p_idx = 4;      /* prime_num[4] > 6 */
    while (j < R)
    {
        if(((p-1) % prime_num[p_idx]) != 0)
        {
            q[j++] = prime_num[p_idx];
        }
        p_idx ++;
    }

    /* iv) permute the sequence q[j] according to inter-row 
     *     permutation patterns */
    if (length <= 159)
    {
        inter_type = 0;
    }
    else if ((length>=160 && length<=200)||(length>=481 && length<=530))
    {
        inter_type = 1;
    }
    else if ((length>=2281 && length<=2480)||(length >= 3161 && length<=3210))
    {
        inter_type = 2;
    }
    else 
    {
        inter_type = 3;
    }

    for(j = 0; j < R; j++)
    {
        r[T[inter_type][j]] = q[j];
    }
    
    /* v) determine intra-row permutation pattern */
    if ( C == p )
    {
        for (i = 0; i < R; i++)
        {
            for (j = 0; j <= p - 2; j++)
            {
                U[i][j] = s[(j * r[i]) % (p - 1)];
            }
            U[i][p - 1] = 0;
        }
    }
    else if ( C == p+1 )
    {
        for (i = 0; i < R; i++)
        {
            for (j = 0; j <= p - 2; j++)
            {
                U[i][j] = s[(j * r[i]) % (p - 1)];
            }
            U[i][p - 1] = 0;
            U[i][p] = p;
        }
        if (length == R * C)
        {
            temp = U[R-1][p];
            U[R-1][p] = U[R-1][0];
            U[R-1][0] = temp;
        }
    }
    else /* C == p-1 */
    {
        for (i = 0; i < R; i++)
        {
            for (j = 0; j <= p - 2; j++)
            {
                U[i][j] = s[(j * r[i]) % (p - 1)] - 1;
            }
        }
    }

    /* vi) perform intra-row and inter-row permutation;
     *     execute interleaving */
    for (j = 0; j < C; j++)
    {
        for (i = 0; i < R; i++)
        {
            pos = T[inter_type][i] * C + U[T[inter_type][i]][j];
            if (pos < length)
            {
                if (il_sel == 0)
                {
                    *output++ = input[pos]; /* interleaving */
                }
                else
                {
                    output[pos] = *input++; /* de-interleaving */
                }
            }
        }
    }
    
}


/* 3GPP turbo encoder */
int turbo_enc
(
    long    length,
    short   *input,
    short   *output
)
{
    long    i;

    short   reg1;
    short   reg2;

    short   tail_bit;
    
    if (length==0) 
    {
        return 0;
    }

    /* turbo code internal interleaving */
    til_3gpp(0, length, input, til_mem);

    /* Macro definition for rolling the RSC shift registers */
    #define ROLL_REG(regx, in_bit)  \
            ((regx)=((regx)<<1)|(((in_bit) ^ ((regx)>>1) ^ ((regx)>>2))&1))

    /* initialize RSC shift register */
    reg1 = 0;
    reg2 = 0;
    
    for (i=0; i<length; i++)
    {
        /* 
         * output systematic bit 
         */
        *output++ = input[i]&1;

        /*
         * output RSC1 parity bit 
         */
        *output++ = (input[i] ^ (reg1>>1) ^ reg1)&1;
        ROLL_REG(reg1,input[i]);
        
        /*
         * output RSC2 parity bit 
         */
        *output++ = (til_mem[i] ^ (reg2>>1) ^ reg2)&1;
        ROLL_REG(reg2,til_mem[i]);
    }
    
    /*
     * RSC1 and RSC2: number of total tail bits = 12
     * RSC1 trellis termination  
     */
    for (i=0; i<3; i++)
    {
        tail_bit = ((reg1>>1) ^ (reg1>>2))&1;
        *output++ = tail_bit;
        *output++ = (tail_bit ^ (reg1>>1) ^ reg1)&1;
        ROLL_REG(reg1,tail_bit);
    }

    /*
     * RSC2 trellis termination 
     */
    for (i=0; i<3; i++)
    {
        tail_bit = ((reg2>>1) ^ (reg2>>2))&1;
        *output++ = tail_bit;
        *output++ = (tail_bit ^ (reg2>>1) ^ reg2)&1;
        ROLL_REG(reg2,tail_bit);
    }

    return 0;
}