Typically data is transmitted along a transmission line by moving a byte to a register in a «serial interface chip» which converts the eight bit byte into a stream of bits which are transmitted from the serial port of the computer one at a time. At the other end the bits come into the serial port of the computer at the other end where there is a similar chip which collects the bits coming in serial fashion and then outputs the reconstituted byte to the CPU.

Unfortunately, during the transmission, there is a possibility of noise in the line which can result in bit flipping that is can result in a change in the value of the occasional bit. We assume that the noise level is such that at most one bit will be flipped. The simplest approach to error detection is the parity check. An extra bit is added to the byte and is set so that the total number of ones in the pattern (including the parity bit) is, say, always even. This is called even parity. The other choice is odd parity, if the total numbers of ones in the pattern is odd. If after transmission, the total number of ones is found to be odd, then an error has been detected. However, it is impossible to say which bit has been flipped and so there is no correction possible.

An approach which can both detect and correct errors is called the Hamming code. It involves adding not one but four extra bits to the data to allow both error detection and correction. These bits are called check bits. Using this particular version of the code, one can encode up to 15 bits (including the 4 check bits which can also suffer errors in transmission). There are other versions of the hamming code which can encode larger numbers of bits using more check bits. For purposes of the algorithm, the four check bits are labelled bits 1, 2, 4 and 8 although they can go anywhere. They are indicated by the letter «c» below. The data bits are labelled with the letter «d» below.

We are using the ASCII code which uses only eight bits. Treat the last data bits as zero. If we assume even parity, then the check bits are set using the following equations: The plus signs mean either (mod 2 addition) or (exclusive or). To encode, we calculate the 4 check bits using the following equations.

X8 = X9 + X10 + X11 + X12 + X13 + X14 + X15

X4 = X5 + X6 + X7 + X12 + X13 + X14 + X15

X2 = X3 + X6 + X7 + X10 + X11 + X14 + X15

X1 = X3 + X5 + X7 + X9 + X11 + X13 + X15

[e.g., X8 = (X9 + X10 + X11 + X12 + X13 + X14 + X15) % 2 or X8 = (X9 ^ X10 ^ X11 ^ X12 ^ X13 ^ X14 ^ X15) ]

Now the entire group of 15 bits are assumed to be transmitted and received at the other end. And now one has to look for possible errors in transmission. To decode we see if the parity of each of the groups has been maintained. To decode, form the mod 2 sums or the EXCLUSIVE OR's of the following:

X8 + X9 + X10 + X11 + X12 + X13 + X14 + X15 should be zero (checksum for X8)

X4 + X5 + X6 + X7 + X12 + X13 + X14 + X15 should be zero (checksum for X4)

X2 + X3 + X6 + X7 + X10 + X11 + X14 + X15 should be zero (checksum for X2)

X1 + X3 + X5 + X7 + X9 + X11 + X13 + X15 should be zero (checksum for X1)

Suppose the checksums for X8 and forX2 both give one rather then zero and the other two check sums give the correct value of zero. Then the bit in error is found by forming the following binary number:

the incorrect bit is thus bit 10.

So to get the incorrect bit you just have to form the following formula:

Incorrect bit = 8* (checksum for X8) + 4* (checksum for X4) + 2* (checksum for X2) + (checksum for X1)

If all check sums are zero then this gives a zero which means that all is well.

You will in this assignment simulate the data transmission by doing the following steps. In fact your main program should just input and output the «transmitted» character and call the rest of the functions in turn.

1. Ask the user to enter a character to be «transmitted» and a bit number to be flipped (range 0-15) which simulates noise in the line (zero means no bit flipped)
2. Call a function to unpack the bits of the input character into an array of 15 ints each of which stores a bit i.e. a zero or a one (see notes). Store the 8 character bits into elements 3,5,6,7,9,10,11,12 leaving other elements zero. Note, elements 13 through 15 are «dummy» data and should be set to zero.
3. Use the following function declaration: int encodeChar(char c, int code[]);
4. Call a function to set the 4 check bits, i.e. bits 1,2,4,8.
5. Use the following function declaration: int setCheckBits(int *code);
6. The array is now assumed to be transmitted and you must simulate noise. Call a function which gets as input the array and the number of the bit to be flipped in the array. This may be any of the 15 bits
7. Use the following function declaration: int flipBit(int code[], int bitNum);
8. Now call a function to simulate the error detection. The array gets passed to the function which returns an int with the incorrect bit number or zero if there are no errors.
9. Use the following function declaration: int checkCode(int *code);
10. If necessary, call a function which gets the array and the incorrect bit number as determined in requirement 5 (above) as input and corrects the bit.
11. Use the following function declaration: int correctTransmission(int code[], int wrongBit);
12. Call a function which gets the array, discards the data bits and repacks the «real» data bits into a

int encodeChar(char c, int code[]);
int setCheckBits(int *code);
int flipBit(int code[], int bitNum);
int checkCode(int *code);
char decodeChar(int code[]);
int correctTransmission(int code[], int wrongBit);

 
int encodeChar(char thechar, int code[]){
int value = (int) thechar;
code[15] = 0;
code[14] = 0;
code[13] = 0;
code[12] = ((value >> 0) % 2);
code[11] = ((value >> 1) % 2);
code[10] = ((value >> 2) % 2);
code[9] = ((value >> 3) % 2);
code[8] = 0;
code[7] = ((value >> 4) % 2);
code[6] = ((value >> 5) % 2);
code[5] = ((value >> 6) % 2);
code[4] = 0;
code[3] = ((value >> 7) % 2);
code[2] = 0;
code[1] = 0;
return 0;
}
 
int correctTransmission(int code[], int wrongBit){
if (code[wrongBit]==0){code[wrongBit]=1;}
else {code[wrongBit]=0;}
}
 
char decodeChar(int code[]){
int x=(code[3]*128)+(code[5]*64)+(code[6]*32)+(code[7]*16)+(code[9]*8)+(code[10]*4)+(code[11]*2)+(code[12]);
char answer=(char)x;
return answer;
}
 
int setCheckBits(int *code){
code[8]=(code[9]+code[10]+code[11]+code[12]+code[13]+code[14]+code[15])%2;
code[4]=(code[5]+code[6]+code[7]+code[12]+code[13]+code[14]+code[15])%2;
code[2]=(code[3]+code[6]+code[7]+code[10]+code[11]+code[14]+code[15])%2;
code[1]=(code[3]+code[5]+code[7]+code[9]+code[11]+code[13]+code[15])%2;
return 0;
}
 
int flipBit(int code[], int bitNum){
if (code[bitNum]==0){code[bitNum]=1;}
else {code[bitNum]=0;}
}
 
int checkCode(int *code){
int bit[3];
int answer;
bit[0]=(code[8]+code[9]+code[10]+code[11]+code[12]+code[13]+code[14]+code[15])%2;
bit[1]=(code[4]+code[5]+code[6]+code[7]+code[12]+code[13]+code[14]+code[15])%2;
bit[2]=(code[2]+code[3]+code[6]+code[7]+code[10]+code[11]+code[14]+code[15])%2;
bit[3]=(code[1]+code[3]+code[5]+code[7]+code[9]+code[11]+code[13]+code[15])%2;
answer=8*bit[0]+4*bit[1]+2*bit[2]+bit[3];
return answer;
}

#include <stdio.h>
 
int encodeChar(char c, int code[]);
int setCheckBits(int *code);
int flipBit(int code[], int bitNum);
int checkCode(int *code);
char decodeChar(int code[]);
int correctTransmission(int code[], int wrongBit);
 
int main(void){
char thechar;
int noise;
char decoded;
int code[16];
 
printf("Please, enter the character you want to encode:\n");
scanf("%c", &thechar);
 
printf("Please, enter the noise in line (0 to 15):\n");
scanf("%d", &noise);
	if (noise<0){noise=0;}
	if (noise>15){noise=15;}
 
encodeChar(thechar, code);
decoded=decodeChar(code);
printf("\nI am transmitting character %c\n", thechar);
printf("It is being corrupted by flipping bit %d\n", noise);
 
 
setCheckBits(code);
flipBit(code, noise);
decoded=decodeChar(code);
printf("The corrupted character is %c\n", decoded);
 
int error=checkCode(code);
if (error>0){correctTransmission(code, error);}
decoded=decodeChar(code);
printf("The correct character is %c\n", decoded);
 
}
 
int encodeChar(char thechar, int code[]){
int value = (int) thechar;
code[15] = 0;
code[14] = 0;
code[13] = 0;
code[12] = ((value >> 0) % 2);
code[11] = ((value >> 1) % 2);
code[10] = ((value >> 2) % 2);
code[9] = ((value >> 3) % 2);
code[8] = 0;
code[7] = ((value >> 4) % 2);
code[6] = ((value >> 5) % 2);
code[5] = ((value >> 6) % 2);
code[4] = 0;
code[3] = ((value >> 7) % 2);
code[2] = 0;
code[1] = 0;
return 0;
}
 
int correctTransmission(int code[], int wrongBit){
if (code[wrongBit]==0){code[wrongBit]=1;}
else {code[wrongBit]=0;}
}
 
char decodeChar(int code[]){
int x=(code[3]*128)+(code[5]*64)+(code[6]*32)+(code[7]*16)+(code[9]*8)+(code[10]*4)+(code[11]*2)+(code[12]);
char answer=(char)x;
return answer;
}
 
int setCheckBits(int *code){
code[8]=(code[9]+code[10]+code[11]+code[12]+code[13]+code[14]+code[15])%2;
code[4]=(code[5]+code[6]+code[7]+code[12]+code[13]+code[14]+code[15])%2;
code[2]=(code[3]+code[6]+code[7]+code[10]+code[11]+code[14]+code[15])%2;
code[1]=(code[3]+code[5]+code[7]+code[9]+code[11]+code[13]+code[15])%2;
return 0;
}
 
int flipBit(int code[], int bitNum){
if (code[bitNum]==0){code[bitNum]=1;}
else {code[bitNum]=0;}
}
 
int checkCode(int *code){
int bit[3];
int answer;
bit[0]=(code[8]+code[9]+code[10]+code[11]+code[12]+code[13]+code[14]+code[15])%2;
bit[1]=(code[4]+code[5]+code[6]+code[7]+code[12]+code[13]+code[14]+code[15])%2;
bit[2]=(code[2]+code[3]+code[6]+code[7]+code[10]+code[11]+code[14]+code[15])%2;
bit[3]=(code[1]+code[3]+code[5]+code[7]+code[9]+code[11]+code[13]+code[15])%2;
answer=8*bit[0]+4*bit[1]+2*bit[2]+bit[3];
return answer;
}