Прокис Дж. - Цифровая связь (1266501), страница 72
Текст из файла (страница 72)
6. Каждый элемент Г, исключая нулевой, имеет обратный элемент. Следовательно если Ь нЕ (Ь~ О), тогда его обратный элемент определен как Ь ' и ЬЬ ' =1. Деление двух элементов, обозначаемое как а„—:Ь или а/Ь, определено как а Ь '. Мы очень свободно обращаемся с полями из вещественных чисел и полями из комплексных чисел. Эти поля могут иметь неограниченное число элементов.
Однако, как было указано выше, коды строятся из полей с ограниченным числом элементов. Ограниченное поле с д элементами обычно называют далем Галуа и обозначают ОР(д). Каждое поле должно иметь нулевой элемент и единичный элемент- следовательно, простейшее поле — это ОР(2). В общем, если а является простым числом, мы можем построить ограниченное поле ОР(а), состоящие из элементов (О, 1, ..., а — 1). Операции суммирования и умножения над элементами из ОР(а) осуществляются по модулю а и обозначается так (шод д). Например, таблицы сложения и умножения для ОР(2) таковы: О О О 1 Подобным образом, поле ОР(5)содержит набор, состоящий из элементов (О, 1, 2, 3, 4).
Таблицы сложения и умножения для Щ5): 23-5б 353 В общем, ограниченное поле ОР(п) можно построить, только если д — простое число или степень простого числа. Если д — простое число, умножение и сложение базируются на арифметике по модулю д, как сказано выше. Если д = р, где р — простое число, а т — ':.
какое-либо целое, возможно расширить поле бг(р) до поля Ог(р ). Последнее называется рпсииренным полем ОР(р) . Умножение и сложение элементов в расширенном 1,' поле базируется на арифметике по модулю р. С этим кратким введением в арифметику операций, которые можно осуществлять над '~~. элементами кодовых слов, рассмотрим теперь некоторые базовые характеристики:1: блоковых кодов.
Предположим, что С,, и С„. — какие либо два кодовых слова в (п,й) кодовом блоке, ~ 2:: Мера разницы между кодовыми словами — число соответствующих элементов или '~" позиций, в которых они различаются. Эта мера называется расстоянием Хемминга между двумя кодовыми словами и обозначается д„. Ясно, что И„при 1~~ удовлетворяет условию 0 <4„.
< н. Наименьшее значение из набора (Ы„) для М кодовых слов называется минимальным расстоянием кода и обозначается Ы . Поскольку хеммингово расстояние ',~:, па~ ' является мерой различия между парами кодовых слов, оно, разумеется, имеет отношение к коэффициенту корреляции между соответствующими парами сигналов, генерируемыми кодовыми словами. Эга связь обсуждается в разделе 8.1.И. Помимо классификации кодов на двоичные и недвоичные можно также их классифицировать на линейные и нелинейные. Возьмем С и С, — два кодовых слова в блоковом коде (п,И) и и,, и„— какие-либо два скалярных элемента из определенного алфавита. Тогда код называют линейным, если и только если а,С,.
+а.,С,. тоже является кодовым словом. Это определение подразумевает, что линейный код должен содержать кодовое слово из одних нулей. Как следствие, код с постоянным весом нелинейный. Предположим, что мы имеем двоичный линейный блоковый код„н пусть С„: = 1, 2, ..., М, где М вЂ” число кодовых слов.
Для удобства пусть С, означает кодовое слово из одних нулей, т.е. С, =(00...0~ и пусть и, означает вес г-го кодового слова. Отсюда следует, что и, является хемминговым расстоянием между кодовыми словами С, и С,. Т.е. расстояние И„= и„. В общем, расстояние д„. между парой кодовых слов С, и С, просто равно весу кодового слова, сформулированного разностью между С, и С,. Поскольку код линейный, разность (что эквивалентно взятию суммы по шод 2 двоичных кодовых слов) между С, и С, также является кодовым словом с весом, включенным в набор (я~,~. Следовательно, распределение весов линейного кода полностью характеризует дистанционные свойства кода. Минимальное расстояние кода равно а~ = ппп(ир ~ (8.1.1) Определенное число элементарных понятий из линейной алгебры особенно полезны, когда имеем дело с линейными блоковыми кодами.
В частности, набор из всех векторов с п элементами формирует векторное пространство о". Если мы выберем набор из Ф <н линейно независимых векторов из о" и из них сформируем набор из всех линейных комбинаций этих векторов, то результирующий набор образует подпространство в 5, назовем его о, размерности 1. Любой набор из х линейно независимых векторов в пространстве о", образует базис.
Теперь рассмотрим набор из векгоров Я, которые 354 ' 8.1.1. Порождающая н проверочная матрицы Пусть хьо х „..., х, означает Й информационных бнт, кодируемых в кодовое слово С . В зтой главе мы следуем установленным соглашениям о представлении кодовых слов в виде векторов.
Так, вектор из Й информационных бит на входе кодера обозначается так: Х =[х„, х„„... х, а выходом кодера является вектор из и символов С =(с,с,...с ]. - Операцию кодирования, выполняемую в линейном двоичном блоковом коде, можно представить совокупностью из п уравнений вида с,„= х„,~ф, +х„а81 +....+х ~ф., /= 1,2,...,и, (8.1.2) где я„..
= О или 1, а х .8ь представляют произведение х . и уа . Линейные уравнения (8.1.2) можно также представить в матричной форме С =ХС, (8.1.3) где С вЂ” порождающая матрица кода, равная +-ф -ь + Яг Я'и Кп " % Ып 8п " Ап (8.1.4) Ум ьь2 * Кы Заметим, что произвольное кодовое слово — зто просто линейная комбинация векторов 18,] из С, С =х,я, +х„,я,+....+х,я, (8.1.5) Поскольку линейный (и,Й) код с 2' кодовыми словами является подпространством размерности 1г, векторы (8,] порождающей матрицы С должны быть линейно независимыми, т.е. они должны образовывать пространство размерности й.
Другими словами, (8,] должны образовать базис для (п,й) кода. Заметим, что ансамбль базовых 23* ортогональны к каждому вектору базиса Я, (и, следовательно, они ортогональны ко всем векторам в Я ). Этот набор векторов также является подпространством Я и он называется нуль-пространством или ортогональным пространством к Я,. Если размерность пространства Я, равна А, то размерность нуль-пространства равна и — Ф. Если пользоваться терминами, предназначенными для двоичных блоковых кодов, векторное пространство Я состоит из 2" двоичных векторов с п элементами. Линейный (.
п,л) код является ансамблем 2 векторов с и элементами, называемыми кодовыми ь словами, которые формируют подпространство Я, в поле из двух злемеигов. Поскольку имеется 2' кодовых слов в Я„базис для Я, имеет Ф кодовых слов. Зто значит, что для конструирования 2' линейных комбинаций требуется А линейно независимых кодовых слов, которые формируют весь код. Нуль-пространство для Я.
образует другой линейный код, который состоит из 2" ~ кодовых слов блока длиной п с п — И информационными битами. Его размерность равна и- Ф. В разделе (8.1.1) мы рассмотрим зги соотношения с большими подробностями. векторов не единственный и, следовательно, С не уникальна. Мы также заметим, что,: поскольку пространство имеет размерность К ранг матрицы С равен к. Любую порождающую матрицу (п,к) кода путем проведения операций над строками (и перестановкой столбцов) можно свести к «систематической формегк 1 0 о О Р11 р1з Р1 ° 1 0 ." Ор, р., " р.„,.
С !'1„..:Р)=- . (8 1.6) О О О " ! р„ р„,. " . р„„ „ где 1« 7г хк единичная матрица, а Р— А х(н — «) матрица, которая определяет в-1 избьпочных илн проверочных символов. Заметим, что порождающая матрица систематического кода создает линейный блоковый код, в котором первые Ф бит любого кодового слова идентичны информационным битам, а остающиеся н — 1. бит любого кодового слова являются линейными комбинациями к информационных бит. Эти (н-к) избыточных бита называют паритетными (проверочными) биэами. Результирующий (л,А) код называется в этом случае свстел~ситпеслтеи кодаи. Если (н,А) код порожден матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим.
Однако . такая матрица эквивалентна матрице а систематической форме в том смысле, что одна может быть получена из другах элементарными операциями над строками и перемещением столбцов. Два (н,к) линейных кода. порожденных двумя эквивалентными порождающими матрицами. называют эквивалентными и один может быть получен из другого перестановкой элементов. Такям образом, каждый линейный (и,,() код эквивалентен линейному систематическому (л,Ц коду.
!1ример 8Л.1. Рассмотрим код (7, 4) с порождающей матрицей 1 О О 01 0 ! 0 1 О 01 ! 1 0 0 1 01 1 0 (8 ! 7) Типичное кодовое слово можно выразить так: С„, =(х„„~„,, х, х с„„с„с„„|, де (х,) представляют четыре информационных бита, а (с,) представляют три паритетных бита, определйнных так: с„„= х, +хке+хьн с, =х,+х „+хан (8.1.8) Збб Линейный систематический (н, Ф) двоичный блоковый кодер можно реализовать, используя 1 -битовый регистр сдвига, и — 7г сумматоров (пюо 2), связанных с соответствующими ячейками регистра сдвига и генерирующих проверочные символы которые потом временно располагаются во втором регистре сдвига длины и — Ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
