Как настроить распределение значений в случайном потоке данных?

Question

Учитывая бесконечный поток случайных 0 и 1, который является из-за смещения (например, 1 более распространены, чем 0 из-за знающего фактора), но в остальном идеальный генератор случайных чисел, я хочу преобразовать его в (более короткий) бесконечный поток, который как идеальный, но и беспристрастный.

Поднимая definition of entropy, этот график показывает, сколько бит вывода я должен теоретически получить от каждого бита ввода.

Вопрос: Есть ли практический способ на самом деле реализовать преобразователь, который почти идеально эффективным?

Answer 1

Существует известное устройство благодаря Фон Нейману за то, что он превратил несправедливую монету в честную монету. Мы можем использовать это устройство для решения нашей проблемы.

Повторно нанесите два бита из вашего смещенного источника, пока не получите пару, для которой бит отличается. Теперь верните первый бит, отбросив второй. Это создает непредвзятый источник. Причина, по которой это работает, заключается в том, что независимо от источника вероятность 01 равна той же вероятности, что и вероятность 10. Поэтому вероятность условия 0 на 01 или 10 равна 1/2 и вероятность 1-го условия на 01 или 10 равно 1/2.

Answer 2

Пожалуйста, см

• http://en.wikipedia.org/wiki/Randomness_extractor

• http://en.wikipedia.org/wiki/Whitening_transform

• http://en.wikipedia.org/wiki/Decorrelation

Answer 3

Хоффман закодировать вход.

Учитывая, что входной сигнал имеет известное смещение, вы можете вычислить распределение вероятности для контрольных сумм каждого n битового сегмента. Из этой конструкции Hoffman code, а затем просто кодируйте последовательность.

Я не уверен, но одна потенциальная проблема заключается в том, что это может привести к некоторой корреляции между последовательными битами.