Summer 2000 |
Lab 13: Parity Checker |
CS61C |
Purpose:
Introduction:
We are going to focus on RAID level 3, or simply RAID3. The main idea behind RAID3 is what is known as a "parity disk". This disk simply holds a parity bit corresponding to bits at the same address striped across other disks. In this lab you will be given 16 bits that have been taken from 16 disks ( i.e. the bits have been "striped" across 16 disks). You will then compute the parity for this row of bits as specified below.
Assignment:
Prelab:
1. Complete the following tables by filling in the X's.
Bit 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
a) | X | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
b) | X | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
c) | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | X | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
d) | 0 | 0 | 1 | 0 | X | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
2. Give a brief pseudocode algorithm to calculate the parity (i.e. the number of 1's in the binary number modulo 2) of a given number. You may use loops. You may find the notions of 'xor' and 'shift' useful.
Task 0:
Copy the framework file from ~cs61c/lab13.
Task 1:
encode_parity: Takes a 16 bit value and returns a 17 bit value,
with the lower 16 bits unchanged and with the 17th bit being a parity
check. The exact specifications are in the framework file.
Task 2:
check_parity: Takes a 17 bit value and return 0 if the
parity matches the 16 bit value and 1 otherwise. The exact
specifications are in the framework file.
NOTE: Efficiency is important. You should implement these functions in as few lines as possible! You should not need to have any branches or loops in your code!
Submission Instructions:
Last updated: 11/15