I'm reading David R. Finston and Patrick J. Morandi's book Abstract Algebra: Structure and Application and hit a proof that I have doubts.
First there are some definitions such as: Elements of $Z_2^n$ are called words. A linear code of length $n$ is a nonempty subset of $Z_2^n$ that is closed under the addition in $Z_2^n$. We refert to elements of a code as codewords. The weight of a word $w=a_1…a_n$ of length $n$ is the number of digits of $w$ equal to $1$, denoted $wt(w):=\sum_{i=1}^n a_i$. If $v$, $w$ are words, the distance between $v$ and $w$ is $D(v,w):=wt(v+w)$.
Then it defines the $t$-error correcting code and distance of a code:
Definition 2.4. Let $C$ be a code and let $t$ be a positive integer.
Then $C$ is a $t$-error correcting code if whenever a word $w$ differs
from the nearest codeword $v$ by a distance of at most $t$, then $v$
is the unique closest codeword to $w$.Definition 2.7. The distance $d$ of a code is defined by
$d:= \min \{ D(u,v):u,v\in C,u\ne v \}$
Then it states:
Proposition 2.8. Let $C$ be a code of distance d and set
$t=\lfloor(d-1)/2)\rfloor$. Then $C$ is a $t$-error correcting code
but not a $(t+1)$-error correcting code.
I'm fine with the first part that $C$ is a $t$-error correcting code. However, when it comes to the second part, i.e. $C$ is not a $(t+1)$-error correcting code, I found it a bit subtle.
Anyway, the proof goes:
To finish the proof, we need to prove that $C$ does not correct $t+1$
errors. Since the code has distance $d$, there are codewords $u_1$,
$u_2$ with $d=D(u_1, u_2)$; in other words, $u_1$ and $u_2$ differ in
exactly $d$ positions. Let $w$ be the word obtained from $u_1$ by
changing exactly $t+1$ of those $d$ positions. Then $D(u_1, w) = t+1$
and $D(u_2,w)=d-(t+1)$.
Since $t=\lfloor(d-1)/2\rfloor$ by our
assumption, $(d-2)/2\le t\le (d-1)/2$. In particular, $d-2\le 2t$ so
that $D(u_2,w)=d-(t+1)\le t+1$. Thus $u_1$ is not the unique closest
codeword to $w$, since $u_2$ is either equally close or closer to $w$.
Therefore $C$ is not a $(t+1)$-error correcting code.
My doubt is: Is this proving the original statement?
The original statement to be proved is actually:
A Given $w$ and its nearest codeword $u_1$, $D(w,u_1)=t+1$, then there exist another codeword $u_2$, s.t. the distance between $w$ and $u_2$, denoted as $s:=D(w, u_2)$, has $s\le t+1$, i.e. either $u_2$ is nearer to $w$ than $u_1$, so that $u_1$ is not the nearest codeword; or, the same distance, so there is ambiguity.
But here, the logic goes as:
B Given $u_1$ and $u_2$, find a $w$ such that $w$ sort of sits on the bench with $u_1$ and $u_2$ on either ends, i.e. only changes bits from $u_1$ among those bits that $u_1$ and $u_2$ differ, then $u_2$ is nearer to $w$ than $u_1$ does.
The problem is, A and B are equivalent, only if given any $w$ and $u_1$, the $u_2$ exists.
But does it? does the bench of $u_1$ and $u_2$ exists?
The thing becomes even more tricky as a linear code is not necessarily $Z_2^n$ — by definition, A linear code of length $n$ is a nonempty subset of $Z_2^n$ that is closed under the addition in $Z_2^n$ — so code $C$ can be just a subgroup of $Z_2^n$ such that given $w$ and $u_1$, there is no such an $u_2$!
Where did I miss?
Best Answer
Your misunderstanding seems to be about basic logic, unless I, too, misunderstood. Or, perhaps more accurately, about reading what exactly that definition requires.
Rephrasing the definition of a $(t+1)$-error correcting code to read:
Observe the universal quantifier for all vectors....
To prove that a code is NOT $(t+1)$-error-correcting, we need to prove the negation of the definition. In other words, the claim to be proved is:
Or, in the quantifier language. The negation of the statement $$\forall w\in\Bbb{Z}_2^n: P(w)$$ is $$ \exists w\in\Bbb{Z}_2^n: \neg P(w). $$