ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.06.2019
Просмотров: 673
Скачиваний: 11
В случае двукратной ошибки полином e(x) содержит два ненулевых компонента: e(x) = xi xj. В результате циклического сдвига через какое-то количество тактов полином ошибки будет выглядеть следующим образом: e(x) = xl xn–1, т. е. одна из ошибок располагается в старшем разряде, а вторая – где-то в остальной части полинома. Очевидно, что количество вариантов расположения второй ошибки равно (n – 1). После исправления ошибки в старшем разряде полином ошибки становится равным e(x) = xl, и далее происходит исправление однократной ошибки. Количество вариантов значений синдрома, как уже рассматривалось ранее, равно 1. Следовательно, для исправления двукратной ошибки количество элементов в селекторе должно быть N = n – 1 + 1 = n.
Для общего случая сложность (количество k-входовых конъюнкторов) селектора можно оценить следующим образом:
(2.2)
В качестве примера сравним сложность селектора в составе декодера Меггита (NM) и со сложностью декомбинатора синдрома (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 x2 x3.
Настройка селектора производится на полином ошибки e(x) = x6 (ошибка в старшем разряде a6): r6(x) x6 mod (1 x2 x3) = x x2.
Рассчитаем синдром для полинома V(x) = 1 x2 x3 (информационный полином u(x) = 1) и полинома ошибки e(x) = x4. В результате воздействия полинома ошибки принят полином V'(x) = V(x) e(x) = 1 x2 x3 x4. Рассчитаем синдромы S(x).
1. Для S(x) x0V'(x) mod (1 x2 x3) = x. С настройкой селектора не совпадает, поэтому можно сделать вывод о том, что в старшем разряде a6 ошибки нет.
2. Для S(x) x1V'(x) mod (1 x2 x3) = 1 x. С настройкой селектора не совпадает, поэтому можно сделать вывод о том, что в старшем разряде a5 ошибки нет.
3.
Для
S(x)
x2V'(x)
mod (1
x2
x3)
= x
x2.
С
настройкой
селектора совпадает,
поэтому можно сделать вывод о том, что
ошибка в разряде
a4.
Номер этапа, на котором ошибочный разряд попадает в старший разряд, определяется как: n – 1 – j = 7 – 1 – 3 = 3.
Номер
этапа, на котором исправляется ошибка,
определяется как
n
–
1 – (j
–
1) =
7
– 1 – 3 + 1 = 4. Напоминаем, что речь идет
об этапах циклического сдвига полинома
V'(x),
при этом 1-й этап соответствует
n-му
такту работы декодера. Для ошибок большей
кратности расчеты и моделирование
осуществляются аналогично.
Рассмотренный
принцип декодирования Меггита обладает
также следующим недостатком. Он
заключается в однозначной зависимости
настройки селектора от длины кода n.
Это означает, что для укороченных
циклических кодов необходимо производить
перерасчет настройки селектора для
разных значений n.
Для нивелирования указанного недостатка
применяется метод, в котором при расчете
синдрома полином V'(x)
предварительно умножается на величину
xk.
При этом настройка селектора, определяемая
из соображений, что ошибочный разряд в
результате циклического сдвига находится
в старшем разряде, осуществляется
следующим
образом:
rn–1(x) xi xn–1–i xk = xi–n–1–i+k = xn xk–1 = xk–1 mod g(x). (2.3)
Очевидно, что такая настройка селектора не зависит от длины вектора n, а определяется только длиной избыточной части k, которая для укороченных кодов не изменяется, т. е. является универсальной для всех укороченных кодов. Такой способ декодирования получил название «декодирование с предварительным умножением на xk». Поскольку степень порождающего полинома g(x) равна k, то настройка селектора просто равна xk–1.
В общем случае (для укороченных и неукороченных кодов) для построения декодера Меггита с универсальной настройкой селектора необходимо внести дополнения в структуру генератора синдрома. Указанные изменения вносятся с учетом вида дополнительного полинома d(x), который определяется следующим образом:
d(x)=xi+k mod g(x), (2.4)
где i – количество символов, на которые был укорочен код. Как вид дополнительного полинома d(x) влияет на структуру декодера, укажем при рассмотрении вопросов построения декодирующих устройств. Как будет показано ниже, для неукороченных кодов дополнительный полином d(x) не влияет на структуру декодера.
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 |
Для расчета настроек элементов селектора используются соотношения следующего вида:
xn–1 mod g(x) – для исправления однократной ошибки,
(xn–1 xi) mod g(x) – для исправления двукратной ошибки (i – номер символа с ошибкой в одном из разрядов: i=0,…, n–2).
После исправления всех ошибок, предусмотренных корректирующей способностью кода, элементы памяти генератора синдрома обнуляются.
Поскольку достаточно широкое применение в системах передачи информации нашли коды Хэмминга (dmin = 3,4), то рассмотрим пример структуры и функционирования декодеров Меггита именно для них.
П
ример
2.2.
Для циклического кода (7,4,3) и проверочного
полинома g(x)
= 1
x2
x3
построить декодер Меггита. Структурная
схема декодера Меггита будет выглядеть
следующим образом (рис. 2.2).
Рис. 2.2. Структурная схема декодирующего устройства Меггита для БЧХ-кода (7,4,3)
Рассчитаем настройку селектора в схеме без предварительного умножения на xk: r6(x) = xn–1 mod g(x) = x x2.
Первые 7 тактов происходит заполнение буферного регистра полиномом V'(x). Одновременно осуществляется вычисление синдрома S(x). Если после 7-го такта элементы памяти генератора синдрома обнулились, значит, ошибок в принятом векторе нет, или кратность ошибки превышает корректирующую способность кода. Если в элементах памяти генератора синдрома находится ненулевой остаток, то деление продолжается дальше. При этом открывается ключ, давая возможность селектору исправить ошибку. На том такте, когда ошибочный разряд попадает в старший (n – 1) разряд буферного регистра, комбинация вектора синдрома S0,…, Sk–1 совпадает с настройкой селектора. Это означает, что выход селектора устанавливается равным 1. Тогда на следующем такте ошибочный разряд, выдвигаясь из старшего разряда БР, складывается по модулю 2 с выходом селектора, что эквивалентно инверсии ошибочного символа (исправлению ошибки). После этого элементы памяти генератора синдрома обнуляются сигналом Reset.
Номер такта, на котором сработает селектор, определяется следующим образом:
2n – i –1, (2.5)
где i – номер ошибочного разряда.
Соответственно, номер такта, на котором произойдет исправление ошибки,
2n – i. (2.6)
Запишем функции возбуждения для элементов памяти ГС РССЛОС:
Промоделируем работу декодирующего устройства для полинома V(x) = 1 x2 x3 при однократной ошибке в разряде a3 (полином ошибки e(x) = x3). В этом случае полином V'(x) будет выглядеть так: V`(x) = V(x) e(x) = 1 x2 x3 x3 = 1 x2. Согласно предварительным расчетам селектор сработает (ошибочный разряд a3 попадает в старший разряд буферного регистра) на такте с номером: 27 – 3 – 1 = 10. Исправление произойдет на следующем такте, т. е. на такте с номером: 27 – 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
x2
x3)
построить декодер Меггита. Структурная
схема декодера Меггита приведена на
рис. 2.3.
Рис. 2.3. Структурная схема декодирующего устройства Меггита для БЧХ-кода (7,3,4)
Для кода Хемминга с dmin = 4 генератор синдрома строится по схеме раздельного деления полинома V'(x) на g(x) и на (1 x) . Поэтому все расчеты селектора для исправления однократной ошибки проводятся аналогично предыдущему примеру.
Рассчитаем настройку селектора в схеме без предварительного умножения на xk: r6(x)=xn–1 mod g(x)=xx2.
Первые
7 тактов происходит заполнение буферного
регистра полиномом V'(x).
Одновременно осуществляется вычисление
синдрома S(x).
Если после 7-го такта элементы памяти
генератора синдрома обнулились, значит,
ошибок в принятом векторе нет, или
кратность ошибки превышает корректирующую
способность кода. Синдром S3
контролирует кратность ошибки (S3
=
1 – однократная ошибка, S3
= 0 – двукратная ошибка (или ошибок нет)).
При однократной ошибке деление
продолжается дальше. При этом открывается
ключ к1,
давая возможность селектору исправить
ошибку. На том такте, когда ошибочный
разряд попадает в старший
(n–1)-й
разряд буферного регистра, комбинация
вектора синдрома
S0,…,
Sk–1
совпадает с настройкой селектора. Это
означает, что выход селектора
устанавливается равным «1». Тогда на
следующем такте ошибочный разряд,
выдвигаясь из старшего разряда БР,
складывается по модулю 2 с выходом
селектора, что эквивалентно инверсии
ошибочного символа (исправлению ошибки).
После этого элементы памяти генератора
синдрома обнуляются сигналом Reset.
В случае возникновения двукратной ошибки после n-го такта синдром S3 будет равен «0». При этом выполнятся все необходимые условия для формирования сигнала стирания (Erase), поскольку хотя бы один из синдромов {S0, S1, S2} будет равен «1». Поэтому через открывшийся на (n+1)-м такте ключ к2 на вход буферного регистра будет подан сигнал стирания, который его обнулит.
Номер такта, на котором сработает селектор в режиме исправления ошибки, определяется по формуле (2.5). Соответственно, номер такта, на котором произойдет исправление ошибки, определяется по формуле (2.6).
Запишем функции возбуждения для элементов памяти ГС РССЛОС:
Промоделируем работу декодирующего устройства для полинома V(x) = 1 x2 x3 при однократной ошибке в разряде a3 (полином ошибки e(x) = x3) и двукратной ошибке в разрядах a3 и a0 (полином ошибки e(x) = = x3 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 |
|
|
|
|
|
|
|