Is this coding exercise well thought? I have to create a code $\mathcal{C}$ of 5 words with length $n = 6$, with the alphabet $\mathbb{F}_{2} = \{0, 1\}$ that corrects $1$ mistake.
I am new to coding theory so I am having some troubles with this particular question...
If it corrects $1$ mistakes, that means that $d>2\cdot1$ (I believe this is a well-known result [I prove it at my courses]), where $d$ is the minimal distance of the code $\mathcal{C}$ defined as $d=d(\mathcal{C})=\min\{d(x,y)|x,y\in \mathcal{C},x\neq y\}$, and that distance in the definition is the Hamming distance defined as $d(x,y)=\#\{i|1\leq i\leq n,x_{i}\neq y_{i}\}$, being $x=(x_{1},x_{2},...,x_{n})$ and $y=(y_{1},y_{2},...,y_{n})$ elements in $\mathbb{F}_{q}^{n}$ (where $\mathbb{F}_{q}$ is the alphabet of the code, and $n$ denotes the length of the words).
So, in my particular case I want that the minimal distance of the code is greater than $2$, i.e., I want that there are no two different words in the code that have Hamming distance equal or lesser than $2$, i.e., no two words in the code that have more than $4$ coordinates equal to each other (as If they have four equal to each other, there would be $6-4=2$ different to each other, so the Hamming distance would be $2$, and if there are $5$ equal to each other, the Hamming distance would be $1$ which is not valid). So, I begin to construct the code, by taking the first word:
$$
 (1,1,1,1,1,1)\in\mathbb{F}_{2}^{6}
 $$
Then, I could take another one like:
$$
 (1,1,1,0,0,0)\in\mathbb{F}_{2}^{6}
 $$
which satisfies the previous conditions. So, taking this kind of words, and taking on account the conditions that must hold, I could keep going with this ''constructive algorithm'' until I have $5$ words. For example:
$$
 (1,0,0,1,0,0)\in\mathbb{F}_{2}^{6}
 $$
$$
 (0,1,0,1,1,0)\in\mathbb{F}_{2}^{6}
 $$
$$
 (0,0,0,0,0,0)\in\mathbb{F}_{2}^{6}
 $$
And this would conclude the exercise (by taking all this $5$ words listed above). I am not sure if this is a great argument and I would really appreciate if someone could give me some feedback on it... Thanks in advanced!
 A: Nice question, and a good start.
It is unclear whether your greedy algorithm will always work without backtracking, as pointed out in the comments.
To put the question in context, you need minimum distance $d\geq 3$ for a length $n=6$ code.
The Hamming code has parameters $[n,k,d]=[2^m-1,2^m-m-1,3]$ and it is linear. Take $m=3$ to obtain a $[7,4,3]$ code. Since it is linear half its codewords have $1$ in any single bit position. So take half of its codewords which have a 1 in the last position and drop the last coordinate. You get a code with 8 codewords, length 6 and minimum distance 3. This is called shortening a code. You can take a subset of this code to answer your question.
Edit:
Consider any binary $[n,k]$ linear code defined by a $k\times n$ generator matrix $G=[G_1|\cdots|G_n]$ via
$$
m^T G = c
$$
where the arithmetic is modulo 2. Fix the last codeword bit, say $c_n.$ Also assume that the generator matrix is nontrivial, i.e., all its columns are nonzero. We then have
$$
(c_1,\ldots,c_n) = (m^T G_1,m^T G_2,\cdots,m^T G_n),
$$
thus $c_n=m^T g_n.$ Let the column $G_n=(g_1,\ldots,g_k),$ and $m=(m_1,\ldots,m_k)$ and note that this means
$$
c_n=m_1 g_1+m_2 g_2+ \cdots+ m_k g_k.
$$
Assume without loss of generality that the first coordinate $g_1\neq 0.$ Let the expression
$$
c'=m_2 g_2+\cdots+m_k g_k
$$
take on the value $0$ exactly $f$ times and the value $1$ exactly
$2^{k-1}-f$ times as the vector $(m_2,\ldots,m_k)$ ranges over $\mathbb{F}_2^{k-1}$ and let the subset of $\mathbb{F}_2^{k-1}$ where $c'$ takes on the value $0$ be denoted $X_0.$
Since $g_1\neq 0,$ then $g_1=1.$ This means that the last bit
$$
c_n=c'+m_1
$$
takes on the values $0$ and $1$ equally many times ($f$ times each) when $(m_2,\ldots,m_k)\in X_0.$ Also $c_n$ takes on the values $0$ and $1$ equally many times ($2^{k-1}-f$ times) when $(m_2,\ldots,m_k) \in \mathbb{F}_2^{k-1} \setminus X_0.$
So $c_n$ takes on the values $0$ and $1$ exactly $2^{k-1}$ times each.
A: We can try a linear code. But then we would have $2^k$ codewords. Then, let's try to find one with $k=3$. If we succeed, we'll have a codebook with $8$ codewords, which is more than we need (we'll remove 3 of them and we'll be done).
The parity check matrix $H$ must have dimensions $(n-k) \times n = 3 \times 6$. Let's build it so it has $d_{min} \ge 3$. Recall that the minimal distance equals the minimum number of columns of $H$ that are LD. Then, to attain  $d_{min} \ge 3$ it suffices to have $H$ with different columns (and not zero).
Then, it's possible, for example (let's make it systematic).
$$H=\begin{pmatrix}
1 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 0 & 1 & 1 \\
\end{pmatrix} = (I | P)$$
(BTW: this is how we design Hamming codes).
What remains is to write $G=(P^t | I)$, write down the $2^3$ codewords and pick five of them.
