1
$\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$
1
$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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