mod2sparse.c

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

    exit(1);
  }

  /* Find old entry and return it, or allocate new entry and insert into row. */

  re = mod2sparse_last_in_row(m,row);  //找到要插入的行的最后一个实体

  if (!mod2sparse_at_end(re) && mod2sparse_col(re)==col) 
  { return re;      //如果re不是链表头，而且re的列与要插入的列相等，即该实体在原矩阵中存在，返回re
  }

  if (mod2sparse_at_end(re) || mod2sparse_col(re)<col) 
  { re = re->right;  //如果re是链表头或者re所在的列小于col，re指向下一个实体
  }  
  else    
  {
    re = mod2sparse_first_in_row(m,row);  //否则使re指向改行的第一个实体

    for (;;)  
    { 
      if (!mod2sparse_at_end(re) && mod2sparse_col(re)==col) 
      { return re;     //如果re不是链表头，而且re的列与要插入的列相等，即该实体在原矩阵中存在，返回re
      }

      if (mod2sparse_at_end(re) || mod2sparse_col(re)>col)
      { break;        //如果re是链表头或者re所在的列小于col，re指向下一个实体    
      } 

      re = mod2sparse_next_in_row(re);   //使re指向改行的下一个实体
    }
  }          //循环结束后，re指向row行中列数大于col的第一个实体

  ne = alloc_entry(m);      //分配新的实体

  ne->row = row;    
  ne->col = col;

  ne->left = re->left;      //把新的实体插入行链表中
  ne->right = re;
  ne->left->right = ne;
  ne->right->left = ne;

  /* Insert new entry into column.  If we find an existing entry here,
     the matrix must be garbled, since we didn't find it in the row. */

  ce = mod2sparse_last_in_col(m,col);   //使ce指向要插入列的最后一个实体  

  if (!mod2sparse_at_end(ce) && mod2sparse_row(ce)==row) 
  { fprintf(stderr,"mod2sparse_insert: Garbled matrix\n");
    exit(1);       //若在改列中找到该实体，则提示矩阵混乱   
  }

  if (mod2sparse_at_end(ce) || mod2sparse_row(ce)<row) 
  { ce = ce->down;   //如果ce使链表头或者ce所在的行小于row，使ce指向该列的下一个实体  
  }
  else
  {
    ce = mod2sparse_first_in_col(m,col);   //使ce指向该列的第一个实体

    for (;;)
    { 
      if (!mod2sparse_at_end(ce) && mod2sparse_row(ce)==row) 
      { fprintf(stderr,"mod2sparse_insert: Garbled matrix\n");
        exit(1);                 //若在改列中找到该实体，则提示矩阵混乱
      } 

      if (mod2sparse_at_end(ce) || mod2sparse_row(ce)>row)
      { break;              
      } 

      ce = mod2sparse_next_in_col(ce);
    }
  }      //循环结束后，ce指向col列中行数大于row的第一个实体
    
  ne->up = ce->up;     //把ne插入到该列链表中
  ne->down = ce;
  ne->up->down = ne;
  ne->down->up = ne;

  /* Return the new entry. */

  return ne;
}


/* DELETE AN ENTRY FROM A SPARSE MATRIX.在矩阵中删除某实体*/

void mod2sparse_delete
( mod2sparse *m,
  mod2entry *e
)
{ 
  if (e==0)
  { fprintf(stderr,"mod2sparse_delete: Trying to delete a null entry\n");
    exit(1);
  }

  if (e->row<0 || e->col<0)
  { fprintf(stderr,"mod2sparse_delete: Trying to delete a header entry\n");
    exit(1);
  }

  e->left->right = e->right;    
  e->right->left = e->left;

  e->up->down = e->down;
  e->down->up = e->up;
 
  e->left = m->next_free;
  m->next_free = e;
}


/* TEST WHETHER TWO SPARSE MATRICES ARE EQUAL.看两个稀疏矩阵是否相等*/

int mod2sparse_equal
( mod2sparse *m1,
  mod2sparse *m2
)
{
  mod2entry *e1, *e2;
  int i;

  if (mod2sparse_rows(m1)!=mod2sparse_rows(m2) 
   || mod2sparse_cols(m1)!=mod2sparse_cols(m2))
  { fprintf(stderr,"mod2sparse_equal: Matrices have different dimensions\n");
    exit(1);     //如果两个矩阵维数不一样提示
  }
  
  for (i = 0; i<mod2sparse_rows(m1); i++)
  { 
    e1 = mod2sparse_first_in_row(m1,i);
    e2 = mod2sparse_first_in_row(m2,i);

    while (!mod2sparse_at_end(e1) && !mod2sparse_at_end(e2))
    {  
      if (mod2sparse_col(e1)!=mod2sparse_col(e2))
      { return 0;
      }

      e1 = mod2sparse_next_in_row(e1);
      e2 = mod2sparse_next_in_row(e2);
    }

    if (!mod2sparse_at_end(e1) || !mod2sparse_at_end(e2)) 
    { return 0;
    }
  }

  return 1;
}


/* COMPUTE THE TRANSPOSE OF A SPARSE MOD2 MATRIX.求稀疏矩阵的转置*/

void mod2sparse_transpose
( mod2sparse *m,	/* Matrix to compute transpose of (left unchanged) */
  mod2sparse *r		/* Result of transpose operation */
)
{
  mod2entry *e;
  int i;

  if (mod2sparse_rows(m)!=mod2sparse_cols(r) 
   || mod2sparse_cols(m)!=mod2sparse_rows(r))
  { fprintf(stderr,
     "mod2sparse_transpose: Matrices have incompatible dimensions\n");
    exit(1);
  }

  if (r==m)
  { fprintf(stderr, 
     "mod2sparse_transpose: Result matrix is the same as the operand\n");
    exit(1);
  }

  mod2sparse_clear(r);

  for (i = 0; i<mod2sparse_rows(m); i++)
  {
    e = mod2sparse_first_in_row(m,i);

    while (!mod2sparse_at_end(e))
    { mod2sparse_insert(r,mod2sparse_col(e),i);
      e = mod2sparse_next_in_row(e);
    }
  }
}


/* ADD TWO SPARSE MOD2 MATRICES. 求两个矩阵的和*/

void mod2sparse_add
( mod2sparse *m1,	/* Left operand of add */
  mod2sparse *m2,	/* Right operand of add */
  mod2sparse *r		/* Place to store result of add */
)
{
  mod2entry *e1, *e2;
  int i;

  if (mod2sparse_rows(m1)!=mod2sparse_rows(r) 
   || mod2sparse_cols(m1)!=mod2sparse_cols(r) 
   || mod2sparse_rows(m2)!=mod2sparse_rows(r)
   || mod2sparse_cols(m2)!=mod2sparse_cols(r)) 
  { fprintf(stderr,"mod2sparse_add: Matrices have different dimensions\n");
    exit(1);    //矩阵的维数是否相等
  }

  if (r==m1 || r==m2)
  { fprintf(stderr,
     "mod2sparse_add: Result matrix is the same as one of the operands\n");
    exit(1);           
  }

  mod2sparse_clear(r);

  for (i = 0; i<mod2sparse_rows(r); i++)
  { 
    e1 = mod2sparse_first_in_row(m1,i);
    e2 = mod2sparse_first_in_row(m2,i);

    while (!mod2sparse_at_end(e1) && !mod2sparse_at_end(e2))
    { 
      if (mod2sparse_col(e1)==mod2sparse_col(e2))
      { e1 = mod2sparse_next_in_row(e1);
        e2 = mod2sparse_next_in_row(e2); 
      }

      else if (mod2sparse_col(e1)<mod2sparse_col(e2))
      { mod2sparse_insert(r,i,mod2sparse_col(e1));
        e1 = mod2sparse_next_in_row(e1);
      }

      else
      { mod2sparse_insert(r,i,mod2sparse_col(e2));
        e2 = mod2sparse_next_in_row(e2);       
      }
    }

    while (!mod2sparse_at_end(e1))
    { mod2sparse_insert(r,i,mod2sparse_col(e1));
      e1 = mod2sparse_next_in_row(e1);
    }

    while (!mod2sparse_at_end(e2))
    { mod2sparse_insert(r,i,mod2sparse_col(e2));
      e2 = mod2sparse_next_in_row(e2);
    }
  }
}


/* MULTIPLY TWO SPARSE MOD2 MATRICES. 两个稀疏矩阵相乘*/

void mod2sparse_multiply 
( mod2sparse *m1, 	/* Left operand of multiply */
  mod2sparse *m2,	/* Right operand of multiply */
  mod2sparse *r		/* Place to store result of multiply */
)
{
  mod2entry *e1, *e2;
  int i, j, b;

  if (mod2sparse_cols(m1)!=mod2sparse_rows(m2) 
   || mod2sparse_rows(m1)!=mod2sparse_rows(r) 
   || mod2sparse_cols(m2)!=mod2sparse_cols(r))
  { fprintf (stderr,
      "mod2sparse_multiply: Matrices have incompatible dimensions\n");
    exit(1);   //矩阵的维数是否匹配
  }

  if (r==m1 || r==m2)
  { fprintf(stderr,
     "mod2sparse_multiply: Result matrix is the same as one of the operands\n");
    exit(1);      //结果矩阵是否与原矩阵占用相同的空间
  }

  mod2sparse_clear(r);

  for (i = 0; i<mod2sparse_rows(m1); i++)   //m1的第i行
  { 
    if (mod2sparse_at_end(mod2sparse_first_in_row(m1,i))) 
    { continue; //如果m1的第i行没有实体，即全零，则跳出执行下一个循环
    }

    for (j = 0; j<mod2sparse_cols(m2); j++)   //m2的第j列
    { 
      b = 0;

      e1 = mod2sparse_first_in_row(m1,i);  //e1指向m1第i行的第一个实体
      e2 = mod2sparse_first_in_col(m2,j);  //e2指向m2第j列的第一个实体

      while (!mod2sparse_at_end(e1) && !mod2sparse_at_end(e2))
      { 
        if (mod2sparse_col(e1)==mod2sparse_row(e2)) 
        { b ^= 1;              //二进制的模2加等同于异或
          e1 = mod2sparse_next_in_row(e1);
          e2 = mod2sparse_next_in_col(e2); 
        }

        else if (mod2sparse_col(e1)<mod2sparse_row(e2))
        { e1 = mod2sparse_next_in_row(e1);
        }

        else
        { e2 = mod2sparse_next_in_col(e2);       
        }
      }

      if (b)
      { mod2sparse_insert(r,i,j);
      }
    }
  }
}


/* MULTIPLY VECTOR BY SPARSE MATRIX.稀疏矩阵与向量相乘*/

void mod2sparse_mulvec
( mod2sparse *m,	/* The sparse matrix, with M rows and N columns */
  int *u,		/* The input vector, N long */
  int *v		/* Place to store the result, M long */
)
{
  mod2entry *e;
  int M, N;
  int i, j;

  M = mod2sparse_rows(m);
  N = mod2sparse_cols(m);

  for (i = 0; i<M; i++) v[i] = 0;    //初始化结果向量，置全零

  for (j = 0; j<N; j++)
  { if (u[j])
    { for (e = mod2sparse_first_in_col(m,j);   //e指向m矩阵第j列的第一个实体
           !mod2sparse_at_end(e);
           e = mod2sparse_next_in_col(e))  
      { v[mod2sparse_row(e)] ^= 1;
      }
    }
  }
}


/* COUNT ENTRIES IN A ROW. 某行的实体个数*/

int mod2sparse_count_row
( mod2sparse *m,
  int row
)
{
  mod2entry *e;
  int count;

  if (row<0 || row>=mod2sparse_rows(m))
  { fprintf(stderr,"mod2sparse_count_row: row index out of bounds\n");
    exit(1);     //行数是否出界
  }

  count = 0;

  for (e = mod2sparse_first_in_row(m,row);
       !mod2sparse_at_end(e);
       e = mod2sparse_next_in_row(e))
  { count += 1;
  }

  return count;
}


/* COUNT ENTRIES IN A COLUMN. 某列的实体个数*/

int mod2sparse_count_col
( mod2sparse *m,
  int col
)
{
  mod2entry *e;
  int count;

  if (col<0 || col>=mod2sparse_cols(m))
  { fprintf(stderr,"mod2sparse_count_col: column index out of bounds\n");
    exit(1);
  }

  count = 0;

  for (e = mod2sparse_first_in_col(m,col);
       !mod2sparse_at_end(e);
       e = mod2sparse_next_in_col(e))
  { count += 1;
  }

  return count;
}


/* ADD TO A ROW. 把m2的第row2行加到m1的第row1行上*/

void mod2sparse_add_row
( mod2sparse *m1,	/* Matrix containing row to add to */
  int row1,		/* Index in this matrix of row to add to */
  mod2sparse *m2,	/* Matrix containing row to add from */
  int row2		/* Index in this matrix of row to add from */
)
{
  mod2entry *f1, *f2, *ft;

  if (mod2sparse_cols(m1)<mod2sparse_cols(m2))
  { fprintf (stderr,
     "mod2sparse_add_row: row added to is shorter than row added from\n");
    exit(1);
  }

  if (row1<0 || row1>=mod2sparse_rows(m1) 
   || row2<0 || row2>=mod2sparse_rows(m2))
  { fprintf (stderr,"mod2sparse_add_row: row index out of range\n");
    exit(1);
  }

  f1 = mod2sparse_first_in_row(m1,row1);
  f2 = mod2sparse_first_in_row(m2,row2);

  while (!mod2sparse_at_end(f1) && !mod2sparse_at_end(f2))
  { if (mod2sparse_col(f1)>mod2sparse_col(f2))
    { mod2sparse_insert(m1,row1,mod2sparse_col(f2));
      f2 = mod2sparse_next_in_row(f2);
    }
    else
    { ft = mod2sparse_next_in_row(f1);  
      if (mod2sparse_col(f1)==mod2sparse_col(f2))
      { mod2sparse_delete(m1,f1);
        f2 = mod2sparse_next_in_row(f2);
      }
      f1 = ft;
    }
  }

  while (!mod2sparse_at_end(f2))
  { mod2sparse_insert(m1,row1,mod2sparse_col(f2));
    f2 = mod2sparse_next_in_row(f2);
  }
}


/* ADD TO A COLUMN. 把m2的第col2列加到m1的第col1列上 */

void mod2sparse_add_col
( mod2sparse *m1,	/* Matrix containing column to add to */
  int col1,		/* Index in this matrix of column to add to */
  mod2sparse *m2,	/* Matrix containing column to add from */
  int col2		/* Index in this matrix of column to add from */