hamming.h

g729 coding ipaddressing

/**************************************************************************
*
* 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
static void encodeham(int codelength1, int codelength2,
	int a_hmatrix[], int *a_paritybit, int a_codeword[])
{
  int temp, i, *codeptr = &a_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 (a_codeword[i] != 0)
	  temp ^= a_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 ^= a_codeword[i];
  }
  *a_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
*
**************************************************************************/

static void decodeham(int codelength1, int a_hmatrix[], int a_syndrometable[],
		  int a_paritybit, int a_codeword[], int *a_twoerror, int *synflag)
{
  int parityflag, errorflag, i, j;

  *a_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 ^= a_codeword[i];
	if (a_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 (a_codeword[i] != 0)
	  *synflag ^= a_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)
	{
	  *a_twoerror = TRUE;
	  return;
	}

	j = a_syndrometable[*synflag - 1];
	a_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.											 */

}

#undef PARITYFLAG