밀도를 높여서 비트를 균등하게 분배하는 알고리즘

Question

일련의 비트를 생성하는 알고리즘을 찾고 있는데, 시리즈의 시작 부분의 밀도가 매우 낮습니다 (즉, 대부분 0). 시리즈는 매우 높습니다 (즉, 대부분 1s). 임의의 숫자가 범위 내에 들어갈 확률을 변경하여이 작업을 수행 할 수 있지만 안정적으로 1의 밀도를 늘리는 일종의 방법과 같이 더 구조화 된 [읽기 : 결정적] 알고리즘을 찾고 싶습니다. .

누구나 비슷한 것을 알고 있습니까? 또는 그러한 주제에 대한 독서가 있습니까? 생각하기에 꽤 재미 있다는 것을 증명할뿐 아니라 (다소 간단한 것을 놓치지 않는 한) 다소 도전적입니다!

Answer 1

결정 론적으로 (어떤 임의의 숫자)이 작업을 수행하는 매우 일반적인 방법은 시그마 함께 : 예상 비율이 0.5이기 때문에, 각 시험 1 개의 예상 수는 여기에 (40)는 실증 분석 결과입니다입니다 - 델타 변조기.

0에서 시작하여 1에서 끝나는 부드럽게 증가하는 함수를 선택합니다. 그런 다음 변조 알고리즘을 사용하여 0과 1로 근사합니다.

NB : 시그마 - 델타 변조기는 아날로그 신호 (사운드, 비디오 등)를 1/0 비트 스트림으로 변환하는 전자 장치에서 매우 일반적으로 사용됩니다.

설명을 위해, 100주기에 걸쳐 0부터 1까지 램프를 사용하고 1 차 변환기를 사용합니다. 그러나 원하는 커브를 선택할 수 있습니다. 예를 들어, 수평으로 축척 된 hyperbolic tangent은 중간에서 더 빠른 변화와 함께 더 작은 시작 및 끝 기울기를 제공합니다. 그리고 2 차 변환기는 "더 좋은"패턴을 제공 할 수 있습니다. 그들은 조금 덜 규칙적인 경향이 있습니다.

아주 간단한 알고리즘입니다. 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; 
} 

여기서 알 수 있듯이 결정적입니다. 또한 매우 간단하고 빠릅니다 : trig 함수, 지수 등이 필요 없습니다. 따라서 하드웨어 구현에 적합합니다.

00000000000100000010000100010001001001001010100101 
01010110101011011011011101110111101111110111111111 

Here 시그마 - 델타 변환에 정액 종이이다

출력보기 쉽게 2 행으로 분할. 위의 프로그램의 변수는 그림 8과 같습니다. 그림 13은이를 시도하려는 경우 2 차 다이어그램을 보여줍니다.

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

Answer 2

이 작업을 수행하는 데는 여러 가지 가능성이 있으므로 원하는 배포본에 따라 다릅니다. 여기에 내가 당신의 목적을 위해 일한다고 생각합니다 아주 간단한 예는 다음과 같습니다

랜드 (0,1) 당신이 결과를 반올림해야 마지막에 0과 1 사이의 값을 생성

for (i=0; i<end; i++) 
    value = rand(0,1) * (2*i/end) * (2*(end-i)/end); 
    if(i>end/2) 
    value = 1 - value; 

.

편집 : 알고리즘의 빠른 구현을 수행하고 50 번 (끝 = 500)으로 시뮬레이션했습니다. 1과 0의 분포를 보여줍니다 (반올림하기 전).

Answer 3

0과 1을 완벽하게 설정하면 중간 결과를 나눌 수 있고 왼쪽 절반은 오른쪽 절반과 비교하여 1/3을가집니다 (즉, 왼쪽 절반은 1/4 모든 것들 중 오른쪽 절반은 3/4을 가지고있다). 그래서이 아이디어를 사용하여 비트를 생성 할 수 있습니다.

private static boolean[] res; 

public static boolean[] generate(int len) { 
    res = new boolean[len]; 
    generate(0, len, len/2); 
    return res; 
} 

private static void generate(int start, int len, int bits) { 
    if (bits == len) 
     for (int i = start; i < start + len; i++) 
      res[i] = true; 
    else if (bits > 0) { 
     int l1 = len/2, l2 = len - l1, b1 = (bits + 2)/4, b2 = bits - b1; 
     if (l2 < b2) { 
      b2 = l2; 
      b1 = bits - b2; 
     } 
     generate(start, l1, b1); 
     generate(start + l1, l2, b2); 
    } 
} 

출력 63, 64, 65 비트 :

000000100000001000100010001011100010001000111111111111111111111 
0000000100000001000100010001011100010001010111111111111111111111 
00000001000000010001000100010111000100010001111111111111111111111 

Answer 4

당신은 매우 다양한 응용에 이용되는 가우스 분포를 사용할 수있다.

나는 이런 종류의 응용이 쉽기 때문에 Matlab을 사용했지만 다른 언어로 쉽게 변환 할 수 있어야합니다.

그래서, 물어 보는 기준으로 20 개 값의 배열을 만들고 싶다고합시다.

len = 20; 
x = 1:len; 
y = normdist(x, len, len/5); % you can play with mean and standard deviation. 
plot(x,y) 

그런 다음 방정식에 임의성을 추가하고 당신이 원하는대로 임계 값을 추가합니다.

그리고 임계 값을 추가

rn = rand(1,len); 
res = y.*rn; 

, 평균 아래의 사람이 영을 말할 수 있습니다.

당신은 값으로 재생하고 당신이 필요로하는 값 세트를 얻을 수 있습니다. 매우 유연

Answer 5

한 가지 방법이 당신이 순서 사전의 길이를 알고 가정 1 0 대 발생의 가능성에 대한 logistic function을 사용하는 것입니다,하지만 ramp-의 비율 당신에게 많은 유연성을 제공 최대, 최소 및 최대 확률은 1입니다.(확률 적)

00000000011000001000001100001101001010000011001011001111000111011111101011111011 
10100000000000000000010000010111000000110110111011111000111011111111111110111111 

결과는 무작위입니다,하지만 당신은 할 수 있습니다 : 두 번 실행

# Creates an array of desired length whose values are symmetric 
# about the mid-point of the array, are bounded below and above 
# by min & max, and have a ramp up rate determined by steepness. 
def logistic_function(length, min, max, steepness) 
    mid = 0.5 * (length - 1) 
    range = max - min 
    # create, initialize elements via logistic fn, and return resulting array 
    Array.new(length) { |x| min + range/(1 + Math.exp(-steepness * (x - mid))) } 
end 

length = 80 
# 80 probabilities will vary from 0.1 to 0.9, with a relatively slow ramp-up 
probability = logistic_function(length, 0.1, 0.9, 0.1) 

# Create an array of bits where each entry's probability of being 1 
# is determined by the logistic function we generated 
bits = Array.new(length) { |i| rand <= probability[i] ? 1 : 0 } 
puts bits.join 

샘플 출력 : 당신은 언어를 지정하지 않았기 때문에

, 나는 루비에서이 프로토 타입 min, max 및 steepness을 통해 1의 밀도와 전환율을 제어하십시오.

로지스틱 함수의 대칭에 의해, 1 비트의 전체 비율은 예상 값 (min + max)/2임을 유의하십시오. 필자가 사용한 매개 변수화를 사용하면 0.5입니다. 이것을 설명하기 위해 나는 80 비트 세트에서 1의 수를 세었고, 10,000 번의 시도를 위해 생성/계산을 반복했다.