Просмотр исходного текста страницы Схема коррекции ошибок Rajendra S. Katti

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

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

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

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

== Модули, имеющие общие делители ==
Каждый набор остатков необязательно соответствует числу из динамического диапазона, если модули не являются попарно взаимно простыми. Легко показать, что такое соответствие есть тогда и только тогда, когда равенство
:<math>|r_i|_k = |r_j|_k</math>,
выполняется для любых <math>i, j</math>, где <math>k = gcd(r_i, r_j)</math>. Таким образом, ошибочный разряд может быть найден выполнением только простой операции вычисления остатка.

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

'''КТО для системы модулей, попарно не взаимно простых'''. Пусть есть представление <math>(r_1, ..., r_n)</math> натурального числа <math>x</math>, определяемое системой модулей <math>(m_1, ..., m_n)</math>. Тогда
:<math>|x|_M = \left | \sum^{n}_{i=1} {{{\alpha}_i}r_i} \right |</math>,
где <math> {\alpha}_i </math>- число, такое что <math>|{\alpha}_i|_M = 0, |{\alpha}_i|_{\frac{M}{{\mu}_i}} = 1 </math>,
где <math> {\mu}_i </math> - числа, такие что <math> M = \prod^n_{i=1}{{\mu}_i} </math>, <math> {\mu}_i </math> делит <math> m_i </math> и <math> M = lcm(m_1, ..., m_n) </math>. Если для некоторого <math>i</math> такое <math>{\alpha}_i</math> не существует, то соответствующее слагаемое в сумме опускается. 

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

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

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

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

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

'''Циклическим числом''' <math>c_i</math> для каждого модуля <math>m_i</math> назовём <math>c_i = M/m_i</math>.
=== Модули с попарно взаимно простыми циклическими числами ===
Построим теперь систему модулей с попарно взаимно простыми циклическими числами, которая поможет получит эффективный алгоритм обнаружения и коррекции ошибок. 

'''Построение 1'''. 
#Выберем <math>n</math> попарно взаимно простых циклических чисел, не равных единице <math>(c_1, ..., c_n)</math>.
#Получим систему модулей <math>(m_1, ..., m_n)</math> следующим образом:
:<math>m_i = \frac{1}{c_i}\prod^n_{k=1}{c_k}</math>.

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

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

==== Алгоритм обнаружения ошибки ====
#Если <math>r_i \geqslant m_i</math>, то произошла ошибка в <math>i</math>-том разряде.
#Если не выполняется хотя бы одно из следующей системы равенств:
:<math>|r_i|_{k_{ij}}=|r_j|_{k_{ij}}, k_{ij} = gcd(m_i, m_j)</math>,
то произошла ошибка.

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

==== Алгоритм локализации ошибки ====
Теорема 2 даёт алгоритм локализации ошибки. Ошибочным является разряд, который содержится во всех равенствах, которые не выполняются.
==== Алгоритм коррекции ошибки ====
Предложим, что ошибка в <math>r_i</math> и <math>\bar{r_i}</math> - правильное значение. Тогда <math>\bar{r_i}</math> можно найти, решая следующую систему уравнений:
:<math>|\bar{r_i}|_{k_a} = |r_j|_{k_a}, k_a = gcd(m_i, m_j)</math>,
:<math>|\bar{r_i}|_{k_b} = |r_k|_{k_b}, k_b = gcd(m_i, m_k)</math>.

Решение заключается в составлении множеств <math>A</math> и <math>B</math>:
:<math>A = \left \{ f = |r_j|_{k_a}  + k_a k_x : f < m_i, k_x \geq 0 \right \}</math>,
:<math>B = \left \{ g = |r_k|_{k_b}  + k_b k_y : g < m_i, k_y \geq 0 \right \}</math>.
и поиске пересечения <math>A \cap B</math>. Можно доказать, что такое пересечение всегда непусто и состоит ровно из одного элемента.

==== Примеры ====
'''Пример обнаружения одной ошибки.'''
Воспользуемся Построением 1 для получения системы модулей. Используя попарно взаимно простые циклические числа <math>(c_1, c_2, c_3, c_4)=(2, 3, 5, 7)</math>, получим систему модулей <math>(m_1, m_2, m_3, m_4)=(105, 70, 42, 30)</math>. Пусть теперь в остаточном представлении <math>(r_1, r_2, r_3, r_4)=(30, 60, 30, 0)</math> содержится одна ошибка. Проверяя совместность представления, найдём, что следующие равенства не выполняются:
:<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>. Вычисления элементов множеств следует прекратить, как только их пересечение больше не пусто.
'''Пример обнаружения двух и коррекции одной ошибки.'''
Для обнаружения двух и коррекции одной ошибки требуется по крайней мере 5 модулей и кодовое расстояние равное 4. Если мы выберем циклические числа <math>(2, 3, 5, 7, 11)</math> мы получим набор модулей <math>(m_1, m_2, m_3, m_4, m_5) = (1155, 770, 462, 330, 210)</math>. Чтобы проверить, есть ли ошибки в остаточном представлении <math>(r_1, r_2, r_3, r_4, r_5)</math>, нужно выяснить, какие из следующих равенств не выполняются:
:<math>|r_1|_{385} = |r_2|_{385}, 385 = gcd(1155, 770)</math>,
:<math>|r_1|_{231} = |r_3|_{231}, 231 = gcd(1155, 462)</math>,
:<math>|r_1|_{105} = |r_5|_{105}, 105 = gcd(1155, 210)</math>,
:<math>|r_2|_{154} = |r_3|_{154}, 154 = gcd(462, 770)</math>,
:<math>|r_2|_{110} = |r_4|_{110}, 110 = gcd(330, 770)</math>,
:<math>|r_2|_{70} = |r_5|_{70}, 70 = gcd(210, 770)</math>,
:<math>|r_3|_{66} = |r_4|_{66}, 66 = gcd(462, 330)</math>,
:<math>|r_3|_{42} = |r_5|_{42}, 42 = gcd(462, 210)</math>,
:<math>|r_4|_{30} = |r_5|_{30}, 30 = gcd(330, 210)</math>.
Следует отметить, что если три или четыре из равенств выше не выполняются, то обнаружена одна ошибка. Если их пять и больше, то ошибок две. Аналогично предыдущему примеру, можно построить три множества <math>A, B, C</math>. Исправленное значение ошибочного разряда получим, найдя пересечение этих множеств:
<math>\{ \bar {r_i} \}= A \cap B \cap C</math>.

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

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

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

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

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

==== Алгоритм обнаружения ошибки ====
#Если <math>r_i \geqslant m_i</math>, то произошла ошибка в <math>i</math>-том разряде.
#Если остаточное представление не является совместным и слово не лежит в динамическом диапазоне, то произошла ошибка. Для проверки нужно воспользоваться КТО для перевода числа из остаточного представления и проверить, выполняется ли <math>x \leq l_1-1</math>.
#Если остаточное представление не является совместным, то произошла ошибка.
#Если остаточное представление является совместным и лежит в динамическом диапазоне, то ошибок нет.
==== Алгоритм коррекции ошибки ====
Начнём описание алгоритма со следующей леммы.

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

Опишем теперь коррекцию ошибки для каждого варианта:
#Кодовое слово за пределами динамического диапазона и совместно.
#Кодовое слово не совместно.

'''Вариант 1'''. Пусть остаточное представление <math>(r_1, r_2, r_3, r_4)</math> соответствует целому <math>R</math>. Так как только один разряд ошибочный, то <math>R</math> принадлежит множеству <math>C</math>. Коррекция выполняется следующим образом:
#Для всех кортежей из трёх остатков вычислить по КТО соответствующее целое.
#Если полученное целое принадлежит динамическому диапазону, то ошибка в исключённом разряде.
#Предположим без потери общности, что ошибочным является <math>r_3</math>. Найдём правильное значение <math>\bar {r_3}</math> из следующих уравнений:
:<math>|\bar{r_3}|_{k_a} = |r_1|_{k_a}, k_a = gcd(m_3, m_1)</math>,
:<math>|\bar{r_3}|_{k_b} = |r_2|_{k_b}, k_b = gcd(m_3, m_2)</math>,
:<math>|\bar{r_3}|_{k_c} = |r_4|_{k_c}, k_c = gcd(m_3, m_4)</math>.

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

'''Вариант 2'''. Пусть кодовое слово <math>(r_1, r_2, r_3, r_4)</math> не является совместным, то есть не выполняется равенство:
:<math>|r_i|_{k_a} = |r_j|_{k_a}, k_a = gcd(m_i, m_j)</math>.

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

==== Примеры ====
Определим множество модулей <math>(m_1, m_2, m_3, m_4) = (8,6,4,2)</math>. Все кодовые слова и их целые эквиваленты приведены ниже:
:<math>(0,0,0,0) = 0</math>
:<math>(1,1,1,1) = 1</math>
:<math>(2,2,2,0) = 2</math>
:<math>(3,3,3,1) = 3</math>
:<math>(4,4,0,0) = 4</math>
:<math>(5,5,1,3) = 5</math>
:<math>(6,0,2,0) = 6</math>
:<math>(7,1,3,1) = 7</math>
:<math>(0,2,0,0) = 8</math>
:<math>(1,3,1,1) = 9</math>
:<math>(2,4,2,0) = 10</math>
:<math>(3,5,3,1) = 11</math>
:<math>(4,0,0,0) = 12</math>
:<math>(5,1,1,1) = 13</math>
:<math>(6,2,2,0) = 14</math>
:<math>(7,3,3,1) = 15</math>
:<math>(0,4,0,0) = 16</math>
:<math>(1,5,1,1) = 17</math>
:<math>(2,0,2,0) = 18</math>
:<math>(3,1,3,1) = 19</math>
:<math>(4,2,0,0) = 20</math>
:<math>(5,3,1,1) = 21</math>
:<math>(6,4,2,0) = 22</math>
:<math>(7,5,3,1) = 23</math>

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

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

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

Единственное представление, лежащее в <math>\{0, ..., 3\}</math> -  это <math>(2,2,0)</math>, следовательно <math>r_2 = 0</math> является ошибочным. Эта ошибка может быть исправлена, правильное значение можно найти из следующих уравнений:
:<math>|\bar {r_2}|_2 = |r_1|_2 = 0</math>,
:<math>|\bar {r_2}|_2 = |r_3|_2 = 0</math>,
:<math>|\bar {r_2}|_2 = |r_4|_2 = 0</math>,
:<math>\bar {r_2} \leq 5</math>.

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

'''Пример 2 '''. Остаточное представление <math>(r_1, r_2, r_3, r_4) = (0,0,0,5)</math>. Так как <math>r_4 \geq 2</math>, то <math>r_4</math> - ошибочный. Найдём правильное значение из следующих уравнений:
:<math>|\bar {r_4}|_2 = |r_1|_2 = 0</math>,
:<math>|\bar {r_4}|_2 = |r_2|_2 = 0</math>,
:<math>|\bar {r_4}|_2 = |r_3|_2 = 0</math>,
:<math>\bar {r_4} \leq 1</math>.

Получаем <math>\bar {r_4} = 1</math>.

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

Пусть <math>r_3</math> - ошибочный. Тогда скорректированное значение <math>r_3</math> может быть найдено из следующих уравнений:
:<math>|\bar {r_3}|_4 = |r_1|_4 = 1</math>,
:<math>|\bar {r_3}|_2 = |r_2|_2 = 1</math>,
:<math>|\bar {r_3}|_2 = |r_4|_2 = 1</math>,
:<math>\bar {r_3} \leq 3</math>.

Решая, находим <math> \bar {r_3} = 1 </math>. Скорректированное остаточное представление <math>(1,3,1,1) = 9</math> лежит вне динамического диапазона. Значит, ошибочным является <math>r_1</math>. Проводя аналогичную процедуру, находим <math>r_1 = 3</math>. Полученное остаточное представление <math>(3,3,3,1) = 3</math> лежит в динамическом диапазоне, коррекция завершена. Заметим, что мы пытались обнаружить ошибку в остаточном представлении <math>(1,3,3,1)</math>, которое имеет кодовое расстояние равное <math>1</math> с совместными представлениями <math>(1,3,1,1)</math> и <math>(3,3,3,1)</math>. По Лемме 1 только одно из них лежит в динамическом диапазоне.
== Литература ==
Rajendra S. Katti, A New Residue Arithmetic Error Correction Scheme, IEEE Trans. Computers, 1996, том 45, стр. 13-19