Схема коррекции ошибок Rajendra S. Katti - История изменений

Turbo в 08:35, 26 мая 2014

2014-05-26T08:35:07Z

Myachikov в 12:53, 31 июля 2013

2013-07-31T12:53:54Z

Myachikov в 12:34, 31 июля 2013

2013-07-31T12:34:08Z

Myachikov в 10:50, 31 июля 2013

2013-07-31T10:50:13Z

Myachikov в 13:12, 22 июля 2013

2013-07-22T13:12:04Z

Myachikov в 12:55, 22 июля 2013

2013-07-22T12:55:22Z

Myachikov: Новая страница: «== Введение == Метод, описанный автором, основан на использовании избыточной системы оста…»

2013-07-22T09:41:05Z

Новая страница: «== Введение == Метод, описанный автором, основан на использовании избыточной системы оста…»

Новая страница

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

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

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

== Алгоритм ==

← Предыдущая		Версия 12:53, 31 июля 2013
Строка 208:		Строка 208:

	Решая, находим <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 только одно из них лежит в динамическом диапазоне.		Решая, находим <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

@@ Строка 12: / Строка 12: @@
 == Модули, имеющие общие делители ==
-Каждый набор остатков необязательно соответствует числу из динамического диапазона, если модули не являются попарно взаимно простыми. Легко показать, что такое соответствие есть тогда и только тогда, когда
+Каждый набор остатков необязательно соответствует числу из динамического диапазона, если модули не являются попарно взаимно простыми. Легко показать, что такое соответствие есть тогда и только тогда, когда равенство
 :<math>|r_i|_k = |r_j|_k</math>,
 выполняется для любых <math>i, j</math>, где <math>k = gcd(r_i, r_j)</math>. Таким образом, ошибочный разряд может быть найден выполнением только простой операции вычисления остатка.
@@ Строка 124: / Строка 124: @@
 Начнём описание алгоритма со следующей леммы.
-'''Лемма 1'''. Существует и единственно кодовое слово в множестве <math>A</math>
+'''Лемма 1'''. Существует и единственно кодовое слово в множестве <math>A</math>, такое что кодовое расстояние между этим словом и остаточным представлением <math>(r_1, r_2, r_3, r_4)</math> равно <math>1</math>.

← Предыдущая		Версия 10:50, 31 июля 2013
Строка 88:		Строка 88:

	Необязательно вычислять множество <math>B</math> полностью. Так как <math>\|r_1\|_{35} > 14</math>, то <math>k_y \geq 2</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>

← Предыдущая		Версия 13:12, 22 июля 2013
Строка 76:		Строка 76:
	:<math>\|r_1\|_{35} = \|r_2\|_{35}, 35 = gcd(105, 70)</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\|_{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>. Вычисления элементов множеств следует прекратить, как только их пересечение больше не пусто.

@@ Строка 1: / Строка 1: @@
 == Введение ==
-Метод, описанный автором, основан на использовании избыточной системы остаточных классов. Недостатки представления чисел в такой системе с целью коррекции ошибок при вычислениях покажем на примере.
+Традиционный метод коррекции ошибок, основан на использовании избыточной системы остаточных классов с взаимнопростыми основаниями. Недостатки представления чисел в такой системе с целью коррекции ошибок при вычислениях покажем на примере.
 Пусть избыточная СОК определяется следующими модулями <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> являются дополнительными и необходимы для проверки на ошибки.

@@ Строка 4: / Строка 4: @@
 Пусть избыточная СОК определяется следующими модулями <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>, правильный результат восстановления будет получен тогда и только тогда, когда отбрасываемая цифра ошибочна. Таким образом, обнаружение ошибок и коррекция выполняется следующим образом:
+Натуральное число из динамического диапазона может быть восстановлено по любым трём из четырёх остатков по представленным модулям. Например, число <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>, правильный результат восстановления будет получен тогда и только тогда, когда отбрасываемая цифра ошибочна. Итак, обнаружение ошибок и коррекция выполняется следующим образом:
 # Если число лежит вне динамического диапазона - произошла ошибка.
 # Остатки отбрасываются по одному и если в результате одного из отбрасываний полученное число лежит в динамическом диапазоне, то отброшенный остаток является ошибочным.
@@ Строка 13: / Строка 13: @@
 == Модули, имеющие общие делители ==
 Каждый набор остатков необязательно соответствует числу из динамического диапазона, если модули не являются попарно взаимно простыми. Легко показать, что такое соответствие есть тогда и только тогда, когда
-: <math>|r_i|_k = |r_j|_k</math>,
+:<math>|r_i|_k = |r_j|_k</math>,
 выполняется для любых <math>i, j</math>, где <math>k = gcd(r_i, r_j)</math>. Таким образом, ошибочный разряд может быть найден выполнением только простой операции вычисления остатка.
@@ Строка 19: / Строка 19: @@
 Используя описанное выше соотношение для проверки, получаем: <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>(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> не существует, то соответствующее слагаемое в сумме опускается.
-Операции над числами остаются корректными и в системе не взаимно простых модулей.
+Операции над числами остаются корректными и в системе не взаимно простых попарно модулей.
 == Алгоритм ==