Схема коррекции ошибок 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$ не существует, то соответствующее слагаемое в сумме опускается.

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

Алгоритм

Если в множестве модулей $(m_1, ..., m_n)$ есть имеющие нетривиальный общий делитель, то каждый набор остатков $(r_1, ..., r_n)$ необязательно соответствует некоторому числу. Каждый набор, для которого такое соответствие имеет место, будем называть кодовым словом.

Расстоянием между двумя представлениями чисел в СОК(кодовыми словами) будем считать количество разрядов, в которых кодовые слова различаются между собой.

Кодовым расстоянием назовём минимальное расстояние среди всех пар кодовых слов.

Чтобы обнаружить и исправить $d-1$ или меньше ошибок, необходимо и достаточно, чтобы кодовое расстояние было не меньше $d$. Не более $t$ ошибок может быть обнаружено и исправлено тогда и только тогда, когда кодовое расстояние больше, чем $(2t+1)$. Если кодовое расстояние больше или равно, чем $(t+d+1)$, то любая комбинация из $t$ ошибок может быть исправлена и до $d$ошибок могут быть обнаружены. Для множества из $n$ модулей в соответствующей системе могут быть представлены числа $(0, ..., M-1)$, где $M = lcm(m_1, ..., m_n)$.

Циклическим числом $c_i$ для каждого модуля $m_i$ назовём $c_i = M/m_i$.

Модули с попарно взаимно простыми циклическими числами

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

Построение 1.

1. Выберем $n$ попарно взаимно простых циклических чисел, не равных единице $(c_1, ..., c_n)$.
2. Получим систему модулей $(m_1, ..., m_n)$ следующим образом:

$m_i = \frac{1}{c_i}\prod^n_{k=1}{c_k}$.

Полученные модули обладают двумя свойствами:

1. Наименьшие общие кратны всевозможных пар модулей равны между собой.
2. Наибольшие общие делители всевозможных пар модулей различны.

Теорема 1. Для построенной системы модулей кодовое расстояние равно $n-1$, где $n$ - количество модулей.

Алгоритм обнаружения ошибки

1. Если $r_i \geqslant m_i$, то произошла ошибка в $i$-том разряде.
2. Если не выполняется хотя бы одно из следующей системы равенств:

$|r_i|_{k_{ij}}=|r_j|_{k_{ij}}, k_{ij} = gcd(m_i, m_j)$,

то произошла ошибка.

Теорема 2. Для системы из четырёх модулей $(m_1, m_2, m_3, m_4)$ ошибка в одном разряде влечёт за собой невыполнением как минимум двух, а как максимум трёх равенств из системы выше. Причём, если ошибка в $r_i$, то равенства, которые не выполняются, содержат $r_i$.

Алгоритм локализации ошибки

Теорема 2 даёт алгоритм локализации ошибки. Ошибочным является разряд, который содержится во всех равенствах, которые не выполняются.

Алгоритм коррекции ошибки

Предложим, что ошибка в $r_i$ и $\bar{r_i}$ - правильное значение. Тогда $\bar{r_i}$ можно найти, решая следующую систему уравнений:

$|\bar{r_i}|_{k_a} = |r_j|_{k_a}, k_a = gcd(m_i, m_j)$,

$|\bar{r_i}|_{k_b} = |r_k|_{k_b}, k_b = gcd(m_i, m_k)$.

Решение заключается в составлении множеств $A$ и $B$:

$A = \left \{ f = |r_j|_{k_a} + k_a k_x : f < m_i, k_x \geq 0 \right \}$,

$B = \left \{ g = |r_k|_{k_b} + k_b k_y : g < m_i, k_y \geq 0 \right \}$.

и поиске пересечения $A \cap B$. Можно доказать, что такое пересечение всегда непусто и состоит ровно из одного элемента.

Примеры

Пример обнаружения одной ошибки. Воспользуемся Построением 1 для получения системы модулей. Используя попарно взаимно простые циклические числа $(c_1, c_2, c_3, c_4)=(2, 3, 5, 7)$, получим систему модулей $(m_1, m_2, m_3, m_4)=(105, 70, 42, 30)$. Пусть теперь в остаточном представлении $(r_1, r_2, r_3, r_4)=(30, 60, 30, 0)$ содержится одна ошибка. Проверяя совместность представления, найдём, что следующие равенства не выполняются:

$|r_1|_{35} = |r_2|_{35}, 35 = gcd(105, 70)$,

$|r_2|_{14} = |r_3k|_{14}, 14 = gcd(70, 42)$.

Так как $r_2$ является общим в этих равенствах, ошибочным является остаток $60$. Для того чтобы получить правильное значение, составим множества $A$ и $B$ как было описано выше:

$A = \left \{ f = |r_1|_{35} + 35 k_x : f < 70, k_x \geq 0 \right \}$,

$B = \left \{ g = |r_3|_{14} + 14 k_y : g < 70, k_y \geq 0 \right \}$.

Получим:

$A = \left \{ 30, 65 \right \}$,

$B = \left \{ 2,16,30,44,58\right \}$.

Таким образом скорректированное значение $\{ \bar {r_2} \}= A \cap B = \{ 30 \}$.

Необязательно вычислять множество $B$ полностью. Так как $|r_1|_{35} > 14$, то $k_y \geq 2$. Вычисления элементов множеств следует прекратить, как только их пересечение больше не пусто. Пример обнаружения двух и коррекции одной ошибки. Для обнаружения двух и коррекции одной ошибки требуется по крайней мере 5 модулей и кодовое расстояние равное 4. Если мы выберем циклические числа $(2, 3, 5, 7, 11)$ мы получим набор модулей $(m_1, m_2, m_3, m_4, m_5) = (1155, 770, 462, 330, 210)$. Чтобы проверить, есть ли ошибки в остаточном представлении $(r_1, r_2, r_3, r_4, r_5)$, нужно выяснить, какие из следующих равенств не выполняются:

$|r_1|_{385} = |r_2|_{385}, 385 = gcd(1155, 770)$,

$|r_1|_{231} = |r_3|_{231}, 231 = gcd(1155, 462)$,

$|r_1|_{105} = |r_5|_{105}, 105 = gcd(1155, 210)$,

$|r_2|_{154} = |r_3|_{154}, 154 = gcd(462, 770)$,

$|r_2|_{110} = |r_4|_{110}, 110 = gcd(330, 770)$,

$|r_2|_{70} = |r_5|_{70}, 70 = gcd(210, 770)$,

$|r_3|_{66} = |r_4|_{66}, 66 = gcd(462, 330)$,

$|r_3|_{42} = |r_5|_{42}, 42 = gcd(462, 210)$,

$|r_4|_{30} = |r_5|_{30}, 30 = gcd(330, 210)$.

Следует отметить, что если три или четыре из равенств выше не выполняются, то обнаружена одна ошибка. Если их пять и больше, то ошибок две. Аналогично предыдущему примеру, можно построить три множества $A, B, C$. Исправленное значение ошибочного разряда получим, найдя пересечение этих множеств: $\{ \bar {r_i} \}= A \cap B \cap C$.

Модули с произвольными циклическими числами

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

Теорема 3. Пусть есть множество модулей $(m_1, m_2, ..., m_n)$ и $(l_1, l_2, ..., l_a)$ - множество наименьших общих кратных всевозможных различных пар модулей, где $a = C^2_n$. Тогда, если $l = \min{(l_1, l_2, ..., l_a)}$, то кодовое расстояние множества всех представлений чисел $\{0, ..., l-1\}$ в системе остаточных классов равно $n-1$.

Следствие. Пусть есть множество модулей $(m_1, m_2, ..., m_n)$ и $(l_1, l_2, ..., l_a)$ - множество наименьших общих кратных всевозможных кортежей из $i$ различных модулей, где $a = C^i_n$. Тогда, если $l = \min{(l_1, l_2, ..., l_a)}$, то кодовое расстояние множества всех представлений чисел $\{0, ..., l-1\}$ в системе остаточных классов равно $n - 1 + i$.

Далее будем предполагать, что ошибочный разряд только один. Из теоремы 3 следует, что для коррекции одной ошибки требуется множество из 4 модулей $(m_1, m_2, m_3, m_4)$. Пусть $l_1, l_2, l_3$ - соответственно наименьшее из НОК всех пар, наименьшее из НОК всех троек и НОК всех модулей. Из теоремы 3 и следствия из неё следует, что для множества чисел $\{0, ..., l_1-1\}$ кодовое расстояние соответствующего множества кодовых слов равно $3$, а для множеств $\{0, ..., l_2-1\}$ и $\{0, ..., l_3-1\}$ - не меньше $2$ и не меньше $1$ соответственно. Разделим множество всех кодовых слов на три подмножества:

$A = \{x : 0 \leq x \leq l_1-1\}$,

$B = \{x : l_1 \leq x \leq l_2-1\}$,

$C = \{x : l_2 \leq x \leq l_3-1\}$.

Для коррекции одной ошибки необходимо кодовое расстояние, равное трём, то есть все слова из $A$ и $B$ выходят за границы динамического диапазона. Пусть необходимо обнаружить/исправить одну ошибку в остаточном представлении.

Алгоритм обнаружения ошибки

1. Если $r_i \geqslant m_i$, то произошла ошибка в $i$-том разряде.
2. Если остаточное представление не является совместным и слово не лежит в динамическом диапазоне, то произошла ошибка. Для проверки нужно воспользоваться КТО для перевода числа из остаточного представления и проверить, выполняется ли $x \leq l_1-1$.
3. Если остаточное представление не является совместным, то произошла ошибка.
4. Если остаточное представление является совместным и лежит в динамическом диапазоне, то ошибок нет.

Алгоритм коррекции ошибки

Начнём описание алгоритма со следующей леммы.

Лемма 1. Существует и единственно кодовое слово в множестве $A$, такое что кодовое расстояние между этим словом и остаточным представлением $(r_1, r_2, r_3, r_4)$ равно $1$.

Опишем теперь коррекцию ошибки для каждого варианта:

1. Кодовое слово за пределами динамического диапазона и совместно.
2. Кодовое слово не совместно.

Вариант 1. Пусть остаточное представление $(r_1, r_2, r_3, r_4)$ соответствует целому $R$. Так как только один разряд ошибочный, то $R$ принадлежит множеству $C$. Коррекция выполняется следующим образом:

1. Для всех кортежей из трёх остатков вычислить по КТО соответствующее целое.
2. Если полученное целое принадлежит динамическому диапазону, то ошибка в исключённом разряде.
3. Предположим без потери общности, что ошибочным является $r_3$. Найдём правильное значение $\bar {r_3}$ из следующих уравнений:

$|\bar{r_3}|_{k_a} = |r_1|_{k_a}, k_a = gcd(m_3, m_1)$,

$|\bar{r_3}|_{k_b} = |r_2|_{k_b}, k_b = gcd(m_3, m_2)$,

$|\bar{r_3}|_{k_c} = |r_4|_{k_c}, k_c = gcd(m_3, m_4)$.

Если полученных решений несколько, то согласно Лемме 1 только одно из них принадлежит динамическому диапазону.

Вариант 2. Пусть кодовое слово $(r_1, r_2, r_3, r_4)$ не является совместным, то есть не выполняется равенство:

$|r_i|_{k_a} = |r_j|_{k_a}, k_a = gcd(m_i, m_j)$.

Значит ошибочным является либо $r_i$, либо $r_j$. Пусть ошибка в $r_i$, найдём правильное значение, как в шаге 3 выше. Если для полученных решений, соответствующие целые не лежат в динамическом диапазоне, то ошибка в $r_j$, и её можно исправить тем же способом, описанным в шаге 3.

Примеры

Определим множество модулей $(m_1, m_2, m_3, m_4) = (8,6,4,2)$. Все кодовые слова и их целые эквиваленты приведены ниже:

$(0,0,0,0) = 0$

$(1,1,1,1) = 1$

$(2,2,2,0) = 2$

$(3,3,3,1) = 3$

$(4,4,0,0) = 4$

$(5,5,1,3) = 5$

$(6,0,2,0) = 6$

$(7,1,3,1) = 7$

$(0,2,0,0) = 8$

$(1,3,1,1) = 9$

$(2,4,2,0) = 10$

$(3,5,3,1) = 11$

$(4,0,0,0) = 12$

$(5,1,1,1) = 13$

$(6,2,2,0) = 14$

$(7,3,3,1) = 15$

$(0,4,0,0) = 16$

$(1,5,1,1) = 17$

$(2,0,2,0) = 18$

$(3,1,3,1) = 19$

$(4,2,0,0) = 20$

$(5,3,1,1) = 21$

$(6,4,2,0) = 22$

$(7,5,3,1) = 23$

Множества $A, B, C$, определённые выше, равны $A = \{0, ..., 3\}, B = \{4, ..., 7\}, C = \{8, ..., 23\}$.

Рассмотрим теперь несколько примеров обнаружения и коррекции.

Пример 1 . Остаточное представление $(r_1, r_2, r_3, r_4) = (2,0,2,0)$ является совместным и не принадлежит динамическому диапазону. Четыре кортежа из трёх остатков и соответствующие им целые:

$(2,0,2) = 18$

$(0,2,0) = 6$

$(2,0,0) = 18$

$(2,2,0) = 2$

Единственное представление, лежащее в $\{0, ..., 3\}$ - это $(2,2,0)$, следовательно $r_2 = 0$ является ошибочным. Эта ошибка может быть исправлена, правильное значение можно найти из следующих уравнений:

$|\bar {r_2}|_2 = |r_1|_2 = 0$,

$|\bar {r_2}|_2 = |r_3|_2 = 0$,

$|\bar {r_2}|_2 = |r_4|_2 = 0$,

$\bar {r_2} \leq 5$.

Им удовлетворяют три решения: $0, 2, 4$. Правильным является $\bar {r_2} = 2$, так оставшиеся два соответствуют представлениям, лежащим вне динамического диапазона.

Пример 2 . Остаточное представление $(r_1, r_2, r_3, r_4) = (0,0,0,5)$. Так как $r_4 \geq 2$, то $r_4$ - ошибочный. Найдём правильное значение из следующих уравнений:

$|\bar {r_4}|_2 = |r_1|_2 = 0$,

$|\bar {r_4}|_2 = |r_2|_2 = 0$,

$|\bar {r_4}|_2 = |r_3|_2 = 0$,

$\bar {r_4} \leq 1$.

Получаем $\bar {r_4} = 1$.

Пример 3 . Остаточное представление $(r_1, r_2, r_3, r_4) = (1,3,3,1)$ является несовместным, так как не выполняется следующее равенство:

$|r_1|_4 = |r_3|_4$.

Пусть $r_3$ - ошибочный. Тогда скорректированное значение $r_3$ может быть найдено из следующих уравнений:

$|\bar {r_3}|_4 = |r_1|_4 = 1$,

$|\bar {r_3}|_2 = |r_2|_2 = 1$,

$|\bar {r_3}|_2 = |r_4|_2 = 1$,

$\bar {r_3} \leq 3$.

Решая, находим $\bar {r_3} = 1$. Скорректированное остаточное представление $(1,3,1,1) = 9$ лежит вне динамического диапазона. Значит, ошибочным является $r_1$. Проводя аналогичную процедуру, находим $r_1 = 3$. Полученное остаточное представление $(3,3,3,1) = 3$ лежит в динамическом диапазоне, коррекция завершена. Заметим, что мы пытались обнаружить ошибку в остаточном представлении $(1,3,3,1)$, которое имеет кодовое расстояние равное $1$ с совместными представлениями $(1,3,1,1)$ и $(3,3,3,1)$. По Лемме 1 только одно из них лежит в динамическом диапазоне.