Objectives
- a. Understanding number representation of integers and floats
- b. Bit manipulation of integers
The assignment is divided into two sections a written part, which solves problems with number representations, and a programming part, which looks at, bit manipulation.
Submission
Submission must be in cuLearn by the due date.
Part I - submission in cuLearn.
Part II - Program submission: submit a single tar file with all the .c and .h files and readme files.
Grading
You can earn points as you submit you assignment. Namely, marks will be added as you correctly complete the assignment.
Part I
4 points for each question.
Part II - programming
- a. Proper documentation, meaning variables, ease of reviewing program compiles with no errors and no warnings.
- b. Functions in the bit_manipulation.c were correctly coded.
- c. Transmit program is correct
- a. correctly setting the parity bits
- b. Providing an example of the input and output of the program
- c. Providing a transmitReadMe file that describes how to compile and use the program.
- d. Receive program is correct
- a. Correctly completing the function for error correction
- b. Correctly completing the function for converting from short integer to char
- c. Providing an example of the input and output of the program
- d. Providing a receiveReadMe file that describes how to compile and use the program.
Part I: Number representation
Show your work.
- 1) How many different values can be represented using 7 digits in Binary Systems? In Hexadecimal Systems? Justify your answer
- 2) Find the decimal equivalent of the following:
(a) (631)8 (b) (FCA1)16 (c) (3738)8 (d) (10110100)2 (e) (010101)2 - 3) What is the simple binary, octal and hexa equivalent of following decimal numbers:
(i) 201 (ii) 1193 (iii) 1925 - 4) Assume that there are 7-bits that are available to store a binary number. Specify the range of numbers that can be represented by the following number systems:
a) Unsigned Integers (i.e. only positive numbers) b) 2’s Complement c) 1’s Complement - 5) Perform the operation on the following 8-bit binary numbers assuming that the numbers are represented in 2’s-complement notation.
a) 01011101 + 10100101 b) 10110111 - 11001011 c) 00000111 * 00000101 - 6) Convert the following decimal numbers into 1’s complement, and 2’s complement representations. Assume that 8 bits are used to store the numbers.
a) 70 b) 0 c) -128 d) -2 - 7) Find the decimal equivalent of the following binary numbers assuming that each number is expressed in: (i) unsigned integer (ii) 1’s complement (iii) 2’s complement iv) Excess 127
(a) 01011000 (b) 10101001 - 8) Convert the following binary integers directly into (i) octal (ii) hexadecimal
(a) 101111110010 (b) 000101111110 - 9) Assuming that you are required to make an 8 bit floating point representation, with a 3 bit exponent using excess-3 notation and a 4 bit mantissa using normalized notation. How would the number 0.5 be stored in the byte?
Part II Programming - Error Correction Code
First: A Note on The Hamming Code: Used for Error Detection and Correction
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.
Error Detection: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.
Error Correction: 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. Therefore, bits in position 0. 13,14,15 are not used.
Setting the error detection bits: 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
X4 = X5 + X6 + X7 + X12
X2 = X3 + X6 + X7 + X10 + X11
X1 = X3 + X5 + X7 + X9 + X11
[e.g., X8 = (X9 + X10 + X11 + X12 ) % 2 or X8 = (X9 ^ X10 ^ X11 ^ X12 ) ]
Error Detection and Correction: 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 should be zero (checksum for X8)
X4 + X5 + X6 + X7 + X12 should be zero (checksum for X4)
X2 + X3 + X6 + X7 + X10 + X11 should be zero (checksum for X2)
X1 + X3 + X5 + X7 + X9 + X11 should be zero (checksum for X1)
Suppose the checksums for X8 and for X2 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:
X8 X4 X2 X1
1 0 1 0 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.
Tasks
In this assignment you will write two short programs that would simulate the transmission a message over a communication line: one program would simulate the transmission of a message (an array of characters) and one that simulate the receiving of a message.
You will use the skeleton in the files transmit.c and receive.c. Helper functions that manipulate bit data should be written in a file bit_manipulation.c
Coding Instructions
- 1) Commenting in Code - as provided in the slides given in class
- 2) No usage of global variables. All data must be passed or received via function parameters.
- 3) Write short and simple functions.
- 4) Suggestion - as you code your small helper functions write small test functions to ensure that the code is correct. This will allow you to focus on the logic of your program without worrying about the simple functions.
bit_manipulation file
The file contains some functions that are required by the main programs.
- Review the functions in the file and their purpose
- Complete the code for each of the functions.
- Add other functions as needed
Transmit program
- Add a function to bit_manipulation.c that takes as input an a short integer num and returns the number of bits that are set to 1. For example if num is 0x9 then the function returns 2. Here you need to declare the function and also add the prototype to the bit_manipulation.h header file.
- Using the function that you created in 1 above add the code to the setParityBits function.
- Use the functions in the bit_manipulation.c file
Receive program
The provided code can already read the encoded message that is provided into an array of integers. The program uses the output from the Transmit program as input to the receive program. Using the provided skeleton do the following:
- Write a function to collects (unpacks) the bits from the encoded short integer into a character. The function is int short2Char(short encodedChar, char *c) which takes an encodedChar (a short integer) and updates the character with the correct bits. Namely, it maps bits 3,5,6,7,9,10,11,12 of the encodedChar onto bits 0,1,2,3,4,5,6,7 of c. Review the code of the function char2Short() in the Transmit program.
- Complete the code of correctCode using the function that you coded in step 1 of the Transmit program and the functions in bit_manipulation.c
- Use the functions in the bit_manipulation.c file
Compiling the programs.
Compile the transmit program
Here we have two files for each program (e.g., transmit.c and bit_manipulation.c). Compiling the program will be as follows:
gcc -o tran transmit.c bit\_manipulation.c
Compiling for the debugger will be as follows:
gcc -g -o tran transmit.c bit\_manipulation.c
Compile the receive program
Here we have two files for each program (e.g., transmit.c and bit_manipulation.c). Compiling the program will be as follows:
gcc -o recv receive.c bit\_manipulation.c
Compiling for the debugger will be as follows:
gcc -g -o recv receive.c bit\_manipulation.c
Execution
- a. Start the transmit program. The program will prompt the user to enter a message. The program will then print the transmitted message as a sequence of short integers.
- b. Start the receive message. The program will prompt the user to enter the transmitted message. Here you will have to copy the output from transmit program. The program should output the uncorrected transmitted message and the corrected message.