Source Code of Block Linear Code Encoder/Decoder
/********************************************************************/
/* */
/* PROJECT of MODERN COMMUNICATION ENGINEERING */
/* */
/*##################################################################*/
/* */
/* EDITOR: Victor Kun Fu DATE: Nov 25,1998 */
/* INSTRUCTOR: Dr. Kim */
/* ORGANIZATION: University of Toledo */
/* Electrical Engineering and Computer Science department */
/* */
/*##################################################################*/
/* */
/* FUNCTION DESCRIPTION: */
/* Encoder and Decoder of the Linear Block Code */
/* */
/********************************************************************/
#include <stdio.h>
#define MESSAGE_LENGTH 11
#define CODE_LENGTH 15
#define MAX_CODEWORD_VALUE 32767 /* codeword length is 15 bits */
void init();
void init_nTupleVecMarkTab();
int stArray_decoder(int, int, int);
int syndrome_decoder(int, int);
int encoder(int);
int calculate_weight(int);
int find_nextCosetLeader(int*);
int calculate_syndrome(int);
int build_syndrome_table();
void show_encode_result(char*, int, int, int, int);
void show_decode_result(char*, int, int, int, int);
void display_Vector(int, int);
void display_Vector_Table(char*, int*, int, int);
void display_Matrix(char*, int*, int, int);
void build_st_array();
void display_st_array(char*, int*, int, int, int);
void display_syn_table(char*, int*, int, int, int);
/********************************************************/
/* Generator Matrix */
/*------------------------------------------------------*/
/* Row No:11, Column No:15 */
/* the First four columns are parity check matrix(11*4) */
/* the other column are identity matrix(11*11) */
/********************************************************/
int nTupleVecMarkTab[MAX_CODEWORD_VALUE+1];
/********************************************************/
/* Generator Matrix */
/*------------------------------------------------------*/
/* Row No:11, Column No:15 */
/* the First four columns are parity check matrix(11*4) */
/* the other column are identity matrix(11*11) */
/********************************************************/
int G_matrix[11][15]={ /*P(11*4) I(11*11)*/
{0,1,1,1, /**/ 1,0,0,0,0,0,0,0,0,0,0},
{1,0,1,1, /**/ 0,1,0,0,0,0,0,0,0,0,0},
{1,1,0,1, /**/ 0,0,1,0,0,0,0,0,0,0,0},
{1,1,1,0, /**/ 0,0,0,1,0,0,0,0,0,0,0},
{1,1,0,0, /**/ 0,0,0,0,1,0,0,0,0,0,0},
{1,0,0,1, /**/ 0,0,0,0,0,1,0,0,0,0,0},
{0,0,1,1, /**/ 0,0,0,0,0,0,1,0,0,0,0},
{1,0,1,0, /**/ 0,0,0,0,0,0,0,1,0,0,0},
{0,1,0,1, /**/ 0,0,0,0,0,0,0,0,1,0,0},
{0,1,1,0, /**/ 0,0,0,0,0,0,0,0,0,1,0},
{1,1,1,1, /**/ 0,0,0,0,0,0,0,0,0,0,1}
};
/********************************************************************/
/* Parity Check Martix */
/*------------------------------------------------------------------*/
/* Row No:4, Column No:15 */
/* the First four columns are Identity matrix(4*4) */
/* the other columns are the Transpose of parity check matrix(4*11) */
/********************************************************************/
int H_matrix[4][15];
/********************************************************************/
/* Transpose matrix of Parity Check Matrix */
/*------------------------------------------------------------------*/
/* Row No:15, Column No:4 */
/********************************************************************/
int HTR_matrix[15][4];
/********************************************************************/
/* Standard Array */
/*------------------------------------------------------------------*/
/* Row No:16<=2^(15-11)>, Column No:2048<=2^11> */
/********************************************************************/
int St_Array[16][2048]={{0x0000}};
/* Syndrome Table */
int Sy_Table[16][2];
/* Vector get bit array*/
int Vector_Get_Bit_Array[16]={
0x1, /* take the 0th bit from vector */
0x2, /* take the 1th bit from vector */
0x4, /* take the 2th bit from vector */
0x8, /* take the 3th bit from vector */
0x10, /* take the 4th bit from vector */
0x20, /* take the 5th bit from vector */
0x40, /* take the 6th bit from vector */
0x80, /* take the 7th bit from vector */
0x100, /* take the 8th bit from vector */
0x200, /* take the 9th bit from vector */
0x400, /* take the 10th bit from vector */
0x800, /* take the 11th bit from vector */
0x1000, /* take the 12th bit from vector */
0x2000, /* take the 13th bit from vector */
0x4000, /* take the 14th bit from vector */
0x8000 /* take the 15th bit from vector */
};
/* All the possible messages to be encoded two to the power 11 for LBC(15,11) */
int Message[2048];
/* All the possible codeword : two the the power 11 for LBC(15, 11) */
int Codeword[2048];
/* here are three sample messages to be encoded */
int Example_message1 = 0x783;
int Example_message2 = 0x254;
int Example_message3 = 0x6c6;
/* here are three sample received vectors to be decoded */
int Example_rev_vector1 = 0x78ad;
int Example_rev_vector2 = 0x54a6;
int Example_rev_vector3 = 0x0d3b;
/****************************************************************/
/* MODULE NAME: init_nTupleVecMarkTab */
/*--------------------------------------------------------------*/
/* FUNCTION: initialize the n-tuple vector mark table */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/****************************************************************/
void init_nTupleVecMarkTab()
{
int i =0;
for (i=0; i<MAX_CODEWORD_VALUE+1; i++)
nTupleVecMarkTab[i] = 0;
}
/****************************************************************/
/* MODULE NAME: build_st_array */
/*--------------------------------------------------------------*/
/* FUNCTION: build the standard array */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* */
/****************************************************************/
void build_st_array(){
int i = 0;
int j = 0;
int current_minimun_weight = 1;
init_nTupleVecMarkTab();
/* establish the first coset */
for (i=0; i<2048; i++) {
St_Array[0][i] = Codeword[i];
nTupleVecMarkTab[St_Array[0][i]] = 1;
}
/* build coset 2 to 16 */
for (i=1; i<16; i++) {
/* find the next available coset leader with the minimum weight*/
St_Array[i][0] = find_nextCosetLeader(¤t_minimun_weight);
for (j=1; j<2048; j++ ) {
St_Array[i][j] = ((~(St_Array[i][0])) & St_Array[0][j]) | (St_Array[i][0] & (~(St_Array[0][j])));
nTupleVecMarkTab[St_Array[i][j]] = 1;
}
}
}
/****************************************************************/
/* MODULE NAME: encoder */
/*--------------------------------------------------------------*/
/* FUNCTION: Encode the input message */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* in_message: input message which is to be encoded */
/****************************************************************/
int encoder(int in_message){
/* codeword to be returned */
int ret_codeword = 0;
int tmp_int1 = 0;
int tmp_int2 = 0;
int bitNo = 0;
int i = 0;
int j = 0;
int Max_row = 11;
int Max_col = 15;
/* printf("\n Input message: ");
display_Vector(in_message, 11);
printf("\n"); */
for(j=0; j<Max_col; j++) {
/* printf("!!!!!!Col No: %3d\n", j);*/
bitNo = Max_row-1;
for (i=0; i<Max_row; i++) {
tmp_int1 = (in_message & (Vector_Get_Bit_Array[bitNo])) >> bitNo;
/* printf("bit %2d is: %2d", bitNo, tmp_int1);*/
tmp_int2 += tmp_int1 * G_matrix[i][j];
/* printf(" G[%2d][%2d]=%2d\n", i,j,G_matrix[i][j]);*/
bitNo--;
}
/* printf("\n Col sum = %3d\n", tmp_int2);*/
tmp_int2 %= 2;
/* printf("flag=%2d\n",tmp_int2);*/
if (tmp_int2)
ret_codeword |= Vector_Get_Bit_Array[CODE_LENGTH-j-1];
/* printf("\n current Output codeword: ");
display_Vector(ret_codeword, 15);
printf("\n"); */
tmp_int2 = 0;
}
/* printf("\n Output codeword: ");
display_Vector(ret_codeword, 15);
printf("\n"); */
return (ret_codeword);
}
/****************************************************************/
/* MODULE NAME: calculate_syndrome */
/*--------------------------------------------------------------*/
/* FUNCTION: calculate the syndrome of a codeword */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* in_codeword: input codeword which is to be received */
/****************************************************************/
int calculate_syndrome(int in_codeword){
/* syndrome to be returned */
int ret_syndrome = 0;
int tmp_int1 = 0;
int tmp_int2 = 0;
int bitNo = 0;
int i = 0;
int j = 0;
int Max_row = 15;
int Max_col = 4;
for(j=0; j<Max_col; j++) {
bitNo = Max_row-1;
for (i=0; i<Max_row; i++) {
tmp_int1 = (in_codeword & (Vector_Get_Bit_Array[bitNo])) >> bitNo;
tmp_int2 += tmp_int1 * HTR_matrix[i][j];
bitNo--;
}
tmp_int2 %= 2;
if (tmp_int2)
ret_syndrome |= Vector_Get_Bit_Array[3-j];
tmp_int2 = 0;
}
return (ret_syndrome);
}
/****************************************************************/
/* MODULE NAME: build_syndrome_table */
/*--------------------------------------------------------------*/
/* FUNCTION: build the syndrome table */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/****************************************************************/
int build_syndrome_table(){
int i = 0;
for (i=0; i<16; i++) {
Sy_Table[i][1] = St_Array[i][0];
Sy_Table[i][0] = calculate_syndrome(Sy_Table[i][1]);
}
}
/****************************************************************/
/* MODULE NAME: stArray_decoder */
/*--------------------------------------------------------------*/
/* FUNCTION: decode the received message using standard array */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* rev_message: <int> received message which is to be decoded */
/* row_no: <int> row number of standard array */
/* col_no: <int> col number of standard array */
/****************************************************************/
int stArray_decoder(int rev_message, int row_no, int col_no)
{
int i = 0;
int j = 0;
for (i=0; i<row_no; i++)
for (j=0; j<col_no; j++)
if (St_Array[i][j] == rev_message)
return(St_Array[0][j]);
}
/****************************************************************/
/* MODULE NAME: syndrome_decoder */
/*--------------------------------------------------------------*/
/* FUNCTION: decode the received message using syndrome_decoder */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* rev_message: received message which is to be decoded */
/* row_no: <int> row number of syndrome table */
/****************************************************************/
int syndrome_decoder(int rev_message, int row_no)
{
int i = 0;
int tmp_int1 = 0;
int ret_vector = 0;
tmp_int1 = calculate_syndrome(rev_message);
/* printf("@@@@tmp syndrome =");
display_Vector(tmp_int1, 4);*/
printf("\n");
for (i=0; i<row_no; i++) {
if (tmp_int1 == Sy_Table[i][0]) {
ret_vector = ((~(Sy_Table[i][1])) & rev_message) | (Sy_Table[i][1] & (~rev_message));
return(ret_vector);
}
}
}
/****************************************************************/
/* MODULE NAME: init */
/*--------------------------------------------------------------*/
/* FUNCTION: Initialize the system */
/*--------------------------------------------------------------*/
/****************************************************************/
void init(){
int i = 0;
int j = 0;
/* initialize the Parity Check Table H According to G */
for (i=0; i<4; i++)
for (j=0; j<15; j++) {
if ((i<4)&&(j<4)) {
if (i==j)
H_matrix[i][j] = 1;
else
H_matrix[i][j] = 0;
}
else
H_matrix[i][j] = G_matrix[j-4][i];
}
/* initialize the message table */
for (i=0; i<2048; i++)
Message[i]=i;
/* initialize the Transpose Parity check Matrix */
for (i=0; i<15; i++)
for (j=0; j<4; j++)
HTR_matrix[i][j] = H_matrix[j][i];
}
/****************************************************************/
/* MODULE NAME: display_Vector_Table */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* vec_name: < char * > vector table name */
/* vec_ptr: < int * > vector table pointer */
/* vec_tab_len: < int > vector table length */
/* vec_len: < int > vector length */
/****************************************************************/
void display_Vector_Table(char *vec_name, int *vec_ptr, int vec_tab_len, int vec_len){
int i = 0;
int j = 0;
printf("\n----------------------------------------------------\n");
printf("%s\n", vec_name);
for(i=0; i<vec_tab_len; i++) {
if ((i % 3) == 0)
printf("\n");
printf("[%6d] ",i);
display_Vector(vec_ptr[i], vec_len);
printf(", ");
}
printf("\n----------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: display_Vector */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* in_Vector: <int > input vector */
/* vec_len: <int > vector length */
/****************************************************************/
void display_Vector(int in_Vector, int vec_len){
int i = 0;
int tmp_int1 = 0;
vec_len--;
for (i=vec_len; i>=0; i--){
tmp_int1 = (in_Vector & (Vector_Get_Bit_Array[i])) >> i;
printf("%d",tmp_int1);
}
}
/****************************************************************/
/* MODULE NAME: display_Matrix */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* m_name: < char * > matrix name */
/* m_ptr: < int * > matrix pointer */
/* m_rowNo:< int > matrix row number */
/* m_colNo:< int > matrix column number */
/****************************************************************/
void display_Matrix(char *m_name, int *m_ptr, int m_rowNo, int m_colNo){
int i = 0;
int j = 0;
int *tmpPtr = m_ptr;
printf("\n----------------------------------------------------\n");
printf("%s\n", m_name);
for (i=0; i<m_rowNo; i++) {
for (j=0; j<m_colNo; j++) {
printf("%5d", *tmpPtr);
tmpPtr++;
}
printf("\n");
}
printf("\n----------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: display_st_array */
/*--------------------------------------------------------------*/
/* FUNCTION: Display standard array */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* st_name: < char * > standard array name */
/* st_ptr: < int * > standard array pointer */
/* st_rowNo: < int > standard array row number */
/* st_colNo: < int > standard array column number */
/* st_code_len < int > standard array codeword length */
/****************************************************************/
void display_st_array(char *st_name, int *st_ptr, int st_rowNo, int st_colNo, int st_code_len){
int i = 0;
int j = 0;
printf("\n----------------------------------------------------\n");
printf("%s\n", st_name);
for (i=0; i<st_rowNo; i++) {
printf("\n----------------------------------------\n");
printf("Row No[%5d]: ",i);
for (j=0; j<st_colNo; j++) {
if ((i==0)||(j==0)) {
printf("Col[%5d]:", j);
display_Vector(*st_ptr, st_code_len);
printf(" ");
if ((j % 50) == 0)
printf("\n");
}
st_ptr++;
}
printf("\n");
}
printf("\n----------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: display_syn_table */
/*--------------------------------------------------------------*/
/* FUNCTION: Display syndrome table */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* syn_name: < char * > syndrome table name */
/* syn_ptr: < int * > syndrome table pointer */
/* syn_rowNo: < int > syndrome table row number */
/* syndrome_len:< int > syndrome number */
/* syn_code_len < int > syndrome table error pattern length */
/****************************************************************/
void display_syn_table(char *syn_name, int *syn_ptr, int syn_rowNo, int syndrome_len, int syn_code_len)
{
int i = 0;
int j = 0;
printf("\n----------------------------------------------------\n");
printf("%s\n", syn_name);
for (i=0; i<syn_rowNo; i++) {
printf("Row No[%5d]: ",i);
display_Vector(*syn_ptr, syndrome_len);
syn_ptr++;
printf(" ");
display_Vector(*syn_ptr, syn_code_len);
syn_ptr++;
printf("\n");
}
printf("\n----------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: calculate_weight */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the weight of the input vector */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* in_vector: < int > input vector */
/****************************************************************/
int calculate_weight(int in_vector)
{
int ret_sum = 0;
int i = 0;
for (i=0; i<16; i++)
ret_sum += (in_vector & (Vector_Get_Bit_Array[i])) >> i;
return(ret_sum);
}
/****************************************************************/
/* MODULE NAME: find_nextCosetLeader */
/*--------------------------------------------------------------*/
/* FUNCTION: */
/* find the next Coset leader with the minimun weight */
/* in order to fulfill the Maximum Likelihood Decoding(MLD) */
/* or Minimum Distance Decoding */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* cur_min_weight: < int* > pointer to the current possible */
/* minimum weight of the remaining */
/* n-tuple vectors */
/****************************************************************/
int find_nextCosetLeader(int *cur_min_weight)
{
int find_flag = 0;
int ret_cosetLeader = 0;
int tmp_cosetLeader = 0;
int tmp_weight = 0;
int i = 0;
while (!find_flag)
{
for (i=1; i<=MAX_CODEWORD_VALUE; i++)
{
tmp_cosetLeader = i;
/* check whether this vector is used */
if (!nTupleVecMarkTab[i])
{
tmp_weight = calculate_weight(tmp_cosetLeader);
/* check whether this vector has the minimum weight */
if (tmp_weight == (*cur_min_weight))
{
ret_cosetLeader = tmp_cosetLeader;
nTupleVecMarkTab[tmp_cosetLeader] = 1;
find_flag = 1;
return (ret_cosetLeader);
}
}
}
*cur_min_weight = (*cur_min_weight) + 1;
}
}
/****************************************************************/
/* MODULE NAME: show_encode_result */
/*--------------------------------------------------------------*/
/* FUNCTION: Show encode result */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* m_name: < char * > decode method name */
/* ori_vec: < int > original vector to be encoded */
/* ori_vecLen: < int > original vector length */
/* en_vec: < int > encoded vector */
/* en_vecLen: < int > encoded vector length */
/****************************************************************/
void show_encode_result(char *m_name, int ori_vec, int ori_vecLen, int en_vec, int en_vecLen)
{
printf("\n------------------------------------------------\n");
printf("Encode the original vectors using %s\n", m_name);
printf("**************************\n");
printf("original vector = ");
display_Vector(ori_vec, ori_vecLen);
printf("\nencoded message = ");
display_Vector(en_vec, en_vecLen);
printf("\n------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: show_decode_result */
/*--------------------------------------------------------------*/
/* FUNCTION: Show decode result */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* m_name: < char * > decode method name */
/* rec_vec: < int > received vector to be decoded */
/* rec_vecLen: < int > received vector length */
/* de_vec: < int > decoded vector */
/* de_vecLen: < int > decoded vector length */
/****************************************************************/
void show_decode_result(char *m_name, int rec_vec, int rec_vecLen, int dec_vec, int dec_vecLen)
{
printf("\n------------------------------------------------\n");
printf("Decode the received vectors using %s\n", m_name);
printf("**************************\n");
printf("receive vector = ");
display_Vector(rec_vec, rec_vecLen);
printf("\ndecoded message = ");
display_Vector(dec_vec, dec_vecLen);
printf("\n------------------------------------------------\n");
}
main()
{
int i = 0;
int tmp_int1 = 0;
int tmp_int2 = 0;
init();
display_Matrix("Generator Matrix:",&G_matrix[0][0],11,15);
display_Matrix("Parity Check Matrix:",&H_matrix[0][0],4,15);
display_Matrix("Transpose Parity Check Matrix:",&HTR_matrix[0][0],15,4);
for (i=0; i<2048; i++)
Codeword[i] = encoder(Message[i]);
/* display_Vector_Table("Source Message Table", Message, 2048, 11);
display_Vector_Table("Codeword Table", Codeword, 2048, 15); */
build_st_array();
display_st_array("Standard Array", &St_Array[0][0], 16, 2048, 15);
build_syndrome_table();
display_syn_table("Syndrome Table", &Sy_Table[0][0], 16, 4, 15);
/* Test Decode three example received vectors */
tmp_int2 = encoder(Example_message1);
show_encode_result("Generator Matrix", Example_message1, 11, tmp_int2, 15);
tmp_int2 = encoder(Example_message2);
show_encode_result("Generator Matrix", Example_message2, 11, tmp_int2, 15);
tmp_int2 = encoder(Example_message3);
show_encode_result("Generator Matrix", Example_message3, 11, tmp_int2, 15);
/* Test Decode three example received vectors */
tmp_int2 = stArray_decoder(Example_rev_vector1, 16, 2048);
show_decode_result("Standard Array", Example_rev_vector1, 15, tmp_int2, 11);
tmp_int2 = stArray_decoder(Example_rev_vector2, 16, 2048);
show_decode_result("Standard Array", Example_rev_vector2, 15, tmp_int2, 11);
tmp_int2 = stArray_decoder(Example_rev_vector3, 16, 2048);
show_decode_result("Standard Array", Example_rev_vector3, 15, tmp_int2, 11);
tmp_int2 = syndrome_decoder(Example_rev_vector1, 16);
show_decode_result("Syndrome Table", Example_rev_vector1, 15, tmp_int2, 11);
tmp_int2 = syndrome_decoder(Example_rev_vector2, 16);
show_decode_result("Syndrome Table", Example_rev_vector2, 15, tmp_int2, 11);
tmp_int2 = syndrome_decoder(Example_rev_vector3, 16);
show_decode_result("Syndrome Table", Example_rev_vector3, 15, tmp_int2, 11);
}
Go back to My Homepage