Прокис Дж. Цифровая связь (2000) (1151856), страница 73

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 73)

а) при Р,(г) = — у (г) покажите, что размерность пространства сигналов У удовлетворяет условию У<гг; Ь) Покажите, что в общем У < 2?г; с) при М = 2 покажите, что приобщил у,(г) н уз(г) Рбо~~б~~)~оо *,бг)) х? - ) гЯ~*ТР) )~) Р. лн где г, х, и х — представления для г(Р'), х (1) и х„(г) в У-мерном пространстве, бг?г — элемент объема пространства. й) Используя результат (с), покажите, что для любого АР Рбо бш)~оо. ~.бг)) х ~ ) ...) х))хбх.,)обоих.,) б м"ки яр о е) Покажите, что (хв — х„,,~ ) ...г ~р(~~*.,)рб )*.,) Й =о~р~- РРРР 4У, и, следовательно, р)о обхх)оор.х бг)) х б, о р БЛОКОВЫЕ И СВЕРТОЧНЫЕ КОДЫ В гл.

7 мы рассмотрели кодирование и декодирование в канале с общей точки зрения и показали, что даже случайно выбранные коды в среднем дают качество, близкое к пропускной способности канала Для случая ортогональных сигналов мы показали, что можно достичь предела пропускной способности канала, если число сигналов не ограничивать. В этой главе мы опишем специальные коды и рассчитаем их качество для канала с АБГШ. В частности, мы рассмотрим два класса кодов, именно линейные блоковые и сверточные коды. Качество кода рассчитывается как для декодирования жестких решений, так и для декодирования мягких решений.

8.1. ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ Блоковый код состоит из набора векторов фиксированной длины, называемых кодовыми словами. Длина кодового слова — это число элементов в векторах, и оно обозначается и. Элементы кодового слова выбираются из алфавита с су элементами. Если алфавит содержит два элемента О и 1, код называется двоичным, а элементы любого кодового слова называют битами (двоичными символами). Если элементы кодового слова выбираются из алфавита, имеющего г7 элементов (г7>2), код называют не двоичным.

Интересно отметить, что если д является степенью 2, т.е. и =2, где Ь вЂ” положительное ь целое число, каждый г7-й элемент имеет эквивалентное двоичное представление, состоящее из Ь битов и, таким образом, недвоичные коды длины У можно отобразить в двоичный код с блоковой длиной п = ЬУ.

В двоичном блоковом коде длиной и можно образовать 2" кодовых слов. Из этих 2" кодовых слов мы можем выбрать М = 2" кодовых слов 1гг<п), чтобы сформировать код. Таким образом, блок из й информационных бит отображается в кодовое слово длины и, выбираемое из набора М= 2" кодовых слов. Мы обозначим результирующий блоковый код, как (»,А) код, а отношение 1/п= — Л, определим как скорость кода. В более общем случае, если код имеет д элементов, можно образовать гу" кодовых слов.

Подмножество из М = 2' кодовых слов можно выбрать для передачи х битовых информационных блоков. Кроме параметра скорости кода Л,, важным параметром кодового слова является его ьес, который равен числу ненулевых элементов, слова. В общем, каждое кодовое слово имеет свой собственный вес, Набор всех весов кода образует распределение весов кода.

Когда все М кодовых слов имеет одинаковый вес, код называется ког)им с фпкспрг>ваипььп весом или ког)ом с постояппь>м весом. Функции кодирования и декодирования включают арифметические операции суммирования и умножения, выполненные над кодовыми словами. Эти арифметические операции выполняются в соответствии с соотношениями, правилами для алгебраического поля, которое имеет своими элементами символы, содержащиеся в алфавите кода. Для примера, символы в двоичном алфавите равны О и 1; следовательно, поле имеет два элемента. В общем, поле Г состоит нз набора элементов, 352 над которыми выполняются две арифметические операции, именно, операции сложения и умножения, которые удовлетворяют следующим свойствам (аксиомам): Сложение 1.

Набор Езамкнут относительно сложения, т.е. если а, Ь аР, тогда а+Ь ~Е. 2. Сложение ассоциативно, т,е. если а, Ь и с — элементы Е, тогда а+(Ь+с) = (а+Ь)+с. 3. Сложение коммутативно, т.е, а+Ь = Ь+а. 4. Набор содержит элемент, называемый нулевым, который удовлетворяет условию а+О=а. 5. Каждый элемент множества имеет свой собственный отрицательный элемент. Следовательно если Ь вЂ” элемент, то его отрицательный элемент обозначается — Ь. Вычитание двух элементов, такие как а — Ь определено как а+( — Ь) . Умножение 1. Набор Ь замкнут относительно умножения, т.е. если а, Ь ~Г, то тогда аЬ ~ Е. 2. Умножение ассоциативно, т.е. если а, Ь и с — элементы Г, тогда а(Ьс) = (аЬ)с. 3.

Умножение коммугативно, т.е. аЬ = Ьа . 4. Умножение дистрибутивно со сложением, т.е. (а+Ь)с = ас+Ьс, 5. Набор содержит элемент, называемый'единичным, который удовлетворяет условию а 1=а длялюбогоэлемента а аР. б. Каждый элемент Г, исключая нулевой, имеет обратный элемент. Следовательно если Ь а.Р' (Ь ~ 0), тогда его обратный элемент определйн как Ь ' и ЬЬ ' =1. Деление двух элементов, обозначаемое как а„—:Ь или а/Ь, определено как а Ь ' Мы очень свободно обращаемся с полями из вещественных чисел и полями из комплексных чисел, Эти поля могут иметь неограниченное число элементов.

Однако, как было указано выше, коды строятся из полей с отраниченным числом элементов. Ограниченное поле с <у элементами обычно называют полем Галуа и обозначают ОР(с/) Каждое поле должно иметь нулевой элемент и единичный элемент — следовательно, простейшее поле — это бР(2).

В общем, если ц является простым числом, мы можем построить ограниченное поле бР(у), состоящие из элементов (О, 1, ..., с/ — 1/. Операции суммирования н умножения над элементами из ОР(д) осуществляются по модулю <у и обозначается так (щод г/), Например, таблицы сложения и умножения для ОР(2) таковы: 0 0 0 1 Подобным образом, поле ОР(5)содержит набор, состоящий из элементов (0„1, 2, 3, 4). Таблицы сложения и умножения для ОР(5); 23-56 353 В об~цем, ограниченное поле ОР(у) можно построить, только если д — простое число или степень простого числа. Если д — простое число, умножение и сложение базируются на арифметике по модулю <у, как сказано выше. Если д = р, где р — простое число, а т— какое-либо целое, возможно расширить поле ОР(р) до поля ОР(р"'). Последнее называетсярасширенным полем ОР(р) .

Умножение и сложение элементов в расширенном поле базируется на арифметике по модулю р. С этим кратким введением в арифметику операций, которые можно осуществлять над элементами кодовых слов, рассмотрим теперь некоторые базовые характеристики блоковых кодов. Предположим, что С, и С,. — какие либо два кодовых слова в (и,'к~)кодовом блоке.

Мера разницы между кодовыми словами — число соответствующих элементов или позиций, в которых они различаются. Эта мера называется расстоянием Хемминга между двумя кодовыми словами и обозначается с~„. Ясно, что а!„при 1~ у удовлетворяет условию 0 < Ы, < и. Наименьшее значение из набора (п*„) для М кодовых слов называется минимальным расстоянием кода и обозначается и',„. Поскольку хеммингово расстояние является мерой различия между парами кодовых слов, оно, разумеется, имеет отношение к коэффициенту корреляции между соответствующими парами сигналов, генерируемыми кодовыми словами. Эта связь обсуждается в разделе 8.1.4.

Помимо классификации кодов на двоичные и недвоичные можно также их классифицировать на линейные и нелинейные. Возьмем С и С вЂ” два кодовых слова в l блоковом коде 1л,я) и а,, а,— какие-либо два скалярных элемента из определенного алфавита. Тогда код называют линейным, если и только если а,С, +и,С, тоже является кодовым словом. Это определение подразумевает, что линейный код должен содержать кодовое слово из одних нулей. Как следствие, код с постоянным весом нелинейный.

Предположим, что мы имеем двоичный линейный блоковый код, и пусть С„=1, 2, ...,М, где М вЂ” число кодовых слов. Для удобства пусть С, означает кодовое слово из одних нулей, т.е. С, =~00...0] и пусть и„означает вес г-го кодового слова. Отсюда следует, что и, является хемминговым расстоянием между кодовыми словами С,. и С,.

Т.е. расстояние Ы„= и~„. В общем, расстояние Ы,. между парой кодовых слов С,. и С, просто равно весу кодового слова, сформулированного разностью между С, и С,. Поскольку код линейный, разность ччто эквивалентно взятию суммы по шод 2 двоичных кодовых слов) между С, и С, также является кодовым словом с весом, включенным в набор (в„]. Следовательно, распределение весов линейного кода полностью характеризует дистанционные свойства кода. Минимальное расстояние кода равно И,„= ппп(и,~ 18.1.1) Определенное число элементарных понятий из линейной алгебры особенно полезны, когда имеем дело с линейными блоковыми кодами. В частности, набор из всех векторов с и элементами формирует векторное пространство о.

Если мы выберем набор из А <п линейно независимых векторов из У и из них сформируем набор из всех линейных комбинаций этих векторов, то результирующий набор образует подпространство в о", назовем его о, размерности я. Любой набор из к линейно независимых векторов в пространстве о, образует базис. Теперь рассмотрим набор из векторов 5, которые 354 ортогона~ьны к каждому вектору базиса Я, (и, следовательно, они ортогональны ко всем векторам в Я,). Эгот набор векторов также является подпространством Я и он называется нуль-пространством или ортогональным пространством к Я,. Если размерность пространства Я, равна й, то размерность нуль-пространства равна и — Ф.

Если пользоваться терминами, предназначенными для двоичных блоковых кодов, векторное пространство о состоит из 2" двоичных векторов с п элементами. Линейный ( п,А) код является ансамблем 2 векторов с и элементами, называемыми кодовыми словами, которые формируют подпростраиство Я, в поле из двух элементов. Поскольку имеется 2 кодовых слов в Ю„базис для Я, имеет 1 кодовых слов.

Это значит, что для конструирования 2 линейных комбинаций требуется Ф линейно независимых кодовых слов, которые формируют весь код. Нуль-пространство для Я, образует другой линейный код, который состоит из 2" ь кодовых слов блока длиной п с п-К информационными битами. Его размерность равна п-' й.

Характеристики

Список файлов книги