0
$\begingroup$

Question: I am looking for a way to transform a series of 1s and 0s to be distributed 50% 1s and 50% 0s. How do I do that?

Background: I am a software engineer working on writing code for a microcontroller and we have a requirement to generate random numbers. So I thought to use "white noise" to generate random bits of information. It is known that when sampling an ADC component (analog to digital converter) the last bit of information is highly sensitive and typically can be categorized as white noise. So I sampled hundreds of samples of this bit in a time difference of a a few micro seconds and I checked what is the distribution of 1s and 0s. The distribution is around 30% 1s and 70% zeros. Moreover, we tested this on several duplicate hardware (with the same micro controller) and the distribution varies (sometimes its 40% 1s and sometimes is 60% 1s etc.). We want to take the first 100 bits and use it to create a random number but we are afraid that if there are some microcontrollers with a very biased distribution (e.g. 95% 1s) then the probability that we would get different numbers among those cases would be very low. We are planning to manufacture millions of units of this product and we must guarantee that there are no two numbers a like and we must do this within the microcontroller (we can't bring this number from outside and load it into the microcontroller ourselves).

My attempt to solve the problem: So I thought to just do a sequence of iterations according to this logic:

  1. Count the number of 1s in the sequence and divide it by the size of the sequence. If the ratio is bigger than 45% or smaller than 55% (we are ready to tolerate a 5% divination) then nothing needs to be done. This is a sequence that is distributed uniformly enough for us. Otherwise, move on to the next step.
  2. Go over every pair of bits (i.e. first pair are bits in location 1 and 2, second pair is bits 3 and 4 etc) and if the pair is 00 or 11 then this will be a new 0 in a new sequence. Otherwise it will be 1 in a new sequence. Repeate step 1 again.

The mathematical logic for this is that if the probability of getting 1 is X and 0 is (1-X) then X*(1-X)*2 is the probability of the pairs 01 and 10 combined and it will always be closer to 0.5 than X or (1-X) separately. And so repeating this process indefinitely should bring me to 50% probability and uniform distribution of 1s and 0s and then I can use the bits knowing I am getting a truly random number (e.g. 100 bit sequence) and the probability of getting the same number across millions of devices is 0.5^100 which is practically zero.

My Issue: I wrote a piece of code to test this and data sets I got from my microcontroller. Most of the time it worked. But there were several times that the probability didn't converge to 50% directly and instead at some point the probability suddenly shot away from 50%. e.g. 5% -> 10% -> 12% -> 16% -> 24% -> 32 % ->64% -> 72% -> 56% -> 77% ->38% -> 46% | this is 11 steps! what the hell happened here? Here is the print output of this example run: enter image description here I want to be able to do this within 5-6 iterations. Otherwise it is taking too long.

My code to test this:

#include <iostream>

#define DATA1_SIZE 32000
//#define DATA2_SIZE DATA1_SIZE/2


bool CheckRandomnessOfArrayData(uint8_t* ucpData, uint16_t usDataSize)
{
    uint16_t usCountOnes = 0;    // init
    uint16_t usLowerBoundryOfUniformDistribution = 45;  // [%]
    uint16_t usUpperBoundryOfUniformDistribution = 55;  // [%]
    uint16_t usUniformDistributionCalc = 0; // init

    for (uint16_t usIndex = 0; usIndex < usDataSize; usIndex++)
    {
        usCountOnes += ucpData[usIndex];
    }

    usUniformDistributionCalc = (usCountOnes * 100 / usDataSize);

    printf("usUniformDistributionCalc = %d\n", usUniformDistributionCalc);

    if ((usUniformDistributionCalc < usLowerBoundryOfUniformDistribution) ||
        (usUniformDistributionCalc > usUpperBoundryOfUniformDistribution) )
        return false;
    else
        return true; 
}

void TransformArray2MoreUniformDistribution(uint8_t* ucpData, uint16_t usDataSize)
{
    for (uint16_t usIndex = 0; usIndex < usDataSize / 2 ; usIndex++)
    {
        ucpData[usIndex] = ucpData[usIndex * 2] ^ ucpData[usIndex * 2 + 1];
    }
}

void PrintFinalData(uint8_t* ucpData, uint16_t usDataSize, uint8_t ucDivisionNum)
{
    uint16_t usIndex = 0u;
    for (usIndex = 0; usIndex < usDataSize; usIndex++)
    {
        printf("%d,",ucpData[usIndex]);
    }
    printf("\n");
    printf("DataSize = %d\n", usDataSize);
    printf("NumberOfDivisions = %d\n", ucDivisionNum);
}

int main()
{
    static uint8_t ucData1[DATA1_SIZE] = {data series is put here}
    uint16_t usDataSize = DATA1_SIZE;
    uint8_t ucDivisionNum = 0;
    bool bIsRandom = false; // init

    while (usDataSize != 0)
    {
        bIsRandom = CheckRandomnessOfArrayData(ucData1, usDataSize);
        PrintFinalData(ucData1, usDataSize, ucDivisionNum);
        printf("---------------------------------------------\n");
        if (bIsRandom == true)
            break;
        else
        {
            TransformArray2MoreUniformDistribution(ucData1, usDataSize);
            usDataSize = usDataSize / 2;
            ucDivisionNum++;
        }
    }
    
    printf("###########################################\n");
    printf("Status = %d\n", bIsRandom);
    PrintFinalData(ucData1, usDataSize, ucDivisionNum);
}
$\endgroup$
7
  • 2
    $\begingroup$ Why don't you just a random number generator like rand(). You get 32 bits in one go. $\endgroup$
    – Hilmar
    Commented May 15, 2022 at 15:58
  • 2
    $\begingroup$ You are aware that it's generally acknowledged that generating truly random numbers in hardware is incredibly difficult? Hence, serious people do things like populating walls with Lava Lamps and using machine vision to extract randomness from looking at the patterns they produce. Anything you do in hardware is going to be subject to all sorts of variation, some of which is correlated to other physical phenomenon, some of which is correlated to the device's own behavior at other times, and some residual that is truly random. I suggest a literature search if it's really important. $\endgroup$
    – TimWescott
    Commented May 15, 2022 at 21:00
  • 2
    $\begingroup$ @Hilmar just my usual rant: rand() is probably the worst widely-employed PRNG you'll find. Don't use it. You do not get 32 bit of entropy! It's really a bad generator, and atop of it, unsafe. Since this is C++: C++ comes with a <random>, which actually has good PRNGs. $\endgroup$ Commented May 16, 2022 at 10:14
  • 1
    $\begingroup$ @EyalGerber which microcontroller? This makes a lot of practical difference here! Also: if things are truly random, you can never guarantee that two devices don't draw the same number, that's not how actual randomness works. You can just push the probability low enough to be acceptable for you. How many units are we actually targetting, and what's an acceptable probability for a collision to happen for you? $\endgroup$ Commented May 16, 2022 at 10:17
  • 1
    $\begingroup$ (and: of the $2^N$ binary numbers of $N$ bits length, only $\frac{N!}{(N/2!)^2}$ have half zero, half one, which is less than $2^N$ for finite $N$. If your random number generator was good in the sense of giving you maximum randomness, it's clear that it necessarily produces numbers that don't have as many 1s as 0s. You can bound this, theoretically, by the way. Sequences where the observed probabilities are $\varepsilon$-close to the source probabilities (here: 1/2 for both values, i.e., entropy of 1 bit) are called typical sequence, and it's the whole point of lossless compression.) $\endgroup$ Commented May 16, 2022 at 10:40

1 Answer 1

-1
$\begingroup$

So I just wanted to update that the algorithm I posted in the question actually works great. The reason I had weird cases that there was no convergence to 50% was because the datasets I used were copies of smaller datasets (e.g. I took 100 random numbers and duplicated it hundreds of times to create a larger sample). Yes I know... that's foolish and it was very naive on my part.

Bottom line, after I simply took really large original samples (without duplicating smaller samples) the algorithm always worked and managed to convert my datasets to become 50% 1s and 50% 0s.

Whether or not the way I collected the data is truly random or not is a different discussion. Thanks for all your comments.


UPDATE: I found another algorithm that is so simple I can't believe I didn't think about it myself. I tested it and it works flawlessly. It is much more efficient than the algorithm I wrote in my question. For those interested it is written here: https://cs.stackexchange.com/a/35223/150782

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.