Simtel MSDOS 1992 June/SIMTEL_0692.cdr/msdos/ddjmag/ddj8606.arc/MARASCO.JUN

Text File | 1986-06-30 | 4.6 KB | 186 lines

/*
 * 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 ) ;
}