Итеративные коды

Техническая реализация циклических кодов

Для умножения и деления многочленов, при реализации кодеров и декодеров циклических кодов, используются регистры сдвига. Для умножения применяются обычные регистры, а для деления на Р(х) – регистры сдвига с обратными связями. При реализации кодеков циклических кодов для построения регистров сдвига с обратными связями используют три правила:

1. Число ячеек регистра сдвига с обратными связями равно степени образующего полинома.

2. Число сумматоров по модулю 2 равно весу образующего полинома минус 1

3. Сумматоры по модулю 2 ставятся перед не нулевыми членами образующего полинома (сумма по модулю 2 старших разрядов делимого и делителя всегда равна нулю – смотри любой пример)

Построение кодера и декодера рассмотрим на примере.

Пример. Циклический код (7,4),d₀=3. Р(х)→ х³+х+1. Построить кодер и декодер

Решение. Структурная схема кодера представлена на рисунке 4.11

Вход Р3 Выход

1 2 3

Кл.1

РС

1 х х² х³

1 2 3

Кл.2

Рис. 4.11

Схема кодера состоит из регистра задержки и регистра сдвига с обратными связями.

В регистре задержки производится умножение комбинации исходного кода на х^r. Число ячеек в РЗ равно степени образующего полинома. У нас r=3 и 3 ячейки в РЗ

В регистре сдвига (РС) обеспечивается деление на образующий полином. Число ячеек РС=3, т.к. r=3; число =2, т.к. r=3 и -1=2; стоят перед х⁰(1) и х; перед х³ ставить не надо.

Работа схемы происходит следующим образом.

Члены исходного полинома Q(х) простого кода вводятся одновременно в РС и РЗ. При этом Кл.1 замкнут, а Кл.2 разомкнут. Из РС выводится остаток от предыдущего деления. Через r тактов (у нас 3) и РЗ, и РС заполнятся и старший член Q(x) окажется в 3 ячейке и РЗ, и РС.

Далее Кл.1 размыкается, а Кл.2 замыкается, создавая цепь обратной связи. С этого момента (с 4 такта) начинается деление Q(x)* х^r на Р(х); и вывод информационной части из РЗ. Через k-тактов (у нас k=4) процесс деления в РС закончится, а из РЗ выйдут все информационные разряды.

После этого Кл.1 замыкается, а Кл.2 размыкается. Из РС остаток за r тактов (r=3)передается так в канал. В то же время и РС и РЗ заполняются новой КК простого кода.

Структурная схема декодера представлена на рис. 4.12

Вход РН Выход

1 2 3 4 5 6 7

1 х х² х³ 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.

Итеративные или матричные коды характеризуются наличием двух или более систем проверок внутри каждой КК.

Принцип построения итеративного кода рассмотрим на примере

Пример запишем КК простого кода, предназначенные для передачи, в виде матрицы:

четность

1 0 1 1 1 0

0 0 1 0 0 1

1 1 1 0 0 1

нечет. 0 1 0 0 1 0

1 1 1 1 0 0

0 0 1 1 1 0

Закодируем каждую строку этой таблицы каким - либо кодом, а затем закодируем (не обязательно этим же кодом) каждый столбец таблицы. Например, строки закодируем кодом с четным числом единиц, а столбцы – с нечетным числом единиц.

Полученная комбинация (вся таблица) есть КК простейшего двухмерного итеративного кода, проверочные разряды которого сосредоточены в правом столбце и нижней строке. Каждый информационный разряд этого кода входит в комбинацию двух кодов – кода с четным числом единиц и кода с нечетным числом единиц.

Передача КК итеративного кода обычно происходит по строкам последовательно от первой строки к последней.

Могут быть образованы и многомерные итеративные коды, систематические и несистематические итеративные коды.

Параметры итеративных кодов определяются:

где n_i, k_i, d_0i,- параметры итеративных кодов

S – кратность итерирования

Поэтому итеративный код из нашего примера имеет d₀ =4 и обнаруживает ошибки кратности до 3. Кроме того, этот код обнаруживает все ошибки нечетной кратности.

Метод исправления ошибок следующий. Если не выполняются проверки для i-ой строки и j-го столбца, то элемент, стоящий на пересечении этих строки и столбца, заменяется на обратный.

Итеративные коды исправляют пачки ошибок длиной l+1, где l – длина строки матрицы.

Недостатком является высокая избыточность – 15-20%. Значительно превышает избыточность циклических кодов.

Используются при программной реализации кодирования и декодирования, т.е. в системах ПДС между ЭВМ, если эти ЭВМ обеспечивают повышение верности.