Prove that the Hamming distances between three n-tuples cannot be 6,2,7
up vote
0
down vote
favorite
Let $x,y,z in {0,1}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y.
Prove
$d_H(x,y) = 6$,
$d_H(y,z) = 2$,
$d_H(x,z) = 7$
cannot happen.
discrete-mathematics finite-fields coding-theory binary
add a comment |
up vote
0
down vote
favorite
Let $x,y,z in {0,1}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y.
Prove
$d_H(x,y) = 6$,
$d_H(y,z) = 2$,
$d_H(x,z) = 7$
cannot happen.
discrete-mathematics finite-fields coding-theory binary
2
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
2
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $x,y,z in {0,1}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y.
Prove
$d_H(x,y) = 6$,
$d_H(y,z) = 2$,
$d_H(x,z) = 7$
cannot happen.
discrete-mathematics finite-fields coding-theory binary
Let $x,y,z in {0,1}^n$, and let $d_H(x,y)$ be the Hamming distance between codes x and y.
Prove
$d_H(x,y) = 6$,
$d_H(y,z) = 2$,
$d_H(x,z) = 7$
cannot happen.
discrete-mathematics finite-fields coding-theory binary
discrete-mathematics finite-fields coding-theory binary
edited Nov 18 at 20:06
leonbloy
39.8k645106
39.8k645106
asked Nov 17 at 12:37
Mark
63
63
2
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
2
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06
add a comment |
2
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
2
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06
2
2
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
2
2
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06
add a comment |
3 Answers
3
active
oldest
votes
up vote
-1
down vote
accepted
Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same.
So suppose then again without loss of generality you have the following for x and z
x:0000000hhhhh...,
z:1111111hhhhh...
Where h is everywhere 0 or 1 (it must be the same value in x and z).
First let $n geq 9$.
The distance between z and y is 2, so you have 3 cases in total to check.
First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.
Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)geq 7$, a contradiction.
Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n geq9$, d(x,y) $geq 7$, contradiction again.
For $n=7,8$ you can reason in a similar manner.
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
add a comment |
up vote
3
down vote
Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).
Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$
Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general
$$d(x,z)=d(x,y)+d(y,z)-2 k$$
for some integer $k$.
Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.
Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.
BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.
BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.
BTW 3: Welcome to MSE
add a comment |
up vote
-1
down vote
Welcome to MSE! I've looked into the triangular inequality: $d(x,z)leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6geq 7$, $2+7geq 6$, $6+7geq 2$.
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
-1
down vote
accepted
Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same.
So suppose then again without loss of generality you have the following for x and z
x:0000000hhhhh...,
z:1111111hhhhh...
Where h is everywhere 0 or 1 (it must be the same value in x and z).
First let $n geq 9$.
The distance between z and y is 2, so you have 3 cases in total to check.
First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.
Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)geq 7$, a contradiction.
Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n geq9$, d(x,y) $geq 7$, contradiction again.
For $n=7,8$ you can reason in a similar manner.
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
add a comment |
up vote
-1
down vote
accepted
Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same.
So suppose then again without loss of generality you have the following for x and z
x:0000000hhhhh...,
z:1111111hhhhh...
Where h is everywhere 0 or 1 (it must be the same value in x and z).
First let $n geq 9$.
The distance between z and y is 2, so you have 3 cases in total to check.
First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.
Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)geq 7$, a contradiction.
Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n geq9$, d(x,y) $geq 7$, contradiction again.
For $n=7,8$ you can reason in a similar manner.
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
add a comment |
up vote
-1
down vote
accepted
up vote
-1
down vote
accepted
Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same.
So suppose then again without loss of generality you have the following for x and z
x:0000000hhhhh...,
z:1111111hhhhh...
Where h is everywhere 0 or 1 (it must be the same value in x and z).
First let $n geq 9$.
The distance between z and y is 2, so you have 3 cases in total to check.
First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.
Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)geq 7$, a contradiction.
Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n geq9$, d(x,y) $geq 7$, contradiction again.
For $n=7,8$ you can reason in a similar manner.
Without loss of generality, suppose that you reorder the bits of x and z such that the first 7 bits of x are different to the first 7 bits of z, as their hamming distance is 7, while the rest of the bits must be the same.
So suppose then again without loss of generality you have the following for x and z
x:0000000hhhhh...,
z:1111111hhhhh...
Where h is everywhere 0 or 1 (it must be the same value in x and z).
First let $n geq 9$.
The distance between z and y is 2, so you have 3 cases in total to check.
First case, y agrees with z in the first 7 bits. But this contradicts d(x,y)=6, so you have a contradiction.
Second case, without loss of generality, y agrees with z on the first 6 bits, but not on the seventh, which must be 0. But then in one of the remaining bit of y in which z has value h (note that by construction also x has value h), y must take value 1 - h. But then again $ d(x,y)geq 7$, a contradiction.
Third and last case, without loss of generality, y agrees with z on the first 5 bits and the sixth and the seventh bits must be both 0. However all the rest of the bits of y must agree with z and, by construction, with x too. Since $n geq9$, d(x,y) $geq 7$, contradiction again.
For $n=7,8$ you can reason in a similar manner.
edited Nov 17 at 22:12
answered Nov 17 at 22:06
Marco Bellocchi
4781412
4781412
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
add a comment |
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
Besides not being a generic solution, and not very elegant I have to admit, as the one propsed by leonbloy, I think it does prove it, I do not see any particular issue. Why downvoted?
– Marco Bellocchi
Nov 19 at 20:40
add a comment |
up vote
3
down vote
Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).
Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$
Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general
$$d(x,z)=d(x,y)+d(y,z)-2 k$$
for some integer $k$.
Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.
Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.
BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.
BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.
BTW 3: Welcome to MSE
add a comment |
up vote
3
down vote
Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).
Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$
Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general
$$d(x,z)=d(x,y)+d(y,z)-2 k$$
for some integer $k$.
Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.
Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.
BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.
BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.
BTW 3: Welcome to MSE
add a comment |
up vote
3
down vote
up vote
3
down vote
Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).
Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$
Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general
$$d(x,z)=d(x,y)+d(y,z)-2 k$$
for some integer $k$.
Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.
Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.
BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.
BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.
BTW 3: Welcome to MSE
Notice that $d(x,y)=w(x+y)$ where the sum is modulo $2$, and $w$ is the weight function (it counts the number of ones).
Then $d(x,z) = w(x+z) = w(x+ y + y+ z) = w(a +b)$ where $a=x+y$ and $b=y+z$
Now $w(a+b) = w(a)+ w(b) - 2 w(c)$ where $c=a.b$ is the pointwise product (or bitwise AND function - or the number of ones in common). Then, in general
$$d(x,z)=d(x,y)+d(y,z)-2 k$$
for some integer $k$.
Or, equivalently, $d(x,z)+d(x,y)+d(y,z)$ is even.
Hence, it can never happen that, of the three mutual distance, two distances are even and one is odd. Either we have three even distances, or two odd and one even.
BTW 1: This problem has nothing to do with Hamming (or linear) codes, the statement refers to arbitrary binary tuples.
BTW 2: Next time you ask a question, please try to add some of your thoughts or what have you tried, to show us that you are not simply looking for someone else to do your homework. That's not what this website is for. And if the people here suspect you are doing that, they might downvote, close or refuse to answer your questions.
BTW 3: Welcome to MSE
edited Nov 19 at 12:43
answered Nov 18 at 1:16
leonbloy
39.8k645106
39.8k645106
add a comment |
add a comment |
up vote
-1
down vote
Welcome to MSE! I've looked into the triangular inequality: $d(x,z)leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6geq 7$, $2+7geq 6$, $6+7geq 2$.
add a comment |
up vote
-1
down vote
Welcome to MSE! I've looked into the triangular inequality: $d(x,z)leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6geq 7$, $2+7geq 6$, $6+7geq 2$.
add a comment |
up vote
-1
down vote
up vote
-1
down vote
Welcome to MSE! I've looked into the triangular inequality: $d(x,z)leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6geq 7$, $2+7geq 6$, $6+7geq 2$.
Welcome to MSE! I've looked into the triangular inequality: $d(x,z)leq d(x,y)+d(y,z)$. But it doesn't help here: $2+6geq 7$, $2+7geq 6$, $6+7geq 2$.
answered Nov 17 at 17:07
Wuestenfux
2,6621410
2,6621410
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%2f3002320%2fprove-that-the-hamming-distances-between-three-n-tuples-cannot-be-6-2-7%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
What have you tried?
– Parcly Taxel
Nov 17 at 13:25
2
Why do you speak of "Hamming codes" in the title? Bear in mind that Hamming codes are one thing and Hamming distance is another
– leonbloy
Nov 18 at 1:06