# On the definition of Error-Correcting Codes

Definition 1. Let $$C\subseteq A^n$$ be a code over $$A$$ and let $$t\in \Bbb Z^+$$ be a positive integer. We say that the code $$C$$ is $$\boldsymbol t$$-error correcting if nearest neighbour decoding is able to correct at most $$t$$ errors, assuming that if a tie occurs in the decoding process, a decoding error is reported. That is, if whenever $$x \in C$$ and $$y\in A^n$$ such that $$\mathrm{d}(x,y)\leq t$$, then $$y$$ is decoded to $$x$$ using nearest neighbour decoding.

Now let us make an observation.

Remark. Recall that when there is no unique nearest codeword to $$x\in C$$, then nearest neighbour decoding fails. So, a code $$C\subseteq A^n$$ is $$t$$-error correcting if and only if whenever $$y\in A^n$$ is a word within distance $$t$$ of a codeword $$x\in C$$ (that is, $$\mathrm{d}(x,y)\leq t$$), then $$\mathrm{d}(x,y) < \mathrm{d}(z,y), \quad \text{for all } x\neq z \in C.$$

The Remark gives us a more abstract way to state the definition of $$t$$-error correcting without mentioning nearest neighbour decoding.

However, I stumbled on another statement of the definition (which I found on some lecture notes on the web):

Definition 2. The code $$C$$ is $$t$$-error correcting if there do not exist $$x,z \in C$$ such that $$x\neq z$$ and $$y\in A^n$$ such that $$\mathrm d(x, y)\leq t, \quad \mathrm d (z, y)\leq t.$$

My question is why the last definition is equivalent to the first one (given with the form of the remark).

Could you please give me a hand?

UPDATE: My attempt: Definition 1 tells us that $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x \implies d(x,y)

Definition 2 tells us that $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(d(z,y)\leq t \implies z=x).$$ Equivalently, $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t ).$$ Equivalently, $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t\geq d(x,y)).$$ So the Def2 $$\implies$$ Def 1. Is that correct? How about $$\Longleftarrow$$?

• The definitions are equivalent. I suggest spending more time on the matter. Feb 15 '21 at 23:13
• @YuvalFilmus Please check my edit :) Feb 16 '21 at 2:36
• As you can see, it’s only a small manipulation to go from one definition to the other. Feb 16 '21 at 5:29

Here is what the remark says:

A code $$C \subseteq A^n$$ is $$t$$-error-correcting if for all $$x \in C$$ and $$y \in A^n$$ such that $$d(x,y) \leq t$$, all $$z \in C$$ other than $$x$$ satisfy $$d(x,y) < d(z,y)$$.

When is a code not $$t$$-error-correcting according to this remark?

A code $$C \subseteq A^n$$ is not $$t$$-error-correcting if there exist $$x,z \in C$$ and $$y \in A^n$$ such that $$x \neq z$$ and $$d(z,y) \leq d(x,y) \leq t$$.

Given $$x,y,z$$, either $$d(z,y) \leq d(x,y)$$ or $$d(x,y) \leq d(z,y)$$, and so, since the other constraints on $$x,z$$ are symmetric in $$x,z$$, the above definition is equivalent to

A code $$C \subseteq A^n$$ is not $$t$$-error-correcting if there exist $$x,z \in C$$ and $$y \in A^n$$ such that $$x \neq z$$ and $$d(x,y),d(z,y) \leq t$$.

This is exactly Definition 2.

• Thanks for your simple and clear answer. So, in other words, given that $d(x,y),d(z,y) \leq t$, either $d(x,y)\leq d(z,y) \leq t$ or $d(z,y) \leq d(x,y) \leq t$, which tells us how to go from 2. to 1. Right? Feb 16 '21 at 18:47
• Right, that's the idea. Feb 16 '21 at 19:03
• Dr Filmus, many thanks. Feb 16 '21 at 19:44