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 00000001Address / Big-Endian representation of 1025 / Little-Endian representation of 1025
03 / 00000000
00000001 / 00000001
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 endianAddress 27 / Address 28
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?
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=4+3 = 7
There will be 7 bits in the code word, numbered from bit1 to bit7Bit Name and Position Number / Bit Position in Binary
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.
The data to be stored is 1101 using even parity. Write down the parity bits.
First calculate the parity bits here:
r1 = ______
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.
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.