Основы теории принятая статистических решений 1051 37 страница

X_b = D²X_a + X„

X, = DX_h + DX_d,

X_d = DX_b + DXj,

X_e = D²X_r.

Здесь X_a,..., X_e являются фиктивными переменными неполных путей между промежу­точными узлами. Передаточную функцию кода, T(D), которую иногда называют произ­водящей функцией кода, можно записать как T{D) = XJX„. Решение уравнений состоя­ния (7.12) имеет следующий вид [15, 16]:

D

T(D) =

1-2 D

= D⁵ +2D⁶ +4D⁷ +... + 2^l D^{l + 5} +...

Передаточная функция этого кода показывает, что имеется один путь с расстоянием 5 до нулевого вектора, два пути — с расстоянием 6, четыре — с расстоянием 7. В общем случае существуют 2' пути с расстоянием 1 + 5 до нулевого вектора, причем 1 = 0, 1,

2,.... Просвет d_f кода является весовым коэффициентом Хэмминга слагаемого, имеющего наименьший порядок в разложении T(D). В данном случае d_f = 5. Для оценки пространственных характеристик при большой длине кодового ограничения передаточную функцию T(D) использовать нельзя, поскольку сложность T(D) экспо­ненциально растет с увеличением длины кодового ограничения.

Более того, мы можем ввести множитель N во все ветви переходов, порожденных входной двоичной единицей. Таким образом, после прохождения ветви суммарный множитель N возрастает на единицу, только если этот переход ветви вызван входной битовой единицей. Для сверточного кода, описанного на рис. 7.3, на перестроенной диаграмме состояний (рис. 7.18) показаны дополнительные множители L и N. Уравне­ния (7.12) теперь можно переписать следующим образом:

Х_ь = D^lLNX„ + LNX„

X_c = DLX_b + DLX_d,

X_d = DIMX_b + DLNX_d, _(7Л4)

X_e = D²U(_c.

Передаточная функция кода такой доработанной диаграммы состояний будет следующей:

d⁵l³n

1- DL(l+ L)N ~

L?N + D⁶L⁴(l + L)N² + D⁷L⁵(1+ l})N^l

I i С I. -5 / ■ 1

= D'

Таким образом, мы можем проверить некоторые свойства путей, показанные на рис. 7.16. Существует один путь с расстоянием 5 и длиной 3, который отличается от нулевого пути одним входным битом. Имеется два пути с расстоянием 6, один из них имеет длину 4, другой — длину 5, и оба отличаются от нулевого пути двумя входными битами. Также есть пути с расстоянием 7, из которых один имеет длину 5, два — дли­ну 6 и один — длину 7; все четыре пути соответствуют входной последовательности, которая отличается от нулевого пути тремя входными битами. Следовательно, если нулевой путь является правильным и шум приводит к тому, что мы выбираем один из неправильных путей с расстоянием 7, то в итоге получится три битовые ошибки.

оо 'ln

10 \

DLN

Рис. 7.18. Диаграмма состояний с обозначением расстояния, длины и числа входных единиц

7.4.1.1. Возможности сверточного кода в коррекции ошибок

В главе 6 при изучении блочных кодов говорилось, что способность кода к кор­рекции ошибок, г, представляет собой количество ошибочных кодовых символов, ко­торые можно исправить в каждом блоке кода путем декодирования по методу мак­симального правдоподобия. В то же время при декодировании сверточных кодов способность кода к коррекции ошибок нельзя сформулировать так лаконично. Из уравнения (7.11) можно сказать, что при декодировании по принципу максималь­ного правдоподобия код способен исправить t ошибок в пределах нескольких длин

*7 Л ПпПМГТРЯ r'nfarYrrkUiJLJv к'гтгю

кодового ограничения, причем “несколько” — это где-то от 3 до 5. Точное значение длины зависит от распределения ошибок. Для конкретного кода и модели ошибки длину можно ограничить с использованием методов передаточной функции кода. Та­кое ограничение будет описано позднее.

7.4.2. Систематические и несистематические сверточные коды

Систематический сверточный код — это код, в котором входной &-кортеж фигурирует как часть выходного л-кортежа кодового слова, соответствующего этому ^-кортежу. На рис. 7.19 показан двоичный систематический кодер со степенью кодирования 1/2 и К = 3. Для линейных блочных кодов любой несистематический код можно преобра­зовать в систематический с такими же пространственными характеристиками блоков. При использовании сверточных кодов это не так. Причина в том, что сверточные ко­ды сильно зависят от просвета', при построении сверточного кода в систематической форме при данной длине кодового ограничения и степени кодирования максимально возможное значение просвета снижается.

  Рис. 7.19. Систематический сверточный кодер (степень кодирования 1/2, К = 3)

В табл. 7.1 показан максимальный просвет при степени кодирования 1/2 для сис­тематического и несистематического кодов с К от 2 до 8. При большой длине кодо­вого ограничения результаты отличаются еще сильнее [17].

Таблица 7.1. Сравнение систематического и несистематического просветов, степень кодирования 1 /2

Длина кодового ограничения Просвет систематического кода Просвет несистематического кода

2 3 3

3 4 5

4 4 6

5 5 7

6 6 8

7 6 10

8 7 10

Источник: A. J. Viterbi and J. К. Omura. Principles of Digital Communication and Coding, McGraw- Hill Book Company, New-York, 1979, p. 251.

7.4.3. Распространение катастрофических ошибок в сверточных кодах

Катастрофическая ошибка возникает, когда конечное число ошибок в кодовых симво­лах вызывает бесконечное число битовых ошибок в декодированных данных. Мэсси

Гnooa V (^аиопиило vr\лмплпаимо¹ идгтк О

(Massey) и Сейн (Sain) указали необходимые и достаточные условия для сверточного кода, при которых возможно распространение катастрофических ошибок. Условием распространения катастрофических ошибок для кода со степенью кодирования 1/2, реализованного на полиномиальных генераторах, описанных в разделе 7.2.1, будет на­личие у генераторов общего полиномиального множителя (степени не менее едини­цы). Например, на рис. 7.20, а показан кодер с К = Ъ, степенью кодирования 1/2, со старшим полиномом g](X) и младшим gz(X).

g,(X) = l+X g₂(X) = l+X²

Генераторы gi(X) и g₂(X) имеют общий полиномиальный множитель 1 + X, поскольку

1 + AT² = (1 +Х)(1 +Х).

Следовательно, в кодере, показанном на рис. 7.20, а, может происходить распростра­нение катастрофической ошибки.

  ю

Если говорить о диаграмме состояний кода произвольной степени кодирования, то катастрофическая ошибка может появиться тогда и только тогда, когда любая петля пути на диаграмме имеет нулевой весовой коэффициент (нулевое расстояние до нуле­вого пути). Чтобы проиллюстрировать это, рассмотрим пример, приведенный на рис. 7.20. На диаграмме (рис. 7.20, б) узел состояния а =00 разбит на два узла, а и е, как и ранее. Допустим, что нулевой путь является правильным, тогда неправильный путь a b d d... d с е имеет точно 6 единиц, независимо от того, сколько раз мы обой­дем вокруг петли в узле d. Поэтому, например, для канала BSC к выбору этого непра­вильного пути могут привести три канальные ошибки. На таком пути может появить-

a Q(х) определяется уравнениями (3.43) и (3.44) и приведено в табл. Б.1. Следователь­но, для кода со степенью кодирования 1/2 и просветом d_f= 5, при использовании ко­герентной схемы BPSK и жесткой схемы принятия решений при декодировании, мо­жем записать следующее:

[1 - 2tx.p(-E_b/2N₀)]

7.4.5. Эффективность кодирования

Эффективность кодирования, представленная уравнением (6.19), определяется как умень­шение (обычно выраженное в децибелах) отношения EJN₀, требуемого для достижения определенной вероятности появления ошибок в кодированной системе, по сравнению с некодированной системой с той же модуляцией и характеристиками канала. В табл. 7.2 перечислены верхние границы эффективности кодирования. Они сравниваются с некоди- рованным сигналом с когерентной модуляцией BPSK для нескольких значений мини­мальных просветов сверточного кода. Длина кодового ограничения в гауссовом канале с жесткой схемой принятия решений при декодировании изменяется от 3 до 9. В таблице отражен тот факт, что даже при использовании простого сверточного кода можно достичь значительной эффективности кодирования. Реальная эффективность кодирования будет изменяться в зависимости от требуемой вероятности появления битовых ошибок [20].

Таблица 7.2. Верхние границы эффективности кодирования для некоторых сверточных кодов

Коды со степенью кодирования 1/2	Коды со степенью кодирования 1/2
К	df	Верхняя граница (дБ)	К	d,	Верхняя граница (дБ)
		3,97			4,26
		4,76			5,23
		5,43			6,02
		6,00			6,37
		6,99			6,99
		6,99			7,27
		7,78			7,78

Источник: V. К. Bhargava, D. Haccoun, R. Matyas and P. Nuspl. Digital Communications by Satellite. John Wiley & Sons, Inc., New York, 1981.

В табл. 7.3 приводятся оценки эффективности кодов, сравниваемые с некодиро- ванным сигналом с когерентной модуляцией BPSK, реализованной аппаратным путем или путем моделирования на компьютере, в гауссовом канале с мягкой схемой приня­тия решений при декодировании [21]. Некодированное значение E,/N₀ дано в крайнем левом столбце. Из табл. 7.3 можно видеть, что эффективность кодирования возрастает при уменьшении вероятности появления битовой ошибки. Однако эффективность ко­дирования не может возрастать бесконечно. Как показано в таблице, она имеет верх­нюю границу. Эту границу (в децибелах) можно выразить следующим образом:

Здесь г — степень кодирования, a d_f— просвет. При изучении табл. 7.3 обнаруживается также, что (при р_в = 1(Г⁷) для кодов со степенью кодирования 1/2 и 2/3 более слабые коды имеют тенденцию находиться ближе к верхней границе, чем более мощные коды.

Таблица 7.3. Основные значения эффективности кодирования (в дБ) при использовании мягкой схемы принятия решений в ходе декодирования по алгоритму Витерби

Некодирова- нное Еь/No	Степень кодирования		1/3		1/2			2/3		3/4
(ДБ)	Рв	к
6,8	КГ^3		4,2	4,4	3,3	3,5	3,8	2,9	3,1	2,6	2,6
9,6	10"^5		5,7	5,9	4,3	4,6	5,1	4,2	4,6	3,6	4,2
11,3	10-^7		6,2	6,5	4,9	5,3	5,8	4,7	5,2	3,9	4,8
Верхняя граница		7,0	7,3	5,4	6,0	7,0	5,2	6,7	4,8	5,7

Источник: I. М. Jacobs. Practical Applications of Coding. IEEE Trans Inf. Theory, vol. IT20, May 1974, pp. 305-310.

Как правило, декодирование по алгоритму Витерби используется в двоичном вход­ном канале с жестким или мягким 3-битовым квантованным выходом. Длина кодо­вого ограничения варьируется от 3 до 9, причем степень кодирования кода редко ока­зывается меньше 1/3, и память путей составляет несколько длин кодового ограниче­ния [12]. Памятью путей называется глубина входных битов, которая сохраняется в декодере. После рассмотрения в разделе 7.3.4 декодирования по алгоритму Витерби может возникнуть вопрос об ограничении объема памяти путей. Из этого примера может показаться, что декодирование кодового слова в любом узле может происходить сразу, как только останется один выживший путь в этом узле. Это действительно так; хотя для создания реального декодера таким способом потребуется большое количест­во постоянных проверок после декодирования кодового слова. На практике вместо всего этого обеспечивается фиксированная задержка, после которой кодовое слово де­кодируется. Было показано [12, 22], что информации о происхождении состояния с наименьшей метрикой состояния (с использованием фиксированного объема путей, порядка 4 или 5 длин кодового ограничения) достаточно для получения характеристик декодера, которые для гауссова канала и канала BSC на величину порядка 0,1 дБ меньше характеристик оптимального канала. На рис. 7.21 показаны характерные ре­зультаты моделирования достоверности передачи при декодировании по алгоритму Витерби с жесткой схемой квантования [12]. Заметьте, что каждое увеличение длины кодового ограничения приводит к улучшению требуемого значения EJN₀ на величину, равную приблизительно 0,5 дБ, при Р_в = 10“\

7.4.6. Наиболее известные сверточные коды

Векторы связи или полиномиальные генераторы сверточного кода ббычно выби­раются исходя из свойств просветов кода. Главным критерием при выборе кода является требование, чтоб код не допускал катастрофического распространения ошибок и имел максимальный просвет при данной степени кодирования и длине кодового ограничения.

  Еь/No (дБ) Рис. 7.21. Зависимость вероятности появления битовой ошибки от EJN₀ при степени кодирования кодов 1/2; используется когерентная модуляция BPSK в канале BSC, декодирование согласно алго­ритму Витерби и 32-битовая память путей. (Перепечатано с разрешения авторов из J. A. Heller and I. М. Jacobs. “Viterbi Decoding for Satellite and Space Communication”. IEEE Trans. Commun. Technol., vol. COM19, n. 5, October, 1971, Fig. 7, p. 84 © 1971, IEEE)

Затем при данном просвете d_f минимизируется число путей или число ошибочных би­тов данных, которые представляют путь. Процедуру выбора можно усовершенство­вать, рассматривая количество путей или ошибочных битов при d_f + 1, d_f + 2 и т.д., пока не останется только один код или класс кодов. Список наиболее известных ко­дов со степенью кодирования 1/2 при К, равном от 3 до 9, и со степенью кодирования 1/3 при К, равном от 3 до 8, соответствующих этому критерию, был составлен Одену- альдером (Odenwalder) [3, 23] и приводится в табл. 7.4. Векторы связи в этой таблице представляют наличие или отсутствие (1 или 0) соединения между соответствующими регистрами сверточного кодера, причем крайний левый элемент соответствует край­нему левому разряду регистра кодера. Интересно, что эти соединения можно обратить (заменить в указанной выше схеме крайние левые на крайние правые). При декоди­ровании по алгоритму Витерби обратные соединения приведут к кодам с точно таки­ми же пространственными характеристиками, а значит, и с такими же рабочими ха­рактеристиками, как показаны в табл. 7.4.

Таблица 7.4. Оптимальные коды с малой длиной кодового ограничения (степень кодирования 1/2 и 1/3)

Степень кодирования	Длина кодового	Просвет	Вектор кода
	ограничения
1/2

Степень кодирования	Длина кодового ограничения	Просвет	Вектор кода
1/2
1/2
1/2
1/2
1/2
1/2
1/3
/
1/3
1/3
1/3
1/3
1/3

Источник: J. P. Odenwalder. Error Control Coding Handbook. Linkabit Corp., San Diego, Calif., July, 15, 1976.

7.4.7. Компромиссы сверточного кодирования

7.4.7.1. Производительность при когерентной передаче PSK-модулированных сигналов

Возможности схемы кодирования в коррекции ошибок возрастают при увеличении числа канальных символов п, приходящихся на число информационных бит к, или при снижении степени кодирования kin. В то же время при этом увеличивается ши­рина полосы пропускания канала и сложность декодера. Выгода низких степеней ко­дирования при использовании сверточного кода совместно с когерентной модуляцией PSK проявляется в снижении требуемого значения E^N₀ (для широкого диапазона степеней кодирования), что позволяет при заданном значении мощности осуществить передачу на более высоких скоростях или снизить мощность при заданной скорости передачи информации. Компьютерное моделирование показало [16, 22], что при фик­сированной длине кодового ограничения снижение степени кодирования с 1/2 до 1/3 в итоге приводит к уменьшению требуемого значения £*//V₀ примерно на 0,4 дБ (сложность декодера при этом возрастает примерно на 17%). Для меньших значений степени кодирования улучшение рабочих характеристик с ростом сложности декоди­рования быстро убывает [22]. В конечном счете, существует точка, по достижении ко­торой дальнейшее снижение степени кодирования приводит к падению эффективно­сти кодирования (см. раздел 9.7.7.2).

7.4.7.2. Качество при некогерентной ортогональной передаче сигналов

В отличие от модуляции PSK, при некогерентной ортогональной передаче сигналов существует оптимальное значение степени кодирования, приблизительно равное 1/2. На­дежность передачи при степени кодирования 1/3, 2/3 и 3/4 хуже, чем при степени кодиро­вания 1/2. При фиксированной длине кодового ограничения и степени кодирования 1/3, 2/3 или 3/4 качество кодирования, как правило, падает на 0,25, 0,5 и 0,3 дБ, соответствен­но, по сравнению с достоверностью передачи при степени кодирования 1/2 [16].

7.4.8. Мягкое декодирование по алгоритму Витерби

Для двоичной кодовой системы со степенью кодирования 1/2, демодулятор подает на декодер два кодовых символа за раз. Для жесткого (двухуровневого) декодирова­ния каждую пару принятых кодовых символов можно изобразить на плоскости в виде одного из углов квадрата, как показано на рис. 7.22, а. Углы помечены двоич­ными числами (0, 0), (0, 1), (1, 0) и (1, 1), представляющими четыре возможных значения, которые могут принимать два кодовых символа в жесткой схеме приня­тия решений. Аналогично для 8-уровневого мягкого декодирования каждую пару кодовых символов можно отобразить на плоскости в виде квадрата размером 8x8, состоящего из 64 точек, как показано на рис. 7.22, б. В этом случае демодулятор больше не выдает жестких решений; он выдает квантованные сигналы с шумом (мягкая схема принятия решений).

Основное различие между мягким и жестким декодированием по алгоритму Ви­терби состоит в том, что в мягкой схеме не используется метрика расстояния Хэм­минга, поскольку она имеет ограниченное разрешение. Метрика расстояний, которая имеет нужное разрешение, называется эвклидовым кодовым расстоянием, поэтому далее, чтобы облегчить ее применение, соответствующим образом преобразуем двоич­ные числа из единиц и нулей в восьмеричные числа от 0 до 7. Это можно увидеть на рис. 7.22, в, где соответствующим образом обозначены углы квадрата; теперь для опи­сания любой из 64 точек мы будем пользоваться парами целых чисел от 0 до 7. На рис. 7.22, в также изображена точка 5,4, представляющая пример пары значений ко­довых символов с шумом. Представим себе, что квадрат на рис. 7.22, в изображен в координатах (*, у). Каким будет евклидово кодовое расстояние между точкой с шумом

5,4 и точкой без шума 0,0? Оно равно ^/(5-О)² +(4-О)² =л/41 • А если мы захотим

узнать евклидово кодовое расстояние между точкой с шумом 5,4 и точкой без шума

7,7? Аналогично -^/(5 — 7)² + (4- 7)² = VU.

  fl О, 0 ^f2 ^f1 V41 ^f2 %-----------------------------------! • * •

\7,7 \V13

г) Д)

Puc. 7.22. Декодирование Витерби: а) плоскость жесткой схемы принятия решений; б) 8-уровневая плоскость мягкой схемы принятия решений; в) пример мягких кодовых симво­лов; г) секция решетки кодирования, д) секция решетки декодирования

Мягкое декодирование по алгоритму Витерби, по большей части, осуществля­ется так же, как и жесткое декодирование (как описывалось в разделах 7.3.4 и 7.3.5). Единственное отличие состоит в том, что здесь не используется расстоя­ние Хэмминга. Поэтому рассмотрим мягкое декодирование, осуществляемое с евклидовым кодовым расстоянием. На рис. 7.22, г показана первая секция решет­ки кодирования, которая вначале имела вид, приведенный на рис. 7.7. При этом кодовые слова преобразованы из двоичных в восьмеричные. Допустим, что пара кодовых символов, поступившая на декодер во время первого перехода, согласно мягкой схеме декодирования имеет значения 5,4. На рис. 7.22, д показана первая

секция решетки декодирования. Метрика (л/41), представляющая евклидово ко­довое расстояние между прибывшим кодовым словом 5,4 и кодовым словом 0,0, обозначена сплошной линией. Аналогично метрика (Vl3) представляет собой евклидово кодовое расстояние между поступившим кодовым символом 5,4 и ко­довым символом 7,7; это расстояние показано пунктирной линией. Оставшаяся часть задачи декодирования, которая сводится к отсечению решетки и поиску полной ветви, осуществляется аналогично схеме жесткого декодирования. Заме­тим, что в реальных микросхемах, предназначенных для сверточного декодирова­ния, евклидово кодовое расстояние в действительности не применяется, вместо него используется монотонная метрика, которая обладает сходными свойствами, но значительно проще в реализации. Примером такой метрики является квадрат евклидова кодового расстояния, в этом случае исключается рассмотренная выше операция взятия квадратного корня. Более того, если двоичные кодовые символы представлены биполярными величинами, тогда можно использовать метрику ска­лярного произведения, определяемую уравнением (7.9). При такой метрике вме­сто минимального расстояния мы должны будем рассматривать максимальные корреляции.

7.5. Другие алгоритмы сверточного декодирования

7.5.1. Последовательное декодирование

До появления оптимального алгоритма Витерби существовали и другие алгоритмы декоди­рования сверточных кодов. Самым первым был алгоритм последовательного декодирования, предложенный Уозенкрафтом (Wozencraft) [24, 25] и модифицированный Фано (Fano) [2]. В ходе работы последовательного декодера генерируется гипотеза о переданной последова­тельности кодовых слов и рассчитывается метрика между этой гипотезой и принятым сиг­налом. Эта процедура продолжается до тех пор, пока метрика показывает, что выбор гипо­тезы правдоподобен, в противном случае гипотеза последовательно заменяется, пока не будет найдена наиболее правдоподобная. Поиск при этом происходит методом проб и ошибок. Для мягкого или жесткого декодирования можно разработать последовательный декодер, но обычно мягкого декодирования стараются избегать из-за сложных расчетов и большой требовательности к памяти.

Рассмотрим ситуацию, когда используется кодер, изображенный на рис. 7.3, и по­следовательность m = 1 1 0 1 1 кодирована в последовательность кодовых слов U = 1 101010001, как было в примере 7.1. Допустим, что принятая последовательность Z является, фактически, правильной передачей U. У декодера имеется копия кодового дере­ва, показанная на рис. 7.6, и он может воспользоваться принятой последовательностью Z для прохождения дерева. Декодер начинает с узла дерева в момент г, и генерирует оба пу­ти, исходящие из этого узла. Декодер следует пути, который согласуется с полученными п кодовыми символами. На следующем уровне дерева декодер снова генерирует два пути, выходящие из узла, и следует пути, согласующемуся со второй группой п символов. Про­должая аналогичным образом, декодер быстро перебирает все дерево.

Допустим теперь, что принятая последовательность Z является искаженным кодо­вым словом U. Декодер начинает с узла дерева в момент t\ и генерирует оба пути, вы­ходящие из этого узла. Если принятые п кодовых символов совпадают с одним из сге­нерированных путей, декодер следует этому пути. Если согласования нет, то декодер следует наиболее вероятному пути, но при этом ведет общий подсчет несовпадений между принятыми символами и кодовыми словами на пути следования. Если две вет­ви оказываются равновероятными, то приемник делает произвольный выбор, как и в случае с нулевым входным путем. На каждом уровне дерева декодер генерирует новые ветви и сравнивает их со следующим набором и принятых кодовых символов. Поиск продолжается до тех пор, пока все дерево не будет пройдено по наиболее вероятному пути, и при этом составляется счет несовпадений.

Если счет несовпадений превышает некоторое число (оно может увеличиваться после прохождения дерева), декодер решает, что он находится на неправильном пути, отбрасыва­ет этот путь и повторяет все снова. Декодер помнит список отброшенных путей, чтобы иметь возможность избежать их при следующем прохождении дерева. Допустим, кодер, представленный на рис. 7.3, кодирует информационную последовательность m = 1 1 0 1 1 в последовательность кодовых слов U, как показано на рис. 7.1. Предположим, что четвер­тый и седьмой биты переданной последовательности U приняты с ошибкой.

Время		h	h	h	и	ts
Информационная последовательность:	m
Переданная последовательность:	Г
Принятая последовательность:	Z =

1. В момент времени /, мы принимаем символы 11 и сравниваем их с кодовыми словами, исходящими из первого узла.

2. Наиболее вероятна та ветвь, у которой кодовое слово 11 (соответствующее входной битовой единице или ответвлению вниз), поэтому декодер решает, что входная бито­вая единица правильно декодирована, и переходит на следующий уровень.

3. В момент t₂ на этом втором уровне декодер принимает символы 00 и сравнивает их с возможными кодовыми словами 10 и 01.

4. Здесь нет “хорошего” пути, поэтому декодер произвольно выбирает путь, соот­ветствующий входному битовому нулю (или кодовому слову 10), и счетчик не­совпадений регистрирует 1.

5. В момент времени t_} декодер принимает символы 01 и сравнивает их на третьем уровне с кодовыми словами 11 и 00.

Дата добавления: 2015-10-28