Вернер М. Основы кодирования

Подождите немного. Документ загружается.

4-8.

Упражнения

сетевой диаграммы состояний; Указание: при декодировании

учтите,

что кодирование начиналось

заканчивалось нулевым

состоянием.

Как

может быть интерпретирована метрика декодированной

информационной

последовательности?

Упражнение

4.2:

Сверточный код, используемый

сети

мо-

бильной связи GSM.

Для передачи речи

сетях мобильной связи GSM использует-

ся

оптимальный сверточный

код с

производящими многочленами

Я\

(х)

= 1 + х

+ х

д2

(х)

= 1 + х + х

+ х

имеющий свободное

расстояние, равное

ree

= 7

1. Приведите

схему

кодера, содержащую переменные х\,

Х2,

хз,

х\.

2. Каждый речевой блок, продолжительностью

мсек, содер-

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

нужно добавить

информационной последовательности

для

того, чтобы кодирование закончилось

нулевом состоянии?

3. Определите значения

следующих

величин: памяти кодера, ко-

дового ограничения, блоковой скорости, относительной потери

скорости, полной памяти кодера.

4. Оцените сложность реализации декодера Витерби.

Упражнение

4.3:

Сверточный код, используемый

сети

мо-

бильной связи GSM.

Для передачи данных

сети GSM

со

скоростью

4,8

кбит/сек

по

каналу TCH/F4,8 используется сверточный

код с

порождающими

многочленами д\{х)

= 1 + х + х

а;

, д2(х)

= 1 + х

+ х

дз(х)

+ х

с d

free

= 12.

1. Приведите

схему

кодера, содержащую переменные хi,a;2,

хз,Xi.

2. Из технических соображений каждый информационный блок,

содержащий 60 бит, кодируется словом, длина которого состав-

ляет 228 бит. Сколько нулевых бит добавляется

конце инфор-

мационного блока? Каким состоянием заканчивается декодиро-

вание?

3. Определите значение памяти кодера, кодового ограничения,

блоковой скорости кода, относительной потери кодовой скоро-

сти, полной памяти кодера.

,264

Глава 4- Сверточные коды

4. Оцените сложность реализации декодера Витерби.

Упражнение

4.4:

Детектор Витерби

субонтимальной метри-

кой.

Повторите ранее рассмотренный пример работы детектора

Ви-

терби

при

субоптимальной метрике

Xi=\z-di\.

Решения заданий.

Решение

задания

4.1.

Сверточный

код.

Для

заданных параметров

из

таблицы находим порождающие

многочлены

д\{х) = 1 + ж

; д

(х) = 1 + х + х

2. Схема кодера.

3. Диаграмма состояний кодера

0/00

1/11

4. Кодирование информационной последовательности.

Из

диаграммы состояний получаем:

Последовательность состояний (старт

So)

—

-S

- Si(-S

«XBOCT»).

Кодовое слово

{v[n]} = {11,01,11,11,10,10,00,01,11}

4-8.

Упражнения

265]

5. Декодирование

по

сетевой диаграмме

минимальным расстоя-

нием

Хэмминга

Принятое

слово

{r[n]}' = {11,01,11,01,10,10,01,10,11}

Продекодйрованная информационная последовательность

{«'[n]} = {1,0,0,1,1,0,1}

6. Если переданное слово иродекодированно правильно,

то мет-

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

как

число ошибочных

бит и в

этом

дучае

метрика может быть

ис-

пользована

для

оценки качества, канала.

Решение задания

4.2.

Сверточньгй:

код,

используемый

для

коди-

рования

речи

сетях мобильной связи

GSM.

1. Схема кодера

•—о—•—э—>-

информационной последовательности необходимо добавить

4 нуля

для

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

состоянием.

3. Память кодера

т = 4.

Кодовое ограничение

= 10.

Глава

Сверточные коды

Блоковая

скорость

185/(2[185

+ 4]) =

0,489

Относительная потеря скорости

4/(185

+ 4) = 2,11

•

10~

Полная

память кодера М = 4.

4. Существует 2

= 16 состояний. На каждом шаге декодер вы-

числяет 32 приращения метрик, исходя из которых вычисляют-

ся

тридцать две частичных метрики и сравниваются попарно;

16 вцживших путей выбираются для продолжения и их частич-

ные метрики запоминаются.

Решение

задания 4.3. Сверточный код для передачи данных в

мобильных сетях связи GSM.

1. Схема кодера

2. Из равенства 3- (60+х) = 228

следует,

что х = 16, т.е. к инфор-

мационной последовательности добавляются 16 нулей и коди-

рование заканчивается нулевым состоянием.

60+л

Кодер

=1/3

228

3. Память кодера т = 4. Кодовое ограничение п

= 3-(4+1) = 15.

Блоковая

скорость 60/(3

•

[60 + 4]) =

0,3125

учитывая 16 нулевых бит получаем

60/228

0,263

Относительная потеря скорости 4/64 = 6,25

•

10~

учитывая 16 нулевых бит получаем 16/76 = 0,211

Полная

память кодера М = 4.

4. Существует I

= 16 состояний. В каждом такте декодер вы-

числяет 32 приращения метрик, исходя из которых вычисля-

ются и попарно сравниваются 32 частичные метрики; 16 полу-

ченных путей выбираются для продолжения и их частичные

метрики запоминаются.

4-8.

Упражнения

267]

Решение

задания 4.4. Детектор Витерби с субоптимальной адди-

тивной

метрикой.

Таким

образом, при аддитивной метрике информационная после-

довательность также детектируется без ошибок.

ГЛАВА 5

ДИСКРЕТНЫЕ

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

КОДЫ

РИДА - СОЛОМОНА

5.1.

Введение

В предыдущих

главах

мы рассматривали только двоичные коды, то

есть коды с символами из

GF(2).

Между тем, коды над алфавитом

GF(q),

где q > 2, так называемые g-ичные коды, помимо чисто теоре-

тического интереса, имеют в настоящее время огромное прикладное

значение.

Мы ограничимся только рассмотрением кодов Рида - Со-

ломона, как наиболее ярких представителей д-ичных кодов, без кото-

рых немыслима современная теория и практика помехоустойчивого

кодирования.

Остановимся, прежде всего, на прикладном значении кодов Ри-

да - Соломона. Как было показано в предыдущих

главах,

простей-

шие алгебраические двоичные коды

могут

успешно применяться для

передачи данных в компьютерных сетях связи, обеспечивая необхо-

димую

надежность передаваемой информации. Это объясняется до-

статочно высоким качеством проводных и оптоволоконных каналов

связи

и возможностью переспроса передаваемых блоков данных. За-

дача

кодирования для таких каналов, в основном, сводится только к

обнаружению независимых ошибок и пакетов ошибок.

Все многообразие современных коммуникационных линий связи

не

исчерпывается только компьютерными сетями. В качестве при-

меров достаточно привести спутниковые каналы и мобильную циф-

ровую

связь. Здесь уже переспросы не допустимы и корректирую-

щая

способность кода определяется максимальным числом исправ-

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

ких каналах жестко ограничивается, что приводит к высокой веро-

ятности появления как независимых ошибок, так и пакетов ошибок.

В таких каналах использование рассмотренных нами простейших

двоичных кодов не имеет смысла. Так, например, коды Хэмминга

dm'm

= 3 и d

;

= 4 при наличии в блоке более, чем одной ошиб-

ки,

вместо исправления ошибок

будут

вносить новые. Проблему, в

5.1.

Введение

какой-то степени,

могут

решить низкоскоростные двоичные коды Бо-

уза

Чоудхури

- Хоквингема, однако, их реализация и декодирова-

ние

аналогично

кодам

Рида

Соломона

осуществляется с помощью

операций над

GF(2

)

при т > 1.

другой

стороны, турбо-коды, построенные на базе двоичных

сверточных кодов,

хотя

и позволяют обеспечить

требуемую

надеж-

ность при кодовых скоростях, близких к пропускной способности ка-

налов с независимыми ошибками, не расчитаны на

борьбу

с длинны-

ми

пакетами ошибок. Кроме этого, для их эффективной реализации

требуются

блоки очень большой длины (десятки и

даже

сотни кбит),

что не

всегда

технически приемлемо.

Решению подобных задач в немалой степени способствовало по-

явление в 1968 г. кодов Рида - Соломона с символами из

GF(q),

где

q > 2 [20]. Коды Рида - Соломона с параметрами (п, к) имеют мини-

мальное расстояние d

= п — к+1 и способны исправлять ](п—к)/2[

ошибок. После открытия Берлекэмпом в 1968 г. простого и эффек-

тивного алгоритма декодирования кодов Рида - Соломона, эти коды

прочно вошли в практику помехоустойчивого кодирования.

В первую очередь в

ых

годах

коды Рида - Соломона стали при-

меняться в качестве внешних кодов в каскадных конструкциях, ис-

пользуемых в спутниковых линиях связи. В таких конструкциях [21]

q-ичные символы кодов Рида - Соломона (один или несколько) коди-

руются внутренними двоичными сверточными кодами. При декоди-

ровании

сверточных кодов используется мягкое решение, особенно

эффективное

в каналах с АБГШ. Так как шум в реальных каналах

всегда

отличается от гауссовского, в спутниковых каналах возможно

появление пакетов ошибок. Такие пакеты

могут

привести к ошибоч-

ному декодированию внутренними сверточными кодами одного или

нескольких довольно длинных блоков. Для внешних кодов Рида -

Соломона это, в основном, эквивалентно появлению ошибочных q-

ичных символов небольшой кратности, лежащих в пределах коррек-

тирующей способности внешнего кода. Таким образом, весь каскад-

ный

код,

даже

при наличии пакетов ошибок, в подавляющем боль-

шинстве

случаев

декодируется правильно, что обеспечивает необхо-

димую

надежность передаваемой информации. Самое удивительное

заключается в том, что четкой альтернативы каскадным кодам с

внешними

кодами Рида Соломона для спутниковых линий связи до

сих пор найти не

удалось

и коды Рида Соломона являются неотъем-

лемой частью большинства стандартов (например Intelsat IESS-308).

Кроме этого коды Рида - Соломона имеют самостоятельное нрак-

270 Глава 5. Дискретные преобразования

Фурье

и коды PC

тическое применение. Они, например, являются практически опти-

мальными при записи информации на носители аудио-CD, что обу-

словлено техническими характеристиками и характером ошибэк при

записи.

Структура кодов Рида - Соломона и алгоритм декодирования

наиболее просто описывается с помощью спектральных методов [5).

Арифметика нолей

Галуа

GF(q) описана в приложении 2.5.

5.2.

Дискретные

преобразования

Фурье

поле

Галуа

Определение.

Пусть задан вектор v = (vo,

«i,...,

-i) над

GF(q),

где q = 2

, a n = q

—

1 и пусть а - примитивный элемент поля

Галуа

GF(q) характеристики 2. Преобразование Фурье в ноле

Галуа

век-

тора v определяется как вектор V = (Vo,

Vi,...,

_i),

задаваемый

равенствами

n-l

y;-

5>y«i,

j = o,...,n-i. (5.i)

i=0

По

аналогии с преобразованиями Фурье непрерывных сиглалов,

дискретный индекс г принято называть временем и говорить э том,

что вектор v принадлежит временной ^области. Естественно, что в

этом

случае

индекс j называется частотой и говорят, что вектор V

определен в частотной области.

Теорема

5.2.1. Над полем GF(q) характеристики 2 вектор v во

временной области и вектор V в частотной области связаны соотно-

шениями

п-1

у;-=

£<*««»

(5-2)

г=0

г*

Х>-^,

(5.3)

По

аналогии с непрерывными сигналами

будем

называть преоб-

разование (5.2) прямым преобразованием Фурье, а (5.3) - обратным

преобразованием.

Вектор v иногда задается многочленом v(X). С помощью преоб-

разования

Фурье в поле

Галуа

многочлен

v(X)

= v

+ v

X + --- +

(5.4)

5.2. Дискретные преобразования Фурье

поле Галуа

может быть преобразован

многочлен

который называется

спектральным

многочленом

или

многочленом

частотной области вектора

Теорема

5.2.2.

1. j-ая частотная компонента

равна нулю

тогда

только

тогда,

когда элемент

а?

является корнем многочлена

v{X);

г-ая

временная компонента Vi равна нулю

тогда

только

тогда

когда элемент

а"

является корнем многочлена

V(X).

Доказательство.

Доказательство утверждений

1. и 2.

очевидны,

так

как

п-1

ту

X "* ij

(г\3

(Z\

f!\

г=0

п-1

V /

j=0

Преобразование Фурье обладает многими важными свойствами,

которые переносятся

на

случай конечных полей. Помимо линейности

преобразований Фурье

для нас

важным является свойство свертки.

Прежде

чем

сформулировать теорему

свертке, введем некоторые

определения.

Пусть

поле

GF{q)

заданы векторы

g =

(<?o,Si>

• • •

,<?n-i)

(do,d\,...,

dn-i), многочлены которых имеют

вид д(Х) =

до

№ +

• • •

Эп-i^""

и d(X) = do + di{X) +

•••

^iX

Тогда компоненты вектора линейной свертки

с =

(со,сь

...

,Cn-i)

векторов

g и d

определяются

как

п-1

к=о

многочлен линейной свертки

с(Х)

может быть записан

виде про-

изведения

с(Х) = g(X)d(X).

272

Глава

Дискретные

преобразования

Фурье

коды

Операцию линейной свертки

двух

векторов мы уже рассматривали

разделе 4.2.

Циклическая

свертка может быть записана в виде

к=о

где двойные скобки означают вычисление индексов по

модулю

п =

—

1 (заметим, что в арифметике но mod n имеет место равенство

—k

= п

—

к).

Многочлен циклической свертки имеет вид

с(Х) =

g{X)d(X)(

modJs:

-l).

Для того, чтобы избежать путаницы,

будем

обозначать операцию

циклической

свертки символом «*», а операцию линейной свертки

Наконец,

операцию покомпонентного умножения

двух

векторов с = gd определим как

gidt.

Заметим, что все введеные выше операции

обладают

свойством ли-

нейности.

Теорема

5.2.3. Теорема о свертке.

Пусть во временной области заданы векторы f = (/о, /i,..., /

-i)

g = (<йь5ь

• • •

<?n-i), прямые преобразования Фурье которых в ча-

стотной области имеют вид F =

(FQ,FI,.

.. ,F

_i) и G = (Go,<?i,---.,

-i),

тогда

покомпонентному произведению векторов в частотной

области Е = FG взаимно однозначно

соответствует

их циклическая

свертка во временной области е = f * g,

т.е.

если Е = FG, то

п-1

Ч = ^2 ?((* ~

))9к, г =

0,...,

п - 1.

fc=o

Справедлива так же обратная теорема. Для ее формулировки

нужно только поменять местами временную и частотные области.

Изложенных выше сведений из теории дискретных преобразова-

ний

Фурье вполне достаточно для изучения

структуры

кодов Рида

- Соломона и алгоритма их декодирования.