peg.zip_LDPC_LDPC 构造_PEG_peg ldpc

#include <stdio.h> #include <stdlib.h> #include <iostream> #include <fstream> #include "BigGirth.h" #include "Random.h" NodesInGraph::NodesInGraph(void) {;} void NodesInGraph::setNumOfConnectionSymbolBit(int deg) { if(deg<=0) {cout<<"Wrong NodesInGraph::setNumOfConnectionSymbolBit()"<<endl;exit(-1);} numOfConnectionSymbolBit=deg; connectionSymbolBit=new int[deg]; } void NodesInGraph::initConnectionParityBit(void) { maxDegParity=10000; numOfConnectionParityBit=0; connectionParityBit=new int[1];//dummy memory, actually not used } void NodesInGraph::initConnectionParityBit(int deg) { maxDegParity=deg; numOfConnectionParityBit=0; connectionParityBit=new int[1];//dummy memory, actually not used } NodesInGraph::~NodesInGraph(void) { if(connectionParityBit!=NULL) delete [] connectionParityBit; if(connectionSymbolBit!=NULL) delete [] connectionSymbolBit; } BigGirth::BigGirth(void) { ; } BigGirth::BigGirth(int M, int N, int quickEnc, int *symbolDegSequence, int *checkDegSequence, char *filename, int sglConcent, int tgtGirth, int verbose){ int i, j, k, m, index, localDepth=100; int *mid; H = NULL; EXPAND_DEPTH = (tgtGirth-4)/2; if( EXPAND_DEPTH < 0 ) EXPAND_DEPTH = 0; // corresponds to depth l in the PEG paper; // the target girth = 2*EXPAND_DEPTH+4 // if set large, then GREEDY algorithm myrandom = new Random(); //(12345678l, 987654321lu); (*this).M = M; (*this).N = N; (*this).filename = filename; mid = new int[M]; localGirth = new int[N]; /* Set variable node degrees according to the sequence obtained from the degree distribution */ nodesInGraph = new NodesInGraph [N]; for( i=0; i<N; i++ ) nodesInGraph[i].setNumOfConnectionSymbolBit(symbolDegSequence[i]); /* Set check node degrees according to the sequence obtained from the degree distribution, if provided */ if( checkDegSequence != NULL ){ for( i=0; i<M; i++ ) nodesInGraph[i].initConnectionParityBit(checkDegSequence[i]); } else{ /* Compute parity check node distribution */ // Get and set mean degree j = 0; for( k = 0; k < N; k++ ) j += symbolDegSequence[k]; k = j/M; for( i = 0; i < M; i++ ) mid[i] = k; // Add remaining connections by increasing the degree of some check nodes as needed for( i = 0; i < j-k*M; i++ ) mid[i]++; // Check that total parity check node connections equal total variable node connections k = 0; for( i = 0; i < M; i++ ) k += mid[i]; if( k != j ) {cout<<"Wrong in computing maxDegParity!"<<endl;exit(-1);} /* If strictly concentrated parity check distribution is required, set check node degrees to the corresponding values, else set to a number that is practically not limiting (10.000) */ for( i = 0; i < M; i++ ){ if( sglConcent == 0 ) nodesInGraph[i].initConnectionParityBit(mid[i]); else nodesInGraph[i].initConnectionParityBit(); } } /* Create graph */ for(k = 0; k < N; k++ ){ if( quickEnc == 1 && k < M ){ nodesInGraph[k].connectionSymbolBit[0] = k; } else{ m = 1000000; index = -1; // Find check node with the smallest degree that does not exceed its assigned degree for(i = 0; i < M; i++ ){ if( nodesInGraph[i].numOfConnectionParityBit < m && nodesInGraph[i].numOfConnectionParityBit < nodesInGraph[i].maxDegParity) { m = nodesInGraph[i].numOfConnectionParityBit; index = i; } } // Make first connection nodesInGraph[k].connectionSymbolBit[0] = index;//least connections of parity bit } // Make rest of connections int iter = 0; ITER: localGirth[k] = 100; for( m = 1; m < nodesInGraph[k].numOfConnectionSymbolBit; m++ ){ nodesInGraph[k].connectionSymbolBit[m] = selectParityConnect(k, m, localDepth, quickEnc); localGirth[k] = ( localGirth[k] > localDepth ) ? localDepth : localGirth[k]; if(k > 0 && localGirth[k] < localGirth[k-1] && iter < 20){ iter++; goto ITER; } if(localGirth[k] == 0 && iter < 30){ iter++; goto ITER; } } if(verbose != 0) { cout<< "k=" << k << " "; for( m = 0; m < nodesInGraph[k].numOfConnectionSymbolBit; m++ ) cout<<nodesInGraph[k].connectionSymbolBit[m] << " "; cout << "LocalGirth=" << 2*localGirth[k] + 4; cout << endl; } updateConnection(k); } cout << "Showing the row weight distribution..." << endl; for( i = 0; i < M; i++ ) cout << nodesInGraph[i].numOfConnectionParityBit << " "; cout << endl; delete [] mid; // Write log to file ofstream cycleFile; cycleFile.open("leftHandGirth.log", ios::out); localDepth = 100; for( k = 0; k < N; k++ ){ if( localGirth[k] < localDepth ) localDepth = localGirth[k]; if( localDepth == 100 ) cycleFile << "inf "; else cycleFile << 2*localDepth + 4 << " "; } cycleFile << endl; cycleFile.close(); cout << endl; cout << "*************************************************************" << endl; cout << " The global girth of the PEG Tanner graph :=" << 2*localDepth + 4 << endl; cout << "*************************************************************" << endl; loadH(); } BigGirth::~BigGirth(void) { if( H != NULL){ for( int i = 0; i < M; i++ ) delete [] H[i]; delete [] H; H = NULL; } delete [] localGirth; delete [] nodesInGraph; nodesInGraph = NULL; delete myrandom; } int BigGirth::selectParityConnect(int kthSymbol, int mthConnection, int & cycle, int quickEnc) { int i, j, k, index, mincycles, numCur, numNext, cpNumCur; int *tmp, *med; int *current;//take note of the covering parity bits mincycles = 0; tmp = new int[M]; med = new int[M]; numCur = mthConnection; current = new int[mthConnection]; // Find existing connections to check nodes for( i = 0; i < mthConnection; i++ ) current[i] = nodesInGraph[kthSymbol].connectionSymbolBit[i]; LOOP: mincycles++; for( i = 0; i < M; i++ ) tmp[i] = 0; //maintain for( i = 0; i < mthConnection; i++ ) tmp[nodesInGraph[kthSymbol].connectionSymbolBit[i]] = 1; for(i = 0; i < numCur; i++ ){ for( j = 0; j < nodesInGraph[current[i]].numOfConnectionParityBit; j++ ){ for(k = 0; k < nodesInGraph[nodesInGraph[current[i]].connectionParityBit[j]].numOfConnectionSymbolBit; k++ ){ tmp[nodesInGraph[nodesInGraph[current[i]].connectionParityBit[j]].connectionSymbolBit[k]] = 1; } } } index = 0; cpNumCur = 0; for( i = 0; i < M; i++ ){ if( tmp[i] == 1 ) cpNumCur++; if( tmp[i] == 1 || nodesInGraph[i].numOfConnectionParityBit >= nodesInGraph[i].maxDegParity ) index++; } if( quickEnc == 1 && index == kthSymbol + 1 ){ index = M; } // Can not expand any more if( cpNumCur == numCur && index < M ){ // Ones in temp[] denote nodes that are rejected from selection if( quickEnc == 1 && kthSymbol < M ){ //additional handlement to select one having least connections j = 10000000; //dummy number for( i = 0; i < kthSymbol; i++ ){ if( tmp[i] == 0 && nodesInGraph[i].numOfConnectionParityBit < j && nodesInGraph[i].numOfConnectionParityBit < nodesInGraph[i].maxDegParity ) //j is smallest degree j = nodesInGraph[i].numOfConnectionParityBit; } for( i = 0; i < kthSymbol; i++ ){ if( tmp[i] == 0){ if( nodesInGraph[i].numOfConnectionParityBit != j || nodesInGraph[i].numOfConnectionParityBit >= nodesInGraph[i].maxDegParity ){ tmp[i] = 1; } } } for( i = kthSymbol; i < M; i++ ) tmp[i] = 1; } else{ //additional handlement to select one having least connections j = 10000000; //dummy number for( i = 0; i < M; i++ ){ if( tmp[i] == 0 && nodesInGraph[i].numOfConnectionParityBit < j && nodesInGraph[i].numOfConnectionParityBit < nodesInGraph[i].maxDegParity ) //j is smallest degree j = nodesInGraph[i].numOfConnectionParityBit; } for( i = 0; i < M; i++ ){ if( tmp[i] == 0)