<< Предыдущая

стр. 39
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

01
1 1
0 0 0
3
1 1 1 Проверочные символы
4 0
-



4. Вычисление кодового многочлена v(X) для информационного
слова и = (0,1,0,1) в систематическом виде производится следую-
щим образом:

Х3 + Х
и(Х) =
Х4и(Х) mod g(X) = X2 + X (3.108)
• Ъ{Х) =
4 7 5 2
v(X) = Х и{Х) + b{X) = X +X +X + X,


что соответствует кодовому слову v = (0,1,1,0,0,1,0,1).
5. Так как CRC (7,3)-код является циклическим, то при отсут-
ствии ошибки в канале принятый многочлен г(Х) должен делиться
на порождающий многочлен д(Х) без остатка. Если в результате ра-
боты декодера получен ненулевой синдром, то с уверенностью можно
утверждать, что принятое слово является ошибочным. Схема вычис-
ления синдрома представлена на рис. 3.30.




При нятое слово Регистр синдрома


Рис. 3.30. Схема вычисления синдрома CRC (7,3)-кода.


6. Работа декодера для принятого слова г = (0,0,1,0,1,0,0,1)
(см. рис. 3.30) представлена в табл. 3.16 по тактам.
3.14- Упражнения
Таблица 3.16. Вычисление синдрома для принятого слова
г = (0,0,1,0,1,0,0,1).

Коментарий
Такт Сообщение so S3
«1

1
0 Инициализация
4 1 0
0010
5 1 1 1
1
001
1
0 0 0
6 00
7 1
0 0
0 0
1
0 0 Ошибка !
8 0
-




7. Представим принятое слово г = (0,0,1,0,1,0,0,1)) в виде мно-
гочлена и найдем остаток от деления многочлена г(Х) на д(Х)

Х7+Х*+Хг
г(Х)=
mod д{Х) = Хъ,
s(X) = r(X) (3.109)

что соответствует синдрому, получаемому в предыдущем пункте.
8. Так как циклический CRC (7,3)-код образуется с помощью по-
рождающего многочлена д(Х) четвертой степени, то все пакеты дли-
ны 4 и менее обнаруживаются.
9. «Концевой» пакет ошибок длины 4 е = (0,1,0,0,0,0,1,1).
Задача 3.2: Укороченный (12,8)-код Хэмминга.
Рассмотрим (12,8)-код, являющийся укорочением циклического
(15,11)-кода Хэмминга'. Начертите блок-схему декодера (12,8)-кода
оптимального с точки зрения сложности, исправляющего одну ошибку.

Решение.
Для минимизации сложности, выбернем схему декодера Меггит-
та, использующего вспомогательный многочлен е'(Х). Напомним,
что е'(Х) образуется умножением многочлена ошибку е(Х) на d(X),
где d(X) = Xi mod g(X). В рассматриваемом примере

(3.110)
д(Х) = 1 +

следовательно, многочлен d(X) равен

(3.111)
^ 218 Глава 3. Циклические коды


Блок-схема декодера приведена на рис. 3.31.

Принятое слово
' Выходной
регистр




\ Модифи кадия
синдрома




Исправление ошибки



Р и с . 3.31. Декодер Меггитта для укороченного (12,8)-кода
Хэмминга,
ГЛАВА 4
СВЕРТОЧНЫЕ
КОДЫ



4.1. Введение
В современной информационной технике сверточные коды играют
такую же важную роль как и блоковые. Первые попытки сопостав-
ления сверточных и блоковых кодов были сделаны в 50-е годы. С
этого времени блоковые коды быстро нашли эффективное примене-
ние, в то время как сверточные коды оставались на заднем плане.
Этот процесс продолжался до тех пор, пока в 1967 г. не был найден
эффективный алгоритм декодирования сверточных кодов. Сегодня
сверточные коды играют ведущую роль в современных системах свя-
зи. Это в первую очередь относится к цифровому радиовещанию и к
мобильной связи сети GSM. Сверточные коды позволяют также эф-
фективно бороться с помехами, вызванными многолучевым распро-
странением радиоволн. В последние годы сверточные коды получили
дальнейшее развитие в связи с открытием турбо-кодов. Достаточно
сказать, что использование турбо-кодов в современных системах пе-
редачи данных позволило достичь скоростей передачи информации
близких к пропускным способностям каналов. В связи с этим весь-
ма неожиданным обстоятельством в мобильных сетях радиовеща-
ния был принят стандарт UMTS -(Universal Mobile Telecommunication
Sistem - англ.).
Важнейшими отличиями сверточных кодов от блоковых являют-
ся следующие:

1. Сверточные коды позволяют производить кодирование и деко-
дирование потоков данных непрерывно во времени.

2. Сверточные коды не нуждаются в блоковой синхронизации.

3. Применение сверточных кодов позволяет достичь очень высо-
кой надежности передаваемой информации.
Глава 4- Сверточные коды


4. «Хорошие» сверточные коды могут быть найдены путем моде-
лирования.

Подробнее изложение теории сверточных кодов и областей их
применения выходит за рамки этой книги. В данной главе мы огра-
ничимся изложением только самых необходимых теоретических основ
и приведем типичные примеры применения сверточных кодов. Более
подробное описание можно найти, например [5],[18],[16].


4.2. Кодер и импульсный отклик
Термин «сверточные коды» возник из теории инвариантных линей-
ных систем LTI (Linear Time Invariant - англ). В теории систем LTI
сверткой называют характерный признак некоторой линейной опе-
рации. С точки зрения этой теории, кодирование является отобра-
жением информационной последовательности символов в кодовую
последовательность с помощью линейной схемы с параметрами, не
меняющимися во времени. Такое отображение наглядно показано на
рис. 4.1. Последовательность информационных символов поступа-
ет в демультиплексор, который разлагает входной поток на к само-
стоятельных подпоследовательностей. Схему рис. 4.1 можно также
интерпретировать как совместное кодирование к независимых ин-
формационных последовательностей. Кодирование производится с
помощью дискретной во времени схемы LTI с к входами и п выхода-
ми. Эта схема характеризуется тремя параметрами (n,fc,m), причем,
параметр т определяется внутренней конструкцией кодера.

Вход Выход

Кодовое слово
Принятое
LTI-System
и,[и]
слово и\щ
п,к,т




Р и с . 4.1. Схема LTI с к входами и п выходами как кодер
сверточного кода.

На практике, как правило, используются двоичные сверточные
коды, поэтому, в дальнейшем мы будем говорить о последовательно-
стях битов. В этом случае, иод линейностью схемы мы подразумева-
4.2. Кодер и импульсный отклик

ем выполнение этой схемой всех операций но правилам арифметики
по модулю 2. (т.е. в поле GF(2)).
Так как декодер представляет собой дискретную схему, для его
описания будем использовать методы теории обработки дискретных
сигналов. Придерживаясь терминологии этой теории, будем гово-
рить об информационной последовательности и[п], входных последо-
вательностях ui[n], иг!/1])---! Wfc[n], выходных последовательностях
Vi[n], V2[n],..., Vk[n] и кодовой последовательности и[пг]. Важней-
шим параметром схемы LTI является импульсный отклик. Смысл
этого параметра мы раскроем ниже.
В схеме, изображенной на рис. 4.1, все выходные последователь-
ности объединяются в одну кодовую последовательность с помощью
мультиплексора MUX. Это происходит путем поочередного считыва-
ния символов i»i[n],«2[и],... ,wn[n] при каждом фиксированном зна-
чении п.
Для того, чтобы записать связь между параметрами кодера рис
4.1 в компактной форме и при этом избежать путаницы, введем еди-
ные обозначения. Фигурными Скобками будем обозначать любою по-
следовательность символов, причем, нижние индексы используются
для нумерации элементов последовательностей. Для импульсного от-
клика системы первый нижний индекс определяет номер выходной
последовательности, а второй - номер входной.
• Входные последовательности {«J[TC]} = {UJO,UJ i,...}, при j =
1,...,*;
• Выходные последовательности {vj[n]} = {vjfi, Vjt\,...}, при j =
l,...,n;
• Информационная последовательность

к СИМВОЛОВ k СИМВОЛОВ

• Кодовая последовательность
= {yho, г>2,о, • • •, ttn,q,yi,i, « 2 , ь • • •, vn,u •••}',
{v[n}}
п СИМВОЛОВ п СИМВОЛОВ

• Импульсный omiviuK{gji[n}} = {9jifi,9ji,i, • • .,gji,mi}
С учетом введенных обозначений операцию свертки, выполняе-
мую схемой рис. 4.1, можно записать в виде
к к пч

г=1 ˜i=l m=0
222 Глава Jf. Сверточные коды

Замечание. Здесь символ «©# обозначает операцию линейной сверт-
ки. В дальнейшем мы будем рассматривать таксисе циклическую
свертку « * .
•»

Эта операция выполняется для всех выходов j. Здесь индексы,
стоящие в квадратных скобках, определяют нормированные пере-
менные времени, то есть они указывают номера элементов соответ-
ствующих последовательностей. Нумерация элементов, как правило,
начинается с нуля, поэтому иг[5], например, обозначает 6-ой элемент
второй входной последовательности. Элементы с отрицательной вре-
менной переменной полагаются равными нулю.

Замечание. В дальнейшем, если это не будет приводить к пута-
нице, лишние индексы будем опускать.

П р и м е р : Свертка двоичных последовательностей.

<< Предыдущая

стр. 39
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>