Пример коррекции ошибки на базе системы остаточных классов

Текущая версия на 16:59, 16 декабря 2013

[править] Постановка задачи

В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Числовое значение строки представляется в модулярном базисе состоящем из 4-5-битных простых чисел (аналог 4-х битного блока в позиционных кодах). Необходимо отследить и исправить одиночную ошибку, внесённую в один из модулярных каналов.

Любой строке из 16 бит можно поставить в соответствие число из диапазона $[0...65536)$ . Далее данное число мы представляем в системе остаточных классов (СОК) по выбранным нами модулям. Затем, внеся одиночную ошибку в любой модуль мы попробуем исправить её. Алгоритм исправления ошибки заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученного числа.

[править] Теоретические основы алгоритма

Пусть имеется $k$ взаимно простых чисел $p_1,p_2,p_3,...,p_k$ . Назовём их рабочими основаниями. Известно, что в СОК по данным модулям однозначно представляется число из рабочего диапазона $[0...p_1*p_2*...*p_k)$ . Далее введём два дополнительных взаимно простых основания $p_{k+1},p_{k+2}$ таких, что все $k+2$ полученных оснований $p_1,p_2,p_3,...,p_k,p_{k+1},p_{k+2}$ будут взаимно простыми. Пусть наше исходное число $A$ принадлежит диапазону $[0...p_1*p_2*...*p_k)$ . Если представить его в СОК по модулям $\left \{p_1,p_2,p_3,...,p_k,p_{k+1}\right \}$ , затем внести ошибку по любому из модулей, а потом попытаться восстановить данное число по Китайской Теореме об Остатках, то известно, что результат $\bar A>p_1*p_2*...*p_k$ . Таким образом, имея два контрольных основания мы можем исправлять одиночную ошибку, последовательно исключая по одному из модулей и получая ситуацию, описанную выше. Если мы исключили основание, по которому произошла ошибка, мы получим правильное число, лежащее в пределах диапазона $[0...p_1*p_2*...*p_k)$ .

[править] Пример

Пусть имеется 16ти-битная строка $1000001000110101$ . Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.

Шаг 1 Для выполнения данной задачи выбираем 4 рабочих основания и 2 контрольных. Рабочие основания: $p_1=13, p_2=16, p_3=17, p_4=19$ . Контрольные основания: $p_5=21, p_6=23$ . При таком выборе рабочих оснований мы можем работать с числами из диапазона от $0$ до $13*16*17*19=67183 > 65536$ . Таким образом, этих рабочих оснований хватит для работы с нашей исходной строкой. Выбор таких рабочих обусловлен тем, что полученный динамический диапазон практически совпадает с исходным $[0...65536)$ . Изначально строка содержала 16 бит, но после кодирования (представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной $4+4+5+5+5+5=28$ . Таким образом, избыточность составляет $28-16=12$ бит. Представим это число в СОК:

Шаг 2 Процесс кодирования и внесения ошибки: Переведем строку $1000001000110101$ в десятичную систему счисления и получим $33.333$

Представим это число в СОК по нашим модулям и получим: $33.333=(1, 5, 13, 7, 6, 6)$ . Представим всё это в бинарном виде: $0001 0101 01101 00111 00110 00110$ . Это и есть наша закодированная строка. Затем внесем ошибку по одному из оснований. Для данного примера я выбрал пятое основание, т.е. 21. В результате ошибки мы получим строку, с которой и будет работать декодер.

Шаг 3 Теперь рассмотрим процесс декодирования: На данном этапе мы хотим выяснить: произошла ли ошибка по какому-либо основанию и если произошла, то исправить эту ошибку. Рассмотрим строку, полученную в результате кодирования и внесения ошибки: $0001 0101 00011 00111 00101 00110$ .

Представим число, соответствующее данной строке, в СОК по нашим модулям: $\bar A=(1, 5, 13, 7, 5, 6)$ . Теперь отбрасываем последовательно по одному основанию и смотрим результат. Если он меньше 67183, то мы принимаем этот результат за исходное число, а по отброшенному основанию произошла ошибка. Пусть мы откидываем первое основание. Тогда по пяти оставшимся мы восстанавливаем число. Получаем систему сравнений: $\left\{ \begin{array}{rcl} x\equiv5 mod(16) \\ x\equiv13 mod(17) \\ x\equiv7 mod(19) \\ x\equiv5 mod(21) \\ x\equiv6 mod(23) \\ \end{array} \right.$

Согласно Китайской Теореме об Остатках данная система имеет одно единственное решение в диапазоне от $0$ до $16*17*19*21*23$

Решением данной системы является число $x=627653$ . Видим, что число находится вне нашего диапазона, а следовательно по одному из неотброшенных оснований произошла ошибка, а по отброшенному основанию ошибки нет.

Теперь отбросим основание $p_2=16$ . Проделывая те же действия, что и для первого основания получим, что $x=1095680$ . Опять мы вышли за допустимый диапазон, а следовательно по второму основанию ошибки нет.

Отбрасывая третье основание $p_3=17$ , получим $x= 1214981$ .

Отбрасывая четвертое основание $p_4=19$ , получим $x= 1415909$

Отбрасывая пятое основание $p_5=21$ , получим $x = 33333$ . Полученное число попадает в динамический диапазон, а следовательно, является нашим верным числом. Таким образом мы нашли и разряд, в котором произошла ошибка, а именно блок, отвечающий за остаток по модулю 21, ведь именно этот блок мы исключили на данном этапе восстановления.

@@ Строка 1: / Строка 1: @@
 == Постановка задачи ==
-В данной статье разбирается пример работы алгоритма коррекции ошибки в одном модулярном канале(аналог исправления ошибки в 4-х битном блоке).
+В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Числовое значение строки представляется в модулярном базисе состоящем из 4-5-битных простых чисел (аналог 4-х битного блока в позиционных кодах). Необходимо отследить и исправить одиночную ошибку, внесённую в один из модулярных каналов.
-Пусть  строка, состоящая из 16 бит. Необходимо отследить и исправить одиночную ошибку, внесённую в данную строку.
-Любой строке из 16 бит можно поставить в соответствие число из диапазона <math>[0...65536)</math>. Далее данное число мы представляем в системе остаточных классов по выбранным нами модулям.
+Любой строке из 16 бит можно поставить в соответствие число из диапазона <math>[0...65536)</math>. Далее данное число мы представляем в системе остаточных классов (СОК) по выбранным нами модулям. Затем, внеся одиночную ошибку в любой модуль мы попробуем исправить её. Алгоритм исправления ошибки заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученного числа.
-Затем, внеся одиночную ошибку в любой модуль мы будем исправлять ее.
-Алгоритм заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученого числа.
+== Теоретические основы алгоритма ==
-==Теоретические основы алгоритма==
+Пусть имеется <math>k</math> взаимно простых чисел <math>p_1,p_2,p_3,...,p_k</math>. Назовём их рабочими основаниями. Известно, что в СОК по данным модулям однозначно представляется число из рабочего диапазона <math>[0...p_1*p_2*...*p_k)</math>. Далее введём два дополнительных взаимно простых основания <math>p_{k+1},p_{k+2}</math> таких, что все <math>k+2</math> полученных оснований <math>p_1,p_2,p_3,...,p_k,p_{k+1},p_{k+2}</math> будут взаимно простыми. Пусть наше исходное число <math>A</math> принадлежит диапазону <math>[0...p_1*p_2*...*p_k)</math>. Если представить его в СОК по модулям <math>\left \{p_1,p_2,p_3,...,p_k,p_{k+1}\right \}</math>, затем внести ошибку по любому из модулей, а потом попытаться восстановить данное число по Китайской Теореме об Остатках, то известно, что результат <math>\bar A>p_1*p_2*...*p_k</math>. Таким образом, имея два контрольных основания мы можем исправлять одиночную ошибку, последовательно исключая по одному из модулей и получая ситуацию, описанную выше. Если мы исключили основание, по которому произошла ошибка, мы получим правильное число, лежащее в пределах диапазона <math>[0...p_1*p_2*...*p_k)</math>.
-Пусть имеется <math>k</math> взаимно простых чисел <math>p_1,p_2,p_3,...,p_k</math>. Назовём их рабочими основаниями. Известно, что в СОК по данным модулям однозначно представляется число из рабочего диапазона <math>[0...p_1*p_2*...*p_k)</math>. Далее введём два дополнительных взаимно простых основания <math>p_{k+1},p_{k+2}</math> таких, что все <math>k+2</math> полученных оснований <math>p_1,p_2,p_3,...,p_k,p_{k+1},p_{k+2}</math> будут взаимно простыми. Пусть наше исходное число <math>A</math> принадлежит диапазону <math>[0...p_1*p_2*...*p_k)</math>. Если представить его в СОК по модулям <math>\left \{p_1,p_2,p_3,...,p_k,p_{k+1}\right \}</math>, затем внести ошибку по любому из модулей, а потом попытаться восстановить данное число по Китайской Теореме об Остатках, то известно, что результат <math>\bar A>p_1*p_2*...*p_k</math>. Таким образом, имея два контрольных основания мы можем исправлять одиночную ошибку, последовательно исключая по одному из модулей, мы получаем ситуацию, описанную выше. Таким образом, если мы исключили основание, по которому произошла ошибка, мы получим правильное число, лежащее в пределах диапазона <math>[0...p_1*p_2*...*p_k)</math>.
-==Пример==
+== Пример ==
-Пусть имеется 16ти битовая строка <math>1000001000110101</math>.Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.
+Пусть имеется 16ти-битная строка <math>1000001000110101</math>. Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.
 '''Шаг 1'''
 Для выполнения данной задачи  выбираем 4 рабочих основания и 2 контрольных.
 Рабочие основания:<math>p_1=13, p_2=16, p_3=17, p_4=19</math>. Контрольные основания: <math>p_5=21, p_6=23</math>.
-При таком выборе рабочих оснований мы можем работать с числами из диапазона  от <math>0</math> до <math>13*16*17*19=67183> 65536</math>. Таким образом, этих рабочих оснований хватит для работы с нашей исходной строкой.
+При таком выборе рабочих оснований мы можем работать с числами из диапазона  от <math>0</math> до <math>13*16*17*19=67183 > 65536</math>. Таким образом, этих рабочих оснований хватит для работы с нашей исходной строкой.
-Выбор таких рабочих обусловлен тем, что полученный динамический диапазон практически совпадает с исходным <math>[0...65536)</math>. Изначально строка содержала 16 бит, но после кодирования ( представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной <math>4+4+5+5+5+5=28</math>.
+Выбор таких рабочих обусловлен тем, что полученный динамический диапазон практически совпадает с исходным <math>[0...65536)</math>. Изначально строка содержала 16 бит, но после кодирования (представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной <math>4+4+5+5+5+5=28</math>.
-Таким образом, избыточность составляет <math>28-16=12</math> бит.
+Таким образом, избыточность составляет <math>28-16=12</math> бит. Представим это число в СОК:
 '''Шаг 2'''
 Процесс кодирования и внесения ошибки:
 Переведем строку <math>1000001000110101</math> в десятичную систему счисления и получим <math>33.333</math>
+Представим это число в СОК по нашим модулям и получим: <math>33.333=(1, 5, 13, 7, 6, 6)</math>. Представим всё это в бинарном виде:
+<math>0001 0101 01101 00111 00110  00110</math>. Это и есть наша закодированная строка. Затем внесем ошибку  по одному из оснований. Для данного примера я выбрал пятое основание, т.е. 21. В результате ошибки мы получим строку, с которой и будет работать декодер.
+[[Изображение:module_error_correction_1.png]]
+'''Шаг 3'''
+Теперь рассмотрим процесс декодирования:
+На данном этапе мы хотим выяснить: произошла ли ошибка по какому-либо основанию и если произошла, то исправить эту ошибку.
+Рассмотрим строку, полученную в результате кодирования и внесения ошибки:
+<math>0001 0101 00011 00111 00101 00110</math>.
+Представим число, соответствующее данной строке, в СОК по нашим модулям:
+<math>\bar A=(1, 5, 13, 7, 5, 6)</math>.
+Теперь отбрасываем последовательно  по одному основанию и смотрим результат. Если он меньше 67183, то мы принимаем этот результат за исходное число, а по отброшенному основанию произошла ошибка. Пусть мы откидываем первое основание. Тогда по пяти оставшимся мы восстанавливаем число. Получаем систему сравнений:
+<math>\left\{
+           \begin{array}{rcl}
+            x\equiv5 mod(16) \\
+            x\equiv13 mod(17) \\
+            x\equiv7 mod(19) \\
+            x\equiv5 mod(21) \\
+            x\equiv6 mod(23) \\
+           \end{array}
+           \right.
+</math>
+Согласно Китайской Теореме об Остатках  данная система имеет одно единственное решение в диапазоне от <math>0</math> до <math>16*17*19*21*23</math>
+Решением данной системы является число <math>x=627653</math>. Видим, что число находится вне нашего диапазона, а следовательно по одному из неотброшенных оснований произошла ошибка, а по отброшенному основанию ошибки нет.
+Теперь отбросим основание <math>p_2=16</math>. Проделывая те же действия, что и для первого основания получим, что <math>x=1095680</math>. Опять мы вышли за допустимый диапазон, а следовательно по второму основанию ошибки нет.
+Отбрасывая третье основание <math>p_3=17</math>, получим <math>x= 1214981</math>.
+Отбрасывая четвертое основание <math>p_4=19</math>,  получим <math>x= 1415909</math>
+Отбрасывая пятое основание <math>p_5=21</math>, получим <math>x = 33333</math>. Полученное число попадает в динамический диапазон, а следовательно, является нашим верным числом.
+Таким образом мы нашли и разряд, в котором произошла ошибка, а именно блок, отвечающий за остаток по модулю 21, ведь именно этот блок мы исключили на данном этапе восстановления.

Пример коррекции ошибки на базе системы остаточных классов

Текущая версия на 16:59, 16 декабря 2013

[править] Постановка задачи

[править] Теоретические основы алгоритма

[править] Пример

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

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

Варианты

Просмотры

Действия

Поиск

Навигация