girth.c

density evolution for LDPC codes design and some related documents

/*
  	FILENAME: girth.c
  	AUTHOR: Tadashi Wadayama

	HOW TO MAKE:
	gcc -O2 -o girth girth.c

*/

#include <stdio.h>
#include <stdlib.h>


#define INFINITY 10000000

int n;
int m;
int rmax;
int cmax;
int *row_weight;
int *col_weight;
int **row_list;
int **col_list_r;
int **col_list_c;

int *vf;
int *cf;
int g;				/* girth */
int local_g;
int local_g_hist[30];

void init_BP(FILE *fp)
{
/**********************************************************************************/
// initialization of BP decoder
/**********************************************************************************/

  int i,j;
  int v;
  int *counter;

// read parity check matrix 

  fscanf(fp,"%d %d\n",&n,&m);	// n:code length, m:number of parity checks
  fscanf(fp,"%d %d\n",&rmax,&cmax); // rmax:maximum number of row weight
				    // cmax:maximum number of column weight
  row_weight = malloc(sizeof(int)*m); // array for row weight profile
  for (i = 0; i <= m-1; i++) fscanf(fp,"%d",&row_weight[i]);
  col_weight = malloc(sizeof(int)*n); // array for column weight profile
  for (i = 0; i <= n-1; i++) fscanf(fp,"%d",&col_weight[i]);
  counter = malloc(sizeof(int)*n); 
  for (i=0; i <= n-1; i++) counter[i] = 0;  

  row_list = malloc(sizeof(int*)*m); // parity check matrix in row form
  for (i=0;i<=m-1;i++) row_list[i] = malloc(sizeof(int)*rmax);
  col_list_r = malloc(sizeof(int*)*n); 
  for (i=0;i<=n-1;i++) col_list_r[i] = malloc(sizeof(int)*cmax);
  col_list_c = malloc(sizeof(int*)*n); 
  for (i=0;i<=n-1;i++) col_list_c[i] = malloc(sizeof(int)*cmax);

// set up for parity check matrix

  for (j = 0; j <= m-1; j++) {
    for (i = 0; i <= row_weight[j]-1; i++) {
      fscanf(fp,"%d",&v);
      v--;
      row_list[j][i] = v;
      col_list_r[v][counter[v]] = j;
      col_list_c[v][counter[v]] = i;
      counter[v]++;
    }
  }

  vf = malloc(sizeof(int)*n);
  cf = malloc(sizeof(int)*m);
}

int visit_cnode(int c, int len)
{
  int i;
  int v;

  if (len > 12) return;
  //printf(">>>>> c = %d\n",c);
  //printf("vf = ");
  //for (i = 0; i<= n-1; i++) printf("%d ",vf[i]);
  //printf("\n");
  //printf("cf = ");
  //for (i = 0; i<= m-1; i++)  printf("%d ",cf[i]);
  //printf("\n");
    
  for (i = 0; i <= row_weight[c]-1; i++) {
    v = row_list[c][i];
    if (vf[v] >= len+1) {
      vf[v] = len+1;
      visit_vnode(v,len+1);
    }
    else {
      if (vf[v] == -1) {
	//printf("loop!! ");
	//printf("len = %d\n",len+1);
	if ((len+1 > 2)&&(len+1 < g)) {
	  g = len+1;
	}
	if ((len+1 > 2)&&(len+1 < local_g)) {
	  local_g = len+1;
	}
      }
    }
  }
}

int visit_vnode(int v, int len)
{
  int i;
  int c;

  if (len > 12) return;
  //printf("v = %d\n",v);
  for (i = 0; i <= col_weight[v]-1; i++) {    
    c = col_list_r[v][i];
    if (cf[c] >= len+1) {
      cf[c] = len+1;
      visit_cnode(c,len+1);
    }
  }
}

int girth()
{
  int i;
  int v;
  g = INFINITY;

  for (v = 0; v <= n-1; v++) {
    printf("======= start node = %d =====\n",v);
    for (i = 0; i<= n-1; i++) vf[i] = INFINITY;
    for (i = 0; i<= m-1; i++) cf[i] = INFINITY;

    vf[v] = -1;			/* start variable node */
    local_g = INFINITY;
    visit_vnode(v,0);
    if (local_g < 29) local_g_hist[local_g]++;
    printf("local girth = %d\n",local_g);
    //printf("vf = ");
    //for (i = 0; i<= n-1; i++) printf("%d ",vf[i]);
    //printf("\n");
    //printf("cf = ");
    //for (i = 0; i<= m-1; i++)  printf("%d ",cf[i]);
    //printf("\n");
  }

  return g;
}

int main(int argc,char **argv)
{
  FILE* fp;
  int i;
  
  if (argc != 2) {
    printf("usage : girth spmatfile\n");
    exit(1);
  }
  if ((fp = fopen(argv[1],"r")) == NULL) {
    fprintf(stderr,"Can't open spmatfile.\n");
    exit(-1);
  }
  init_BP(fp);
  
  for (i = 0; i <= 29; i++) local_g_hist[i] = 0;
  printf("girth = %d\n",girth());
  for (i = 0; i <= 29; i++) printf("%d %d\n",i,local_g_hist[i]);
}