Class Worksheet for some of the topics discussed in CSIT413F’02; Sept 17th

BIG ENDIAN/LITTLE ENDIAN

Assume the number 1025 is to be stored. In binary, it would be:

00000000 00000000 00000100 00000001

Address / Big-Endian representation of 1025 / Little-Endian representation of 1025
00
01
02
03 / 00000000
00000000
00000100
00000001 / 00000001
00000100
00000000
00000000

Many mainframe computers, particularly IBM mainframes, use a big-endian architecture. Most modern computers, including PCs, use the little-endian system. The PowerPC system is bi-endian because it can understand both systems.

Converting data between the two systems is sometimes referred to as the NUXI problem. Imagine the word UNIX stored in two 2-byte words. In a Big-Endian systems, it would be stored as UNIX. In a little-endian system, it would be stored as NUXI.

Specify how the number 17 (represented as 0000 0000 0001 0001) would be stored starting at address location 27, where each location takes one byte only.

Address 27 / Address 28

Big endian

Address 27 / Address 28

Little endian 

Error Correcting with a Distance of 3

Let us specify 3 out of 6 code in which any 3 bits are 1 for a given code word. The condition is that each codeword is at a minimum distance of 3 from the others:

CW1 = 000111

CW2 = 110010

CW3 = 011100

Store CW1 into the memory, read it back as 100111. The codeword is INVALID. But can we find out the original from the word read back?

Hint: Calculate the distance of the invalid codeword from all three valid codewords. The minimum distance would give you the correct word.

Hamming's Algorithm (Step by Step)

How to calculate the number of parity bits required for correcting errors?

Let m=4,

m+r+1 <= 2r, substitute m by 4

5+r <= 2r

Let us make r=1, 6<=2 FALSE

Let us have r=2, 7<=4 FALSE

Let us have r=3, 8<=8 TRUE

Therefore we need 3 parity bits in the code word.

n=m+r

n=4+3 = 7

There will be 7 bits in the code word, numbered from bit1 to bit7

Bit Name and Position Number / Bit Position in Binary
222120
b1 / 001
b2 / 010
b3 / 011
b4 / 100
b5 / 101
b6 / 110
b7 / 111
b7 / r3r2r1 /  Parity bits

Bit position numbers will be counted in binary format, with LSB being r1 and MSB being r3.

Where to place the parity bits in the message?

The parity bits will be placed at positions corresponding to powers of 2.

20  1  position b1

21  2  position b2

22  4  position b4

What bits will be supervised by parity bits?

At position b1 is the parity bit r1. It will supervise ALL bits whose position number carries a 1 in the 20 position. Write down all bit position numbers that carry a 1 in the 20 position.

______

At position b2 is the parity bit r2. It will supervise ALL bits whose position number carries a 1 in the 21 position. Write down all bit position numbers that carry a 1 in the 21 position.

______

At position b4 is the parity bit r3. It will supervise ALL bits whose position number carries a 1 in the 22 position. Write down all bit position numbers that carry a 1 in the 22 position.

______

Example

The data to be stored is 1101 using even parity. Write down the parity bits.

First calculate the parity bits here:

r1 = ______

r2= ______

r3= ______

Position number / b1 / b2 / b3 / b4 / b5 / B6 / b7
Data Bits / 1 / 1 / 0 / 1
Parity bits / r1 / r2 / r3
Final Code Word
Erroneous Code Word

DETECTING THE ERROR LOCATION

Suppose that a bit is altered due to a single error. What is the position of the erroneous bit?

To answer this question, write the last digit of your SS# here______

If this digit is 0, add 2. If it is more than 7, subtract 2 and enter the result______

This is the bit number in error. Change that bit and rewrite the code word in the erroneous code word row in the table above. Now compute check bits c3c2c1.

c3 = (XOR all bits that are supervised by parity bit r3 including itself)=

c2 = (XOR all bits that are supervised by parity bit r2 including itself)=

c1 = (XOR all bits that are supervised by parity bit r1 including itself)=

(RULE: Perform XOR of two bits at a time)

Check bits are read as c3c2c1 to indicate the position number of the error.

c3c2c1 =

Write the bit position number (i.e. b1,b2…..b7)=

Is this the bit in error? Confirm your answer from the table above and answer YES or NO:

If NO, show your worksheet to me for analysis.