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

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

В данной статье разбирается пример работы алгоритма коррекции ошибки в одном модулярном канале(аналог исправления ошибки в 4-х битном блоке). Пусть строка, состоящая из 16 бит. Необходимо отследить и исправить одиночную ошибку, внесённую в данную строку. Любой строке из 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$ бит.