Схема коррекции ошибок Rajendra S. Katti

Введение

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

Пусть избыточная СОК определяется следующими модулями $m_1 = 3, m_2 = 4, m_3 = 5, m_4 = 7$, а динамический диапазон определяется $m_1$ и $m_2$ и соответственно равен $\{0,...,11\}$, а модули $m_3, m_4$ являются дополнительными и необходимы для проверки на ошибки.

Натуральное число из динамического диапазона может быть восстановлено по любым трём из четырёх остатков по представленным модулям. Например, число $x=5=(2,1,0,2)$ может быть представлено как $(2,1,0)$ в системе модулей $\{m_1, m_2, m_3\}$ или $(2,0,2), (1,0,2)$ в системах $\{m_1, m_3, m_4\}$ и $\{m_2, m_3, m_4\}$ соответственно. Поэтому, если одна цифра отбрасывается в представлении $(2,1,0,2)$, правильный результат восстановления будет получен тогда и только тогда, когда отбрасываемая цифра ошибочна. Таким образом, обнаружение ошибок и коррекция выполняется следующим образом:

1. Если число лежит вне динамического диапазона - произошла ошибка.
2. Остатки отбрасываются по одному и если в результате одного из отбрасываний полученное число лежит в динамическом диапазоне, то отброшенный остаток является ошибочным.
3. Корректное значение остатка получается расширением полученного на шаге 2 множества модулей, остатки по которым не содержат ошибок.

Такой подход требует много времени и вычислительных ресурсов. Ниже будет предложена новая схема обнаружения и коррекции ошибок на основе СОК.

Модули, имеющие общие делители

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

$|r_i|_k = |r_j|_k$,

выполняется для любых $i, j$, где $k = gcd(r_i, r_j)$. Таким образом, ошибочный разряд может быть найден выполнением только простой операции вычисления остатка.

Приведём пример, демонстрирующий, как можно проверить набор остатков на наличие ошибок. Проверим набор $(2, 6, 30, 42)$ в системе модулей $\{4, 15, 36, 48\}$. Наибольшие общие делители всевозможных пар модулей соответственно равны: $gcd(4, 15) = 1, gcd(4, 36) = 4, gcd(4, 48) = 4, gcd(15, 36) = 3, gcd(15, 48) = 3, gcd(36, 48) = 12$. Используя описанное выше соотношение для проверки, получаем: $|2|_4=|30|_4, |2|_4=|42|_4, |6|_3 = |30|_3, |6|_3=|42|_3$ и $|30|_{12}=|42|_{12}$. То есть ошибок нет и число может быть восстановлено с использованием китайской теоремы об остатках (КТО) для модулей, имеющих нетривиальные общие делители.

КТО для системы модулей, не взаимно простых попарно. Пусть есть представление $(r_1, ..., r_n)$ натурального числа $x$, определяемое системой модулей $(m_1, ..., m_n)$. Тогда

$|x|_M = \left | \sum^{n}_{i=1} {{{\alpha}_i}r_i} \right |$,

где ${\alpha}_i$- число, такое что $|{\alpha}_i|_M = 0, |{\alpha}_i|_{\frac{M}{{\mu}_i}} = 1$, где ${\mu}_i$ - числа, такие что $M = \prod^n_{i=1}{{\mu}_i}$, ${\mu}_i$ делит $m_i$ и $M = lcm(m_1, ..., m_n)$. Если для некоторого $i$ такое ${\alpha}_i$ не существует, то соответствующее слагаемое в сумме опускается.

Операции над числами остаются корректными и в системе не взаимно простых модулей.