Why the dimension of bch code is unknown?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $delta$, and I asked for it dimension.
The output file ALWAYS ends with a $p^m+1$ code of dimension $1$ then there are no code of dimension less then $p+1$ so there are a "jump" of $p$. in fact the "jump" is ALWAYS a divisor of $m$ and there are a certain number of those. and things get nicer when $m$ is prime.
There is well behaved pattern here but I'm not too smart to tell a general formula. But I believe it can be done.
So my question is: Why the dimension of bch code still unknown?
coding-theory
asked Aug 25 at 1:54
TWJ
1
 |Â
show 1 more comment
up vote
0
down vote
favorite
My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $delta$, and I asked for it dimension.
The output file ALWAYS ends with a $p^m+1$ code of dimension $1$ then there are no code of dimension less then $p+1$ so there are a "jump" of $p$. in fact the "jump" is ALWAYS a divisor of $m$ and there are a certain number of those. and things get nicer when $m$ is prime.
There is well behaved pattern here but I'm not too smart to tell a general formula. But I believe it can be done.
So my question is: Why the dimension of bch code still unknown?
coding-theory
asked Aug 25 at 1:54
TWJ
1
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $delta$, and I asked for it dimension.
The output file ALWAYS ends with a $p^m+1$ code of dimension $1$ then there are no code of dimension less then $p+1$ so there are a "jump" of $p$. in fact the "jump" is ALWAYS a divisor of $m$ and there are a certain number of those. and things get nicer when $m$ is prime.
There is well behaved pattern here but I'm not too smart to tell a general formula. But I believe it can be done.
So my question is: Why the dimension of bch code still unknown?
coding-theory
asked Aug 25 at 1:54
TWJ
1
My professor told me that dimension of bch code is unknown in general, so I made a loop in SAGEMATH that create a BCH code of length $p^m-1$ over $GF(p)$ with every possible designed minimum distance $delta$, and I asked for it dimension.
The output file ALWAYS ends with a $p^m+1$ code of dimension $1$ then there are no code of dimension less then $p+1$ so there are a "jump" of $p$. in fact the "jump" is ALWAYS a divisor of $m$ and there are a certain number of those. and things get nicer when $m$ is prime.
There is well behaved pattern here but I'm not too smart to tell a general formula. But I believe it can be done.
So my question is: Why the dimension of bch code still unknown?
coding-theory
asked Aug 25 at 1:54
TWJ
1
asked Aug 25 at 1:54
TWJ
1
asked Aug 25 at 1:54
TWJ
1
asked Aug 25 at 1:54
TWJ
1
1
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44
 |Â
show 1 more comment
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
2
down vote
There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.
- Whenever you increase the designed distance of a BCH-code, you can't
immediately tell whether the code changes at all because the new
zeros of the generator polynomial may not come from the smallest
elements in their cyclotomic coset (in which case there will be no new zeros at all). - Also, even if you get a new cyclotomic coset, its size is not
immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).
The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
add a comment |Â
up vote
1
down vote
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.
There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.
There is a nice survey by Ruud Pelikaan here.
answered Aug 25 at 9:55
kodlu
2,891615
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.
- Whenever you increase the designed distance of a BCH-code, you can't
immediately tell whether the code changes at all because the new
zeros of the generator polynomial may not come from the smallest
elements in their cyclotomic coset (in which case there will be no new zeros at all). - Also, even if you get a new cyclotomic coset, its size is not
immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).
The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
add a comment |Â
up vote
2
down vote
There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.
- Whenever you increase the designed distance of a BCH-code, you can't
immediately tell whether the code changes at all because the new
zeros of the generator polynomial may not come from the smallest
elements in their cyclotomic coset (in which case there will be no new zeros at all). - Also, even if you get a new cyclotomic coset, its size is not
immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).
The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
add a comment |Â
up vote
2
down vote
up vote
2
down vote
There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.
- Whenever you increase the designed distance of a BCH-code, you can't
immediately tell whether the code changes at all because the new
zeros of the generator polynomial may not come from the smallest
elements in their cyclotomic coset (in which case there will be no new zeros at all). - Also, even if you get a new cyclotomic coset, its size is not
immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).
The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
There are two factors at play making it difficult to come up with a formula. Thinking about it in terms gradually incrementing the designed distance one by one.
- Whenever you increase the designed distance of a BCH-code, you can't
immediately tell whether the code changes at all because the new
zeros of the generator polynomial may not come from the smallest
elements in their cyclotomic coset (in which case there will be no new zeros at all). - Also, even if you get a new cyclotomic coset, its size is not
immediately clear, so you can't tell how much the dimension of the code will drop (in comparison to the previos code).
The solutions to both problems are easy and well understood in the sense that it is easy to write an algorithm checking, whether the new zero does introduce a new cyclotomic coset. It is equally easy to write an algorithm figuring out the size of that cyclotomic coset. What's difficult is to write the outcome of these algorithms in a useful closed formula (other than the obvious summation). What is even more difficult (an open problem in general!) is to figure out the actual minimum distance of a BCH-code (rather than its designed distance).
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
edited 2 days ago
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
answered Aug 28 at 5:31
Jyrki Lahtonen
105k12161358
105k12161358
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
add a comment |Â
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
Of course, many special cases are known, among them the "last code" you observed.
– Jyrki Lahtonen
Aug 28 at 5:33
add a comment |Â
up vote
1
down vote
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.
There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.
There is a nice survey by Ruud Pelikaan here.
answered Aug 25 at 9:55
kodlu
2,891615
add a comment |Â
up vote
1
down vote
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.
There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.
There is a nice survey by Ruud Pelikaan here.
answered Aug 25 at 9:55
kodlu
2,891615
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.
There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.
There is a nice survey by Ruud Pelikaan here.
answered Aug 25 at 9:55
kodlu
2,891615
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to polynomial factorisation over finite fields, and algebraic techniques only go so far.
There are the BCH, Roos, Hartmann-Tzeng bounds, the van Lint-Wilson shift method, but no general closed form formula exists.
There is a nice survey by Ruud Pelikaan here.
answered Aug 25 at 9:55
kodlu
2,891615
answered Aug 25 at 9:55
kodlu
2,891615
answered Aug 25 at 9:55
kodlu
2,891615
answered Aug 25 at 9:55
kodlu
2,891615
2,891615
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2893738%2fwhy-the-dimension-of-bch-code-is-unknown%23new-answer', 'question_page');
);
Post as a guest
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
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
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
This is a duplicate of a question in mathoverflow mathoverflow.net/questions/304032/… by the same author which was answered there.
– kodlu
Aug 25 at 9:52
short answer, it is combinatorial in nature so no closed form answer is likelly to exist, assuming this is what the poster is after.
– kodlu
Aug 25 at 9:53
it seems mo questions are not considerd duplicates.
– kodlu
Aug 25 at 9:55
i'm an under graduated student that why i repost my question here i was hoping for a simple straightforward answer.
– TWJ
Aug 27 at 1:19
Sorry there isn't a simpler answer than it is combinatorial and depends on divisibility of polynomials. Consider divisibility of integers. The specific question is unrelated but why are some primes close to squares and some not? This isn't straightforward either. Hope this helps.
– kodlu
Aug 27 at 4:44