1
$\begingroup$

How is the parity function defined in standard way if inputs are in $\{-1,+1\}$ instead of $\{0,1\}$. For $\{0,1\}$, parity is $x_1\oplus x_2\oplus\cdots\oplus x_{n-1}\oplus x_n$. I am looking for how is inner product mod $2$ defined if inputs are in $\{-1,+1\}$. Is it $\frac{1}{4}\sum_i(x_i+1)(y_i+1)\mod 2$ or just $\sum_i x_iy_i \mod 2$?

What if one replaces $2$ by $p$ a prime or $N$ a composite?

$\endgroup$
2
$\begingroup$

In the representation of bits by $\pm 1$, the most important aspect is in fact the sign. In fact the best way to describe the mapping from $\{0,1\}$ to $\{-1,+1\}$ is the function $f(x) = (-1)^x$. This is a representation in which logical AND and OR are awkward at best, but PARITY is dead easy. Let $a = f(x)$, $b = f(y)$, and $c = f(x \oplus y)$: $$c := f(x\oplus y) = f(x + y - 2xy) = (-1)^{x + y - 2xy} = (-1)^{x + y} = f(x) f(y) = ab.$$ Thus, in the sign representation, parities are computed by multiplication.

$\endgroup$
  • $\begingroup$ $0->1$ and $1->-1$. How about for inner product? $\endgroup$ – Turbo Dec 9 '14 at 18:39
  • $\begingroup$ @Turbo: I am not sure what you mean either by your remark, or your question, in your comment above. Do you mean to ask how to represent $(x_1 \wedge y_1) \oplus (x_2 \wedge y_2) \oplus \cdots \oplus (x_n \wedge y_n)$? $\endgroup$ – Niel de Beaudrap Dec 9 '14 at 18:40
  • $\begingroup$ Yes. when inputs are in $\{-1,+1\}$. For $\{0,1\}$ it is just $\sum_ix_iy_j\mod P$. The parity has to agree when using either formulation of inputs. $\endgroup$ – Turbo Dec 9 '14 at 18:57
  • $\begingroup$ I mean $0\rightarrow 1$ and $1\rightarrow -1$. $\endgroup$ – Turbo Dec 9 '14 at 18:58
  • $\begingroup$ As I noted in my answer, logical AND is awkward in the sign representation. For $a = (-1)^x$ and $b = (-1)^y$ we can define $\mathrm{AND}(a,b) = 1 + (\tfrac{a+b}{2}) - (\frac{a+b}{2})^2$, and simply express the dot-product as the product of $\mathrm{AND}(a_1,b_2), \mathrm{AND}(a_2,b_2), \ldots, \mathrm{AND}(a_n,b_n)$ as with the boolean representation; but that seems terribly awkward, and I'm not sure when one would want to. $\endgroup$ – Niel de Beaudrap Dec 9 '14 at 19:44

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.