Prove this inequality about the weights of code words (Coding Theory)

[imDooiNGMATH]

Homework Statement

Prove $wt(x+y) \leq wt(x) + wt(y)$. where "wt(x)" is referring to the weight of a specific code word

Relevant Equations

$0 \leq wt(x)$, $0 \leq wt(y)$

I'm trying to prove the following:

$wt(x+y) \leq wt(x) + wt(y)$, where "wt(x)" is referring to the weight of a specific code word.

Proof:

For two code words $x, y \in F^{n}_2$, we have the inequalities $0 \leq wt(x)$ and $0 \leq wt(y)$. Adding these together, we have $0 \leq wt(x) + wt(y)$. From here, adding $wt(x+y)$ to both sides, we have $wt(x+y) \leq wt(x) + wt(y) + wt(x+y)$. From this, it is clear that $wt(x) + wt(y) \leq wt(x) + wt(y) + wt(x+y)$. Thus, $wt(x+y) \leq wt(x) + wt(y) \leq wt(x) + wt(y) + wt(x+y)$.

At first, I was thinking I should do cases where $x = y$ and $x \neq y$, but reading over it, this seems sufficient.

 

[Office_Shredder]

It's not obvious to me how the last two lines follow from the lines before them.

 

[imDooiNGMATH]

It's not obvious to me how the last two lines follow from the lines before them.

I've been thinking about this since I posted and I think what you pointed out is what's bothering me. With the cases idea, it's easier to make use of the digits in the words themselves to more directly make the point.

For example:
A case where $x = y$. If $x = y$, then $x + y = 0$, and as such $wt(x + y) = 0$. As $0 \leq wt(x)$ and $0 \leq wt(y)$, we have $0 \leq wt(x) + wt(y)$. And thus $wt(x+y) \leq wt(x) + wt(y)$.

Then I just need to make a similarly detailed argument for the case $x \neq y$. I second guessed this idea, but I think this is a more proper way to go about it because the above makes a leap in logic at the end. What do you think?

 

[Mark44]

For example:
A case where $x = y$. If $x = y$, then $x + y = 0$, and as such $wt(x + y) = 0$. As $0 \leq wt(x)$ and $0 \leq wt(y)$, we have $0 \leq wt(x) + wt(y)$. And thus $wt(x+y) \leq wt(x) + wt(y)$..

With your expression x + y, it looks like you are doing bitwise binary addition of 1-bit quantities. So with x = y, you have 0 + 0 = 1 and 1 + 1 = 0. Is that what's happening here? How is wt(x) being defined? Is it the number of nonzero bits in a word? For example, would wt(100110) be 3?

I don't see how you can do a proof without some idea of how wt() is defined.

 

[imDooiNGMATH]

With your expression x + y, it looks like you are doing bitwise binary addition of 1-bit quantities. So with x = y, you have 0 + 0 = 1 and 1 + 1 = 0. Is that what's happening here? How is wt(x) being defined? Is it the number of nonzero bits in a word? For example, would wt(100110) be 3?

I don't see how you can do a proof without some idea of how wt() is defined.

Yep! Everything you said is exactly how everything is defined.

Edit: Sorry, actually in this case 0+0 = 0, not 1.

 

[Mark44]

Everything you said is exactly how everything is defined.

Which is information you should have included in your post. Also, when you add two multibit numbers, are there carries?

What I would do is play around with some specific examples, and see if you can generalize things for a proof. For example, suppose that $x, y \in F_2^4$; i.e., bit strings of length 4.

Some examples:
1. x = 1001, y = 1001 -- wt(x) = 2, wt(y) = 2, wt(x + y) = 1 (assuming the 1-bit additions carry)
2. x = 1100, y = 0011 -- wt(x) = 2, wt(y) = 2, wt(x + y) = 4
3. x = 1010, y = 1110 -- wt(x) = 2, wt(y) = 3, wt(x + y) = 0 (again assuming the 1-bit additions carry)

 

[imDooiNGMATH]

Which is information you should have included in your post. Also, when you add two multibit numbers, are there carries?

What I would do is play around with some specific examples, and see if you can generalize things for a proof. For example, suppose that $x, y \in F_2^4$; i.e., bit strings of length 4.

Some examples:
1. x = 1001, y = 1001 -- wt(x) = 2, wt(y) = 2, wt(x + y) = 1 (assuming the 1-bit additions carry)
2. x = 1100, y = 0011 -- wt(x) = 2, wt(y) = 2, wt(x + y) = 4
3. x = 1010, y = 1110 -- wt(x) = 2, wt(y) = 3, wt(x + y) = 0 (again assuming the 1-bit additions carry)

What do you mean by "the 1-bit additions carry"? I'm assuming they don't in this context because for any code x,y x+y = 0. So any instance of 1+1 = 0. Sorry, if I'm misunderstanding. I naively assumed the conventions of the field would more uniform like some other math courses I've taken.

Regarding what you said about examples, I do have the following worked out. Still regarding cases:

If $x \neq y$, then the amount of non-zero digits in $x + y$ can't be equal to zero. So we have $1 \leq wt(x+y)$. It is also the case that because $x \neq y$, at least one of them has to have a weight greater than one because they can't both be the zero word then ( the code word with all entries equal to zero). So without loss of generality, we have $1 \leq wt(x)$ and $0 \leq wt(y)$.

I don't know if any of this will be particularly useful yet.

Edit: I think I got it. There's an equivalency: $wt(x+y) = wt(x) + wt(y) - 2wt(x \cap y)$. ($x \cap y$ is pair-wise multiplication of the codewords. Not super relevant here.) From this, we have $wt(x) + wt(y) = wt(x+y) + 2wt(x \cap y)$. From this, it is immediately clear that $wt(x+y) \leq wt(x+y) + 2wt(x \cap y)$ because $0 \leq 2wt(x \cap y)$. What a great way to spend several hours (not).

 

[Mark44]

You wrote this in post #1:

For two code words $x, y \in F^{n}_2$

I assume this notation means vectors of length n whose components come from the set {0, 1}. From the lack of information that you provided, I assumed that maybe you were talking about strings of bits, with addition defined as binary addition on n-bit words. If that's not the case, you need to clarify exactly what x + y means.

What do you mean by "the 1-bit additions carry"? I'm assuming they don't in this context because for any code x,y x+y = 0. So any instance of 1+1 = 0. Sorry, if I'm misunderstanding. I naively assumed the conventions of the field would more uniform like some other math courses I've taken.

This is all fine if x and y happen to be in $F_2^1$; i.e., single bits. But what if x and y aren't just single bits? How is addition defined?

 

[imDooiNGMATH]

You wrote this in post #1:
I assume this notation means vectors of length n whose components come from the set {0, 1}. From the lack of information that you provided, I assumed that maybe you were talking about strings of bits, with addition defined as binary addition on n-bit words. If that's not the case, you need to clarify exactly what x + y means.
This is all fine if x and y happen to be in $F_2^1$; i.e., single bits. But what if x and y aren't just single bits? How is addition defined?

Ok, so your first paragraph holds for how addition is defined in this context:

It can essentially be thought of as vector addition. It should also be noted: we are working in $\mathbb Z_{2}$ (well, this is how we formed the basis of the addition anyway, but these are binary block codes), hence the set ${0,1}$.

$x + y = (x_1 + y_1)(x_2 + y_2)...(x_n + y_n)$
A similar approach is used for multiplication, denoted as $x \cap y$. Just multiply corresponding entries in the strings, keeping in mod 2.

Really sorry for the missing context

 

[sysprog]

With your expression x + y, it looks like you are doing bitwise binary addition of 1-bit quantities. So with x = y, you have 0 + 0 = 1 and 1 + 1 = 0. Is that what's happening here? How is wt(x) being defined? Is it the number of nonzero bits in a word? For example, would wt(100110) be 3?

I don't see how you can do a proof without some idea of how wt() is defined.

From https://en.wikipedia.org/wiki/Linear_code:

==Definition and parameters==​

A linear code of length $n$ and rank $k$ is a linear subspace $C$ with dimension $k$ of the vector space $\mathbb{F}_q^n$ where $\mathbb{F}_q$ is the finite field with $q$ elements. Such a code is called a $q$-ary code. If $q=2$ or $q=3$, the code is described as a binary code, or a ternary code respectively. The vectors in $C$ are called codewords. The size of a code is the number of codewords and equals $q^k$.​

​

The weight of a codeword is the number of its elements that are nonzero and the distance between two codewords is the Hamming distance between them, that is, the number of elements in which they differ. The distance $d$ of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length $n$, dimension $k$, and distance $d$ is called an [$n,k,d$] code.​

​

We want to give $\mathbb{F}_q^n$ the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (a binary symmetric channel). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.​