Алгоритм: минимальное кодирование, исправление ошибок, пожалуйста, помогите?

Question

Say есть массив из 1024 битов, все нули:

пример: [0,0,0,0,0,0,0, ...]

Тогда я перезаписать 20 нулей с них на совершенно случайных позициях:

Пример: [0,1,0,0,0,0,0, ...]

Что такое теоретическое минимальное количество битов, необходимых для кодирования местоположения этих 20 случайно размещенные биты, предполагая, что у меня есть идеальный кодер?

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

Более сложный вопрос: покажите мне код для алгоритма, который реализует кодировку, которая подходит к этому минимальному пределу.

Бонусный бонус: что, если бит переворачивается, где уровень байта вместо битового уровня? например целые байты перевернуты. Тот же результат?

Answer 1

Если вы обработали строку из 200 бит в виде массива из 20 десятибитовых чисел, каждый из которых перечисляет позицию одного из бит, вы должны сохранить 824 бит.

Но я не думаю, что это минимум. Например, если вы относитесь к каждому из чисел по сравнению с предыдущим, а не к абсолютной позиции, некоторый анализ может показать, что в среднем вам понадобится, например, 8 бит для кодирования расстояния до следующего одноразрядного. Итак, добавьте немного в начало: когда 0, то последуют 200 бит с абсолютными позициями. Когда 1, затем следуют 160 бит с относительными положениями. Это должно дать более низкое среднее количество бит для кодирования полного значения.

Обобщение, это просто сжатие данных. Вероятно, существует множество алгоритмов сжатия, которые могут уменьшить среднее число бит, необходимое для кодирования «двадцать один бит в 1024» до очень небольшого числа. Вычисление подходящего двоичного дерева, сохранение его представления, а затем сохранение битов, необходимых для прохождения дерева, вероятно, даст очень эффективный алгоритм (на самом деле это основа современного сжатия данных).

Answer 2

Если вы собираетесь использовать словарь на основе кодировки, где декодер также имеет словарь, абсолютного минимума нет. Для кодирования частот на основе, однако, что вам нужно, чтобы вычислить энтропию:

E = -(P(0) * log_2(P(0)) + P(1) * log_2(P(1))) 
E = -(1004/1024 * log_2(1004/1024) + 20/1024 * log_2(20/1024)) 
E = 0.1388005 

Таким образом, каждый бит на входе должен требовать 0.1388005 биты выходного сигнала в среднем. Всего:

0.1388005 * 1024 = 142.1317 bits. 

Это означает, что в теории, используя оптимальный алгоритм можно закодировать любую строку с 1004 нулями и 20 из них (или наоборот) с использованием 143 бит.

Answer 3

потолок (log2 (1024 выбрать 20)) = 139 бит

(calculation on Wolfram Alpha)

Другие ответы говорят 143 бит оставить, что мы знаем, что есть ровно 20 из них. Вот конкретная кодировка, чтобы показать один способ использования этих знаний: используя arithmetic coding, отправьте каждый из 1024 '0' или '1' символов подряд. Первый символ взвешивается с вероятностью 20/1024: «1»; но каждый последующий символ взвешивается по-разному.Если первый символ был «0», используйте 20/1023 на следующем; но если это «1», используйте 19/1023. Продолжайте так же до конца. Арифметическое кодирование делает всю сложную работу примерно в 139 бит, если мы скажем ей правильные вероятности.

На «бонус-бонус»: исправления ошибок не было в исходном вопросе. Вы можете сложить код с исправлением ошибок, прежде чем сначала найти оптимальное кодирование, не допуская ошибок, как указано выше (и это обычно хороший способ разбить проблему). Вы не теряете никакой эффективности кодирования таким образом, хотя я думаю, что вы можете потерять надежность - как в случае, если вы получите больше ошибок, чем может исправить ваш ECC, выйдет ли сообщение как полный мусор или будет ухудшаться изящно?