Category : Files from Magazines
Archive   : DDJ8606.ZIP
Filename : MARASCO.JUN

/*
* short demo program to illustrate Hamming forward error correction
* code detects and corrects all one bit errors and detects two
* bit errors in a total transmitted block of 16 bits.
* eleven bits are message bits, the rest are error checks
*
* implementation is oriented toward exposition, not speed or
* efficiency -- this is not industrial strength code!
*
* bit fields not implemented in C/80
*
* Joe Marasco, March 1986
*/

#include "fprintf.h"
#define EOF -1

#define B0 1
#define B1 2
#define B2 4
#define B3 8
#define B4 16
#define B5 32
#define B6 64
#define B7 128
#define B8 256
#define B9 512
#define B10 1024
#define B11 2048
#define B12 4096
#define B13 8192
#define B14 16384
#define B15 32768

#define C1 (B1 + B3 + B5 + B7 + B9 + B11 + B13 + B15)
#define C2 (B2 + B3 + B6 + B7 + B10 + B11 + B14 + B15)
#define C3 (B4 + B5 + B6 + B7 + B12 + B13 + B14 + B15)
#define C4 (B8 + B9 + B10 + B11 + B12 + B13 + B14 + B15)

main()
{
int input[11] ; /* input message bits */
register unsigned int xmit ; /* transmitted message */
int recvd[16] ; /* received message bits*/
register unsigned int rec ; /* received message */
int syndrome ; /* computed syndrome */
int recpar ; /* parity of rec'd msg */
int i , ch ;

for (;;) {

printf("input 11 message bits, ^C to quit\n") ;
printf("1 2 3 4 5 6 7 8 9 0 1\n") ;

i = 0 ;
while ( ((ch = getchar()) != EOF) && i<11 )
switch(ch) {
case '0' : input[i++] = 0 ;
break ;
case '1' : input[i++] = 1 ;
break ;
}
/*
* anything but a 0 or 1 is ignored
* check that we have 11 good bits
*/
if ( i < 11 ) {
printf("not enough valid bits, try again\n") ;
continue ;
}
/*
* build the message
*/
xmit = 0 ;
xmit |= input[0] << 3 ;
xmit |= input[1] << 5 ;
xmit |= input[2] << 6 ;
xmit |= input[3] << 7 ;
xmit |= input[4] << 9 ;
xmit |= input[5] << 10 ;
xmit |= input[6] << 11 ;
xmit |= input[7] << 12 ;
xmit |= input[8] << 13 ;
xmit |= input[9] << 14 ;
xmit |= input[10] << 15 ;
/*
* and the check bits -- even parity
*/
xmit |= (parity( C1 & xmit ) << 1) |
(parity( C2 & xmit ) << 2) |
(parity( C3 & xmit ) << 4) |
(parity( C4 & xmit ) << 8) ;
/*
* and last but not least, make total parity even
*/
xmit |= parity( xmit ) ;
/*
* display it
*/
printf("the block sent is %x \n", xmit ) ;
printf("0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5\n") ;
for (i=0 ; i<16 ; ++i)
printf("%d ", ((xmit>>i) & 01) ) ;
printf("\n") ;
printf("now input the received block\n") ;
printf("0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5\n") ;
/*
* get the received message
*/
readagain: i = 0 ;
while ( ((ch = getchar()) != EOF) && i<16 )
switch(ch) {
case '0' : recvd[i++] = 0 ;
break ;
case '1' : recvd[i++] = 1 ;
break ;
}
/*
* anything but a 0 or 1 is ignored
* check that we have 16 good bits
*/
if ( i < 16 ) {
printf("not enough valid bits, try again\n") ;
goto readagain ;
}
for (i=0 , rec=0 ; i<16 ; ++i )
rec |= (recvd[i] << i) ;
printf("the block received is %x \n", rec ) ;
/*
* compute the syndrome
*/
syndrome = parity( C1 & rec ) |
( parity( C2 & rec ) << 1 ) |
( parity( C3 & rec ) << 2 ) |
( parity( C4 & rec ) << 3 ) ;
/*
* and the parity bit, which should be zero
*/
recpar = parity( rec ) ;
/*
* decision time
*/
if ( syndrome == 0 ) {
printf("good message!\n") ;
if (recpar) {
printf("with reversed parity bit\n") ;
rec = rec ^ 01 ;
printf("the recovered block is %x\n",
rec ) ;
printf("0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5\n") ;
for (i=0 ; i<16 ; ++i)
printf("%d ", ((rec>>i) & 01) ) ;
printf("\n") ;
}
printf("---------------------------------\n") ;
}
else {
if (!recpar) {
printf("two bit errors, can't fix\n") ;
printf("--------------------------------\n") ;
}
else {
printf("bad bit in position %d\n",
syndrome ) ;
rec = rec ^ ( 01 << syndrome ) ;
printf("the recovered block is %x\n",
rec ) ;
printf("0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5\n") ;
for (i=0 ; i<16 ; ++i)
printf("%d ", ((rec>>i) & 01) ) ;
printf("\n-------------------------------\n") ;
}
}
}
}
parity( message )
unsigned int message ;
{
/*
* return 1 if odd parity, 0 if even
*/
int j , k ;
for ( j=0 , k=0 ; j<16 ; ++j ) k += ( (message >> j) & 01 ) ;
return( k & 01 ) ;
}