Прокис Дж. Цифровая связь (2000) (1151856), страница 74
Текст из файла (страница 74)
В разделе (8.1.1) мы рассмотрим эти соотношения с большими подробностями. 8'о Ки "' й К2! 822 К2» (8.1.4) Км Хм "' Я» Заметим, что произвольное кодовое слово — это просто линейная комбинация векторов (д,~ из С, С„=х„,8, +х„,я,+....+х д, (8.1.5) Поскольку линейный (п,А) код с 2" кодовыми словами является подпространством размерности Ф, векторы (8,.) порождающей матрицы С должны быть линейно независимыми, т.е. они должны образовывать пространство размерности Ф. Другими словами, (8,.) должны образовать базис для (п,к) кода.
Заметим, что ансамбль базовых 23* 355 8.1.1. Порождающая и проверочная матрицы Пусть х „х„„..., х, означает А. информационных бит, кодируемых в кодовое слово С„. В этой главе мы следуем установленным соглашениям о представлении кодовых слов в виде векторов. Так, вектор из Ф информационных бнт на входе кодера обозначается так: Х ~х ~ х»» хщ~ ~ > а выходом кодера является вектор из п символов С„=(с„, с„, ... с ).
Операцию кодирования, выполняемую в линейном двоичном блоковом коде, можно представить совокупностью из и уравнений вида с,„= х„,д~+ х„ву„+....+х,уя, 1 = 1,2,...,п, (8.1.2) где 8» = О или 1, а х .я„.. представляют произведение х,. и я,, Линейные уравнения (8.1.2) можно также представить в матричной форме С =Х„С, (8.1.3) где С вЂ” порождающая матрица кода, равная векторов ие единственный и, следовательно, С не уникальна, Мы также заметим, что, поскольку пространство имеет размерность к, ранг матрицы С равен Ф. Любую порождающую матрицу (и, я) кода путем проведения операций над строками (и перестановкой столбцов) можно свести к «систематической форме».
О О" Ор„р„" р,„„ 1 0 " Ор„р„" р,„, =М 1= (8.1.6) ООО "1р„, р„" р„ Пример 8.1.1. Рассмотрим код (7, 4) с порождающей матрицей 1 0 0 01 0 1 0 1 0 01 1 1 0010110 (8.1.7) 0 0 0 10 1 1 Типичное кодовое слово можно выразить так: С„= (х, х„, х„, х „с„с„с,|, где (х,) представляют четыре информационных бита, а (с,) представляют три паритетных бита, определенных так: с , = хм + х„„ + х„„, (8.1.8) л~б ю2 аЗ в47 с 7 — хт! + хв2 +хлю4 Линейный систематический (п, Ф) двоичный блоковый кодер можно реализовать, используя Ф -битовый регистр сдвига, п — й сумматоров (птод 2), связанных с соответствующими ячейками регистра сдвига и генерирующих проверочные символы, которые потом временно располагаются во втором регистре сдвига длины п — й .
Затем А информационных бита, а за ними п — к проверочных бита последовательно покидают два регистра и подаются на модулятор. Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1) 356 где 1» — 1хФ единичная матрица, а Р— хх(п — х) матрица, которая определяет и — А избыточных или проверочных символов. Заметим, что порождающая матрица систематического кода создает линейный блоковый код, в котором первые к бит любого кодового слова идентичны информационным битам„а остающиеся и — Ф бит любого кодового слова являются линейными комбинациями к информационных бит. Эти (и — Ф) избьггочных бита называют паритетными (проверочными) битами.
Результирующий (и, /~) код называется в этом случае систематическим ког)ом. Если (п,7г) код порожден матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим. Однако, такая матрица эквивалентна матрице в систематической форме в том смысле, что одна может быть получена из другой элементарными операциями над строками и перемещением столбцов. Два (п,А) линейных кода, порожденных двумя эквивалентными порождающими матрицами. называют эквивалентными и один может быть получен из другого перестановкой элементов. Таким образом, каждый линейный (п,1) код эквивалентен линейному систематическому (п,х) коду. Вхадные денные дные ные Рис. 3.1.1.
Линейный регистр сдвига для получения двоичного кода (7,4) (8.1.1 1) Отрицательный знак в (8.1.11) может быть опущен при работе с двоичными кодами, поскольку вычитание по шод2 идентично сложению по шод2. Пример (8.1.2). Для систематического кода (7, 4), генерируемого матрицей я, определяемой (8.1,7), имеем согласно (8.1.11) матрицу Н в виде 010 О~ 0111010~. Н= (8.1. 12) 1 1 О'10 О 1 Теперь уравнение С Нт = О распадается на три уравнения х, +х, +х„, +с, =О, ен ео еы нб > (8.1.13) х ~+х ~+х +с т — О, Таким образом, видим, что произведение СнН эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления с, г' = 5, б, 7.
Это значит, что (8.1,13) эквивалентно (8.1.8). 357 С любым линейным кодом (п, 7г ) кодом связан дуальный код размерностью и — 1г, Дуальный код является линейным (п,п-я) кодом с 2" ' кодовыми векторами, которое образуют нуль-пространство по отношению к (п, Ф) коду. Порождающая матрица для дуального кода, обозначаемая Н, состоит из п-гс линейно независимых кодовых векторов, выбираемых в нуль-пространстве. Любое кодовое слово Сн из (п, Ф) кода ортогонально любому кодовому слову дуального кода.
Следовательно, любое кодовое слово (и, ~г ) кода ортогонально любой строке матрицы Н, т.е. С Нт=о, (8.1 9) где О означает вектор-столбец, состоящий из и-К нулей, а С„- кодовое слово (п, Ф ) кода. Поскольку (8.1.9) справедливо для любого кодового слова (и, 1г ) кода, то следует СН =О, (8.1.10) где О-теперь 1 х(п — гг) матрица со всеми нулевыми элементами. Теперь предположим, что линейный (и, й) код является систематическим, и его порождающая матрица дана в систематической форме (8.1.б). Тогда, поскольку СН' = О, следует, что Матицу Н можно использовать в декодере для проверки того, удовлетворяет ли принимаемое кодовое слово к' условию (8.1.13), т.е.
УН = О . Таким образом, декодер сверяет принятые проверочные символы с соответствующей линейной комбинацией символов у„у„у, и у4, которые формируют проверочные символы на передаче. Поэт~му принято называть Н проверочной матрилец связанной с ~п, Iс) кодом. Выскажем соображение, касающееся связи минимального расстояния кода и его проверочной матрицы Н. Произведение С Н с С„, ~ О представляют линейную комбинацию п столбцов Н . Поскольку С Н = О, векторы-столбцы Н линейно зависимы. Допустим, что С,. означает кодовое слово с минимальным весом линейного кода (и, к) . Оно должно удовлетворять условию С,.Н = О.
Поскольку минимальный вес равен минимальному расстоянию, следует, что И ,.„столбцов Н линейно зависимы. Альтернативно, мы можем сказать, что не более, чем а' ь — 1 столбцов Н линейно независимы. Поскольку ранг матрицы Н не больше и — к, имеем п — К > д — 1. Следовательно, а~ . имеет верхнюю границу И и сп-1+1, (8.1.14) Задаваясь линейным двоичным кодом (и, к) с минимальным расстоянием а', мы можем синтезировать линейный двоичный код (и+1, й) путем добавления одного дополнительного проверочного символа к каждому кодовому слову. Проверочный символ обычно выбирается так, чтобы бьггь проверочным символом по всем символам кодового слова.
Таким образом, добавляемый проверочный символ равен О, если исходное кодовое слово имеет четное число единиц, и равен 1, если кодовое слово имеет нечетное число единиц. Следовательно, если минимальный вес и, следовательно, минимальное расстояние кода нечетно, добавляемый проверочный символ увеличит минимальное расстояние на 1. Мы называем код (и+ 1, /с) расширенмым кодом. Его проверочная матрица (8.1.15) Н Н,= 1 1 1 " 1~1 358 где Н- проверочная матрица исходного кода. Систематический (п, к) код может бьггь также укорочен размещением в начале информационного блока нулевых символов.
Это значит„что линейный код (и, Ф), состоящий из Ф информационных символов и и-Ф проверочных может быть укорочен до линейного кода (п-1, Й-1), если установить первые 1 информационных символов (во всех кодовых комбинациях) нулями. Эти символов не передаются по каналу, а и — Й проверочных символа рассчитываются обычным образом, как в исходном коде. Поскольку С = Х С, замена первых 1 символов Х„, нулями эквивалентна сокращению числа строк матрицы С за счет удаления первых! строк. Аналогично, вследствие того, что С Нт=о, мы можем удалить первые 1 столбцов матрицы Н.
Укороченный код (и — 1, х — !) состоит из 2" ' кодовых слов. Минимальное расстояние этих 2' ' кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного (и, к) кода. 8.1.2. Некоторые известные линейные блоковые коды В этом подразделе мы подробнее опишем три типа линейных блоковых кодов, которые часто встречаются на практике н характеризуются своими важными параметрами, Коды Хеммингн.
Сюда относятся как двоичные, так и недвоичные коды Хемминга Мы ограничим обсуждение свойствами двоичных кодов Хемминга. Они включают класс кодов со свойствами 1и, 1г) = ~2 — 1, 2" — 1- и), (8,1.16) где А, — число кодовых слов с весом 1. Коды Адамара. Код Адамара получается путем выбора в качестве кодового слова столбцов матрицы Адамара.-Матрица Адамара М„ — это и хп матрица (и — четное целое) из единиц и нулей с тем свойством, что один столбец отличается от другого столбца ровно в з,и позициях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
