Прокис Дж. Цифровая связь (2000) (1151856), страница 75
Текст из файла (страница 75)
Один столбец матрицы содержит одни нули. Остальные строки имеют за и 1 нулей и оп единиц. Для и = 2 матрица Адамара имеет вид (8.1.18) ' Иногда элементы матрицы Адамара обозначаииса - 1 н -1. Тогла строки матрицы Адамара взаимно ортогональны. Также заметим, что М= 2 сигналов, полученных из адамаровскнх кодовых слов путем отображения каждого бита кодовою слова в двоичный ФМ сигнал, взаимно ортогональны.
359 где гп — некоторое положительное целое число, Например, если т = 3, мы имеем код (7, 4). Проверочная матрица Н кода Хемминга имеет особое свойство, которое позволяет нам существенно облегчить описание кода. Напомним, что проверочная матрица (и, 1г) кода -имеет п — 1г строк и и столбцов. Для двоичного (и, 1г) кода Хемминга и=2" — 1 столбцов состоят из всех возможных двоичных векторов с и — 1г = ги элементами, исключая вектор со всеми нулевыми элементами, Для примера, код (7, 4), рассмотренный в примерах 8.1.1 и 8,1.2, является кодом Хемминга. Его проверочная матрица состоит из семи вектор- столбцов (001), (010), (011), (100), (101), (110), (111). Если необходимо генерировать систематический код Хемминга, то проверочная матрица Н может легко приводиться к систематической форме (8.1.11).
Затем соответствующую порождающую матрицу С можно получить из (8.1.11). Заметим, что любые два столбца матрицы Н не являются линейно зависимыми, так как иначе эти два столбца были бы идентичными. Однако при т > 1 возможно найти три столбца из Н, которые при сложении дают нуль. Следовательно, для (и, к) кода Хемминга г1,„= 3. Путем прибавления ко всем кодовым комбинациям (и, 1г) кода Хемминга одного проверочного символа получаем расширенный код Хемминга (и+1, 1г) с Ы „=4. С другой стороны, (и, 1г) код Хемминга можно укоротить до (п-1, 1г-1) путем удаления 1 строк порождающей матрицы С и„соответственно, удаления 1 столбцов в проверочной матрице Н.
Распределение весов для класса кодов Хемминга (и, 1г) известно и выражается в компактной форме посредством следующего весового полинома: Затем из матрицы Адамара М„можно генерировать матрицу Адамара М,„согласно соотношению М2 М М (8.1.19) где М„означает дополнение матрицы М„(нули заменятся единицами и наоборот). Так, подставив (8.1.18) в (8.1.19), получим 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 О М4 (8.1.20) Дополнение к М, равно 1 1 1 1 1 0 1 0 1 1 0 0 м„= (8.1.21) 1 0 0 1 Теперь строки из Ме и М4 формируют линейный двоичный код с длиной блока и=4, имеющий 2п=8 кодовых слов. Минимальное расстояние кода Ы,„= ьп=2. Путем повторного применения (8.1,19)'мы можем генерировать код Адамара с длиной и = 2 Ф=1о8,2п=1о8,2"" =и+1 и Ы .
=тп=2 ', где т — положительное целое число. В дополнение к важному частному случаю, когда и = 2, возможны коды Адамара с другой длиной блока, но эти коды нелинейные. Код Голеи. Код Голея — это двоичный линейный код (23, 12) с И„,„=7. Расширенный двоичный линейный код Голея (24, 12) с 1, =8 получается из кода Голея путем добавления ко всем кодовым комбинациям проверочного символа. Таблица (8.1.1) показывает распределение весов кодовых слов кода Голея (23, 12) и расширенного кода Голея (24, 12). Мы обсудим процедуру синтеза кода 1 алея в разделе 8.1.3.
Таблица 8.1.1. Распределение весов кода Голея (23, 12) и расширенного кода Голея (24, 12) Числа кодовых слов Вес ко 24 12 код 23 12 Источник: Ре~еееоп н Ке1йоп (1972) 360 0 11 12 15 16 23 24 1 253 506 1288 1288 506 253 1 0 1 0 759 0 2576 0 759 0 1 8.1.3. Циклические коды Циклические коды -подкласс класса линейных кодов, которые удовлетворяют следующим циклическим свойствам: если С = 1с„, с„, ...с, со1 — кодовое слово циклического кода, тогда [с„ г с„, ...с, с„ 11, полученное цикли еским сдвигом элементов кода С, также являются кодовым словом.
Все циклические сдвиги С образуют кодовые слова. Как следствие циклического свойства, эти коды обладают значительным количеством структурных удобств, которые можно. использовать при реализации операций кодирования и декодирования. Большое количество алгоритмов эффективных кодеров и декодеров жестких решений были сделаны посредством циклических кодов, что сделало возможным в практических системах связи строить блоковые коды большой длины с большим количеством кодовых слов, Описание специфических алгоритмов находится вне кругозора этой книги.
Наша основная цель — вкратце описать некоторые характеристик циклических кодов. При работе с циклическими кодами принято связывать с кодовым словом С =(с„, с„, ...с, с,1 полипом С(р) степени < п-1, определенный так С(Р) = с.-~р" '+с.-гр" '+ "+с~р+со. (8.1.22) Для двоичного кода каждый из коэффициентов полинома является или нулем„или единицей.
Теперь предположим, мы формируем полином РС(р) = с гр +с гр +...+сгр +сор. Этот полином не может представить кодовое слово, так как его степень может быть равна п (еслн с, = 1). Однако если мы разделим РС(р) на р" +1, мы получим РС(р) С(р) (8.1.23) р" +1 " ' р" +1' где С (р) = РС(р) шод(р" + 1) . (8.1.24) Аналогичным образом, если С(р) представляет кодовое слово в циклическом коде, тогда р'С(р) шоо(р" +1) также является кодовым словом циклического кода. Так что можно написать р С(р) = фр)(р" + 1)+С,(р), (8.1.25) где остаточный полипом С(р) представляет кодовое слово циклического кода, а Д(р)— частное. Мы можем генерировать циклический (п,х) код, используя порождающий гголином 8(р) степени п — Й с двоичными коэффициентами, который является множителем при факторизации полинома р" +1.
Порождающий полинам в общем виде можно записать так 8(Р) = Р +8' ~-1Р +К~Р+1 (8.1.26) 361 С1(р) — С гр +С р +...+Сор+С Заметим, что полипом С,(р) представляет кодовое слово С, =[с„г с„, ...с, с„,1, которое как раз образовано из кодового слова С циклическим сдвигом на одну позицию. Поскольку С,(р) представляет собой остаток, полученный делением РС(р) на р" +1, мы говорим, что а(р) = р'+р'+1 или й(р) = Р + Р+ 1. Коды, генерируемые порождающими полиномами д,(р) и д,(р), эквивалентны. Кодовые слова кода (7,4), генерируемые полиномом у,(р) = р'+ р" +1 даны в табл. 8.1.2.
В общем полипом р" +1 можно факторизовать так: р + 1 = 8(р)п(р) где дф) — означает порождающий полином для циклического (П'к) кода, й(р) означает проверочный полипом степени Ф, Последний можно использовать для генерирования дуального кода. (8.1.31) Мы также определяем полином ингрорл~ационного сообщения Х(р) Х(р) = х,,р' '+х„,р' '+...+х,р+ х„ (8.!.27) где )х,, х,, ...х, х,1 определяет к информационных бит. Ясно, что произведение Х(р)8(р) — это полипом степени меньшей илн равной п-1, который может представлять кодовое слово. Заметим, что имеется 2 полиномов (Х,.(р)~ и, следовательно, имеется 2' возможных кодовых слов, которые можно формировать при заданном 8(р) . Допустим, что мы обозначим зти кодовые слова так С„(р) = Х„,(р)8(р), т = 1, 2, ...., 2 (8.1.28) Чтобы показать, что кодовые слова в (8.1.28) удовлетворяют циклическому сдвигу, рассмотрим какое-либо кодовое слово С(р) в (8.1.28), Циклический сдвиг С(р) дает С,(р) = рС(р)+с„,(р" +1) (8.1.29) и, поскольку и р" +1, и С(р) делятся на д(р) без остатка, то и С,(р) делится на 8(р) без остатка, т.е.
С,(р) можно представить как С,(р) = Х,(р)8(р). Следовательно, циклический сдвиг в кодовом слове С(р), генерируемый согласно (8.1.28), порождает другое кодовое слово. Из вышесказанного мы видим, что кодовые слова, обладающие циклическими свойствами, можно генерировать умножением 2" сообщений на уникальный полипом степени и — 1с 8(р) — называемый порождающим полиномом циклического (п,й) кода, который является множителем при факторизации р" +1. Циклический код, генерируемый указанным образом, занимает подпространство о", векторного пространства з, Размерность подпространства о', равна Ф.
Иример 8.1.3. Рассмотрим код с длиной блока п=7. Полипом р'+1 можно разложить на следующие сомножители 7 + 1 ( + 1)( 3 + 2 + 1)( 3 + + 1) (8.1.30) Чтобы синтезировать циклический код (7,4), мы можем взять один из двух порождающих полиномов: Зб2 Таблица 8.1.2. Циклический код (7,4). Порождающий полином д,(р) = р'+р'+1 Информационные биты Кодовые слова С этой целью можно использовать поливом, обратный !2(р), определяемый так: р Ь~ )=р (р ~+И„,р ~'+...+72р ~ +1)=1+Б,,р+Ь, 2р +...+72р +р (8.1,32) Ясно, что р'+1 делится без остатка и на обратный полином. Следовательно, р" Ь(р ') является порождающим полиномом циклического (и, и — х) кода.
Этот циклический код дуален коду (и,Ф), генерируемому порождающим полиномом 8(р). Таким образом, (и, и — й) дуальный код образует нуль-пространство циклического (и, И) кода. Пример 8,1.4. Рассмотрим циклический код, дуальный коду (7,4), генерированному в примере 8.1.3.
Этот дуальный циклический код (7,3) связан с проверочным полиномом МР)=(Р+1)(Р +Р +1)=Р+Р +Р +! (8133) Обратный полипом равен 4! ( -1) 1+ + 2+ 4 Этот полипом генерирует дуальный код (7, 3), данный в таблице 8.1.3. Читатель может убедиться в том, что кодовые слова дуального кода (7, 3) ортогональны кодовым словам циклического кода (7, 4) из примера 8.1.3. Заметим, что ни код (7, 4), ни код (7, 3) не являются систематическими.
Желательно показать, как можно получить порождающую матрицу из порождающего полинома циклического кода (и,Ф). Как указано выше, порождающую матрицу для (и,1) кода можно сконструировать из любого набора й линейно независимых кодовых слов. По заданному порождающему полиному 8'(р) легко генерировать набор х линейно независимых кодовых слов — это кодовые слова, соответствующие набору А линейно независимых полиномов р 8(р), р 8(р), ..., Рд(р), 8(р). 363 Р Р Р Р 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 О 1 1 1 1 0 1 1 1 1 Р Р Р 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 Р Р Р 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 Таблица 8.1.3. Дуальный код (7, 3), Порождающий полинам Р4Ь,(Р ') = 1+ р+р'+р4 Информационные биты Кодовые слова Поскольку любой из полиномов степени меньшей или равной п — 1, который делится на д(р), можно выразить как линейную комбинацию этих полиномов, набор образует базис размерностью /с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
