How flexibible can one choose the properties of algebraic-geometric codes?
$begingroup$
Theorem 7.3 on page 67 in these lecture notes states the following.
For every even power of a prime $q$, and every parameter $delta < 1 - 1/(sqrt{q} - 1)$, there exists an infinite family of $q$-ary linear codes of relative distane $delta$ and rate $R geq 1- delta - 1/(sqrt{q} - 1)$. Further a generator matrix for such a code can be construted in $tilde{mathcal{O}}(n^3)$ time, where $n$ is the length of the code.
While this is really nice in asymptotic contexts, I wonder how flexible one can choose the concrete parameters of these algebraic geometric codes. For example: Could one choose
$q = 64, delta = 0.19$ and $k = 2$ to have an $[3, 2, 1]_64$ code? Or phrased more generally: Which constraints are there on the choice of these parameters?
I tried reading the paper the theorem above is based on, but I am to unacquainted to algebraic geometry to answer the question myself.
algebraic-geometry asymptotics coding-theory
asked Dec 28 '18 at 19:07
DaveDave
1237
$endgroup$
add a comment |
$begingroup$
Theorem 7.3 on page 67 in these lecture notes states the following.
For every even power of a prime $q$, and every parameter $delta < 1 - 1/(sqrt{q} - 1)$, there exists an infinite family of $q$-ary linear codes of relative distane $delta$ and rate $R geq 1- delta - 1/(sqrt{q} - 1)$. Further a generator matrix for such a code can be construted in $tilde{mathcal{O}}(n^3)$ time, where $n$ is the length of the code.
While this is really nice in asymptotic contexts, I wonder how flexible one can choose the concrete parameters of these algebraic geometric codes. For example: Could one choose
$q = 64, delta = 0.19$ and $k = 2$ to have an $[3, 2, 1]_64$ code? Or phrased more generally: Which constraints are there on the choice of these parameters?
I tried reading the paper the theorem above is based on, but I am to unacquainted to algebraic geometry to answer the question myself.
algebraic-geometry asymptotics coding-theory
asked Dec 28 '18 at 19:07
DaveDave
1237
$endgroup$
1
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42
add a comment |
$begingroup$
Theorem 7.3 on page 67 in these lecture notes states the following.
For every even power of a prime $q$, and every parameter $delta < 1 - 1/(sqrt{q} - 1)$, there exists an infinite family of $q$-ary linear codes of relative distane $delta$ and rate $R geq 1- delta - 1/(sqrt{q} - 1)$. Further a generator matrix for such a code can be construted in $tilde{mathcal{O}}(n^3)$ time, where $n$ is the length of the code.
While this is really nice in asymptotic contexts, I wonder how flexible one can choose the concrete parameters of these algebraic geometric codes. For example: Could one choose
$q = 64, delta = 0.19$ and $k = 2$ to have an $[3, 2, 1]_64$ code? Or phrased more generally: Which constraints are there on the choice of these parameters?
I tried reading the paper the theorem above is based on, but I am to unacquainted to algebraic geometry to answer the question myself.
algebraic-geometry asymptotics coding-theory
asked Dec 28 '18 at 19:07
DaveDave
1237
$endgroup$
Theorem 7.3 on page 67 in these lecture notes states the following.
For every even power of a prime $q$, and every parameter $delta < 1 - 1/(sqrt{q} - 1)$, there exists an infinite family of $q$-ary linear codes of relative distane $delta$ and rate $R geq 1- delta - 1/(sqrt{q} - 1)$. Further a generator matrix for such a code can be construted in $tilde{mathcal{O}}(n^3)$ time, where $n$ is the length of the code.
While this is really nice in asymptotic contexts, I wonder how flexible one can choose the concrete parameters of these algebraic geometric codes. For example: Could one choose
$q = 64, delta = 0.19$ and $k = 2$ to have an $[3, 2, 1]_64$ code? Or phrased more generally: Which constraints are there on the choice of these parameters?
I tried reading the paper the theorem above is based on, but I am to unacquainted to algebraic geometry to answer the question myself.
algebraic-geometry asymptotics coding-theory
algebraic-geometry asymptotics coding-theory
asked Dec 28 '18 at 19:07
DaveDave
1237
asked Dec 28 '18 at 19:07
DaveDave
1237
asked Dec 28 '18 at 19:07
DaveDave
1237
asked Dec 28 '18 at 19:07
DaveDave
1237
asked Dec 28 '18 at 19:07
DaveDave
1237
1237
1
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42
add a comment |
1
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42
1
1
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There is no single theorem that says what parameters are possible.
If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.
In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
$endgroup$
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
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%2f3055201%2fhow-flexibible-can-one-choose-the-properties-of-algebraic-geometric-codes%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$
There is no single theorem that says what parameters are possible.
If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.
In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
$endgroup$
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
add a comment |
$begingroup$
There is no single theorem that says what parameters are possible.
If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.
In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
$endgroup$
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
add a comment |
$begingroup$
There is no single theorem that says what parameters are possible.
If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.
In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
$endgroup$
There is no single theorem that says what parameters are possible.
If you Ctrl-F (or whatever equivalent) your document for “bound”, you will find several famous constrains on the relationship between code length, alphabet size and distance. That is what you are looking for, essentially.
In coding theory, you will encounter many families of codes, all of which have different properties and performance. All you can do is check their parameters. I don’t think it’s feasible to exhaustively search for combinations of parameters.
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
answered Dec 28 '18 at 19:21
rschwiebrschwieb
107k12102250
107k12102250
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
add a comment |
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
Thank you for your quick response. I already know about the several bounds. What I wonder about much more is the granularity in the concrete case. Meaning if it is possible to construct codes for all $n$ in the bounds or if there for example has to exist a set with certain properties which does not always exist.
$endgroup$
– Dave
Dec 28 '18 at 20:07
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
$begingroup$
@Dave Like I said: There is no single theorem that says what parameters are possible. Sometimes a given bound will introduce an example to show the maximum can be attained, but I have never heard of one providing examples for all combinations of parameters below the bound. I don't think its feasible.
$endgroup$
– rschwieb
Dec 28 '18 at 20:49
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%2f3055201%2fhow-flexibible-can-one-choose-the-properties-of-algebraic-geometric-codes%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
1
$begingroup$
Those results (at least most of them) are asymptotic in nature. To realize a fixed pair of parameters $(R,delta)$ may require quite long codes. I'm afraid I'm not up to speed with what exactly is possible. I would look up Garcia-Stichtenoth curves (or a tower of curves/function field extensions) to get a more precise idea about explicit parameter sets. I'm not sure whether the original Tsfasman-Vladuts-Zink results were based on explicit curves or simply on some existence results. I would need to check a few sources to say anything precise.
$endgroup$
– Jyrki Lahtonen
Dec 30 '18 at 20:03
$begingroup$
@JyrkiLahtonen Thank you for your comment. Something like this was what I was looking for. Concerning the explicitness, I think it was the way that Garcia and Strichtenloh were the first to provide an polynomial time construction. However, the polynomial was something like $n^30$. Then the paper I linked above was the first to come up with a construction in time $tilde{mathcal{O}}(n^3)$.
$endgroup$
– Dave
Dec 30 '18 at 21:42