Прокис Дж. - Цифровая связь (1266501), страница 73
Текст из файла (страница 73)
Затем к информационных бита, а за ними н — к проверочных бита последовательно покидают два ф регистра и подаются на модулятор. Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1) %Ъ Вмднна данн ы нив нь3 а Рис. 8.1.1. Линейный регистр сдвигаддя получении двоичного кода (7,4) Н = ~-Р':1„„~ (8.1. 11) Отрицательный знак в (8.1.11) может быть опущен при работе с двоичными кодами, поскольку вычитание по тод2 идентично сложению по гпод2. кода (7, 4), генерируемого матрицей С, матрицу Н в виде Пример (8.1.2).
Для систематического определяемой (8. 1.7), имеем согласно (8. 1. 11) 1 1 1 01 о о1 (8 1.12) Н= О 1 1 10 О 10 Теперь уравнение С Нт = 0 распадается на три уравнения Хн! + иР нЗ ае х.атх з+х атс и — О, (8.1.1З) х, + х, + х„„+с, — О. Таким образом, видим, что произведение С„Н эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления сч, /=5, б, 7, Это значит, что (8.1.)3) эквивалентно (8.1.8).
357 С любым линейным кодом(л, Й) кодом связандуальный код размерностью и — х, Дуальный код является линейным (и, и — «) кодом с 2" ' кодовыми векторами, которое образуют нуль-пространство по отношению к (и, А ) коду. Порождающая матрица для дуального кода, обозначаемая Н, состоит из и — ат линейно независимых кодовых векторов„выбираемых в нуль-пространстве. Любое кодовое слово С из (и, к) кода ортогонально любому кодовому слову дуального кода.
Следовательно, любое кодовое слово (и, Й ) кода ортогонально любой строке матрицы Н, т.е. С„Нт= О, (8.1 9) где О означает вектор-столбец, состоящий из и — Ф нулей, а С„ — кодовое слово (и,к ) кода. Поскольку (8.1.9) справедливо для любого кодового слова (л, А ) кода, то следует СНт =О, 18.1. 10) где О-теперь й х (и — к) матрица со всеми нулевыми элементами.
Теперь предположим, что линейный (и, й) код является систематическим, и его порождающая матрица дана в систематической форме (8.1.6). Тогда, поскольку СН вЂ” О следует, что р символ увеличит минимальное расстояние на 1. одом. Его проверочная матрица '0 Н (8.1. 15) ,'О 1 1 1 1 ~0 1 Н = в 1 1 1 ". 1~1 где Н вЂ” проверочная матрица исходного кода. Систематический (и, й) код может быть также укорочен размещением в начале информационного блока нулевых символов.
Это значит, что линейный код (н„к)„состоящий из к информационных символов и и — к проверочных может быть укорочен до линейного кода (и — /, к — /), если установить первые / информационных символов (во всех кодовых комбинациях) нулями. Эти символов не передаются по каналу, а н — к проверочных символа рассчитываются обычным образом, как в исходном коде.
Поскольку С = Х С, замена первых / символов Х нулями эквивалентна сокращению числа строк матрицы С за счет удаления первых / строк. Аналогично, вследствие того, что С Нт--0„ мы можем удалить первые / столбцов матрицы Н. Укороченный код (д — /, к — /) состоит из " ' кодовых слов. Минимальное расстояние этих 2" ' кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного (п, к) кода.
Матрицу Н можно использовать в декодере для проверки того, удовлетворяет ли принимаемое кодовое слово У условию (8.1.13)„ т.е. УН = О. Таким образом, декодер. сверяет принятые проверочные символы с соответствующей линейной комбинацией символов у,, у„, у, и у„, которые формируют проверочные символы на передаче Поэтому принято называть Н проверочной матряйей, связанной с (н, к) кодом. Выскажем соображение, касающееся связи минимального расстояния кода и его проверочной матрицы Н. Произведение С„Н с С ~ 0 представляют линейную комбинацию н столбцов Н .
Поскольку С Н" - О, векторы-столбцы Н линейно зависимы. Допустим„что С/ означает кодовое слово с минимальным весом линейного кода (п, Ф) . Оно должно удовлетворять условию С,Н = О. Поскольку минимальный вес равен минимальному расстоянию, следует, что И„,„столбцов Н линейно зависимы.
Альтернативно, мы можем сказать, что не более, чем Ы,„— 1 столбцов Н линейно независимы. Поскольку ранг матрицы Н не больше и — к, имеем и — к гз И,„— 1. Следовательно, а~,„имеет верхнюю границу а~,„<н †к. (8.1.14) Задаваясь линейным двоичным кодом (н, 1) с минимальным расстоянием Ы,„„„мы можем синтезировать линейный двоичный код (н+ 1, /г) путем добавления одного дополнительного проверочного символа к каждому кодовому слову.
Проверочный символ обычно выбирается так, чтобы быть проверочным символом по всем символам кодового слова. Таким образом, добавляемый проверочный символ равен О, если исходное кодовое слово имеет четное число единиц, и равен 1, если кодовое слово имеет нечетное число единиц. Следовательно, если минимальный вес и следовательно минимальное асстояние кода нечетно, добавляемый проверочный Мы называем код (и+ 1„ /г) расмшренныл~ к 8.1.2. Некоторые известные линейные блоковые коды В этом подразделе мы подробнее опишем три типа линейных блоковых кодов, которые часто встречаются на практике и характеризуются своими важными параметрами. (и, 1) = (2" — 1, 2 — 1 — иг), (8.1.16) где и — некоторое положительное целое число.
Например, если ги = 3, мы имеем код (7, 4). Проверочная матрица Н кода Хемминга имеет особое свойство, которое позволяет нам существенно облегчить описание кода. Напомним, что проверочная матрица (и, 7г) кода имеет и — л строк и и столбцов. Для двоичного (и, А) кода Хемминга и = 2 — 1 столбцов состоят из всех возможных двоичных векторов с и — л = и элементами, исключая вектор со всеми нулевыми элементами. Для примера, код (7, 4), рассмотренный в примерах 8.1.1 и 8.1.2, является кодом Хемминга.
Его проверочная матрица состоит из семи вектор- столбцов'(001), (010), (О11), (100), (101), (110), (111) Если необходимо генерировать систематический код Хемминга, то проверочная матрица Н может легко приводиться к систематической форме (8.1.11). Затем соответствующую порождающую матрицу С можно получить из (8.1.11). Заметим, что любые два столбца матрицы Н не являются линейно зависимыми, так как иначе эти два столбца были бы идентичными.
Однако при и > 1 возможно найти три столбца из Н, которые при сложении дают нуль. Следовательно. для (и. 7г) кода Хемминга г~~,„= 3. Путем прибавления ко всем кодовым комбинациям (и, А) кода Хемминга одного проверочного символа получаем расширенный код Хемминга (и+1,А) с Ы, =4. С другой стороны, (и, А) код Хемминга можно укоротить до (и — (, Й вЂ” Ц путем удаления 1 строк порождающей матрицы С и, соответственно, удаления 1 столбцов в проверочной матрице Н. Распределение весов для класса кодов Хемминга (и, гг) известно и выражается в компактной форме посредством следующего весового полинома: А(л) ~1, 4 [(1+~у' +и(1+ к)( «д(1 )ы 1лт) (8 1 1 7) =л и+1 где А, — число кодовых слов с весом г'.
Коды Адамара. Код Адамара получается путем выбора в качестве кодового слова столбцов матрицы Адамара. Матрица Адамара ̄— это и х и матрица (и — четное целое) из единиц и нулей с тем свойством, что один столбец отличается от другого столбца ровно в зи позициЯх. Один столбец матРицы содеРжит одни нУли. Остальные стРоки имеют зти ! нулей и ззи единиц.
Для и = 2 матрица Адамара имеет вид (8.1.1 8) 1 Иногда элементы матрицы Адамара обозначится - 1 н -1. Тогда строки матрицы Адамара взаимно ортагоцольньь Также заметим, что ЛУ= 2" сигналов, полученных из гдамаровскнх кодовых слов пэтом отображения каждого бита кодового слава в двоичный 4ЭМ сигнал, взаимно ортаганальны. 359 Коды Хеммннга. Сюда относятся как двоичные, так и недвоичные коды Хемминга.
Мы ограничим обсуждение свойствами двоичных кодов Хемминга. Они включают класс кодов со свойствами Затем из матрицы Адамара М„можно генерировать матрицу Адамара М,„согласно соотношению м„=[ (8.1.19) где М„означает дополнение матрицы М„(нули заменятся единицами и наоборот). Так, подставив (8.1,18) в (8.1.19), получим 0 0 0 0 О 1 0 1 0 О 1 1 0 1 1 0 (8.1.20) Дополнение к М4 равно 1 1 1 1 1 О 1 0 1 1 0 0 (8.1.21) 1 О О 1 Теперь строки из М, и М„формируют линейный двоичный код с длиной блока и =4, имеющий 2п =8 кодовых слов.
Минимальное расстояние кода И,„= и и =2. Путем повторного применения (8.1.19) мы можем генерировать код Адамара с длиной и =2, Й=1о8,2и=!о8,2 "=т+1 и Ы. =,п=2 ', где т — положительное целое число. В дополнение к важному частному случаю, когда и = 2, возможны коды Адамара с другой длиной блока, но эти коды нелинейные. Код Голея. Код Голея — это двоичный линейный код (23, 12) с а~„,„=7. Расширенный двоичный линейный код Голея (24, 12) с Ы =8 получается из кода Голея путем добавления ко всем кодовым комбинациям проверочного символа.
Таблица (8.1.1)- показывает распределение весов кодовых слов кода Голея (23, 12) и расширенного кода Голея (24, 12). Мы обсудим процедуру синтеза кода Голея в разделе 8.1.3. Таблица 8.1.1. Распределение весов кода Голея (23, 12) и расширенного кода Голея (24, 12) Число кодовых слов Вес ко 23 12 код 24 12 Источник: Реееееол и ИlеЫол (1972) збО 0 7 11 12 15 16 23 24 1 253 506 1288 1288 506 253 1 О 1 0 759 0 2576 0 759 0 1 где С,(р) =с,р" '+с„,р" '+...+с,р+с„,. Заметим„что полипом С,(р) представляет кодовое слово С, = (с, . с„, ...с„с„,|„ которое как раз образовано из кодового слова С циклическим сдвигом на одну позицию. Поскольку С,(р) представляет собой остаток, полученный делением РС(р) на р" +1, мы говорим, что С,(р) = РС(р) шо4Р" + 1).
(8.1.24) Аналогичным образом, если С(р) представляет кодовое слово в циклическом коде, тогда р'С(р) пюй(р'+1) также является кодовым словом циклического кода. Так что можно написать р С(р) — ЯЯр + 1)+С(р), (8.1.25) где остаточный полипом С(р) представляет кодовое слово циклического кода, а О(р)— частное. Мы можем генерировать циклический (п,1г) код, используя порождающий полином я(р) степени и-Й с двоичными коэффициентами, который является множителем при факторизации полинома р'+1. Порождающий полипом в общем виде можно записать так Я(Р)=Р +Я,-ьчр +Я;Р+1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
