I’ve been wondering if you can do DSP operations usefully with bitwise operations on infinite streams of bits, perhaps representing a signal in PDM, with a pipelined graph of binary-signal combinators. This is tempting both because you can get 64-way or 128-way parallelism on modern CPUs and because you can perhaps conserve area in FPGA implementations.
For example, to detect a frequency, you could generate two 1-bit-deep square waves in quadrature at the frequency, XOR them with the input bits, and then run a population count of the bits. This has the disadvantage that you’re getting contaminated with the correlation with odd harmonics of the square-wave probe signals; I think you can maybe reduce this problem with upconversion?
Upconversion, of course, is also XOR.
Population count can be done with streaming full-adders on the bitstreams, after ANDing them with wavelength-2, wavelength-4, wavelength-8, etc., square waves and their complements, then delaying the output of the complemented version by 1, 2, 4, etc., bit times, before adding it back to its counterpart. This crudely converts the bitstream into PCM, but the full-adders can remain oblivious to the PCM sample boundaries. Thresholding the PCM can perhaps use a single bit test in each sample (generated by AND with a low-duty-cycle wave of the same frequency). AND and OR may be adequate approximations for min and max.
For other practical operations, a perfect-unshuffle operation would be useful, converting one bitstream into two bitstreams at half the speed.
A FIR filter might be a fixed-length word that you XOR against the bitstream at every bit offset, emitting perhaps the majority-rule of the XOR output bits.
2019 update: it turns out that there is some substantial research on a bitstream approach, but it uses very different primitives than I was thinking. The fundamental operations are NOT (1 - X), AND (X·Y), selecting bits at random from either of two bitstreams (½(X+Y)), and of course delay with a D flip-flop. The random-selection idea is very clever! My thinking was stuck in the deterministic paradigm, which is perhaps an unnecessary constraint when we’re talking about bitstreams that by necessity incorporate a lot of error.
(I wish I could remember the names of the bitstream DSP papers or researchers.)
I’ve also read more about oversampling 1-bit ADCs and DACs since I wrote the above (mostly in Horowitz & Hill) and what I read leads me to believe that this approach could be more effective than you might think, since a third-order ΔΣ converter can hit an ENOB of 16 at only a 64× oversampling ratio, only 4× worse efficiency than PCM. I don’t know that the noise shaping of these incredible devices will survive the kinds of operations described here.
If not, a sort of ΔΣ converter might itself be in some sense a safer way to do these computations. For example, if you want to attenuate the signal represented by a ΔΣ bitstream by 9dB, you could very reasonably build an all-digital feedback system using a couple of up/down counters which attempts to maintain the input counter at 8× the value of the output counter.