Зачем нужно избыточное кодирование?

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

Photo by form PxHere

Для формализации проблемы определим канал связи, в котором передаются исключительно нули и единицы и есть вероятность p ошибочных переходов "ноль - единица" и "единица - ноль". Если эта вероятность равна 50%, никакая избыточная информация не поможет, все сообщения будут портиться каналом. Если вероятность меньше 50%, избыточная информация поможет нам уменьшить вероятность ошибки.

Пусть в исходном сообщении вероятности появления обоих символов (ноль и единица) одинаковы и равны 50%. При добавлении избыточной информации будем разбивать исходное сообщение на части по n бит и добавлять после каждой такой части простую хэш-сумму: единицу, если количество единиц в предстоящей части нечетное и ноль в противном случае. Очевидно, что чем длиньше часть (больше n), тем меньше избыточной информации. Интересно исследовать зависимость результирующей ошибки от длины n частей, на которые разбивается сообщение. Если получатель определяет ошибку в хэш-сумме, он запрашивает испорченную часть сообщения заново. Для простоты можно ограничить максимально возможное количетство m повторных передач для каждой части. Если на некоторой повторной итерации i<m происходит успешная передача части сообщения, считаем, что ошибка не произошла.

Может, здесь читатель решит остановиться и рассмотреть задачу самостоятельно с любой степенью подробности, а ниже предлагается ее решение в самом простом случае, достаточном для старта:)

Photo by form PxHere

Рассмотрим сначала только случай примешивания хэш-суммы к каждому отдельному биту (n=1). Тогда каждое отдельное сообщение будет состоять из двух битов, первый - часть сообщения, а второй - хэш-сумма, равная первому биту. Есть три варианта при однократной передаче такой части сообщения:

1. оба бита передались без ошибки (вероятность такого исхода равна (1 - p)^2);
2. испортился один из битов (вероятность этого исхода равна p(1 - p) + (1-p)p) = 2p(1 - p);
3. испортились оба бита (вероятность равна p^2).

Сумма вероятностей всех четырех исходов должна быть равна единице, это условие выполняется:

(1 - p)^2 + 2p(1 - p) + p^2 = 1 - 2p + p^2 + 2p - 2p^2 + p^2 = 1.

Случай 3 непоправимый, если мы получили другое сообщение с другой хэш-суммой (11 вместо 00 или 00 вместо 11), получатель подумает, что сообщение верное, хотя оно ложное. Стоит отметить, что вероятность такого события довольно низкая в сравнении с исходной вероятностью ошибки при передаче одного бита информации (p^2 заметно меньше p в случае p заметно меньшем единицы).

Первый случай не требует коррекции и он соответствует правильной передаче части сообщения. Второй случай требует коррекции. Если коррекции не предусмотрены, вероятности от второго случая подпадают под вероятность ошибки. Другими словами, вероятность успешной передачи равна (1 - p)^2, а вероятность ошибки равна 2p(1 - p)+p^2. Первое слагаемое (2p(1 - p)) в вероятности ошибки можно корректировать и уменьшать, а второе слагаемое (p^2) неисправимо.

Предположим, что система передачи данных подразумевает однократную коррецию в случае необходимости. Тогда сообщение передается еще один раз и для него справедливы все рассуждения, приведенные выше. С вероятностью p^2 оно может полностью испортиться и с вероятностью (1 - p)^2 оно может передаться успешно. Промежуточный корректируемый случай возникнет с вероятностью 2p(1 - p).

В целом для процедуры с передачей с одной коррекцией получается такое распределение вероятностей:

успешная передача: (1 - p)^2 + 2p(1 - p)(1 - p)^2 = (1 + 2p(1 - p))(1 - p)^2;

корректируемая ошибка: 2p(1 - p)2p(1 - p) = (2p(1 - p))^2;

некорректируемая ошибка: p^2 + 2p(1 - p)p^2 = p^2(1 + 2p(1 - p)).

Можете поверить, а можете проверить:) сумма этих вероятностей тоже равна единице.

Если допустить две коррекции, вероятности перераспределятся следующим образом:

успешная передача: (1 - p)^2 + 2p(1 - p)(1 - p)^2 + (2p(1 - p))^2*(1 - p)^2;

корректируемая ошибка: (2p(1 - p))^3;

некорректируемая ошибка: p^2 + 2p(1 - p)p^2 + (2p(1 - p))^2*p^2.

Тут уже можно заметить закономерность, в случае m корректировок мы получим следующее распределение вероятностей:

успешная передача: (1 - p)^2 + ((2p*(1 - p))^1)*((1 - p)^2) + ((2p*(1 - p))^2)*((1 - p)^2) + ... + ((2p*(1 - p))^m)*((1 - p)^2);

корректируемая ошибка: (2p*(1 - p))^(m+1);

некорректируемая ошибка: p^2 + ((2p*(1 - p))^1)*(p^2) + ((2p*(1 - p))^2)*(p^2) + ... + ((2p*(1 - p))^m)*(p^2).

Эти выражения можно представить в виде суммы:

успешная передача:

\sum_{i=0}^m ((2p(1 - p))^i)(1 - p)^2

корректируемая ошибка:

(2p(1 - p))^{m+1}

некорректируемая ошибка:

\sum_{i=0}^m ((2p(1 - p))^m)p^2

В случае неограниченного количества корректировок (m стремится к бесконечности):

успешная передача:

\lim_{m\to \infty}\sum_{i=0}^m ((2p(1 - p))^i)(1 - p)^2

корректируемая ошибка:

\lim_{m\to \infty} (2p(1 - p))^{m+1}

некорректируемая ошибка:

\lim_{m\to \infty} \sum_{i=0}^m ((2p(1 - p))^m)p^2

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

Между первым и третьим пределом нам можно выбрать тот, выражение для которого проще (третий), потому что оставшийся (первый) можно будет найти вычитанием третьего из единицы.

Рассмотрим выражение под пределом для увеличивающихся значений m от нуля и дальше:

p^2

p^2 + 2p^3 - 2p^4

p^2 + 2p^3 + 2p^4 - 8p^5 + 4p^6

p^2 + 2p^3 + 2p^4 - 20p^6 + 24p^7 - 8p^8

p^2 + 2p^3 + 2p^4 - 4p^6 - 40p^7 + 88p^8 - 64p^9 + 16p^10

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 72p^8 + 256p^9 - 304p^10 + 160p^11 - 32p^12

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 8p^8 - 128p^9 + 656p^10 - 1120p^11 + 928p^12 - 384p^13 + 64p^14

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 8p^8 - 240p^10 + 1568p^11 - 3552p^12 + 4096p^13 - 2624p^14 + 896p^15 - 128p^16

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 8p^8 + 16p^10 - 480p^11 + 3616p^12 - 10240p^13 + 15296p^14 - 13440p^15 + 7040p^16 - 2048p^17 + 256p^18

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 8p^8 + 16p^10 + 32p^11 + 32p^12 - 2048p^13 + 18368p^14 - 71808p^15 + 157568p^16 - 217088p^17 + 196864p^18 - 118272p^19 + 45568p^20 - 10240p^21 + 1024p^22

p^2 + 2p^3 + 2p^4 - 4p^6 - 8p^7 - 8p^8 + 16p^10 + 32p^11 + 32p^12 - 4160p^14 + 40832p^15 - 180352p^16 + 458752p^17 - 749312p^18 + 827904p^19 - 630272p^20 + 327680p^21 - 111616p^22 + 22528p^23 - 2048p^24

ряд получается довольно замысловатым, но, заметив паттерн, можем представить его следующим образом: p^2 + 2^1(p^3 + p^4) - 2^2p^6 - 2^3(p^7 + p^8) + 2^4p^10 + 2^5(p^11 + p^12) - 2^6p^14 - 2^7(p^15 + p^16) + 2^8p^18 + 2^9(p^19-p^20) ...

Это вероятность ошибки при неограниченном количестве коррекций в случае передачи дополнительного бита на каждый бит информационного сообщения. Этот ряд скорее всего является сходимым при p<1, не так просто, правда, найти, к чему он сходится.

Если интересно продолжение решения задачи (можно рассмотреть дополнительный бит на каждые два бита, три бита, и т.д.), то пишите в комментариях об этом. В итоге все результаты можно было бы собрать в один и построить интересные зависимости от длины сообщения, на которое делается хэш-сумма. Также можно было бы рассмотреть обратный случай: добавление двух дополнительных битов на каждый бит, трех, четырех, и т.д.