Разбор контрольной работы (1127255), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

В2nэтом расширении f (x) имеет n корней α, αq , αq , . . . , αq , где α – произвольный корень f (x) в построенном расширении F . При этом многочлен f (x) не имеет корней ни в каком конечном поле,содержащим менее, чем q n элементов, и имеющим ту же характеристику, что и F .Рассмотрим расширение поля F3 : F3 [x]/(x2 + 2x + 2). В этом расширении многочлен x2 + 2x + 2имеет корни α и α3 = α ·α2 = α(α +1) = α2 +α = 2α +1. Кроме того, данное расширение содержит всебе корень 2, найденный ранее для f (x). Таким образом, многочлен f (x) в поле F3 [x]/(x2 + 2x + 2)раскладывается на линейные множители:f (x) = x3 + x + 2 = (x + 1)(x + 2α)(x + α + 2).В общем случае процесс получения всех корней некоторого многочлена f (x) над конечным полемF из q элементов можно представить следующим образом:1. Разложить f (x) на неприводимые множители над F :f (x) = m1 (x)m2 (x) .

. . mk (x).Пусть di = deg mi .di2. Для каждого mi (x) рассмотреть расширение F [x]/(mi (x)) и взять в нём корни α, αq , . . . , αq .3. Объединить все корни в одном общем расширении F . Данное расширение будет состоять изq HOK(m1 ,m2 ,...,mk ) элементов.Найти минимальный многочлен m(x) ∈ F5 [x], который имеет корень α3 , где α – примитивныйэлемент поля F25 = F5 [x]/(x2 + x + 2).Известно, что минимальный многочлен m(x) в поле F25 содержит вместе с корнем α3 все смежные22с ним (α3 )5 , (α3 )5 , . . .

. С учётом α5 −1 = α24 = 1 получаем, что смежный класс, образованный α3 ,содержит только два элемента α3 и α15 . Следовательно, минимальный многочлен имеет степень 2и может быть представлен какm(x) = (x − α3 )(x − α15 ) = x2 − (α3 + α15 )x + α18 .Найдём коэффициенты многочлена с учётом α2 = −α − 2 = 4α + 3:α3 = α · α2 = α(4α + 3) = 4α2 + 3α = 4(4α + 3) + 3α = 4α + 2,α15 = (α3 )5 = (4α + 2)5 = 4α5 + 2 = 4α2 α3 + 2 = 4(4α + 3)(4α + 2) + 2 == 4(α2 + 1) + 2 = 4(4α + 4) + 2 = α + 3,α3 + α15 = 4α + 2 + α + 3 = 0,α18 = α3 α15 = (4α + 2)(α + 3) = 4(4α + 3) + 4α + 1 = 3.Заметим, что в полном соответствии с теорией значения коэффициентов m(x) получились из F5 . Витогеm(x) = x2 + 3.Линейный код задан своей проверочной матрицей0 0 1 1H = 0 1 0 11 1 1 011110 .0Требуется построить порождающую матрицу кода G для систематического кодирования, прикотором биты исходного сообщения переходят в последние биты кодового слова.

Найти систематическое кодирование для векторов u1 = [1 1 0]T , u2 = [1 0 1]T .Порождающая матрица кода G, обеспечивающая требуемое систематическое кодирование, должPна иметь вид, где I3 – единичная матрица размера 3×3. Такую матрицу можно получить, еслиI3привести проверочную матрицу H к виду I3 P , т.е. с помощью эквивалентных преобразованийстрок выделить в первых трех колонках единичную матрицу:0 0 1 1 1 11 1 1 0 1 01 0 1 1 0 01 0 0 0 11↔31←1+21←1+30 1 0 1 1 0 −−−→ 0 1 0 1 1 0 −−−−−→ 0 1 0 1 1 0 −−−−−→ 0 1 0 1 10 0 1 1 11 1 1 0 1 00 0 1 1 1 10 0 1 1 1 1Теперь можно построить требуемую порождающую матрицу и осуществить кодирование для u1и u2 :0 1 11 11 1 00 11 1 1 , [v 1 , v 2 ] = G[u1 , u2 ] = 0 0 .G=1 0 01 10 1 01 00 0 10 1Циклический (9, 3)-код задан своим порождающим полиномом g(x) = x6 + x3 + 1. Требуетсяопределить минимальное расстояние кода d, а также осуществить систематическое кодирование полинома u(x) = x2 + x.10 .1Для определения минимального кодового расстояния d найдём все кодовые полиномы:v(x) = g(x)(ax2 +bx+c) = (x6 +x3 +1)(ax2 +bx+c) = ax8 +bx7 +cx6 +ax5 +bx4 +cx3 +ax2 +bx+c, a, b, c ∈ F2 .В векторном виде все кодовые слова представляются как [a, b, c, a, b, c, a, b, c].

Следовательно, минимальный хэммингов вес ненулевого кодового слова равен 3, т.е. d = 3.Систематическое кодирование полинома u(x) вычисляем непосредственноv(x) = x6 u(x) + mod(x6 u(x), g(x)) = x8 + x7 + mod(x8 + x7 , x6 + x3 + 1) = x8 + x7 + x5 + x4 + x2 + x.Рассмотрим код Хэмминга, ноль которого определяется примитивным элементом α ∈F2 [x]/(x3 + x + 1). Требуется декодировать полученный полином w(x) = x7 + x6 + x2 + 1.Вычислим синдром с учётом α3 = α + 1:s = w(α) = α7 + α6 + α2 + 1 = α(α3 )2 + (α3 )2 + α2 + 1 == α(α + 1)2 + (α + 1)2 + α2 + 1 = α(α2 + 1) + α2 + 1 + α2 + 1 = α3 + α = α + 1 + α = 1.Далее необходимо найти полином ошибок вида e(x) = xk такой, что e(α) = s, т.е. найти k: αk = 1.Очевидно, что k = 0.

Следовательно, v̂(x) = w(x) + e(x) = x7 + x6 + x2 .Рассмотрим код БЧХ с нулями αi , i = 1, . . . , 4, где α – примитивный элемент поля F2 [x]/(x4 +x + 1). Требуется найти полином локаторов ошибок σ(x) для принятого полинома w(x) = x14 +x10 + x5 + x4 .Для удобства вычислений в поле F42 построим таблицу соответствий между степенным и полиномиальным представлением элементов поля:αα2α3α4α5α6α7α8α9α10α11α12α13α14α15αα2α3α+1α2 + αα3 + α2α3 + α + 1α2 + 1α3 + αα2 + α + 1α3 + α2 + αα3 + α2 + α + 1α3 + α2 + 1α3 + 11С помощью этой таблицы вычислим синдромы:s1 = w(α) = α14 + α10 + α5 + α4 = α7 ,s2 = w(α2 ) = (w(α))2 = α14 ,s3 = w(α3 ) = α12 + 1 + 1 + α12 = 0,s4 = w(α4 ) = (w(α2 ))2 = α13 .В результате синдромный полином s(x) = α13 x4 + α14 x2 + α7 x + 1.

Синдромов всего четыре, следовательно, t = 2. Полином локаторов ошибок σ(x) является решением уравненияx2t+1 a(x) + s(x)σ(x) = λ(x), deg λ(x) ≤ t.Решим данное уравнение с помощью расширенного алгоритма Евклида:r−2 (x) = x5 , // Инициализацияr−1 (x) = α13 x4 + α14 x2 + α7 x + 1,y−2 (x) = 0,y−1 (x) = 1.Шаг 1. r−2 (x) = r−1 (x)q0 (x) + r0 (x), // Делим с остатком r−2 (x) на r−1 (x)q0 (x) = α2 x,r0 (x) = αx3 + α9 x2 + α2 x,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = α2 x.Шаг 2. r−1 (x) = r0 (x)q1 (x) + r1 (x), // Делим с остатком r−1 (x) на r0 (x)q1 (x) = α12 x + α5 ,r1 (x) = α14 x2 + 1,y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + α2 x(α12 x + α5 ) = α14 x2 + α7 x + 1.Таким образом, искомый полином локаторов ошибок σ(x) = α14 x2 + α7 x + 1.Шаг 0.Рассмотрим код БЧХ, нули которого определяются степенями α, где α – примитивный элемент поля F2 [x]/(x4 + x + 1).

Пусть для некоторого принятого слова w(x) полином локаторовошибок σ(x) = α2 x2 + α6 x + 1. Требуется определить позиции ошибок в w(x).Найдём корни полинома локаторов ошибок полным перебором. Для вычислений будем пользоваться таблицей соответствий между степенным и полиномиальным представлением элементовполя, вычисленной выше:σ(α) = α4 + α7 + 1 = α3 + 1,σ(α2 ) = α6 + α8 + 1 = α3 ,σ(α3 ) = α8 + α9 + 1 = α3 + α2 + α,σ(α4 ) = α10 + α10 + 1 = 1,σ(α5 ) = α12 + α11 + 1 = 0,σ(α6 ) = α14 + α12 + 1 = α2 + α + 1,σ(α7 ) = α + α13 + 1 = α3 + α2 + 1,σ(α8 ) = α3 + α14 + 1 = 0,σ(α9 ) = α5 + 1 + 1 = α2 + α,σ(α10 ) = α7 + α + 1 = α3 ,σ(α11 ) = α9 + α2 + 1 = α3 + α2 + α + 1,σ(α12 ) = α11 + α3 + 1 = α2 + α + 1,σ(α13 ) = α13 + α4 + 1 = α3 + α2 + α + 1,σ(α14 ) = 1 + α5 + 1 = α2 + α,σ(α15 ) = α2 + α6 + 1 = α3 + 1.Заметим, что полином локаторов ошибок σ(x) является полиномом над полем F42 .

Поэтому здесьне выполняется свойство σ(α2 ) = (σ(α))2 . Обратные элементы для обнаруженных корней α5 и α8равны, соответственно, α10 и α7 . Отсюда получаем, что полином ошибок e(x) = x10 + x7 ..

Характеристики

Список файлов ответов (шпаргалок)