Декодирование циклических кодов
Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.
1011
1011
1011
011 - ошибка в четвертом разряде
Если ошибка содержится в одном из поверочных разрядов, то одночлен одиночной ошибки будет иметь степень, меньшую, чем степень образующего многочлена и совпадет с остатком от деления. При этом номер разряда остатка прямо укажет на номер искаженного поверочного разряда.
1011
1011
1011
1011
010 - ошибка во 2-м контрольном разряде
Существует более общий алгоритм обнаружения и исправления ошибок:
1. Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.
2. Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.
3. Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x) и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.
Пример 5.7. Необходимо проверить принятый код 1101110, для g(x)=1011 и t=1.
1. Принятый код 1101110 делим на g(x), находим остаток R(x)=111, w=3
2. Код 1101110 сдвигаем влево на один разряд, получаем 1011101. Делим на образующий многочлен g(x). Находим остаток R(x)=101, вес w=2
3. Снова производим сдвиг влево, получаем 0111011. Делим на g(x). Остаток R(x)=001. w=1
4. Складываем сдвинутую комбинацию с остатком 0111011+001=0111010
5. Производим два циклических сдвига вправо
0111010 -> 0011101 ->1001110
В результате получили исправленную комбинацию.
Аппаратурная реализация циклических кодов
Циклические коды реализуются с помощью сдвиговых регистров. Схема кодирования (образуется с помощью деления на образующий многочлен):
Рис. 5.7. Схема кодирования
Ключи к1 и к2 первоначально замкнуты, а ключ к3 – разомкнут. Исходная комбинация через ключ к1 поступает на выход и через входной сумматор на сдвиговый регистр, где и образуется контрольные символы. Затем ключ к2 замыкается, а к1 и к3 размыкаются. Контрольные символы подаются на выход в след, за информационными символами.
Рис.5.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
Пример 5.8. Пусть на вход подается комбинация 1101. Последовательность деления представлена в таблице. В результате на выходе будет получена комбинация 1101001
Пример 5.9. Пусть на вход подается комбинация 1001. В результате деления будет получена комбинация 1001011
Вх 1 2 3
1 1 1 0
1 1 0 1
0 1 0 0
1 1 0 0
Схема декодирования (образуется с помощью деления на образующий многочлен):
Рис.5.9. Схема декодирования циклического кода. АО - анализатор ошибок.
Исходная комбинация подается в буферный регистр и одновременно через ключ в декодирующий регистр. Если с приходом последнего символа, зафиксирован нулевой остаток, то ошибок нет, и, если не нулевой, то есть ошибка. Принятая комбинация подается через выходной сумматор, и искаженный сигнал исправляется анализатором ошибок (АО).
Рис.5.10. Пример схемы декодирования методом деления на полином
Пример 5.10. Пусть декодирующий регистр построен методом деления на образующий полином .
Пусть на вход подается комбинация 1101001
Вх 1 2 3
1 1 0 0
1 1 1 0
0 0 1 1
1 0 1 1
0 1 1 1
0 1 0 1
1 0 0 0
В результате деления получился нулевой остаток, следовательно, ошибок нет.
Теперь пусть на вход подается комбинация с ошибкой 1100001
Вх 1 2 3
1 1 0 0
1 1 1 0
0 0 1 1
0 1 1 1
0 1 0 1
0 1 0 0
1 1 1 0
В результате получился не нулевой остаток 110. Отключим ключ и начнем выводить комбинацию из буферного регистра. На четвертом такте
№ 1 2 3
--- 1 1 0
1 0 1 1
2 1 1 1
3 1 0 1
4 1 0 0
анализатор ошибок подаст на выходной сумматор сигнал исправления. Ошибка будет исправлена.
Для исправления многократных ошибок используется произведение образующих многочленов:
Таблица 5.3. Неприводимые полиномы
g(x) | полином | g(x) | полином |
g(x) | x+1 | g1(x6) | x6+x+1 |
g(x2) | x2+x+1 | g2(x6) | x6+x3+1 |
g1(x3) | x3+x1+1 | g3(x6) | x6+x5+1 |
g2(x3) | x3+x2+1 | …………… | …………… |
g1(x4) | x4+x+1 | g1(x7) | x7+x+1 |
g2(x4) | x4+x3+1 | g2(x7) | x7+x3+1 |
g3(x4) | x4+x3+x2+x+1 | g3(x7) | x7+x3+x2+x+1 |
g1(x5) | x5+x2+1 | …………… | …………… |
g2(x5) | x5+x3+1 | g1(x8) | x8+x4+x3+x+1 |
g3(x5) | x5+x3+x4+x+1 | g2(x8) | x8+x4+x3+x2+1 |
g4(x5) | x5+x4+x2+x+1 | …………… | …………… |
g5(x5) | x5+x4+x3+x+1 | g1(x9) | x9+ x+1 |
g6(x5) | x5+x4+x3+x2+1 | g2(x9) | x9+x4+ 1 |