biggirth.c

PROGRASSIVE EDGE GROWTH 累加边增加LDPC算法

  for(i=0;i<M;i++){
    for(j=0;j<N;j++){
      H[i][j]=0;
    }
  }
  for(i=0;i<M;i++){
    for(j=0;j<nodesInGraph[i].numOfConnectionParityBit;j++){
      H[i][nodesInGraph[i].connectionParityBit[j]]=1;
    }
  }
}

void BigGirth::writeToFile_Hmatrix(void){
  int i, j;

  loadH();

  //cout<<"---------------code format--------------------------"<<endl;
  //cout<<"-            Block length N                        -"<<endl;
  //cout<<"-            Num of Check Nodex M                  -"<<endl;
  //cout<<"-            H matrix                              -"<<endl;
  //cout<<"----------------------------------------------------"<<endl;

  ofstream codefile;  
  codefile.open(filename,ios::out);
  codefile<<N<<" "<<M<<endl;

  for(i=0;i<M;i++){
    for(j=0;j<N;j++){
      codefile<<H[i][j]<<" ";
    }
    codefile<<endl;
  }
  codefile.close();
}

void BigGirth::writeToFile_Hcompressed(void){
  int i, j, max_col;
  int *(*parityCheck_compressed);

  //cout<<"---------------code format--------------------------"<<endl;
  //cout<<"-            Block length N                        -"<<endl;
  //cout<<"-            Num of Check Nodex M                  -"<<endl;
  //cout<<"-            Num of column in the compressed H     -"<<endl;
  //cout<<"-            H matrix (compressed)                 -"<<endl;
  //cout<<"----------------------------------------------------"<<endl;

  //finding the num of columns, l, of the compressed parity-check matrix

  max_col=0;
  for(i=0;i<M;i++)
    if(nodesInGraph[i].numOfConnectionParityBit>max_col) 
      max_col=nodesInGraph[i].numOfConnectionParityBit;

  parityCheck_compressed=new int * [M];
  for(i=0;i<M;i++)
    parityCheck_compressed[i]=new int[max_col];
  for(i=0;i<M;i++){
    for(j=0;j<max_col;j++) parityCheck_compressed[i][j]=0;
    for(j=0;j<nodesInGraph[i].numOfConnectionParityBit;j++){
      parityCheck_compressed[i][j]=nodesInGraph[i].connectionParityBit[j]+1; 
    }
  }

  ofstream codefile;  
  codefile.open(filename,ios::out);
  codefile<<N<<endl;
  codefile<<M<<endl;
  codefile<<max_col<<endl;
  for(i=0;i<M;i++){
    for(j=0;j<max_col;j++)
      codefile<<parityCheck_compressed[i][j]<<" ";
    codefile<<endl;
  }
  codefile.close();

  for(i=0;i<M;i++){
    delete [] parityCheck_compressed[i];
    parityCheck_compressed[i]=NULL;
  }
  delete [] parityCheck_compressed;
  parityCheck_compressed=NULL;
}

void BigGirth::writeToFile(void){
  int i, j, k, d, redun;
  int imed, max_row, index, max_col;
  int *Index, *J, *itmp, *(*generator), *(*generator_compressed), *(*parityCheck_compressed);
  //Gaussian Ellimination    
  Index=new int[M];
  J=new int[N];
  itmp=new int[N];
  for(i=0;i<M;i++) Index[i]=0; //indicator of redudant rows 
  for(j=0;j<N;j++) J[j]=j; //column permutation
  redun=0;//the number of redundant rows

  loadH();
  
  for(k=0;k<M;k++){
    if(H[k][J[k-redun]]==0) {    
      d=k;
      for(i=k+1-redun;i<N;i++)
	if(H[k][J[i]]!=0) {d=i;break;}
      if(d==k) {//full-zero row:delete this row
	redun++;
	Index[k]=1;
	continue;
      }	
      else {//SWAP d column and k column in H matrix
	imed=J[k-redun];
	J[k-redun]=J[d];
	J[d]=imed;
      }
    }
    if(H[k][J[k-redun]]==0) {
      cout<<"ERROR: should not come to this point"<<endl;
      exit(-1);
    }
    else {
      for(i=k+1;i<M;i++){
	if(H[i][J[k-redun]]!=0){
	  for(j=k-redun;j<N;j++)
	    H[i][J[j]]=(H[i][J[j]]+H[k][J[j]])%2;
	}
      }
    }
  }

  cout<<"Row rank of parity check matrix="<<M-redun<<endl;

  K=N-M+redun;//num of the information bits

  index=0;
  for(i=0;i<M;i++){
    if(Index[i]==0){ // all-zero row
      for(j=0;j<N;j++)
	itmp[j]=H[i][J[j]];
      for(j=0;j<N;j++)
	H[index][j]=itmp[j]; //Note: itmp can not be omitted here!!!
      index++;
    }
  }
  if(index!=M-redun) {cout<<"ERRor...if(index!=M-redun)"<<endl;exit(-1);}

  for(k=index-1;k>0;k--){
    for(i=k-1;i>=0;i--){
      if(H[i][k]==1)
	for(j=k;j<N;j++)
	  H[i][j]=(H[i][j]+H[k][j])%2;
    }
  }  
 
  cout<<"****************************************************"<<endl;
  cout<<"      Computing the compressed generator"<<endl;
  cout<<"****************************************************"<<endl;
  generator=new int * [K];
  for(i=0;i<K;i++)
    generator[i]=new int[N-K];
  for(i=0;i<K;i++){
    for(j=0;j<N-K;j++)
      generator[i][j]=H[j][i+N-K];
    //for(j=N-K;j<N;j++)
    //generator[i][j]=0;
    //generator[i][i+N-K]=1;
  } 
  max_row=0;
  for(j=0;j<N-K;j++){
    imed=0;
    for(i=0;i<K;i++)
      imed+=generator[i][j];
    if(imed>max_row) max_row=imed;
  }
  generator_compressed=new int * [max_row];
  for(i=0;i<max_row;i++)
    generator_compressed[i]=new int[N];
  for(j=0;j<N-K;j++){
    index=0;
    for(i=0;i<max_row;i++)  generator_compressed[i][j]=0;
    for(i=0;i<K;i++){
      if(generator[i][j]==1) {
	generator_compressed[index][j]=i+1;
	if(index>=max_row-1) break;
	index++;
      }
    }
  }
  for(j=0;j<K;j++){
    for(i=0;i<max_row;i++) generator_compressed[i][j+N-K]=0;
    generator_compressed[0][j+N-K]=j+1;
  }
  cout<<"*****************************************************"<<endl;
  cout<<"     Computing the compressed parity-check matrix"<<endl;
  cout<<"*****************************************************"<<endl;  
  //finding the num of columns, l, of the compressed parity-check matrix
  loadH(); //loading parity check matrix again
  max_col=0;
  for(i=0;i<M;i++){
    imed=0;
    for(j=0;j<N;j++)
      imed+=H[i][j];
    if(imed>max_col) max_col=imed;
  }
  parityCheck_compressed=new int * [M];
  for(i=0;i<M;i++)
    parityCheck_compressed[i]=new int[max_col];
  for(i=0;i<M;i++){
    for(j=0;j<max_col;j++) parityCheck_compressed[i][j]=0;
    index=0;
    for(j=0;j<N;j++){
      if(H[i][J[j]]==1) {
	parityCheck_compressed[i][index]=j+1; 
	if(index>=max_col-1) break;
	index++;
      }
    }
  }
  cout<<"****************************************************"<<endl;
  cout<<"      Write to file (TEXT!) "<<endl;
  cout<<"****************************************************"<<endl;  
  ofstream codefile;  
  codefile.open(filename,ios::out);
  codefile<<N<<endl;
  codefile<<K<<endl;
  codefile<<M<<endl;
  codefile<<max_row<<endl;
  codefile<<max_col<<endl;
  for(i=0;i<max_row;i++){
    for(j=0;j<N;j++)
      codefile<<generator_compressed[i][j]<<" ";
    codefile<<endl;
  }
  for(i=0;i<M;i++){
    for(j=0;j<max_col;j++)
      codefile<<parityCheck_compressed[i][j]<<" ";
    codefile<<endl;
  }
  for(i=N-K;i<N;i++)
    codefile<<i+1<<" ";
  codefile<<endl;

  codefile.close();
   cout<<"****************************************************"<<endl;
  cout<<"      Free memory"<<endl;
  cout<<"****************************************************"<<endl;
  delete [] Index;
  Index=NULL;
  delete [] J;
  J=NULL;
  delete [] itmp;
  itmp=NULL;
  for(i=0;i<M;i++){
    delete [] parityCheck_compressed[i];
    parityCheck_compressed[i]=NULL;
  }
  delete [] parityCheck_compressed;
  parityCheck_compressed=NULL;
  for(i=0;i<max_row;i++){
    delete [] generator_compressed[i];
    generator_compressed[i]=NULL;
  }
  delete [] generator_compressed;
  generator_compressed=NULL;
  for(i=0;i<K;i++){
    delete [] generator[i];
    generator[i]=NULL;
  }
  delete [] generator;
  generator=NULL;
  
  cout<<"****************************************************"<<endl;
  cout<<"      OK!"<<endl;
  cout<<"****************************************************"<<endl;   

}