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

Текущая версия на 11:35, 26 мая 2014

Содержание

1 Введение
2 Модули, имеющие общие делители
3 Алгоритм
- 3.1 Модули с попарно взаимно простыми циклическими числами
- 3.2 Модули с произвольными циклическими числами
4 Литература

[править] Введение

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

Пусть избыточная СОК определяется следующими модулями $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)$ , правильный результат восстановления будет получен тогда и только тогда, когда отбрасываемая цифра ошибочна. Итак, обнаружение ошибок и коррекция выполняется следующим образом:

Если число лежит вне динамического диапазона - произошла ошибка.
Остатки отбрасываются по одному и если в результате одного из отбрасываний полученное число лежит в динамическом диапазоне, то отброшенный остаток является ошибочным.
Корректное значение остатка получается расширением полученного на шаге 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.

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

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

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

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

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

[править] Алгоритм обнаружения ошибки

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

$|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$ выходят за границы динамического диапазона. Пусть необходимо обнаружить/исправить одну ошибку в остаточном представлении.