Summer 2000

Lab 13: Parity Checker

CS61C

Purpose:

Understanding a simple, yet effective, way to detect errors within blocks of data.

Introduction:

RAID ( Redundant Array of Inexpensive Disks ) technology, developed at UC Berkeley, has been around for sometime. You may already be familiar with some of the various levels corresponding to this technology.

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:

The parity bit for a bitstream is defined to be 0 if there is an even number of 1's in the stream, or 1 if there is a odd number of 1's in the stream. (Hint: think xor.) For example, the parity bit for 101 is 0, while the parity bit for 100 is 1. Specifically, this is known as even parity. In odd parity, the parity bit is the opposite. An easy way to remember it is that in even parity, there is always an even number of 1's (including the parity bit). In odd parity, there is always an odd number. In this lab, you will use even parity. You are asked to write two mips assembly functions for parity checking: encode_parity and check_parity.

Prelab:
1. Complete the following tables by filling in the X's.

Bit 17161514131211 109876543210
a) X100111011 00110110
b) X0100010 1110101011
c) 01110111 X100100010
d) 0010X110 1011100100

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:

Turn in your prelab to your TA at the beginning of lab. Submit lab13.s as usual before the time you would ordinarily have discussion section. Please follow the instructions inside of lab13.s and do not modify any code above the designated line.

Last updated: 11/15