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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «== Введение == В данной статье разбирается пример работы алгоритма коррекции одиночной ош…»)
 
 
(не показаны 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Введение ==
+
== Постановка задачи ==
В данной статье разбирается пример работы алгоритма коррекции одиночной ошибки, основанного на использовании избыточной системы остаточных классов.
+
В данной статье разбирается пример работы алгоритма коррекции ошибки для 16-битных строк. Числовое значение строки представляется в модулярном базисе состоящем из 4-5-битных простых чисел (аналог 4-х битного блока в позиционных кодах). Необходимо отследить и исправить одиночную ошибку, внесённую в один из модулярных каналов.
Имеется  строка <math>1000001000110101</math>, состоящая из 16 бит. Необходимо отследить и исправить одиночную ошибку, внесённую в данную строку.
+
 
==Теоретические основы алгоритма==
+
Любой строке из 16 бит можно поставить в соответствие число из диапазона <math>[0...65536)</math>. Далее данное число мы представляем в системе остаточных классов (СОК) по выбранным нами модулям. Затем, внеся одиночную ошибку в любой модуль мы попробуем исправить её. Алгоритм исправления ошибки заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученного числа.
Пусть имеется <math>n</math> взаимно простых модулей <math>p_1,p_2,p_3,...,p_n</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>. Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.
 +
 
 +
'''Шаг 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...65536)</math>. Изначально строка содержала 16 бит, но после кодирования (представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной <math>4+4+5+5+5+5=28</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

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

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

Module error correction 1.png

Шаг 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, ведь именно этот блок мы исключили на данном этапе восстановления.


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

Варианты
Действия
Навигация