# Definition of Perfect Code

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

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:

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?

• A bit pattern of length $n$ is (here) just a vector consisting of $0$'s and $1$'s of length $n$. Nov 25, 2019 at 17:56

A bit pattern of length $$n$$ is (here) just a vector consisting of $$0$$'s and $$1$$'s of length $$n$$. These are the messages that are actually sent and can be disturbed.

A code of length $$n$$ is just a set of such vectors and each of them stands for a message: in the case of a linear code, as the Hamming example, you have a generator matrix $$G$$, and a message of length $$4$$ (so a 4 bit vector) that you multiply from the left by $$G$$ to get the code word. Because we have a $$4 \times 7$$ matrix in this special form, the result is a $$7$$ bit vector that has as its first 4 bits the message vector and the last $$3$$ bits are called the check bits or parity bits.

Now the Hamming code has $$16$$ code words, because we have $$2^4 = 16$$ messages to send. So not just the rows of the $$G$$ matrix, but also all its linear combinations. The transmission can flip bits randomly and the receiver receives some $$7$$ bit vector that might be a code word or not (he could have received one of $$2^7=128$$ vectors).

Now if you consider a code word and you flip exactly one bit, the resulting vector could be one of $$7$$ vectors (depending on which position the flip occurred) but the first part of being perfect (for $$t=1$$, as we have for Hamming) means that all codewords plus all 1-flips of codewords together exactly form all possible 7-bit receivable words, and the flip is uniquely reconstructible: no two code words are exactly 2 flips apart so that you can change a code word $$w_1$$ by 1 flip to $$w_1'$$ and be certain there is no other code word $$w_2$$ and another flip that changes it into $$w_1'$$. The so-called Hamming-weight (closed) balls of radius 1, are exactly a disjoint cover of the vectors of length $$7$$ of size $$2^7$$ and this is plausible as each such ball has $$1+7=8$$ vectors and $$16 \times 8 = 2^7$$.

So when we use a Hamming code we can correct exactly one error occurring, but only detect an error for 2 errors and we'd get a wwrong decode. With three errors we can transform one codeword in another one, which you can already see in the first 2 rows of $$G$$ (flip 1, 2 and 6, say).

Normally you'd have a check matrix $$H$$ for decoding of a linear code: if you multiply this matrix by a code word you get $$0$$ and if some error occurs you get some unit vector that tells you what position to correct (syndrome decoding).

• Thank you very much, very excellent answer. Nov 26, 2019 at 9:08
• A last question: why is it called perfect? it can correct only 1 bit error Nov 26, 2019 at 10:18
• @Kinka-Byo Because it can correct all 1 bit errors perfectly and without inefficiency. And "perfect" is just a property name. Because such codes are quite rare among all codes. Nov 26, 2019 at 10:20
• Perfect, thank you very much Nov 26, 2019 at 10:47