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

Question

Скажем, есть массив из 1024 битов, которые являются нулями:

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

Затем я перезаписываю 20 нулей на совершенно случайные позиции:

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

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

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

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

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

Answer 1

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

(расчет по Wolfram Alpha)

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

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

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

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

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

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