4.15 Техническая реализация циклических кодов
Для умножения и
деления многочленов, при реализации
кодеров и декодеров циклических кодов,
используются регистры сдвига. Для
умножения применяются обычные регистры,
а для деления на Р(х) – регистры сдвига
с обратными связями. При реализации
кодеков циклических кодов для построения
регистров сдвига с обратными связями
используют три правила:
Число ячеек регистра сдвига с обратными связями равно степени образующего полинома.
Число сумматоров по модулю 2 равно весу образующего полинома минус 1
Сумматоры по модулю 2 ставятся перед не нулевыми членами образующего полинома (сумма по модулю 2 старших разрядов делимого и делителя всегда равна нулю – смотри любой пример)
Построение кодера и декодера рассмотрим на примере.
Пример. Циклический код (7,4),d0=3. Р(х)→ х3+х+1. Построить кодер и декодер
Решение. Структурная схема кодера представлена на рисунке 4.11
Вход Р3 Выход
1 2 3
Кл.1
РС
1 х х2 х3
1 2 3
Кл.2
Рис. 4.11
Схема кодера состоит из регистра задержки и регистра сдвига с обратными связями.
В регистре задержки производится умножение комбинации исходного кода на хr. Число ячеек в РЗ равно степени образующего полинома. У нас r=3 и 3 ячейки в РЗ
В
регистре сдвига (РС) обеспечивается
деление на образующий полином. Число
ячеек РС=3, т.к. r=3;
число
=2, т.к.r=3
и -1=2;
стоят перед х0(1)
и х; перед х3
ставить
не надо.
Работа схемы происходит следующим образом.
Члены исходного полинома Q(х) простого кода вводятся одновременно в РС и РЗ. При этом Кл.1 замкнут, а Кл.2 разомкнут. Из РС выводится остаток от предыдущего деления. Через r тактов (у нас 3) и РЗ, и РС заполнятся и старший член Q(x) окажется в 3 ячейке и РЗ, и РС.
Далее Кл.1 размыкается, а Кл.2 замыкается, создавая цепь обратной связи. С этого момента (с 4 такта) начинается деление Q(x)* хr на Р(х); и вывод информационной части из РЗ. Через k-тактов (у нас k=4) процесс деления в РС закончится, а из РЗ выйдут все информационные разряды.
После этого Кл.1 замыкается, а Кл.2 размыкается. Из РС остаток за r тактов (r=3)передается так в канал. В то же время и РС и РЗ заполняются новой КК простого кода.
Структурная схема декодера представлена на рис. 4.12
Вход РН Выход
12 3 4 5 6 7
1 х х2х3 DC
1 2 3
PC
Рис.4.12
Декодер состоит из регистра накопителя (РН), регистра сдвига (РС), дешифратора и сумматора по модулю 2, исправляющего ошибки.
В РН число ячеек определяется длиной КК циклического кода.
РС строится аналогично РС в кодере.
ДС настроен на синдром, указывающий на ошибки в 7 разряде (старшем).
Алгоритм исправления ошибок в данном случае (при исправлении однократной ошибки) будет проще, чем рассмотренный ранее.
Действительно, можно записать:
F(x)= F(x)+E(x), где
F(x)- принятая КК
F(x)- переданная КК
E(x)- полином, вектор ошибок
Если F(x), то Е(х)=0,т.е. ошибок нет. Единица в Е(х) указывает на номер разряда, где произошла ошибка.
Исправление ошибки происходит следующим образом. Пусть после деления принятой КК получился остаток 101 (смотри образующую матрицу в примере- последняя строка), он соответствует ошибке в старшем разряде (7). В этот момент все 7 разрядов КК будут зафиксированы в РН. Со следующим тактом старший разряд КК поступает в сумматор по модулю 2. дешифратор настроен на эту комбинацию (101). Т.е. на его выходе появится 1. Она складывается со старшим разрядом КК и ошибка исправляется.
Если ошибка произошла во втором от старшего разряде, то на первом такте остаток будет 111 и дешифратор не сработает. Однако на втором такте вектор ошибки опять будет таким же, как и на первом такте. Поэтому и остаток будет 101. Сработает дешифратор и ошибка во втором разряде исправляется.
Также происходит и исправление ошибок в других разрядах.
При реализации дешифраторов для исправления многократных ошибок используется алгоритм в 4.13.