# Does Hamming encoding preserve orthogonality?

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?

• By "Hamming encode ... with an $(n,k)$ code" do you mean that you are using a (possibly shortened) Hamming code (a single-error-correcting $(2^n-1,2^n-1-n)$ code? Also, orthogonality with respect to $\mathbb F_2^n$ is not the same as orthogonality with respect to channel coding. – Dilip Sarwate Aug 10 '17 at 16:07

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.

• It is also easy to check this using two all-one messages in (for example) a (7,4) code and consider the corresponding codewords. – msm Aug 10 '17 at 10:36