Декодирование циклических кодов
Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.
1100001
1011
1110
1011
1010
1011
011 ошибка в четвертом разряде
Если ошибка содержится в одном из поверочных разрядов, то одночлен одиночной ошибки будет иметь степень, меньшую, чем степень образующего многочлена и совпадет с остатком от деления. При этом номер разряда остатка прямо укажет на номер искаженного поверочного разряда.
1101011
1011
1100
1011
1111
1011
1001
1011
010 ошибка во 2м контрольном разряде
Существует более общий алгоритм обнаружения и исправления ошибок:
Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.
Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.
Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x) и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.
Пример 6.7. Необходимо проверить принятый код 1101110, для g(x)=1011 и t=1.
Принятый код 1101110 делим на g(x), находим остаток R(x)=111, w=3
Код 1101110 сдвигаем влево на один разряд, получаем 1011101. Делим на образующий многочлен g(x). Находим остаток R(x)=101, вес w=2
Снова производим сдвиг влево, получаем 0111011. Делим на g(x). Остаток R(x)=001. w=1
Складываем сдвинутую комбинацию с остатком 0111011+001=0111010
Производим два циклических сдвига вправо
0111010 > 0011101 >1001110
В результате получили исправленную комбинацию.
Аппаратурная реализация циклических кодов.
Циклические коды реализуются с помощью сдвиговых регистров.
Схема кодирования (образуется с помощью деления на образующий многочлен):
Р
ис.
6.7. Схема кодирования
Ключи к1 и к2 первоначально замкнуты, а ключ к3 – разомкнут. Исходная комбинация через ключ к1 поступает на выход и через входной сумматор на сдвиговый регистр, где и образуется контрольные символы. Затем ключ к2 замыкается, а к1 и к3 размыкаются. Контрольные символы подаются на выход в след, за информационными символами.
Р
ис.6.8.
Схема кодирования методом деления на
образующий многочлен g(x)=x3+x+1
Вх. |
1 |
2 |
3 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
Последовательность деления представлена в таблице.
В результате на выходе будет получена комбинация
1101001
Пример 6.9. Пусть на вход подается комбинация 1001
Вх. |
1 |
2 |
3 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
Схема декодирования (образуется с помощью деления на образующий многочлен):
Рис. 6.9. Схема декодирования циклического кода. АО анализатор ошибок.
Исходная комбинация подается в буферный регистр и одновременно через ключ в декодирующий регистр. Если с приходом последнего символа, зафиксирован нулевой остаток, то ошибок нет, и, если не нулевой, то есть ошибка.
П
ринятая
комбинация подается через выходной
сумматор, и искаженный сигнал исправляется
анализатором ошибок (АО).
Рис.
6.10. Пример схемы декодирования методом
деления на полином
Пример
6.10. Пусть
декодирующий регистр построен методом
деления на образующий полином
.