AA3-2(ECC) (1127140), страница 10
Текст из файла (страница 10)
d = 3.Проводим систематическое кодирование сообщения u(x):v(x) = x6 u(x) + r(x) =r(x) ≡ g(x) x6 u(x) ≡x6 +x3 +1 x8 + x7 = x5 + x4 + x2 + x,= x8 + x7 + x5 + x4 + x2 + x ↔ [011011011]и убеждаемся, что биты сообщения находятся в крайне правыхпозициях кодового слова.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-3Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ F2 [x]/ x3 + x + 1 .Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.117 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями117 / 132Задача ТК-3Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ 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 6= 0.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями117 / 132Задача ТК-3Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ 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 6= 0.Далее необходимо найти полином ошибок вида e(x) = xkтакой, что e(α) = s, т.е.
найти такое k, что αk = 1.Очевидно, что k = 0 ⇒ vb(x) = w(x) + e(x) = x7 + x6 + x2 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями118 / 132Задача ТК-4Для кода БЧХ с нулями αi , i = 1, . . ., 4, где α — примитивныйэлемент поля F = F2 [x]/ x4 + x + 1 , и принятого словаw(x) = x14 + x10 + x5 + x4 .найти полином локаторов ошибок σ(x).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями118 / 132Задача ТК-4Для кода БЧХ с нулями αi , i = 1, . .
., 4, где α — примитивныйэлемент поля F = F2 [x]/ x4 + x + 1 , и принятого словаw(x) = x14 + x10 + x5 + x4 .найти полином локаторов ошибок σ(x).РешениеДля удобства вычислений в поле F построим таблицусоответствий между степенным и полиномиальнымпредставлением элементов поля.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-4... ( α4 = α + 1)αα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 + 11119 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-4...С помощью этой таблицы вычислим синдромы: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.120 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-4...С помощью этой таблицы вычислим синдромы: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) является решениемуравненияx2r+1 a(x) + s(x)σ(x) = λ(x), deg λ(x) 6 t.120 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-4... ( x2r+1 a(x) + s(x)σ(x) = λ(x), deg λ(x) 6 t)Решаем с помощью расширенного алгоритма Евклида:Шаг 0. 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.121 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-4...Таким образом, искомый полином локаторов ошибокσ(x) = α14 x2 + α7 x + 1.122 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-5Рассмотрим код БЧХ, нули которого определяются степенямиα, где α — примитивный элемент поля F2 [x]/ x4 + x + 1 .Пусть для некоторого принятого слова w(x) полиномлокаторов ошибок σ(x) = α2 x2 + α6 x + 1.Требуется определить позиции ошибок в w(x).123 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями123 / 132Задача ТК-5Рассмотрим код БЧХ, нули которого определяются степенямиα, где α — примитивный элемент поля F2 [x]/ x4 + x + 1 .Пусть для некоторого принятого слова w(x) полиномлокаторов ошибок σ(x) = α2 x2 + α6 x + 1.Требуется определить позиции ошибок в w(x).РешениеНайдём корни полинома локаторов ошибок полным перебором.Для вычислений будем пользоваться таблицей соответствиймежду степенным и полиномиальным представлениемэлементов поля, вычисленной в предыдущей задаче ТК-4.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-5... (α4 = α + 1)σ(x) = α2 x2 + α6 x + 1σ(α) = α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 ,124 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями125 / 132Задача ТК-5...σ(x) = α2 x2 + α6 x + 1σ(α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.Обратные элементы для обнаруженных корней α5 и α8 равны,соответственно, α10 и α7 (α15 = 1).Отсюда получаем, что полином ошибок естьe(x) = x10 + x7 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-6Построить БЧХ-код длины 15, исправляющий не менее 2-хошибок.126 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями126 / 132Задача ТК-6Построить БЧХ-код длины 15, исправляющий не менее 2-хошибок.Решение .Имеем qОбразуем поле F = F42неприводимый полином= 4, n = 24 − 1 = 15 и d = 5.∼= F2 [x]/(a(x)), взяв в качестве a(x)4-й степени x4 + x + 1.Полином a(x) — примитивен, т.е. является м.м.
для x.Находим циклотомические классы для элементов α, α2 , α3 , α4поля F , где α = x — генератор мультипликативной группыF ∗ , учитывая, что α15 = 1, α4 = α + 1.Очевидно, данных циклотомических класса два: α, α2 , α4 , . . . и α3 , α6 , α12 , . . . ,так что для порождающего многочлена g(x) конструируемогоБЧХ-кода будем иметь g(x) = gα (x) · gα3 (x).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями127 / 132Задача ТК-6... α4 = α + 1Ясно, что gα (x) = a(x) = x4 + x + 1.Определим циклотомический класс для элемента α3 , для чеговычислим требуемые его степени:α6 = α4 α2 = (α + 1)α2 = α3 + α2 ,22α12 = α6 = α3 + α2 = α4 + α3 + α2 = α3 + α2 + α + 1,α24 = α8 + α6 + α4 = (α2 + 1) + (α3 + α2 ) + (α + 1) = α3 + α,α48 = α6 + α2 = α3 .В результате получаем4-х элементный циклотомический классα3 , α6 , α12 , α24 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениями128 / 132Задача ТК-6... α4 = α + 1, α15 = 1Вычислим м.м. для α3 :gα3 (x) = (x + α3 )(x + α6 )(x + α12 )(x + α24 ) == x2 + (α3 + α12 x + α15 ) x2 + (α6 + α24)x + α30 == x2 + (α2 + α + 1)x + 1 x2 + (α2 + α)x + 1 == x4 + x3 + x2 + x + 1.Таким образом,g(x) = gα (x)·gα3 (x) = x4 + x + 1= x8 + x7 + x6 + x4 + 1,x4 + x3 + x2 + x + 1 =deg g(x) = m = 8, k = 15 − 8 = 7и получен порождающий полином g(x) для БЧХ(15, 7, 5)-кода.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЗадачи с решениямиЗадача ТК-7Построить 31-разрядный БЧХ-код для исправления не менее3-х ошибок.129 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями129 / 132Задача ТК-7Построить 31-разрядный БЧХ-код для исправления не менее3-х ошибок.РешениеИмеем n = 31 = 25 − 1, r = 3, d = 7.Порождающий многочлен g(x) конструируемого кода должениметь корни α, α2 , α3 , α4 , α5 , α6 , где α — примитивныйэлемент поля F = F52 .Поле F можно задать так, чтобы в разбиении егомультипликативнойгруппы на циклотомическиеклассы имелся248165-элементный α, α , α , α , αкласс.Остальные рассматриваемые степени α будут входить вциклотомические классы 3 6α , α , . . .
и α5 , α10 , . . . .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЗадачи с решениями130 / 132Задача ТК-7...Потребуем, чтобы эти классы были также пятиэлементным ииз специальных таблиц найдём минимальные многочленыпятой степени для α, α3 и α5 :gα (x) = x5 + x3 + 1,gα3 (x) = x5 + x3 + x2 + x + 1,gα5 (x) = x5 + x4 + x3 + x + 1.Тогда g(x) = gα · gα3 (x) · gα5 (x) == x15 + x11 + x10 + x9 + x8 + x7 + x5 + x3 + x2 + x + 1,deg g(x) = m = 15, k = n − m = 16 и порождающиймногочлен для (31, 16)-кода БЧХ, исправляющего не менее 3-хошибок, построен.Поле F определяется как F2 [x]/ x5 + x3 + 1 .ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЧто надо знатьРазделы I12Блоковое кодирование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
