mod2dense.c

用于LDPC编码译码的仿真实现。包括随机生成校验矩阵、由校验矩阵产生生成矩阵、编码、加随机噪声、译码等内容。原作者是老外

/* MOD2DENSE.C - Procedures for handling dense mod2 matrices. */

/* Copyright (c) 1996, 2000, 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.
 */


/* NOTE:  See mod2dense.html for documentation on these procedures. */


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

#include "alloc.h"
#include "intio.h"
#include "mod2dense.h"


/* ALLOCATE SPACE FOR A DENSE MOD2 MATRIX. 为一个dense矩阵分配内存*/

mod2dense *mod2dense_allocate 
( int n_rows, 		/* Number of rows in matrix */
  int n_cols		/* Number of columns in matrix */
)
{
  mod2dense *m;
  int j;

  if (n_rows<=0 || n_cols<=0)
  { fprintf(stderr,"mod2dense_allocate: Invalid number of rows or columns\n");
    exit(1);
  }

  m = chk_alloc (1, sizeof *m);

  m->n_rows = n_rows;
  m->n_cols = n_cols;

  m->n_words = (n_rows+mod2_wordsize-1) >> mod2_wordsize_shift;  //计算存一列比特需要的字数（右移5位）

  m->col = chk_alloc (m->n_cols, sizeof *m->col);     

  m->bits = chk_alloc(m->n_words*m->n_cols, sizeof *m->bits);

  for (j = 0; j<m->n_cols; j++)       //为每个col[]赋值，使它指向所对应的存储改列比特的内存
  { m->col[j] = m->bits + j*m->n_words;   
  }

  return m;
}


/* FREE SPACE OCCUPIED BY A DENSE MOD2 MATRIX.释放存储dense矩阵所占的内存 */

void mod2dense_free
( mod2dense *m		/* Matrix to free */
)
{ free(m->bits);
  free(m->col);
  free(m);
}


/* CLEAR A DENSE MOD2 MATRIX.把一个dense矩阵置为全零 */

void mod2dense_clear
( mod2dense *r
)
{
  int k, j;

  for (j = 0; j<mod2dense_cols(r); j++)
  { for (k = 0; k<r->n_words; k++)
    { r->col[j][k] = 0;
    }
  }

}


/* COPY A DENSE MOD2 MATRIX.复制一个dense矩阵 */

void mod2dense_copy
( mod2dense *m,		/* Matrix to copy */
  mod2dense *r		/* Place to store copy of matrix */
)
{ 
  int k, j;

  if (mod2dense_rows(m)>mod2dense_rows(r)  //如果目标矩阵的行数或列数小于源矩阵则提示出错，目标矩阵太小
   || mod2dense_cols(m)>mod2dense_cols(r))
  { fprintf(stderr,"mod2dense_copy: Destination matrix is too small\n");
    exit(1);
  }

  for (j = 0; j<mod2dense_cols(m); j++)
  { for (k = 0; k<m->n_words; k++)
    { r->col[j][k] = m->col[j][k];    //把每列的比特存储字赋值给新的矩阵，
    }
    for ( ; k<r->n_words; k++)    // 如果新矩阵每列的字数大于原矩阵，则多余的字都置为0  
    { r->col[j][k] = 0;
    }
  }

  for ( ; j<mod2dense_cols(r); j++)   //如果新矩阵的列数大于原矩阵，
  { for (k = 0; k<r->n_words; k++) //则多余的列的字全部置0
    { r->col[j][k] = 0;
    }
  }
}


/* COPY ROWS OF A DENSE MOD2 MATRIX.复制矩阵的行 */

void mod2dense_copyrows
( mod2dense *m,		/* Matrix to copy */
  mod2dense *r,		/* Place to store copy of matrix */
  int *rows		/* Indexes of rows to copy, from 0 */
)
{ 
  int i, j;

  if (mod2dense_cols(m)>mod2dense_cols(r))  //如果目标矩阵的列小于原矩阵，则提示出错
  { fprintf(stderr,                          //并结束该函数
      "mod2dense_copyrows: Destination matrix has fewer columns than source\n");
    exit(1);
  }

  mod2dense_clear(r);        //把目标矩阵全置0

  for (i = 0; i<mod2dense_rows(r); i++)
  { if (rows[i]<0 || rows[i]>=mod2dense_rows(m))   //若要复制的行超出原矩阵的范围，则提示出错
    { fprintf(stderr,"mod2dense_copyrows: Row index out of range\n");
      exit(1);
    }
    for (j = 0; j<mod2dense_cols(m); j++)
    { mod2dense_set(r,i,j,mod2dense_get(m,rows[i],j));
    }
  }
}


/* COPY COLUMNS OF A DENSE MOD2 MATRIX. 复制dense矩阵的列*/

void mod2dense_copycols
( mod2dense *m,		/* Matrix to copy */
  mod2dense *r,		/* Place to store copy of matrix */
  int *cols		/* Indexes of columns to copy, from 0 */
)
{ 
  int k, j;                  

  if (mod2dense_rows(m)>mod2dense_rows(r))   //如果目标矩阵的行数小于原矩阵提示出错 
  { fprintf(stderr,
      "mod2dense_copycols: Destination matrix has fewer rows than source\n");
    exit(1);
  }

  for (j = 0; j<mod2dense_cols(r); j++)  //按列复制
  { if (cols[j]<0 || cols[j]>=mod2dense_cols(m))
    { fprintf(stderr,"mod2dense_copycols: Column index out of range\n");
      exit(1);    //如果要复制的列不在原矩阵的范围，则提示出错
    }
    for (k = 0; k<m->n_words; k++)    
    { r->col[j][k] = m->col[cols[j]][k];
    }
    for ( ; k<r->n_words; k++)    //若目标矩阵的行数大于原矩阵，则多余的字置0
    { r->col[j][k] = 0;
    }
  }
}


/* PRINT A DENSE MOD2 MATRIX IN HUMAN-READABLE FORM.以可读的藩方式输出dense矩阵 */

void mod2dense_print     
( FILE *f,
  mod2dense *m
)
{ 
  int i, j;

  for (i = 0; i<mod2dense_rows(m); i++)
  { for (j = 0; j<mod2dense_cols(m); j++)
    { fprintf(f," %d",mod2dense_get(m,i,j));
    }
    fprintf(f,"\n");
  }
}


/* WRITE A DENSE MOD2 MATRIX TO A FILE IN MACHINE-READABLE FORM.以机器可处理的形式把矩阵写到某文件

   Data is written using intio_write, so that it will be readable on a machine
   with a different byte-ordering.  At present, this assumes that the words 
   used to pack bits into are no longer than 32 bits. */

int mod2dense_write     
( FILE *f, 
  mod2dense *m
)
{ 
  int j, k;

  intio_write(f,m->n_rows);           //先写行数
  if (ferror(f)) return 0;

  intio_write(f,m->n_cols);           //再写列数
  if (ferror(f)) return 0;

  for (j = 0; j<mod2dense_cols(m); j++)   //一列一列的把dense矩阵的存储字写到文件中  
  {
    for (k = 0; k<m->n_words; k++)
    { intio_write(f,m->col[j][k]);
      if (ferror(f)) return 0;
    }
  }

  return 1;
}


/* READ A DENSE MOD2 MATRIX STORED IN MACHINE-READABLE FORM FROM A FILE. */
//从文件中读矩阵，返回指向该矩阵地指针
mod2dense *mod2dense_read  
( FILE *f
)
{ 
  int n_rows, n_cols;
  mod2dense *m;
  int j, k;
  
  n_rows = intio_read(f);           //先读行数
  if (feof(f) || ferror(f) || n_rows<=0) return 0;

  n_cols = intio_read(f);          //再读列数
  if (feof(f) || ferror(f) || n_cols<=0) return 0;

  m = mod2dense_allocate(n_rows,n_cols);   //为矩阵分配内存

  for (j = 0; j<mod2dense_cols(m); j++)
  {
    for (k = 0; k<m->n_words; k++)
    { m->col[j][k] = intio_read(f);   //按矩阵存储的顺序一个一个地往外读字
      if (feof(f) || ferror(f)) 
      { mod2dense_free(m);
        return 0;
      }
    }
  }

  return m;
}


/* GET AN ELEMENT FROM A DENSE MOD2 MATRIX.取dense矩阵的一个元素 */

int mod2dense_get  
( mod2dense *m, 	/* Matrix to get element from */
  int row,		/* Row of element (starting with zero) */
  int col		/* Column of element (starting with zero) */
)
{
  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))
  { fprintf(stderr,"mod2dense_get: row or column index out of bounds\n");
    exit(1);    //如果行或列超出范围，提示出错，并结束函数
  }

  return mod2_getbit (m->col[col][row>>mod2_wordsize_shift], 
                      row&mod2_wordsize_mask);
}


/* SET AN ELEMENT IN A DENSE MOD2 MATRIX.给dense矩阵的某个元素置数 */

void mod2dense_set 
( mod2dense *m, 	/* Matrix to modify element of */
  int row,		/* Row of element (starting with zero) */
  int col,		/* Column of element (starting with zero) */
  int value		/* New value of element (0 or 1) */
)
{ 
  mod2word *w;

  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))
  { fprintf(stderr,"mod2dense_set: row or column index out of bounds\n");
    exit(1);               //如果行或列超出范围，提示出错，并结束函数
  }

  w = &m->col[col][row>>mod2_wordsize_shift]; //w指向要指数元素所在的存储字

  *w = value ? mod2_setbit1(*w,row&mod2_wordsize_mask)   
             : mod2_setbit0(*w,row&mod2_wordsize_mask);
}


/* FLIP AN ELEMENT OF A DENSE MOD2 MATRIX.把dense矩阵中的某元素取反，并返回取反后的值 */

int mod2dense_flip  
( mod2dense *m, 	/* Matrix to flip element in */
  int row,		/* Row of element (starting with zero) */
  int col		/* Column of element (starting with zero) */
)
{
  mod2word *w;
  int b;

  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))
  { fprintf(stderr,"mod2dense_flip: row or column index out of bounds\n");
    exit(1);    //如果行或列超出范围，提示出错，并结束函数
  }

  b = 1 ^ mod2_getbit (m->col[col][row>>mod2_wordsize_shift], 
                       row&mod2_wordsize_mask);   //取得该元素并取反(与1异或相当于取反)

  w = &m->col[col][row>>mod2_wordsize_shift];   //w指向该元素所在的存储字

  *w = b ? mod2_setbit1(*w,row&mod2_wordsize_mask) 
         : mod2_setbit0(*w,row&mod2_wordsize_mask);

  return b;
}


/* COMPUTE THE TRANSPOSE OF A DENSE MOD2 MATRIX. 求dense矩阵的转置矩阵*/

void mod2dense_transpose
( mod2dense *m,		/* Matrix to compute transpose of (left unchanged) */
  mod2dense *r		/* Result of transpose operation */
)
{
  mod2word w, v, *p;
  int k1, j1, i2, j2;

  if (mod2dense_rows(m)!=mod2dense_cols(r)    //若原矩阵的行数不等于目标矩阵的列数
   || mod2dense_cols(m)!=mod2dense_rows(r))
  { fprintf(stderr,                //或原矩阵的列数不等于目标矩阵的行数则提示出错
     "mod2dense_transpose: Matrices have incompatible dimensions\n");
    exit(1);
  }

  if (r==m)          //如果目标矩阵和原矩阵的地址相同，提示出错     
  { fprintf(stderr, 
     "mod2dense_transpose: Result matrix is the same as the operand\n");
    exit(1);
  }

  mod2dense_clear(r);   //把目标矩阵清零

  for (j1 = 0; j1<mod2dense_cols(m); j1++)   //j1原矩阵额的列数
  { 
    i2 = j1 >> mod2_wordsize_shift;  //目标矩阵的j1行所在的第i2个存贮字
    v = 1 << (j1 & mod2_wordsize_mask);

    p = m->col[j1];
    k1 = 0;

    for (j2 = 0; j2<mod2dense_cols(r); j2++)
    { if (k1==0)
      { w = *p++;
        k1 = mod2_wordsize;
      }
      if (w&1)
      { r->col[j2][i2] |= v;
      }
      w >>= 1;     
      k1 -= 1;