1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Aug 10 '17 at 16:07
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.