Matrix size for error-correcting linear code

Question

This is Exercise 21 of the textbook "Abstract Algebra: Theory and Applications" by Thomas W. Judson, 2016; Page 111. Chapter 8 "Algebraic Coding Theory" mainly deals with binary linear code with Hamming code as an example.

Exercise 8.21: If we are to use an error-correcting linear code $C$ to transmit the 128 ASCII characters, what size matrix must be used?

The screenshot is as follows:

---

My Attempt: I consider the parity check matrix $H_{(n-k) \times n} = [P_{(n-k)\times k}\mid I_{n-k}]$. Let $m = n - k$, the number of parity bits. First of all, the data bit is $k = \log_2 128 = 7$.

Let the error-correcting capability be $t = 1$. The minimum Hamming distance of the linear code $C$ is at least $3$. Therefore, the zero column and $e_i$'s columns are not in $P_{(n-k) \times k}$ (because $H$ contains no idential columns). Thus, we have $2^{m} - m - 1 \ge k$, which gives $m \ge 4$. That is, the matrix size is $4 \times 11$ (Note: not $4 \times 7$ as pointed out in the comment by @Jyrki Lahtonen).

---

Is the argument above correct?

Also, how to solve this problem for any parameter $t$, the error-correcting capability of $C$?

Answer 1

I assume that by "an error-correcting linear code", they meant a code capable of correcting one (bit) error (per coded symbol).

In that case your reasoning is on the right track (and it's the reasoning used to construct a Hamming code). We know $k=7$, the matrix $H$ will have up to $2^m-1=n$ columns. The smallest Hamming code in our case is then $(15,11)$ ($11$ bits of information plus $4$ of redundacy).

Because this give a code with higher $k$ than needed, we can trim the $11-7=4$ unused data bits, and we are left with a $(11,7)$ code ($7$ bits of information plus $4$ of redundacy).

(Equivalently, the Hamming construction gives the -sufficient- condition of $n\le 2^{n-k}-1$; it's easy to check that, for $k=7$, $n=11$ is the minimum number that fulfill the condition)

If we only need one error detection, a single parity bit is enough, so we have a $(8,7)$ code.

Answer 2

Answer my question: I realized that my argument in the post relies on the standard parity-check matrix $H$. I show another argument here and ask for reviews.

First, the information bit $k = \log_2 128 = 7$.
Let $r = (n-k)$.
The parity-check matrix $H_{(n-k) \times n}$ has $r$ rows. Therefore, $H$ has at most $2^{r} - 1$ columns (the zero column is excluded).
To achieve the an-error-correcting capability, the code should be able to correct all the possible $n = 7 + r$ one-bit errors, each corresponding to one column of $H$. Therefore, we have $$2^r - 1 \ge 7 + r.$$ That is, $r \ge 4$ and the size of $H$ is at least $4 \times 11$.