2
$\begingroup$

Let us start with the following well-known definition:

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)<d(z,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$?

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

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Chris Feb 16 at 18:47
  • 1
    $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus Feb 16 at 19:03
  • $\begingroup$ Dr Filmus, many thanks. $\endgroup$ – Chris Feb 16 at 19:44

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.