Finding minimum weight codewords in a Code over F9.
$begingroup$
Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong.
Consider the finite field $F_9$, and x a solution to the equation $X^2+1=0$. Let C be the code with parity-check matrix
$h=begin{bmatrix}
1 & 0 & 1 & x & 1\
0 & 1 & 1 & 1 & x
end{bmatrix}$
Find two code words of minimum weight.
My attempt at a solution:
First, the code words shouldn't be zero. Any codeword $c=(c_1,c_2,c_3,c_4,c_5)$ will satisfy $ch=0$, that is
$$
c_1+c_3+xc_4+c_5=0,c_2+c_3+c_4+xc_5=0
$$
Solving for $c_1,c_2$ gives the basis
$$
a=(-1,-1,1,0,0),b=(-x,-1,0,1,0),c=(-1,-x,0,0,1)
$$
So the dimension is 3, is this right?
Now, the weights. The weight is the number of nonzero elements, so I see that $w(a)=w(b)=w(c)=3$. So are $a,b$ just the required code words? And how does $x$ come into play?
Thanks in advance for any replies...
finite-fields coding-theory
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
$endgroup$
add a comment |
$begingroup$
Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong.
Consider the finite field $F_9$, and x a solution to the equation $X^2+1=0$. Let C be the code with parity-check matrix
$h=begin{bmatrix}
1 & 0 & 1 & x & 1\
0 & 1 & 1 & 1 & x
end{bmatrix}$
Find two code words of minimum weight.
My attempt at a solution:
First, the code words shouldn't be zero. Any codeword $c=(c_1,c_2,c_3,c_4,c_5)$ will satisfy $ch=0$, that is
$$
c_1+c_3+xc_4+c_5=0,c_2+c_3+c_4+xc_5=0
$$
Solving for $c_1,c_2$ gives the basis
$$
a=(-1,-1,1,0,0),b=(-x,-1,0,1,0),c=(-1,-x,0,0,1)
$$
So the dimension is 3, is this right?
Now, the weights. The weight is the number of nonzero elements, so I see that $w(a)=w(b)=w(c)=3$. So are $a,b$ just the required code words? And how does $x$ come into play?
Thanks in advance for any replies...
finite-fields coding-theory
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
$endgroup$
2
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
1
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54
add a comment |
$begingroup$
Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong.
Consider the finite field $F_9$, and x a solution to the equation $X^2+1=0$. Let C be the code with parity-check matrix
$h=begin{bmatrix}
1 & 0 & 1 & x & 1\
0 & 1 & 1 & 1 & x
end{bmatrix}$
Find two code words of minimum weight.
My attempt at a solution:
First, the code words shouldn't be zero. Any codeword $c=(c_1,c_2,c_3,c_4,c_5)$ will satisfy $ch=0$, that is
$$
c_1+c_3+xc_4+c_5=0,c_2+c_3+c_4+xc_5=0
$$
Solving for $c_1,c_2$ gives the basis
$$
a=(-1,-1,1,0,0),b=(-x,-1,0,1,0),c=(-1,-x,0,0,1)
$$
So the dimension is 3, is this right?
Now, the weights. The weight is the number of nonzero elements, so I see that $w(a)=w(b)=w(c)=3$. So are $a,b$ just the required code words? And how does $x$ come into play?
Thanks in advance for any replies...
finite-fields coding-theory
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
$endgroup$
Hello everyone reading this. I seem to have a problem understanding weights in Coding Theory, and will attempt to provide a solution to a problem - please correct me where I am wrong.
Consider the finite field $F_9$, and x a solution to the equation $X^2+1=0$. Let C be the code with parity-check matrix
$h=begin{bmatrix}
1 & 0 & 1 & x & 1\
0 & 1 & 1 & 1 & x
end{bmatrix}$
Find two code words of minimum weight.
My attempt at a solution:
First, the code words shouldn't be zero. Any codeword $c=(c_1,c_2,c_3,c_4,c_5)$ will satisfy $ch=0$, that is
$$
c_1+c_3+xc_4+c_5=0,c_2+c_3+c_4+xc_5=0
$$
Solving for $c_1,c_2$ gives the basis
$$
a=(-1,-1,1,0,0),b=(-x,-1,0,1,0),c=(-1,-x,0,0,1)
$$
So the dimension is 3, is this right?
Now, the weights. The weight is the number of nonzero elements, so I see that $w(a)=w(b)=w(c)=3$. So are $a,b$ just the required code words? And how does $x$ come into play?
Thanks in advance for any replies...
finite-fields coding-theory
finite-fields coding-theory
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
asked Dec 11 '18 at 21:32
MelaniesWoesMelaniesWoes
351112
351112
2
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
1
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54
add a comment |
2
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
1
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54
2
2
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
1
1
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54
add a comment |
0
active
oldest
votes
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%2f3035855%2ffinding-minimum-weight-codewords-in-a-code-over-f9%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3035855%2ffinding-minimum-weight-codewords-in-a-code-over-f9%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
$begingroup$
Your basis is correct. You still need to somehow prove that there are no words of weight two. Because there are 729 words altogether, listing them all, while doable, is not the recommended way. Are you familiar with a result relating the existence of a word of weight two to the set of columns of the check matrix?
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 5:38
$begingroup$
Thanks for the answer. Yes I read about that somewhere but I thought I could figure it out by hand. Guess there is no easy alternative... Oh well.
$endgroup$
– MelaniesWoes
Dec 12 '18 at 9:50
$begingroup$
Also, do formulate this as a proper answer, I will accept it :)
$endgroup$
– MelaniesWoes
Dec 12 '18 at 10:11
1
$begingroup$
I think that way is easy! All you need to do is to check that no small set of columns of $H$ is linearly independent over $Bbb{F}_9$. In other words, calculate ten 2x2 determinants. Much simpler than generating a list of 729 vectors don¨t you think :-). I think I have done a similar calculation in the past so I will pass the offer. I don't want to give the impression that "getting paid twice for the same work" is ok. Go ahead and post the answer yourself!
$endgroup$
– Jyrki Lahtonen
Dec 12 '18 at 13:16
$begingroup$
Νο Ι won't. The prize belongs to you, whether you take it or not. Thanks!
$endgroup$
– MelaniesWoes
Dec 12 '18 at 13:54