main.cpp

已知LDPC码的稀疏交验矩阵H

//Calculate the girth and local girth of LDPC codes given the H 
//已知LDPC码的稀疏交验矩阵H，计算girth和local girth
//Author: Zhang Xiqing
//Sam 2008-07-22
//参考文献:ldpc码理论与应用，袁东风，2008.4,P59
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

#include "BigGirth.h"
#include "Random.h"
#include "CyclesOfGraph.h"
#define INF  1e+6
using namespace std;
int main()
{
  int i, j,k, m,n, N, M,K;
 char HName[100];
 map<int,int> girth_dist;


///////////////////////////////////

///////////////////////////////////

  //strcpy(HName, "drm_H_msc_10_20.txt");
  //  strcpy(HName, "H_PEG_518x1024.txt");
 strcpy(HName, "drm_H_msc_279x1080chong04.txt"); //H 在该文件之中以稀疏矩阵表示!

 
  
  ifstream infn(HName);
  if (!infn) {std::cout<< "\nCannot open file " << infn << endl;
             exit(-1); } 
  infn >>M;
  infn >>N;
std::cout<<"sam00"<<endl;
   ///////////////////////////////////
  int *symbolDegSequence=new int[N];
  int *checkDegSequence=new int[M];
   int * H_out=new int [N*M];
    int * H_normal=new int [M*N];

    for(i=0;i<N;i++){
             for(j=0;j<M;j++){
                H_out[i*M+j]=0;
			 }
	}

	    for(i=0;i<M;i++){
             for(j=0;j<N;j++){
                H_normal[i*N+j]=0;
			 }
	}
    
    for(j=0;j<N;j++){
        symbolDegSequence[j]=0;
	}


	for(i=0;i<M;i++){
             checkDegSequence[i]=0;
	}
	///////////////////////////////////
	   NodesInGraph *nodesInGraph;
   nodesInGraph=new NodesInGraph [N]; 
	////////////////setNumOfConnectionSymbolBit 列数据///////////////////

  for(i=0;i<N;i++){
	  infn >>m;                   //0=<m<=M-1
	  symbolDegSequence[i]=m;
	  nodesInGraph[i].setNumOfConnectionSymbolBit(symbolDegSequence[i]);  //符号比特数据
	 // std::cout<<"symbolDegSequence["<<i<<"] : "<<symbolDegSequence[i]<<endl;

	  for(j=0;j<m;j++){
		  infn >>k;
		  checkDegSequence[k]++;  //0=<k<=M-1
	      H_out[i*M+k]=1; 
		  H_normal[i+k*N]=1;
		  nodesInGraph[i].connectionSymbolBit[j]=k;
	  }
	}

  infn.close(); 
  infn.clear(); 
  map<int,int> degree_symbol;
  map<int,int> degree_check;
  map<int,int>::const_iterator it_degree;
  int total_symbol=0;
  int total_check=0;
////////////
    ofstream fout_symbolDegSequence("test/drm_H_msc_279x1080chong04symbolDegSequence.txt");////////////////ofstreamofstream33
    ofstream fout_checkDegSequence("test/drm_H_msc_279x1080chong04checkDegSequence.txt");  ////////ofstreamofstreamofstream004
	 
	fout_symbolDegSequence.unsetf(ostream::floatfield);    
	fout_checkDegSequence.unsetf(ostream::floatfield);
	std::cout.unsetf(ostream::floatfield);

	 for(i=0;i<N;i++){
       fout_symbolDegSequence<<i<<" "<<symbolDegSequence[i]<<endl;
	   ++degree_symbol[symbolDegSequence[i]];
	   total_symbol+=symbolDegSequence[i];
	 }
         for(i=0;i<M;i++){
			 fout_checkDegSequence<<i<<" "<<checkDegSequence[i]<<endl;
			 	   ++degree_check[checkDegSequence[i]];
				   total_check+=checkDegSequence[i];
		 }
 /*计算度分布*/
		 fout_symbolDegSequence<<" degree_symbol:"<<endl;
		 std::cout<<" degree_symbol:"<<endl;
		 for(it_degree=degree_symbol.begin();it_degree!=degree_symbol.end();it_degree++){
			 fout_symbolDegSequence<<it_degree->first<<" "<<it_degree->second<<" "<<(double)it_degree->second/(N+0.0)<<" total_symbol: "<<total_symbol<<endl;	
			 std::cout<<it_degree->first<<" "<<it_degree->second<<" "<<(double)it_degree->second/(N+0.0)<<" "<<total_symbol<<endl;	
		 }
  
		 fout_checkDegSequence<<" degree_check:"<<endl;
		 std::cout<<" degree_check:"<<endl;
		 for(it_degree=degree_check.begin();it_degree!=degree_check.end();it_degree++){
			 fout_checkDegSequence<<it_degree->first<<" "<<it_degree->second<<" "<<(double)it_degree->second/M<<" "<<total_check<<endl;
			 std::cout<<it_degree->first<<" "<<it_degree->second<<" "<<(double)it_degree->second/M<<" "<<total_check<<endl;
		 }

    
fout_symbolDegSequence.close();
fout_symbolDegSequence.clear();
fout_checkDegSequence.close();
fout_checkDegSequence.clear();

	/////////////////////setNumOfConnectionParityBit 行数据//////////////
 
  for(i=0;i<M;i++){
	  nodesInGraph[i].setNumOfConnectionParityBit(checkDegSequence[i]); //校验比特数据
        k=0;

	    for(j=0;j<N;j++){		    
		     if(1==H_normal[i*N+j]){
			  //std::cout<<" i: "<<i<<" k:"<<k<<" j: "<<j<<endl;
			  nodesInGraph[i].connectionParityBit[k]=j;
			  k++;	  
			 }
		}
	//	std::cout<<" i: "<<i<<" k:"<<k<<endl;
	  if(k!=checkDegSequence[i]){
		  std::cout<<"Wrong NodesInGraph, k!=checkDegSequence[i]-1)"<<endl;
		  std::cout<<"k: "<<k<<endl;
		  std::cout<<"checkDegSequence["<<i<<"]-1 :"<<checkDegSequence[i]-1<<endl;
		  exit(-1);
	  
	  }

  }
/**/
   // ofstream fout_H_normal("test/H_PEG279_1080.txt"); //////////////ofstreamofstreamofstream 05
	//	for(i=0;i<M;i++){
		//	for(j=0;j<N;j++){
				
		  //   fout_H_normal<<H_normal[i*N+j]<<" ";
		//	}	 
		//	fout_H_normal<<endl;
	//	}
    delete []H_out;
     H_out=NULL;
    delete []H_normal;
     H_normal=NULL;
  ///every local girth/////////////////////////////////// 
  ofstream fgirth("test/drm_H_msc_279x1080chong04Girth.txt");////////////ofstreamofstreamofstream
  ofstream fgirth_local("test/drm_H_msc_279x1080chong04LocalGirth.txt"); ///////// ofstreamofstreamofstream
  int temp_sym00,temp_sym01,temp_sym02,temp_par01,temp_par02,depth,level0_counter;
  int couter_same=0;

  int girth_H;
  int girth_H_biggest;
 vector<int> girth_local;
 vector<int> level_temp01;
 vector<int> level_temp02;
 map<int,int> num_count;
 map<int,int>::const_iterator map_it;

 for(temp_sym00=0;temp_sym00<N;temp_sym00++)
 {  
	 //fgirth<<"symbol bit "<<temp_sym00<<" begin"<<endl;
	 //fgirth_local<<"symbol bit "<<temp_sym00<<" begin"<<endl;
	 for(i=0;i<M;i++){
	   nodesInGraph[i].ParityBitInCt=false; 
	   nodesInGraph[i].ParityBitInCt_lev=-1;

	}
	 for(i=0;i<N;i++){
	   nodesInGraph[i].SymbolBitInCt=false;
	   nodesInGraph[i].SymbolBitInCt_lev=-1;
	}

  level_temp01.clear();
  level_temp02.clear();
  num_count.clear();

  depth=0;
  level0_counter=0;

  temp_sym01=temp_sym00;

  nodesInGraph[temp_sym00].SymbolBitInCt=true;
  nodesInGraph[temp_sym00].SymbolBitInCt_lev=level0_counter;


  temp_sym02=temp_sym01;
  level_temp02.push_back(temp_sym02);

  

  do{                
	  if(0==level0_counter%2){
		    level0_counter++;
		    for(vector<int>::iterator iter=level_temp02.begin();iter!=level_temp02.end();++iter){
				temp_sym01=*iter;
				   fgirth<<"  Symbol node: "<<temp_sym01<<" have "<<nodesInGraph[temp_sym01].numOfConnectionSymbolBit<<" Parity nodes: "<<endl;
                       for(j=0;j<nodesInGraph[temp_sym01].numOfConnectionSymbolBit;j++){
				          temp_par01=nodesInGraph[temp_sym01].connectionSymbolBit[j];
						  //level_temp01.push_back(temp_par01);//全部放入
                           fgirth<<temp_par01<<" ";//
						     if(!nodesInGraph[temp_par01].ParityBitInCt){//是否已经到达过，但是没有标明是哪一级到达的
								 level_temp01.push_back(temp_par01);
						     //    fgirth<<temp_par01<<" ";// change 部分放入
						         nodesInGraph[temp_par01].ParityBitInCt=true;  
								 nodesInGraph[temp_par01].ParityBitInCt_lev=level0_counter;
							 }	

							 if(level0_counter==nodesInGraph[temp_par01].ParityBitInCt_lev){
								++num_count[temp_par01];						  
							 }
							 

					   }
            fgirth<<endl;
			}  
			fgirth<<" level0_counter: "<<level0_counter<<endl;
				   /*k  级level_temp01上的某一个节点至少与k-1 级 level_temp02上的两个节点相连*/
			map_it=num_count.begin();
			while(map_it!=num_count.end()){
				if(map_it->second>=2){
				goto LOOP;
				}	
				++map_it;
			}
			 num_count.clear();
			 level_temp02.clear();
		   
	   }
	   else{
		    level0_counter++;
		   for(vector<int>::iterator iter=level_temp01.begin();iter!=level_temp01.end();++iter){
			   temp_par01=*iter;
				   fgirth<<"  Check node: "<<temp_par01<<" have "<<nodesInGraph[temp_par01].numOfConnectionParityBit<<" symbol nodes: "<<endl;
				   for(j=0;j<nodesInGraph[temp_par01].numOfConnectionParityBit;j++){	
					   temp_sym02=nodesInGraph[temp_par01].connectionParityBit[j];
                       //level_temp02.push_back(temp_sym02);//全部放入
					   fgirth<<temp_sym02<<" ";
					   if(!nodesInGraph[temp_sym02].SymbolBitInCt){
						level_temp02.push_back(temp_sym02);
					 	//fgirth<<temp_sym02<<" "; //change 部分放入
						nodesInGraph[temp_sym02].SymbolBitInCt=true;
						nodesInGraph[temp_sym02].SymbolBitInCt_lev=level0_counter;
						}

					   if(level0_counter==nodesInGraph[temp_sym02].SymbolBitInCt_lev){
								++num_count[temp_sym02];						  
							 }
					 }				   		   
	
         fgirth<<endl;
		   }
		     
			 fgirth<<" level0_counter: "<<level0_counter<<endl;

			 	   /*k  级level_temp01上的某一个节点至少与k-1 级 level_temp02上的两个节点相连*/
			 map_it=num_count.begin();
			while(map_it!=num_count.end()){
				if(map_it->second>=2){
				goto LOOP;
				}	
				++map_it;
			}

			 num_count.clear();
	         level_temp01.clear();  
	   }


    

	 }while(!level_temp02.empty()||!level_temp01.empty()); //不可能结束了
    goto LOOP2;

     LOOP:
	 fgirth<<" map_it->second>=2 over "<<endl;
	 fgirth<<"map_it->first: "<<map_it->first<<" map_it->second: "<<map_it->second<<endl;
	 	 fgirth<<" for symbol "<<temp_sym00<<" the local level is"<<level0_counter<<endl;
	 fgirth_local<<" for symbol bit "<<temp_sym00<<" the local girth is: "<<2*level0_counter<<endl;
	  girth_local.push_back(2*level0_counter);

	 LOOP2:
	 if(num_count.empty()){
		 //没有形成 cycle
	 fgirth<<" while over "<<endl;
	 	 fgirth<<" for symbol "<<temp_sym00<<" the local level is"<<level0_counter<<endl;
	 fgirth_local<<" for symbol bit "<<temp_sym00<<" the local girth is: "<<INF<<endl;	
	 girth_local.push_back(INF);
	 }
 
}



        girth_H=INF;
		girth_H_biggest=0;
       for(vector<int>::iterator iter_girth=girth_local.begin();iter_girth!=girth_local.end();++iter_girth){
		   if(*iter_girth<girth_H){
			   girth_H=*iter_girth;
		   }
		    if(*iter_girth>girth_H_biggest){
			   girth_H_biggest=*iter_girth;
		   }
			++girth_dist[*iter_girth];
	   }
	   std::cout<<"the girth of this H is: "<<girth_H<<endl;
	   std::cout<<"the biggest local girth of this H is: "<<girth_H_biggest<<endl;




/*公布结果*/
map<int,int>::iterator map_it2;
double map_it2_second;	
    
    fgirth_local.unsetf(ostream::floatfield);
	std::cout.unsetf(ostream::floatfield);
for(map_it2=girth_dist.begin();map_it2!=girth_dist.end();map_it2++){
	std::cout<<"the "<<map_it2->first<<"  local girth of this H is: "<<map_it2->second<<" that is sa "<<(double)map_it2->second/(N+0.0)<<endl;
	map_it2_second=map_it2->second/(N+0.0);//(N+0.0)+0.0;
	std::cout<<map_it2_second<<endl;
	fgirth_local<<"the number of local girth"<<map_it2->first<<" in this H is: "<<map_it2->second<<" that is :"<<map_it2_second<<" in total"<<endl;
}
for(iter_girth=girth_local.begin();iter_girth!=girth_local.end();++iter_girth){
	fgirth_local<<*iter_girth<<" ";
}
fgirth_local<<endl;
fgirth.close();
fgirth.clear();
fgirth_local.close();
fgirth_local.clear();

//fout_H_normal.close();
//fout_H_normal.clear();
	////////求解说明：进行生成树的展开，同时在该树上求解最小的cycle,不足之处：可能不严密！！为什么都是4呢？尝试课本上的方法进行对比！///////////////////////////
  

   
std::cout<<"sam100"<<endl;

   delete []symbolDegSequence; 
   symbolDegSequence=NULL;

   
   delete []checkDegSequence;
   checkDegSequence=NULL;
   //int *checkDegSequence=new int[M];
   //delete []H_out;
   //H_out=NULL;

   //delete NodesInGraph;
   //nodesInGraph=new NodesInGraph [N];

   
return 0;
}