Hamming[7,4] ECC
Hamming[7,4] ECC is single error correct and double error detect. It can detect some cases of more bits in error.
Using code developed directly from the Brilliant description with one minor modification -- the addition of a overall odd parity bit (so that the overall one bit count is odd) at the right hand end, generated the following codeword which has 4 bits of data, 3 bits of error check code and the odd parity bit. By the way, the code written from the Brilliant description behaves identically to the code that I wrote from the algorithm that I learned at Bell Laboratories in the 1980s.
Using a different data payload than the Brilliant description uses, I copied an 8-bit ECC and parity protected value.
Unfortunately, one of the bits is in error. This falls into the single error correct case. The problem is which bit is in error.
Encode your answer as 0, no actual error at all, 1 to 8 numbering the bits from left to right, and 8 if it is the odd parity bit itself that is in error. To get you started, there is an even number of one bits, therefore the odd parity bit is wrong.
The answer is 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
(* This is Wolfram Mathematica 11.3.0 code *)
d = 4
ecc = 3
t = d+ecc
logical = Function[a, ((# != 0) &)[a], Listable]
dot = Boole[Inner[And, logical[#1], logical[#2], Xor]] &
bitJoin = StringJoin[Table[ToString[b], {b, #}]] &
map = ConstantArray[0, t + 1];
Do[map[[2^i]] = -2^i, {i, 0, [LeftFloor]N[Log[2, t]][RightFloor]}];
Do[map[[dataBits[[i]]]] = i, {i, d}];
map = Table[If[b < 0, d + 1 + Log[2, -b], b], {b, map}];
map = Table[ToString[i], {i, map}];
map = Take[map, t];
PrependTo[map, "None"] (* {"None", "5", "6", "1", "7", "2", "3", "4"} *)
dataBits = Take[Flatten[Position[map, 0]], d] (* {3, 5, 6, 7} *)
m = ConstantArray[1, {ecc, d}] (* fill with 1s *)
Do[m[[i, (ecc + 1) - i]] = 0, {i, ecc}] (* enter the 0s *)
m = Join[m, IdentityMatrix[ecc], 2] (*assemble the complete m matrix *)
g = Join[IdentityMatrix[d], Take[m, All, d][Transpose], 2] (* Generate the g matrix *)
v = {1, 1, 0, 1, 0, 0, 0, 1}
data = Take[v, d];
code = Take[v, {d + 1, d + ecc}];
parityCheck = logical[Mod[Total[v] + 1, 2]];
check = Take[dot[{data}, g][[1]], -ecc];
syndrome = Table[Boole[logical[code[[i]]] [Xor] logical[check[[i]]]], {i,Length[check]}];
{parityCheck, bitJoin[syndrome], map[[FromDigits[Reverse[syndrome], 2] + 1]]} (* {True, "100", "5"} *)