0
$\begingroup$

Let's consider the following sentences about coding a message before transmitting it in a communication system (here you find the complete pdf)

enter image description here

enter image description here

First question: can you explain me these two definitions of perfect code? I do not understand what "bit patterns" mean (I think they are the received bits but I am not sure). And I do not understand what do they mean practically.

Now let's consider the Hamming Code (7,4): here the generator matrix G (such that C = B*G, by referring on the upper blocks scheme) is shown:

enter image description here

enter image description here

Second question: I do not understand these two sentences. The rows of G do not appear to be one bit distant from a codeword and the second sentence is completely obscure for me. Can you explain me them?

$\endgroup$

2 Answers 2

1
$\begingroup$

I give an explanation that avoids the pejorative comments of Engineer.

First question: can you explain me these two definitions of perfect code?

Those are not two definitions of perfect codes but rather a single somewhat poorly-phrased definition of a perfect code. It should read

A perfect (binary) $t$-error-correcting code of block length $n$ is a set $\mathcal C$ of binary vectors of length $n$ that enjoys both properties listed below:

  • Given any $\mathbf x$, one of the $2^n$ binary vectors of length $n$, there exists a codeword $\mathbf c \in \mathcal C$ such that $\mathbf x$ and $\mathbf c$ differ from each other in $t$ or fewer places, that is, every binary $n$-vector $\mathbf x$ is at (Hamming) distance $t$ or less from some (suitably chosen) codeword in $\mathcal C$.
  • Each binary $n$-vector $\mathbf x$ is at distance $t$ or less from one and only one codeword in $\mathcal C$.

It is important to bear in mind that both properties must hold in order for $\mathcal C$ to be called perfect.

This definition is best understood in terms of the notion of Hamming balls in binary spaces. A Hamming ball of radius $t$ and centered at $\mathbf y$ is the set of all binary vectors $\mathbf x$ that are at Hamming distance $t$ or less from the center $\mathbf y$ of the ball. Note that a Hamming ball contains $$\binom{n}{0}+\binom{n}{1}+ \cdots + \binom{n}{t}$$ binary vectors in it. So, the first property says that if $|\mathcal C| = M$, then every binary $n$-vector $\mathbf x$ lies in one (or more) of the $M$ Hamming balls that are centered at the codewords, while the second property says that the Hamming ball that contains $\mathbf x$ does not contain any codewords other than the codeword at the center of the ball. Thus, the $M$ Hamming balls centered at the codewords fill the entire binary $n$-space without any overlap, that is, each $\mathbf x$ belongs in exactly one of the disjoint $M$ Hamming balls of radius $t$, and so we have a perfect packing of disjoint Hamming balls into the binary $n$-space. This is something that is impossible in our more familiar Euclidean spaces: non-overlapping balls don't fill entire spaces and there are always points in the space that don't belong in any of the balls.

Second question: I do not understand these two sentences.

The first sentence uses the fact that the $[7,4]$ Hamming code is a $1$-error-correcting perfect code and since every binary vector $\mathbf x$ must belong to a Hamming ball of radius $1$ centered on a codeword, it must either be a codeword (the center of the ball) or be one of the $n$ binary vectors at distance $1$ from the codeword at the center. In binary $n$-space, a Hamming ball of radius $1$ has exactly $\binom{n}{0}+\binom{n}{1} = n+1$ binary vectors in it.

The second sentence points out an addendum to the unstated notion that if $\mathbf c$ is the transmitted codeword and if the channel makes at most one error (flips no more than one of the transmitted bits), then the maximum-likelihood decoding algorithm, which maps received vectors into the nearest codeword, will decode correctly. The received vector $\mathbf x$ is at distance $0$ (no flips) or distance $1$ (exactly one flip) from $\mathbf c$ and so is in the Hamming ball of radius $1$ centered ar $\mathbf c$. The addendum, which is stated more explicitly, is that if two errors have occurred, then the received $\mathbf x$ lies in a Hamming ball centered at some other codeword $\mathbf c^\prime$ and so will get decoded into $\mathbf c^\prime \neq \mathbf c$ by the maximum-likelihood decoding algorithm, resulting in decoding error. Left unsaid (since these are presumably not things that are dreamt of in the book author's philosophy) are the facts that decoding errors will also occur if the channel makes three, four, five, six, or seven errors.

$\endgroup$
4
  • $\begingroup$ Excuse me, another question. Why does a Hamming Ball contains that sum of binomial coefficients binary vectors? $\endgroup$
    – Kinka-Byo
    Commented Dec 8, 2019 at 6:03
  • $\begingroup$ Moreover, how can we realize a perfect code, if it is impossible in Euclidean Spaces? $\endgroup$
    – Kinka-Byo
    Commented Dec 8, 2019 at 6:11
  • $\begingroup$ $\binom{n}{i}$ is the number of binary $n$-vectors that differ from a given binary $n$-vector in exactly $i$ places, that is, are at Hamming distance $i$ from the given binary vector. We can, in very rare cases, manage to pack Hamming balls to cover the entire Hamming space which is different from Euclidean space and which allows such packings. They are different spaces because the distance function is different not to mention the field over which the spaces are defined. $\endgroup$ Commented Dec 8, 2019 at 22:07
  • $\begingroup$ Perfect, thank you very much $\endgroup$
    – Kinka-Byo
    Commented Dec 8, 2019 at 22:53
0
$\begingroup$

First question: The perfect code definition is just what you wrote down, it is just a definition. But don't let it fool you, a perfect code is not always a good code. For example, no coding at all is a "perfect code" for $t=0$, and actually the $(7, 4)$ Hamming code is a perfect code but not all that great.

A bit pattern is just a pattern of bits. For $n$ bits, there are $2^n$ possible bit patterns.

Second question: "The rows of $G$ do not appear to be one bit distant from a codeword..." That is not what it says! It says that each of the possible $2^7$ seven bit patterns are either a codeword or, at most, 1 bit away from being a codeword. It is subtle difference and can see how you're confused.

The second sentence is explaining the error correction capability. Since every length $7$ bit pattern is either a codeword or within one bit of a codeword, this code can detect and correct up to one bit error. But what if there is $2$ bit errors? Well, the first bit error is fine and can be detected and corrected, but the second bit error now puts the received $7$ bit pattern "closer" to a different codeword and there is an error! Look into "sphere packing" as a way to visualize this notion better, it is very helpful. Hope this helps!

$\endgroup$
1
  • $\begingroup$ Perfect, thank you very much $\endgroup$
    – Kinka-Byo
    Commented Nov 26, 2019 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.