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

Решение

m(X) = 1 + Х² + Х³, п = 1, к = 4, п-к=3\

Х^п~^кт(Х)=Х³(1 + Х² + АГ³) = АГ³ + Х⁵ + Х⁶ Разделив Х"~^кт(Х) на g(X), можно записать следующее:

Х³ + Х⁵ + Х⁶ = (1+Х + Х² + Х³) (1+Х + Х³) + 1

частноеq(X) генератор g(X) остаток р(Х)

Используя уравнение (6.64), получаем следующее:

U(X) = р(Х) + X³m(X) = 1 + X³ + X^s + X⁶ и= 10 0 10 11

биты четности биты сообщения

6.7.4. Логическая схема для реализации полиномиального деления

Выше показывалось, что при циклическом сдвиге полинома кодового слова и кодиро­вании полинома сообщения применяется операция деления полиномов друг на друга. Такие операции легко реализуются в схеме деления (регистр сдвига с обратной свя­зью). Итак, пусть даны два полинома V(X) и g(X), где

V (X) ⁼⁼ Vq + V(X + v₂X² +... + УщХ"¹

и

gW - ga + 8\Х + g₂X² +... +g_pX^p,

причем m>p. Схема деления, приведенная на рис. 6.16, выполняет полиномиальное деление V(X) на g(X), определяя, таким образом, частное и остаток:

^ = _{qW +} PW.

g(X) ^4V g(X)

В исходном состоянии разряды регистра содержат нули. Коэффициенты V(X) посту­пают и продвигаются по регистру сдвига по одному за такт, начиная с коэффициентов более высокого порядка. После р-го сдвига частное на выходе равно g_p^-1v_m; это сла­гаемое наивысшего порядка в частном. Далее для каждого коэффициента частного q, из делимого нужно вычитать полином q,g(X). Это вычитание обеспечивает обратная связь, отображенная на рис. 6.16. Разность крайних слева р слагаемых остается в де­лимом, а слагаемое обратной связи q,g(X) формируется при каждом сдвиге схемы и отображается в виде содержимого регистра. При каждом сдвиге регистра разность смещается на один разряд; слагаемое наивысшего порядка (которое по построению схемы равно нулю) удаляется, в то время как следующий значащий коэффициент в

V(X) перемещается на его место. После всех т + 1 сдвигов регистра, на выход после­довательно выдается частное, а остаток остается в регистре.

(первым идет коэффициент старшей степени)

Рис. 6.16. Логическая схема для реализации полиномиального деления

Пример 6.9. Схема полиномиального деления

Используя схему деления, показанную на рис. 6.16, разделите V(X) = X³ + X⁵ + X⁶ (V = 0 0 0 1 0 1 1) на g(X) = (1 + X + X³). Найдите частное и остаток. Сравните реализацию схемы и действия, происходящие при прямом делении полиномов.

Решение

Схема деления должна выполнить следующее действие:

^{Х 3 +} = q(X) + —•

1+Х + Х³ 1+Х + Х³

Полином обратной связи Х° X¹ X² X³   Рис. 6.17. Схема деления для примера 6.9

Необходимый регистр сдвига с обратной связью показан на рис. 6.17. Предположим, что первоначально регистр содержит нули. Схема выполнит следующие шаги.

Входная очередь Номер сдвига Содержимое регистра Выход и обратная связь

			-
-

После четвертого сдвига коэффициенты частного {q,}, последовательно поступающие с вы­хода, выглядят как 1111 или же полином частного имеет вид q(X) =1 + Х+ Х²+Х³. Ко­
эффициенты остатка {р,} имеют вид 10 0, т.е. полином остатка имеет вид р(Х)= 1. Таким образом, схема выполнила следующие вычисления:

Х³ + Х⁵ + Х⁶, _{v v2 v3} 1

-= 1+ X + X¹ + X^J +

1 + Х + Х³ 1+Х + Х³

• Прямое деление полиномов дает результат, показанный ниже.

Х⁶ + Х⁵+ X³ |Х³ + X +1

обратная связь после 4-го сдвига —> X⁶ + Х⁴ + Х³ Х³ + Х² + Х+1

регистр после 4-го сдвига х⁵ + х⁴ Т Т Т Т

обратная связь после 5-го сдвига —> X^s + Х³ + Х² 4 5 67 регистр после 5-го Сдвига —> Х⁴ + Х⁵ + Х²

обратная связь после 6-го сдвига —> X⁴ + X² + X

регистр после 6-го сдвига —> Х³+ X

обратная связь после 7-го сдвига —> X³ + X +1

регистр после 7-го сдвига —> 1

(остаток)

6.7.5. Систематическое кодирование с (л - #с)-разрядным регистром сдвига

Как было показано в разделе 6.7.3, кодирование с помощью циклического кода в систематической форме включает в себя вычисление битов четности, как результат деления X”^_4m(X) по модулю g(X),; иными словами, деление смещенного вверх (смещенного вправо) полиномиального сообщения на полиномиальный генератор g(X). Сдвиг вверх приводит к освобождению места для битов четности, которые прибавляются к разрядам сообщения, что в результате дает вектор кода в система­тической форме. Сдвиг вверх на п - к разрядов сообщения является тривиальной операцией и в действительности не выполняется в схеме деления. На самом деле вычисляются только биты четности; затем они помещаются на соответствующие места рядом с битами сообщения. Полином четности — это остаток от деления на полиномиальный генератор; он находится в регистре после п сдвигов через (п - к)- разрядный регистр сдвига с обратной связью, показанного на рис. 6.17. Отметим, что первые п - к сдвигов по разрядам — это просто заполнение регистра. У нас не может появиться никакой обратной связи, пока не будет заполнен крайний справа разряд; следовательно, мы можем сократить цикл деления, загружая входные дан­ные с выхода последнего разряда, как показано на рис. 6.18. Слагаемое обратной связи в крайнем левом разряде является суммой входных данных и крайнего пра­вого разряда. Гарантия создания этой суммы — обеспечение g₀ = g_n-ic= 1 для произ­вольного полиномиального генератора g(X). Соединения схемы обратной связи со­ответствуют коэффициентам полиномиального генератора, которые записываются в следующем виде:

g (X) = l_+giX + g₂X²+...+g_n-_k-_iXⁿ~^k~'+Xⁿ-^k. (6.66)

Следующие шаги описывают процедуру кодирования, использующую устройство, изображенное на рис. 6.18.

  Переключатель 2 Рис. 6.18. Кодирование с помощью (п — к)-разрядного регистра сдвига

1. При первых к сдвигах ключ 1 закрыт для передачи битов сообщения в (п - к)- разрядный регистр сдвига.

2. Ключ 2 установлен в нижнее положение для передачи битов сообщения на вы­ходной регистр в течение первых к сдвигов.

3. После передачи к-ro бита сообщения ключ 1 открывается, а ключ 2 переходит в верхнее положение.

4. При остальных п-к сдвигах происходит очищение кодирующих регистров, биты четности перемещаются на выходной регистр.

5. Общее число сдвигов равно п, и содержимое выходного регистра представляет собой полином кодового слова р(Х) +Х^п~*т(Х).

Пример 6.10. Систематическое кодирование циклического кода

Используя регистр сдвига с обратной связью, показанный на рис. 6.18, кодируйте вектор со­общения m = 1 0 1 1 в кодовое слово (7, 4). Полиномиальный генератор g(X) = 1 +Х + Х*. Решение

m= 1 0 1 1

т(Х) = 1 + X² + X³

Xⁿ~^km(X)=X³m(X)=X³+Х⁵+Х⁶

Xⁿ-^km(X) = q(X)g(X) + p(X)

р(Х) = (X³ + X⁵ + X⁶) по модулю (1 + X + X³)

Для (п - к) = 3-разрядного регистра сдвига, показанного на рис. 6.19, действия будут сле­дующими.

Входная очередь Номер сдвига Содержимое регистра Выход и обратная связь

		ООО	-
-

  Переключатель 2 Рис. 6.19. Пример кодирования циклического кода (7, 4) с по­мощью (п - к)-разрядного регистра сдвига

После четвертого сдвига ключ 1 открывается, ключ 2 переходит в верхнее положение, а би­ты четности переходят в выходной регистр. Выходное кодовое слово U = 1001011 или, в полиномиальной форме, U(X) = 1+ Х^э + Х^, + Х⁶.

6.7.6. Обнаружение ошибок с помощью (л - fc)-разрядного регистра сдвига

Передаваемое кодовое слово может быть искажено помехами, и, следовательно, при­нятый вектор будет искаженным вариантом переданного кодового слова. Допустим, что передается кодовое слово, имеющее в полиномиальном представлении вид U(X), а принимается вектор, в полиномиальном представлении имеющий вид Z(X). Посколь­ку U(X) — это полином кодового слова, он должен без остатка делиться на полиноми­альный генератор g(X).

U(X) = m(X)g(X) (6.67)

Z(X), искаженную версию U(X), можно представить следующим образом:

Z(X) = U(X) + е(Х). (6.68)

Здесь е(Х) — полином модели ошибки. Декодер проверяет, является ли Z(X) полино­мом кодового слова, т.е. делится ли он на g(X) без остатка. Это осуществляется путем вычисления синдрома принятого полинома. Синдром S(X) равен остатку от деления Z(X) на g(X):

Z(X) = q(X)g(X) + S(X). (6.69)

Здесь S(X) — полином степени п-к—1 или меньше. Соответственно, синдром — это (л - /:)-кортеж. Используя уравнения (6.67) и (6.69), получаем следующее:

е(Х) = [m(X) + q(X)] g(X) + S(X). (6.70)

Сравнивая уравнения (6.69) и (6.70), видим, что синдром S(X), полученный как Z(X) по модулю g(X), аналогичен остатку деления е(Х) на g(X). Таким образом, синдром приня­того полинома ЩХ) содержит информацию, необходимую для исправления модели ошибки. Расчет синдрома выполняется с помощью схемы деления, почти аналогичной схеме кодирования, используемой в передатчике. Пример вычисления синдрома со сдвигом на (п-к) разрядов регистра приведен на рис. 6.20 с использованием вектора ко­да, полученного в примере 6.10. В исходном состоянии ключ 1 закрыт, а ключ 2 открыт.

Принятый вектор подается во входной регистр, в котором в исходном состоянии все разряды имеют нулевое значение. После того как весь принятый вектор будет занесен в регистр сдвига, содержимое регистра — это и есть синдром. Теперь ключ 1 открывается, а ключ 2 закрывается, так что вектор синдрома теперь можно извлечь из регистра. Опи­санная последовательность действий имеет следующий вид.

  10 0 10 11 Рис. 6.20. Пример вычисления синдрома с помощью (п - к)-разрядного регистра сдвига

Входная очередь Номер сдвига Содержимое регистра

-		000 Синдром

Если вектор синдрома нулевой, считается, что принятый вектор является правильным кодовым словом. Если синдром отличен от нуля, значит, обнаружена ошибка и при­нятый вектор — это искаженное кодовое слово; данная ошибка исправляется путем прибавления к принятому вектору вектора ошибки (указанной синдромом), т.е. ана­логично процедуре, описанной в разделе 6.4.8. Этот метод декодирования хорош для простых кодов. Более сложные коды для практического использования требуют при­менения алгебраических методик.

6.8. Известные блочные коды

6.8.1. Коды Хэмминга

Коды Хэмминга (Hamming codes) — это простой класс блочных кодов, которые имеют следующую структуру:

(л, к) = (2^m - 1, 2^т - 1 - /и), (6.71)

где /и = 2,3,.... Минимальное расстояние этих кодов равно 3, поэтому, согласно уравнениям (6.44) и (6.47), они способны исправлять все однобитовые ошибки или определять все модели ошибки из двух или малого числа ошибок в блоке. Декодиро­вание с помощью синдромов особенно хорошо подходит к кодам Хэмминга. Фактиче­ски синдром можно превратить в двоичный указатель местоположения ошибки [5]. Хотя коды Хэмминга не являются слишком мощными, они принадлежат к очень ог­раниченному классу блочных кодов, называемых совершенными', их особенности опи­сывались в разделе 6.5.4.

Если предположить, что используется жесткое декодирование, вероятность появ­ления битовой ошибки можно записать с помощью уравнения (6.46):

(6.72)

Здесь р — вероятность ошибочного приема канального символа (вероятность перехода в двоичном симметричном канале). Для отдельных кодов коррекции ошибок (таких как ко­ды Хэмминга) вместо уравнения (6.72) мы можем использовать другое эквивалентное уравнение (это уравнение (Г. 16), которое выводится в приложении Г):

Рв~р~р(1 ~р)"~¹

На рис. 6.21 приведен график зависимости вероятности ошибки в декодированном бите от вероятности ошибки в канальном символе, на котором сравниваются разные блочные коды. Для кодов Хэмминга на графике взяты значения т = 3, 4 и 5 или (л, к) = (7, 4), (15,11), (31, 26). Для описания гауссового канала с использованием коге­рентной демодуляции сигналов BPSK, вероятность ошибки в канальном символе можно выразить через EJN₀, как это было сделано в уравнении (4.79):

(6.74)

Здесь EJN₀ — отношение энергии кодового символа к спектральной плотности мощ­ности шума, a Q(X) определено в уравнении (3.43). Чтобы связать EJN₀ с энергией би­та информации на единицу плотности спектрального шума (Еь/No), используем сле­дующее выражение:

(6.75)

Для кодов Хэмминга уравнение (6.75) принимает следующий вид:

Объединяя уравнения (6.73), (6.74) и (6.76), Р_в при когерентной демодуляции сигна­лов BPSK в гауссовом канале можно выразить как функцию EtJN₀. Результаты для различных типов блочных кодов отображены на рис. 6.22. Для кодов Хэмминга взяты следующие значения (л, к) = (7, 4), (15, 11), (31, 26).

Кодированный сигнал с модуляцией BFSK передается по гауссовому каналу. Сигнал не коге­рентно детектируется и жестко декодируется Найдите вероятность ошибки в декодирован­ном бите, если кодирование осуществляется блочным кодом Хэмминга (7, 4), а принятое значение EJNa равно 20.

Решение

Сначала, используя уравнение (6.75), находим E,JNo.

А- = 1(20) = 11,43 Л'о 7

Затем для кодированного некогерентного сигнала BFSK мы можем связать вероятность ошибки в канальном символе с EJN₀, подобно тому, как это было сделано в уравне­нии (4.96).

Р

Подставляя этот результат в уравнение (6.73), получаем следующее значение вероятности ошибки в декодированном бите:

Р_в ~ р — р(1 -р)"¹ = 1,6 х 10~⁵.

6.8.2. Расширенный код Голея

Одним из наиболее практичных блочных кодов является двоичный расширенный код Голея (extended Golay code) (24, 12), который образован путем прибавления битов чет­ности к совершенному коду (23, 12), известному как код Голея (Golay code). Эти до­полнительные биты повышают минимальное расстояние d^ с 7 до 8, что дает степень кодирования 1/2, реализовать которую проще (с точки зрения системного тактового генератора), чем степень кодирования кода Голея, равную 12/23. Расширенный код Голея значительно мощнее рассмотренного в предыдущем разделе кода Хэмминга. Цена, которую приходится платить за повышение эффективности, заключается в бо­лее сложном декодере и, соответственно, более широкой полосе пропускания.

Для расширенного кода Голея d_mm = 8, поэтому, исходя из уравнения (6.44), можно сказать, что код гарантирует исправление всех трехбитовых ошибок. Кроме того, де­кодер можно сконструировать так, чтобы он исправлял некоторые модели с четырьмя ошибками. Поскольку исправить можно только 16,7% моделей с четырьмя ошибками, декодер, для упрощения, обычно реализуется для исправления только трехбитовых моделей ошибки [5]. Если предположить жесткое декодирование, то вероятность би­товой ошибки для расширенного кода Голея можно представить как функцию веро­ятности р ошибки в канальном символе (см. уравнение (6.46)):

(6.77)

График зависимости (6.77) показан на рис. 6.21; вероятность появления ошибки для рас­ширенного кода Голея значительно меньше, чем у кодов Хэмминга. Исходя из уравне-

ний (6.77), (6.74) и (6.75), можно связать Р_в с EJN₀ для сигнала BPSK в гауссовом канале с кодированием расширенным кодом Голея. Результаты показаны на рис. 6.22.

6.8.3. Коды БХЧ

Коды Боуза-Чоудхури-Хоквенгема (Bose-Chadhuri-Hocquenghem — ВСН, БХЧ) явля­ются результатом обобщения кодов Хэмминга, которое позволяет исправлять множе­ственные ошибки. Они составляют мощный класс циклических кодов, который обеспе­чивает достаточную свободу выбора длины блока, степени кодирования, размеров ал­фавита и возможностей коррекции ошибок. В табл. 6.4 приводятся наиболее часто употребляемые при создании кодов БХЧ генераторы g(x) [8] с разными значениями п, к и t для блоков длиной до 255. Коэффициенты g(x) представлены восьмеричными числами, оформленными так, что при преобразовании их в двоичные символы край­ние правые разряды отвечают коэффициенту нулевой степени в g(x). С помощью табл. 6.4 можно легко проверить свойство циклического кода — полиномиальный ге­нератор имеет порядок п-к. Коды БХЧ очень важны, поскольку при блоках, длина которых равна порядка несколько сотен, коды БХЧ превосходят своими качествами все другие блочные коды с той же длиной блока и степенью кодирования. В наиболее часто применяемых кодах БХЧ используется двоичный алфавит и блок кодового слова длиной и = 2^т - 1, где т = 3, 4,....

Из названия табл. 6.4 ясно, что показаны генераторы только для примитивных кодов БХЧ. Термин “примитивные” (primitive) — это теоретико-числовое понятие, требующее алгебраического рассмотрения [7, 10-11], которое представлено в разде­ле 8.1.4. На рис. 6.21 и 6.22 изображены графики вероятности ошибки для двух ко­дов БХЧ: (127, 64) и (127, 36). На рис. 6.21 показана зависимость Р_в от вероятности ошибки в канальном символе при жестком декодировании. На рис. 6.22 показана зависимость Р_в от E,JN₀ для когерентно демодулированного сигнала BPSK в гауссо­вом канале. Кривые на рис. 6.22 выглядят совсем не так, как можно было бы ожи­дать. Все они имеют одну и ту же длину блока, но большая избыточность кода (127, 36) не дает той эффективности кодирования, какая имеется у менее избыточ­ного кода (127, 64). Известно, что относительно широкий максимум эффективности кодирования, в зависимости от степени кодирования при фиксированном п, для ко­дов БХЧ находится примерно между степенью 1/3 и 3/4 [12]. Стоит также отметить, что передача по гауссову каналу сильно ухудшается при переходе от очень высоких до очень низких степеней [11].

n	k	t	gto n	к	t	gW
			13 255
							Окончание табл.6.4
n	к	t	g(x) n	к	t	g(*)

Источник. Перепечатано с разрешения авторов из Table of Generators for BCH Codes”. IEEE Trans. Inf. Theory, vol. IT10, n. 4, October, 1964, p. 391. © 1964, IEEE.

n	k	t	g(x) n	k	t	g(x)
			13 255
						Окончание табл.6.4
n	k	t	g(x) n	k	t	g(x)

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