I have a question of two (and a half) parts relating to parity functions. I) Pertaining to the definition of a parity function. II) Pertaining to the intuition behind checking some specific functions' parity.
I) In this particular set of questions, the parity function is defined as (image link here): Parity function $Pf(X)$ is equal to $1$ if an even number of inputs is $1$ (i.e the function being checked, further on $f(x)$, is even), and $-1$ otherwise.
This is not in line with the typical "Parity Bit" function which, unlike this one, returns "$1$" if the $f(x)$ is odd. I was wondering whether my case was a specific definition or a distinct widely known separate one.
II) I would like my intuition checked on the following exercise, if possible, explained why/where I was wrong.
For which of these does the parity function return $1$ for? In other words, which of these are "even"? The dimension of input is $n>1$.
1) Function that returns the least-significant (right-most) bit of the argument.
For a two-bit variable there's only one possible input where it returns a "$1$". Thus, this one is odd.
2) Function that returns k-numbered bit of argument, where k is less than n.
Same logic as previous case.
3) const f(x) = 1
There's $2^{(n-1)}$ possible inputs for every $n>2$, and there's an equal amount of possible outputs. The function is even.
4) const f(x) = 0
If you consider 0 an even number, then the logic from before applies.
5) "Characteristic function of a set with the cardinality of 5"
This seems to be referring to an indicator function. My understanding is limited, but it wouldn't seem like this is even.
6) f(x)=1 only if x has an odd number of ones when written in binary
For every n, half of the inputs have an odd number of ones, which is $2^{(n-2)}$. For $n=2$ this number is equal to $1$, so it's incorrect to generalize this function's evenness.
7) f(x)=1 only if x has an even number of ones when written in binary
For every n, half of the inputs have an even number of ones, which is $2^{(n-2)}$. For $n=2$ this number is equal to $1$, so it's incorrect to generalize this function's evenness.
We define $\tilde x\in\mathbb{Z}$ and $\tilde x_i\in\mathbb{Z_2}$ (is a bit-value),
and $\tilde x_i = 1-2x_i$ is clearly represented like the following function:
\begin{align*} f(x) = \begin{cases} 1 &\text{if $x$ = 0}\\ -1 &\text{if $x$ = 1} \end{cases}\end{align*}
When $x$ (the input bit) is equal to $0$ the function returns $1$, else if $x$ is equal to $1$ the function returns $-1$.
The length of the bitstream of $\tilde x$ can be calculated this way: $$N = \lfloor\log_2{\tilde x}\rfloor+1$$
The parity function is defined as \begin{align*} P(\tilde x)=\prod_{i=0}^{N-1}f(\tilde x_i), \end{align*}
The capital pi symbol represents multiplication of successive values. Hence, we multiply together all the parities. And since $f(x)$ returns either $1$ or $-1$ then $P(\tilde x)$ will return either the value $-1$ or the value $1$. The proccess of $P$ is iterative, and the value $-1$ is never changed unless a successive parity is also $-1$ (then it changes its sign), this parity will flip as many times as there are one's in the binary expansion (of $\tilde x$) and keep the final state when $i=N-1$. The final state depends on the number of $1$'s in the binary expansion basically. In short, everytime $\tilde x_i=1$ the product will change its sign, but when $\tilde x_i=0$ the product will do nothing to the result. These two series of actions can easily be understood when $x\cdot -1=-x$ and $x\cdot 1=x$. i.e.:
$$+\cdot+ = +$$ $$+\cdot- = -$$ $$-\cdot+ = -$$ $$-\cdot- = +$$
From the above reasonings we can deduce some facts:
Examples:
$$P(2_{10}) = P(10_2) = -1$$ $$P(13_{10}) = P(1101_2) = -1$$ $$P(27_{10}) = P(11011_2) = 1$$ $$P(60_{10}) = P(111100_2) = 1$$
Other facts:
The bitlength itself do not influence the parity.
Answers:
1) Function that returns the least-significant (right-most) bit of the argument.
$$P(00_2) = 1$$ $$P(01_2) = -1$$ $$P(10_2) = -1$$ $$P(11_2) = 1$$
There are two possible inputs where it returns a $1$: $0$ and $3_{10}$.
2) Function that returns k-numbered bit of argument, where k is less than n.
Im not sure what you mean by k-numbered bit of argument. Assuming you mean the bitlength of the argument, this does not influence the output parity.
3) const f(x) = 1
The function is only even when $\tilde x = 0$ or there is an even number of $1$'s in the binary expansion of $\tilde x$.
4) const f(x) = 0
$0=$ parity $1$
5) "Characteristic function of a set with the cardinality of 5"
Assuming you mean the parity $1$ is even, then $5$ is even.
6) f(x)=1 only if x has an odd number of ones when written in binary
False, $P(\tilde x)=-1$ if there is an odd number of ones.
7) f(x)=1 only if x has an even number of ones when written in binary
True, $P(\tilde x)=1$ if there is an even number of ones.