sumproductdecoder.java

density evolution for LDPC codes design and some related documents

// =================================================================
//
// SumProductDecoder.java
//
// 懳悢椞堟sum-product暅崋朄僋儔僗
//
// 奐敪娐嫬
// Windows2000
// Java 2 SDK, Standard Edition
// Version 1.3.1
//
// 摦嶌妋擣娐嫬
// Windows2000
// java version "1.3.1_02"
// Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1_02-b02)
// Java HotSpot(TM) Client VM (build 1.3.1_02-b02, mixed mode)
//
// (C) Tadashi Wadayama, 2002
//  April 11, 2002
//  April 26, 楍張棟丄峴張棟偺岠棪壔
// =================================================================

import java.io.*;
import java.util.*;

public class SumProductDecoder {
  
  public int tmp_bit[];		// 堦帪悇掕岅
  public double posterior[];	// 懳悢帠屻妋棪斾

  private double alpha[][];
  private double beta[][];
  
  public int n;			// 晞崋挿
  public int m;			// 専嵏婰崋悢
  public int rmax;		// 峴廳傒偺嵟戝抣
  public int cmax;		// 楍廳傒偺嵟戝抣
  public int row_weight[];	// 奺峴偺峴廳傒
  public int col_weight[];	// 奺楍偺楍廳傒
  public int row_list[][];
  public int col_list_r[][];
  public int col_list_c[][];

  public int dec(double lambda[], int loop_max) {
				// 曉傝抣偼丄晞崋岅偑摼傜傟傞偲0,偦偆偱側偗傟偽-1
				// lambda偼僔儞儃儖懳悢栟搙斾丄loop_max偼嵟戝斀暅夞悢
    int i,j,k;
    int ret = -1;
    alpha = new double[m][rmax]; // 懳悢奜晹抣斾
    beta  = new double[m][rmax]; // 懳悢帠慜抣斾
    tmp_bit= new int[n];
				// beta偺弶婜壔
    for (i=0; i <= m-1; i++) {
      for (j=0; j <= row_weight[i]-1; j++) {
	beta[i][j] = 0.0;
      }
    }

    double sum, tmp;
    int prod;
    posterior = new double[n];	
    int f,parity;
    for (int loop = 1; loop <= loop_max; loop++) { // 斀暅奐巒
      
				// 峴張棟
      for (i = 0; i <= m-1; i++) { 
	sum = 0.0; prod = 1;
	for (k = 0; k <= row_weight[i]-1; k++) { 
	  tmp = lambda[row_list[i][k]] + beta[i][k];
	  sum = sum + gallager_f(Math.abs(tmp));
	  prod = prod * sign(tmp);
	}
	for (j = 0; j <= row_weight[i]-1; j++) {
	  tmp = lambda[row_list[i][j]] + beta[i][j];
	  alpha[i][j] = prod * sign(tmp) * gallager_f(sum-gallager_f(Math.abs(tmp)));
	}		
      }			
				// 楍張棟
      sum = 0.0;
      for (i = 0; i <= n-1; i++) {
	sum = 0.0;
	for (k = 0; k <= col_weight[i]-1; k++) 
	  sum += alpha[col_list_r[i][k]][col_list_c[i][k]];
	for (j = 0; j <= col_weight[i]-1; j++) {	
	  beta[col_list_r[i][j]][col_list_c[i][j]] 
	    = sum-alpha[col_list_r[i][j]][col_list_c[i][j]];
	}			
	posterior[i] = lambda[i] + sum;
	if (posterior[i] >0) tmp_bit[i] = 0;
	else tmp_bit[i] = 1;
      }				
      System.out.println( "-----------------------------loop no. = " +loop);
      for (i = 0; i <= n-1; i++) 
	System.out.print(posterior[i]+" ");
      System.out.println("\n");

				//僷儕僥傿専嵏

      f = 0;
      for (i=0; i <= m-1; i++) {
	parity = 0;
	for (j=0; j <= row_weight[i]-1; j++) 
	  parity = (parity + tmp_bit[row_list[i][j]]) % 2;
	if (parity == 1) f = 1;
      }
      if (f == 0) {
	ret = 0;
	break;
      }

    }				// 斀暅廔傢傝
    return ret;
  }
  
				// sign娭悢
  public int sign(double x) {
    if (x >= 0.0) return 1;
    else return -1;
  }
				// Gallager偺f娭悢
  public double gallager_f(double x) {
    double y;
    double a = Math.exp(x);
    if (x < 0.00001) 
      y = 12.21;		// 傾儞僟乕僼儘乕懳嶔
				// 12.21 = gallager_f(0.00001)
    else 
      y = Math.log((a+1.0)/(a-1.0));
    return y;
  }
				//僐儞僗僩儔僋僞
  SumProductDecoder(String file){
				// file偱spmat僼傽僀儖傪巜掕偡傞丅
    try{
				// 僼傽僀儖偺撉傒崬傒
      BufferedReader in = new BufferedReader(new FileReader(file));
      String input = in.readLine();
      StringTokenizer t = new StringTokenizer(input);
      n = Integer.parseInt(t.nextToken());
      m = Integer.parseInt(t.nextToken());
      //System.out.println("n = " + n);
      //System.out.println("m = " + m);

      input = in.readLine();
      t = new StringTokenizer(input);
      rmax = Integer.parseInt(t.nextToken());
      cmax = Integer.parseInt(t.nextToken());

      row_weight = new int[m];
      input = in.readLine();
      t = new StringTokenizer(input);
      for (int i = 0; i <= m-1; i++) {
	row_weight[i] = Integer.parseInt(t.nextToken());
      }

      col_weight = new int[n];
      input = in.readLine();
      t = new StringTokenizer(input);
      for (int i = 0; i <= n-1; i++) {
	col_weight[i] = Integer.parseInt(t.nextToken());
      }

      int v;
      int counter[] = new int[n];
      for (int i=0; i <= n-1; i++) counter[i] = 0;
      row_list = new int[m][rmax];
      col_list_r = new int[n][cmax];
      col_list_c = new int[n][cmax];

      for (int j = 0; j <= m-1; j++) {
	input = in.readLine();
	t = new StringTokenizer(input);
	for (int i = 0; i <= row_weight[j]-1; i++) {
	  v = Integer.parseInt(t.nextToken())-1;
	  row_list[j][i] = v;
	  col_list_r[v][counter[v]] = j;
	  col_list_c[v][counter[v]] = i;
	  counter[v]++;
	}
      }
    } catch (IOException e){}
  }
}