1
$\begingroup$

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:

coding-128


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$?

$\endgroup$
4
  • 2
    $\begingroup$ The dimensions of $H$ are $(n-k)\times n$. So the number of columns should be $n=k+m$. Not $k$ as your final answer suggests. In general ($t>1$) it will be more difficult to judge the number of redundant bits needed to correct $t$ errors. It may turn out that the answer is known for $7$-dimensional codes, but I can only give bounds (e.g. what you would get using a BCH-code). $\endgroup$ Apr 17 '17 at 9:45
  • $\begingroup$ @JyrkiLahtonen Thanks. I will modify my answer. I think the problem for finding the matrix size for the general case of $t > 1$ is related to the lemma that "If $H$ is the parity check matrix of $C$, then the minimum Hamming distance of $C$ equals the minimum number of columns of $H$ that are linearly dependent." Is it right? By the way, a bound on the matrix size is also appreciated. $\endgroup$
    – hengxin
    Apr 17 '17 at 9:52
  • 1
    $\begingroup$ " what matrix size must be used?" Is that really the full text of the exercise? What are the error detection-correction capabilities desired? Is the code binary? There seems to be some missing data. BTW, the link does not work for me (what about a screenshot?) $\endgroup$
    – leonbloy
    Apr 17 '17 at 22:04
  • $\begingroup$ @leonbloy Yes, it is "what size matrix must be used" (I have reordered two words by mistake). The code is binary. This is implied by the text in the chapter. Thanks for pointing this out. I will update this post right now. $\endgroup$
    – hengxin
    Apr 18 '17 at 3:03
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. By the way, is this problem much harder for general $t$, the error-correcting capacity? $\endgroup$
    – hengxin
    Apr 18 '17 at 3:35
  • $\begingroup$ Yes, see BCH codes for example. $\endgroup$
    – leonbloy
    Apr 18 '17 at 4:57
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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