바이어스 된 (예를 들어, 1은 알고있는 인자에 의해 0보다 공통적 인) 무작위 0과 1의 무한한 스트림이 주어 지지만 그렇지 않은 이상적인 난수 생성기에서는,이를 (더 짧은) 무한 스트림으로 변환하고 싶습니다. 이상적이기는하지만 편파적이기도합니다.임의의 데이터 스트림에서 값 분포를 조정하는 방법은 무엇입니까?
위의 그래프를 보면이 그래프에서 출력의 몇 비트가 이론상 입력의 각 비트에서 얻어야 하는지를 보여줍니다.
질문 : 실제로 거의 이상적으로 효율적인 변환기를 구현할 수있는 실질적인 방법이 있나요?
부당한 동전을 공정한 동전으로 바꾸는 것에 대한 Von Neumann의 유명한 장치가 있습니다. 이 장치를 사용하여 여기에서 문제를 해결할 수 있습니다.
비트가 다른 쌍을 얻을 때까지 바이어스 된 소스에서 2 비트를 반복하여 그립니다. 이제 첫 번째 비트를 반환하고 두 번째 비트는 무시합니다. 이것은 공평하지 않은 출처를 산출합니다. 그 이유는 소스에 관계없이 01의 확률이 10의 확률과 같기 때문입니다. 따라서 01 또는 10에 대한 조건부 확률은 1/2이고 1에 대한 조건부 확률은 01입니다. 또는 10은 1/2입니다.
또한 쌍이 겹치지 않아야합니다. –
그 효율성은 무엇입니까? 하나의 출력 비트를 생성하려면 몇 비트를 사용해야합니까? (그 외에도 간단하고 좋은 +1) – BCS
데이터 배포에 따라 다릅니다. 하나의 "0"비트가 산재 된 10000 "1"비트의 문자열을 얻으면 알고리즘은 단일 출력 비트를 생성합니다. –
호프만 입력를 인코딩 참조하십시오.
입력이 알려진 바이어스 인 경우 각 n 비트 세그먼트의 체크 합계에 대한 확률 분포를 계산할 수 있습니다. 해당 구성에서 Hoffman code 그리고 나서 단지 시퀀스를 인코딩하십시오.
하나의 잠재적 인 문제는 순차적 비트 사이에 약간의 상관 관계가 발생할 수 있다는 것입니다.
데이터를 "미백"이라고합니다. –