Objective:

The objective of this assignment is to implement a simple parity checking algorithm for use in error detection. This should then be extended as outlined in the course notes.

Operating System:

This practical should be done through your Solaris accounts.

To use the java compiler and virtual machine in Solaris you may first need to enter in the following command in the shell:

set path=($path /usr/local/java/java1.2/bin)

This has the effect of adding the java binary directory to your path, which means that the next time you type javac your shell will be able to find it.

Introduction:

In this practical the student will implement new routines in the BitDisplay class developed last week. As mentioned in the lectures over the past few weeks one of the major tasks of the data-link layer is to provide error detection (and sometimes error correction). This is due to the fact that the physical layer is inherently noisy and hence can causes errors to be introduced in the data transmitted by the data-link layer. The simplest form of error detection is known as parity checking. The parity of a string of bits refers to whether the number of ones in the string is even or odd.
Even parity string:     10110100
Odd parity string:       10110000

Parity checking works by first calculating the parity of a frame, if it is odd a 1 bit is appended to the end of the frame, if it is even a 0 bit is appended. This has the effect of making all frames have even parity. For example for the frames above the transmitted frames would be 101101000, and 101100001 respectively, both of which have even parity.

When the destination data-link layer receives a frame again it simply checks to ensure that it has even parity. If it has then it removes the last bit (known as the data-link trailer) and passes the rest of the frame up to the network layer. (Note in reality the data-link frame will also contain header information which must also be removed.)

To Do:

• Again, assuming integers to be 16 bits in length, add the following methods to BitDisplay:
• int ComputeParity(int ) - computes the parity of the input. Returns: 0 if even, 1 if odd. Note that here we assume that the data is of maximum 15 bits in length so that we have space for the parity bit at the end i.e. the method should shift the bits to the left by one bit prior to appending the parity bit.
• int AppendParity(int ) - shifts input one bit to the left and appends the parity bit in the rightmost bit.
• Verify that the above methods work.

Making Parity Checking More Robust:

One method of making parity checking more robust is to treat the frame as a matrix. This then allows the parity to be computed column-wise. This is best expained through the use of an example. Let's assume that frames are now up such that the most significant 12-bits are used for data and the least significant 4-bits are used by the error detection algorithm. If we start with the following frame (without the lower 4-bits)
1011 1001 1110
then using the standard parity checking algorithm we would simply append a 1 bit onto the 12-bits. Here, on the other hand, we first of all divide the frame into blocks of 4-bits and stack them as follows:
1011
1001
1110
We may now calculate the parity along each column, the result of which would be:
1100.
This result is then appended to the frame (forming 1011 1001 1110 1100) and transmitted.

This technique is much more robust than standard parity since it can garauntee to detect any burst error less than or equal to the the width of the matrix (i.e. 4 in this case but typically much more!).

To Do:

• Add the following methods to BitDisplay:
• int ComputeMParity(int ) - computes the parity matrix as defined above.
• int AppendParity(int ) - shifts input 4 bits to the left and appends the parity bits in the rightmost 4 bits.
• Verify that the above methods work.

Helpful Resources:
Data Link Layer Course Notes (Powerpoints slides)(PostScript Format) Slides 18-23
(Note: These five slides are self contained i.e. you do not need to read slides 1-17 to understand them).

Java How to Program by Deitel & Deitel provides an excellent overview of these functions.

Developing Java Software by Russel Winder & Graham Roberts provides the KeyboardInput class.