Constructing generator polynomial for a BCH code
How can I construct a generator polynomial for a BCH code $(7,3)$ code
over $GF(2^3)$ with designed distance $delta =5$.
Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where $m_i(x)$ are the minimal polynomials for $alpha^i$ where $alpha$ is the primitive element of $$GF(2^3)= GF(2)/(y^3+y+1).$$ Also, $alpha$ is the $7$-th root of unity and $m_1(x)=m_2(x)=m_4(x)$ and $m_3=m_5=m_6(x)$.
Note that the cyclotomic sets are $$C_0={0}, quad C_1= {1,2,4}, C_2= {3,5,6}.$$ Since the designed distance is $5$, I cant pick $delta-1=4$ distinct consecutive elements from $$alpha^a, alpha^{a+1}, cdots, alpha^{a+delta-2}$$ for any value of $a$ without having an element in the three cosets and that will make the degree of my polynomial to be $6$ or $7$ and I also want the weight of the generator to be at least $5$. The most natural choice would be $$1+x+x^2+x^3+x^4$$ but this can not work because it does not divide $x^7-1$. Also, it is not the lcm of any of the minimal polynomial. Please, How can i construct this generator polynomial. Any help will be appreciated.
abstract-algebra coding-theory
asked Nov 26 '18 at 7:33
Jaynot
487515
add a comment |
How can I construct a generator polynomial for a BCH code $(7,3)$ code
over $GF(2^3)$ with designed distance $delta =5$.
Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where $m_i(x)$ are the minimal polynomials for $alpha^i$ where $alpha$ is the primitive element of $$GF(2^3)= GF(2)/(y^3+y+1).$$ Also, $alpha$ is the $7$-th root of unity and $m_1(x)=m_2(x)=m_4(x)$ and $m_3=m_5=m_6(x)$.
Note that the cyclotomic sets are $$C_0={0}, quad C_1= {1,2,4}, C_2= {3,5,6}.$$ Since the designed distance is $5$, I cant pick $delta-1=4$ distinct consecutive elements from $$alpha^a, alpha^{a+1}, cdots, alpha^{a+delta-2}$$ for any value of $a$ without having an element in the three cosets and that will make the degree of my polynomial to be $6$ or $7$ and I also want the weight of the generator to be at least $5$. The most natural choice would be $$1+x+x^2+x^3+x^4$$ but this can not work because it does not divide $x^7-1$. Also, it is not the lcm of any of the minimal polynomial. Please, How can i construct this generator polynomial. Any help will be appreciated.
abstract-algebra coding-theory
asked Nov 26 '18 at 7:33
Jaynot
487515
2
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32
add a comment |
How can I construct a generator polynomial for a BCH code $(7,3)$ code
over $GF(2^3)$ with designed distance $delta =5$.
Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where $m_i(x)$ are the minimal polynomials for $alpha^i$ where $alpha$ is the primitive element of $$GF(2^3)= GF(2)/(y^3+y+1).$$ Also, $alpha$ is the $7$-th root of unity and $m_1(x)=m_2(x)=m_4(x)$ and $m_3=m_5=m_6(x)$.
Note that the cyclotomic sets are $$C_0={0}, quad C_1= {1,2,4}, C_2= {3,5,6}.$$ Since the designed distance is $5$, I cant pick $delta-1=4$ distinct consecutive elements from $$alpha^a, alpha^{a+1}, cdots, alpha^{a+delta-2}$$ for any value of $a$ without having an element in the three cosets and that will make the degree of my polynomial to be $6$ or $7$ and I also want the weight of the generator to be at least $5$. The most natural choice would be $$1+x+x^2+x^3+x^4$$ but this can not work because it does not divide $x^7-1$. Also, it is not the lcm of any of the minimal polynomial. Please, How can i construct this generator polynomial. Any help will be appreciated.
abstract-algebra coding-theory
asked Nov 26 '18 at 7:33
Jaynot
487515
How can I construct a generator polynomial for a BCH code $(7,3)$ code
over $GF(2^3)$ with designed distance $delta =5$.
Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where $m_i(x)$ are the minimal polynomials for $alpha^i$ where $alpha$ is the primitive element of $$GF(2^3)= GF(2)/(y^3+y+1).$$ Also, $alpha$ is the $7$-th root of unity and $m_1(x)=m_2(x)=m_4(x)$ and $m_3=m_5=m_6(x)$.
Note that the cyclotomic sets are $$C_0={0}, quad C_1= {1,2,4}, C_2= {3,5,6}.$$ Since the designed distance is $5$, I cant pick $delta-1=4$ distinct consecutive elements from $$alpha^a, alpha^{a+1}, cdots, alpha^{a+delta-2}$$ for any value of $a$ without having an element in the three cosets and that will make the degree of my polynomial to be $6$ or $7$ and I also want the weight of the generator to be at least $5$. The most natural choice would be $$1+x+x^2+x^3+x^4$$ but this can not work because it does not divide $x^7-1$. Also, it is not the lcm of any of the minimal polynomial. Please, How can i construct this generator polynomial. Any help will be appreciated.
abstract-algebra coding-theory
abstract-algebra coding-theory
asked Nov 26 '18 at 7:33
Jaynot
487515
asked Nov 26 '18 at 7:33
Jaynot
487515
asked Nov 26 '18 at 7:33
Jaynot
487515
asked Nov 26 '18 at 7:33
Jaynot
487515
asked Nov 26 '18 at 7:33
Jaynot
487515
487515
2
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32
add a comment |
2
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32
2
2
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32
add a comment |
1 Answer
1
active
oldest
votes
The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $mathbb{F}_8 := mathbb{F}_2/(x^3+x+1)$. Denote $alpha := [x]$, then $alpha^3=alpha+1$. Finding a primitive element of the field means find a generator of the multiplicative group $(mathbb{F}_8)^* := mathbb{F}_8$. Note that $vert (mathbb{F}_8)^* vert = 7$ and since every element $ 1 neq beta in (mathbb{F}_8)^*$ has a period that divide 7, each non trivial element of $(mathbb{F}_8)^*$ is primitive. In conclusion we can take $alpha$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set ${ 1,2,3,4 }$, which is also a complete defining set for a suitable polynomial $$g:=(x-alpha)cdot (x-alpha^2) cdot (x-alpha^3) cdot (x-alpha^4) in mathbb{F}_8[x]$$
Computing $g$ we obtain $g = x^4+(alpha+1)x^3+x^2+alpha x + alpha + 1$
Observe that this polynomial satisfies your request
answered Nov 26 '18 at 13:24
Bilo
1089
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%2f3013988%2fconstructing-generator-polynomial-for-a-bch-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
The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $mathbb{F}_8 := mathbb{F}_2/(x^3+x+1)$. Denote $alpha := [x]$, then $alpha^3=alpha+1$. Finding a primitive element of the field means find a generator of the multiplicative group $(mathbb{F}_8)^* := mathbb{F}_8$. Note that $vert (mathbb{F}_8)^* vert = 7$ and since every element $ 1 neq beta in (mathbb{F}_8)^*$ has a period that divide 7, each non trivial element of $(mathbb{F}_8)^*$ is primitive. In conclusion we can take $alpha$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set ${ 1,2,3,4 }$, which is also a complete defining set for a suitable polynomial $$g:=(x-alpha)cdot (x-alpha^2) cdot (x-alpha^3) cdot (x-alpha^4) in mathbb{F}_8[x]$$
Computing $g$ we obtain $g = x^4+(alpha+1)x^3+x^2+alpha x + alpha + 1$
Observe that this polynomial satisfies your request
answered Nov 26 '18 at 13:24
Bilo
1089
add a comment |
The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $mathbb{F}_8 := mathbb{F}_2/(x^3+x+1)$. Denote $alpha := [x]$, then $alpha^3=alpha+1$. Finding a primitive element of the field means find a generator of the multiplicative group $(mathbb{F}_8)^* := mathbb{F}_8$. Note that $vert (mathbb{F}_8)^* vert = 7$ and since every element $ 1 neq beta in (mathbb{F}_8)^*$ has a period that divide 7, each non trivial element of $(mathbb{F}_8)^*$ is primitive. In conclusion we can take $alpha$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set ${ 1,2,3,4 }$, which is also a complete defining set for a suitable polynomial $$g:=(x-alpha)cdot (x-alpha^2) cdot (x-alpha^3) cdot (x-alpha^4) in mathbb{F}_8[x]$$
Computing $g$ we obtain $g = x^4+(alpha+1)x^3+x^2+alpha x + alpha + 1$
Observe that this polynomial satisfies your request
answered Nov 26 '18 at 13:24
Bilo
1089
add a comment |
The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $mathbb{F}_8 := mathbb{F}_2/(x^3+x+1)$. Denote $alpha := [x]$, then $alpha^3=alpha+1$. Finding a primitive element of the field means find a generator of the multiplicative group $(mathbb{F}_8)^* := mathbb{F}_8$. Note that $vert (mathbb{F}_8)^* vert = 7$ and since every element $ 1 neq beta in (mathbb{F}_8)^*$ has a period that divide 7, each non trivial element of $(mathbb{F}_8)^*$ is primitive. In conclusion we can take $alpha$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set ${ 1,2,3,4 }$, which is also a complete defining set for a suitable polynomial $$g:=(x-alpha)cdot (x-alpha^2) cdot (x-alpha^3) cdot (x-alpha^4) in mathbb{F}_8[x]$$
Computing $g$ we obtain $g = x^4+(alpha+1)x^3+x^2+alpha x + alpha + 1$
Observe that this polynomial satisfies your request
answered Nov 26 '18 at 13:24
Bilo
1089
The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $mathbb{F}_8 := mathbb{F}_2/(x^3+x+1)$. Denote $alpha := [x]$, then $alpha^3=alpha+1$. Finding a primitive element of the field means find a generator of the multiplicative group $(mathbb{F}_8)^* := mathbb{F}_8$. Note that $vert (mathbb{F}_8)^* vert = 7$ and since every element $ 1 neq beta in (mathbb{F}_8)^*$ has a period that divide 7, each non trivial element of $(mathbb{F}_8)^*$ is primitive. In conclusion we can take $alpha$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set ${ 1,2,3,4 }$, which is also a complete defining set for a suitable polynomial $$g:=(x-alpha)cdot (x-alpha^2) cdot (x-alpha^3) cdot (x-alpha^4) in mathbb{F}_8[x]$$
Computing $g$ we obtain $g = x^4+(alpha+1)x^3+x^2+alpha x + alpha + 1$
Observe that this polynomial satisfies your request
answered Nov 26 '18 at 13:24
Bilo
1089
edited Nov 26 '18 at 13:37
answered Nov 26 '18 at 13:24
Bilo
1089
answered Nov 26 '18 at 13:24
Bilo
1089
answered Nov 26 '18 at 13:24
Bilo
1089
1089
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3013988%2fconstructing-generator-polynomial-for-a-bch-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
2
You need to work over the field $GF(8)$, not $GF(2)$.
– Wuestenfux
Nov 26 '18 at 7:51
@Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :)
– Jaynot
Nov 26 '18 at 8:32