=== Assignment 10 ===
The following table shows which data bits influence which parity bits. In the
top line the data bits are represented by '-' signs, and the parity bits are
represented by the letters p through u . In the following lines it is marked
which bits are used to calculate parity. The parity bits are set so that each
of these lines has even parity.
pq-r---s-------t---------------u-------------------------------
p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p
qq qq qq qq qq qq qq qq qq qq qq qq qq qq qq qq
rrrr rrrr rrrr rrrr rrrr rrrr rrrr rrrr
ssssssss ssssssss ssssssss ssssssss
tttttttttttttttt tttttttttttttttt
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
It is worth noting that each data bit influences a distinct subset of the parity
bits.
--1--
Three parity bits are required to encode four data bits: The above table shows
that four data bits affect exactly the first three parity bits.
Hence, to store the parities of four (evenly sized) hard disks, it is required
to add three disks for parity information.
--2--
Let m ∈ Nat , and k = 2^m-1 . Then there is a Hamming code that encodes k-m
bits payload into a code word of k bits.
If calculation modulo two is used, 'sum' is 'parity', and 'product' is 'and'.
Then it is easy to construct a (k-m, k) "Generator Matrix" G , so that for a
data word d of k-m bits, the product G · d yields the code word. (We do
not distinguish row-vectors and column-vectors here. To do so, transpose d to
get a column-vector).
For the entries in the matrix you just have to think about which bits of the
input influence which bit of the output:
a b c d Examples
p 1 1 0 1 <-- p = (a+b+d) % 2 = (1·a + 1·b + 0·c + 1·d) % 2
q 1 0 1 1
a 1 0 0 0
r 0 1 1 1
b 0 1 0 0 <-- b = b % 2 = (0·a + 1·b + 0·c + 0·d) % 2
c 0 0 1 0
d 0 0 0 1
Let G be the matrix constructed above. Then the encodings of "0110" and
"1010" read
G · "0110" = "1100110"
G · "1010" = "1011010"
--3--
The validation matrix V is
0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1
The calculations yield
V · "0100011" = "011" = 3 ⇒ fixed: "0110011"
V · "1111111" = "000" = 0
V · "0110010" = "111" = 7 ⇒ fixed: "0110011"
======