Is maximizing hamming distance the same as minimizing correlation?

Question

For the design of an error correcting code, I might wish to maximize the distance between the codewords $\sum a_i \oplus b_i$.

For spreading sequences I'd like to minimize the cross-correlation at $t=0$ of $\sum \sigma(a_i)\sigma(b_i)$ where $\sigma(\cdot)$ maps binary $0\to1$ and $1 \to (-1)$ (i.e. what you'd get out of a BPSK matched filter when $E_b$ is normalized and there is no noise).

Are these criteria the same? It seems to me that since $\sigma$ acts as an isomorphism that turns cyclic$\pmod 2$ addition into cyclic complex multiplication, they are equivalent statements. Can you verify this and let me know where I can read more about it?

Answer 1

Well, as you can easily verify, these two criteria aren't the same if you define "minimum correlation" to mean that the absolute value of the correlation coefficient is minimized (i.e. 0):

• In $\mathbb F_2^N$, the vector that's the farthest away from any given vector $v$ is its bit-wise inverse $\overline v$ (using Hamming distance)
• Using your mapping, the BPSK symbol vector mapping to $\overline v$ is the $-1$ times the one mapping to $v$: $\sigma(v) =-\sigma(\overline v)$. That's maximal correlation, not minimal.

In short, the hamming distance defined over your finite field isn't a compatible norm to the $\mathcal L_2$ norm that gives a correlation coefficient over fields over the real or complex numbers, given your $\sigma$. There's not much to say here – they are simply not the same.

If you, however, define the minimum correlation to be found when the correlation coefficient takes the smallest possible value (not: absolute value), then yes, due to normalization, the minimum possible correlation coefficient is -1, and as shown above, your method is one to find the matching BPSK representation.

Answer 2

Two codewords $c_1$ and $c_2$ of length $n$, with elements in $\lbrace +1, -1 \rbrace$, and Hamming distance $d$, have a cross-correlation given by $$(n-d) -d = n-2d.$$ The reason is that there are $n-d$ bits that are equal and their product is $1$, and $d$ bits that are different and their product is $-1$.

Note that:

• The larger the distance $d$, the smaller the correlation.
• The correlation by itself does not tell you anything about the distance, since you also need to know $n$. For example, $1,1,1$ and $-1,-1,-1$ have correlation $-3$ but $1,1,1,1,1,1$ and $1,1,1,-1,-1,-1$ have correlation $0$.