3
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ hey, what's "minimally correlated" in terms of correlation coefficient to you? Zero? -1? $\endgroup$ – Marcus Müller Oct 14 '19 at 20:43
  • $\begingroup$ I did mean the numerical minimum, so I thought of large (magnitude) negative values to be minimal for the purpose of the comparison with the hamming distance. I graphed both functions for a bunch of vectors and noticed that one measurement is a linear transformation of the other. $\endgroup$ – user827822 Oct 14 '19 at 20:54
  • $\begingroup$ ah, ok, yeah, in that case, your approach is right: since by normalization no value below -1 can occur, the vector that is -1 the other is the one with the minimum cross-correlation (in your definition). Whether that definition is useful is a different question, though! $\endgroup$ – Marcus Müller Oct 14 '19 at 21:21
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Marcus, I also suspect that they're not the same, but I'm not sure about your example. Let's say a codeword is $1,1,1$, then the codeword at largest distance is $-1,-1,-1$; the correlation is -3, which is the minimum possible given 3 elements restricted to $\pm 1$. $\endgroup$ – MBaz Oct 14 '19 at 19:36
  • 1
    $\begingroup$ @MBaz ah, it's the minimum correlation coefficient, but maximally correlated, I'd say; I'd say "correlation" is a measure on the absolute of the correlation coefficient, because, from a purely practical point of view, two signals that are linked by a factor (like -1) are very correlated. Doesn't get any more correlated :) $\endgroup$ – Marcus Müller Oct 14 '19 at 19:51
  • $\begingroup$ Marcus, I agree that a very large negative correlation coefficient means that the signals are highly correlated. In the context of this problem, though, it might prove interesting to interpret "minimize the correlation" as "obtaining the actual smallest correlation coefficient", without taking absolute values. $\endgroup$ – MBaz Oct 14 '19 at 20:15
  • $\begingroup$ good point, let's ask OP, maybe I also just misunderstood him or her $\endgroup$ – Marcus Müller Oct 14 '19 at 20:43
4
$\begingroup$

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$.
| improve this answer | |
$\endgroup$

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.