sdvd.cpp

卷积码的Viterbi解码器

					accum_err_metric[j][0] = accum_err_metric[j][0] - x;                   
					if (accum_err_metric[j][0] > MAXMETRIC)                     
						accum_err_metric[j][0] = MAXMETRIC;        
				} /* end 'j' for-loop */       
			}          
#endif          
			/* now pick the starting point for traceback */     
			state_sequence[depth_of_trellis] = h;         
			/* now work backwards from the end of the trellis to the oldest state    
			in the trellis to determine the optimal path. The purpose of this        
			is to determine the most likely state sequence at the encoder          
			based on what channel symbols we received. */    
			for (j = depth_of_trellis; j > 0; j--) {        
				sh_col = j + ( sh_ptr - depth_of_trellis );        
				if (sh_col < 0)               
					sh_col = sh_col + depth_of_trellis + 1;       
				state_sequence[j - 1] = state_history[ state_sequence[j] ] [sh_col];   
			} /* end of j for-loop */     
			/* now figure out what input sequence corresponds to the state sequence     
			in the optimal path */        
			*(decoder_output_matrix + t - depth_of_trellis + 1) =    
				input[ state_sequence[0] ] [ state_sequence[1] ];     
		} /* end of if-statement */           
 } /* end of 't' for-loop */

 /* ************************************************************************** */    
 /* now decode the encoder flushing channel-output bits */   
 for (t = channel_length - m; t < channel_length; t++) {   
	 /* set up the state history array pointer for this time t */   
	 sh_ptr = (int) ( ( t + 1 ) % (depth_of_trellis + 1) );      
	 /* don't need to consider states where input was a 1, so determine    
	 what is the highest possible state number where input was 0 */     
	 last_stop = (int) (number_of_states / pow(2.0, 1.0*(t - channel_length + m)));     
	 /* repeat for each possible state */       
	 
	 for (j = 0; j < last_stop; j++) {         
		 branch_metric = 0;          
		 deci2bin(output[j][0], n, binary_output);   
		 /* compute metric per channel bit, and sum for all channel bits          
		 in the convolutional encoder output n-tuple */         
		 for (ll = 0; ll < n; ll++) {             
			 branch_metric = branch_metric + soft_metric( *(channel_output_matrix +      
				 (ll * channel_length + t)), binary_output[ll] );       
		 } /* end of 'll' for loop */           
		 /* now choose the surviving path--the one with the smaller total      
		 metric... */       
		 if ( (accum_err_metric[ nextstate[j][0] ][1] > accum_err_metric[j][0] +       
			 branch_metric) /*|| flag[ nextstate[j][0] ] == 0*/) 
		 {              
				 /* save a state metric value for the survivor state */     
				 accum_err_metric[ nextstate[j][0] ][1] = accum_err_metric[j][0] +       
					 (double) branch_metric;          
				 /* update the state_history array with the state number of     
				 the survivor */             
				 state_history[ nextstate[j][0] ][sh_ptr] = j;    
		 } /* end of if-statement */        
	 } /* end of 'j' for-loop */   

	 /* for all rows of accum_err_metric, swap columns 1 and 2 */    
	 for (j = 0; j < number_of_states; j++) {       
		 accum_err_metric[j][0] = accum_err_metric[j][1];     
		 accum_err_metric[j][1] = MAXINT;        
	 } /* end of 'j' for-loop */   
	 /* now start the traceback, if i >= depth_of_trellis - 1*/     
	 if (t >= depth_of_trellis - 1) {          
		 /* initialize the state_sequence vector */    
		 for (j = 0; j <= depth_of_trellis; j++) state_sequence[j] = 0;       
		 /* find the state_history element with the minimum accum. error metric */      
		 x = accum_err_metric[0][0];           
		 h = 0;            
		 for (j = 1; j < last_stop; j++) {       
			 if (accum_err_metric[j][0] < x) {           
				 x = accum_err_metric[j][0];                  
				 h = j;            
			 } /* end if */       
		 } /* end 'j' for-loop */       
#ifdef NORM       
		 /* if the smallest accum. error metric value is > MAXMETRIC, normalize the  
		 accum. errror metrics by subtracting the value of the smallest one from        
		 all of them (making the smallest = 0) and saturate all other metrics          
		 at MAXMETRIC */         
		 if (x > MAXMETRIC) {           
			 for (j = 0; j < number_of_states; j++) {          
				 accum_err_metric[j][0] = accum_err_metric[j][0] - x;         
				 if (accum_err_metric[j][0] > MAXMETRIC) {                
					 accum_err_metric[j][0] = MAXMETRIC;               
				 } /* end if */               
			 } /* end 'j' for-loop */       
		 }           
#endif           
		 state_sequence[depth_of_trellis] = h;         
		 /* now work backwards from the end of the trellis to the oldest state        
		 in the trellis to determine the optimal path. The purpose of this      
		 is to determine the most likely state sequence at the encoder          
		 based on what channel symbols we received. */       
		 for (j = depth_of_trellis; j > 0; j--) {           
			 sh_col = j + ( sh_ptr - depth_of_trellis );         
			 if (sh_col < 0)              
				 sh_col = sh_col + depth_of_trellis + 1;  
			 state_sequence[j - 1] = state_history[ state_sequence[j] ][sh_col];   
		 } /* end of j for-loop */        
		 /* now figure out what input sequence corresponds to the    
		 optimal path */          
		 *(decoder_output_matrix + t - depth_of_trellis + 1) =      
			 input[ state_sequence[0] ][ state_sequence[1] ];   
	 } /* end of if-statement */   
 }  /* end of 't' for-loop */   
 for (i = 1; i < depth_of_trellis - m; i++)     
	 *(decoder_output_matrix + channel_length - depth_of_trellis + i) =    
	 input[ state_sequence[i] ] [ state_sequence[i + 1] ];   
 /* free the dynamically allocated array storage area */   
 free(channel_output_matrix);   
 return;
}
 /* end of function sdvd */
 /* ********************* END OF SDVD FUNCTION ******************************* */

 /* this initializes a 3-bit soft-decision quantizer optimized for about 4 dB Eb/No.*/
 void init_quantizer(void) {  
	 int i;    
	 for (i = -128; i < -31; i++)       
		 quantizer_table[i + 128] = 7;  
	 for (i = -31; i < -21; i++)     
		 quantizer_table[i + 128] = 6;
	 for (i = -21; i < -11; i++)      
		 quantizer_table[i + 128] = 5;   
	 for (i = -11; i < 0; i++)      
		 quantizer_table[i + 128] = 4;  
	 for (i = 0; i < 11; i++)  
		 quantizer_table[i + 128] = 3;   
	 for (i = 11; i < 21; i++)     
		 quantizer_table[i + 128] = 2; 
	 for (i = 21; i < 31; i++)       
		 quantizer_table[i + 128] = 1;   
	 for (i = 31; i < 128; i++)     
		 quantizer_table[i + 128] = 0;}
 /* this initializes a quantizer that adapts to Es/No */
 void init_adaptive_quant(double es_ovr_n0) {  
	 int i, d;   
	 double es, sn_ratio, sigma;  
	 es = 1;   
	 sn_ratio = (double) pow(10.0, ( es_ovr_n0 / 10.0 ) ); 
	 sigma =  (double) sqrt( es / ( 2.0 * sn_ratio ) );   
	 d = (int) ( 32 * 0.5 * sigma );   
	 for (i = -128; i < ( -3 * d ); i++)   
		 quantizer_table[i + 128] = 7;   
	 for (i = ( -3 * d ); i < ( -2 * d ); i++)    
		 quantizer_table[i + 128] = 6;   
	 for (i = ( -2 * d ); i < ( -1 * d ); i++)  
		 quantizer_table[i + 128] = 5;    
	 for (i = ( -1 * d ); i < 0; i++)     
		 quantizer_table[i + 128] = 4;   
	 for (i = 0; i < ( 1 * d ); i++)      
		 quantizer_table[i + 128] = 3;    
	 for (i = ( 1 * d ); i < ( 2 * d ); i++)
		 quantizer_table[i + 128] = 2;   
	 for (i = ( 2 * d ); i < ( 3 * d ); i++)    
		 quantizer_table[i + 128] = 1;  
	 for (i = ( 3 * d ); i < 128; i++)      
		 quantizer_table[i + 128] = 0;}
 /* this quantizer assumes that the mean channel_symbol value is +/- 1, 
 and translates it to an integer whose mean value is +/- 32 to address  
 the lookup table "quantizer_table". Overflow protection is included.*/ 
 int soft_quant(double channel_symbol) 
 {   
	 int x;    
	 x = (int) ( 32.0 * channel_symbol );  
	 if (x < -128) x = -128;    
	 if (x > 127) x = 127;   
	 return(quantizer_table[x + 128]);
 }
 /* this metric is based on the algorithm given in Michelson and Levesque, 
 page 323. */
 int soft_metric(int data, int guess) 
{ 
	 return(abs(data - (guess * 7)));
}

 /* this function calculates the next state of the convolutional encoder, given  
 the current state and the input data.  It also calculates the memory   
 contents of the convolutional encoder. */
 int nxt_stat(int current_state, int input, int *memory_contents) 
	 {  
		 int binary_state[K - 1]; 

		 /* binary value of current state */  
		 int next_state_binary[K - 1];    
		 /* binary value of next state */  
		 int next_state;                     
		 /* decimal value of next state */   
		 int i;                       
		 /* loop variable */   
		 /* convert the decimal value of the current state number to binary */  
		 deci2bin(current_state, K - 1, binary_state);   
		 /* given the input and current state number, compute the next state number */  
		 next_state_binary[0] = input;    
		 for (i = 1; i < K - 1; i++)     
			 next_state_binary[i] = binary_state[i - 1];   
		 /* convert the binary value of the next state number to decimal */  
		 next_state = bin2deci(next_state_binary, K - 1);   
		 /* memory_contents are the inputs to the modulo-two adders in the encoder */  
		 memory_contents[0] = input;    
		 for (i = 1; i < K; i++)      
			 memory_contents[i] = binary_state[i - 1];  
		 return(next_state);}
 /* this function converts a decimal number to a binary number, stored  
 as a vector MSB first, having a specified number of bits with leading 
 zeroes as necessary */

 void deci2bin(int d, int size, int *b) {  
	 int i;   
	 for(i = 0; i < size; i++)  
		 b[i] = 0;   
	 b[size - 1] = d & 0x01; 
	 for (i = size - 2; i >= 0; i--) 
	 {        
		 d = d >> 1;   
	 b[i] = d & 0x01;   
	 }
 }/* this function converts a binary number having a specified 
	   number of bits to the corresponding decimal number  
	   with improvement contributed by Bryan Ewbank 2001.11.28 */
 int bin2deci(int *b, int size) 
 {    int i, d;   
 d = 0;    
 for (i = 0; i < size; i++)   
	 d += b[i] << (size - i - 1);   
 return(d);
 }