Схема коррекции ошибок Rajendra S. Katti — различия между версиями

Версия 13:12, 22 июля 2013

Содержание

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

Введение

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

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

@@ Строка 76: / Строка 76: @@
 :<math>|r_1|_{35} = |r_2|_{35}, 35 = gcd(105, 70)</math>,
 :<math>|r_2|_{14} = |r_3k|_{14}, 14 = gcd(70, 42)</math>.
+Так как <math>r_2</math> является общим в этих равенствах, ошибочным является остаток <math>60</math>. Для того чтобы получить правильное значение, составим множества <math>A</math> и <math>B</math> как было описано выше:
+:<math>A = \left \{ f = |r_1|_{35}  + 35 k_x : f < 70, k_x \geq 0 \right \}</math>,
+:<math>B = \left \{ g = |r_3|_{14}  + 14 k_y : g < 70, k_y \geq 0 \right \}</math>.
+Получим:
+:<math>A = \left \{ 30, 65 \right \}</math>,
+:<math>B = \left \{ 2,16,30,44,58\right \}</math>.
+Таким образом скорректированное значение <math>\{ \bar {r_2} \}= A \cap B = \{ 30 \}</math>.
+Необязательно вычислять множество <math>B</math> полностью. Так как <math>|r_1|_{35} > 14</math>, то <math>k_y \geq 2</math>. Вычисления элементов множеств следует прекратить, как только их пересечение больше не пусто.

Схема коррекции ошибок Rajendra S. Katti — различия между версиями

Версия 13:12, 22 июля 2013

Содержание

Введение

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

Алгоритм

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

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

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

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

Примеры

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты