Вероятность ошибки на символ

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

Соотношение
между вероятностями ошибки декодирования
слова и ошибки на бит определяется
структурой порождающей матрицы
конкретного кода. Однако для обобщенного
анализа могут быть получены простые
границы для вероятности ошибки на бит.
Пусть длительность сеанса связи
составляет 1с. Тогда за сеанс связи может
быть передано 1/T_W
кодовых слов, которые содержат k/T_W
информационных символов. Количество
ошибочно принятых кодовых слов равно
P_Wk/T_W.
Если через k₀
обозначить количество ошибочно
принятых информационных символов при
каждом ошибочно принятом кодовом слове,
то вероятность ошибки на бит будет равна

. (3.19)

Проблема
заключается в определении величины k₀.
В наихудшем случае ошибочный прием
кодового слова сопровождается ошибочным
приемом всех k
информационных символов. Тогда
получаем верхнюю границу

. (3.20)

Рис.3.2.
Характеристики помехоустойчивости
блоковых кодов: 1 – без кодирования; 2 –
код Хэмминга (7, 4); 3 – код Хэмминга
(15, 11); 4 – код Хэмминга (31, 26); 5 – код
Голея (24, 12); 6 – код БЧХ (127, 64)

В
лучшем случае ошибочный прием кодового
слова приводит к единственной ошибке
в информационных символах. Поэтому для
нижней границы имеем k₀=1
и

. (3.21)

Для
малых значений k
верхняя и нижняя границы становятся
строгими, и для оценки вероятности
ошибки на бит может быть использована
вероятность ошибочного приема слова.
Для высоких значений E_b/N₀
вероятность ошибки на символ оказывается
чрезвычайно малой и ошибки при
декодировании кодовых слов с большой
вероятностью возникают при появлении
(t+1) ошибочных символов.
Из этих (t+1) ошибочных
символов в среднем (t+1)/n
относится к информационным. В результате

, (3.22)

. (3.23)

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

3.5. Сверточные коды

Сверточные
(или рекуррентные) коды отличаются от
блоковых кодов структурой. В блоковом
коде n символов кода, формируемых
кодером в любой выбранный интервал
времени, зависят только от k
информационных символов, поступивших
на его вход в течение этого же интервала
времени. В сверточном коде блок из n
символов кода, формируемых кодером
в любой выбранный интервал времени,
зависит не только от k
информационных символов, поступивших
на его вход в течение этого же интервала
времени, но и от информационных символов,
поступивших в течение (K–1)
предыдущих интервалов. Параметр K
называется длиной кодового
ограничения. Для сверточных кодов
значение параметров n и k
выбираются малыми. Сверточные коды
могут использоваться для исправления
случайных ошибок, ошибок, группирующихся
в пакеты, и для тех и других. Кодер
двоичного сверточиого кода содержит
kK-разрядный регистр
и n сумматоров по mod
2. Обобщенная структурная схема кодера
сверточного кода приведена на рис.3.3.

Рис.
3.3. Обобщенная структурная схема
кодера сверточного кода

На
рис. 3.4 приведены пример кодера сверточного
кода с параметрами k =1,
n = 2,
K = 3,
R_k = 1/2.
Информационные символы поступают на
вход регистра, а символы кода формируются
на выходе коммутатора. Коммутатор (КМ)
последовательно опрашивает выходы
сумматоров по mod 2 в течение
интервала времени, равного длительности
информационного символа (бита).

Схема
подключения сумматоров по mod
2, значения k, n и K
полностью описывают сверточный код. Их
можно определить с помощью генераторных
векторов или многочленов. Например,
сверточный код, формируемый кодером,
изображенным на рис.3.4,

Рис.
3.4. Структурная
схема кодера несистематического
сверточного кода со скоростью 1/2

Информационные
символы имеет порождающие векторы
g₁ = 111
и g₂ = 101
и порождающие многочлены g₁(х) = х²+х+1
и g₂(х)=х²+1.
Кроме того, сверточный код может быть
задан импульсной характеристикой,
определяемой как последовательность
символов кода на выходе кодера при
подаче на его вход единственного символа
1. Легко проверить, что импульсная
характеристика данного кода равна
111011. Так как операция сложения по mod
2 является линейной операцией, то
сверточные коды относятся к классу
линейных, и выходная последовательность
кодера может рассматриваться как
результат свертки входной последовательности
с импульсной характеристикой кодера.
Отсюда и происходит название кода и
метода кодирования.

Процедуры
кодирования и декодирования удобно
описывать с помощью так называемого
кодового дерева, которое отображает
последовательности на выходе кодера
для любой возможной входной
последовательности. На рис. 3.5 приведено
кодовое дерево кодера, изображенного
на рис. 3.4, для блока из пяти информационных
символов. Если первый символ принимает
значение 0, то на выходе кодера формируется
пара символов 00. Если первый символ
принимает значение 1, то на выходе кодера
формируется пара символов 11. Это показано
с помощью двух ветвей, которые выходят
из начального узла. Верхняя ветвь
соответствует 0, нижняя – 1. В каждом из
последующих узлов ветвление происходит
аналогичным образом: из каждого узла
исходит две ветви, причем верхняя ветвь
соответствует 0, а нижняя – 1. Ветвление
будет происходить вплоть до последнего
символа входного блока. Вслед за ним
все входные символы принимают значение
0, и образуется только одна обрывающаяся
ветвь. Таким образом, каждой из возможных
входных комбинаций информационных
символов соответствует своя вершина
на кодовом дереве. В данном случае
имеется 32 вершины. С помощью кодового
дерева легко построить выходную
последовательность символов кода,
соответствующую определенной входной
последовательности. Например, входной
последовательности 11010 соответствует
выходная последовательность, лежащая
на пути, изображенном пунктирной линией.

Рис.3.5.
Кодовое дерево для кодера, изображенного
на рис. 3.4

Анализируя
структуру кодового дерева на рис. 3.5,
можно заметить, что, начиная с узлов
третьего уровня, она носит повторяющийся
характер. Действительно, группа ветвей,
заключенных в прямоугольники, изображенные
пунктирными линиями, полностью совпадают.
Это означает, что при поступлении на
вход четвертого символа выходной символ
кода будет одним и тем же, независимо
от того, каким был первый входной символ:
0 или 1. Другими словами, после первых
трех групп выходных символов кода
входные последовательности 1x₁x₂x₃x₄…
и 0x₁x₂x₃x₄…
будут порождать один и тот же выходной
символ.

Обозначим
четыре узла третьего уровня, т.е. узлы,
в которых происходит третье ветвление,
буквами a,b,c,d.
Повторяющаяся структура ветвей имеет
место и для узлов четвертого и пятого
уровней, поэтому их также можно обозначить
этими же буквами. Для узлов пятого уровня
любой из четырех комбинаций (11,10,01, 00)
первых двух входных символов будет
соответствовать один и тот же выходной
символ.

Такое
поведение можно объяснить следующим
образом. Когда входной символ поступает
в регистр (входной разряд R₁),
то выходные символы зависят не только
от символа, записанного в R₁,
но и от двух предыдущих символов,
хранящихся в R₂
и R₃.
Имеется четыре возможные комбинации
символов, хранящихся в R₂
и R₃:
00, 01, 10, 11. Обозначим эти четыре комбинации
или состояния регистра сдвига
соответственно буквами a,
b, c,
d как показано на
рис. 3.5. Количество состояний равно 2^K–1.

Входные
символы 0 и 1 будут формировать четыре
различные комбинации выходных символов
в зависимости от состояния кодера. Если
входной символ 0, то на выходе декодера
будут формироваться 00, 10, 11 или 01 в
зависимости от того, в каком состоянии
находился кодер: a, b,
c или d.
To же самое правило можно
применить относительно символа 1.

Таким
образом, поведение кодера можно полностью
описать с помощью диаграммы состояний,
изображенной на рис. 3.6, а или
направленного графа с четырьмя состояниями
(рис. 3.6, б) который устанавливает
однозначное соответствие между входными
и выходными символами кодера. На графе
сплошные линии соответствуют входному
символу 0, а пунктирные – символу 1.
Например, если кодер находится в состоянии
а и на вход поступает 1, то на выходе
декодера будет формироваться комбинация
11 (пунктирная линия) и декодер перейдет
в состояние b,
соответствующее R₃ = 0
и R₂ = 1
– Аналогичным образом при поступлении
0 декодер останется в состоянии а
(сплошная линия) и на выходе будет
формироваться комбинация 00.

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

Рис.
3.6. Диаграмма состояний для кодера,
изображенного на рис. 3.4

Другим
полезным способом описания кодового
дерева является решетчатая диаграмма,
изображенная на рис. 3.7. Диаграмма берет
начало из состояния а и на ней
отображаются все возможные переходы
при поступлении на вход очередного
символа. Сплошным линиям соответствуют
переходы, происходящие при поступлении
символа 1 пунктирным – символа 0. При
поступлении на вход двух символов кодер
оказывается в одном из четырех состояний:
a, b,
c или d.
Заметим, что решетчатая диаграмма имеет
повторяющийся характер и может быть
легко построена с помощью диаграммы
состояний.

Рис.
3.7. Решетчатая диаграмма для кодера,
изображенного на рис.3.4

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #

  26.02.2016541.64 Кб17Сертификат Реконструкция жизни.PDF

• #
• #
• #
• #
• #
• #

Кодирование Рида-Соломона для чайников

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

Что может этот код?

Итак, что из себя представляет избыточный код Рида-Соломона с практической точки зрения? Допустим, есть у нас сообщение – «DON’T PANIC». Если добавить к нему несколько избыточных байт, допустим 6 штук: «rrrrrrDON’T PANIC» (каждый r – это рассчитанный по алгоритму байт), а затем передать через какую-нибудь среду с помехами, или сохранить там, где данные могут понемногу портиться, то по окончании передачи или хранения у нас может остаться такое, например: «rrrrrrDON’AAAAAAA» (6 байт оказались с ошибкой). Если мы знаем номера байтов, где вместо букв, которые были при создании кода, вдруг оказались какие-нибудь «A», то мы можем полностью восстановить сообщение в исходное «rrrrrrDON’T PANIC». После этого можно для красоты убрать избыточные символы. Теперь текст можно печатать на обложку.

Вообще, избыточных символов к сообщению мы можем добавить сколько угодно. Количество избыточных символов равно количеству исправляемых ошибок (это верно лишь в том случае, когда нам известны номера позиций ошибок). Как правило, ошибки, положение которых известно, называют erasures. Благозвучного перевода найти не могу («стирание» мне не кажется благозвучным), так что в дальнейшем я буду применять термин «опечатки» и ставить его в кавычки (прекрасно понимаю, что этот термин обычно несёт похожий, но другой смысл). Исправление «опечаток» полезно, например, при восстановлении блоков QR кода, которые по какой-либо причине не удалось прочитать.

Также код Рида-Соломона позволяет исправлять ошибки, положение которых неизвестно, но тогда на каждую одну исправляемую ошибку должно приходиться 2 избыточных символа. «rrrrrrDON’T PANIC», принятые как «rrrrrrDO___ PANIC» легко будут исправлены без дополнительной информации. Неправильно принятый байт, положение которого неизвестно, в дальнейшем я буду называть «ошибкой» и тоже брать в кавычки.

Можно комбинировать исправление «ошибок» и «опечаток». Если, например, есть 3 избыточных символа, то можно исправить одну «ошибку» и одну «опечатку». Ещё раз обращу внимание на то, что чтобы исправить «опечатку», нужно каким-то образом (не связанным с алгоритмом Рида-Соломона) узнать номер байта «опечатки». Что важно, и «ошибки» и «опечатки» могут быть исправлены алгоритмом и в избыточных байтах тоже.

Стоит отметить, что если количество переданных и принятых байт отличается, то здесь код Рида-Соломона практически бессилен. То есть, если на расшифровку попадёт такое: «rrrrrrDO’AIC», то ничего сделать не получится, если, конечно, неизвестно какие позиции у пропавших букв.

Как закодировать сообщение?

Здесь уже не обойтись без понимания арифметики с полиномами в полях Галуа. Ранее мы научились представлять сообщения в виде полиномов и проводить операции сложения, умножения и деления над ними. Уже этого почти достаточно, чтобы создать код Рида-Соломона из сообщения. Единственно, для того, чтобы это сделать понадобится ещё полином-генератор. Это результат такого произведения:

Где – это примитивный член поля (как правило, выбирают 2), а – это количество избыточных символов. То есть, прежде чем создавать код Рида-Соломона из сообщения, нужно определиться с количеством избыточных символов, которое мы считаем достаточным, затем перемножить биномы вида в количестве штук по правилам перемножения полиномов. Для любого сообщения можно использовать один и тот же полином-генератор, и любое сообщение в таком случае будет закодировано с одним и тем же количеством избыточных символов.

Пример: Мы решили использовать 4 избыточных символа, тогда нужно составить такое выражение:

Так как мы работаем с полем Галуа с характеристикой 2, то вместо минуса можно смело писать плюс, не боясь никаких последствий. Жаль, что это не работает с количеством денег после похода в магазин. Итак, возводим в степень, и перемножаем (по правилам поля Галуа GF[256], порождающий полином 285):

Необязательное дополнение

Легко заметить (правда легко – надо лишь взглянуть на произведение биномов), что корнями получившегося полинома будут как раз степени примитивного члена: 2, 4, 8, 16. Что самое интересное, если взять какой-нибудь другой полином, умножить его на (4 – в данном случае это количество избыточных символов), получится тот же самый полином, только с нулями в коэффициентах перед первыми 4 младшими степенями, а затем разделить его на полином-генератор, и прибавить остаток от деления к нашему полиному с 4 нулями, то его корнями также будут эти 4 числа (2, 4, 8, 16).

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

Прежде чем приводить пример кодирования, нужно договориться об обозначениях. Полиномы, записанные «по-математически» с иксами и степенями выглядят довольно-таки громоздко. На самом деле, при написании программы достаточно знать коэффициенты полинома, а степени можно узнать из положения этих коэффициентов. Таким образом полученный в примере выше полином-генератор можно записать так: {116, 231, 216, 30, 1}. Также, для ещё большей компактности, можно опустить скобки и запятые и записать всё в шестнадцатеричном представлении: 74 E7 D8 1E 01. Выходит в 2 раза короче. Надо отметить, что если в «математической» записи мы не пишем члены, коэффициенты которых равны нулю, то при принятой здесь шестнадцатеричной записи они обязательны, и, например, нужно записывать так: или 00 00 00 00 0A. Там, где «математическая» запись позволит более понятно объяснить суть, я буду прибегать к ней.

Итак, чтобы представить сообщение «DON’T PANIC» в полиномиальной форме, с учётом соглашения выше достаточно просто записать его байты:

44 4F 4E 27 54 20 50 41 4E 49 43.

Чтобы создать код Рида-Соломона с 4 избыточными символами, сдвигаем полином вправо на 4 позиции (что эквивалентно умножению его на ):

00 00 00 00 44 4F 4E 27 54 20 50 41 4E 49 43

Теперь делим полученный полином на полином-генератор (74 E7 D8 1E 01), берём остаток от деления (DB 22 58 5C) и записываем вместо нулей к полиному, который мы делили. (это эквивалентно операции сложения):

DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 43

Вот эта строка как раз и будет кодом Рида-Соломона для сообщения «DON’T PANIC» с 4 избыточными символами.

Некоторые пояснения

Как раскодировать сообщение?

Здесь всё посложнее будет. Ненамного, но всё же. Вопрос про раскодировать, собственно «не вопрос!» – убираем избыточные символы и остаётся исходное сообщение. Вопрос в том, как узнать, были ли ошибки при передаче, и если были, то как их исправить.

В первую очередь нужно отметить, что при проверке на наличие ошибок нужно знать количество избыточных символов. А во-вторую – надо научиться считать значение полинома при определённом . Про количество избыточных символов нам должен заранее сообщить тот, кто кодировал сообщение, а вот чтобы вычислить значение полинома нужно написать ещё одну функцию для работы с полиномами. Это элементарщина – просто вместо подставляется нужное значение. Но пример, всё же, никогда не помешает.

Пример: Нужно вычислить полиномпри . Подставляем, возводим в степень: , перемножаем, , складываем и получаем число . Сложение, умножение и возведение в степень здесь по правилам поля Галуа GF[256] (порождающий полином 285)

Код приводить не буду, оставлю ссылку на гитхаб. Там всё что я описывал в этой и предыдущих статьях реализовано на C#, в виде демо-приложения (собирается под win в VS2019, бинарник тоже выложен). Можно посмотреть как работает арифметика в поле Галуа, а также посмотреть, как работает кодирование Рида-Соломона.

Итак, прежде чем исправлять «ошибки» или «опечатки» нужно узнать есть ли они. Элементарно. Нужно вычислить полином принятого сообщения с избыточными символами при равном степеням примитивного члена. Это те же числа, которые мы использовали при составлении полинома-генератора: , – количество избыточных символов, – примитивный член. Если ошибок нет, то все вычисленные значения будут равны нулю. Закодированное ранее сообщение «DON’T PANIC» с 4 избыточными символами, в виде полинома в шестнадцатеричном представлении:

DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 43,

если вычислить этот полином при равном 2, 4, 8, 16, то получатся значения: 0, 0, 0, 0, ведь здесь сообщение точно в таком же виде, в котором оно и было закодировано. Если изменить хотя бы один байт, например, последний символ сделаем более правильным: 42 вместо 43:

DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 42,

то результат такого же вычисления станет равным 13, 18, B5, 5D. Эти значения называются синдромами. Их тоже можно принять за полином. Тогда это будет полином синдромов.

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

Важное, но совсем занудное дополнение

Что же делать, если синдром не равен нулю? Конечно же исправлять ошибки! Для начала рассмотрим случай с «опечатками», когда мы точно знаем номера позиций некорректно принятых байт. Ошибёмся намеренно в нашем закодированном сообщении 4 раза, столько же, сколько у нас избыточных символов:

DB 22 58 5C 44 4F 4E 27 54 20 41 41 41 41 41

41 – это буква A, поэтому их 5 подряд получилось. Позиции ошибок считаются слева направо, начиная с 0. Для удобства используем шестнадцатеричную систему при нумерации:

00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E
DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 43
DB 22 58 5C 44 4F 4E 27 54 20 41 41 41 41 41

Позиции ошибок: 0A 0C 0D 0E.

Итак, если мы находимся на стороне приёмника, то у нас есть следующая информация:

• Сообщение с 4 избыточными символами;

• само сообщение: DB 22 58 5C 44 4F 4E 27 54 20 41 41 41 41 41;

• В сообщении есть ошибки в позициях 0A 0C 0D 0E.

Этого достаточно, чтобы восстановить сообщение в исходное состояние. Но обо всём по порядку.

Для продолжения необходимо разучить ещё одну операцию с полиномами в полях Галуа — взятие формальной производной от полинома. Формальная производная полинома в поле Галуа похожа на обычную производную. Формальной она называется потому, что в полях вроде GF[256] нет дробных чисел, и соответственно нельзя определить производную, как отношение бесконечно малых величин. Вычисляется похоже на обычную производную, но с особенностями. Если при обычном дифференцировании , то для формальной производной в поле Галуа с основанием 2, формула для дифференцирования члена такая: . Это значит, что достаточно просто переписать полином, начиная с первой степени (нулевая выкидывается) и у оставшегося убрать (обнулить, извиняюсь) члены с нечётными степенями. Пример:

Необходимо найти производную

(Это рандомный полином, не связан с примером). Производная суммы равна сумме производных, соответственно применяем формулу для производной члена и получаем:

Или, если записывать в шестнадцатеричном виде, то это же самое выглядит так:

(01 2D A5 C6 8C DF )’ = 2D 00 C6 00 DF .

Думаю, что из примера в шестнадцатеричном виде проще всего составить алгоритм нахождения формальной производной.

Теперь можно уже исправить «опечатки»? Как бы не так! Нужно ещё два полинома. Полином-локатор и полином ошибок.

Полином-локатор – это полином, корнями которого являются числа обратные примитивному члену в степени позиции ошибки. Сложно? Можно проще. Полином-локатор это произведение вида

где – это примитивный член, и так далее – это позиции ошибок.

Пример: у нас есть позиции ошибок 10, 12, 13, 14; примитивный член тогда полином локатор будет таким:

Перемножаем и получаем полином-локатор для позиций ошибок 10, 12, 13, 14:

Или в шестнадцатеричной записи: 01 2D A5 C6 8C.

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

Полином ошибок – его по-разному называют в разных статьях, он не так уж и сложен. Представляет из себя произведение полинома синдромов и полином-локатора, с отброшенными старшими степенями. Продолжая пример, найдём полином ошибок для искажённого сообщения:

DB 22 58 5C 44 4F 4E 27 54 20 41 41 41 41 41

Полином синдромов: 72 BD 22 5B

Произведение полинома синдромов и полинома-локатора не буду расписывать в «математическом» виде, напишу так:

(72 BD 22 5B)(01 2D A5 C6 8C) = 72 4B 10 22 D9 C0 57 15

У результата оставляем количество младших членов, равное количеству избыточных символов, в нашем случае их 4, старшие степени просто выбрасываем, они не нужны. Остаётся

72 4B 10 22

Это и есть полином ошибок.

Осталось посчитать амплитуды ошибок. Звучит угрожающе, но на деле это просто значения, которые нужно прибавить к искажённым символам сообщения чтобы получились неискажённые символы. Для этого воспользуемся алгоритмом Форни. Здесь придётся привести фрагмент кода, словами расписать так, чтобы было понятно, очень сложно.

Функция принимает на входе

• полином синдромов (Syndromes),

• полином, в котором члены – позиции ошибок (ErrPos),

• количество избыточных символов (NumOfErCorrSymbs).

Класс GF_Byte — это просто байт, для которого переопределены арифметические операции так, чтобы они выполнялись по правилам поля Галуа GF[256], класс GF_Poly – Это полином в поле Галуа. По сути, массив GF_Byte. Для него также переопределны арифметические операции так, чтобы они выполнялись по правилам арифметики с полиномами в полях Галуа.

public static GF_Poly FindMagnitudesFromErrPos(
   GF_Poly Syndromes,
   GF_Poly ErrPos,
   uint NumOfErCorrSymbs)
{
 	//Вычисление локатора из позиций ошибок
	GF_Poly Locator = CalcLocatorPoly(ErrPos);
	//Произведение для вычисления полинома ошибок
	GF_Poly Product = Syndromes * Locator;
	//Полином ошибок. DiscardHiDeg оставляет указаное количество младших степеней
	GF_Poly ErrPoly = Product.DiscardHiDeg(NumOfErCorrSymbs);
	//Производная локатора
	GF_Poly LocatorDer = Locator.FormalDerivative();
	//Здесь будут амплитуды ошибок. Количество членов - это самая большая позиция ошибки
	GF_Poly Magnitudes = new GF_Poly(ErrPos.GetMaxCoef());

	//Перебор каждой заданной позиции ошибки
	for (uint i = 0; i < ErrPos.Len; i++) {
		//число обратное примитивному члену в степени позиции ошибки
		GF_Byte Xi = 1 / GF_Byte.Pow_a(ErrPos[i]);
		//значение полинома ошибок при x = Xi
		GF_Byte W = ErrPoly.Eval(Xi);
		//значение производной локатора при x = Xi
		GF_Byte L = LocatorDer.Eval(Xi);
		//Это как раз и будет найденное значение ошибки,
		//которое надо вычесть из ошибочного символа, чтобы он стал не ошибочным
		GF_Byte Magnitude = W / L;
		//запоминаем найденную амплитуду в текущей позиции ошибки
		Magnitudes[ErrPos[i]] = Magnitude;
	}            
	return Magnitudes;
}

Если скормить функции следующие параметры:

• полином синдромов 72 BD 22 5B

• полином, в котором члены — позиции ошибок 0A 0C 0D 0E

• количество символов коррекции ошибок 4,

то на выходе она даст полином амплитуд ошибок:

00 00 00 00 00 00 00 00 00 00 11 00 0F 08 02.

Теперь можно прибавить полученное к искажённому сообщению

DB 22 58 5C 44 4F 4E 27 54 20 41 41 41 41 41

(по правилам сложения полиномов, конечно же), и на выходе получится исходное сообщение:

DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 43.

Первые 4 байта — это избыточные символы. Если бы в них оказались «опечатки», то разницы никакой для алгоритма нет, разве что они нам не нужны после исправления. Можно их просто отбросить:

44 4F 4E 27 54 20 50 41 4E 49 43 Это исходное сообщение «DON’T PANIC».

Здесь должно быть понятно, как исправлять ошибки, положение которых известно. Само по себе уже это может нести практическую пользу. В QR кодах на обшарпанных стенах могут стереться некоторые квадратики, и программа, которая их расшифровывает сможет определить в каких именно местах находятся байты, которые не удалось прочитать, которые «стёрлись» – erasures, или как мы договорились писать по-русски «опечатки». Но нам этого, конечно же недостаточно. Мы хотим уметь выявлять испорченные байты без дополнительной информации, чтобы передавать их по радио, или по лазерному лучу, или записывать на диски (кого я обманываю? CD давно мертвы), может быть, захотим реализовать передачу через ультразвук под водой, чтобы управлять моделью подводной лодки, а какие-нибудь неблагодарные дельфины будут портить случайные данные своими песнями. Для всего этого нам понадобится уметь выявлять, в каких именно байтах при передаче попортились биты.

Как найти позиции ошибок?

Вспомним про полином-локатор. Его можно составить из заранее известных позиций ошибок, а ещё его можно вычислить из полинома-синдромов и количества избыточных символов. Есть не один алгоритм, который позволяет это сделать. Здесь будет алгоритм алгоритм Берлекэмпа-Мэсси. Если хочется много математики, то гугл с википедией на неё не скупятся. Я, если честно, не вник до конца в циклические полиномы и прочее-прочее-прочее. Стыдно, немножко, конечно, но я взял реализацию этого алгоритма с сайта Wikiversity переписал его на C#, и постарался сделать его более доходчивым и читаемым:

public static GF_Poly CalcLocatorPoly(GF_Poly Syndromes, uint NumOfErCorrSymbs) {
	//Алгоритм Берлекэмпа-Мэсси
	GF_Poly Locator;
	GF_Poly Locator_old;
	
	//Присваиваем локатору инициализирующее значение (1*X^0)
	Locator = new GF_Poly(new byte[] { 1 });
	Locator_old = new GF_Poly(Locator);

	uint Synd_Shift = 0;

	for (uint i = 0; i < NumOfErCorrSymbs; i++) {
		uint K = i + Synd_Shift;
		GF_Byte Delta = Syndromes[K];

		for (uint j = 1; j < Locator.Len; j++) {
			Delta += Locator[j] * Syndromes[K - j];
		}
		//Умножение полинома на икс (эквивалентно сдвигу вправо на 1 байт)
		Locator_old = Locator_old.MultiplyByXPower(1);
		if (Delta.val != 0) {
			if (Locator_old.Len > Locator.Len) {
				GF_Poly Locator_new = Locator_old.Scale(Delta);
				Locator_old = Locator.Scale(Delta.Inverse());
				Locator = Locator_new;
			}
			//Scale – умножение на константу. Можно было бы
			//вместо использования Scale 
			//умножить на полином нулевой степени. Разницы нет, но так короче:
			Locator += Locator_old.Scale(Delta);
		}
	}
	return Locator;
}

Пояснения по коду

Класс GF_Poly по сути – обёртка над массивом GF_Byte. Есть ещё одна особенность. Свойство Lenght любого массива — возвращает количество его элементов независимо от значений элементов. Здесь Len — возвращает количество членов полинома. Массив может быть любой длины, но если начиная с какого-то номера все элементы равны нулю, то старшая степень полинома — это последний ненулевой элемент.

Приведённый алгоритм считает локатор. Если количество «ошибок» больше, чем количество избыточных символов, поделённое на 2, то алгоритм не сработает правильно.

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

DB 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 43,

ошибиться в нулевом и последнем символе (2 «ошибки», мы притворяемся, что не знаем в каких позициях ошиблись), получится такой полином:

02 22 58 5C 44 4F 4E 27 54 20 50 41 4E 49 01,

Полином синдромов для него 4B A7 E8 BD. Если выполнить функцию, приведённую выше с параметрами 4B A7 E8 BD, и 4 (количество избыточных символов), то она вернёт нам такой полином: 01 12 13. Это не похоже на позиции ошибок, которые мы ожидаем, но полином-локатор содержит в себе информацию о позициях ошибок, ведь это «полином, корнями которого являются числа обратные примитивному члену в степени позиции ошибки». Из этого, если немного поскрипеть мозгами или ручкой по бумаге следует, что позиция ошибки – это логарифм числа по основанию примитивного члена, обратного корню полинома.

E – позиция ошибки, a – примитивный член (2, как правило), R – корень полинома.

Что-ж, будем искать корни в поле. Поиск корней полинома в поле Галуа занятие лёгкое и непыльное. В GF[256] может быть 256 чисел всего, так что иксу негде разгуляться. Просто считаем полином 256 раз, подставляя вместо x число, и если полином посчитался как нуль, то записываем к массиву с корнями текущее значение x. Дальше считаем по формуле и получаем позиции ошибок 00 и 0E, именно там где они и были допущены. Теперь эти значения вместе с синдромами и цифрой 4 можно скармливать алгоритму Форни, чтобы он исправил «ошибки» также, как он исправлял «опечатки».

Ещё пара пояснений

Если у нас есть 4 избыточных символа, при этом мы знаем что есть 2 «опечатки» в известных позициях, то алгоритм Берлекэмпа-Мэсси сможет найти ещё одну «ошибку». Но для этого его нужно будет совсем немного модифицировать. Всего то надо там где мы писали

	//Присваиваем локатору инициализирующее значение (1*X^0)
	Locator = new GF_Poly(new byte[] { 1 });

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

Надеюсь материал в этой статье поможет тем, кто захочет в каком-нибудь своём проекте реализовать избыточное кодирование без сторонних библиотек. Просьба: Если что-то не понятно, не стесняйтесь комментировать. Постараюсь ответить на вопросы, или внести правки в статью.