AA3-2(ECC) (1127140), страница 6
Текст из файла (страница 6)
Систематическое кодирование. Находим остаток r(x) отделения многочлена x3 u(x) на g(x):x3 (x3 + x2 ) = x6 + x5 = (x3 + x2 + x)(x3 + x2 + 1) + x,поэтому v(x) = u(x) + r(x) = x6 + x5 + xили в векторном представлении v = [0100011] (n = 7).Мы видим, что биты входного сообщения u воспроизводятся вкрайних правых битах кодового слова v.(Декодировать v с одной ошибкой будем при рассмотренииБЧХ-кодов.)ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование65 / 132Циклические коды: декодированиеОпределениеСиндромом принятого полинома w(x), закодированногоциклическим (n, k)-кодом с порождающим полиномом g(x) и,возможно, содержащим ошибки, назовём полиномs(x) ≡g(x) w(x).Определение синдрома для циклического кода, очевидно, естьперефразировка в терминах полиномов синдрома длягрупповых кодов.Свойства синдрома w(x):s(x) ≡ 0 ⇔ w(x) — кодовое слово;0 6 deg s(x) < m = n − k;s(x) ≡g(x) v(x) + e(x) ≡g(x) e(x) ≡xn +1 w(x)h(x).ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование66 / 132Циклические коды: декодирование... и свойстваДекодирование циклического кода проходит по общей схемедекодирования линейного кода:1вычисляется синдром s(x) принятого слова w(x);2ищутся решения системы e(x) = s(x) + g(x)u(x) для всех2k возможных полиномов u(x) степени k − 1;3определяется полином ошибок как решение сминимальным числом ненулевых слагаемых;4восстанавливается переданное сообщениеu(x) = w(x) + e(x).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование67 / 132Циклические групповое коды (n, k): резюмеЦиклические коды — подкласс групповых.Кодирование производится с помощью порождающегополинома, являющийся делителем многочлена xn + 1.При этом:для задания циклических кодов достаточно указатьпорождающий полином;выбор делителя, порождающего код с большим кодовымрасстоянием — сложная задача.Декодирование осуществляется с помощью вычисляемогосиндрома принятого полинома, в результате:вместо умножения матриц на векторы и решение СЛАУ(как в линейных кодах общего вида) используются болеепростые операции умножения полиномов и их деления состатком;однако общий алгоритм декодирования по-прежнему имеетэкспоненциальную сложность по k.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХРазделы I12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать68 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойстваРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать69 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства70 / 132Коды БЧХРассматриваемый далее способ построения «хорошего» кода,исправляющего «много» ошибок предложили Р.Ч. Боуз иД.К.
Рей-Чоудхури в 1960 г. независимо от на год ранееопубликованной работы А. Хоквингема.Они называются кодами Боуза-Чоудхури-Хоквингема илиБЧХ-кодами (BCH, Bose-Chaudhuri-Hocquenghem) — это классциклических кодов, исправляющих кратные ( 2 и более, d > 5)ошибки.Теоретически коды БЧХ могут исправлять произвольноеколичество ошибок, но при этом существенно увеличиваетсядлина кодового слова n, что приводит к уменьшению скоростипередачи данных и усложнению приёмно-передающейаппаратуры.Коды Хэмминга — частный случай БЧХ-кодов.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойстваР.Ч. Боуз и Д.К.
Рей-ЧоудхуриРадж Чандра Боуз(Raj Chandra Bose, 1901–1987) —индийский математик, работавший в США.Известен работой (в соавторстве), опровергающейгипотезу Л.Эйлера о несуществовании двухвзаимно ортогональных латинских квадратовпорядка 2n + 2 для любого натурального n.Двайджендра Камар Рей-Чоудхури(Dwijendra Kumar Ray-Chaudhuri, 1933) —индийский математик, работающий в США.Обладатель медали Эйлера, присуждаемойИнститутом комбинаторики и приложений(Institute of Combinatorics and its Applications,Канада) за вклад в развитие комбинаторики.71 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства72 / 132А. ХоквингемАлексис Хоквингем(Alexis Hocquenghem, 1908?–1990) —французский математик.В его работе 1959 г.
содержится первоеописание линейных циклических кодов,исправляющих кратные ошибки.Правильное чтение его фамилии — Окенгем.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойстваСвойства минимальных многочленов mβ (x) поля73 / 132FnpВспоминаем:1∀ β ∈ Fnp ( ∃! mβ (x) ) и deg mβ (x) = b 6 n;2Если3Fnp = Fp [x]/(a(x)), то a−1n a(x) — м.м. для x;.f (β) = 0 ⇒ f (x) .. mβ (x);4Минимальный многочлен неприводим.5Минимальный многочлен генератора мультипликативнойгруппы поля (примитивного элемента) называетсяпримитивным многочленом.Если β — корень неприводимого многочлена ϕ(x) ∈ Fp [x]степени n, тоno2n−1β, β p , β p , .
. . , β p— все n различных (смежных) корней ϕ(x).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства74 / 132Циклотомический смежный класс элемента поляОпределениеПусть n 6 N .Циклотомическим классом (или классом смежности) надполем Fnp , порождённым элементом α ∈ FNp называетсяNмножество всех различных элементов Fp , являющихся pn -ымистепенями α.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства74 / 132Циклотомический смежный класс элемента поляОпределениеПусть n 6 N .Циклотомическим классом (или классом смежности) надполем Fnp , порождённым элементом α ∈ FNp называетсяNмножество всех различных элементов Fp , являющихся pn -ымистепенями α.Свойства циклотомических классовЦиклотомические классы смежности различных элементовлибо совпадают, либо не пересекаются.Т.е.
совокупность всех циклотомических классов поля FNpобразует его разбиение его мультипликативной группы.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойстваСвойства циклотомических классов...Если α — примитивный элемент поля Fmnp , то его onn2n(m−1)nциклотомический класс α, αp , αp . . .
, αpнадnполем Fp содержит ровно m элементов.75 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства75 / 132Свойства циклотомических классов...Если α — примитивный элемент поля Fmnp , то его onn2n(m−1)nциклотомический класс α, αp , αp . . . , αpнадnполем Fp содержит ровно m элементов.Примеры ( p = 2: разложения мультипликативных группполей Fmnна циклотомические классы над Fn2 )21n = 1, m = 3 и α — примитивный элемент F32 .Тогда α7 = 1 и рассматриваемое разложение над2436{ 1 }, { α, α , α }, { α , α , α125F2 есть= α }.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства75 / 132Свойства циклотомических классов...Если α — примитивный элемент поля Fmnp , то его onn2n(m−1)nциклотомический класс α, αp , αp .
. . , αpнадnполем Fp содержит ровно m элементов.Примеры ( p = 2: разложения мультипликативных группполей Fmnна циклотомические классы над Fn2 )21n = 1, m = 3 и α — примитивный элемент F32 .Тогда α7 = 1 и рассматриваемое разложение над2436{ 1 }, { α, α , α }, { α , α , α212F2 есть5= α }.n = 2, m = 2 и α — примитивный элемент F42 .Тогда α15 = 1 и рассматриваемое разложение надF22 есть{ 1 }, { α, α4 }, { α2 , α8 }, { α3 , α12 },{ α5 }, { α10 }, { α6 , α9 }, { α7 , α13 }, { α11 , α14 }ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства76 / 132Свойства циклотомических классов...Если α ∈ Fn2 и m — мощность его циклотомическогокласса над некоторым подполем α ∈ Fn2 , то полиномg(x) =m−1Yi(x + α2 ) = xm−1 + λm−2 xm−2 + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
