Generating uniform binary arrays that sum to a given number

Question

I want to generate some binary arrays to control the brightness of an LED without a controller. Rather than generate the pulse widths on the microcontroller (which would take up instruction cycles that should be used for other things), I'll hard-code them as a look-up table, and loop through the binary array over and over, setting the LED either on or off at that instruction.

Assuming I have an array length of 4, I would have 5 brightness levels:

{{ 0, 0, 0, 0 },
 { 1, 0, 0, 0 },
 { 1, 0, 1, 0 },
 { 1, 1, 1, 0 },
 { 1, 1, 1, 1 }}

Notice that I have tried to distribute the 1's as evenly as possible throughout the array, which is not always possible but small anomalies shouldn't be visible to the human eye.

Let's say I have an array length of 8, and I want a brightness of 5/8:

{ 1, 0, 1, 1, 0, 1, 1, 0 };

This seems like a good spread, but I could have also used:

{ 1, 0, 1, 1, 1, 0, 1, 0 };

Which is better? The average brightness is, of course, the same. The number of changes from one state to another is also the same. The standard deviation is the same. Looking at the runs, however, the first example has a much lower variance of run length which means it's more uniform and, therefore, better.

Anyway. I need an algorithm to generate these arrays for a given length and brightness. If possible, the algorithm should find an optimal array - one that's as uniform as possible.

It's not as simple as it sounds. To be honest, I'm tempted to just write a brute-force algorithm that compares all possibilities and returns the best.

I was even considering putting together an Integer Programming model, but that seems like overkill for this problem.

Unless someone has a better idea?

Edit:

It turns out that { 1, 1, 1, 1, 0, 0, 0, 0 } has the same run variance as { 1, 0, 1, 0, 1, 0, 1, 0 }, so the metric needs to be a little more complicated as the second example is clearly superior to the first. (For longer array lengths, some LED flicker might be visible of the 1's are bunched up).

Are you trying to evenly distribute the zeros in this array? — argentage
– argentage, Commented Jan 10, 2013 at 0:17
What you want to do is minimize the run length of either 0 or 1. The main idea is that this sequence goes through a low pass filter (our visual system). If your sequence contains transient low frequencies that are below the high cut off of this low pass filter, then you would see a transient flicker. The sequences A={ 1, 0, 1, 1, 0, 1, 1, 0 } and B={ 1, 0, 1, 1, 1, 0, 1, 0 } have the same energy content, but if you do a Fourier transform on the sequences, you would see B contains lower frequencies than A due to the 1,1,1. — thang
– thang, Commented Jan 10, 2013 at 1:11

thang · Accepted Answer · 2013-01-10 01:42:55Z

Ok here it is. Basically, what you want to do is minimize the maximum run length of 0 or 1. The general idea is to distribute what we can. For the remainder, just jam it in at the front.

N = # of total bits n = # of 1s

void pwm(int N, int n, char* z = 0) {
    if (n == 0) {
        // degenerate case!
        for (int i = 0; i < N; i++) {
            printf("0");
        }
        printf("\n");
        return;
    } else if (n == N) {
        // degenerate case!
        for (int i = 0; i < N; i++) {
            printf("1");
        }
        printf("\n");
        return;
    }
    int m = N - n;
    int sep = m/n;
    int rem = m%n;
    int pre;
    int i,j;
    std::list<char> clist;

    if (z == 0) {
        // if more 1 than 0, then flip
        if (sep > 0) pwm(N,n,"01");
        else pwm(N,N-n,"10");
        return;
    }

    pre = sep/2;

    for (j = 0; j < pre; j++)
        clist.push_back(z[0]);
    if (rem > 0) {
        clist.push_back(z[0]);
        rem--;
    }

    for (i = 0; i < n; i++) {
        if (i!=0) {
            for (j = 0; j < sep; j++)
                clist.push_back(z[0]);
            if (rem > 0) {
                clist.push_back(z[0]);
                rem--;
            }
        }
        clist.push_back(z[1]);
    }

    for (j = 0; j < sep-pre; j++)
        clist.push_back(z[0]);


    // output the data so we can see
    char* res = new char[N+1];
    memset(res, ' ', N);
    res[N] = 0;
    char* u = res;
    for (std::list<char>::iterator cli = clist.begin(); cli != clist.end(); cli++) {
        (*u) = *cli;
        u++;
    }

    printf("%s\n", res);


    delete [] res;
}

Here's an output for N=25:

0000000000000000000000000
0000000000001000000000000
0000001000000000001000000
0000100000001000000010000
0001000001000001000001000
0010000100001000010000100
0010001000100010001000100
0010001000100010010010010
0010010010010010010010010
0100100100100100100101010
0100100100100101010101010
0100100101010101010101010
0101010101010101010101010
1010101010101010101010101
1011011010101010101010101
1011011011011010101010101
1011011011011011011010101
1101101101101101101101101
1101110111011101101101101
1101110111011101110111011
1101111011110111101111011
1110111110111110111110111
1111011111110111111101111
1111110111111111110111111
1111111111110111111111111

ElKamina · Accepted Answer · 2013-01-10 01:22:36Z

0

Assume you need to light up k points in a grid of n points. You can follow the following probabilistic approach.

remk=k
remn=n
for i in range(n):
    x[i] = 1 if rand()< remk*1.0/remn else 0
    remk-=x[i]
    remn-=1

x is the array that contains lighting arrangement.

answered Jan 10, 2013 at 1:22

ElKamina

7,82730 silver badges45 bronze badges

Collectives™ on Stack Overflow

Generating uniform binary arrays that sum to a given number

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related