0
$\begingroup$

Assuming the coded data is errorless and given generator polynomial coefficients. By what algorithm can I decode the data coded by matrix constructed by given generator polynomial?

$\endgroup$
2
  • $\begingroup$ Have you checked your course material? Or do you mean there should be a faster algorithm assuming the coded data is errorless? $\endgroup$
    – John L.
    Dec 18, 2018 at 20:20
  • $\begingroup$ main problem is that generator matrix is irreversible(as it is not square) so i am confused how to revert coded word to it's original meaning. "assuming the code is errorless" is by problem declaration, that i am trying to solve $\endgroup$ Dec 18, 2018 at 21:47

1 Answer 1

1
$\begingroup$

Let us start with generator matrix $G$, a matrix of $k$ rows and $n$ columns where $n\ge k$. Given any input row vector $s$ of $k$ characters, we can generate the codeword for $s$, a row vector of $n$ entries by $$w=sG$$ If given $s$, how can we get back $w$? Suppose we can find a matrix $G'$ of $n$ rows and $k$ columns such that $$GG'=I_k$$ where $I_k$ is the identity matrix of $k$, we will have $$s=sI_k=s(GG')=(sG)G'=wG'$$

So the question becomes how to find such matrix $G'$ from $G$. You should be able to find in your course material the procedure or technique to accomplish that. Note that $G'$ is not a square matrix. In general $G'$ is not unique, either.

Now suppose you are given a generator polynomial instead. You can form the generator matrix from the generator polynomial and proceed as above. There might be a shortcut procedure for generator polynomial because of its special form.

$\endgroup$
5
  • $\begingroup$ yeah, the main problem is dividing the codeword by generator matrix(that has no inverse) $\endgroup$ Dec 19, 2018 at 11:28
  • $\begingroup$ Do you mean the main problem is how to find the matrix $G'$? Note that $w$ is obtained by multiplying $w$, the coded word with $G'$. There is no "dividing" here. $\endgroup$
    – John L.
    Dec 19, 2018 at 14:17
  • $\begingroup$ I mean: multiplying with G' is "division" with G $\endgroup$ Dec 20, 2018 at 8:28
  • $\begingroup$ We can find $G'$ by an established method that involves no "dividing" by a matrix. Is dividing by a scalar needed? Yes. (In fact, dividing by a scalar can be done by multiplication by a scalar.) $\endgroup$
    – John L.
    Dec 20, 2018 at 10:33
  • $\begingroup$ You should be able to find in your course material the procedure or technique that finds $G'$. $\endgroup$
    – John L.
    Dec 20, 2018 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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