In this programming assignment, you will implement Cyclic Redundancy Check (CRC). CRC is one of the popular methods of the integrity check. It has been used in network transmission. The details of CRC was addressed in L17: Integrity Check and Secure Hash. You can refer to slides NO.7-8 of "17-Integrity Check and Secure Hash.pptx" and 17b-CRC Example.pptx
In the assignment you will implement both CRC calculation and CRC verification. As shown in the example in "17b-CRC Example.pptx", CRC calculation is a long division, where the input message in binary form (with padding) is dividend and a polynomial in binary form is the divisor. In the process of long division, XOR instead of regular subtraction is used. The polynomial is usually a fixed value. In this assignment, you will use the following polynomial.
Polynomial: 1100 1101 1010 1
As shown in the example in "17b-CRC Example.pptx", we must pad the input message with a serials of zeros. The number of the padding zeros depends on the length of polynomial.
Number of padding zeros = length of polynomial -1
In this assignment, since the length of polynomial is 13, you will pad 13-1=12 zeros to the end of the input message. Then this message with padding will be used as dividend in the long division. Calculating a long division with XOR means lining up the polynomial with the leftmost '1' of padded message and then applying XOR instead of subtraction. Please refer to slide "17b-CRC Example.pptx" for the details of long division. After the long division is finished, the remainder is the CRC. However, the length of CRC should be (length of polynomial -1). If the length of remainder is shorter, one or more zeros should be added to the left of the remainder (in this way, the value of the remained is unchanged).
In "17b-CRC Example.pptx", we discussed two options of conducting CRC verification. In this assignment, we ask you to use Option 2 on the slide No. 1 of 17b-CRC Example.pptx. So when message is 0x5AE and CRC is 0x3, the final message is 0x5AE3. So when you verify the CRC, you can calculate CRC again using the message with CRC attached and the polynomial. In other word, you do a long division with message=0x5AE3 (no need for padding 0s) and the polynomial. If this calculation generates an all-zero remainder, the verification is successful. Otherwise, the verification fails.
2.1. Inputs to CRC Calculation
The CRC calculation requires two elements: the input message and the polynomial. Since we already define polynomial, you will ask the user to enter the input message. In this assignment, the command line argument is not required. You can use scanf (in C programming) or Scanner class (in Java) or anything equivalent to take the user inputs. To ease the difficulty of entering a long binary sequence, you will ask the user to enter the message in hexadecimal format. Then your program will translate the hex number string to binary string and use the binary string as the input message to your CRC calculation. The user-entered message should be 3-5 hexadecimal digits. Once CRC value is generated, it will be attached to the original message (without padding). This complete message will be translated into hexadecimal digits. During the verification process, the user will be prompted to enter the message (i.e. the message attached with CRC value) again for verification.
2.2. Intermediate Results
When you calculate the long division, a number of intermediate results will be generated. From the example shown in "17b-CRC Example.pptx", we can see the message is 0x5AE, which can be translated in to 010110101110 and the polynomial is 10011. Then we can express the long division in a table form as shown in Figure 1. The first row is the padded message. In the second row, we line up the polynomial with the leftmost 1. The third line is the result of the first XOR operation. The black digits are the XOR results and red zeros in the row are fillers. In the fourth line, more bit or bits of the message is brought down until it reaches the length of polynomial. Then the long division goes on in the similar way until all the bits have been brought down and calculated. For this example, the final result (remainder) is 100. So the CRC checksum is 0100 (One 0 needs to be added to the left of the remainder to reach the length of the polynomial, which is 4). So in this assignment, you are required to show the rows of XOR results. As shown in Figure 1, the filler 0s (in red) should be used to indicate the position of the XOR result (in black). Although Figure 1 shows a two-dimensional table, you are not required to use matrix to record your intermediate results (i.e. XOR results). You may choose to use a vector and print out the XOR result at every step of the long division.
Figure 1: CRC Long Division in Table Form see image.
2.3. Two-part Process
This assignment contains two parts: CRC calculation and CRC verification. Although they have different purposes, they share the same principles. Once the CRC calculation is done, the CRC verification can re-use the CRC calculation procedure to generate the verification results. The results of both parts will be printed on the screen. To the basic procedure including the input and output requirements is shown as below:
Step 1: Prompt the user to enter the message in hexadecimal format
Step 2: Translate the message from Hex to binary and print out the binary message
Step 3: Print out modified binary message (with padding) and given polynomial in binary
Step 4: Calculate CRC and print out intermediate results
Step 5: Print out CRC value and print out the input message with CRC attached in Hex format
Step 6: Start the verification and prompt the user to enter the message in hexadecimal format. One can enter the complete message generated in Step 5 or modified message (i.e. changing one or two bits in Step 5 message)
Step 7: Translate the message from Hex to binary and print out the binary message
Step 8: Calculate CRC for the input message
Step 9: Examine the CRC value. If the result is all-zeros, print out a successful message. Otherwise print out a failure message. You are required to run at least one successful and one failed CRC verification.
Based on this procedure, the possible modules or function blocks you need to generate for this assignment include CRC calculation module, XOR operation module, hex to binary module, binary to hex module as well as input and output (i.e. print out). Note: although bit level XOR is provided in the programming language, in the assignment we are dealing with characters that can be input and output to the screen. So most likely you will work with ASCII characters. So even if you want to use bit level XOR offered by the programming language, you still have to go through certain converting process. Or you can generate your own XOR operation on character level.