GNU Radio Viterbi Implementation

[Moses Browne Mwakyanjala]

Hello everyone,

I have a couple of questions on GNU Radio implementation of the Butterfly macros. I'm somehow familiar with doing butterfly on paper (the trellis) but could someone explain to me how this macro works? I also don't understand how the list of butterflies for a specific code (for example the CCSDS CC(K= 7, R = 1/2) butterflies generated by the program below the butterfly macro) are generated (in particular, how to derive the partab lookup).

Regards,

#define BUTTERFLY(i, sym)                                         \

    {                                                             \

        int m0, m1;                                               \

                                                                  \

        /* ACS for 0 branch */                                    \

        m0 = state[i].metric + mets[sym];          /* 2*i */      \

        m1 = state[i + 32].metric + mets[3 ^ sym]; /* 2*i + 64 */ \

        if (m0 > m1) {                                            \

            next[2 * i].metric = m0;                              \

            next[2 * i].path = state[i].path << 1;                \

        } else {                                                  \

            next[2 * i].metric = m1;                              \

            next[2 * i].path = (state[i + 32].path << 1) | 1;     \

        }                                                         \

        /* ACS for 1 branch */                                    \

        m0 = state[i].metric + mets[3 ^ sym];  /* 2*i + 1 */      \

        m1 = state[i + 32].metric + mets[sym]; /* 2*i + 65 */     \

        if (m0 > m1) {                                            \

            next[2 * i + 1].metric = m0;                          \

            next[2 * i + 1].path = state[i].path << 1;            \

        } else {                                                  \

            next[2 * i + 1].metric = m1;                          \

            next[2 * i + 1].path = (state[i + 32].path << 1) | 1; \

        }                                                         \

    }

/* Generate the inline BUTTERFLY macro calls for viterbi.c */

/* The two generator polynomials for the NASA Standard K=7 code */  

#include <stdio.h>

#define POLYA   0x4f

#define POLYB   0x6d  

unsigned char Partab[] = {

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

 0, 1, 1, 0, 1, 0, 0, 1,

 0, 1, 1, 0, 1, 0, 0, 1,

 1, 0, 0, 1, 0, 1, 1, 0,

};

 

int main(int argc, char *argv[])  

{  

int e,i;

int nNonInv = 1;

for(i=0;i<32;i++){  

if(nNonInv) {

e = Partab[2*i & POLYA] << 1;  

e |= Partab[2*i & POLYB];  

}

else {

// CCSDS Poly V27POLYB, -V27POLYA

e = Partab[2*i & POLYA] << 1;  

e |= 1^Partab[2*i & POLYB];  

}

printf("BUTTERFLY(%d,%d); ",i,e);

if (i % 4 ==3) {

printf("\n");

}  

}  

return 0;

}