2
$\begingroup$

I found this problem in here
(Problem 6 on page 6)

Consider the triple repeat code. What codewords are closest to $(1, 1, 0)$? Describe the set of vectors at distance $1$ or less from the codeword $(0, 0, 0)$. Do the same for the set of vectors at distance $1$ or less from the codeword $(1, 1, 1)$. What is the relation between these two sets? (We think of them as balls of radius one around the respective codewords.) What is the distance between the codewords $(0,0, 0)$ and $(1, 1, 1)$?

  • 1
    Megan, this is a small problem. As this is probably your first exercise in coding theory, you could simply list all the 8 binary vectors of length 3, and calculate their Hamming distances from the two codewords. Trust me, it won't take you too long, and gives you a feeling of how the Hamming distance works.2012-04-23

1 Answers 1

3

In triple repeat code, there are only two possible codewords: $c_0 = (0,0,0)$ and $c_1 = (1,1,1)$. So the closest codeword to $(1,1,0)$ is $c_1$ with Hamming distance $1$, and the next one is $c_0$ with Hamming distance $2$. To do the second part, imagine a unit cube, with the vertex in the origin named $c_0$ and the opposite vertex called $c_1$. In this setting the Hamming distance is the number of edges you must to use to go from one vertex to another. So using this intuition, the distance between $c_0$ and $c_1$ is 3, and balls of radius 1 (i.e. the set of vertices you can reach by using no more that 1 edge) with centers at $c_0$ and $c_1$ are disjoint! Try to draw it and see for yourself, you can slice the cube in two by plane $x+y+z = 3/2$.

Edit: Considering the comments, I think I should explain the plane at the end a bit more. In a setting where you are dealing with sequences of binary numbers, then the Hamming distance is equivalent to distance induced by the $\|\cdot\|_1$ norm on $n$-dimentional unit hypercube (observe that the coordinates of the vertices are tuples exactly of length $n$ with values being $0$ and $1$ only). In your case $n = 3$ so this is the ordinary 3D cube ;-)

  • 0
    Yup! A good point.2012-04-23