/* This file is part of wsprd. File name: fano.c Description: Soft decision Fano sequential decoder for K=32 r=1/2 convolutional code. Copyright 1994, Phil Karn, KA9Q Minor modifications by Joe Taylor, K1JT */ #define LL 1 // Select Layland-Lushbaugh code //#define debug 1 #include #include #include #include #include "fano.h" struct node { unsigned long encstate; // State enkoder untuk node berikutnya long gamma; // Nilai metrik path sekarang int metrics[4]; // Empat pilihan metrik int tm[2]; // Dipilah hanya dua...?? tm[i], i=0 atau 1 // best branch tm[0] dan second best branch tm[1] saja int i; // Terpilih satu branch }; // Convolutional coding polynomials. All are rate 1/2, K=32 #ifdef NASA_STANDARD /* "NASA standard" code by Massey & Costello * Nonsystematic, quick look-in, dmin=11, dfree=23 * used on Pioneer 10-12, Helios A,B */ #define POLY1 0xbbef6bb7 #define POLY2 0xbbef6bb5 #endif #ifdef MJ /* Massey-Johannesson code * Nonsystematic, quick look-in, dmin=13, dfree>=23 * Purported to be more computationally efficient than Massey-Costello */ #define POLY1 0xb840a20f #define POLY2 0xb840a20d #endif #ifdef LL /* Layland-Lushbaugh code * Nonsystematic, non-quick look-in, dmin=?, dfree=? */ #define POLY1 0xf2d05351 #define POLY2 0xe4613c47 #endif /* yang dipakai adalah polinomial LL */ /* Convolutionally encode a packet. The input data bytes are read * high bit first and the encoded packet is written into 'symbols', * one symbol per byte. The first symbol is generated from POLY1, * the second from POLY2. * * Storing only one symbol per byte uses more space, but it is faster * and easier than trying to pack them more compactly. */ int encode( unsigned char *symbols, // Output buffer, 2*nbytes*8 unsigned char *data, // Input buffer, nbytes unsigned int nbytes) // Number of bytes in data { unsigned long encstate; int sym; int i; /* konversi satu bit data menjadi satu byte data --> untuk memudahkan proses */ encstate = 0; printf("nbytes= %d\n",nbytes); getchar(); while(nbytes-- != 0) { for(i=7;i>=0;i--) { encstate = (encstate << 1) | ((*data >> i) & 1); ENCODE(sym,encstate); *symbols++ = sym >> 1; *symbols++ = sym & 1; } data++; } return 0; } /* Decode packet with the Fano algorithm. * Return 0 on success, -1 on timeout */ int fano( unsigned int *metric, // Final path metric (returned value) unsigned int *cycles, // Cycle count (returned value) unsigned int *maxnp, // Progress before timeout (returned value) unsigned char *data, // Decoded output data unsigned char *symbols, // Raw deinterleaved input symbols unsigned int nbits, // Number of output bits = 81 int mettab[2][256], // Metric table, [sent sym][rx symbol] int delta, // Threshold adjust parameter unsigned int maxcycles, unsigned int *upaya) // Decoding timeout in cycles per bit { struct node *nodes; // First node struct node *np; // Current node struct node *lastnode; // Last node struct node *tail; // First node of tail int t; // Threshold int m0,m1; int ngamma; unsigned int lsym; unsigned int i; if((nodes = (struct node *)malloc((nbits+1)*sizeof(struct node))) == NULL) { printf("malloc failed\n"); return 0; } lastnode = &nodes[nbits-1]; tail = &nodes[nbits-31]; *maxnp = 0; /* int symbols0,symbols1,titik=0; printf("\n\n"); for(i=0;i<162;i+=2){ symbols0=(int)symbols[i];symbols1=(int)symbols[i+1]; if(i<5)printf("[%d, %d, %d] ",titik, symbols0, symbols1); else{ if(i%5==0)printf("\n"); printf("[%d, %d, %d] ",titik, symbols0, symbols1); } titik++; } printf("\n\n"); getchar(); */ /* Menghitung semua kemungkinan metrik branch untuk masing-masing pasangan simbol */ /* Ini adalah tempat satu-satunya kita masih dapat melihat simbol input asli/mentah */ i=0; for(np=nodes;np <= lastnode;np++) { np->metrics[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]]; np->metrics[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]]; np->metrics[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]]; np->metrics[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]]; if(i<3)printf("[%d, %d, %d, %d, %d] ",i,np->metrics[0],np->metrics[1],np->metrics[2],np->metrics[3]); else{ if(i%3==0)printf("\n"); printf("[%d, %d, %d, %d, %d] ",i,np->metrics[0],np->metrics[1],np->metrics[2],np->metrics[3]); } i++; symbols += 2; /* pasangan 2 bit konvolusi */ } printf("\n\n"); np = nodes; /* node pertama */ np->encstate = 0; /* kondisi awal diset 0 */ /* Hitung dan pilih metrik branch dari node root */ ENCODE(lsym,np->encstate); // 0-branch (LSB adalah 0) least significant bit // diagram state untuk memetakan np->encstate menjadi // satu pilihan (lsym) diantara empat metriks didepannya m0 = np->metrics[lsym]; // m0 adalah pilihan pertama /* Now do the 1-branch. To save another ENCODE call here and * inside the loop, we assume that both polynomials are odd, * providing complementary pairs of branch symbols. * This code should be modified if a systematic code were used. */ m1 = np->metrics[3^lsym]; // 3^lsym komplemen lsym adalah pilihan kedua if(m0 > m1) { np->tm[0] = m0; // jika 0-branch mempunyai metriks lebih baik np->tm[1] = m1; } else { np->tm[0] = m1; // jika 1-branch mempunyai nilai metriks lebih baik np->tm[1] = m0; np->encstate++; // Set low bit (bit paling kanan diubah) // jika 0 jadi 1; jika 1 jadi 0 } np->i = 0; // Start dengan best branch maxcycles *= nbits; // maxcycles = 10.000 * 81 np->gamma = t = 0; // nilai threshold awal = 0 printf("Start algoritma Fano...\n"); printf("\n\nMPS[Node Sekarang]= Metrik Path Sekarang; \nMBBD= Metrik Best Branch Depan; T= Threshold sekarang; \nD= Delta; CN= Capaian Node; U= Upaya; SE= State Encoder\n\n"); /* Start the Fano decoder */ for(i=1;i <= maxcycles;i++) { if((int)(np-nodes) > (int)*maxnp) *maxnp=(int)(np-nodes); /* capaian node sekarang */ #ifdef debug /* printf("node=%d, lsym=%d, lsym^3=%d, g=%ld, t=%d(delta= %d), m[%d]=%d, maxnp=%d, encstate=%lx\n", np-nodes,lsym, lsym^3,np->gamma,t,delta, np->i,np->tm[np->i],*maxnp,np->encstate); */ /* NS= Node Sekarang MPS[NS]= Metrik Path Sekarang MBBD= Metrik Best Branch Depan T= Threshold sekarang D= Delta CM= Capaian Node U= Upaya SE= State Encoder */ // printf("MPS[%d]=%ld, MBBD m[%d]=%d, T=%d(D= %d), CN=%d, U=%d, SE=%lx\n", // np-nodes, np->gamma,np->i,np->tm[np->i],t,delta, *maxnp, i,np->encstate); // getchar(); #endif // Look forward */ ngamma = np->gamma + np->tm[np->i]; // MPS_depan = MPS_sekarang + MBBD_depan if(ngamma >= t) { // boleh maju jika MPS_depan >= T_sekarang if(np->gamma < t + delta) { // jika MPS_sekarang < T_sekarang+D /* * Sebenarnya loop ini dapat diganti dengan * t += delta * ((ngamma - t)/delta); * namun perkalian dan pembagian * membuat beban prosesor berat sehingga waktu eksekusi * menjadi lebih lama * jika pertama kali algoritma sampai pada node ini * nilai threshold dikencangkan (dibesarkan). */ while(ngamma >= t + delta) t += delta; // jika MPS_depan >=T_sekarang+D maka T=T+D } np[1].gamma = ngamma; // gerak maju np[1].encstate = np->encstate << 1; // LSB dibuat 0 if( ++np == (lastnode+1) ) { printf("sukses... tiba di node %d dengan jumlah upaya = %d (%d)\n",np-nodes,i,maxcycles); *upaya=i; break; // Sukses... } /* Compute and sort metrics, starting with the * zero branch */ ENCODE(lsym,np->encstate); // konversi np->encstate menjadi // satu pilihan metriks node depan (lsym) if(np >= tail) { /* bagian tail semuanya adalah zero, tak perlu hitung branch-1 */ np->tm[0] = np->metrics[lsym]; } else { m0 = np->metrics[lsym]; // nilai metriks lebih baik m1 = np->metrics[3^lsym]; // nilai komplemen if(m0 > m1) { np->tm[0] = m0; // jika 0-branch mempunyai metriks lebih baik np->tm[1] = m1; } else { np->tm[0] = m1; // jika 1-branch mempunyai metriks lebih baik np->tm[1] = m0; np->encstate++; // Set low bit (bit paling kanan berubah) // jika 0 jadi 1; jika 1 jadi 0 } } np->i = 0; // Start dengan best branch continue; } // batas MP depan >= threshold // menyalahi Threshold, maka tidak bisa bergerak maju for(;;) { // lihat belakang if(np == nodes || np[-1].gamma < t) { // jika node pertama atau MPS_sebelum < T /* Can't back up either. * Relax threshold and and look * forward again to better branch. */ // printf("\nMPS[%d]= %ld; MPS[%d]= %ld; t= %d\n",(np-nodes), np[0].gamma,(np-nodes)-1,np[-1].gamma,t); t -= delta; // threshold dilonggarkan // printf("\nMPS[%d]= %ld; MPS[%d]= %ld; t= %d\n",(np-nodes), np[0].gamma,(np-nodes)-1,np[-1].gamma,t); // printf("Threshold dilonggarkan karena MPS[%d]i != 0) { np->i = 0; np->encstate ^= 1; // mengubah LSB menjadi sebaliknya; 0->1 atau 1->0 // karena sifat komplemen dari polinomial yang dipakai } break; } // batas node mundur selangkah // mundur if(--np < tail && np->i != 1) { np->i++; // Search next best branch np->encstate ^= 1; // mengubah LSB menjadi sebaliknya; 0->1 atau 1->0 // karena sifat komplemen dari polinomial yang dipakai break; } // else terus lihat belakang } // batas lihat belakang } *metric = np->gamma; // Return the final path metric // Copy decoded data to user's buffer // meletakkan deretan bit np->enstate kedalam buffer data siap pakai int jj=0; unsigned char ddata[11]; nbits >>= 3; /* nbits= 81>>3=10 */ np = &nodes[7]; while(nbits-- != 0) { *data++ = (unsigned char)np->encstate; /* sama saja */ //data[jj] = np->encstate; /* sama saja */ ddata[jj]= *(data-1); printf("np->encstate= %lx\n",np->encstate); np += 8; jj++; } printf("\n"); printf("\nHasil dekode: "); for(jj=0;jj<10;jj++){ printf("%X ",ddata[jj]); } *cycles = i+1; free(nodes); if(i >= maxcycles){ printf("gagal...\n"); return -1; // Decoder timed out } return 0; // Successful completion }