Source Code of Cyclic 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 Cyclic Code */
/* */
/********************************************************************/
/*###########################*/
/* IMPORTED FILE DECLARATION */
/*###########################*/
#include <stdio.h>
/*#############################*/
/* GLOBAL CONSTANT DECLARATION */
/*#############################*/
#define MESSAGE_LENGTH 11
#define CODE_LENGTH 21
#define MAX_CODEWORD_VALUE 2097152 /* codeword length is 21 bits */
/*###################################*/
/* GLOBAL DATA STRUCTURE DECLARATION */
/*###################################*/
/* Generator Polynomial of degree r=n-k=21-11=10 */
long Gx_polynomial = 0x4d5; /*g(x)=1+x^2+x^4+x^6+x^7+x^10 (low bit->high bit) */
long Hx_polynomial = 0; /* Parity check polynomial */
/* here are three sample messages to be encoded */
long Example_message1 = 0x513; /* u1(x)=1+x+x^4+x^8+x^10 (low bit->high bit)*/
long Example_message2 = 0x6a5; /* u2(x)=1+x^2+x^5+x^7+x^9+x^10 (low bit->high bit)*/
long Example_message3 = 0x2f3; /* u3(x)=1+x+x^4+x^5+x^6+x^7+x^9 (low bit->high bit)*/
/* here are three sample messages to be encoded */
long Example_rev_vector1 = 0x20021;
long Example_rev_vector2 = 0x84189;
long Example_rev_vector3 = 0x188146;
/* Vector get bit array*/
unsigned long Vector_Get_Bit_Array[32]=
{
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 */
0x10000, /* take the 16th bit from vector */
0x20000, /* take the 17th bit from vector */
0x40000, /* take the 18th bit from vector */
0x80000, /* take the 19th bit from vector */
0x100000, /* take the 20th bit from vector */
0x200000, /* take the 21th bit from vector */
0x400000, /* take the 22th bit from vector */
0x800000, /* take the 23th bit from vector */
0x1000000, /* take the 24th bit from vector */
0x2000000, /* take the 25th bit from vector */
0x4000000, /* take the 26th bit from vector */
0x8000000, /* take the 27th bit from vector */
0x10000000,/* take the 28th bit from vector */
0x20000000,/* take the 29th bit from vector */
0x40000000,/* take the 30th bit from vector */
0x80000000 /* take the 31th bit from vector */
};
/* Syndrome Table */
long Symdrome_Table[1024][2];
int nTupleVecMarkTab[MAX_CODEWORD_VALUE+1];
long codeWord[2048];
FILE *f1 = NULL;
/*#############################*/
/* GLOBAL FUNCTION DECLARATION */
/*#############################*/
long meggitt_decoder(long, int);
long syndrome_decoder(long, int, long *);
long Gx_Cyc_Encoder(long);
long Hx_Cyc_Encoder(long);
long Gx_Cyc_CKT_Encoder(long);
long Hx_Cyc_CKT_Encoder(long);
long Cyc_Syndrome_computation_CKT(long);
int calculate_weight(long in_vector);
/*############################*/
/* LOCAL FUNCTION DECLARATION */
/*############################*/
/* functions realated with decoding */
void build_Cyc_Syndrome_Table();
long find_nextCosetLeader(int *);
void init_nTupleVecMarkTab();
/* interaction between two polynomials */
long muliply_Polynomial(long,long,int);
long div_Polynomial(long,long,long*);
long add_Polynomial(long,long);
/* show polynomial */
void display_Polynomial(long, int);
void show_encode_result(char*, long, int, long, int);
void show_decode_result(char*, long, int, long, int);
int getPolynomialDeg(long);
long getPolynomialBit(long, int);
/*############################*/
/* MAIN FUNCTION DEFINITION */
/*############################*/
main ()
{
long tmp_long1 = 0;
long tmp_err_pattern = 0;
f1 = fopen("ttt1", "w");
fprintf(f1, "\n----------------\n");
fprintf(f1, "g(x) = ");
display_Polynomial(Gx_polynomial,11);
fprintf(f1, "\n----------------\n");
tmp_long1 = Gx_Cyc_Encoder(Example_message1);
show_encode_result(" g(x) ", Example_message1, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Gx_Cyc_Encoder(Example_message2);
show_encode_result(" g(x) ", Example_message2, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Gx_Cyc_Encoder(Example_message3);
show_encode_result(" g(x) ", Example_message3, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Gx_Cyc_CKT_Encoder(Example_message1);
/* show_encode_result(" g(x) CKT ", Example_message1, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH); */
tmp_long1 = Gx_Cyc_CKT_Encoder(Example_message2);
/* show_encode_result(" g(x) CKT ", Example_message2, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH); */
tmp_long1 = Gx_Cyc_CKT_Encoder(Example_message3);
/* show_encode_result(" g(x) CKT ", Example_message3, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);*/
tmp_long1 = Hx_Cyc_Encoder(Example_message1);
show_encode_result(" h(x) ", Example_message1, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Hx_Cyc_Encoder(Example_message2);
show_encode_result(" h(x) ", Example_message2, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Hx_Cyc_Encoder(Example_message3);
show_encode_result(" h(x) ", Example_message3, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH);
tmp_long1 = Hx_Cyc_CKT_Encoder(Example_message1);
/* show_encode_result(" h(x) CKT ", Example_message1, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH); */
tmp_long1 = Hx_Cyc_CKT_Encoder(Example_message2);
/* show_encode_result(" h(x) CKT ", Example_message2, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH); */
tmp_long1 = Hx_Cyc_CKT_Encoder(Example_message3);
/* show_encode_result(" h(x) CKT ", Example_message3, MESSAGE_LENGTH, tmp_long1, CODE_LENGTH); */
fprintf(f1, "\nStart building syndrome table\n!");
build_Cyc_Syndrome_Table();
fprintf(f1, "\nfinish building syndrome table\n!");
tmp_long1 = syndrome_decoder(Example_rev_vector1, 1024, &tmp_err_pattern);
show_decode_result("Syndrome Table", Example_rev_vector1, 21, tmp_long1>>10, 11);
tmp_long1 = syndrome_decoder(Example_rev_vector2, 1024, &tmp_err_pattern);
show_decode_result("Syndrome Table", Example_rev_vector2, 21, tmp_long1>>10, 11);
tmp_long1 = syndrome_decoder(Example_rev_vector3, 1024, &tmp_err_pattern);
show_decode_result("Syndrome Table", Example_rev_vector3, 21, tmp_long1>>10, 11);
tmp_long1 = meggitt_decoder(Example_rev_vector1, 1024);
show_decode_result("Meggitt decoding", Example_rev_vector1, 21, tmp_long1>>10, 11);
tmp_long1 = meggitt_decoder(Example_rev_vector2, 1024);
show_decode_result("Meggitt decoding", Example_rev_vector2, 21, tmp_long1>>10, 11);
tmp_long1 = meggitt_decoder(Example_rev_vector3, 1024);
show_decode_result("Meggitt decoding", Example_rev_vector3, 21, tmp_long1>>10, 11);
fclose(f1);
}
/*############################*/
/* GLOBAL FUNCTION DEFINITION */
/*############################*/
/****************************************************************/
/* MODULE NAME: meggitt_decoder */
/*--------------------------------------------------------------*/
/* FUNCTION: decode the received message using meggitt_decoder */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* rev_message: received message which is to be decoded */
/* row_no: <int> row number of syndrome table */
/****************************************************************/
long meggitt_decoder(long rev_message, int row_no)
{
long tmp_retVal = 0;
int cur_retBit = 0;
int shift_step = 0;
int buffer_reg[CODE_LENGTH];
int tmp_buffer_reg[CODE_LENGTH];
int syndrome_reg[CODE_LENGTH-MESSAGE_LENGTH];
int tmp_syndrome_reg[CODE_LENGTH-MESSAGE_LENGTH];
long tmp_syndrome = 0;
long err_pattern = 0;
int i = 0;
int input = 0;
int output = 0;
/* init registers */
for (i=0; i<CODE_LENGTH; i++) {
buffer_reg[i] = 0;
tmp_buffer_reg[i] = 0;
}
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++) {
syndrome_reg[i] = 0;
tmp_syndrome_reg[i] = 0;
}
/* step 1 */
for (i=0; i<CODE_LENGTH; i++)
buffer_reg[i] = (rev_message & (Vector_Get_Bit_Array[i]))>>i;
tmp_syndrome = Cyc_Syndrome_computation_CKT(rev_message);
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
syndrome_reg[i] = (tmp_syndrome & (Vector_Get_Bit_Array[i]))>>i;
for (shift_step=0; shift_step<CODE_LENGTH; shift_step++) {
/* step 2 */
for (i=0; i<row_no; i++)
if (tmp_syndrome == Symdrome_Table[i][1]) {
err_pattern = Symdrome_Table[i][0];
break;
}
output = (err_pattern & (Vector_Get_Bit_Array[CODE_LENGTH-1])) >> (CODE_LENGTH-1);
/* step 3 */
cur_retBit = (output + buffer_reg[CODE_LENGTH-1]) % 2;
if (cur_retBit)
tmp_retVal = tmp_retVal | Vector_Get_Bit_Array[CODE_LENGTH-shift_step-1];
tmp_buffer_reg[0] = cur_retBit;
for (i=1; i<CODE_LENGTH; i++)
tmp_buffer_reg[i] = buffer_reg[i-1];
tmp_syndrome_reg[0] = (output + syndrome_reg[CODE_LENGTH-MESSAGE_LENGTH-1])%2;
for (i=1; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
tmp_syndrome_reg[i] = (syndrome_reg[i-1]+syndrome_reg[CODE_LENGTH-MESSAGE_LENGTH-1]*((Gx_polynomial & Vector_Get_Bit_Array[i])>>i))%2;
for (i=0; i<CODE_LENGTH; i++)
buffer_reg[i] = tmp_buffer_reg[i];
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
syndrome_reg[i] = tmp_syndrome_reg[i];
tmp_syndrome = 0;
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
if (syndrome_reg[i])
tmp_syndrome = tmp_syndrome | Vector_Get_Bit_Array[i];
}
return(tmp_retVal);
}
/****************************************************************/
/* 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 */
/* err_pattern: pointer to the error pattern */
/****************************************************************/
long syndrome_decoder(long rev_message, int row_no, long *err_pattern)
{
int i = 0;
long tmp_long1 = 0;
long ret_vector = 0;
tmp_long1 = Cyc_Syndrome_computation_CKT(rev_message);
printf("\n");
for (i=0; i<row_no; i++) {
if (tmp_long1 == Symdrome_Table[i][1]) {
*err_pattern = Symdrome_Table[i][0];
ret_vector = ((~(Symdrome_Table[i][0])) & rev_message) | (Symdrome_Table[i][0] & (~rev_message));
return(ret_vector);
}
}
}
/****************************************************************/
/* MODULE NAME: Gx_Cyc_Encoder */
/*--------------------------------------------------------------*/
/* FUNCTION: Encode the input message Using Generator Polynomial*/
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* inMessage: input message which is to be encoded */
/* */
/* OUTPUT: */
/* RetVal: the encoded codeword */
/****************************************************************/
long Gx_Cyc_Encoder(long inMessage)
{
long tmp_Long1 = 0;
long tmp_bx = 0;
long tmp_retVal = 0;
/* printf("\nStep 1 starting ...\n "); */
/* Step1: form x^(n-k)*u(x); x^(21-11)=x^10 : 0x400 */
tmp_Long1=muliply_Polynomial(0x400, inMessage, MESSAGE_LENGTH);
/* printf("\nStep 1 stop ...\n ");
printf("\nStep 2 starting ...\n "); */
/* Step2: get b(x), b(x)= remainder of x^(n-k)*u(x)/g(x) */
div_Polynomial(tmp_Long1, Gx_polynomial, &tmp_bx);
/* printf("\nStep 2 stop ...\n ");
printf("\nStep 3 starting ...\n "); */
/* combine step1 & step2 */
tmp_retVal = add_Polynomial(tmp_bx,tmp_Long1);
/* printf("\nStep 3 stop ...\n "); */
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: Gx_Cyc_CKT_Encoder */
/*--------------------------------------------------------------*/
/* FUNCTION: Encode the input message Using Generator Polynomial*/
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* inMessage: input message which is to be encoded */
/* */
/* OUTPUT: */
/* RetVal: the encoded codeword */
/****************************************************************/
long Gx_Cyc_CKT_Encoder(long inMessage)
{
long tmp_retVal = 0;
int shift_step = 0;
int b_reg[CODE_LENGTH-MESSAGE_LENGTH];
int tmp_b_reg[CODE_LENGTH-MESSAGE_LENGTH];
int input = 0; /* current input message bit */
int i = 0;
/* display */
fprintf(f1, "\n------------------------------------------------\n");
fprintf(f1, "Encode the original message using g(x) CKT \n");
fprintf(f1, "**************************\n");
fprintf(f1, "original message = ");
display_Polynomial(inMessage, MESSAGE_LENGTH );
/* init shift reg */
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++) {
b_reg[i] = 0;
tmp_b_reg[i] = 0;
}
fprintf(f1, "\n\nInput Register Contents\n");
/* show input */
fprintf(f1, " ");
for (i=0; i<10; i++)
fprintf(f1, "%2d",b_reg[i]);
fprintf(f1, "( initial state)\n");
/* shifting reg */
for (shift_step=0; shift_step<MESSAGE_LENGTH; shift_step++)
{
input = (inMessage&(Vector_Get_Bit_Array[10-shift_step]))>>(10-shift_step);
tmp_b_reg[0] = (b_reg[9] + input)%2;
tmp_b_reg[1] = b_reg[0];
tmp_b_reg[2] = ((b_reg[9] + input)%2+ b_reg[1])%2;
tmp_b_reg[3] = b_reg[2];
tmp_b_reg[4] = ((b_reg[9] + input)%2+ b_reg[3])%2;
tmp_b_reg[5] = b_reg[4];
tmp_b_reg[6] = ((b_reg[9] + input)%2+ b_reg[5])%2;
tmp_b_reg[7] = ((b_reg[9] + input)%2+ b_reg[6])%2;
tmp_b_reg[8] = b_reg[7];
tmp_b_reg[9] = b_reg[8];
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
b_reg[i] = tmp_b_reg[i];
/* show input */
fprintf(f1, "%3d ", input);
for (i=0; i<10; i++)
fprintf(f1, "%2d",b_reg[i]);
fprintf(f1, "( %3dth shift)\n", shift_step+1);
}
/* produce output */
tmp_retVal = inMessage << 10;
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
if (b_reg[i])
tmp_retVal = tmp_retVal | Vector_Get_Bit_Array[i];
/* display */
fprintf(f1, "\nencoded codeword = ");
display_Polynomial(tmp_retVal, CODE_LENGTH);
fprintf(f1, "\n------------------------------------------------\n");
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: Hx_Cyc_Encoder */
/*--------------------------------------------------------------*/
/* FUNCTION: Encode the input message Using Parity Polynomial*/
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* inMessage: input message which is to be encoded */
/* */
/* OUTPUT: */
/* RetVal: the encoded codeword */
/****************************************************************/
long Hx_Cyc_Encoder(long inMessage)
{
long tmp_Long1 = 0;
long tmp_bx = 0;
long tmp_retVal = 0;
long tmp_remainder = 0;
int i = 0;
int j = 0;
int bitPosVal1 = 0;
int bitPosVal2 = 0;
int tmpSum=0;
/* h(x)=(x^CODE_LENGTH+1)/g(x) */
Hx_polynomial = div_Polynomial(0x200001, Gx_polynomial, &tmp_bx);
/* printf("\n\n!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
printf("h(x)= ");
display_Polynomial(Hx_polynomial, 32);
printf("\n!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n"); */
tmp_retVal = muliply_Polynomial(0x400, inMessage, MESSAGE_LENGTH);
for (j=1; j<=CODE_LENGTH-MESSAGE_LENGTH; j++) {
tmpSum = 0;
for (i=0; i<=MESSAGE_LENGTH-1; i++){
bitPosVal1 = getPolynomialBit(Hx_polynomial, i);
bitPosVal2 = getPolynomialBit(tmp_retVal, CODE_LENGTH-i-j);
tmpSum += (bitPosVal1 * bitPosVal2);
}
if(tmpSum % 2) {
tmp_Long1 = Vector_Get_Bit_Array[CODE_LENGTH-MESSAGE_LENGTH-j];
tmp_retVal = add_Polynomial(tmp_retVal, tmp_Long1);
}
}
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: Hx_Cyc_CKT_Encoder */
/*--------------------------------------------------------------*/
/* FUNCTION: Encode the input message Using Parity Polynomial */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* inMessage: input message which is to be encoded */
/* */
/* OUTPUT: */
/* RetVal: the encoded codeword */
/****************************************************************/
long Hx_Cyc_CKT_Encoder(long inMessage)
{
long tmp_retVal = 0;
int shift_step = 0;
int u_reg[MESSAGE_LENGTH];
int tmp_u_reg[MESSAGE_LENGTH];
long tmp_bx = 0;
int i = 0;
int j = 0;
int tmpSum=0;
/* display */
fprintf(f1, "\n------------------------------------------------\n");
fprintf(f1, "Encode the original message using h(x) CKT \n");
fprintf(f1, "**************************\n");
fprintf(f1, "original message = ");
display_Polynomial(inMessage, MESSAGE_LENGTH );
/* h(x)=(x^CODE_LENGTH+1)/g(x) */
Hx_polynomial = div_Polynomial(0x200001, Gx_polynomial, &tmp_bx);
/* produce output */
tmp_retVal = inMessage << 10;
/* init shift reg */
for (i=0; i<MESSAGE_LENGTH; i++) {
u_reg[i] = (inMessage & Vector_Get_Bit_Array[i])>>i;
tmp_u_reg[i] = 0;
}
fprintf(f1, "\n\n Register Contents Output\n");
for (i=0; i<11; i++)
fprintf(f1, "%2d",u_reg[i]);
fprintf(f1, "( initial state)\n");
/* shifting reg */
for (shift_step=0; shift_step<CODE_LENGTH-MESSAGE_LENGTH; shift_step++)
{
tmpSum = 0;
for (i=0; i<MESSAGE_LENGTH; i++)
tmpSum = tmpSum + u_reg[i]* ((Hx_polynomial & Vector_Get_Bit_Array[10-i])>>(10-i));
tmp_u_reg[0] = tmpSum%2;
tmp_u_reg[1] = u_reg[0];
tmp_u_reg[2] = u_reg[1];
tmp_u_reg[3] = u_reg[2];
tmp_u_reg[4] = u_reg[3];
tmp_u_reg[5] = u_reg[4];
tmp_u_reg[6] = u_reg[5];
tmp_u_reg[7] = u_reg[6];
tmp_u_reg[8] = u_reg[7];
tmp_u_reg[9] = u_reg[8];
tmp_u_reg[10] = u_reg[9];
for (i=0; i<MESSAGE_LENGTH; i++)
u_reg[i] = tmp_u_reg[i];
if (u_reg[0])
tmp_retVal = tmp_retVal | Vector_Get_Bit_Array[CODE_LENGTH-MESSAGE_LENGTH-1-shift_step];
/* show regs */
for (i=0; i<11; i++)
fprintf(f1, "%2d",u_reg[i]);
fprintf(f1, "( %3dth shift) %2d\n", shift_step+1, u_reg[0]);
}
/* display */
fprintf(f1, "\nencoded codeword = ");
display_Polynomial(tmp_retVal, CODE_LENGTH);
fprintf(f1, "\n------------------------------------------------\n");
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: Cyc_Syndrome_computation_CKT */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the syndrome Using a division circuit */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* recVector: received vector whose syndrome will be calculated */
/* */
/* OUTPUT: */
/* RetVal: the syndrome */
/****************************************************************/
long Cyc_Syndrome_computation_CKT(long recVector)
{
long tmp_retVal = 0;
int shift_step = 0;
int s_reg[CODE_LENGTH-MESSAGE_LENGTH];
int tmp_s_reg[CODE_LENGTH-MESSAGE_LENGTH];
int input = 0;
int i = 0;
/* init shift reg */
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++) {
s_reg[i] = 0;
tmp_s_reg[i] = 0;
}
/* shifting reg */
for (shift_step=0; shift_step<CODE_LENGTH; shift_step++)
{
input = (recVector & (Vector_Get_Bit_Array[CODE_LENGTH-shift_step-1]))>>(CODE_LENGTH-shift_step-1);
tmp_s_reg[0] = (input + s_reg[CODE_LENGTH-MESSAGE_LENGTH-1])%2;
for (i=1; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
tmp_s_reg[i] = (s_reg[i-1]+s_reg[CODE_LENGTH-MESSAGE_LENGTH-1]*((Gx_polynomial & Vector_Get_Bit_Array[i])>>i))%2;
for (i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
s_reg[i] = tmp_s_reg[i];
}
/* produce output */
for(i=0; i<CODE_LENGTH-MESSAGE_LENGTH; i++)
if (s_reg[i])
tmp_retVal = tmp_retVal | Vector_Get_Bit_Array[i];
return(tmp_retVal);
}
/*############################*/
/* LOCAL FUNCTION DEFINITION */
/*############################*/
/****************************************************************/
/* MODULE NAME: calculate_weight */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the weight of the input vector */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* in_vector: < long > input vector */
/****************************************************************/
int calculate_weight(long in_vector)
{
int ret_sum = 0;
int i = 0;
for (i=0; i<21; i++)
ret_sum += (in_vector & (Vector_Get_Bit_Array[i])) >> i;
return(ret_sum);
}
/****************************************************************/
/* MODULE NAME: init_nTupleVecMarkTab */
/*--------------------------------------------------------------*/
/* FUNCTION: initialize the n-tuple vector mark table */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/****************************************************************/
void init_nTupleVecMarkTab()
{
int i =0;
long tmp_long1 = 0;
for (i=0; i<MAX_CODEWORD_VALUE+1; i++)
nTupleVecMarkTab[i] = 0;
for (i=0; i<2048; i++)
{
codeWord[i] = Gx_Cyc_Encoder(i);
nTupleVecMarkTab[codeWord[i]] = 1;
}
}
/****************************************************************/
/* MODULE NAME: build_Cyc_Syndrome_Table */
/*--------------------------------------------------------------*/
/* FUNCTION: Build the syndrome table of cyc code */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* */
/* OUTPUT: */
/****************************************************************/
void build_Cyc_Syndrome_Table()
{
long tmp_long1 =0;
long tmp_cosetLeader =0;
int i = 0;
int j = 0;
int current_minimun_weight = 1;
long tmp_symdrome = 0;
int find_flag =1;
init_nTupleVecMarkTab();
Symdrome_Table[0][0] = 0;
Symdrome_Table[0][1] = Cyc_Syndrome_computation_CKT(0);
fprintf(f1, "\n\n------------------------");
fprintf(f1, "\nshow symdrome table");
fprintf(f1, "\n\n##############");
fprintf(f1, "\n\nRow# Error Pattern Syndrome");
Symdrome_Table[0][0] = 0;
Symdrome_Table[0][1] = Cyc_Syndrome_computation_CKT(0);
fprintf(f1, "\n%4d ", 0);
display_Polynomial(Symdrome_Table[0][0], 21);
fprintf(f1, ": ");
display_Polynomial(Symdrome_Table[0][1], 10);
for (i=1; i<1024; i++)
{
/* find_flag =0;
while (!find_flag)
{ */
/* find the next available coset leader with the minimum weight*/
tmp_cosetLeader = find_nextCosetLeader(¤t_minimun_weight);
tmp_symdrome = Cyc_Syndrome_computation_CKT(tmp_cosetLeader);
/* for (j=0; j<i; j++)
{
if (tmp_symdrome == Symdrome_Table[j][1]) {
nTupleVecMarkTab[tmp_cosetLeader] = 1;
find_flag = 0;
break;
}
}
if (j==i) {
find_flag = 1;
printf("\nfind %2d", i);
}
} */
Symdrome_Table[i][0] = tmp_cosetLeader;
Symdrome_Table[i][1] = Cyc_Syndrome_computation_CKT(tmp_cosetLeader);
for (j=1; j<2048; j++)
{
tmp_long1 = add_Polynomial(tmp_cosetLeader, codeWord[j]);
nTupleVecMarkTab[tmp_long1] = 1;
}
printf("\nfind %2d", i);
fprintf(f1, "\n%4d ", i);
display_Polynomial(Symdrome_Table[i][0], 21);
fprintf(f1, ": ");
display_Polynomial(Symdrome_Table[i][1], 10);
}
fprintf(f1, "\n------------------------\n");
}
/****************************************************************/
/* 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 */
/****************************************************************/
long find_nextCosetLeader(int *cur_min_weight)
{
int find_flag = 0;
long ret_cosetLeader = 0;
long 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: getPolynomialBit */
/*--------------------------------------------------------------*/
/* FUNCTION: Get the specific bit of polynomial */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* p1: the polynomial from which get the bit */
/* bitPos: the position of the bit to be get */
/* */
/* OUTPUT: */
/* RetVal: the value of the specific bit(1 or 0) */
/* */
/****************************************************************/
long getPolynomialBit(long p1, int bitPos)
{
long tmp_retVal = 0;
tmp_retVal = (p1 & Vector_Get_Bit_Array[bitPos]) >> bitPos;
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: muliply_Polynomial */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the Multiplication of two polynomials */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* p1: one polynomial(one of the multiplier) */
/* p2: one polynomial(one of the multiplier) */
/* p2Len: length of p2 */
/* */
/* OUTPUT: */
/* RetVal: the result of the multiplication */
/* */
/****************************************************************/
long muliply_Polynomial(long p1,long p2, int p2Len)
{ long tmp_retVal = 0;
long tmp_long1 = 0;
long tmp_long2 = 0;
int i = 0;
/* printf("\n======================"); */
/* printf("\np1(x) = %ld; p2(x)= %ld", p1, p2); */
for (i=0; i<p2Len; i++) {
tmp_long1 = p2 & (Vector_Get_Bit_Array[i]);
if ( tmp_long1 ) {
tmp_long2 = p1 << i;
tmp_retVal = add_Polynomial(tmp_retVal, tmp_long2);
}
}
/* printf("\np1(x)*p2(x)=%ld", tmp_retVal); */
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: div_Polynomial */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the Division of two polynomials */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* p_n: the nominator polynominal */
/* p_dn: the denominator polynominal */
/* */
/* OUTPUT: */
/* RetVal: the quotient of the division */
/* remainder: the remainder of the division */
/* */
/****************************************************************/
long div_Polynomial(long p_n,long p_dn, long* remainder)
{
long tmp_RetVal = 0;
long tmp_Remainder = 0;
int degree1 = 0;
int degree2 = 0;
long tmp_Long1 = 0;
long tmp_Long2 = 0;
int tmp_Int1 = 0;
int testCount=0;
degree1 = getPolynomialDeg(p_n);
degree2 = getPolynomialDeg(p_dn);
while (degree1 >= degree2)
{
/* printf("\n count=%8d",testCount++);
printf("\ndegree of nominator %d", degree1);
printf("\ndegree of denominator %d\n", degree2); */
tmp_Long2 = Vector_Get_Bit_Array[degree1-degree2];
/* printf("\n tmp_Long2=%ld", tmp_Long2); */
tmp_RetVal = add_Polynomial(tmp_RetVal, tmp_Long2);
/* printf("\n tmp_RetVal=%ld", tmp_RetVal);*/
tmp_Int1 = getPolynomialDeg(tmp_Long2);
/* printf("\n tmp_tmp_Int1=%ld", tmp_Int1); */
tmp_Long1 = muliply_Polynomial(p_dn, tmp_Long2, tmp_Int1+1);
/* printf("\n tmp_Long1=%ld", tmp_Long1); */
p_n = add_Polynomial(p_n, tmp_Long1);
/* printf("\n p_n=%ld", p_n); */
degree1 = getPolynomialDeg(p_n);
degree2 = getPolynomialDeg(p_dn);
}
*remainder = p_n;
return(tmp_RetVal);
}
/****************************************************************/
/* MODULE NAME: add_Polynomial */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the Addition of two polynomials */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* a1: one polynomial */
/* a2: one polynomial */
/* */
/* OUTPUT: */
/* RetVal: the result of the addition */
/* */
/****************************************************************/
long add_Polynomial(long a1,long a2)
{
long tmp_retVal = 0;
/* printf("\n====================="); */
/* printf("a1=%5d; a2=%5d", a1, a2); */
tmp_retVal = ((~a1) & a2) | (a1 & (~a2));
/* printf("\na1(x)+a2(x)= %5ld", tmp_retVal);*/
return(tmp_retVal);
}
/****************************************************************/
/* MODULE NAME: display_Polynomial */
/*--------------------------------------------------------------*/
/* FUNCTION: display polynomial */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* p: the polynomial to be displayed */
/* v_Len: length of the polynomial to be displayed */
/* */
/* OUTPUT: */
/* */
/****************************************************************/
void display_Polynomial(long p, int v_Len)
{
int i = 0;
int tmp_int1 = 0;
v_Len--;
for (i=0; i<=v_Len; i++) {
tmp_int1 = (p & (Vector_Get_Bit_Array[i])) >> i;
fprintf(f1, "%d", tmp_int1);
}
}
/****************************************************************/
/* MODULE NAME: show_encode_result */
/*--------------------------------------------------------------*/
/* FUNCTION: Show encode result */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* m_name: < char * > encode method name */
/* ori_vec: < long > message to be encoded */
/* ori_vecLen: < int > message length */
/* en_vec: < long > encoded vector */
/* en_vecLen: < int > encoded vector length */
/****************************************************************/
void show_encode_result(char *m_name, long ori_vec, int ori_vecLen, long en_vec, int en_vecLen)
{
fprintf(f1, "\n------------------------------------------------\n");
fprintf(f1, "Encode the original message using %s\n", m_name);
fprintf(f1, "**************************\n");
fprintf(f1, "original message = ");
display_Polynomial(ori_vec, ori_vecLen);
fprintf(f1, "\nencoded codeword = ");
display_Polynomial(en_vec, en_vecLen);
fprintf(f1, "\n------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: show_decode_result */
/*--------------------------------------------------------------*/
/* FUNCTION: Show encode result */
/*--------------------------------------------------------------*/
/* PARAMETERS: */
/* m_name: < char * > encode method name */
/* rec_vec: < long > message to be encoded */
/* rec_vecLen: < int > message length */
/* de_vec: < long > encoded vector */
/* de_vecLen: < int > encoded vector length */
/****************************************************************/
void show_decode_result(char *m_name, long rec_vec, int rec_vecLen, long de_vec, int de_vecLen)
{
fprintf(f1, "\n------------------------------------------------\n");
fprintf(f1, "Decode the original message using %s\n", m_name);
fprintf(f1, "**************************\n");
fprintf(f1, "received message = ");
display_Polynomial(rec_vec, rec_vecLen);
fprintf(f1, "\ndecoded codeword = ");
display_Polynomial(de_vec, de_vecLen);
fprintf(f1, "\n------------------------------------------------\n");
}
/****************************************************************/
/* MODULE NAME: getPolynomialDeg */
/*--------------------------------------------------------------*/
/* FUNCTION: Calculate the polynomial's degree */
/*--------------------------------------------------------------*/
/* PARAMETER: */
/* ============== */
/* INPUT: */
/* p: the polynominal whose degree is to be calculated */
/* */
/* OUTPUT: */
/* RetVal: the degree of the polynomial */
/* */
/****************************************************************/
int getPolynomialDeg(long p)
{
long tmp_Long1 = 0;
int i;
for (i=30; i>=0; i--) {
tmp_Long1 = (p & (Vector_Get_Bit_Array[i])) >> i;
if (tmp_Long1)
break;
}
if (i<0) i = 0;
return i;
}
Go back to My Homepage