С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 14
Текст из файла (страница 14)
Предложены Р.Ч. Боузоми Д.К. Рей-Чоудхури в1960г. нез ависимо от опубликованной на год ранее работы А. Хоквингема.Теоретически коды БЧХ могут исправлять произвольное количество ошибок, но при этом существенноу величивается длина кодового слова с уменьшением егоскоростиR.148 IIIпоток: Глава3.Коды, исправляrощие ошибкиРадж Чандра Боуз(Raj Chandra Bose, 1901- 1987) индийский математик , р аботавший в США.Двайджендра Камар Рей- Чоудхури(Dwij endra Kumar Ray-Chaudhuri , 1933) индийский математик, работающий в США.Обладатель медали Эйлера за вкладв раз витие комбин аторики.Алексис Хоквингем7(Alexis Hocquenghem, 1908?-1990) французский математик.В его работе1959г. содержится первоеописание линейных циклических кодов,и справля1ощих кратные ошибки .Основные свойства минимальных многочленов(напоминание).1.
V (3 Е [F~ :3! т!З (х) , м . м . т!З (х) неприводим иdeg т!З (х) ~ n ;2. Если f( x) Е lrp[x] и f( f3 ) ==О , то т!З (х)3.f(x).Миним альн ый многочлен примитивного элементаполя называется при.митивгны.м .мгногочлегно.м .7Hocquenghem является галицинизированиой , формой германской илифламандской фамилии , правильное её чтение- 0-к;епге.м.3.6.(III поток) Коды, исправляrощие ошибки149Циклотомический класс элемента поля./3 -ним, что еслиf(x)Е!Fp[x]Н апомкорень неприводимого многочленастепени п, тор/3 ' /З 'f3P2' ...'fЗРп - l-все n различных (сопряжённых) корнейf( x).Определение 3.8 (для пол е й ха рактер и стики 2). Пустьn N .
Цигк;лото.мичесгк;и.м гк;лассо.м (или гк;лассо.м сопр.яжённости) элемента а Е !Ff над подполем IF2, называется множество всех различных элементов !F являп2ntО 1ющихся 2 -м и степенями а : а, t = , , .. . .f,Свойства циклатомических классов.1. Циклотомические классы р азличных элементовлибо совпадаi{)Т, либо не пересекаi{)ТСЯ ==? циклаfтомические классы всех элементов поля !Fобразуi{)Т разбиение его мультипликативной группы .2. Если а - примитивный элемент поля !F~n , то дикIF2лотомический класс а над подполемжит ровноqсодерэлементов, т. е .
это класс•3. Если а - примитивный элемент поля !F~n и диклотомический класс ak над подполем IF2 содержиттэлеме нтов , то полиномm-1mfЗ (x) = Пх- (ak)2tt=O=Хm- 1+ Лт- 2Х\m-2+ ... + л1 Х +\\ЛQ150 IIIпоток: Главаявляетсям.м.3.Коды, исправляrощие ошибкидлявсехэлементов,входящихвданный диклотомический класс.При мер3.9 .Принедём примеры разложения мультипликативных групп полейIF~nна циклотомическиеклассы над IF~ .q = 3 и а - примитинный элемент поля7IF~ = F. Тогда а = 1 и разложение F * над IF21. n= 1,есть (каждый элемент циклотомического классапоследовательно умножаем на 2n = 2) -465{ 1 } , { а, а , а } , { аз, а , а } .22. n = 2, q = 2 и а- при митивный элемент поля15IFi = F .
Тогда а = 1 и разложение F* над IF§есть (каждый элемент циклотомического классапоследовательно умножаем на 2n = 4) -{ 1 } , { а, а4}, {2а , а8}, {аз, а12}, {а5},{ о? о } , { а б, ag } , { а 7, а1з } , { o?l, al4 } .3. n = 1, q = 4 и а - примитинный элемент поля15IFi = F. Тогда а = 1 и разложение F * над IF2есть (умножение на 2n = 2) 248612{ 1} {а а а а } {аз а а а''''''''249= а }'БЧХ-коды: определение (простейший случай) иuосновное своиствоПусть выбраны параметркодаq,определяющий длинуn = 2q- 1 и no?-lcmpynmuв?-loe расстояние dc < n.(III поток) Коды, исправляrощие ошибки3.
7.151Код БЧХ есть циклическийлящийxn -1порождаiощий(n, k)-код, в котором демногочлен g(x) являетсяполиномом минимальной степени , име}ощим корнямипули пода а, а 2 , а 3 , ... , adc- l, где а - примитивныйэлемент поля IF~ , т== deg g(x) и k == n- т .Кодовое расстояниеdпостроенного ВЧХ-кода оказывается не менее выбранного конструктивного расстоянияКодыdc.БЧХ:синдромы.Поскольку все кодовыеслова циклического кода С делятся на полиномкорнями а, а 2 ,...
, ad-l,g(x)сто эти корни- одновременнои корни любого кодового слова:v ( х) Е С 9Определениеv (а~ ) == О ,i == 1, ... , d - 1.3.9. Сипдро.ма.ми поли'Но.ма w(x), принятого при передаче сообщения , закодированного БЧХ.кодом с нулями а\i == 1, ... , d - 1и, возможно, содер-жащего ошибки , назовём значенияsi==w(x)в нулях кода:w(ai).Я сно , что•определение синдрома для БЧХ-кода, очевидно ,есть перефразировка в терминах нулей кода полиномов синдрома для циклического кода;•посколькуw (х) == v (х)+ е( х),тоsi.== w(a~ ) == е(а~ );• << все синдромы равны нулю >> 9слово..w(x)- кодовое152 III3.7поток : Глава3.Коды, исправляrощие ошибкиПостроение БЧХ-кодовАлгоритмпостроенияБЧХ-кода.Б ЧХ(n , k)-код , как и любой циклический , задаётся порождающим полиномомk=9(х)делителем бинома-xn - 1,n- deg9(x).Для его нахождения нужно:1) задать величину q, определяющуiо длину кодаn = 2q- 1;2) задать величину конструктивного расстоянияdc = 2r + 1 < n, если предполагается исправлятьдо r ошибок;3) определить полеrrg =водимый полиномlF2 [x]j(a(x)), выбрав неприа(х) Е lF 2 [x] степени q и примитивный элемент поля а;4) определить циклотомические классы элементаrrgа Енад полем [F 2 , в которые попадатот нули кода а, а 2 , ..
. , adc-\ пусть таких классов h;5) найти h минимальных многочленов 91 (х), 92 (х),.. ., 9h (х) для каждого циклотомического класса;6) вычислить порождаJощий полином9 (х)Пример3.1 0=91 (х) . 92 (х) . ... . 9h (х).(построения кодов Б"LIX). Выберем q =3и построим различные Б ЧХ-коды длины n = 23 -1 = 7.Для получения разложения бинома х - 1 рассмотрим поле F = lF2[x]j(a(x)) rv [F~, deg а(х) = q = 3.73. 7.(IIIТогдапоток) Коды, исправляrощие ошибки153как показано ранее, разбивается на следуюF *,щие диклотомические классы над2{ 1 } , { а, а , а4} , {lr2 :6аз, а , а5} .Конкретно в качестве порождающего многочленавозьмём примитивный многочлен а(х) === хзкоторыйявляетсям.м .дляпримитивного2+х+1,элемента4а === х и всего класса {а, а , а }.Для построения кодов , исправляющих разное количество ошибок, необходимо определить соответству1оvvщии порождающии полином.1. КодВЧХ длиныn===7,исправляющий r1ошибку (код Хэмминга).В этом случае dc - 1 === 2r === 2 и нули кода а, а2попадают в один диклотомический класс .Минимальный многочлен для обоих элементов этого классаg(x)а(х), поэтому порождат-ощий полином=== а(х), т ===чаем уже2.-degg(x) === 3 и в результате полуизвестный (7, 4, 3)-код Хэмминга.Код ВЧХ длиныn===2r===7,исправляющий не менееr === 2 ошибок.Теперь2dc - 1===4.Н ули строящегося ко4да а, а , аз, а входят в два циклатомических класса:{ а, а 2 , а4 } и { аз, а 6 , а 5 } , порождаемых а и азсоответственно, поэтомуg (Х)===gа (Х) · gаз ( Х) ,где 9а(х) и gаз(х) - м.м.
для а и аз .М.м. для а известен :ga(x)=== а(х)хз+ х + 1.154 IIIпоток: Глава3.Коды, исправляrощие ошибкиНайдем м . м . для аз ==а+ 1:56gаз(х) == (х-аз ) (х- а ) (х- а )== хз+ (аз+аs+а6 ) х2+ (a8 +ag+all) x+a14.Вычислим коэффициенты полинома gаз (х)с••у ч е-том а 7 == 1 и аз ==а+ 1:562аз+ а + а == (а+ 1) + а (а + 1) +(а+ 1)22== а + 1 + аз + а + а + 1 == 1 ,89а + а + а112422== а + а + а == а + а + а( а + 1) == О ,14а== 1.2Т.
о.gаз(х) == хз+х + 1 (что можно было определитьср азу: это второй из двух неприводимых многочленовстепени3)и2g (Х) == gа (Х) · gаз (Х) == (ХЗ + Х + 1) (ХЗ + х + 1) ==6== х + х + х + хз + х + х + 1.Получаем542deg g(x) == 6 и k == 1, т. е. построен тривиальный код с 7-кр атным повторением , и спр авляющий3ошибки и содержащий всего дв а кодовых слова :[0 0 0 0 0 0 О]т и [1 1 1 1 1 1 1]Т.Код получился очень плохой : хотя он и испр авляет больше ошибок , чем планировалось , его скоростьR == 1/ 7чрезвычайно мала.Попытаемся построить лучший код для испр авления2 ошибок ,взяв большую его длину.3.
7.(IIIпоток) Коды, исправляrощие ошибкиПрим ерn==3.11. Выбер ем q2q - 1 == 15.==4,155т. е . длина кода будет15Для получения разложения бинома х - 1 рассмотрим поле F == IF2[x]j(a(x)) rv IF~, dega(x) == q == 4.ТогдаF*разбивается на следуiощие циклотомическиеклассы надIF 2:{1}'Конкретно в качестве порождающего многочлена......возьмем примитивныи многочлена(х) == x +x+l,4которыйаявляетсям.м.дляпримитивного2х и всего класса { а, а , а , а==1.Код ВЧХ длины4n == 15,8элемента} .исправляrощий r ==2ошибки.В этом случае dc - 1конст р уи р уем о го== 2r == 42и нули а, а , аз, акода располагаютсяв двух циклатомических классах - для элементов а и аз .М . м . для (всех) элементов этих классов:первого (а) : 9а (х)==второго (аз) : gаз (х)6а(х).==912(х- аз)(х - а )(х - а )(х - а )• • •. . .
== х4 +х з +х 2 +х+ 1.Тогда порождающий полином кода естьg (Х) == gа (Х) · gаз ( Х) == х8+ Х + Х + х + 1.7464поток: Глава156 IIIП олучено т ==3.Коды, исправляrощие ошибки8, k == 7и, как можно показать ,5, т. е . построен БЧХ (15, 7,стью уже R == 7/ 15 > 1/7.d==dc==5)-код со скороП остроим теперь2.
КодБЧХ длиныn==15,исправляrощий r ==3ошибки.Теперь нужно найти полином, являющийся м . м. длянулей а, а 2 , ... , а 6 , которые попадаJот в 3 циклатомических класса :(имеются ещё1- и 4-х элементный классы).Пусть поле разложения бинома х 15 - 1 то же, тогдам.м. для а и а 3 уже найдены.2Очевидно ga5 (х) == х + х + 1 и по рождающий полином п олученного кода естьg(x)==ga(x) · gаз (х) · ga5(x)10х + х + х + х + х + х + 1.10, k == 5 и можно показать , что==Получено т ==d85427.Этот (15, 5, 7)-код БЧХ при той же длине, что==dc==и предыдущий , исправляет больше ошибок , но имеетменьшую скоростьR==1/3.(III поток) Коды, исправляrощие ошибки3. 7.157Зависимости скорости ВЧХ-кодов от кодового расстояния<< Ступеньки >> на графиках соответствуют ситуации ,когда реальное кодовое расстояние оказалось больше ,чем выбранное конструктивное.Декодирование кодов Б ЧХДекодирование кода Хэмминга как линейного кода с поv••мо щ ыо п роверочном матрицы и вычисляемого с ее п о-мощыо вектора-синдрома было уже рассмотрено в Разделе3.4.О пишем ещё один метод декодирования кодовХэмминга как простейших кодов БЧХ .В этом случаеd == 3, и поэтому нулями кода являются а и а 2 , где а - примитивный элемент поля IF2,n == 2q- 1.Для декодирования принятого слова w ( х) вычисляем синдромs 1 ==w(a)==s(синдромs2 ==w(a 2) намне потребуется) .•П риs== О считаем, что ошибок не произошло.158 IIIпоток: ГлаваЕсли•3.Коды, исправляrощие ошибкиs .
=!= О , то определяем значение j , для кото-рога а) ==s и считаем, что произошла единичнаяошибка в j-м р аз ряде дляПримерриваемре3.81, ... , n - 1.для цикл ических кодов .был== хзвание== О ,3.12 (декодирование кода Хэмминга). Рассмат(7, 4)-код Хэмминга, построенный в ПримеТамg(x)jвыбранпорождающийполином+х+1v(x)и найдено систематическое кодиросообщения u(x) == хз + х 2 н [О О 1 1] т :65v(x) ==х +х +х н [О 1 О ,О О 11] т .Пусть при передаче сообщенияu(x)произошлаошибка в 5-й позици и , т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
