0
$\begingroup$

In one of the coding theory books I read the unique decoding radius for Reed Solomon codes is $\frac{1-\rho}{2}$. Precisely, if the relative distance be less than these amount so the receiver is able to reconstruct the noisy received code-word uniquely. While for bigger amount of relative distance there are other code-words that are closer to the received code-word instead of the original code-word.

How this bound is calculated?

$\endgroup$
0
$\begingroup$

Let the linear block code $C$ with the minimum distance of $d_{min}$ which this amount is either odd or even so for each integer $t$ we can define the below inequality: \begin{equation} 2t+1 \leq d_{min} \leq 2t+2 \end{equation} Suppose $W$ is all code-words in code $C$ except $V$ which is the original code-word along with the channel and $r$ is the received code-word. Therefore, the below inequality according to one of the famous Lemma is satisfied. \begin{equation} d(V,r)+d(r,W) \geq d(V,W) \end{equation} Since $V$, $W$ $\in$ $C$, \begin{equation} d(V,W) \geq d_{min} \geq 2t+1 \end{equation} Now, suppose the number of error between $V$ and $r$ is $l$ i.e. $d(V,r)=l$. So \begin{equation} d(r,w) \geq 2t+1-l \end{equation} If $l$ $\leq$ $t$ then \begin{equation} d(r,w) \geq t \end{equation}

In other words, if the number of errors between the transmitted and the received code-words be less than $t$ so the code-word $V$ is the closest code-word to $r$ than all other code-words in code $C$. i.e. \begin{equation} d(V,r) < \frac{d_{min}-1}{2} \end{equation}

We can generalize this bound for all linear block codes such as Reed Solomon codes. The $d_{min}$ for RS codes is $n-k+1$ so we can conclude: \begin{equation} d(V,r) < \frac{n-k+1-1}{2}=n\frac{1-\frac{k}{n}}{2} \end{equation} So \begin{equation} \delta < \frac{1-\rho}{2} \end{equation}

It is exactly the bound for the RS codes to obtain uniquely the original code-word.

$\endgroup$

Your Answer

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