Прокис Дж. - Цифровая связь (1266501), страница 74
Текст из файла (страница 74)
(8.1.2б) 361 8.1.3. Циклические коды Циклические коды — подкласс класса линейных кодов, которые удовлетворяют следующим циклическим свойствам: если С = 1с„, с„, ...с, со1 — кодовое слово циклического кода, тогда 1с„, с„, ...с, с„11, полученное циклическим сдвигом элементов кода С, также являются кодовым словом. Все циклические сдвиги С образуют кодовые слова. Как следствие циклического свойства, эти коды обладают значительным количеством структурных удобств, которые можно.
использовать при реализации операций кодирования и декодирования. Большое количество алгоритмов эффективных кодеров и декодеров жестких решений были сделаны посредством циклических кодов, что сделало возможным в практических системах связи строить блоковые коды большой длины с большим количеством кодовых слов. Описание специфических алгоритмов находится вне кругозора этой книги. Наша основная цель — вкратце описать некоторые характеристик циклических кодов.
При работе с циклическими кодами принято связывать с кодовым словом С= (с„, с„, ...с, с,| полипом С(р) степени ~ и — 1, определенный так С(р) = с„,р + с„~р +...+с,р+ со . (8.1.22) Для двоичного кода каждый из коэффициентов полинома является нли нулем, илн единицей. Теперь предположим, мы формируем полипом С( ) + 1+ + т+ Этот полипом не может представить кодовое слово„так как его степень может быть равна и (если с„, = 1). Однако если мы разделим РС(р) на р" +1, мы получим РС(р) С,(р) (8.1.23) р" +1 " ' р" +1' р'+! можно Пример 8.1.3. Рассмотрим код с длиной блока п= 7.
Полинам разложить на следующие самножители р +1 = (р+ 1)(р + р + 1)(р + р+ 1) . Чтобы синтезировать циклический код (7,4), мы можем взять порождающих полиномов: (8.1.30) один из двух я,(р) = р'+ р'+ ! или (8.1.З !) К,(р) = р'+ р+! Коды, генерируемые порождающими полиномами 3',(р) и у,(р), эквивалентны.
Кодовые слова кода (7,4), генерируемые полиномом н,(р) = р' + р' + 1 даны в табл. 8.1.2. В общем полинам р" +1 можно факторизовать так: Р+ =8()~Ы. где 8ф) — означает порождающий полинам для циклического (пИ) кода, Ь(р) означает проверочный полинам степени гг. Последний можно использовать для генерирования дуального кода. 362 Мы также определяем полипом информог1нонного сообн1ення Х(р) Х(р) = х,, р' ' + х„,р" '+...+х, р+ х,, (3.1.27) где ~х,, х,,,х, х ~ определяет 1е информационных бит. Ясно, чта произведение Х(р)8(р) — зто полинам степени меньшей или равной и-1, который может представлять кодовое слово.
Заметим, что имеется 2' полинамов (Х,(р)) и, следовательно, имеется 2',:: возможных кодовых слов, которые можно формировать при заданном 8(р). Допустим, что мы обозначим эти кодовые слова так С (р) = Х (р)8(р), гп=1, 2, ...., 2' (8.1.28) Чтобы показать, что кодовые слова в (8.1.28) удовлетворяют циклическому сдвигу, рассмотрим какое-либо кодовое слово С(р) в (8.1.23), Циклический сдвиг С(р) дает С,(р) = рС(р)+с„,(р" +1) (8.1.29) и, поскольку и р" +1 „и С(р) делятся на 8(р) без остатка, то и С,(р) делится на 8(р) без остатка, т.е.
С,(р) можно представить как С,(Р) = Х,(Р)8(Р). Следовательно, циклический сдвиг в кодовом слове С(р), генерируемый согласно (8.1.23), порождаетдругое кодовое слово. Из вышесказанного мы видим, что кодовые слова, обладающие циклическими свойствами, можно генерировать умножением 2' сообщений на уникальный полинам степени >г — Й д(р) — называемый порождающим полиномом циклического (п,й) кода который является множителем при факторизации р" -г1. Циклический кад, генерируемый указанным образом, занимает подпространство а. векторного пространства 5.
Размерность надпространства а', равна Й. Таблица 8.1.2. Циклический код (7,4). ПоРождающий полипом Уг(Р) = Р'+Р'+1 Информационные биты Кодовые слова С атой целью можно использовать полипом, обратный Ь(Р), определяемый так: Р Ь(Р ') = Р''!Р '+ Ц, гР "+...+Ь Р ' + 1) = 1+ Ь„,Р+ Ь„,Р +...+Ь Р ' + Р" (8 1 32) Ясно, что р" +1 делится без остатка и на обратный полинам. Следовательно, Р'Ь(Р ') является порождающим полиномом циклического (и, и — й) кода.
Этот циклический код дуален коду (гг,Ь), генерируемому порождающим полиномом фР). Таким образом, ( и, и — Ф) дуальный код образует нуль-пространство циклического (и, й) кода. Пример 8.1.4. Рассмотрим циклический код, дуальный коду (7,4), генерированному в примере 8.1.3. Зтот дуальный циклический код (7,3~ связан с проверочным полиномом Ь(Р) (Р+!)(Рз+Рг+1) Рг+Рз+Рг+1 (8 ! 33) Обратный полипом равен Р Ьг!Р ) =!+Р+Р +Р . Этот полипом генерирует дуальный код (7, 3), данный в таблице 8.1.3.
Читатель может убедиться в том, что.кодовые слова дуального кода (7, 3) ортогональны кодовым словам циклического кода (7,4) из примера 8.1.3. Заметим, что ни код (7, 4), ни код (7,3) не являются систематическими. Желательно показать, как можно получить порождающую матрицу из порождающего полинома циклического кода (и, Ь).
Как указано выше, порождающую матрицу для (и, Ь) кода можно сконструировать из любого набора Й линейно независимых кодовых слов. По заданному порождающему пол иному фР) легко генерировать набор й линейно независимых кодовых слов — зто кодовые слова, соответствующие набору Й линейно независимых полиномов Р' ЯР), Р 8(р), ..., Р8(Р), 8(Р). Р 0 О 0 0 0 О 0 0 1 1 1 1 1 1 1 1 Р Р Р О 0 0 О 0 1 0 1 0 0 1 1 1 0 О 1 О 1 1 1 О 1 1 1 0 0 0 0 0 1 0 1 О 0 1 1 1 0 0 1 0 1 1 1 О 1 1 1 Р 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Р Р Р О 0 0 О 0 1 0 1 1 0 1 0 1 1 О 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 О О 0 0 0 0 1 Р Р Р 0 0 0 1 0 1 0 1 0 1 1 1 1 О 0 0 0 1 1 1 0 0 1 1 0 0 О 1 О 1 0 1 0 1 1 1 1 0 0 О О 1 1 0 0 1 1 Таблица 8.1.3.
Дуальный код (7, 3). Порождающий полипом р'Ьу(р ') = 1+ р+ р'+ р" Информационные биты Кодовые слова Поскольку любой из полиномов степени меньшей или равной и — 1, который делится на 8(р), можно выразить как линейную комбинацию этих полиномов, набор образует базис размерностью я.
Следовательно, кодовые слова, связанные с этими полиномами, формируют базис размерности Й для циклического кода (и, Й) . Пример 8.1.5. Четыре строки порождающей матрицы для циклического кода (7, 4) с порождающим полиномом у,(р) = р'+р +1 можно получить из полиномов Рй(Р)=Р +Р +р, г=3,2, 1, О. Легко видеть, что порождающая матрица равна (8.1.34) 1 1 0 1 0 О 0 О 1 1 0 1 0 0 0 О 1 1 О 1 0 0 0 0 1 1 0 ! Аналогично, порождающая матрица для циклического кода (7, 4), образуемая поРождающим полиномом 8г(Р) = Р'+ Р+ 1, Равна 1 0 1 1 0 О 0 (8.1.35) 0 1 О 1 1 0 0 0 0 1 0 1 1 0 ооо! а Проверочные матрицы, соответствующие С, и С„можно сконструировать аналогичным образом, используя соответствующие обратные полиномы (задача 8.8).
Эаметим, что порождающие матрицы, полученные таким конструированием, не имеют систематическую форму. Мы можем сконструировать порождающую матрицу циклического кода в систематической форме С вЂ” [1„:Р] от порождающего полинома ыаау щ або о . да а~~, у- усама С со у ю~ осу ф р р-"ая1! у=у,г,...,а, о я!р)- ° °,, -. а- -а.э; форму можно получить делением р" ' на 8(р).
Таким образом, имеем Р Р Р 0 0 О 0 0 1 О 1 0 О 1 1 1 0 0 1 О 1 1 1 0 1 1 1 Р Р 0 О 0 0 0 1 0 1 1 0 1 0 1 1 1 1 Р Р 0 0 1 0 0 1 1 1 1 1 0 1 1 0 О 0 г ~ о 0 0 0 1 1 1 1 1 О 0 0 1 1 О 0 0 1 1 0 1 0 1 0 1 или„ что эквивалентно Пример $.1.6. Дпя циклического кода (7, 4) с порождающим полиномом 8«(р) = р'+ р+ 1, ранее рассмотренного в примере 8.1.5, имеем Р' =(Р'+Р+~)И (Р)+р'+1, Р' =(Р'+ )К,(р)+ р'+ р+1, р' = л,(р)+р'+р. Р' = 8;(Р)+Р+1.
Следовательно, порождающая матрица кода в систематической форме 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 (8.1.37) 0 0 О 1 0 1 1 и соответствующая проверочная матрица 1 1 1 О 1 0 О Н„=0111010 1 1 0 1 0 О 1 (8.1,38) Оставляем в качестве упражнения для читателя показать, что порождающая матрица С„даваемая (8.1.35) и матрица С„в систематической форме (8.1.37) генерируют одинаковые наборы кодовых слов (задача 8.2). Метод конструирования порождающей матрицы С в систематической форме согласно (8.1.36) также подразумевает, что систематический код можно генерировать непосредственно из порождающего полинома 8(р).
Предположим, что мы умножим полипом сообщения Х(р) на р" «. Тогда получим Р Х(Р) ~«-1Р + ~«-«Р +" ~к| Р + хор В систематическом коде этот полипом представляет первые к бит слова С(р). К этому полиному мы должны прибавить полипом степени меньшей, чем и-к, представляющей проверочные символы. Теперь, если р" «Х(р) разделить на 8(р), результат равен р~х» ~~ «Ы или р Х(р) = 0(р)ДР)+ (р), (8.1.39) 365 р" ' = 0,(р)К(р)+й,(р), 1= 1, 2, ..., й, (8.1.3б) где Я(р) — частное. Но р" +Н,(р) представляет кодовое слово в циклическом коде, поскольку р" ' + Щ(р) = Я(р)8(р) . Следовательно, желательный поли ном, соответствующий «-й строке С, равен р '+ Л,(р) . где г(р) имеет степень меньшую, чем и — х. Ясно, что 0(р)д(р) — это кодовое слово циклического кода. Следовательно, суммируя (по пю4 2) г(р) с обеими частями (8.
!.39), мы получаем желаемый систематический код. Подытоживая, скажем, что систематический код можно генерировать так: 1. Умножаем полипом сообщения Х(р) на р" "; 2. Делим р" 'Х(р) на д(р), чтобы получить остаток г(р); и 3. Добавляе ~(р) р" 'Х(р). Ниже мы продемонстрируем, как эти вычисления можно выполнить, используя сдвиговые регистры с обратной связью. Поскольку р" +1 = Ь(р)Ь(р) или, что эквивалентно, 8(р)Ь(р) = О той(р" + 1), мы видим, что полиномы д(р) и Ь(р) ортогональны. Далее, полиномы р'~~р) и р'Ь(р) также ортогональны для всех ! и !'.
Однако, векторы, соответствующие полиномам й(р) и Ь( р), ортогональны только, если порядок следования элементов одного из этих векторов реверсировать. То же угверждение применимо к векторам, соответствующим полиномам р'у(р) и р'Ь(р). Действительно, если проверочный полипом Ь(р) используется как порождающий для (л, и — А) дуального кода, ансамбль кодовых слов, полученный так, включают в себя те же кодовые слова, которые генерируются обратным полиномом, за исключением того, что кодовые векторы реверсированы. Это подразумевает, что порождающая матрица для дуального кода, полученная от обратного полинома р"Ь(р '), может быть также получить непосредственно от Ь(р).
Поскольку проверочная матрица Н для циклического кода (н, Й) является порождающей матрицей для дуального кода, следует, что Н также можно получить от Ь(р). Следующий пример иллюстрируют это соотношение. Пример 3.1.7. Дуальный код для циклического кода 17„4), порождаемого полиномом д,(р) = р' + р' + 1, — это код 17, 3), который порождается обратным полиномом р"Ь,(р ') = р'+р +р+1. Однако„мы можем также использовать Ь,(р) для получения порождающей матрицы для дуального кода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
