hamming.c

4.8kcelp语音压缩编码程序

/**************************************************************************
*
* ROUTINE
*               encodeham
*
* FUNCTION
*               This subroutine calculates the parity bits necessary
*		to form the code word.
*
*
* SYNOPSIS
*               encodeham(codelength1,codelength2,hmatrix,
*			  paritybit,codeword)
*
*   formal
*
*                       data    I/O
*       name            type    type    function
*       -------------------------------------------------------------------
*	codelength1	int	i	number of data bits
*	codelength2	int	i	number of information bits
*	hmatrix		int	i	vector to encode a decode by
*	paritybit	int	o	overall parity bit
*	codeword	int	o	encoded stream (paritybits at end)
*
***************************************************************************
*
* DESCRIPTION
*
*		This subroutine is part of a set of subroutines which perform
*	a Generalized Hamming Code.  As you know, Hamming codes are perfect
*	codes and can only detect and correct one error.  We added an overall
* 	parity checkbit, which allows us to detect 2 errors.  When 2 errors
*	are detected, (in subroutine decodeham) no correction attempt is
*	made.  This would most likely result in more errors.  Instead, a flag
*	is sent to the calling program notifying it of multiple errors so
*	that smoothing may be attempted.  The Hamming codes presently supported
*	by the routines are (63,57), (31,26), (15,11), and shortened variations
*	thereof.  It could be made even more general by making minor 
*	modifications to the decimal to binary output vector code in the 
*	encodeham procedure.  This routine at present will calculate
*	a maximum of 6 bits.
*
*	Hamming routines consist of the following procedures:
*
*		matrixgen - generates the hmatrix and sydrometable.
*		encodeham - generates the code word and overall paritybit.
*		decodeham - recovers infobits, checks for errors, corrects 1
*			    error, and sends out flag for smoothing.
*
*
*               This subroutine performs the Hamming encode function.
*		It will calculate the necessary parity bits, depending on 
*		which code is requested, and will add the overall parity bit 
*		to the end of the code word generated.
*
*
***************************************************************************
*
* CALLED BY
*
*	celp
*
* CALLS
*
*
***************************************************************************
*
* REFERENCES
*
*	Lin and Costello : Error Control Coding
*	Berlekamp : Algebraic Coding Theory
*
**************************************************************************/
#define PARITYFLAG	1
encodeham(codelength1, codelength2, hmatrix, paritybit, codeword)
int codelength1, codelength2, hmatrix[], *paritybit, codeword[];

{
  int temp, i, *codeptr = &codeword[codelength1];

  /*	First generate the parity bits for the Hamming code word.  This is
	relatively straightforward.  hmatrix was generated in matrixgen.c,
	which is called as part of the Hamming initialization routines.	*/

  for (temp = i = 0; i < codelength2; i++)
  {
    if (codeword[i] != 0)
      temp ^= hmatrix[i];
  }

  /*	since the hmatrix is stored in a packed decimal format, the parity
	bits must be unpacked and appended to the end of the bitsteam.
	after this code you will have the complete code word.  	 	 */

  /* 	the following code converts a decimal number into a binary output 
     	vector.								 */

  for (i = codelength1 - codelength2; --i >= 0;)
    *--codeptr =(temp & 1<<i)>>i;

  /*	Now I check to see if the parityflag is set, indicating the user
	requests an overall parity bit be generated.  Normally this will
	be the case.							 */

#if PARITYFLAG == 1
  for (temp = i = 0; i < codelength1; i++)
  {
    temp ^= codeword[i];
  }
  *paritybit = temp;
#endif
}

/**************************************************************************
*
* ROUTINE
*               decodeham
*
* FUNCTION
*               This subroutine decodes the bitstream generated by
*		encodeham.  It will correct a single error, and detect 2
*		errors.
*
*
* SYNOPSIS
*               subroutine decodeham(codelength1, hmatrix, syndrometable,
*			paritybit, codeword, twoerror, synflag)
*
*   formal
*
*                       data    I/O
*       name            type    type    function
*       -------------------------------------------------------------------
*       codelength1	int	i	number of data bits
*	hmatrix		int	i	vector to encode a decode by
*	syndrometable	int	i	errormasks used to correct single
*					errors
*	paritybit	int	i	overall parity bit
*	codeword	int	i/o	encoded/decoded stream
*	twoerror	int	o	flag for 2 error detect
*	synflag		int	o	value 0 or 1, 1 if syndrome  !=  0
*
***************************************************************************
*
* DESCRIPTION
*
*		This subroutine is part of a set of subroutines which
*	perform a Generalized Hamming Code.  As you know, Hamming codes
*	are perfect codes and can only detect and correct one error.  We
* 	added an overall parity checkbit, which allows us to detect 2 errors.
*	When 2 errors are detected, (in subroutine decodeham) no correction
*	attempt is made.  This would most likely result in more errors.
*	Instead, a flag is sent to the calling program notifying it of
*	multiple errors so that smoothing may be attempted.  The Hamming
*	codes presently supported by the routines are (63,57), (31,26),
*	(15,11), and shortened variations thereof.  It could be made even 
*	more general by making minor modifications to the decimal to binary 
*	output vector code in the encodeham procedure.  This routine at  
*	presentwill calculate a maximum of 6 bits.
*
*	Hamming routines consist of the following procedures:
*
*		matrixgen - generates the hmatrix and sydrometable.
*		encodeham - generates the code word and overall paritybit.
*		decodeham - recovers infobits, checks for errors, corrects 1
*			    error, and sends out flag for smoothing.
*
*
*	This subroutine, decodeham, is responsible for checking for errors,
*	correcting the error if there is only one, and sending a smoothing
*	flag to the calling routine if there is more than one.
*
***************************************************************************
*
* CALLED BY
*
*	celp
*
* CALLS
*
*
***************************************************************************
*
* REFERENCES
*
*	Lin and Costello : Error Control Coding
*	Berlekamp : Algebraic Coding Theory
*
**************************************************************************/
#define TRUE	1
#define FALSE	0
decodeham(codelength1, hmatrix, syndrometable,
	  paritybit, codeword, twoerror, synflag)
int codelength1, hmatrix[], syndrometable[];
int paritybit, codeword[], *twoerror, *synflag;
{
  int parityflag, errorflag, i, j;

  *twoerror = FALSE;
  errorflag = 0;
  parityflag = 1;

  /* This part of the routine checks the overall parity of the code word and
     compares it with the overall paritybit sent.  If they are not the same
     that means there is at least one error.  If, later on in the routine,
     the syndrome check indicates that there is an error and the parity is
     correct in this part of the routine, that indicates there are two
     errors.  One of the weaknesses of this method is that there is no way
     of knowing if we have 3,5,7,... errors.  We always smooth if there are
     2,4,6,... errors.	 						 */

  if (parityflag == 1)
  {
    for (*synflag = i = 0; i < codelength1; i++)
      *synflag ^= codeword[i];
    if (paritybit != *synflag)
      errorflag++;
  }

  /* This part of the routine generates the syndrome.  The syndrome will
     equal zero if there are no errors.  synflag accumulates the syndrome
     and is used as the offset in the syndrome table, which tells the 
     routine which bit is in error.					 */

  for (*synflag = i = 0; i < codelength1; i++)
  {
    if (codeword[i] != 0)
      *synflag ^= hmatrix[i];
  }

  /* *** Check to see if the parityflag is set and if it is then check to see
     if the parity bit was in error. If the parityflag was set and there was
     an error in the syndrome, the errorflag should equal 1. If it doesn't,
     then there are more errors than can be corrected and the infobits are
     passed on unchanged.			 			 */

  if (*synflag != 0)
  {
    if (errorflag != 1 && parityflag == 1)
    {
      *twoerror = TRUE;
      return;
    }

    j = syndrometable[*synflag - 1];
    codeword[j - 1] ^= 1;
  }

  /* *** If the syndrome is equal to zero and the errorflag is set (not
     likely, but must be checked) then more than one error has occured, 
     but it cannot be corrected, so I pass on the infobits the same as  
     if there were no errors.				 		 */

}