By Paul Dreik 2023-09-02
Imagine you have a DA converter, but it has poor resolution compared to what you want. On the other hand, it has a much higher update frequency than requested. Then you could do something like pulse width modulation. Say the DA is capable of 16 bits resolution, but you wish to have 24 bits. Then you determine the two closest 16 bit values, and flip between those such that the average output is the desired.
Example: the desired 24 bit output is 0x7D1225. The closest 16 bit values are 0x7D12 and 0x7D13. The bottom bits are 0x25. Let the output be 0x7D12 for 0x25 (37) samples and 0x7d13 for 0xDB (219) samples. The average value will be 0x7D1225.
-------------- -----------
| DA converter | --> | LP filter | --> output
-------------- -----------Imaging the desired value to be right between two steps of the DA. (For example, wanting 0x7D1280 in the example above). Outputting 128 samples of 0x7D12 and then 128 samples with 0x7D13 would create a a square wave with a 1/256 frequency of the DA rate. Compare this to outputting the values interleaved (0x7D12, 0x7D13, 0x7D12, 0x7D13 and so on) which would give the square wave a frequency of 1/2 of the DA rate. This creates an error with much higher frequency, which is attenuated much more by the LP filter downstream of the DA converter.
Assume the output sequence of the DA is to be repeated each N cycles. Assume the duty cycle of 0<M<=N which creates an average value M/N (for M=0 and M=N, there is no interpolation, the DAC can output those values perfectly). The problem is now to calculate a binary sequence (with M ones and N-M zeros) such that the noise after passing through the low pass filter is as small as possible. Because the output range can be time shifted without affecting the spectrum or average, we can assume the first output always is a one.
A first order low pass filter has transfer function
1/(tau*s+1) where tau is the time constant in seconds.
Assume the output of the DA converter (=our binary sequence) has fourier
transform X (an array of N values) which can be calculated given the
binary sequence. The gain of the low pass filter is calculated as Y
(same size as X). The noise on the output of the low pass filter, will
be sum |X(i)*Y(i)|^2. The first element (the DC value)
could be skipped since that is given by M/N.
I made a small program that tried random permutations, keeping the best. This is very time consuming, since the number of permutations is very high even for moderately sized problems. But I was able to see that the output sequence spreads the ones evenly, as opposed to PWM which puts them all in the beginning.
One way to generate the output is to use something that generates a permutation of values 1-N and then output a one if the the output value is >=M and a zero otherwise. This relates to what I talked about in my 2019 talk Home made crypto for a non-cryptographic problem: the permutation can be generated by using a block crypto on a repeating counter.
A crypto is however expensive compared to using a linear feedback register
The suggestion is to use a m-bit linear feedback register where
N=2^m-1 and output a one if the output is
>=M. Any invertible transformation (such as an xor or
bit rotation) can be inserted to increase the quality of the output.
I am an automatic control engineer, and of course I will try to approach the problem as a feedback problem. This uses a integral of the control error with a nonlinear controller.
Assume the desired output is M/N with M and N integers. For each time step k of the DA output, update the running sum s(k):
s(0)=0
u(0)=0
s(k+1)=s(k)+N*u(k)-M
u(k)= 1 if s(k)<0
0 otherwiseI simulated this and there seems to be a cycle length of at most N. I think this can be proved by the pidgeon hole principle, since s(k) is integer and it is limited by N-M upwards and -M downwards.
This resembles the delta-sigma modulator. Also, see the Bresenham line algorithm.
There are related concepts which are very interesting: