Algorithm to distribute bits evenly but with increasing density

Question

I'm looking for an algorithm to generate a series of bits such that the density at the start of the series is very low (i.e. mostly 0s), and by the end of the series is very high (i.e. mostly 1s). I've got this to work by varying the probability that a random number would fall within a range, but I'd like to find a more structured [read: deterministic] algorithm, like some sort of way to steadily increase the density of 1s.

Does anyone know of something similar? Or perhaps some reading on such topics? It's proving to be quite fun to think about but also rather challenging (unless I'm missing something simple)!

Answer 1

A very general way to do this deterministically (no random numbers) is with a sigma-delta modulator.

Pick a smoothly increasing function that starts at 0 and ends at 1. Then use the modulator algorithm to approximate with 0's and 1's.

NB: Sigma-delta modulators are very commonly used in electronics to convert analog signals (sound, video, etc.) to 1/0 bit streams.

For illustration, I'll take a ramp from 0 to 1 over a period of 100 and use a first-order converter. But you could choose any curve you like. For example, a hyperbolic tangent scaled horizontally will give smaller start and finish slope with more rapid change in the middle. And a second order converter might provide "nicer" patterns. They tend to be a bit less regular.

It's a very simple algorithm. In C:

#include <stdio.h>

int main(void) {
  int x_max = 99;
  double vn = 0;
  for (int x = 0; x <= x_max; ++x) {
    double xn = (double) x / x_max; // linear ramp from 0 to 1.
    int yn = vn > 0.5;
    printf("%d", yn);
    vn += xn - yn;
  }
  printf("\n");
  return 0;
}

As you can see, it's deterministic. It's also very simple and fast: no trig functions, exponentials, etc. That's why it's good for hardware implementation.

Output split into 2 lines for easier viewing:

00000000000100000010000100010001001001001010100101
01010110101011011011011101110111101111110111111111

Here is a seminal paper on sigma-delta conversion. The variables in the program above match Figure 8. Figure 13 shows a second-order diagram if you want to try that.

For fun, here's a run with an interval of 1000:

00000000000000000000000000000000010000000000000000
00000010000000000000001000000000000100000000001000
00000010000000010000000100000001000000010000001000
00010000010000010000010000010000010000100001000010
00010000100001000010001000010001000100001000100010
00100010001000100100010001001000100100010010001001
00010010010010010001001001001001001001001001001001
00101001001001001010010010100100101001010010010100
10100101010010100101001010100101010010101010010101
01001010101010100101010101010101010010101010101010
10101010101010101101010101010101010110101010101011
01010101101010101101010110101011010110101101010110
10110101101101011010110110101101101011011011011010
11011011011011011011011011011011011101101101101101
11011011101101110110111011011101110110111011101110
11101110111011110111011101111011101111011110111101
11101111011110111101111101111101111101111101111101
11111011111101111111011111110111111101111111101111
11111011111111110111111111111011111111111111101111
11111111111111111101111111111111111111111111111111