2.2. Проектирование декодеров Меггита

Структурная схема декодера Меггита в режиме исправления ошибок приведена на рис. 2.1.

Рис.2.1. Структурная схема декодирующего устройства Меггита

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

Для исправления однократной ошибки селектор состоит из одного k-входового конъюнктора, который настраивается на выделение ошибки в старшем разряде, т. е. на следующий вектор ошибки (табл. 2.2):

Таблица 2.2

V′	a'0	a'1	…	a'n-1
e	0	0	…	1

Для исправления двукратной ошибки селектор состоит из n k-входовых конъюнкторов. Один элемент настраивается на выделение однократной ошибки в старшем разряде, а (n–1) элементов – на следующие векторы, соответствующие двукратной ошибке (табл. 2.3):

Таблица 2.3

V′	a'0	a'1	…	a'n–2	a'n–1
e	1	0	…	0	1
e	0	1	…	0	1
…	…	…	…	…	…
e	0	0	…	1	1

Для расчета настроек элементов селектора используются соотношения следующего вида:

x^n–1 mod g(x) – для исправления однократной ошибки,

(x^n–1  xⁱ) mod g(x) – для исправления двукратной ошибки (i – номер символа с ошибкой в одном из разрядов: i=0,…, n–2).

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

Поскольку достаточно широкое применение в системах передачи информации нашли коды Хэмминга (d_min = 3,4), то рассмотрим пример структуры и функционирования декодеров Меггита именно для них.

Пример2.2. Для циклического кода (7,4,3) и проверочного полинома g(x) = 1  x²  x³ построить декодер Меггита. Структурная схема декодера Меггита будет выглядеть следующим образом (рис. 2.2).

Рис. 2.2. Структурная схема декодирующего устройства Меггита для БЧХ-кода (7,4,3)

Рассчитаем настройку селектора в схеме без предварительного умножения на x^k: r₆(x) = x^n–1 mod g(x) = x  x².

Первые 7 тактов происходит заполнение буферного регистра полиномом V'(x). Одновременно осуществляется вычисление синдрома S(x). Если после 7-го такта элементы памяти генератора синдрома обнулились, значит, ошибок в принятом векторе нет, или кратность ошибки превышает корректирующую способность кода. Если в элементах памяти генератора синдрома находится ненулевой остаток, то деление продолжается дальше. При этом открывается ключ, давая возможность селектору исправить ошибку. На том такте, когда ошибочный разряд попадает в старший (n – 1) разряд буферного регистра, комбинация вектора синдрома S₀,…, S_k–1 совпадает с настройкой селектора. Это означает, что выход селектора устанавливается равным 1. Тогда на следующем такте ошибочный разряд, выдвигаясь из старшего разряда БР, складывается по модулю 2 с выходом селектора, что эквивалентно инверсии ошибочного символа (исправлению ошибки). После этого элементы памяти генератора синдрома обнуляются сигналом Reset.

Номер такта, на котором сработает селектор, определяется следующим образом:

2n – i –1, (2.5)

где i – номер ошибочного разряда.

Соответственно, номер такта, на котором произойдет исправление ошибки,

2n – i. (2.6)

Запишем функции возбуждения для элементов памяти ГС РССЛОС:

Промоделируем работу декодирующего устройства для полинома V(x) = 1  x²  x³ при однократной ошибке в разряде a₃ (полином ошибки e(x) = x³). В этом случае полином V'(x) будет выглядеть так: V`(x) = V(x)   e(x) = 1  x²  x³  x³ = 1  x². Согласно предварительным расчетам селектор сработает (ошибочный разряд a₃ попадает в старший разряд буферного регистра) на такте с номером: 27 – 3 – 1 = 10. Исправление произойдет на следующем такте, т. е. на такте с номером: 27 – 3 = 11. На этом такте произойдет обнуление элементов памяти генератора синдрома.

Промоделируем работу декодера, подав на вход вектор V' и вектор ошибки e (табл. 2.4).

Таблица 2.4

№ такта	V'	D0	D1	D2		№ такта	e	D0	D1	D2
		0	0	0				0	0	0
1	0	0	0	0		1	0	0	0	0
2	0	0	0	0		2	0	0	0	0
3	0	0	0	0		3	0	0	0	0
4	0	0	0	0		4	1	1	0	0
5	1	1	0	0		5	0	0	1	0
6	0	0	1	0		6	0	0	0	1
7	1	1	0	1		7	0	1	0	1
8	0	1	1	1		8	0	1	1	1
9	0	1	1	0		9	0	1	1	0
10	0	0	1	1		10	0	0	1	1
11	0	0	0	0		11	0	0	0	0

Пример2.3. Для циклического кода (7,3,4) и проверочного полинома g(x) = (1  x²  x³) построить декодер Меггита. Структурная схема декодера Меггита приведена на рис. 2.3.

Рис. 2.3. Структурная схема декодирующего устройства Меггита для БЧХ-кода (7,3,4)

Для кода Хемминга с d_min = 4 генератор синдрома строится по схеме раздельного деления полинома V'(x) на g(x) и на (1  x) . Поэтому все расчеты селектора для исправления однократной ошибки проводятся аналогично предыдущему примеру.

Рассчитаем настройку селектора в схеме без предварительного умножения на x^k: r₆(x)=x^n–1 mod g(x)=xx².

Первые 7 тактов происходит заполнение буферного регистра полиномом V'(x). Одновременно осуществляется вычисление синдрома S(x). Если после 7-го такта элементы памяти генератора синдрома обнулились, значит, ошибок в принятом векторе нет, или кратность ошибки превышает корректирующую способность кода. Синдром S₃ контролирует кратность ошибки (S₃ = 1 – однократная ошибка, S₃ = 0 – двукратная ошибка (или ошибок нет)). При однократной ошибке деление продолжается дальше. При этом открывается ключ к₁, давая возможность селектору исправить ошибку. На том такте, когда ошибочный разряд попадает в старший (n–1)-й разряд буферного регистра, комбинация вектора синдрома S₀,…, S_k–1 совпадает с настройкой селектора. Это означает, что выход селектора устанавливается равным «1». Тогда на следующем такте ошибочный разряд, выдвигаясь из старшего разряда БР, складывается по модулю 2 с выходом селектора, что эквивалентно инверсии ошибочного символа (исправлению ошибки). После этого элементы памяти генератора синдрома обнуляются сигналом Reset.

В случае возникновения двукратной ошибки после n-го такта синдром S₃ будет равен «0». При этом выполнятся все необходимые условия для формирования сигнала стирания (Erase), поскольку хотя бы один из синдромов {S₀, S₁, S₂} будет равен «1». Поэтому через открывшийся на (n+1)-м такте ключ к₂ на вход буферного регистра будет подан сигнал стирания, который его обнулит.

Номер такта, на котором сработает селектор в режиме исправления ошибки, определяется по формуле (2.5). Соответственно, номер такта, на котором произойдет исправление ошибки, определяется по формуле (2.6).

Запишем функции возбуждения для элементов памяти ГС РССЛОС:

Промоделируем работу декодирующего устройства для полинома V(x) = 1  x²  x³ при однократной ошибке в разряде a₃ (полином ошибки e(x) = x³) и двукратной ошибке в разрядах a₃ и a₀ (полином ошибки e(x) = = x³  1). Результаты моделирования сведем в табл. 2.5.

Таблица. 2.5

№ такта	e	D0	D1	D2	D3		№ такта	e	D0	D1	D2	D3
		0	0	0	0				0	0	0	0
1	0	0	0	0	0		1	0	0	0	0	0
2	0	0	0	0	0		2	0	0	0	0	0
3	0	0	0	0	0		3	0	0	0	0	0
4	1	1	0	0	1		4	1	0	0	0	1
5	0	0	1	0	1		5	0	0	1	0	1
6	0	0	0	1	1		6	0	0	0	1	1
7	0	1	0	1	1		7	1	0	0	1	0
8	0	1	1	1	1		8	0	0	0	0	0
9	0	1	1	0	1
10	0	0	1	1	1
11	0	0	0	0	0

Моделирование показало правильность предварительных расчетов и построения декодера.