С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

, 2m - 1.Тогда лiобой синдром есть соответствующий столбецН , т. е . двоичное представление своего н омера==поз и­ция ошибки . Заметим, что единичнуiо подматрицу та­кой матрицы будут образовывать столбцы с номерами,ЯВЛЯIQЩИМИСЯ СТеПеНЬЮН апример , дляq == 31Нзх72: 1, 2, ... , 2m,-l.это матрицаооо11 1оо1 11 1 1 1оо1ооТогда порождающая матрица есть1•(III поток) Коды, исправляrощие ошибки3.4.1 1G7x4о11о11 1ооо1 1 11 о оо 1 оо о 1ооо139о•Она помещает сообщение последовательно в3, 5, 6и7-ю позиции кодового слова, а остальные биты явля­ются проверочными: подматрица образованная1, 2 и4-й строками является подматрицей Н , оставшейся по­сле удаления из неё единичной подматрицы .

Тогда, каклегко проверить,HGЛинейные коды•(п, k) :(3х 4)-матрица.резюмеЛинейные коды могут иметь произвольные пара­метры•~ О -нулеваяиnk < n.Требование линейн остипроизводить позволяетупростить кодирование и декодирование.1. Кодирование осуществляется особенно про­сто-умножением вектора сообщения на по­рождающую матрицу.Однако вопрос << как найти порождаrощуюматрицу для получения кода с хорошими ха­рактеристиками? >> остаётся открьrтым .2.Декодирование осуществляется с помощыолегко вычисляемых синдромов, а этап2присистематическом кодировании элементарен.140 IIIпоток : Глава3.Коды, исправляrощие ошибкиП ри этом процесс декодирования остаётся••т р удоемким .3.5Циклические кодыОпределение и построение циклических кодовОпред ел ениеКод3.6.Сназываетсяrцигх;личесrх;и.м(сдвиговъt.м), если он инвариантен относительно цик­лических сдвигов, т.е .

для любого О ~s~n- 1спра­ведливо(ао, . . . ,йп- l) Е С =?=? (as, as+l , .. . 'йп- l, ао,. .. 'йs- l) Е С.Ранее было показано :• В кольце R == п=-р[х]/(хп- 1), рассматриваемомкак n- ме р ное векто р ное прост р анство над полем!Fр, имеется базис-1 n- l'х,... 'х•Циклический сдв иг координат в этом базисе рав­носилен умножению на•х.В екторное подпрост р анствося циклическимiff I -кольцаIидеалRявляет­R.Поэтому построить циклический(n, k) -коддлиныбиномаxn- 1.можно следу1ощим образом .1. Выбираем любой делительМногочленg(x)образующим.g(x)называют порождающи.м или3.5.(III2.поток) Коды, исправляrощие ошибкиН айденный полином порождает идеал в кольцеR == !Fp[x]j(xn - 1),а коэффициенты многочленовиз идеала(g(x)) будут кодовымиm==degg(x) и k==n-m.3.141словами .

ТогдаПри удачном выборе порождающего полинома бу­дут получен код с приемлемым значениемd.Однако:•есть только несколько конструкций циклическихкодов с хоро1пими пара мет рам и ;•в общем случае определение кодового расстоянияциклического кода••и-чрезвычаино т р удоемкая за-дача .Циклический код-англ .CRC, Cyclic RedundancyCode. Из всех линейных (п, k)-кодов будем далее рас­смат рив ать циклические .Полиномиальноепредставлениеслов.Устано­вим соответствие векторов сообщения и Е {0, 1}k и ко­дового словаvЕ{0, 1}n с их полиномиальными пред­ставлениямиu(x), v(x)ЕIF2[x] :и == [uo ' и 1 ' . . . ' и k - 1 ] т +-+1+-+ и(х) == uo + и 1 х + ...

+ uk_1xkV == [Vo, V1 , · · · , Vn- 1]Т +-1n-1+-1- V( Х ) == Vo + V1 Х + . . . + Vn-1 ХЛюбое кодовое словоv(x)Еv(x)представляется в виде(g(x)) == { g(x)q(x) q(x)ЕIF2[x], xn == 1}142 III поток : Глава 3. Коды, исправляrощие ошибкиКоды Хэмминга могут быть циклическими. П остроен­ная Примере3.2таблица4хдля кода Хэмминга не7порождает циклического кода .Однако если переставить 3-элементные окончаниядвух последних строк , то полученная таблица1оооооо1 1 о1 о о о 1 1о 1 о 1 1 1о о 1 1 о 1уже порождает циклический код (проверьте ! ).При мер 3. 7 (построения циклического кода) .

Построимциклический код длиныn ~ 23.Для определения порождающего полинома кода на­ходим разложение бинома х23-1 на неприводимыемно г очле ны.Один корень находится сразу : это1и имеем р азло­жение( х + 1) (х22+ х212+ . . . + х + х + 1) .f( x)Перебором неприводимых над [Г 2 полиномов находим119765f( x ) ~ (х +х +х +х + х +х+ 1 )хЛ(х)х (xll + x lo + х6 + xs + х4 + х2 + 1)!2(х)3.5.(IIIпоток) Коды, исправляrощие ошибки143fПоскольку deg 1 (х) == deg f 2 (x) == 11 == т, любойиз полиномов f 1 (x), f 2 (x) может быть выбран порож­дающим4 для построения (23, 12)-кода.Можно показать, что в обоих случаях кодовое р ас­стояние оказывается р авны мпорождающим полинома7.g(x)Н апри мер, при выборе== !2(х) и несистемати­ческом кодировании сообщения[ 100000000000] т по­лучаем кодовое слово [10101110001100000000000]т ве­са7.Я сно, что построен код Голея.Заметим, что делители бинома х 23-1 пришлосьискать перебором.Кодированиециклическимиопределён порождаi-ощий полиномdeg g (х) == т< n , зада1-ощийкодами.g(x): g(x)Пустьxn- 1код С.Н есистематическое кодирование'осуществляется••путем ум ноже ния кодируемо г о по линома н а порожда-ющий:u(x)нv(x)==g(x)u(x) .Систематическое кодирование осуществляется пу­тём приписыванием к кодовому слову слева (в младшиеразряды) остатка r(x) от деления xmu(x) на g(x) .Посколькуxmu(x)==g(x)q(x) + r(x)иdeg r(x) <т,При выборе g (х) = х + 1 получим код с проверкой на чётность (m = 1) ,при g(x ) = (х + 1)(f1 (x)) или g(x ) = (х + 1)(f2 (x)) получим pacшup en'H/ЫUкод Голея с m = 12.4144 IIIтопоток: Главаxmu(x)3.+ r(x) ==Коды, исправляrощие ошибкиg(x)q (x)Е С и систематическоекодирование может быть задано какнu(x)v(x ) == xmu(x) + r(x),при котором полиномтов полиномаu(x)вv(x)kсодержиткоэффициен­kкрайних правых позициях (пристарших степенях х).Пример3.8.

1.П острои мцикли ческийкоддлины== 7.nСначала нужно найти какой-либо делитель биномах71, для чего необходимо разложить его на веприво­-дим ые множ ит ели.Заметим , что 723ния бинома х -1== 23 -1 . Но F ==IF~- поле разложе­1 и поэтому его корнями являютсявсе венулевые элементы поля F .Делаем вывод: выбор длины кода n == 2q - 1 очень-удобен, т. к . легко определяются число и степени непри­водимых делителей биномаПусть а -xn - 1 == x 2q-l -1.произвольвый при митивный элемент по­7ля F == IF~ .

Тогда с учетом а == 1 находим разбиение7корней х - 1 ( == всех элементов F*) на орбиты:2{ 1} , { а, а , а4} , {Таким образом , многочлен х3а , а , а765} .+ 1 имеет один непри­водимый делитель 1-й степени и два неприв одим ых де­лителя3- й степени (их всего два) .В р езультате получаем разложениех7-1== х + 1 == (х + 1) (х + х + 1) (х + х + 1).7332(III поток) Коды, исправляrощие ошибки145В качестве порождаiощего полинома g ( х)можно3.5.выбр ать любой из вышеуказанных полиномов 3-й степе­ни . Тогда ти будет построен циклический== 3, k == 4(7, 4)-код5 .

Выберем конкретно g(x) == х 3 + х + 1.Закодируем несистематическим и систематиче­2.ским кодам сообщение и == [О О 1 1]ти( х) == х 3 + х 2 .+-+Несистемати ческое кодирование.323v(x) == u(x )g(x) == (х + х ) (х + х + 1) ==4265== х +х +х +х +-+ [0010111 )т== v.Систематическое кодирование .от деления многочленаr(x)3х (х3+х2) == х6+х5== (хx 3u(x)3Н аходимнаостатокg(x) :23+ х + х) (х + х + 1) + х,поэтому6v(x) == x u(x)+r(x) == х +х +х +-+ [О 1 О ,О О 11] т == v .35= VДекодирование циклических кодовОпределение3.7.Синдромом полипомаw(x) , принято­го при передаче сообщения, закодированного цикличе­ским кодом и, возможно, содержащего ошибки, назо­вём остаток s(x) от делениякод многочлен g(x).w(x)на порождающийОпределение синдрома для циклического кода , оче­видно ,естьперефр азировка в тер минах полиномовuопределения синдрома для линеи ных кодов.Свойства синдрома-полинома w ( х):5Ясно, это код Хэмминга!146 IIIпоток : ГлаваКоды, исправляrощие ошибки3.• О ~ degs(x) < m==n - k;О 9• s(x)• s(x)-g(x)w(x)w(x)-кодовое слово;-g(x)+ е(х))(v(x)-g(x) е(х) .Декодирование циклического кода проходит по об­щей схеме декодирования линейного кода:1) вычисляется синдром s (х) принятого слова w ( х);2)s(x) + g(x)u(x)для всех 2k возможных сообщений u(x) .ВЫЧИСЛЯI-QТСЯ ПОЛИНОМЫ е(х) ==3) определяется полином ошибок еа(х) как решениес минимальн ы м чи слом мо но мов.4) восстанавливается переданное сообщениеu(x)==w(x)+ еа(х ).Пр имеры декодирования циклических кодов будутданы при рассмотрении БЧХ-кодов 6 .Циклические линейные коды•резюмеЛин ейный код будет циклически м, только если онпринадлежит идеалунов•(n, k) :(g( х))в кольце многочле­IF2[x]j(xn- 1).Порождающийполиномg(x)циклического(n, k)-кода является делителем бинома xn - 1;degg(x) ==т - число проверочных бит кода.6Существуют и альтернативные методы декодирования циклических ко­дов общего вида (декодеры Меггита, Касами-Рудольфа, пороговый, мажо­ритарный,...

)также экспоненциальной поkтрудоёмкости.(III поток) Коды, исправляrощие ошибки3.6.147Можно выбрать ЛI{)бой делитель , однако нахожде­ние g(x) , порождающего код с большим кодовымрасстоянием d - сложная задача (оценка сверху:d не превосходит числа мономов в g(x)).•Циклические коды общего вида могут иметь про­извольную длинуn,но , в отличие от линейногокода общего вида, его параметры т=следовательно,•k = n-deg g(x) и ,т уже не произвольны .Кодирование и декодирование сводится к выпол­нени}О операций ум ножения и деления полиномов ,легко реализуемые н а регистрах сдвига с обрат­ными связями.Однако алгоритмы декодирования по-прежнемуимеют экспоненциальную сложность по3.6k.Коды Боуза- Чоудхури-ХоквингемаОпределение и основны е свойства БЧХ-кодовКоды Боуза-Чоудхури-Хоквингема (БЧХ , ВС Н) - под­класс циклических кодов, и справ ляiощих не менее зара­нее заданного числа ошибок.

Характеристики

Список файлов лекций