AA3-2(ECC) (1127140), страница 7
Текст из файла (страница 7)
. . + λ1 x + λ0i=0является м.м. α (а также для всех элементов, входящих вего циклотомический класс смежности).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства76 / 132Свойства циклотомических классов...Если α ∈ Fn2 и m — мощность его циклотомическогокласса над некоторым подполем α ∈ Fn2 , то полиномg(x) =m−1Yi(x + α2 ) = xm−1 + λm−2 xm−2 + . . . + λ1 x + λ0i=0является м.м. α (а также для всех элементов, входящих вего циклотомический класс смежности).Отсюда выводится метод построения м.м. для данногоэлемента поля α:1определить число m элементов циклотомического классаэлемента α;2найти коэффициенты полинома mα (x) путемiперемножения многочленов x + α2 для всех i = 0, m − 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства77 / 132Специальные циклические кодыЕсли длина циклического кода n = 2q − 1, то:12корнями многочлена xn + 1 являются все ненулевыеэлементы поля Fq2 ;порождающими многочленами циклического кода могутбыть только произведения минимальных многочленов длянекоторых совокупностей элементов Fq2 .Такие коды:1являются подмножеством циклических кодов, имеющимуказанную удобную связь между порождающимполиномом и элементами из Fq2 ;2уже не могут иметь произвольные дли́ны (есть способобойти это ограничение — использование т.н.
укороченныхкодов БЧХ, которые мы не рассматриваем).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства78 / 132БЧХ-коды: построение (в простейшем случае)Пусть выбраны параметры q, определяющий длину кодаn = 2q − 1 и конструктивное расстояние d 6 n.Код БЧХ есть циклический (n, k)-код, в котором порождающиймногочлен g(x) имеет корнями элементы α, α2 , α3 , . . .
, αd−1поля F = Fq2 (называемые нулями БЧХ-кода), где α —генератор мультипликативной группы F ∗ , deg g(x) = m (числопроверочных бит), k = n − m (число информационных бит).При этом:g(x) выбирают как произведение полиномов,соответствующих всем циклотомическим классам, вкоторые попали нули БЧХ-кода (или как НОК их м.м.);кодовое расстояние построенного кода оказывается неменее выбранного конструктивного расстояния d.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства79 / 132БЧХ-код: кодовое расстояние не менее конструктивногоТеоремаПусть БЧХ-код длиной n = 2q − 1 задаётся кодирующиммногочленомg(x) = HOK (m1 (x), . .
. , md−1 (x)),где mi (x), i = 1, d − 1 — минимальные многочлены нулей кодаα, α2 , . . . , αd−1 .Тогда кодовое расстояние данного БЧХ-кода не менее d.ДоказательствоПокажем, что многочлен g(x) с корнями α, α2 , . . . , αd−1имеет не менее d ненулевых элементов.Предположим противное. Тогда g(x) можно записать в видеg(x) = b1 xn1 + b2 xn2 + . .
. + bd−1 xnd−1 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства80 / 132БЧХ-код: кодовое расстояние не менее конструктивного...Поскольку α, α2 , . . . , αd−1 — корни g(x), его коэффициентыb1 , . . . , bd−1 удовлетворяют линейной системеb1 αn1+ . . . + bd−1 αnd−1= 02n2n1d−1b1 α+ . . . + bd−1 α= 0..................b1 α(d−1)n1 + . . . + bd−1 α(d−1)nd−1 = 0Матрица A коэффициентов невырождена, т.к. её определительВандермонда отличен от нуля:Y|A| =( αni − αnj ) 6= 0, nj < ni < 2q .i>jСледовательно, b1 = .
. . = bd−1 = 0 — противоречие.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХОпределение и основные свойства81 / 132Коды БЧХ: синдромыПоскольку все кодовые слова циклического кода C делятся наполином g(x) с корнями α, α2 , . . . , αd−1 , тоv(x) ∈ C ⇔ v(αi ) = 0, i = 1, d − 1.ОпределениеСиндромами принятого полинома w(x), закодированногоБЧХ-кодом с нулями αi , i = 1, d − 1 и, возможно, содержащегоошибки, назовём значения w(x) в нулях кода: si = w(αi ).Ясно, что«все синдромы равны нулю» ⇔ w(x) — кодовое слово.Определение синдрома для БЧХ-кода, очевидно, естьперефразировка в терминах нулей кода полиномов синдромадля циклического кода.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодамиРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать82 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодами83 / 132Построение кодов БЧХ: пример для q = 3, n = 23 − 1 = 7Пусть q = 3, т.е.
строим БЧХ-коды для поля F = F32 и n = 7.В качестве порождающего поле F = F2 [x]/(a(x)) многочленавозьмём неприводимый многочлен a(x) = x3 + x + 1.a(x) — м.м. для некоторого генератора α ∈ F ∗ и F ∗разбивается на следующие циклотомические классы над { 1 } , α, α2 , α4 , α3 , α6 , α5 .F2 :ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодами83 / 132Построение кодов БЧХ: пример для q = 3, n = 23 − 1 = 7Пусть q = 3, т.е. строим БЧХ-коды для поля F = F32 и n = 7.В качестве порождающего поле F = F2 [x]/(a(x)) многочленавозьмём неприводимый многочлен a(x) = x3 + x + 1.a(x) — м.м.
для некоторого генератора α ∈ F ∗ и F ∗разбивается на следующие циклотомические классы над { 1 } , α, α2 , α4 , α3 , α6 , α5 .F2 :1. Код БЧХ, исправляющий r = 1 ошибку (код Хэмминга).Тогда d − 1 = 2r = 2 и элементы α, α2 попадают в одинциклотомический класс.Минимальный многочлен для элементов этого класса — a(x).Поэтому порождающий полином g(x) = a(x),m = deg a(x) = 3 и в результате получаем уже известный(7, 4, 3)-код.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодами84 / 132Построение кодов БЧХ: пример для q = 3, n = 23 − 1 = 7...2. Код БЧХ, исправляющий не менее r = 2 ошибок.Поскольку d − 1 = 2r = 4, то порождающий полином g(x)есть многочлен минимальной степени с корнями α, α2 , α3 , α4из поля F .Данныеэлементы входят в два циклотомических класса:α, α2 , α4 и α3 , α6 , α5 , порождаемых α и α3соответственно, следовательно g(x) = gα (x) · gα3 (x),где gα (x) и gα3 (x) — м.м. для α и α3 соответственно.М.м.
для α известен: gα (x) = a(x) = x3 + x + 1.Найдем м.м. для α3 :gα3 (x) = (x + α3 )(x + α5 )(x + α6 ) == x3 + (α3 + α5 + α6 )x2 + (α8 + α9 + α11 )x + α14 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодами85 / 132Построение кодов БЧХ: пример для q = 3, n = 7...Вычислим коэффициенты gα3 (x).Поскольку α — примитивный элемент полято α7 = 1, α3 = α + 1 иF2 [x]/ x3 + x + 1 ,α3 + α5 + α6 = α + 1 + (α + 1)2 + α2 (α + 1) == α + 1 + α2 + 1 + α3 + α2 = 1 ,α8 + α9 + α11 = α2 + α + α4 = α2 + α + α(α + 1) = 0 ,α14 = 1 .Таким образом, gα3 (x) = x3 + x2 + 1 иg(x) = gα (x) · gα3 (x) = (x3 + x + 1)(x3 + x2 + 1) == x6 + x5 + x4 + x3 + x2 + x + 1,deg g(x) = 6, k = 7−6 = 1.В результате построен тривиальный (7, 1, 7)-код (очевидно,содержащий всего два кодовых слова v 1 = [0000000],v 2 = [1111111]), исправляющий 3 ошибки.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодамиПостроение кодов БЧХ: пример для q = 4, n = 15, d = 7Построим БЧХ-код длины n = 15, исправляющий 3 ошибки(т.е. q = 4, d = 7).В качестве порождающего поле F ∼= F2 [x]/(a(x))неприводимого многочлена возьмём a(x) = x4 + x + 1.Пусть α — генератор F ∗ (т.е. α15 = 1, α4 = α + 1).Нулями конструируемого БЧХ-кода будут α, α2 , . . . , α6 ,которые попадают в циклотомические классы α, α2 , α4 , α8 , α3 , α6 , α12 , α9 = α24 , α5 , α10 .86 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХКодирование БЧХ-кодамиПостроение кодов БЧХ: пример для q = 4, n = 15, d = 7Построим БЧХ-код длины n = 15, исправляющий 3 ошибки(т.е. q = 4, d = 7).В качестве порождающего поле F ∼= F2 [x]/(a(x))неприводимого многочлена возьмём a(x) = x4 + x + 1.Пусть α — генератор F ∗ (т.е. α15 = 1, α4 = α + 1).Нулями конструируемого БЧХ-кода будут α, α2 , . . .
, α6 ,которые попадают в циклотомические классы α, α2 , α4 , α8 , α3 , α6 , α12 , α9 = α24 , α5 , α10 .Минимальные многочлены для элементов-представителей этихклассов суть gα (x) = x4 + x + 1, gα3 (x) = x4 + x3 + x2 + x + 1 иgα5 (x) = x2 + x + 1, а порождающим полиномом полученного(15, 5, 7)-кода БЧХ естьg(x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1) == x10 + x8 + x5 + x4 + x2 + x + 1.86 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХРазделы12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать87 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ88 / 132Декодирование кода Хэмминга (n = 2q − 1)Код Хэмминга является простейшим кодом БЧХ.У него r = 1, d = 3 и поэтому нулями кода Хэммингаявляются α и α2 , где α — примитивный элемент поляFq2 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ88 / 132Декодирование кода Хэмминга (n = 2q − 1)Код Хэмминга является простейшим кодом БЧХ.У него r = 1, d = 3 и поэтому нулями кода Хэммингаявляются α и α2 , где α — примитивный элемент поляFq2 .Для декодирования принятого слова w(x) вычисляем синдромs1 = w(α) (s2 = w(α2 ) нам не потребуется).Приs1 = 0 — ошибки не произошло и v(x) = w(x);s1 6= 0 — произошли ошибки иесли s1 = αj для некоторого j ∈ {0, . .
. , n − 1}, то j —искомая позиция ошибки (при единичной ошибке в j-ойпозиции e(x) = xj ) и v(x) = w(x) + xj ;иначе, произошло более одной ошибки.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХ89 / 132Декодирование кода Хэмминга: примерРассматриваем (7, 4)-код Хэмминга, построенный в примередля циклических кодов (порождающий полиномg(x) = x3 + x + 1).Там было найдено систематическое кодирование входногополинома u(x) = x3 + x2 : v(x) = x6 + x5 + x.Теперь мы построили этот же код с использованием поляF = F2 [x]/ x3 + x + 1 .
Для примитивного элемента α этогополя имеем α7 = 1 и α3 = α + 1.Пусть при передаче рассматриваемого сообщения произошлаошибка в позиции 5, т.е. принято слово w(x) = x6 + xи (неизвестный) полином ошибок e(x) = x5 .Для декодирования w(x) найдем синдром2s1 = w(α) = α6 + α = α3 + α = (α + 1)2 + α == α2 + α + 1 6= 0.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиКоды БЧХДекодирование кодов БЧХДекодирование кода Хэмминга: пример...Вычислим αj для j = 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
