С предварительным умножением на x3

Функции возбуждения для элементов памяти:

Промоделируем работу кодера и занесем результаты в таблицу переходов и выходов (табл. 1.3).

Таблица 1.3

№ такта	u	D0	D1	D2	V
		0	0	0
1	0	0	0	0	0	У = 1:
2	0	0	0	0	0	к1 открыт,
3	0	0	0	0	0	к2 закрыт
4	1	1	0	1	1
5	0	0	1	0	1	У = 0:
6	0	0	0	1	0	к1 закрыт,
7	0	0	0	0	1	к2 открыт

Моделирование показало, что к такту с номером m = 4 в элементах памяти регистра сформировалась избыточная часть r(x) = 1  x², а к такту с номером n = 7 в канал связи передан полином V(x) = 1  x²  x³.

Достоинством рассмотренной схемы кодирующего устройства является отсутствие временной задержки и, соответственно, отсутствие дополнительного элемента задержки.

Способы построения кодирующих устройств для кодов с четным минимальным кодовым расстоянием не имеют принципиальных отличий от рассмотренных, за тем исключением, что для построения РСЛЛОС применяется порождающий полином g(x)(1  x).

Способы построения кодирующих устройств для укороченных кодов также не имеют принципиальных отличий от рассмотренных, поскольку порождающий полином для укороченного и табличного кодов совпадают.

2. Декодирование циклических кодов (бчх-кодов)

2.1. Принципы декодирования бчх-кодов по алгоритму Меггита (декодер Меггита)

Синдромное декодирование для БЧХ-кодов наиболее эффективно реализуется при помощи алгоритма, предложенного американским ученым Меггитом. Поясним декодирование по алгоритму Меггита на самом простом примере – исправлении однократной ошибки (s = 1), а затем распространим приведенные соображения на произвольное значение s.

Предположим, что однократная ошибка исказила разряд (полином ошибки e(x) = xⁱ). При циклическом сдвиге вектора V' в сторону старших разрядов, что эквивалентно умножению полинома на x, ошибочный разряд будет также смещаться. При этом за счет замкнутости векторного пространства БЧХ-кодов относительно операции циклического сдвига (Т) старший разряд всегда будет присутствовать у слагаемого x^n–1. До позиции старшего разряда ошибочный разряд дойдет в результате умножения полинома на величину x^n–1–i. При попадании ошибочного разряда в старший разряд полином ошибки может быть представлен как e(x) = = x^n–1. На этот единственный вариант полинома ошибки и настраивается декомбинатор синдрома. Для декодера Меггита декомбинатор синдрома принято называть селектор. Количество элементов в селекторе, настроенном на исправление однократной ошибки, равно 1. Настройка селектора определяется как

r_n–1(x)  xⁱ  x^n–1–i = x^n–1 mod g(x). (2.1)

Декодирование происходит следующим образом. После приема из канала связи полинома , т. е. начиная с (n+1)-го такта, последовательно производится его домножение на x. После каждой операции домножения, что эквивалентно циклическому сдвигу вектора V', соответственно и вектора ошибки на один разряд, производится определение синдрома S(x). Оно осуществляется путем вычисления остатка от деления полинома x^j–1 на порождающий полином g(x), где j – номер этапа домножения (j = 1,2,…). После вычисления значение S(x) сравнивается с настройкой декомбинатора синдрома r_n–1(x). Совпадение полиномов S(x) и r_n–1(x) означает, что ошибочный разряд находится в старшем разряде. Значит, на следующем такте он должен быть исправлен. Номер этапа, на котором произойдет исправление ошибки, определяется следующим образом: 2n–i, где i – номер ошибочного разряда.

В случае двукратной ошибки полином e(x) содержит два ненулевых компонента: e(x) = xⁱ  x^j. В результате циклического сдвига через какое-то количество тактов полином ошибки будет выглядеть следующим образом: e(x) = x^l  x^n–1, т. е. одна из ошибок располагается в старшем разряде, а вторая – где-то в остальной части полинома. Очевидно, что количество вариантов расположения второй ошибки равно (n – 1). После исправления ошибки в старшем разряде полином ошибки становится равным e(x) = x^l, и далее происходит исправление однократной ошибки. Количество вариантов значений синдрома, как уже рассматривалось ранее, равно 1. Следовательно, для исправления двукратной ошибки количество элементов в селекторе должно быть N = n – 1 + 1 = n.

Для общего случая сложность (количество k-входовых конъюнкторов) селектора можно оценить следующим образом:

(2.2)

В качестве примера сравним сложность селектора в составе декодера Меггита (N_M) и со сложностью декомбинатора синдрома (N_ДС) в составе декодера, реализующего общий (традиционный) подход к синдромному декодированию (табл. 2.1).

Таблица 2.1

S	Код	NСД	NМ
1	(15,11,3)	15	1
2	(15,7,5)	120	15
3	(15,3,7)	575	106
…	…	…	…

На основании анализа таблицы можно сделать вывод, что алгоритм Меггита дает значительное упрощение декомбинатора синдрома, и с увеличением длины кода n выигрыш увеличивается. Это является существенным достоинством алгоритма Меггита, что повлекло за собой его широкое практическое применение.

Исправление ошибки происходит с (n+1)-го по (2n)-й такты работы декодирующего устройства. Поэтому недостатком алгоритма Меггита является то, что появляется задержка на n тактов, необходимая для сдвига вектора ошибки в сторону старшего разряда. В то же время следует отметить, что сложность декодера Меггита, определяемая сложностью селектора ошибок, все еще велика (хотя и существенно ниже декодера, реализующего традиционный подход к синдромному декодированию). Это обусловило поиск иных алгоритмов декодирования циклических кодов. В частности, получили развитие алгебраические алгоритмы декодирования БЧХ-кодов (алгоритм Берлекэмна с процедурой Чена, алгоритм Питерсона и др.).

Пример 2.1. Рассчитать значения настройки селектора и синдрома для циклического кода (7,4,3) и порождающего полинома g(x) = 1  x²  x³.

Настройка селектора производится на полином ошибки e(x) = x⁶ (ошибка в старшем разряде a₆): r₆(x)  x⁶ mod (1  x²  x³) = x  x².

Рассчитаем синдром для полинома V(x) = 1  x²  x³ (информационный полином u(x) = 1) и полинома ошибки e(x) = x⁴. В результате воздействия полинома ошибки принят полином V'(x) = V(x)  e(x) = 1  x²  x³  x⁴. Рассчитаем синдромы S(x).

1. Для S(x)  x⁰V'(x) mod (1  x²  x³) = x. С настройкой селектора не совпадает, поэтому можно сделать вывод о том, что в старшем разряде a₆ ошибки нет.

2. Для S(x)  x¹V'(x) mod (1  x²  x³) = 1  x. С настройкой селектора не совпадает, поэтому можно сделать вывод о том, что в старшем разряде a₅ ошибки нет.

3. Для S(x)  x²V'(x) mod (1  x²  x³) = x  x². С настройкой селектора совпадает, поэтому можно сделать вывод о том, что ошибка в разряде a₄.

Номер этапа, на котором ошибочный разряд попадает в старший разряд, определяется как: n – 1 – j = 7 – 1 – 3 = 3.

Номер этапа, на котором исправляется ошибка, определяется как n – 1 – (j – 1) = 7 – 1 – 3 + 1 = 4. Напоминаем, что речь идет об этапах циклического сдвига полинома V'(x), при этом 1-й этап соответствует n-му такту работы декодера. Для ошибок большей кратности расчеты и моделирование осуществляются аналогично.

Рассмотренный принцип декодирования Меггита обладает также следующим недостатком. Он заключается в однозначной зависимости настройки селектора от длины кода n. Это означает, что для укороченных циклических кодов необходимо производить перерасчет настройки селектора для разных значений n. Для нивелирования указанного недостатка применяется метод, в котором при расчете синдрома полином V'(x) предварительно умножается на величину x^k. При этом настройка селектора, определяемая из соображений, что ошибочный разряд в результате циклического сдвига находится в старшем разряде, осуществляется следующим образом:

r_n–1(x)  xⁱ  x^n–1–i  x^k = x^{i–n–1–i+k} = xⁿ  x^k–1 = x^k–1 mod g(x). (2.3)

Очевидно, что такая настройка селектора не зависит от длины вектора n, а определяется только длиной избыточной части k, которая для укороченных кодов не изменяется, т. е. является универсальной для всех укороченных кодов. Такой способ декодирования получил название «декодирование с предварительным умножением на x^k». Поскольку степень порождающего полинома g(x) равна k, то настройка селектора просто равна x^k–1.

В общем случае (для укороченных и неукороченных кодов) для построения декодера Меггита с универсальной настройкой селектора необходимо внести дополнения в структуру генератора синдрома. Указанные изменения вносятся с учетом вида дополнительного полинома d(x), который определяется следующим образом:

d(x)=x^i+k mod g(x), (2.4)

где i – количество символов, на которые был укорочен код. Как вид дополнительного полинома d(x) влияет на структуру декодера, укажем при рассмотрении вопросов построения декодирующих устройств. Как будет показано ниже, для неукороченных кодов дополнительный полином d(x) не влияет на структуру декодера.