Generator matrix for Reed-Solomon code
$begingroup$
Given $,f(t)=t^3+t+1,,$ let $,mathbb{F}_{2^3}=frac{mathbb{F}_2left[tright]}{langle f,rangle},$ be a finite field and $,xi=t,left(textrm{mod},fright).$ Let also $,mathcal{C},$ be a cyclic code where $,g(x)=left(x-xiright)left(x-xi^2right)left(x-xi^3right)left(x-xi^4right),$ is his generator polynomial.
Question: Find a generator matrix of $,mathcal{C},$ in the basis $,B=left{1,xi,xi^2right},$ of $,mathbb{F}_{2^3},$ as an $,mathbb{F}_{2}$- vector space.
The fisrt thing they ask is to prove that $,xi,$ is a $,7^{,th},$ primitive root of the unity (quite easy). Then, prove that the length of $,mathcal{C},$ is $,n=7$.
I found out that $,mathcal{C},$ is a Reed-Solomon code, a type of BCH code whose length is always $,n=q-1,$ over a finite field $,mathbb{F}_q,,$ so this question is also easy to answer.
However, I do not know how to proceed to find the generator matrix of $,mathcal{C}.$ I tried to expand the generator polynomial
$$g(x)=g_0+g_1x+dots+g_4x^4$$
and define the generator matrix as
$$G=begin{pmatrix}g_0&g_1&g_2&g_3&g_4 & 0 & 0\
0 & g_0&g_1&g_2&g_3&g_4 & 0\
0 & 0 & g_0&g_1&g_2&g_3&g_4end{pmatrix}$$
in the basis $,B=left{1,xi,xi^2right},$ but I guess I failed.
Somebody please, help me! Thanks in advance.
abstract-algebra finite-fields coding-theory
$endgroup$
|
show 6 more comments
$begingroup$
Given $,f(t)=t^3+t+1,,$ let $,mathbb{F}_{2^3}=frac{mathbb{F}_2left[tright]}{langle f,rangle},$ be a finite field and $,xi=t,left(textrm{mod},fright).$ Let also $,mathcal{C},$ be a cyclic code where $,g(x)=left(x-xiright)left(x-xi^2right)left(x-xi^3right)left(x-xi^4right),$ is his generator polynomial.
Question: Find a generator matrix of $,mathcal{C},$ in the basis $,B=left{1,xi,xi^2right},$ of $,mathbb{F}_{2^3},$ as an $,mathbb{F}_{2}$- vector space.
The fisrt thing they ask is to prove that $,xi,$ is a $,7^{,th},$ primitive root of the unity (quite easy). Then, prove that the length of $,mathcal{C},$ is $,n=7$.
I found out that $,mathcal{C},$ is a Reed-Solomon code, a type of BCH code whose length is always $,n=q-1,$ over a finite field $,mathbb{F}_q,,$ so this question is also easy to answer.
However, I do not know how to proceed to find the generator matrix of $,mathcal{C}.$ I tried to expand the generator polynomial
$$g(x)=g_0+g_1x+dots+g_4x^4$$
and define the generator matrix as
$$G=begin{pmatrix}g_0&g_1&g_2&g_3&g_4 & 0 & 0\
0 & g_0&g_1&g_2&g_3&g_4 & 0\
0 & 0 & g_0&g_1&g_2&g_3&g_4end{pmatrix}$$
in the basis $,B=left{1,xi,xi^2right},$ but I guess I failed.
Somebody please, help me! Thanks in advance.
abstract-algebra finite-fields coding-theory
$endgroup$
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
1
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30
|
show 6 more comments
$begingroup$
Given $,f(t)=t^3+t+1,,$ let $,mathbb{F}_{2^3}=frac{mathbb{F}_2left[tright]}{langle f,rangle},$ be a finite field and $,xi=t,left(textrm{mod},fright).$ Let also $,mathcal{C},$ be a cyclic code where $,g(x)=left(x-xiright)left(x-xi^2right)left(x-xi^3right)left(x-xi^4right),$ is his generator polynomial.
Question: Find a generator matrix of $,mathcal{C},$ in the basis $,B=left{1,xi,xi^2right},$ of $,mathbb{F}_{2^3},$ as an $,mathbb{F}_{2}$- vector space.
The fisrt thing they ask is to prove that $,xi,$ is a $,7^{,th},$ primitive root of the unity (quite easy). Then, prove that the length of $,mathcal{C},$ is $,n=7$.
I found out that $,mathcal{C},$ is a Reed-Solomon code, a type of BCH code whose length is always $,n=q-1,$ over a finite field $,mathbb{F}_q,,$ so this question is also easy to answer.
However, I do not know how to proceed to find the generator matrix of $,mathcal{C}.$ I tried to expand the generator polynomial
$$g(x)=g_0+g_1x+dots+g_4x^4$$
and define the generator matrix as
$$G=begin{pmatrix}g_0&g_1&g_2&g_3&g_4 & 0 & 0\
0 & g_0&g_1&g_2&g_3&g_4 & 0\
0 & 0 & g_0&g_1&g_2&g_3&g_4end{pmatrix}$$
in the basis $,B=left{1,xi,xi^2right},$ but I guess I failed.
Somebody please, help me! Thanks in advance.
abstract-algebra finite-fields coding-theory
$endgroup$
Given $,f(t)=t^3+t+1,,$ let $,mathbb{F}_{2^3}=frac{mathbb{F}_2left[tright]}{langle f,rangle},$ be a finite field and $,xi=t,left(textrm{mod},fright).$ Let also $,mathcal{C},$ be a cyclic code where $,g(x)=left(x-xiright)left(x-xi^2right)left(x-xi^3right)left(x-xi^4right),$ is his generator polynomial.
Question: Find a generator matrix of $,mathcal{C},$ in the basis $,B=left{1,xi,xi^2right},$ of $,mathbb{F}_{2^3},$ as an $,mathbb{F}_{2}$- vector space.
The fisrt thing they ask is to prove that $,xi,$ is a $,7^{,th},$ primitive root of the unity (quite easy). Then, prove that the length of $,mathcal{C},$ is $,n=7$.
I found out that $,mathcal{C},$ is a Reed-Solomon code, a type of BCH code whose length is always $,n=q-1,$ over a finite field $,mathbb{F}_q,,$ so this question is also easy to answer.
However, I do not know how to proceed to find the generator matrix of $,mathcal{C}.$ I tried to expand the generator polynomial
$$g(x)=g_0+g_1x+dots+g_4x^4$$
and define the generator matrix as
$$G=begin{pmatrix}g_0&g_1&g_2&g_3&g_4 & 0 & 0\
0 & g_0&g_1&g_2&g_3&g_4 & 0\
0 & 0 & g_0&g_1&g_2&g_3&g_4end{pmatrix}$$
in the basis $,B=left{1,xi,xi^2right},$ but I guess I failed.
Somebody please, help me! Thanks in advance.
abstract-algebra finite-fields coding-theory
abstract-algebra finite-fields coding-theory
edited Jan 19 at 12:16
CarlIO
asked Jan 11 at 11:01
CarlIOCarlIO
957
957
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
1
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30
|
show 6 more comments
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
1
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
1
1
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30
|
show 6 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Lots of comments. We have
$$g = (x-xi)(x-xi^2)(x-xi^3)(x-xi^4).$$
If $xi$ is a zero of the primitive polynomial $f=x^3+x+1$, then $f$ has the zeros $xi,xi^2,(xi^2)^2=xi^4$. Thus
$$g = (x^3+x+1)(x+xi^3) = x^4+x^2+x+xi^3x^3+xi^3 x +xi^3\
= x^4 + xi^3 x^3 +x^2+(xi^3+1)x+xi^3.$$
Since $xi$ is a zero of $f$, $xi^3+xi+1=0$ and so $xi=xi^3+1$
Hence,
$$g= = x^4 + xi^3 x^3 +x^2+xi x+xi^3.$$
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069717%2fgenerator-matrix-for-reed-solomon-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Lots of comments. We have
$$g = (x-xi)(x-xi^2)(x-xi^3)(x-xi^4).$$
If $xi$ is a zero of the primitive polynomial $f=x^3+x+1$, then $f$ has the zeros $xi,xi^2,(xi^2)^2=xi^4$. Thus
$$g = (x^3+x+1)(x+xi^3) = x^4+x^2+x+xi^3x^3+xi^3 x +xi^3\
= x^4 + xi^3 x^3 +x^2+(xi^3+1)x+xi^3.$$
Since $xi$ is a zero of $f$, $xi^3+xi+1=0$ and so $xi=xi^3+1$
Hence,
$$g= = x^4 + xi^3 x^3 +x^2+xi x+xi^3.$$
$endgroup$
add a comment |
$begingroup$
Lots of comments. We have
$$g = (x-xi)(x-xi^2)(x-xi^3)(x-xi^4).$$
If $xi$ is a zero of the primitive polynomial $f=x^3+x+1$, then $f$ has the zeros $xi,xi^2,(xi^2)^2=xi^4$. Thus
$$g = (x^3+x+1)(x+xi^3) = x^4+x^2+x+xi^3x^3+xi^3 x +xi^3\
= x^4 + xi^3 x^3 +x^2+(xi^3+1)x+xi^3.$$
Since $xi$ is a zero of $f$, $xi^3+xi+1=0$ and so $xi=xi^3+1$
Hence,
$$g= = x^4 + xi^3 x^3 +x^2+xi x+xi^3.$$
$endgroup$
add a comment |
$begingroup$
Lots of comments. We have
$$g = (x-xi)(x-xi^2)(x-xi^3)(x-xi^4).$$
If $xi$ is a zero of the primitive polynomial $f=x^3+x+1$, then $f$ has the zeros $xi,xi^2,(xi^2)^2=xi^4$. Thus
$$g = (x^3+x+1)(x+xi^3) = x^4+x^2+x+xi^3x^3+xi^3 x +xi^3\
= x^4 + xi^3 x^3 +x^2+(xi^3+1)x+xi^3.$$
Since $xi$ is a zero of $f$, $xi^3+xi+1=0$ and so $xi=xi^3+1$
Hence,
$$g= = x^4 + xi^3 x^3 +x^2+xi x+xi^3.$$
$endgroup$
Lots of comments. We have
$$g = (x-xi)(x-xi^2)(x-xi^3)(x-xi^4).$$
If $xi$ is a zero of the primitive polynomial $f=x^3+x+1$, then $f$ has the zeros $xi,xi^2,(xi^2)^2=xi^4$. Thus
$$g = (x^3+x+1)(x+xi^3) = x^4+x^2+x+xi^3x^3+xi^3 x +xi^3\
= x^4 + xi^3 x^3 +x^2+(xi^3+1)x+xi^3.$$
Since $xi$ is a zero of $f$, $xi^3+xi+1=0$ and so $xi=xi^3+1$
Hence,
$$g= = x^4 + xi^3 x^3 +x^2+xi x+xi^3.$$
answered Jan 13 at 8:43
WuestenfuxWuestenfux
4,5161413
4,5161413
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069717%2fgenerator-matrix-for-reed-solomon-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
No, its fine. You need to calculate the coefficients $g_i$.
$endgroup$
– Wuestenfux
Jan 11 at 11:31
$begingroup$
Basic Galois theory tells us that the zeros of $f(t)$ are $xi,xi^2$ and $xi^4$. So $$f(x)=x^3+x+1=(x-xi)(x-xi^2)(x-xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-xi^3).$$ Observe that $xi^3=xi+1$ because $xi$ is a zero of $f$.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 11:41
$begingroup$
@Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $xi$ over $mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - left(xi +1right)^3+x^2-xi x-left(xi+1right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how.
$endgroup$
– CarlIO
Jan 11 at 17:45
$begingroup$
Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $xi^3=xi+1$, no?
$endgroup$
– Jyrki Lahtonen
Jan 11 at 17:51
1
$begingroup$
Effectively you would then replace each entry of the $3times7$ matrix with a $3times3$ block.
$endgroup$
– Jyrki Lahtonen
Jan 11 at 18:30