Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
The question I have is this-- if I have two binary vectors, i.e. $x_1, x_2 \in \mathbb F_2^k$ that are orthogonal, i.e. $x_1^T x_2 = 0$, and let's say I Hamming encode each of them separately with an $(n,k)$ code to produce $y_1, y_2 \in \mathbb F_2^n$, respectively.
Can we make any general statements about the orthogonality of $y_1$ and $y_2$? Will they be orthogonal also?
I don't think you cannot state generally that $y_1$ and $y_2$ will be orthogonal. I'll try to sketch out my thinking:
Since the Hamming code is a linear code, each parity bit can be represented as a linear combination of the information bits; that is, each bit can be represented as:
$$ p_i = \mathbf{g_i^T}\mathbf{x} $$
where $\mathbf{x}$ is the information bit vector and $\mathbf{g_i^T}$ is the generator for the $i$-th parity bit (it's one column from the code's generator matrix $\mathbf{G}$); it is a binary vector that represents the parity checks that go into $p_i$. When formulated this way, the parity bit can be thought of as the projection of the information bits onto the respective generator vector.
Assuming that you have a systematic code (all Hamming codes that I've seen before are), the encoded vectors $\mathbf{y_i}$ look like (assuming the code has $k$ information bits and $m$ parity bits):
$$ \mathbf{y_i} = \left[x_{i_1}\ x_{i_2}\ \ldots \ x_{i_k}\ |\ p_{i_1}\ p_{i_2}\ \ldots \ p_{i_m} \right]^T $$ $$ \mathbf{y_i} = \left[x_{i_1}\ x_{i_2}\ \ldots \ x_{i_k}\ |\ \mathbf{g_1^T}\mathbf{x_i}\ \mathbf{g_2^T}\mathbf{x_i}\ \ldots \ \mathbf{g_m^T}\mathbf{x_i} \right]^T $$
In order for the vectors $\mathbf{y_1}$ and $\mathbf{y_2}$ to be orthogonal, their dot product must be zero. It has the form:
$$ \mathbf{y_1} \cdot \mathbf{y_2} = \sum_{j=1}^k \left(x_{1_j} + x_{2_j}\right) + \sum_{j=1}^m \left(\mathbf{g_j^T}\mathbf{x_1} + \mathbf{g_j^T}\mathbf{x_2}\right) $$
Since the information vectors $\mathbf{x_1}$ and $\mathbf{x_2}$ are orthogonal, the first sum above is zero, so we are left with:
$$ \mathbf{y_1} \cdot \mathbf{y_2} = \sum_{j=1}^m \left(\mathbf{g_j^T}\mathbf{x_1} + \mathbf{g_j^T}\mathbf{x_2}\right) $$
$$ \mathbf{y_1} \cdot \mathbf{y_2} = \sum_{j=1}^m \mathbf{g_j^T}\left(\mathbf{x_1} + \mathbf{x_2}\right) $$
There is no requirement that this condition be zero for an arbitrary linear block code. I haven't taken the specific structure of the Hamming code into account here, but I suspect that it doesn't happen to meet this criterion either.
