#include #include #include #include /* hamming.c : This program demonstrates how 7-bit ASCII characters may be encoded and transmitted using the 11-bit Hamming encoding scheme. The Hamming scheme permits the detection and correction of a single bit error in each 7->11 bit transmission. It is, however, computationally expensive to perform and such correction is not generally performed in practice. The program may be invoked with either the -e or -o flags. The program first accepts a single ASCII character from the keyboard, displays it as a 7-bit binary value (with no parity) and then shows how the 7 data bits and the 4 check bits are calculated and positioned within the 11-bit Hamming encoding. This 11-bit pattern is then (ficticiously) transmitted. The user is then asked to supply the 11 bits as they are received, ideally with at most 1 bit in error. The program then states what character is received and performs checking of the check bits to determine if the received bit pattern was a valid one. In conclusion, the program states if the character was received correctly, needs correction to another character, or if Hamming's encoding is unable to detect an error (if more than 1 bit transition). Compile with (on Linux or macOS): cc -std=c99 -Wall -o hamming hamming.c -lncurses Written by Chris.McDonald@uwa.edu.au, Dec 1993- */ #define PARITY(n_1s) (even ? EVEN(n_1s) : ODD(n_1s)) #define WHICH (even ? "even" : "odd") #define EVEN(n_1s) ('0' + (n_1s % 2)) #define ODD(n_1s) ('1' - (n_1s % 2)) static char *ascii_table[] = { "NUL", "SOH", "STX", "ETX", "EOT", "ENQ", "ACK", "BEL", "BS ", "HT ", "NL ", "VT ", "NP ", "CR ", "SO ", "SI ", "DLE", "DC1", "DC2", "DC3", "DC4", "NAK", "SYN", "ETB", "CAN", "EM ", "SUB", "ESC", "FS ", "GS ", "RS ", "US ", "SP ", " ! ", " \" ", " # ", " $ ", " % ", " & ", " ' ", " ( ", " ) ", " * ", " + ", " , ", " - ", " . ", " / ", " 0 ", " 1 ", " 2 ", " 3 ", " 4 ", " 5 ", " 6 ", " 7 ", " 8 ", " 9 ", " : ", " ; ", " < ", " = ", " > ", " ? ", " @ ", " A ", " B ", " C ", " D ", " E ", " F ", " G ", " H ", " I ", " J ", " K ", " L ", " M ", " N ", " O ", " P ", " Q ", " R ", " S ", " T ", " U ", " V ", " W ", " X ", " Y ", " Z ", " [ ", " \\ ", " ] ", " ^ ", " _ ", " ` ", " a ", " b ", " c ", " d ", " e ", " f ", " g ", " h ", " i ", " j ", " k ", " l ", " m ", " n ", " o ", " p ", " q ", " r ", " s ", " t ", " u ", " v ", " w ", " x ", " y ", " z ", " { ", " | ", " } ", " ~ ", "DEL" }; static void read11bits(int y, int x, char *buf) { #define LEN 11 #define BS 8 char ch, *s=buf; while(true) { ch = mvgetch(y,x); if(ch == BS) { // allow even the 11th character to be corrected if(s > buf) { s--; move(y,--x); delch(); refresh(); } continue; } if((s-buf) == LEN) { // have we got 11 characters yet? *s = '\0'; // yes, NULL terminate and return return; } if(ch == '0' || ch == '1') { // make sure any other characters *s++ = ch; addch(ch); ++x; // are the bits 0 and 1 } else /* beep() */; refresh(); } } static void ch2ascii(int ch, char *a) { int power = 64; a++; do { *a++ = (ch&power) ? '1' : '0'; } while(power /= 2); *a = '\0'; } static void ascii2ch(char *a, int *ch) { *ch = 0; for(int i=1; i<=7; i++) *ch = (*ch*2) + (a[i]-'0'); } static void ascii2hamming(char *a, char *h) { h[ 3] = a[1]; h[ 5] = a[2]; h[ 6] = a[3]; h[ 7] = a[4]; h[ 9] = a[5]; h[10] = a[6]; h[11] = a[7]; h[12] = '\0'; } static void hamming2ascii(char *h, char *a) { a[1] = h[ 3]; a[2] = h[ 5]; a[3] = h[ 6]; a[4] = h[ 7]; a[5] = h[ 9]; a[6] = h[10]; a[7] = h[11]; a[8] = '\0'; } // ------------------------ Display Stuff --------------------------- static bool initdone = false; static void InitDisplay(void) { initscr(); initdone = true; noecho(); nonl(); raw(); clear(); refresh(); } static void EndDisplay(int why) { if(initdone) endwin(); } static void Hamming(bool even) { InitDisplay(); mvaddstr(0,0, "This program demonstrates Hamming's encoding technique to correct single bit"); mvaddstr(1,0,"errors in 7-bit ASCII characters, transmitted as 11 bits "); printw("(with %s parity)",WHICH); mvaddstr(3,0,"Input an ASCII character:"); int again = 'y'; do { int i, ch, sum; char ascii7 [16]; char send11 [16]; char recv11 [16]; move(3,26); clrtobot(); refresh(); ch = getch() & 0177 ; ch2ascii(ch,ascii7); ascii2hamming(ascii7,send11); mvaddstr(3,36,"In binary (with no parity):"); standout(); mvaddstr(3,26,ascii_table[ch]); mvaddstr(3,64,ascii7+1); standend(); refresh(); mvaddstr(5,5,"Bit position: 1 2 3 4 5 6 7 8 9 10 11"); mvaddstr(7,5,"Data bits:"); standout(); mvaddch(7,20 + 4* 3,ascii7[1]); mvaddch(7,20 + 4* 5,ascii7[2]); mvaddch(7,20 + 4* 6,ascii7[3]); mvaddch(7,20 + 4* 7,ascii7[4]); mvaddch(7,20 + 4* 9,ascii7[5]); mvaddch(7,20 + 4*10,ascii7[6]); mvaddch(7,20 + 4*11,ascii7[7]); standend(); mvaddstr( 8,5,"Check bit 1: X X X X X"); mvaddstr( 9,5,"Check bit 2: X X X X X"); mvaddstr(10,5,"Check bit 3: X X X"); mvaddstr(11,5,"Check bit 4: X X X"); refresh(); #define bit(i) (ascii7[i]-'0') i = bit(1)+bit(2)+bit(4)+bit(5)+bit(7); send11[1] = PARITY(i); i = bit(1)+bit(3)+bit(4)+bit(6)+bit(7); send11[2] = PARITY(i); i = bit(2)+bit(3)+bit(4); send11[4] = PARITY(i); i = bit(5)+bit(6)+bit(7); send11[8] = PARITY(i); standout();mvaddch( 8,24,send11[1]);mvaddch( 9,28,send11[2]); mvaddch(10,36,send11[4]);mvaddch(11,52,send11[8]);standend(); move(13,0); printw("Using Hamming encoding (with %s parity) we transmit: ",WHICH); standout(); mvaddstr(13,55,send11+1); standend(); // NOW, RECEIVE A BIT PATTERN AND ATTEMPT TO DETECT AND CORRECT AN ERROR mvaddstr(14,25,"What bit pattern is received? "); refresh(); standout(); read11bits(14,55,recv11+1); standend(); hamming2ascii(recv11,ascii7); ascii2ch(ascii7,&ch); mvaddstr(15,0,"Hmmm, a ' ' eh?"); standout(); mvaddstr(15,9,ascii_table[ch]); standend(); refresh(); #undef bit #define bit(i) (recv11[i]-'0') sum = 0; mvaddstr(16,5,"Check bit 1 is "); addch(recv11[1]); i = bit(3)+bit(5)+bit(7)+bit(9)+bit(11); if(PARITY(i) == recv11[1]) addstr(", correct"); else printw(", should be %c sum+=1 (=%2d)",PARITY(i),sum+=1); mvaddstr(17,5,"Check bit 2 is "); addch(recv11[2]); i = bit(3)+bit(6)+bit(7)+bit(10)+bit(11); if(PARITY(i) == recv11[2]) addstr(", correct"); else printw(", should be %c sum+=2 (=%2d)",PARITY(i),sum+=2); mvaddstr(18,5,"Check bit 3 is "); addch(recv11[4]); i = bit(5)+bit(6)+bit(7); if(PARITY(i) == recv11[4]) addstr(", correct"); else printw(", should be %c sum+=4 (=%2d)",PARITY(i),sum+=4); mvaddstr(19,5,"Check bit 4 is "); addch(recv11[8]); i = bit(9)+bit(10)+bit(11); if(PARITY(i) == recv11[8]) addstr(", correct"); else printw(", should be %c sum+=8 (=%2d)",PARITY(i),sum+=8); standout(); if(sum == 0) mvaddstr(21,1,"The character was received without error"); else { recv11[sum] = (recv11[sum] == '1' ? '0' : '1'); hamming2ascii(recv11,ascii7); ascii2ch(ascii7,&ch); move(21,1); printw("Bit %d is wrong, character corrected to '%s'", sum,ascii_table[ch]); ch = 0; for(int i=1; i<=11; i++) if(send11[i] != recv11[i]) ch++; if(ch>1) addstr(" (naughty)"); } standend(); mvaddstr(21,60,"Another (y/n)? "); refresh(); again = getch(); } while(again == 'y' || again == 'Y'); EndDisplay(0); } // --------------------------------------------------------------------- typedef void (*sighandler_t)(int); int main(int argc, char *argv[]) { bool even = true; ++argv, --argc; // skip argv[0] while(argc > 0 && argv[0][0] == '-') { switch ((int)argv[0][1]) { // WE WANT even PARITY case 'e' : even = true; break; // WE WANT odd PARITY case 'o' : even = false; break; } ++argv, --argc; // skip argument } signal(SIGINT, (sighandler_t) EndDisplay); signal(SIGBUS, (sighandler_t) EndDisplay); signal(SIGSEGV,(sighandler_t) EndDisplay); signal(SIGQUIT,(sighandler_t) EndDisplay); Hamming(even); return 0; } // vim: ts=8 sw=4