Пример коррекции ошибки на базе системы остаточных классов

Постановка задачи

В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Числовое значение строки представляется в модулярном базисе состоящем из 4-5-битных простых чисел (аналог 4-х битного блока в позиционных кодах). Необходимо отследить и исправить одиночную ошибку, внесённую в один из модулярных каналов.

Любой строке из 16 бит можно поставить в соответствие число из диапазона $[0...65536)$. Далее данное число мы представляем в системе остаточных классов (СОК) по выбранным нами модулям. Затем, внеся одиночную ошибку в любой модуль мы попробуем исправить её. Алгоритм исправления ошибки заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученного числа.

Теоретические основы алгоритма

Пусть имеется $k$ взаимно простых чисел $p_1,p_2,p_3,...,p_k$. Назовём их рабочими основаниями. Известно, что в СОК по данным модулям однозначно представляется число из рабочего диапазона $[0...p_1*p_2*...*p_k)$. Далее введём два дополнительных взаимно простых основания $p_{k+1},p_{k+2}$ таких, что все $k+2$ полученных оснований $p_1,p_2,p_3,...,p_k,p_{k+1},p_{k+2}$ будут взаимно простыми. Пусть наше исходное число $A$ принадлежит диапазону $[0...p_1*p_2*...*p_k)$. Если представить его в СОК по модулям $\left \{p_1,p_2,p_3,...,p_k,p_{k+1}\right \}$, затем внести ошибку по любому из модулей, а потом попытаться восстановить данное число по Китайской Теореме об Остатках, то известно, что результат $\bar A>p_1*p_2*...*p_k$. Таким образом, имея два контрольных основания мы можем исправлять одиночную ошибку, последовательно исключая по одному из модулей и получая ситуацию, описанную выше. Если мы исключили основание, по которому произошла ошибка, мы получим правильное число, лежащее в пределах диапазона $[0...p_1*p_2*...*p_k)$.

Пример

Пусть имеется 16ти-битная строка $1000001000110101$. Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.

Шаг 1 Для выполнения данной задачи выбираем 4 рабочих основания и 2 контрольных. Рабочие основания:$p_1=13, p_2=16, p_3=17, p_4=19$. Контрольные основания: $p_5=21, p_6=23$. При таком выборе рабочих оснований мы можем работать с числами из диапазона от $0$ до $13*16*17*19=67183 > 65536$. Таким образом, этих рабочих оснований хватит для работы с нашей исходной строкой. Выбор таких рабочих обусловлен тем, что полученный динамический диапазон практически совпадает с исходным $[0...65536)$. Изначально строка содержала 16 бит, но после кодирования (представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной $4+4+5+5+5+5=28$. Таким образом, избыточность составляет $28-16=12$ бит. Представим это число в СОК:

Шаг 2 Процесс кодирования и внесения ошибки: Переведем строку $1000001000110101$ в десятичную систему счисления и получим $33.333$

Представим это число в СОК по нашим модулям и получим: $33.333=(1, 5, 13, 7, 6, 6)$. Представим всё это в бинарном виде: $0001 0101 01101 00111 00110 00110$. Это и есть наша закодированная строка. Затем внесем ошибку по одному из оснований. Для данного примера я выбрал пятое основание, т.е. 21. В результате ошибки мы получим строку, с которой и будет работать декодер.

Шаг 3 Теперь рассмотрим процесс декодирования: На данном этапе мы хотим выяснить: произошла ли ошибка по какому-либо основанию и если произошла, то исправить эту ошибку. Рассмотрим строку, полученную в результате кодирования и внесения ошибки: $0001 0101 00011 00111 00101 00110$.

Представим число, соответствующее данной строке, в СОК по нашим модулям: $\bar A=(1, 5, 13, 7, 5, 6)$. Теперь отбрасываем последовательно по одному основанию и смотрим результат. Если он меньше 67183, то мы принимаем этот результат за исходное число, а по отброшенному основанию произошла ошибка. Пусть мы откидываем первое основание. Тогда по пяти оставшимся мы восстанавливаем число. Получаем систему сравнений: $\left\{ \begin{array}{rcl} x\equiv5 mod(16) \\ x\equiv13 mod(17) \\ x\equiv7 mod(19) \\ x\equiv5 mod(21) \\ x\equiv6 mod(23) \\ \end{array} \right.$

Согласно Китайской Теореме об Остатках данная система имеет одно единственное решение в диапазоне от $0$ до $16*17*19*21*23$

Решением данной системы является число $x=627653$. Видим, что число находится вне нашего диапазона, а следовательно по одному из неотброшенных оснований произошла ошибка, а по отброшенному основанию ошибки нет.

Теперь отбросим основание $p_2=16$. Проделывая те же действия, что и для первого основания получим, что $x=1095680$. Опять мы вышли за допустимый диапазон, а следовательно по второму основанию ошибки нет.

Отбрасывая третье основание $p_3=17$, получим $x= 1214981$.

Отбрасывая четвертое основание $p_4=19$, получим $x= 1415909$

Отбрасывая пятое основание $p_5=21$, получим $x = 33333$. Полученное число попадает в динамический диапазон, а следовательно, является нашим верным числом. Таким образом мы нашли и разряд, в котором произошла ошибка, а именно блок, отвечающий за остаток по модулю 21, ведь именно этот блок мы исключили на данном этапе восстановления.