1
$\begingroup$

Differential equations can be used to describe functions. Some famous ones include $$\frac{\partial f}{\partial x} - f(x) = 0$$ $$\frac{\partial^2 f}{\partial x^2} - f(x) = 0$$

The iterated running xor working on a sequence of numbers $\{x_0,\cdots,x_N\}$ on $\mathbb Z_2$ :

$$\mathcal{X}\{x\}_{k} = x_{k} \oplus x_{k-1}$$

carries some of similar properties as the differential operator with perhaps the most obvious one: constants are taken to $0$. A string of $x_{k_1}=x_{k_1+1}=\cdots=x_{k_2}$ will give $\mathcal{X}\{x\}_{k} = 0$ for all $k\in\{k_1+1,k_2\}$.

We can obviously model or represent (families of) continuous functions with differential equations.

Now to my question : how can we do the same with iterated xor operations?

$\endgroup$

1 Answer 1

3
$\begingroup$

"xor" corresponds to addition over the binary field $\mathbb F_2$. I suppose a natural generalization of differential equations in this context might be recurrence equations for sequences in $\mathbb F_2$. For example, the linear equation $$ x_{n+1} = x_{n} + x_{n-5}$$ with initial conditions $x_0 = 1$, $x_1 = \ldots = x_5 = 0$ produces an interesting sequence with period $63$.

$\endgroup$
1
  • $\begingroup$ Yes, wonderful! Thank you Robert. Something akin to this is precisely what I had in mind. For my toy examples of thresholded sine waves this can reduce the number of 1 bits very closely to what I believe would be the theoretically optimal. $\endgroup$ Apr 18 at 17:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .