Реализация действий над элементами поля

При построении кодирующих и декодирующих устройств циклических кодов, особенно БЧХ и Рида—Соломона, должны быть реализованы операции умножения и деления в поле GF(2^k). Рассмотрим реализационные основы таких действий над элементами конечного поля Галуа.

Пусть задан примитивный полином k - йстепени над про­стым полем GF (2):

Квадратной матрице F соответствует характеристический поли­ном f (λ), представляющий собой определитель характеристи­ческой матрицы [λЕ — F], где Е — квадратная единичная мат­рица k-го порядка, т. е. f (λ) =│ λ Е — F│. Корни полинома f (λ) λ ₁, λ ₂, … λ _k,называемые характеристическими числами, являются решением векового [9] уравнения │ λ Е — F│ = 0.

Как видно из этого уравнения, одним из корней полинома f (λ) является сопровождающая матрица F. Действительно, если в характеристический полином f (λ) вместо λ подставить F, то получим f (F) = │FE — F│ =0, Тем самым доказана тео­рема Гамильтона—Кэли [9], в соответствии с которой всякая квадратная матрица F является корнем своего характеристиче­ского полинома f (λ).

С другой стороны, легко проверить, что заданный прими­тивный полином Р (х) в точности совпадает с характеристиче­ским полиномом f (X) при подстановке х = λ, т. е. f (λ) = Р (λ). Отсюда следует, что матрица F является также корнем поли­нома Р (х), т. е. Р (F) = 0. Последнее условие приводит к важ­ному следствию, заключающемуся в том, что множество эле­ментов поля GF(2^k) построенного по примитивному полиному Р (х), изоморфно множеству полиномов — вычетов по модулю P(F). Другими словами, любому элементу a^mполя GF(2^k), выраженному через степенной базис

где. а — первообразный элемент поля, а коэффициенты а, eGF(2), взаимнооднозначно соответствует многочлен

приведенный по модулю Р (F). Указанное свойство позволяет достаточно просто реализовать умножение и деление элемен­тов поля GF (2^к) в векторной форме. Рассмотрим эти действия.

6.4.1. Умножение элементов поля

Пусть необходимо умножить элемент аⁱ на элемент a^J. С этой целью выразим эти элементы поля GF (2^k) через степен­ной базис следующим образом:

Тогда произведение aⁱa^j=a^m=c₀+c₁a+c₂a²+…+c_k-1a^k-1 может быть реализовано в векторной форме следующим обра­зом:

(a₀a₁…a_k)F^j=(a₀a₁…a_k)[b₀E+b₁F+…b_k-1F^k-1]=

Напомним, что для двоичных кодов сложение производится по mod 2.

Структурная схема умножителя в соответствии с алгорит­мом (6.24) представлена на рис. 6.8.

Рис. 6.8. Структурная схема умножителя произвольных элементов поля G F(2^k)

Рассмотрим конкретный пример.

Пусть поле GF (2⁴) образовано примитивным полиномом Р (х) = 1+x+x ⁴. Сопровождающая матрица F этого полино­ма и ее степени F² и F³ имеют вид

Необходимо произвести умножение двух элементов аⁱ и а^j, принадлежащих полю GF (2⁴).

Выразим аⁱ и а^jчерез базис {1, а, а², а³} следующим образом:

Таким образом, векторная форма записи элементов аⁱ и а^j будет соответственно [а] = [а₀, а_ь а₂, a₃] и [b] = [b_о, b₁, b₂, b₃]. Заменив элемент поля a^J на F^j, равный F^j =b₀E+b₁F+b₂F²+b₃F³, найдем произведение (aⁱa^j )= с_о +c₁a+c₂a²+c₃a³ в векторной форме, используя алгоритм (6.24), а именно

Учтем, что для данного полинома Р (х) и его матрицы F имеют место равенства:

Тогда вектор [c]=[c₀,c₁,c₂,c₃], соответствующий произведению aⁱa^j, будет равен поэлементной сумме по модулю два

Функциональная схема существенно упрощается, если необходимо произвольный элемент поля aⁱ умножить на константу a^j. Пусть для рассматриваемого выше примера необходимо производить умножение на а⁵. Тогда произведение аⁱa⁵ в векторной форме будет выражаться следующим образом:

Функциональная схема такого умножителя представлена на рис. 6.10.

Рис 6.9. Функциональная схема умножения произвольных элементов поля G F (2⁴) с образующим многочленом Р(х) = 1 + х + х⁴

Другой распространенный в настоящее время алгоритм ум­ножения элементов поля GF (2^k) основан на применении опе­раций логарифмирования и антилогарифмирования в полях GF (2^k) [4, 6].

Рис. 6.10. Функциональная схема ум­ножения произвольного элемента аⁱ поля GF(2⁴) на константу a⁵

Если некоторый элемент поля β=aⁱ принадлежит полю GF(2^k), то логарифм элемента β по основанию a€GF (2^k) есть показатель степени i, а именно: Log β = log aⁱ=i, i≥0. Тогда, умножение aⁱa^j= a^m может быть реализовано по сле­дующему алгоритму, представленному на рис. 6.11.

Рис. 6.11. Структурная схема умножителя произволь­ных элементов аⁱ и а^j в поле GF(2^k) с использо­ванием логарифмировании и антилогарифмирования

Особенностью данного алгоритма является то, что комби­нациям из k нулей или k единиц на выходе арифметического сумматора должно соответствовать появление на выходе ан-тилогарифматора одинакового элемента, а именно а⁰ = 1.

Логарифмирование и антилогарифмирование реализуется чаще всего табличным способом.

6.4.2. Деление элементов поля

В теории циклических кодов часто встречающейся операцией является деление произвольного элемента aⁱна некоторый эле­мент a^j, где aⁱ, aⁱ€ GF (2^k). Вместе с тем на практике деле­ние элементов заменяется умножением элемента aⁱ на a^-j, т. е.

где a^-j —элемент поля, обратный элементу а^j. Напомним, что для любого элемента а^j в поле GF (2^k) всегда существует и обратный ему a^-j, которые связаны равенством a^ja^-j= 1. Та­ким образом, реализация деления осуществляется по той же схеме, что и умножение (рис. 6.9) с той разницей, что один из сомножителей является обратным элементом a^-j. Рассмот­рим способы обращения элементов поля GF(2^k).

Один из способов основан на свойстве полей Галуа, кото­рое заключается в том, что ненулевые элементы поля GF (2^k) образуют циклическую мильтипликативную группу порядка 2^k — 1, т. е. для любого ненулевого элемента а^j справедливо

равенство (а^j)^2k-1 = 1. Отсюда получается (а^j)^2k-2 =

= (a^J)^-1 = a^-j. Для вычисления (2^k —2)-й степени элемента β можем воспользоваться одним из следующих двух равенств:

(β)^2k-2={[(β²β)²β]²… β }²= β ^-1 (6.27)

Характерной особенностью равенства (6.26) является то, что обращение элемента β может быть реализовано аппарат­ным путем за один шаг (такт), тогда как равенство (6.27) мо­жет быть реализовано за (k —1) последовательных этапов. Вместе с тем реализация последнего значительно проще. На каждом этапе необходимо осуществить умножение текущего значения на β и возведение результата в квадрат. Если элементβ выразить через базисные элементы поля 1, а, а²,..., а^k-1 в виде β = а₀ +a₁a+a₂a²+…a_k-1a^k-1, то на основании свойств (1.4) и (1.5) возведение в квадрат в поле GF (2*) со­ответствует выражению

Тогда операцию возведения в квадрат в векторной форме мож­но записать

(a₀a₁a₂…a_k-1)[X] = (b₀b₁b₂…b_k-1),

где [X] — квадратная матрица k-го порядка, строки которой представляют собой двоичные векторы элементов поля

Пример. Построить матрицу [X]и схему возведения в квад­рат, если конечное поле GF (2⁴) образовано примитивным по­линомом Р (х) = 1+x+x⁴

Выразим элементы поля а⁰, а², а⁴, а⁶ через базис {1, а, а² а³} в виде аⁱ = с₀ + с₁а + с₂а² + c₃а³, где с€GF (2):

Из векторов (с0 с1 с2 с3) указанных элементов составим матрицу [X]:

Пусть элементу аⁱ соответствует вектор (а₀ а₁ а₂ а₃). Для возведения аⁱ в квадрат произведем умножение вектора (а₀ а₁ а₂ а₃) на матрицу [X]:

Логическая схема возведения в квадрат в поле GF (2⁴) с

образующим полиномом Р(х) = 1 + х +x⁴ представлена на рис. 6.12.

Для проверки возведем эле­мент а⁵ в квадрат. Так как a⁵ = a +а², то для получения элемента (а⁵)² выполним ум­ножение вектора элемента а⁵ на матрицу [X], т. е.

Рис. 6.12. Функциональная схе­ма

возведения в квадрат про­извольного элемента аⁱ в по­ло GF(2⁴)

Полученный вектор (1110)соответствует элементу (а⁵)² = a¹⁰ поля GF (2⁴).

Дата добавления: 2015-07-16