Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 30
Текст из файла (страница 30)
Значит, это либо многочлен степени не выше 2, чегоне может быть по теореме 3.52, либо многочлен 1 + x3 . Но1 + x3 ≡ x mod (1 + x + x3 ), поэтому в последнем случае мы быполучили все кольцо вычетов. Таким образом, минимальноечисло единиц (равное кодовому расстоянию) для этого кодаравно 3.Вопрос о кодовом расстоянии произвольного циклическогокода безнадежно труден.
Но есть несколько важных конструкций циклических кодов с хорошими параметрами. Далее мыприводим несколько примеров.4.3. Коды БЧХВ этом разделе будем рассматривать коды, имеющие длину n = 2k − 1. Описываемый ниже способ способ построения«хорошего» кода, исправляющего «много» ошибок, придуманБоузом, Чоудхури и Хоквингемом. Поэтому коды, которые мыполучим, называются БЧХ-кодами.Рассмотрим такое уточнение описанной выше схемы.
Возьмем какой-нибудь неприводимый многочлен и построим понему поле. Ненулевые элементы поля, как было показано выше, образуют циклическую группу по умножению. Выберемпорождающий элемент этой группы α и рассмотрим степениα, α2 , . . . , α2r , где r — число ошибок, которые нужно уметьисправлять. И теперь в разложении соответствующего многочлена xn − 1 выберем такие неприводимые множители, чтобыкаждая из указанных степеней была корнем одного из них.Оказывается, что это гарантирует исправление r ошибок.Пример 4.10. Возьмем x15 − 1.
Предположим, что нуженкод, исправляющий три ошибки. Значит, нужно найти многочлены, корнями которых являются первые шесть степенейпорождающего элемента α. Если многочлен имеет корень α,то по теореме 3.41 можно указать все его корни: α, α2 , α4 , α8 .176Глава 4.Коды, исправляющие ошибкиАналогично, если у многочлена есть корень α3 , то у него будуткорни α3 , α6 , α12 , α9 . Наконец, если у многочлена есть кореньα5 , то у него также есть корень α10 .Перемножив три многочлена, подобранных по указанныммножествам корней, получим многочлен 10-й степени. Значит,идеал по модулю этого многочлена дает пять степеней свободы.
Построенный код будет 5-мерным пространством.Теперь проведем эти рассуждения в более общем виде.Начнем с простой части — построения кода, а затем ужебудем доказывать, что он действительно исправляет ошибки.Итак, полагаем n = 2k − 1. Из разложения на множителимногочлена xn − 1xn − 1 = ϕ1 (x) · . . . · ϕk (x) · . . . · ϕp (x)(4.1)α, α2 , α3 , . .
. , α2r .(4.2)выберем те сомножители, корни которых содержат степениПеремножая выбранные сомножители, получаем искомый многочлен ϕ, порождающий идеал, который и даст нам хорошийкод. Какова степень ϕ?Если какой-то многочлен имеет корень α, значит, он такжеимеет корень α2 . И вообще, если многочлен имеет корень αs ,то он имеет также и корень α2s .
Таким образом, нам потребуется не более r штук многочленов, потому что каждый извыбираемых многочленов имеет по крайней мере два корня.А степень неприводимого делителя xn − 1 не больше k (напомним, что было выбрано n = 2k − 1). Поэтому общая степеньпроизведения всех выбранных многочленов не больше rk, гдеk = log2 (n + 1), rk = r log2 (n + 1).Итак, идеал, порожденный ϕ, будет иметь размерность nминус степень порождающего полинома, значит точек в этомидеале будет не меньше, чем2n2n−r log2 (n+1) =.(n + 1)rНа самом деле эта оценка неточная: в ней учитываются толькопо два корня из каждого многочлена, а их может быть больше.Докажем, что расстояние между точками кода не меньше,чем 2r + 1.
Заметим, что все многочлены, входящие в наш код,4.3.177Коды БЧХкратны ϕ. Поэтому каждый кодовый многочлен имеет корниα, α2 , . . . , α2r . Значит, нам достаточно доказать следующееутверждение.Лемма 4.11. Если ψ(αs ) = 0 при 1 6 s 6 2r, то у ψ не менее2r + 1 ненулевого коэффициента.Доказательство. Рассмотрим многочлен ψ(x) = a0 + a1 x ++ · · · + an−1 xn−1 , удовлетворяющий этому условию. Его коэффициенты дают решение следующей системы линейных уравнений: 1αα2...αn−1a001 (α2 ) (α2 )2 . .
. (α2 )n−1 a 0 1 = . (4.3). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1α2r(α2r )2...(α2r )n−1an−10Если набор a = (a0 , . . . , an−1 ) — решение этой системы, то,как нетрудно видеть, между kak столбцами матрицы системы (4.3) есть линейная зависимость. Поэтому для доказательства леммы 4.11 достаточно показать, что любые 2r столбцовэтой матрицы линейно независимы.Теория решения линейных уравнений над конечным полемничем не отличается от привычной теории решения линейныхуравнений над полем действительных чисел R. (На самом деле, она вовсе не зависит от того, над каким полем мы решаемсистему линейных уравнений.) В частности, линейная зависимость между столбцами квадратной матрицы равносильнаобращению в нуль определителя этой матрицы.Давайте выберем из матрицы системы (4.3) столбцы j1 ,j2 , .
. . , j2r . Получим квадратную матрицу j...αj2rαj2α1 (α2 )j1(α2 )j2 . . . (α2 )j2r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .(α2r )j1(α2r )j2...(α2r )j2rВынесем из всех элементов столбца t общий множитель αjt .Получим, что определитель нашей матрицы с точностью до178Глава 4.Коды, исправляющие ошибкиненулевого множителя αj1 +j2 +···+j2r равен11...1j2j2r αj1α...αj1 2j2 2j2r 2 (α )...(α ) .V = (α ).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . j 2r−1(α 1 )(αj2 )2r−1 . . . (αj2r )2r−1 (4.4)Это хорошо известный определитель Вандермонда. Вычисляется он над конечным полем точно так же, как и над привычным R:YV =(αjt2 − αjt1 ).t1 <t2В нашем случае определитель отличен от нуля: напомним,что мы взяли в качестве α порождающий элемент мультипликативной группы поля, поэтому все степени α вплоть до(n − 1)-й различны.Итак, мы доказали лемму 4.11.
Значит, построенный намикод действительно исправляет r ошибок (расстояние междукодовыми словами не меньше 2r + 1).4.4. Квадратично-вычетные кодыКвадратично-вычетные коды дают еще один пример хороших циклических кодов.В этом разделе предполагаем, что длина кода простое число, которое дает остаток ±1 от деления на 8.
Длину кода вэтом разделе будем обозначать через p = 8m ± 1. Напомним(см. с. 164), что ненулевой вычет a называется квадратичнымвычетом по модулю p, если уравнение x2 = a имеет решениев поле Z/(p). Множество квадратичных вычетов по модулю nобозначим через Qp , а множество квадратичных невычетов —через Np .Если x2 = a, y 2 = b в поле Z/(p), то (xy −1 )2 = ab−1 . Поэтому квадратичные вычеты по модулю p образуют подгруппумультипликативной группы поля Z/(p).Утверждение 4.12. Пусть q — нечетное простое число. Тогда 2 ∈ Qq тогда и только тогда, когда q ≡ ±1 (mod 8).4.4.179Квадратично-вычетные кодыДоказательство (по [21]). Используем результат задачи 3.8:2 является квадратичным вычетом по нечетному простомумодулю q тогда и только тогда, когда 2(q−1)/2 = 1 (mod q).Любое поле характеристики q содержит подполе GF (q), поэтому условие можно проверять в любом таком поле.Рассмотрим расширение F поля GF (q), которое содержитгруппу корней 8-й степени из единицы (см.
раздел 3.9). Обозначим через α примитивный корень 8-й степени из единицы.В поле F у 2 есть квадратный корень. А именно, β 2 = 2, гдеβ = α + α−1 . В самом деле,(α + α−1 )2 = 2 + α2 + α−2 = 2 + α−2 (α4 + 1) = 2(α4 = −1 так как α — примитивный корень восьмой степени).Теперь нам нужно вычислить β q−1 = 2(q−1)/2 . Пусть q == 8m ± 1. Тогдаβ q = αq + α−q = α±1 + α∓1 = β,поэтому β q−1 = 1.Пусть q = 8m ± 5. Тогдаβ q = αq + α−q = α±5 + α∓5 = −β,поэтому β q−1 = −1.Возьмем поле F характеристики 2, которое содержит группу корней степени p.
Примитивный корень степени p обозначим через ω. Рассмотрим многочленыYYf (x) =(x − ω i ), g(x) =(x − ω i )i∈Qpi∈NpВ силу утверждения 4.12 если p = 8m ± 1, то 2 являетсяквадратичным вычетом по модулю p. Умножение на квадратичный вычет переводит множество квадратичных вычетов всебя и множество квадратичных невычетов в себя. Вспоминаяструктуру разложения xn − 1 на неприводимые множители,описанную в разделе 3.9, получаем, что f (x) и g(x) являютсямногочленами над полем GF (2). Таким образом, над GF (2)имеем разложениеxn − 1 = (x − 1)f (x)g(x).(4.5)180Глава 4.Коды, исправляющие ошибкиОпределение 4.13. Квадратично-вычетными кодами называются идеалы кольца GF (2)/(xn −1), порожденные f (x), g(x),(x − 1)f (x), (x − 1)g(x).Код, порожденный f (x), будем обозначать Q, а код, порожденный g(x), будем обозначать N .Теорема 4.14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
