generating_matrix.cpp

低密度奇偶校验码中编码矩阵的c实现程序,不错

#include "LDPC_head.h"
#include <stdlib.h>

matrix_bit *Gen(unsigned int M, unsigned int N, unsigned int t)
{
	matrix_bit *Matrix;
	unsigned int *col;
	unsigned int *row;
	unsigned int *check;
	unsigned int i;
	unsigned int j;
	unsigned int k;
	unsigned int l;
	unsigned int rank;
	unsigned int retry;
	long now;


	//apply for the coresponding space
	Matrix=(struct matrix_bit *)malloc (sizeof(struct matrix_bit));
	Matrix->row=M;
	Matrix->col=N;
	Matrix->H=(unsigned int *) malloc (sizeof(unsigned int)*(N-M)*N);
	Matrix->G=(unsigned int *) malloc (sizeof(unsigned int)*M*N);
	for(j=0;j<N;j++)
	{
		for(i=0;i<M;i++)
		{
			Matrix->G[i*N+j]=0;
		}
	}


	col=(unsigned int *)malloc ((sizeof(unsigned int))*N);
	for(i=0;i<N;i++)
	{
		col[i]=0;
	}
	row=(unsigned int *)malloc ((sizeof(unsigned int))*N);

	//generate the H at random
loop1:
	for(j=0;j<N;j++)
	{
		for(i=0;i<N-M;i++)
		{
			Matrix->H[i*N+j]=0;
		}
	}

	for(i=0;i<N-M;i++)
	{
		row[i]=0;
	}
	retry=0;
	srand(time(&now));
	for(j=0;j<N;j++)
	{
		for(k=0;k<t;k++)
		{
			i=rand()%(N-M);
			if((Matrix->H[i*N+j]==0)&&(row[i]<(double)(t*N/(N-M))))
			{
				Matrix->H[i*N+j]=1;
				row[i]++;
			}else
			{
				k--;
				retry++;
				if(retry>N*(N-M))
				{
					goto loop1;
				}
			}
		}
	}
	//check if H is full rank
	check=(unsigned int *)malloc ((sizeof(unsigned int))*(N-M)*N);
	for(i=0;i<N-M;i++)
	{
		for(j=0;j<N;j++)
		{
			check[i*N+j]=Matrix->H[i*N+j];
//			cout<<check[i*N+j]<<"  ";
		}
//		cout<<endl;
	}
	//change H into upper triangle form when check the rank of H
	rank=0;
	for(j=0;j<N;j++)
	{
		for(i=rank;i<N-M;i++)
		{
			if(check[i*N+j]==1)
			{
//				cout<<"("<<rank<<","<<j<<")"<<endl;
				for(k=0;k<N;k++)
				{
					col[k]=check[i*N+k];
					check[i*N+k]=check[rank*N+k];
					check[rank*N+k]=col[k];
				}
				for(k=i+1;k<N-M;k++)
				{
					if(check[k*N+j]==1)
					{
						for(l=j;l<N;l++)
						{
							check[k*N+l]^=check[rank*N+l];
						}
					}
				}
				rank++;
/*
				for(k=0;k<N-M;k++)
				{
					for(l=0;l<N;l++)
					{
						cout<<check[k*N+l]<<"  ";
					}
					cout<<endl;
				}
*/
				break;
			}
		}
	}
/*
	cout<<"arranged!-------"<<endl;
	for(i=0;i<N-M;i++)
	{
		for(j=0;j<N;j++)
		{
			cout<<check[i*N+j]<<"  ";
		}
		cout<<endl;
	}
*/
//	cout<<rank<<endl;
	if(rank!=N-M)
	{
//		cout<<"not full rank"<<endl;
//		getchar();
		goto loop1;
	}
	//re-arrange H matrix
	//exchange the columns of H to change H into standard upper triangle form
	for(i=0;i<N-M;i++)
	{
		j=i;
		while(check[i*N+j]==0)
		{
			j++;
		}
		if(j>=N)
		{
			cout<<j<<"  Error!"<<endl;
			getchar();
		}
		if(i!=j)
		{
			for(k=0;k<N-M;k++)
			{
				row[k]=Matrix->H[k*N+i];
				Matrix->H[k*N+i]=Matrix->H[k*N+j];
				Matrix->H[k*N+j]=row[k];

				row[k]=check[k*N+i];
				check[k*N+i]=check[k*N+j];
				check[k*N+j]=row[k];
			}
		}
	}
	//change H into unit matrix + P matrix form
	for(j=0;j<N-M;j++)
	{
		for(i=0;i<j;i++)
		{
			if(check[i*N+j]==1)
			{
				for(k=0;k<N;k++)
				{
					check[i*N+k]^=check[j*N+k];
				}
			}
		}
	}
	// check if there is all-zero column in it
	for(j=N-M;j<N;j++)
	{
		k=1;
		for(i=0;i<N-M;i++)
		{
			if(check[i*N+j]==1)
			{
				k=0;
				break;
			}
		}
	}
	if(k)
	{
		goto loop1;
	}
	//generate G
	for(i=0;i<N-M;i++)
	{
		for(j=N-M;j<N;j++)
		{
			Matrix->G[(j-(N-M))*N+i+M]=check[i*N+j];
		}
	}
	for(i=0;i<M;i++)
	{
		Matrix->G[i*N+i]=1;
	}
	//rearrange H in to standard form
	for(i=0;i<N-M;i++)
	{
		for(j=0;j<N;j++)
		{
			check[i*N+j]=Matrix->H[i*N+j];
		}
	}
	for(i=0;i<N-M;i++)
	{
		for(j=0;j<N;j++)
		{
			Matrix->H[i*N+j]=check[i*N+(j+M)%N];
		}
	}
	return(Matrix);


}