С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 16
Текст из файла (страница 16)
7.(IIIпоток) Коды, исправляrощие ошибки394. По найденным корням а , а , а1512,15169вычисляем позиции ошибок :J2-3-9jз- 15J16,-1515 О.5. Т. о. полином ошибок е(х)х 12=+ х 6 + 1 опреде-••лен правильно иv(x)=w(x)+ е(х)=v(x)и кодовое слово восстановлено .6. Проверка v(a)= v(a2)= ... = v(a 6 )говорит от том, что восстановление верное12О.БЧХ-коды: исторические сведения. Первым практически реализованным БЧХ-кодом былисправля1-ощий5(127, 92, 11)-код,ошибок.В системах передачи данных широко используетсядвоичный БЧХ (255, 231, 7)- код ( 255 = 28 -1) со свойствами :• степень порождающего код многочлена g(x)т= 24;••в общем количестве слов длинывых - 2- 24 ~ 17. 10- 6 ·все шары радиуса'255доля кодо3 с центрами в кодовых255ЗаНИМаiОТ ~ 16, 5% объёма куба В .словахВ течении м ногих лет не было случая, чтобы ошибкапередачи прошла незамеченной.12с учётом замечания на с.
134.170 IIIпоток: ГлаваБЧХ (п,k, d) -коды:3.Коды, исправляrощие ошибкирезюме•БЧХ-коды являются подклассом циклических.•Самое ценное свойствониякодаскодовым-возможность построерасстояниемнеменьше заданного .•Кодирование осуществляется с помощью пораждаю щегополинома ,имеющегокорнямистепенивекоторого примитивного элемента поля.•Декодирование может быть проведено с помощьюэффективных алгоритмов (Фор ни, БерлекэмпаМэсси, П итерсона- Горенстейна- Цирлера, Евклидов алгоритм,•...) .Теоретически коды Б ЧХ могут исправлять произвольвое количество ошибок, но при этом существенно увеличивается длина кодовогословачтопередачиприводитданныхикуменьшениrоусложнениrо..скорости...прие мн о-передаrощеип,ап-паратуры, и поэтому при больших длинах приходится использовать другие коды .•При небольшихnсреди кодов БЧХ существуютхорошие (но, как правило, не лучшие из известных) коды.Коды Рида-Соломона: общие сведения.Широко используемым частным случаем кодов Б ЧХ являются rх;оды Рида- Соло.могна(Reed- Solomon codes),позволяют исправлять пакеты ошибок.которые3.
7.(IIIпоток) Коды, исправляrощие ошибкиПarк;em ошибоrк;171группа битов, в ко(error burst) -торой два последовательных ошибочных бита всегдар азделены правильными битами , число которых менееустановленного .Коды Рида-Соломона :• небинарвые (в частности , очень распространеныкоды, работающие с байтами);•часто используются в устройствах цифровой записи звука, в том числе на компакт - диски .Пример 3.14 (негруппового блокового кода). Пусть подвоичному симметричному каналу с шумом требуетсяпередаватьдлиныt== 4битовых сообщения5 1 , 5 2 , 53 , 5 42.Б локовый разделимый негрупповой код С, исправляiощий1ошибку задаётся таблицей5с00011011001100110 11001111000<< Зазор >> : 25-4 · (1 + 5)== 8слов ;граница Плоткина достигается(проверьте)Кодовое расстояние построенного кода С равнои построен систематический(5, 2, 3)-код,3содержащийи сходное сообщение в первых двух пози циях.Помехоустойчивое кодирование применяется:•для получения надежной связи, когда мощностьп ринимаемого сигнала близка к мощности тепловых шумов;172 III поток: Глава 3.
Коды, исправляrощие ошибки•длязащиты протившума,намеренноорганизованного противником в военных приложениях;•припередачеданныхввычислительныхсистемах·•'для защиты данных во внутренних и внешних ЗУ(ленты, диски ...);•присинтезеотказоустойчивыхустройств (например , БИС , ПЛМ,•дискретных...);для получения устойчивых признаков из биометрических характеристик (сетчатка глаза, отпечатки пальцев ,...) .Для выбора минимальных многочленов при построении БЧХ-кодов составлены специальные таблицы.Коррекции ошибок может требоваться не всегда :многие современные каналы связи обладают хорошими характеристиками , и принимаr-ощей стороне частодостаточно лишь проверить , успешно ли прошла передача и в случае наличия ошибок повторить её.Также при синтезе сбоеустойчивых ИМ С часто требуется лишь зафиксировать наличие ошибки , котораяисчезает при повторном вычислении выходного вектора .В этих случаях применяr-отся коды специально предназначенные для обнаружения ошибок, а не для их исправления .Вся математика делится на три раздела: небеснаямеханика , гидродинамика и теория кодирования.В.
И. Ар'Нолъд3.8.поток) Коды, исправляrощие ошибки(III3.8Задачи с решениямиЗ адача3. 1.173Для линейного гк;ода 7 заданного своей проверочной .матрицей1 1 1о 1 о 1 1 1 о1 о 1 1 1 о оо}{о1отребуется1)построитъ порождающую .матрицугк;ода дляGсисте.матигчесrк;ого rк;одирования, при rк;оторо.м биты исходного сообщения переходят в последниебиты rк;одового слова 7•'Найти таrк;ое rк;одирование для сообщений2)и1= [1 1 О 1] т, и 2 = [1 О О 1]т.Р е ш е ни е . П роверочная матрица3тх1lимеет размерностьследовательно код при длине7,=3проверочных иk = 7- 3= 4n=7содержитинформационныхбит.П орождающая матрица кодаобеспечивающаяG,требуемое систематическое кодирование , должна иметьрВИД/.4Матрицу Р можно получить, если привести проверочную матрицу 1l к виду [Iз P J , преобразуя строки:оо1о1о1оо1 1 11 1 11 1 1 ооо(1)+--+(3)1о1 1 1о1ооооо1 1 1о1о1 1 1174 IIIпоток : Глава3.Коды, исправляrощие ошибкио1 о 1 11 о 1 1 1 оо 1 о 1 1 11(1) + (3) f---+(1)оооТеперь можно построить требуемую порождающу1оматрицу и осуществить кодирование для u 1 = [1101] т,U 2 = [1 001] т :G=1 о 1 11 1 1 оо 1 1 11 о о о'о 1 о оо о 1 оо о о 1ооо[v1 , v2]Gх[и1 , и2]1о 11 11 оо•о1 1Очевидно был задан(7, 4, 3)-код Хэмминга, помещаiощий информационные биты в последние 4, а проверочные - в первые 3 поз иции кода.Задача3.
2.Ципли"-lеспиu(9, 3) - под за дансв оим поро;)!сдающим полиномом63g(x)=x +x +1.Тр ебуется определитъ ег о подо вое ра ссто.яниеd,а тапже осуществитъ системати"-lеспое подированиеполиномаРешение .••Для определения кодового расстояния най-дем все кодовые слова :3.8.(IIIv(x)==ах8поток) Коды, исправляrощие ошибки26g(х)(ах +Ьх+с) == (х +х + 1 )(ах +Ьх+с) ==642+ Ьх + сх + ах + Ьх + сх + ах + Ьх + с,75317532а, Ь, с ЕIF2 .В векторном виде все кодовые слова представля1отсякак[ с, Ь, а, с, Ь, а, с, Ь, а ] .Очевидно, что минимальный хэммингов вес иенулевогокодового слова равен3и , следовательно,d==3.Проводим систематическое кодирование сообщенияu(x):u(x) ~ v(x)66==х и(х) == х (х26x u(x)+ х)==+ r(x),х8Находим остаток degr(x ) от делениях7х+ xs7+хх +х45Т.о .v(x).x 6 u(x) на g(x ):+ х245+х7+х2+хr(x) ==х +х +х +х и874+х5242== х +х +х +х +х +х н [О 1 1 О 1 1 ,0 11]т .Замечание.
Очевидно задан тривиальный код утроения :кодовое слово есть трижды повторенное сообщение. Поэтому кодирование будет только систематическим и видv (х)сразу определён в(*).176 IIIЗадачапоток: Глава3.Коды, исправляrощие ошибкиРа ссмотрим rкод Хэ.м.минга систе.матиче3.3.сrкого rкодировани.я с порождающи.м при.митивнъt.м полиномом а( х) == х3+ х + 1.Требуется деrкодироватъ полипо.мъt1.
w1 ( х) == х + х + х,26532. w2 ( х) == х + х + х + х + х,2633. wз (х) == х + х + х + х.6Решен и е.2Очевидно, имеем(7, 4, 3) -код Хэмминга, вкотором сообщение есть коэффициенты перед степенями3, ... , 6формальной п еременной х кодового полинома .Для декодирования необходимо вычислить синдромs == w(a) сучётом а 3 ==а+ 1 ,где а - генераторполяIF2[x]j(a(x)) .Если s == О , то считаем, что ошибок при передаче не произошло; иначе необходимо найти такоеk, что== s и перед восстановлением сообщения инвертировать k-й разряд w(a) (что, очевидно, имеет смысл приk Е {3, .
.. , 6} ).ak1. w1 ( х) == х62+ х + х +-+[О 1 1 ,О О О 1]6s == w(a) == а +о?+а == (а ) + а +а ==23 22222== (а+1) +а +а == а +1+а +а == а+1 #О .3Очевидно , а + 1 == а , т. е. k == 3, ошибка произошла263в 3-м разряде и v(x) == w(x) + е(х) == х + х + х +х+-+ [О 111 О О 1], u(x) +-+ [1 О О 1].62. w 2 ( х) == х + х + х + х + х +-+ [О 1 1 ,1 О 1 1]6532532s == w(a) == а +а +а +а +а ==3.8.(IIIпоток) Коды, исправляrощие ошибки==(а+ 1) +(а+ 1 )а +а+ 1 + а +а2222222а + 1 +аз+а +а + 1 == аз+ а == а +а+ 12Очевидно, аз+а == (а+ 1 )а23. wз ( х)== х2#-О.== а 5 , т. е .произошла в 5-м разряде и снова6177k == 5, ошибкаu(x) +-+ [1 О О 1].2+ хз + х + х +-+[О 1 1 ,1 О О 1] .Убеждаемся, что в этом случаеs == О ,произошло и u(x) == v(x) +-+ [1 О О 1] .т.
е . ошибок неЗамечание. Декодирование систематического кода Хэмминга можно провести делениемп ринятогополиномана порождающий: остаток от деления есть синдромw(x)q(x) · g(x)==+ r(x),r(x)==s:s.В нашем случае:621. х + х + х== (хз+ х + 1) + ~ + ~;2V'=s6522. х + х + хз + х + х ==22== ( хз + х + х + 1) (хз + х + 1) + ~ + х + ~;V'=s623. х + хз + х + х== (хз+ х)(хз + х + 1) + ~·=sЗа да ч а3.4.Пустъ а -F == IF 2 [х]/ (х4+ х + 1).примитивныu элемент поляДля пода В ЧХ с нулями а,а 2 , аз и а 4 и принятого словаw(x)== х14+ xlO +х5+х4 .наuти полином лопаторав ошибоп а-(х).178 IIIпоток : Глава3.Коды, исправляrощие ошибкиРе ш е ни е.
Для удобства вычислений продублируем таблицу соответствий между степенным и полиномиальным п р едставлением элементов данного поля, уже ранее использованную нами (см. с.(0010)а2(0100)аз(1000)(0011 )а+ 12(0110)а +ааз+ а2(1100)аз+ а+ 1(1011)2(0101 )а + 1аз+а(1001)2(0111 )а +а+ 12аз+ а +а(1110)2аз+ а +а+ 1 (1111)аз+ а 2 + 1(1101)аз+ 1(1001)1(0001 )ааа2аза4а5а72).6а7а8agа1оallа12а1за14al5С помощыо этой таблицы вычислим синдромы :s1 ~ w(a) ~ а1405+о? +о: +а24~~ (аз + 1) + (а + а + 1) + (о: + о:) + (о: + 1)~ аз+а+12~ о: 7'221s2 ~ w(a ) ~ (w(a)) ~ о: \sз ~ w(аз) ~ а12+ 1+ 1+ а12s4 ~ w(a4) ~ (w(a2) ) 2 ~ о:28Си ндромны й полином-~ о'3.8.(IIIпоток) Коды, исправляrощие ошибки3s(x) == о? х4+а142х +а? х179+ 1.Синдромов всего четыре, следовательно число возникших ошибокvне более2.Полином локаторов ошибок (]" (х) удовлетворяет соотношениr-о В езуx2r+1a(x)+ s(x)(J"(x) ==А(х),deg А(х) ~ r.Реш аем с данное соотношение помощью расширенного алгоритма Евклида:Шаг О .115r-2(x) == х ,r_ 1 (х)==(]"_ 2(х)Инициализация13 414 27а х + а х + а х + 1,О,(J"_l(x) == 1.Шаг 1.r -2(х) == r - l(x)qo(x)11 Делим r -2(х )+ ro(x),на r - l(x) с остатком2qo (х) == а х ,239 2ro(x) == ах + а х + а х ,(J"o(x) == (]"_2(х)- (J"_l(x)qo(x)2== -qo(x) == а х .Шаг 2.r - l ( х) == ro (х) ql (х) + r1 ( х ),11 Делим r_l(x) на ro(x) с остатком125q1(x) == а х + а ,r 1 ( х)(J"l (х)== а х + 1, deg r1 ( х) == 2 ~ r ,== (J"_l (х) - (J"o(x )ql (х) ==2125== 1 + а х( а х + а ) ==14 27а х +а х+ 1== (J"(x).142полином локаторов ошибокпоток: Глава180 IIIЗадача3.5.Коды, исправляrощие ошибки3.Рассмотрим по д В ЧХ, '1-lули поторого определ.я'tотс.я стеnе'li.ями а , где аме'liт пол.я lr 2[х] / (х4примитив'liъtu эле-+ х + 1).Пустъ дл.я '1-lепоторого при'li.ятого словаw(x)поли'liом лопаторав ошибоп естъ2а( х) ~ а х2+а6х+ 1.Требуется определитъ позиции ошибок вw (x) .Решение.
Найдём корни (их 2, полином квадратный)полинома локаторов ошибок полны м перебором.Для вычислений удобно пользоваться таблицей соответствий между степенным и полиномиальным представлением элементов поля, вычисленной в предыдущей задаче.4а(а) ~ а +а +1 ~аз,2а(а )а3а(а )76+а +18983~ а ,а + а + 1 ~ аз+ а +а,4а(а )а+а +11211а + а + 15а(а )6а(а )7а(а )8а(а )102а1410+а12+1а16+а13а18+а +1+1141,О,2а +а+1,32а +а + 1 ,О.Дальше можно не вычислять: оба корня а (х) найдены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
