/*
convolution.c : Defines the entry point for the console application.
This function does a 1/2 rate convolutional encoding.
The output of this function is given to the Viterbi Decoder and the
output of the decoder is compared with the input of the encoder. The resulting BER should be 0 as there is no noise.
This program currently works on 5 random numbers but it can be easily modified to any number of 32 bit numbers
*/
#include "stdlib.h"
#define ENC_SM_SIZE 8
typedef struct {
unsigned char curr_state;
unsigned char in_bit;
unsigned char op_bits;
unsigned char next_state;
} conv_encoder_SM;
/* curr_state, input, output, next_state */
conv_encoder_SM enc_state_table[ENC_SM_SIZE] = {
{0x00, 0x0, 0x00, 0x00},
{0x00, 0x1, 0x03, 0x02},
{0x01, 0x0, 0x03, 0x00},
{0x01, 0x1, 0x00, 0x02},
{0x02, 0x0, 0x02, 0x01},
{0x02, 0x1, 0x01, 0x03},
{0x03, 0x0, 0x01, 0x01},
{0x03, 0x1, 0x02, 0x03}
};
void encode(unsigned int input, unsigned int *output);
unsigned int viterbiDecode(unsigned int* encodedOutput);
unsigned char calculateBer(unsigned int input, unsigned int decodedOutput)
{
unsigned int i, xor, count;
count = 0;
xor = input ^ decodedOutput;
for (i=0; i < 32; i++)
{
if (xor%2 == 1)
count++;
xor >>= 1;
}
return count;
}
int main()
{
unsigned int i, input, decodedOutput, encodedOutput[2];
unsigned int no_errors, ber, total_input_bits;
no_errors=0;
for (i = 0; i < 5; i++)
{
input = rand();
//input = 0x2c405d4f;
input = input & 0xFFFFFFF0; /*Taking upper 28 bits and padding the remaining with 0 */
printf("input is 0x%08x \n", input);
encode(input, encodedOutput);
printf("encodedOutput[0] is 0x%08x \n", encodedOutput[0]);
printf("encodedOutput[1] is 0x%08x \n", encodedOutput[1]);
decodedOutput = viterbiDecode(encodedOutput);
printf("decodedOutput is 0x%08x \n", decodedOutput);
no_errors += calculateBer(input, decodedOutput);
}
total_input_bits = 28 * i;
ber = no_errors / total_input_bits;
printf("no_errors = %d\n", no_errors);
printf("total_input_bits = %d\n", total_input_bits);
printf("ber = %d\n", ber);
}
/* Funtion: lookup_conv_encoder
* Parameters:
* Takes the current state and input bit as arguments
* Returns the corresponding output bits and next state in the arguments
* Return Value: void
*/
void lookup_conv_encoder(unsigned char current_state, unsigned char input_bit, unsigned char * output_bits, unsigned char* next_state)
{
int i;
for (i = 0; i < ENC_SM_SIZE; i++)
{
if ((enc_state_table[i].curr_state == current_state)
&& (enc_state_table[i].in_bit == input_bit))
{
*output_bits = enc_state_table[i].op_bits;
*next_state = enc_state_table[i].next_state;
}
}
return;
}
/*
Function: encode
Does 1/2 rate convolution encoding.
The encoding function used will be (3, [7 5]) which denotes:
3 bit shift register
Bits are expressed as m(j), m(j-1) and m(j-2)
Input bit = m(j)
Output bit 1 = m(j) XOR m(j-1) XOR m(j-2) (Specified by '7' in the notation)
Output bit 2 = m(j) XOR m(j-2) (Specified by '5' in the notation)
Initiial state: m(j-1) and m(j-2) are 0
Parameters:
input = 32 bit sample contained in an integer
encodedOutput = 64 bits returned in an integer (32 bit) array of size 2
Return value: void
*/
void encode(unsigned int input, unsigned int* output)
{
unsigned char current_state, input_bit, output_bits, next_state;
unsigned int i, msb;
printf("Entering encode\n");
current_state = 0x00; /*Initial state is 0 */
output[0] = 0x00000000; /*Initialising output bytes*/
output[1] = 0x00000000;
for ( i = 0; i < 32; i++)
{
msb = input & 0x80000000; /*Extract MSB*/
input_bit = msb >> 31; /*Right shift by 31 to get it into the lsb*/
lookup_conv_encoder(current_state, input_bit, &output_bits, &next_state);
if (i <= 15)
{
/*First 16 bits will go in the first output int i.e. output[0] */
output[0] <<= 2;
/*Get the output bits into the last 2 bits of the output int*/
output[0] = output[0] | (output_bits & 0x03);
}
else
{
/*Second 16 bits will go in the second output int i.e. output[1] */
output[1] <<= 2;
/*Get the output bits into the last 2 bits of the output int*/
output[1] = output[1] | (output_bits & 0x03);
}
current_state = next_state;
input <<= 1; /*Shift left by 1 to get the next MSB*/
}
printf("Leaving encode\n");
return;
}
/*
* Function: calculate_branch_matric
* Parameters:
* enc_bits = bits that are in the data received at the receiver
* output = bits that would have been outputted by the conv encoder
* branch_matric = contains the Hamming distance between above two parameters
*
* Return Value: void
* */
void calculate_branch_matric( unsigned char enc_bits, unsigned char output, unsigned char *branch_matric)
{
unsigned char tmp;
tmp = enc_bits ^ output;
/*Count the number of 1s in the last 2 bits*/
*branch_matric = tmp/2 + tmp%2;
}
/*
* Function: lookup_input_bit
* This function returns the input bit that will cause the transition from current_state
* to next_state
*/
void lookup_input_bit(unsigned char current_state, unsigned char next_state, unsigned char * input_bit)
{
int i;
for (i = 0; i < ENC_SM_SIZE; i++)
{
if ((enc_state_table[i].curr_state == current_state)
&& (enc_state_table[i].next_state == next_state))
{
*input_bit = enc_state_table[i].in_bit;
break;
}
}
return;
}
/*
Function: viterbiDecode
This function does the decoding of the 1/2 rate (3,[7 5]) convolution encoded data
For simplicity, the traceback depth is 32 which is the same as the number of bits
*/
unsigned int viterbiDecode(unsigned int* encodedOutput)
{
unsigned int decOutput, encoded1, encoded2;
unsigned char enc_bits, i, j, prev_state, output, next_state;
unsigned char branch_matric, temp_matric, tr_state, input_bit;
unsigned char accum_matric[4][32];
unsigned char pred_state[4][32];
unsigned char traceback_states[33];
printf("Entering Viterbi\n");
/*Initialise accum_matric and pred_state to invalid values */
for (i=0; i < 32; i++)
{
for (j = 0; j < 4; j++)
{
pred_state[j][i] = 0xFF;
accum_matric[j][i] = 0x00;
}
}
encoded1 = encodedOutput[0];
encoded2 = encodedOutput[1];
/* if i = 0, only look at state 00
* if i = 1, only look at state 00, 02
* if i >= 2, look at all state
* */
for (i = 0; i < 32; i ++)
{
if(i < 16)
{
enc_bits = ((encoded1 & 0xC0000000) >> 30); // get the upper 2 bits
}
else
{
enc_bits = ((encoded2 & 0xC0000000) >> 30); // get the upper 2 bits
}
for ( j = 0; j < 4; j++)
{
if ( i == 0 )
{
/* First sample, only look at first (j=0) state */
if ( j != 0)
continue;
/*lookup output and next state for input 0*/
lookup_conv_encoder(j, 0, &output, &next_state);
calculate_branch_matric(enc_bits, output, &branch_matric);
pred_state[next_state][i] = j;
accum_matric[next_state][i] = branch_matric;
/*lookup output and next state