Алгоритм интерпретации однородной последовательности Бернулли как неоднородной

Question

У меня есть большая, равномерно распределенная последовательность двоичных цифр (P (1) = P (0)), и мне нужно интерпретировать эту последовательность случайных битов как последовательность двоичных цифр размером EQUAL , чьираспределение не является равномерным (т. е. P (1)! = P (0)).

В частности, я ищу одно из следующего:

1.) НЕОБХОДИМАЯ функция F, чья область равна его диапазону = множество двоичных битов Nпоследовательности (то есть функция, чья область = range = {0,1} ^ N для некоторого фиксированного N) AND со свойством, что функция отображает последовательности с высокой энтропией в последовательности с низкой энтропией и наобороткак нельзя лучше

Идеи?

Это для сжатия;Я опубликую больше об этом позже

Answer 1

Шеннон доказал, что невозможно сжать единую случайную двоичную строку.Алгоритмы сжатия используют неравномерность во входном распределении.

Answer 2

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

отредактируйте свой комментарий:

A = YourLargeSequence

f(0^N) = A
f(A) = 0^N
otherwise, f(x) = x

имеет все свойства, которые вы просили. Домен = Диапазон = {0,1} ^ N, он обратен сам по себе, 0 имеет низкую энтропию. Я предполагаю, что вы пропустили требование?