check.c

ldpc的11个程序 encode decode extract make-gen make-ldpc make-pchk print-gen print-pchk rand-src transm

/* CHECK.C - Compute parity checks and other stats on decodings. */

/* Copyright (c) 2001 by Radford M. Neal 
 *
 * Permission is granted for anyone to copy, use, or modify this program 
 * for purposes of research or education, provided this copyright notice 
 * is retained, and note is made of any changes that have been made. 
 *
 * This program is distributed without any warranty, express or implied.
 * As this program was written for research purposes only, it has not been
 * tested to the degree that would be advisable in any important application.
 * All use of this program is entirely at the user's own risk.
 */

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

#include "mod2sparse.h"
#include "check.h"



/* COMPUTE PARITY CHECKS.  Returns the number of parity checks violated by
   dblk.  The results of all the parity checks are stored in pchk. */

int check
( mod2sparse *H,	/* Parity check matrix */
  char *dblk,		/* Guess for codeword */
  char *pchk		/* Place to store parity checks */
)
{
  int M, i, c;

  M = mod2sparse_rows(H);

  mod2sparse_mulvec (H, dblk, pchk);

  c = 0;
  for (i = 0; i<M; i++) 
  { c += pchk[i];
  }

  return c;
}


/* COUNT HOW MANY BITS HAVED CHANGED FROM BIT INDICATED BY LIKELIHOOD.  The
   simple decoding based on likelihood ratio is compared to the given decoding.
   A bit for which the likelihood ratio is exactly one counts as half a 
   change, which explains why the result is a double rather than an int.
 */

double changed
( double *lratio,	/* Likelihood ratios for bits */
  char *dblk,		/* Candidate decoding */
  int N			/* Number of bits */
)
{ 
  double changed;
  int j;

  changed = 0;
  for (j = 0; j<N; j++)
  {
	  changed += ((lratio[j]==1 )? 0.5 : (dblk[j] != (lratio[j]>1)));
  }

  return changed;
}


/* COMPUTE THE EXPECTED NUMBER OF PARITY CHECK ERRORS.   Computes the
   expected number of parity check errors with respect to the distribution
   given by the bit probabilities passed, with bits assumed to be independent. 
 */

double expected_parity_errors
( mod2sparse *H,	/* Parity check matrix */
  double *bpr		/* Bit probabilities */
)
{ 
  mod2entry *f;
  double ee, p;
  int M, i, j;

  M = mod2sparse_rows(H);

  ee = 0;

  for (i = 0; i<M; i++)
  { p = 0;
    for (f = mod2sparse_first_in_row(H,i);
         !mod2sparse_at_end(f);
         f = mod2sparse_next_in_row(f))
    { j = mod2sparse_col(f);
      p = p * (1-bpr[j]) + (1-p) * bpr[j];
    }
    ee += p;
  }

  return ee;
}


/* COMPUTE LOG LIKELIHOOD OF A DECODING. */

double loglikelihood 
( double *lratio,	/* Likelihood ratios for bits */
  char *bits,		/* Bits in decoding */
  int N			/* Length of codeword */
)
{ 
  double ll;
  int j;
  
  ll = 0;

  for (j = 0; j<N; j++)
  { ll -= bits[j] ? log(1+1/lratio[j]) : log(1+lratio[j]);
  }

  return ll;
}


/* COMPUTE THE EXPECTED LOG LIKELIHOOD BASED ON BIT PROBABILITIES.  Computes
   the expected value of the log likelihood with respect to the distribution
   given by the bit probabilities passed, with bits assumed to be independent. 
 */

double expected_loglikelihood 
( double *lratio,	/* Likelihood ratios for bits */
  double *bpr,		/* Bit probabilities */
  int N			/* Length of codeword */
)
{ 
  double ll;
  int j;
  
  ll = 0;

  for (j = 0; j<N; j++)
  { if (bpr[j]>0) 
    { ll -= bpr[j]*log(1+1/lratio[j]);
    }
    if (bpr[j]<1) 
    { ll -= (1-bpr[j])*log(1+lratio[j]);
    }
  }

  return ll;
}


/* COMPUTE ENTROPY FROM BIT PROBABILITIES.  Computes the entropy of the
   distribution given by the bit probabilities, on the assumption that
   bits are independent.
 */

double entropy 
( double *bpr,		/* Bit probabilities */
  int N			/* Length of codeword */
)
{
  double e;
  int j;

  e = 0;
  for (j = 0; j<N; j++)
  { if (bpr[j]>0 && bpr[j]<1)
    { e -= bpr[j]*log(bpr[j]) + (1-bpr[j])*log(1-bpr[j]);
    }
  }

  return e/log(2.0);
}