So I'm writing a program that takes as input a message, and produces the encoded version of that message using Hadamard encoding. Then another program takes the encoded message, and produces the original message.
To achieve this I've been looking around on Wikipedia, where it gives directions on how to encode messages using inner product and generator matrices. I am aware that you can use Hadamard matrices as well, but the former two methods seem a lot easier. Regardless, I'm still having trouble understanding them.
The methods are written here https://en.wikipedia.org/wiki/Hadamard_code under the titles "Construction using inner products" and "Construction a generator matrix".
1. Construction using inner products
Let's say we have a message/vector $x = 1101$, so its length $k = 4$, it's alphabet $\Sigma \in \{0,1\}$ and of course $x \in \{0,1\}^k$.
My problem here is that wikipedia suddenly introduces a vector $y$ and doesn't explain what it is. It only says that we can construct the codeword using this formula:
$\sum\limits_{i=1}^k x_i y_i$ mod $2$
So I can do a summation over x, because $x_1 = 1$, $x_2 = 1$, $x_3 = 0$ and $x_4 = 1$. But then what is $y$? Can I just make it up to be anything?(anything that starts with "1" that is, if I don't want to be wasteful as explained in the text under the formula). I only know that $y \in \{0,1\}^k$, just like $x$.
2. Construction using a generator matrix
I've had linear algebra at my university, and there we learned that when you want to multiply an $m$ x $n$ matrix with a vector of length $k$, then it must be the case that $m = k$. For example you can only multiply a 3x4 matrix with a vector of length 4.
Now, on the wiki page they give us an example for $k = 3$. They give us the encoding formula:
$pHad(x) = x \cdot G'$
where $G'$ is a 3x4 matrix. But $x$ has length $k = 3$. How do they expect me to multiply a vector $x$ with size 3, with a matrix that has 4 columns?
So to summarize my questions:
- What should vector $y$ be in the first method?
- How can I encode a message $x$ using a Generator matrix if the dimensions are dissimilar?
The article you link explicitly states "Then the Hadamard encoding of $x$ is defined as the sequence of all inner products with $x$: $$ \mathrm{Had}(x) = \left(\langle x,y\rangle\right)_{y\in\{0,1\}^k}$$" The encoding is a tuple of $2^k$ values, one for each $y\in\{0,1\]^k$. That's what "$y$ is": for every $y$, you compute the inner product with $x$, and store it in one of the coordinates.
Again, the articles states "where the message $x$ is viewed as a row vector." This now makes sense: $x$ is a $1\times k$ matrix (row vector), the punctured matrix $G'$ is a $k\times 2^{k-1}$ matrix, so that $$ xG'$$ is well-defined and gives a $1\times 2^{k-1}$ matrix (row vector).