Файл: Кодирование и декодирование ЦСК_теория.doc

ПРИМЕНЕНИЕ ЦИКЛИЧЕСКИХ КОДОВ В КАНАЛАХ

С НЕЗАВИСИМЫМИ ОШИБКАМИ

1. Кодирование при помощи порождающего полинома g(x)

1.1. Общие принципы кодирования

Полином циклического кода можно представить в виде

(1.1)

где c_j – коэффициенты полинома избыточной части ; u_i – коэффициенты исходного полинома информационной части

Полином информационной части u(x) сдвинут в сторону старших разрядов на k символов, что эквивалентно умножению информационного полинома на x^k. Представим полином циклического кода в виде

(1.2)

Поскольку полиномы циклических кодов делятся на порождающий полином g(x) без остатка, то выражение можно записать в виде

(1.3)

где g(x) – порождающий полином; q(x) – частное от деления полинома u(x)x^k на порождающий полином g(x); r(x) – остаток от деления полинома u(x)x^k на порождающий полином g(x).

Таким образом, для определения избыточной части r(x) полинома циклического систематического кода V(x) необходимо определить остаток от деления полинома u(x)x^k на порождающий полином g(x). Указанный способ достаточно прост и эффективно алгоритмизируется, поэтому нашел наибольшее применение на практике.

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

Определим остаток от деления полинома u(x)x^k = 1x³ = x³ на порождающий полином g(x) = 1  x²  x³.

Рассчитанную избыточную часть представим в виде полинома
r(x) = 1x². Полином V(x) может быть представлен в виде V(x) = 1x²x³. Вектор V может быть представлен в виде V = (1011000).

Кодирование при помощи порождающего полинома g(x) для кодов с четным минимальным кодовым расстоянием проводится по указанному алгоритму, за исключением одного нюанса. Он связан с видом порождающего полинома, который, как известно, получается путем умножения порождающего полинома g(x) кода с нечетным минимальным кодовым расстоянием на полином (1x). Все остальные вычисления с применением полученного порождающего полинома проводятся аналогично.

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

Построим порождающий полином для заданного кода

g(x) = (1  x²  x³)·(1  x) = 1 x²  x³  x  x³  x⁴ = 1  x  x²  x⁴.

Определим остаток от деления полинома u(x)x^k = 1x⁴ = x⁴ на порождающий полином g(x) = 1  x  x²  x⁴:

Рассчитанную избыточную часть представим в виде полинома r(x) =
= 1  x  x². Полином V(x) может быть представлен как V(x) = 1  x  x² 
 x⁴. Вектор V может быть представлен в виде V = (1110100).

Кодирование при помощи порождающего полинома g(x) для укороченных циклических кодов не имеет принципиальных отличий. Это объясняется тем, что количество избыточных символов для неукороченного и полученного от него укороченного циклического кода, как известно, совпадает. Укорочению подвергается информационная часть, что не влияет на алгоритм кодирования.

---

1.2. Кодирующие устройства БЧХ-кодов, построенные
при помощи порождающего полинома g(x)

Коды БЧХ названы в честь его создателей-разработчиков - Боуза-Чоудхури-Хоквингема.

Кодирующее устройство (кодер) предназначено для выполнения следующих функций.

1. Прием и промежуточное хранение информационной части u(x).

2. Вычисление избыточных символов.

3. Формирование полинома V(x) и передача его в канал связи.

Основным элементом кодирующего устройства является регистр сдвига с линейной логической обратной связью (РСЛЛОС). Способ построения РСЛЛОС зависит от вида полинома, при помощи которого строится кодер.

С
труктурная схема регистра сдвига в рассматриваемом случае определяется порождающим полином g(x) и выглядит следующим образом (рис. 1.1).

Рис. 1.1. Структурная схема устройства деления на полином g(x)

На рис. 1.1 g_i – коэффициенты порождающего полинома g(x) для конкретного кода. Если коэффициент g_i=0 (xⁱ не входит в порождающий полином g(x)), то i-й элемент обратной связи и соответствующий ему сумматор отсутствуют. Количество элементов памяти (ЭП) равно k – степени порождающего полинома g(x). Элемент памяти D_i соответствует xⁱ.

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

Функции возбуждения для элементов памяти могут быть представлены в следующем виде:

Представленная схема осуществляет деление информационного полинома u(x) на порождающий полином g(x). Полином u(x) подается на вход схемы последовательно, начиная со старшего разряда, при этом происходит его предварительное умножение на x^k. К окончанию деления, т.е.
к n-му такту работы схемы, в регистре D₀…D_k–1 формируется остаток, который и является избыточной частью для заданного информационного вектора.

Пример 1.3. Построить схему РСЛЛОС для циклического кода (7,4,3) и порождающего полинома g(x) = 1  x²  x³. Промоделировать работу схемы для информационного полинома u(x)=1.

С
учетом параметров кода и вида порождающего полинома g(x) схема будет выглядеть следующим образом (рис. 1.2).

Рис. 1.2. Структурная схема устройства деления на полином g(x) = 1  x²  x³

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

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

Таблица 1.1

№ такта	u	D0	D1	D2
		0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	0	0
4	1	1	0	0
5	0	0	1	0
6	0	0	0	1
7	0	1	0	1

---

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

Кодирующее устройство, кроме задачи расчета избыточной части, должно еще сформировать полином V(x) и передать его в канал связи. Избыточная часть формируется к n-му такту вследствие того, что для деления информационный полином u(x) должен быть умножен на величину x^k. Поэтому необходимо сформировать задержку передачи в канал связи информационного вектора на k тактов, тогда к k + m = n-му такту информационный вектор будет выдан в канал связи, а избыточная часть – рассчитана и размещена в регистре. После этого необходимо организовать выдачу избыточной части в канал связи, прекратив процедуру деления. Структурная с
хема кодирующего устройства, работающего по описанному алгоритму, приведена на рис. 1.3.

Рис. 1.3. Структурная схема кодирующего устройства БЧХ-кода:

ЭЗ – элемент задержки, к₁, к₂ – ключи, У – управление

Элемент задержки предназначен для организации временной задержки выдачи информационного вектора в канал связи на k тактов. Ключ к₁ открыт в течение первых n тактов для активизации обратной связи, закрыт в течение последующих k тактов для разрыва обратной связи. Ключ к₂ закрыт в течение первых n тактов для отключения регистра от выхода, открыт в течение последующих k тактов для выдачи избыточной части в канал связи. Ключи переключаются по сигналу управления У: 1 – к₁ открыт, к₂ закрыт, 0 – к₁ закрыт, к₂ открыт.

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

С

учетом параметров кода и вида порождающего полинома g(x) схема кодера будет выглядеть следующим образом (рис. 1.4).

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

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

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

Таблица 1.2

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

---

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

Недостатком рассмотренной схемы кодирующего устройства является наличие временной задержки на k тактов и, соответственно, наличие дополнительного элемента задержки. Задержка объясняется тем, что, как уже говорилось выше, в течение первых k тактов происходит умножение информационного полинома u(x) на величину x^k. Данную проблему удалось бы решить, подавая в схему информационный полином u(x), предварительно умноженный на величину x^k. Это можно сделать, подавая полином u(x) не на вход первого элемента памяти, соответствующего младшей (нулевой) степени, а на выход последнего, соответствующего k-й степени. Схема такого устройства приведена на рис. 1.5.

Р
ис. 1.5. Структурная схема кодера БЧХ-кода с предварительным умножением на x^k

Функции возбуждения для элементов памяти могут быть представлены в следующем виде:

Ключ к₁ открыт в течение первых m тактов для активизации обратной связи, закрыт в течение последующих k тактов для разрыва обратной связи. Ключ к₂ закрыт в течение первых m тактов для отключения регистра от выхода, открыт в течение последующих k тактов для выдачи избыточной части в канал связи. Ключи переключаются по сигналу управления
У: 1 – к₁ открыт, к₂ закрыт, 0 – к₁ закрыт, к₂ открыт. Расчет избыточной части по предварительно умноженному на x^k информационному полиному u(x) осуществляется за первые m тактов работы схемы.

Пример 1.5. Построить схему кодирующего устройства с пред­варительным умножением на x^k для циклического кода (7,4,3) и порождающего полинома g(x) = 1  x²  x³. Промоделировать работу схемы для информационного полинома u(x) = 1.

С учетом параметров кода, вида порождающего полинома g(x) и способа кодирования схема будет выглядеть следующим образом (рис. 1.6).

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

с предварительным умножением на x³

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

Промоделируем работу кодера и занесем результаты в таблицу переходов и выходов (табл. 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 – номер ошибочного разряда.

---