Вернер М. Основы кодирования (2004) (1151882), страница 22
Текст из файла (страница 22)
Используя эту таблицу, очень легко определить двоичный эквивалент элемента а* по заданному г, 0 < г < 14. Таблица логарифмов(табл." 2.6), наоборот, позволяет быстро найти степень примитивногоэлемента а по его двоичному представлению.Так как операция деления в полях Галуа эквивалентна умножению на обратный элемент, весьма полезной при вычислениях оказывается таблица обратных элементов (табл. 2.7), которая для поля4GF(2 ) строится следующим образом. Пусть, например, нам нужно найти обратный элемент к (1010).
По таблице логарифмов находим, что (1010) соответствует а 9 . Обратным элементом к а 9 является а 1 5 " 9 = а 6 . По таблице антилогарифмов находим, что двоичным160Глава 2. Линейные блоковые кодыТаблица 2.6. Таблица логарифмов элементов GF(2 4 ).0001 0010 ООН 0100 01010аа1а4а2а8ОНО 0111 1000 1001 1010 1011 1100 1101а5а10а3ыаа9а7а6а13шо 1111а11а12эквивалентом а 6 является (1100). Таким образом, окончательно получаем (1010)-1 = (1100).При небольших значениях т для ускорения умножения при программной реализации можно построить таблицу умножений элементов ноля GF(2m) размерности 2т х 2т. После того, как все необходимые арифметические таблицы построены, можно заменить двоичныеобозначения на целочисленные.Реализация операции сложения (и совпадающей с ней операциивычитания) элементов в поле GF(2m) не представляет проблем.
Сложение элементов из GF(2 m ) сводится к покомпонентному сложениюих двоичных представлений по модулю 2. Так, например, в нолеGF(2 4 ) (ООН) + (1101) = (1110).Таблица 2.7. Таблица обратных элементов ноля GF(24).0001 0010 0011 0100 0101 0110 0 Ш 1000 1001 1010 1011 1100 1101 1110 11110001 1001 1110 1101 1011 0111оно 1111 00101100 0101 1010 0100 0011 1000С подробным обоснованием построения полей GF(2 m ) и исследованием их алгебраической структуры читатель может ознакомитьсяв [5].В заключение отметим, что при всей кажущейся сложности, использование полей Галуа в теории помехоустойчивого кодированияимеет глубокий математический смысл. Свойства полей Галуа позволяют при построении кодов использовать законы линейной алгебры, справедливые для полей действительных и комплексных чисел.Отличие заключается лишь в том, что арифметические операциинеобходимо производить но правилам, определенным для данногоконечного поля.ГЛАВА 3ЦИКЛИЧЕСКИЕКОДЫ3.1. ВведениеПрежде всего покажем, что применение на практике простейших линейных блоковых кодов с их последующим синдромным декодированием связано с чрезмерными техническими затратами.
Для этойцели рассмотрим два примера.Первым примером является протокол передачи данных по телефонному каналу ISDN-D, в котором используется формат передачиданных LAPD (Link Asset Procedure on D-channel). Все передаваемыеданные заносятся в отведенные им поля в потоке данных, согласностандарту (см. рис. 3.1). Длины полей заданы в байтах (один байтсодержит блок из 8 бит). Под проверочные символы отводится полеFCS (Frame Check Sequens) длиной 2 байта. С помощью проверочныхсумм производится обнаружение ошибок в поле адреса A (Adress),поле команд С (Control) и информационном поле I (Information). Таким образом, общая длина блока составляет (2+2-f 260+2) =266 байтили 2128 бит.
При использовании для защиты данных от ошибокпростейшего линейного кода с 16-ю проверочными битами потребовалась бы порождающая матрица размерности 2112x2128 и порождающая матрица размерности 16 х 2128.Байт121(2)шах 26021Р и с . 3.1. Формат передачи данных LAPD с флагомF=(01111110), полем адреса А, полем команд Си информационным полем I.В качестве второго примера рассмотрим формат передаваемыхданных, используемый в стандарте 802.3-CSMA/CD (Carrier SenseMultiple Access/ Collision Detection) для передачи данных в локальных сетях связи (Lokal Area Network, LAN) (рис 3.2).6—795Глава 3.
Циклические кодыПреамбулаРазделительАдрес получателяАдрес источникаДанныеБайт712(6)2(6)64... 1518Р и с . 3.2. Формат передачиданных802.3-CSMA/CD(Carrier Sense Multiple Access/ Collision Detection).В этом случае защита информации от помех методами, рассмотренными в предыдущей главе этой книги, также требует использования кодовых слов очень большой длины и, связанных с этим, чрезмерных технических затрат.Оба примера показывают, что на практике кодируются и декодируются информационные потоки относительно большой длины.
Применяемые при этом методы контроля ошибок должны быть максимально эффективными. В рассмотренных двух примерах этим требованиям отвечают двоичные циклические коды.Циклические коды используются в беспроводной телефонии встандарте DECT (Digital Enhanced Cordless Telephony), и в мобильной связи. В мобильной связи циклические коды применяются как встандарте GSM (Global System For Mobile Communication), так и встандарте CDMA (Code Division Multiple Access).Далее будет показано, что, при передаче в стандарте ATM(Asynchronins Transfer Mode), циклические коды, используемые вНЕС (Header Error Control), позволяют также обнаруживать ошибкисинхронизации.Замечание. Последующее изложение материала базируется на /7].Математические основы формулируются в виде тезисов и по мере необходимости доказываются.
Доказательства иллюстрируются короткими примерами. Практические применения циклическихкодов поясняются с помощью регистров с обратными связями, которые выполняют роль кодеров и декодеров. Такое изложение теории на примерах схемной реализации вначале может показатьсянемного непривычным.
С другой стороны, детальное усвоение процессов реализации кодирования и декодирования в дальнейшем может принести Вам большую пользу. Изучив последующие разделы,3.2. Определение и свойства двоичных циклических кодов 163;Вы будете подготовлены к самостоятельной программной реализации изученных алгоритмов.3.2. Определение и свойства двоичныхциклических кодовЦиклические коды являются подмножеством линейных кодов.
Ониобладают новыми специфическими свойствами, позволяющими упрощать процессы кодирования и декодирования. При этом, корректирующая способность циклических кодов в большинстве случаев довольно высока.Упростив изложение, мы ограничимся описанием только двоичных циклических кодов.
Заметим, что операции с компонентами двоичных кодов производятся по правилам арифметики по модулю 2.Замечание. Двоичные циклические коды образуют линейные векторные пространства над полем Галуа GF(2). На практике широко используются циклические коды с компонентами из расширенных полей Галуа GF(2m).
Такими кодами являются коды БоузаЧоудхури-Хоквингема (БЧХ) и коды Рида-Соломона (PC). Коды PC,в частности, используются в проигрывателях компакт дисков.Линейный (п, к)-код С является циклическим, если циклическийсдвиг любого кодового слова из С также принадлежит коду С.Рассмотрим кодовое словоv = (wo,«i,...,u n _i),(3.1)с компонентами v* е {0,1}. Циклический сдвиг соответствует сдвигу всех компонент на один разряд вправо, причем, освободившеесяместо слева занимает крайняя правая компонентаvW = (vn-i,vo,vu...,vn-2).(3.2)При г-кратном циклическом сдвиге получаемvW= (t7n_i,...,un_i,i;o,Vi,...,Vn-i-i).(3-3)Циклический сдвиг реализуется с помощью регистра сдвига длинып с обратной связью (рис. 3.3).Циклические коды можно описать, представив кодовые векторы в виде многочленов.
Такое представление позволяет обнаружитьГлава 3. Циклические кодынекоторые дополнительные полезные математические свойства циклических кодов. Использование этих свойств приводит к построениюпростых и эффективных процедур кодирования и декодирования.Регистр сдвига в начальном состоянииРегистр сдвига на такте 3Рис. 3.3. Регистр сдвига с обратной связью.Существует взаимно-однозначное соответствие между кодовымвектором v = («Oi vii • • • ivn-i) и степенью многочлена п — 1+ v1X1+ --- + vn^1Xn-1.(3.4)При необходамости можно переходить от векторного представлениякодового слова к представлению в виде многочлена и наоборот.Замечание. С математической точки зрения, представление кодовых слов в виде многочлена изоморфно линейному векторномупространству кодовых векторов.
При этом, операции с коэффициентами многочленов производятся по привычным правилам арифметики по модулю 2. Можно так же заметить, что степени переменной X используются только для обозначения места соответствующей компоненты кодового вектора в регистре сдвига и никакой иной смысловой нагрузки не несут.Представим циклический сдвиг кодового слова в виде многочлена=vn-i + « „ - г + i * 1 + • • • + Wn-iJf'"1 + voX*(3.5)Сравним (3.5) с результатом умножения v(x) на х'Внимательное рассмотрение (3.5) и (3.6) позволяет обнаружить связьмежду,(х)3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
