Can anyone line out where I can get a step by step algorithm for viterbi decoder?

Question

I have this Viterbi Decoder function code, which is quite lengthy and there are no comments labeling to help, and I want to try to understand it.

So anyone can point me to an easy to understand algorithm?

Anyway, here is the code:

int viterbiDecode( int nBit, float *p_pm, int *p_sp, int *p_bStore, float *p_hd, int TB, int fc, int lc, int startTB) //initiate Viterbi Decoder function
{

int ipLut[4][4]; // intialization

ipLut[0][0] = 0; ipLut[0][1] = 0; ipLut[0][2] = 0; ipLut[0][3] = 0;

ipLut[1][0] = 0; ipLut[1][1] = 0; ipLut[1][2] = 0; ipLut[1][3] = 0;

ipLut[2][0] = 1; ipLut[2][1] = 1; ipLut[2][2] = 0; ipLut[2][3] = 0;

ipLut[3][0] = 0; ipLut[3][1] = 0; ipLut[3][2] = 1; ipLut[3][3] = 1;

int cs, ps,loopII;

float bm[2], pm_n[4];

int err, nErr;

int bHat;

int tt1, tt2;

int tbStCnt;

int decodeStCnt;

nErr = 0;

   if (fc==1)

    {
      bm[0] = *p_pm+*p_hd;
      *(p_sp+nBit*4+0) = 0;
      pm_n[0] = bm[0];

      bm[0] = *(p_pm+2)+*(p_hd+2);
      *(p_sp+nBit*4+1) = 2;
      pm_n[1] = bm[0];

      bm[0] = *p_pm + *(p_hd+3);
      *(p_sp+nBit*4+2) = 0;
      pm_n[2] = bm[0];

      bm[0] = *(p_pm+2)+ *(p_hd+1);
      *(p_sp+nBit*4+3) = 2;
      pm_n[3] = bm[0];

    } else {

      bm[0] = *p_pm + *p_hd;
      bm[1] = *(p_pm+1) + *(p_hd+3);
      *(p_sp+nBit*4+0) = (bm[0] < bm[1])? 0:1;
      pm_n[0] = bm[(*(p_sp+nBit*4+0))];

      bm[0] = *(p_pm+2) + *(p_hd+2);
      bm[1] = *(p_pm+3) + *(p_hd+1);
      *(p_sp+nBit*4+1) = (bm[0]<bm[1])? 2:3;
      pm_n[1] = bm[(*(p_sp+nBit*4+1))-2];

      bm[0] = *p_pm + *(p_hd+3);
      bm[1] = *(p_pm+1) + *p_hd;
      *(p_sp+nBit*4+2) = (bm[0]<bm[1])? 0:1;
      pm_n[2] = bm[(*(p_sp+nBit*4+2))];

      bm[0] = *(p_pm+2) + *(p_hd+1);
      bm[1] = *(p_pm+3) + *(p_hd+2);
      *(p_sp+nBit*4+3) = (bm[0]<bm[1])? 2:3;
      pm_n[3] = bm[(*(p_sp+nBit*4+3))-2];

     }
    *p_pm = pm_n[0];
    *(p_pm+1) = pm_n[1];
    *(p_pm+2) = pm_n[2];
    *(p_pm+3) = pm_n[3];

    // trace back

    if ( (startTB==1) || (lc ==1)  )
       {
          tt1 = (pm_n[0] < pm_n[1])? 0: 1;
          tt2 = (pm_n[2] < pm_n[3])? 2: 3;
          if (pm_n[tt1] < pm_n[tt2]) {
                 cs = tt1;
          }
          else{
               cs = tt2;
          }

          tbStCnt     = nBit;
          decodeStCnt = tbStCnt-TB;
          if (lc ==1)
             {
             cs = 0;
             decodeStCnt = tbStCnt-2;
             }


          for (loopII=tbStCnt;loopII>=0;loopII--)
          {
             ps = *(p_sp + 4*loopII + cs);

             /* counting the errors */
             if (loopII<decodeStCnt)
             {
                bHat = ipLut[cs][ps];
                err =  (bHat == *(p_bStore+loopII))? 0:1;
                nErr = nErr+ err;
             }
             cs = ps;

           }

        }

return nErr;

}

Answer 1

Google ? Viterbi algorithm

Answer 2

Tip : It is almost exactly the 'Dijkstra algorithm' to find the shortest path into pondered graph.

Of course if you don't know Dijkstra algorithm either you could try Wikipedia.