Пример коррекции ошибки на базе системы остаточных классов
AlexT (обсуждение | вклад) |
AlexT (обсуждение | вклад) |
||
Строка 6: | Строка 6: | ||
Алгоритм заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученого числа. | Алгоритм заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученого числа. | ||
==Теоретические основы алгоритма== | ==Теоретические основы алгоритма== | ||
− | Пусть имеется <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>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>.Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку. | ||
Строка 15: | Строка 15: | ||
При таком выборе рабочих оснований мы можем работать с числами из диапазона от <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''' | '''Шаг 2''' | ||
Процесс кодирования и внесения ошибки: | Процесс кодирования и внесения ошибки: | ||
Переведем строку <math>1000001000110101</math> в десятичную систему счисления и получим <math>33.333</math> | Переведем строку <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, ведь именно этот блок мы исключили на данном этапе восстановления. |
Версия 13:46, 16 декабря 2013
Постановка задачи
В данной статье разбирается пример работы алгоритма коррекции ошибки в одном модулярном канале(аналог исправления ошибки в 4-х битном блоке). Пусть строка, состоящая из 16 бит. Необходимо отследить и исправить одиночную ошибку, внесённую в данную строку. Любой строке из 16 бит можно поставить в соответствие число из диапазона . Далее данное число мы представляем в системе остаточных классов по выбранным нами модулям. Затем, внеся одиночную ошибку в любой модуль мы будем исправлять ее. Алгоритм заключается в следующем: последовательно исключаем из рассмотрения один из модулей, восстанавливаем число по Китайской Теореме об Остатках и смотрим на величину полученого числа.
Теоретические основы алгоритма
Пусть имеется взаимно простых чисел . Назовём их рабочими основаниями. Известно, что в СОК по данным модулям однозначно представляется число из рабочего диапазона . Далее введём два дополнительных взаимно простых основания таких, что все полученных оснований будут взаимно простыми. Пусть наше исходное число принадлежит диапазону . Если представить его в СОК по модулям , затем внести ошибку по любому из модулей, а потом попытаться восстановить данное число по Китайской Теореме об Остатках, то известно, что результат . Таким образом, имея два контрольных основания мы можем исправлять одиночную ошибку, последовательно исключая по одному из модулей и получая ситуацию, описанную выше. Если мы исключили основание, по которому произошла ошибка, мы получим правильное число, лежащее в пределах диапазона .
Пример
Пусть имеется 16ти битовая строка .Мы ставим ей в соответствие число, затем представляем его в Системе Остаточных Классов, вносим ошибку по одному из оснований и исправляем эту ошибку.
Шаг 1 Для выполнения данной задачи выбираем 4 рабочих основания и 2 контрольных. Рабочие основания:. Контрольные основания: . При таком выборе рабочих оснований мы можем работать с числами из диапазона от до . Таким образом, этих рабочих оснований хватит для работы с нашей исходной строкой. Выбор таких рабочих обусловлен тем, что полученный динамический диапазон практически совпадает с исходным . Изначально строка содержала 16 бит, но после кодирования ( представления строки в СОК и перевода обратно в двоичную системы) мы получим строку длиной . Таким образом, избыточность составляет бит. Представим это число в СОК:
Шаг 2 Процесс кодирования и внесения ошибки: Переведем строку в десятичную систему счисления и получим
Представим это число в СОК по нашим модулям и получим: . Представим всё это в бинарном виде: . Это и есть наша закодированная строка. Затем внесем ошибку по одному из оснований. Для данного примера я выбрал пятое основание, т.е. 21. В результате ошибки мы получим строку, с которой и будет работать декодер.
Шаг 3 Теперь рассмотрим процесс декодирования: На данном этапе мы хотим выяснить: произошла ли ошибка по какому-либо основанию и если произошла, то исправить эту ошибку. Рассмотрим строку, полученную в результате кодирования и внесения ошибки: .
Представим число, соответствующее данной строке, в СОК по нашим модулям: . Теперь отбрасываем последовательно по одному основанию и смотрим результат. Если он меньше 67183, то мы принимаем этот результат за исходное число, а по отброшенному основанию произошла ошибка. Пусть мы откидываем первое основание. Тогда по пяти оставшимся мы восстанавливаем число. Получаем систему сравнений:
Согласно Китайской Теореме об Остатках данная система имеет одно единственное решение в диапазоне от до
Решением данной системы является число . Видим, что число находится вне нашего диапазона, а следовательно по одному из неотброшенных оснований произошла ошибка, а по отброшенному основанию ошибки нет.
Теперь отбросим основание . Проделывая те же действия, что и для первого основания получим, что . Опять мы вышли за допустимый диапазон, а следовательно по второму основанию ошибки нет.
Отбрасывая третье основание , получим .
Отбрасывая четвертое основание , получим
Отбрасывая пятое основание , получим . Полученное число попадает в динамический диапазон, а следовательно, является нашим верным числом. Таким образом мы нашли и разряд, в котором произошла ошибка, а именно блок, отвечающий за остаток по модулю 21, ведь именно этот блок мы исключили на данном этапе восстановления.