hamming.c
上传用户:szhypcb168
上传日期:2007-01-06
资源大小:2187k
文件大小:8k
- /**************************************************************************
- *
- * 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. */
- }