ldpc.c

介绍了ldpc编码相关的设计与实现

#include "LDPC.h"

/************************************************************************************************************************
 * NAME : void init_H_para(short *mat_para, FILE *f_H_data)
 * ABSRTACT : initilize the matrix parameter by reading the data from the file 
 * ENTRY : input : FILE *f_H_data : the exited file download from the Mackay web 
 	   output : short *mat_para : contain these parameters,see detail in program 
 * return: void
 *************************************************************************************************************************/
void init_mat_para(short *mat_para, FILE *f_H_data)
{
	short COLUMN,H_ROW;
	short Max_row_weight, Max_col_weight;//the max weight of the row and column,also suitable for irregular GF(2) LDPC
	
        fscanf(f_H_data,"%hd",&COLUMN);//read from the file
	fscanf(f_H_data,"%hd",&H_ROW);
	fscanf(f_H_data,"%hd",&Max_col_weight);
	fscanf(f_H_data,"%hd",&Max_row_weight);	
	
	mat_para[0] = COLUMN;//matrix column for both H and G
	mat_para[1] = H_ROW;//matrix row for H
	mat_para[2] = mat_para[0] - mat_para[1];//G_ROW : row of Generator matrix
	mat_para[3] = Max_col_weight;
	mat_para[4] = Max_row_weight;
}

/************************************************************************************************************************
 * NAME : void array_sort (short *in , short length , short init_min)
 * ABSTRACT : the total function aims to sort the series in decensend 
 * ENTRY : input : short *in;
                   short length;
                   short init_min;
           output :short *in;
 * RETURN : void
 ***********************************************************************************************************************/
void array_sort (short *in , short length , short init_min)
{
	short i;
	short j;
	short temp;
	short min;
	short min_index;
	
	for(i=0;i<length;i++)
	{
		min = init_min;
		
		//sort the min among the rest datas,record the index
		for(j=i;j<length;j++)
		{
			if(in[j]<min)
			{
				min = in[j];
				min_index  = j;
			}
		}
		
		//change the datas
		temp = in[i];
		in[i] = min;
		in[min_index] = temp;
	}
}

/*************************************************************************************************************************
 * NAME : void Construct_H_Matrix(short *mat_para,short *mat_col,short *mat_row,FILE *f_H_data)
 * ABSTRACT : this function is to construct the H matrix by tracking its 1 postion,not the whole matrix 
 * ENTRY : input : short *mat_para : the same as function init_mat_para()
                   FILE *f_H_data  : the same as function init_mat_para()
           output : short *mat_col : tracking the weigh of '1' in H matrix's column and its postion
                    short *mat_row : tracking the weigh of '1' in H matrix's row and its postion
 * RETURN : void
 ************************************************************************************************************************/
void Construct_H_Matrix(short *mat_para,short *mat_col,short *mat_row,FILE *f_H_data)
{
	short i,j;
	short temp;
	short pos;
	short COLUMN,G_ROW,H_ROW;
	short Max_row_weight , Max_col_weight;
	
	COLUMN = mat_para[0];
	H_ROW  = mat_para[1];
	G_ROW  = mat_para[2];
	Max_col_weight = mat_para[3];
	Max_row_weight = mat_para[4];
	
	//store each column's weight to mat_col
	for(i=0;i<COLUMN;i++)
	{
		fscanf(f_H_data,"%hd",&temp);
		mat_col[i*(Max_col_weight+1)] = temp;		
	}
        
        //store each row's weight to mat_row
	for(i=0;i<H_ROW;i++)
	{
		fscanf(f_H_data,"%hd",&temp);
		mat_row[i*(Max_row_weight+1)] = temp;
	}
	
	//store each column's 1 postion to mat_col in descendly order 
	for(i=0;i<COLUMN;i++)
	{
		temp = mat_col[i*(Max_col_weight+1)];
		
		for(j=1;j<=temp;j++)
		{
			fscanf(f_H_data,"%hd",&pos);
			if(pos==0) j--;
			else mat_col[i*(Max_col_weight+1)+j] = pos-1;
		}
		
		array_sort(&mat_col[i*(Max_col_weight+1)+1],temp,COLUMN);//descendly order
	}
	
	//store each row's 1 postion to mat_row in descendly order 
	for(i=0;i<H_ROW;i++)
	{
		temp = mat_row[i*(Max_row_weight+1)];
		
		for(j=1;j<=temp;j++)
		{
			fscanf(f_H_data,"%hd",&pos);
			if(pos==0) j--;
			else mat_row[i*(Max_row_weight+1)+j] = pos-1;
		}
		
		array_sort(&mat_row[i*(Max_row_weight+1)+1],temp,COLUMN);//descendly order
	}
}

/************************************************************************************************************************
 * NAME : void gauss_elimate_to_P_I (short *mat_col , short *mat_row , short **t , short *rank , short *mat_para)
 * ABSTRACT : this function is aimed to complete gauss elimate
 * ENTRY : input  : short *mat_para : contain these parameters
                    short *mat_col  : tracking the weigh of '1' in H matrix's column and its row postion for each column
                    short *mat_row  : tracking the weigh of '1' in H matrix's row and its column postion for each row
           output : 
           	    short *mat_col  : tracking the weigh of '1' in H matrix's column and its row postion for each column after ordering
                    short *mat_row  : tracking the weigh of '1' in H matrix's column and its column postion for each row after ordering 	
           	    short **t : H matrix after reorder
                    short *rank : 
 * RETURN : void
 ************************************************************************************************************************/		
void gauss_elimate_to_P_I (short *mat_col , short *mat_row , short **t , short *rank , short *mat_para)
{
	int	i;
	int j;
	int k;
	short  reorder_flag=0;
	short  temp;
	short  delta;
	short  COLUMN;
	short  G_ROW;
	short  H_ROW;
	short  Max_row_weight;
	short  Max_col_weight;
	short  *temp_col;
	
	COLUMN = mat_para[0];
	H_ROW  = mat_para[1];
	G_ROW  = mat_para[2];
	Max_col_weight = mat_para[3];
	Max_row_weight = mat_para[4];

	if ((temp_col = (short *) malloc(sizeof(short)*(Max_col_weight+1))) == NULL)
	{
		printf("can not malloc \n");
	}
	
	while(reorder_flag>=0)
	{
		reorder_flag = -1;
		
		memset((*t),0,sizeof(short)*H_ROW*COLUMN);//(* t)[] is a pointer varibles pointing to a array contain H_ROW*COLUMN element
		
		//build the H matrix
		for(i=0;i<COLUMN;i++)
		{
			temp = mat_col[i*(Max_col_weight+1)];//Max_col_weight of this column
			for(j=1;j<=temp;j++)
			{
				(*t)[ mat_col[i*(Max_col_weight+1)+j] * COLUMN + i ] = 1;//mat_col[i*(Max_col_weight+1)+j] is the 1's row position
			}
		}//so we have the H matrix here
		
		//try to convert the matrix to [P|I]
		for(i=1;i<=H_ROW;i++)
		{
			//detect if the t[H_ROW-i][COLUMN-i]==1,and try to set it
			if((*t)[(H_ROW-i+1)*COLUMN-i] == 0)
			{
				j = i+1;
				while(j<=H_ROW)
				{
					if((*t)[(H_ROW-j+1)*COLUMN-i] == 1)
					{
						for(k=0;k<COLUMN;k++)
						{
							(*t)[(H_ROW-i)*COLUMN + k] 
							= (*t)[(H_ROW-i)*COLUMN + k] ^ (*t)[(H_ROW-j)*COLUMN + k];
						}	
						j = H_ROW;//if there is 1 in the upper tringle matrix,end up loop;
					}
					j++;
				}
			}
			//detect if the t[H_ROW-i][COLUMN-i]==1,and try to set it
			
			//after setting through above operations
			//detect whether t[H_ROW-i][COLUMN-i] set successfully
			//if not succeed, set the reorder_flag = index of that column
			if(((*t)[(H_ROW-i+1)*COLUMN-i]==0)&&(reorder_flag<0))
			{
				reorder_flag = COLUMN-i;//can know the index of that column
			}
			
			//cancel the other 1 position in (COLUMN-i) column of the upper tringle matrix
			for(j=i+1;j<=H_ROW;j++)
			{
				if((*t)[(H_ROW-j+1)*COLUMN-i] == 1)
				{
					for(k=0;k<COLUMN;k++)
					{
						(*t)[(H_ROW-j)*COLUMN + k]
					        = (*t)[(H_ROW-j)*COLUMN + k] ^ (*t)[(H_ROW-i)*COLUMN + k];
					}
					        
				}
			}
			//cancel the other 1 position in (COLUMN-i) column of the upper tringle matrix
		}
		//try to convert the matrix to [P|I]
		//so there are all 0 in (COLUMN-i) column of the upper tringle matrix
		//H_matrix becomes a nether triangle matrix	
			
		//construct [P|I]
		for(j=G_ROW;j<COLUMN;j++)
		{
			for(i=(j-G_ROW+1);i<H_ROW;i++)
			{
				if((*t)[i*COLUMN + j] == 1)
				{
					for(k=0;k<COLUMN;k++)
					{
						(*t)[i*COLUMN + k]
						= (*t)[i*COLUMN + k] ^ (*t)[(j-G_ROW)*COLUMN + k];
					}
				}
			}
		}
		//construct [P|I]
		
		//detect all zero row 
		i=0;
		j=0;
		temp=0;
		delta=0;
		
		while(i<H_ROW)
		{
			j=0;
			while(j<COLUMN)
			{
				if((*t)[i*COLUMN + j] !=0)
				{
					j = COLUMN;
					delta ++ ;//if the row number which has 1, delta ++,then escape this row
				}
				
				j++;
			}
			
			if((delta-temp)==0)
			{
				delta++;
				temp++;//the zero row number
			}
			
			i++;
		}
		
		(*rank) = temp;//the number of zero row
		
		//right to be the first rows,so no need to reord culumn
		if((COLUMN-reorder_flag+temp-1)==H_ROW)		reorder_flag=-1;
	        //detect all zero row
	        
	        //for test
		//printf("%d\n",reorder_flag);
		//for test
		
		//if reorder_flag ,reorder column
		if(reorder_flag>=0)		
		{
			//store the all zeros row's postion temparoly
			for(j=0;j<=Max_col_weight;j++)
				temp_col[j] = mat_col[reorder_flag*(Max_col_weight+1)+j];
                        
                        //column shift
			for(k=(reorder_flag-1);k>=0;k--)
				for(j=0;j<=Max_col_weight;j++)
					mat_col[(k+1)*(Max_col_weight+1)+j] = mat_col[k*(Max_col_weight+1)+j];

			for(j=0;j<=Max_col_weight;j++)	mat_col[j] = temp_col[j];
		}
		//if reorder_flag ,reorder column

	} //end of while 

	free(temp_col);
}

/****************************************************************************************************************
 * NAME : void Construct_G_Matrix (short *mat_col , short *mat_row , short **p_gen, short *mat_para)
 * ABSTRACT : constuct G matrix
 * ENTRY : input : short *mat_col :
                   short *mat_row :
                   short *mat_para:
           output : short **p_gen : G matrix
 * RETURN : void
 ****************************************************************************************************************/
void Construct_G_Matrix (short *mat_col , short *mat_row , short **p_gen, short *mat_para)
{
        int	i,j,k;
	short   *t;
	short	*gen;
	short   reorder_flag=0,temp;
	short   COLUMN , G_ROW , H_ROW;
	short   Max_row_weight , Max_col_weight;

	COLUMN = mat_para[0];
	H_ROW  = mat_para[1];
	G_ROW  = mat_para[2];
	Max_col_weight = mat_para[3];
	Max_row_weight = mat_para[4];
	gen = *p_gen;

	if ((t = (short *) malloc(sizeof(short)*(H_ROW*COLUMN))) == NULL)
	{
		printf("can not malloc \n");
	}

	gauss_elimate_to_P_I(mat_col,mat_row,&t,&temp,mat_para);

	printf("the system check_sum matrix\n");

	/*construct generate matrix*/
	G_ROW = G_ROW + temp;
	mat_para[2] = G_ROW;

	if(temp!=0)
	{
		free(gen);
		if ((gen = (short *) malloc(sizeof(short)*(G_ROW*COLUMN))) == NULL)
			printf("can not malloc \n");
	}

	for(i=0;i<G_ROW;i++)
		for(j=0;j<G_ROW;j++)
			if(i==j)	gen[j*COLUMN+i]=1;
			else		gen[j*COLUMN+i]=0;	
	
	for(i=G_ROW;i<COLUMN;i++)
	{
		for(j=0;j<G_ROW;j++)
		{
			gen[j*COLUMN+i] = t[(i-G_ROW+temp)*COLUMN+j];			
		}				
	}	
	printf("the generate matrix\n");

	/*reconstruct the coordinate of checksum matrix row*/		
	//for(i=0;(i<H_ROW*COLUMN);i++)	t[i] = 0;

	memset(t,0,sizeof(short)*H_ROW*COLUMN);		

	for(i=0;i<COLUMN;i++)
	{
		temp = mat_col[i*(Max_col_weight+1)];
		for(j=1;j<=temp;j++)
			t[mat_col[i*(Max_col_weight+1)+j]*COLUMN + i] = 1;
	}

	for(i=0;i<H_ROW;i++)
	{
		k = 1;
		for(j=0;j<COLUMN;j++)
		{
			if(t[i*COLUMN + j] == 1)
			{
				mat_row[i*(Max_row_weight+1)+k] = j;
				k++;
			}				
		}
	}
	*p_gen = gen;
	printf("The G_matrix has been created\n");
	
	/*reconstruct the coordinate of checksum matrix row*/
	free(t);
	
}

/**************************************************************************************************************************
 * NAME     :  void LDPC_init(struct LDPCParam *p_ldpc_param, FILE *fpLDPC)
 * ABSTRACT :  initialize LDPC
 * ENTRY    :  input  : FILE *fpLDPC
 	       output : struct LDPCParam *p_ldpc_param 
 * RETURN   :  void
 *************************************************************************************************************************/
void LDPC_init(struct LDPCParam *p_ldpc_param, FILE *fpLDPC)
{
	short	mat_param[5];

	init_mat_para(mat_param, fpLDPC);
	
	p_ldpc_param->mat_param[0]	=	mat_param[0];//COLUMN
	p_ldpc_param->mat_param[1]	=	mat_param[1];//H_ROW
	p_ldpc_param->mat_param[2]	=	mat_param[2];//G_row
	p_ldpc_param->mat_param[3]	=	mat_param[3];//MAX_COLUMN_WEIGHT
	p_ldpc_param->mat_param[4]	=	mat_param[4];//MAX_ROW_WEIGHT
	p_ldpc_param->MatCol		=	(short*) malloc(mat_param[0]*(mat_param[3]+1)*sizeof(short));