УказательРазделыОбозначенияАвторО проектеEnglish version


. Настоящий раздел поддерживается компанией


§

Вспомогательная страница к разделу ПОЛЯ ГАЛУА. Здесь приводится краткий алгоритм построения поля Галуа — для тех программистов, которые не хотят забивать свою оперативную память излишней математической теорией, а желают побыстрее добраться до клавиатуры.

§

Всё же немного математики потребуется: полиномы (делимость, неприводимость, алгоритм Евклида), матрицы (и некоммутативность операции их умножения), определители (не очень конструктивный аппарат при практических вычислениях, но такой наглядный!).


Поле Галуа GF(16) (версия для программистов)

Итак, поле \mathbf{GF}(16) cостоит из 16 элементов, которые мы будем обозначать малыми готическими буквами \mathfrak a,\mathfrak b, \mathfrak c,\dots Каждый из этих элементов — четырёхразрядная строка (вектор) \mathfrak a=(A_0,A_1,A_2,A_3) двоичных разрядов \{A_j\}_{j=0}^3 \subset \{0,1\}.

Операция сложения — поразрядная по модулю 2_{} (XOR):

\mathfrak a+\mathfrak b=(A_0,A_1,A_2,A_3)\oplus (B_0,B_1,B_2,B_3)=
=(A_0+B_0 \pmod {2},A_1+B_1 \pmod {2},\ A_2+B_2 \pmod {2},\ A_3+B_3 \pmod {2}) \ .

Сложнее определить операцию умножения. Прежде всего, мы хотим, чтобы результат умножения \mathfrak a и \mathfrak b был снова вектором из двоичных разрядов:

(A_0,A_1,A_2,A_3)\times (B_0,B_1,B_2,B_3)=(C_0,C_1,C_2,C_3) \in \mathbf{GF}(16) ;

т.е. множество \mathbf{GF}(16) должно быть замкнуто относительно операции умножения. Это требование сразу же блокирует желание прибегнуть к скалярному произведению. Векторное же произведение определено только для трехразрядных строк.

Умножение

Операцию умножения будем вводить «обходным манёвром», привлекая для этой цели аппарат полиномов. Берем пока произвольный полином f(x)=x^4+a_1x^3+a_2x^2+a_3x+a_4 с коэффициентами \{a_j\}_{j=1}^4 \subset \{0,1\}. Существенно, что степень полинома равна именно 4_{}. Каждому вектору поставим в соответствие также по полиному:

\begin{array}{lll} \mathfrak a &=(A_0,A_1,A_2,A_3) \mapsto & a(x)= A_0x^3+A_1x^2+A_2x+A_3, \\ \mathfrak b &= (B_0,B_1,B_2,B_3) \mapsto & b(x)= B_0x^3+B_1x^2+B_2x+B_3 \ . \end{array}

Перемножим эти полиномы. В результате получаем полином a(x)b(x) степени \le 6. Вычислим остаток от деления этого полинома на f_{}(x):

a(x)b(x)\equiv q(x)f(x) + \underbrace{{\tilde c}_0x^3+{\tilde c}_1x^2+{\tilde c}_2x+{\tilde c}_3}_{=r(x)} \ .

Здесь q_{}(x) обозначает частное от деления (и оно нас абсолютно не интересует), а вот как раз коэффициенты остатка r_{}(x) нам нужны. Заметим, что \deg r(x) \le 3, т.е. для задания этого полинома нужно определить 4_{} коэффициента. За счет того, что старший коэффициент полинома f_{}(x) равен 1_{}, коэффициенты r_{}(x) будут целыми числами: \{ {\tilde c}_j \}_{j=0}^3 \subset \mathbb Z (см. ЗДЕСЬ). Так вот, теперь мы рассматриваем эти коэффициенты по модулю 2_{}, т.е. заменяем четные — на 0_{}, а нечетные — на 1_{}. Результат —

\mathfrak c= (c_0,c_1,c_2,c_3)=({\tilde c}_0,{\tilde c}_1,{\tilde c}_2,{\tilde c}_3) \pmod{2}

и будем считать произведением элемента \mathfrak a на элемент \mathfrak b, записывая этот факт в виде \mathfrak c=\mathfrak a \times \mathfrak b.

П

Пример. Пусть \mathfrak a=(1,0,1,1), \mathfrak b=(0,1,1,1) и f(x)=x^4+x^3+x. Имеем, a(x)=x^3+x+1,\ b(x)=x^2+x+1 и

a(x)b(x) \equiv x^5+x^4+2\,x^3+2\,x^2+2\,x+1 \ .

Делим результат на f_{}(x):

\begin{array}{rrrrrrr|l} x^5&+ x^4 &+2x^3 &+2x^2 &+2x &+1 && x^4+x^3+x\\ x^{5}&+x^4&&+x^2&& && \overline{ x \quad } \\ \hline &&2\,x^3&+x^2&+2\,x&+1 \end{array} \qquad \Rightarrow
\Rightarrow \quad c(x)= 2\,x^3+x^2+2\,x+1 \Rightarrow \quad \mathfrak a \times \mathfrak b=(0,1,0,1) \ .

Заметим, что окончательный результат не изменится, если сразу после вычисления произведения a(x)b(x) мы осуществим приведение коэффициентов полинома по модулю 2_{}:

x^5+x^4+2\,x^3+2\,x^2+2\,x+1 \equiv x^5+x^4+1 \pmod{2} ,

и остаток от деления последнего полинома на f_{}(x) будет равен x^{2}+1.

§

Дальнейшие упрощения операции умножения по двойному модулю обсуждаются НИЖЕ.

Будем запись

u(x) \quad (\operatorname{modd} \ 2,f(x))

понимать в смысле, что мы вычисляем остаток от деления полинома u_{}(x) на полином f_{}(x) и во всех этих вычислениях коэффициенты «удерживаем с точностью до четности», т.е. по модулю 2_{}. Будем также говорить об этом остатке как об остатке по двойному модулю 2,f(x).

Если мы возьмем другой полином f_{}(x) четвертой степени, то результат умножения будет другим. Однако при любом выборе, операция умножения будет коммутативна: \mathfrak a \times \mathfrak b= \mathfrak b \times \mathfrak a — поскольку коммутативна операция умножения полиномов.

§

В дальнейшем для обозначения операции умножения я вместо \times_{} буду использовать или вообще обозначение опускать — как для обычных чисел.

Очевидно, что умножение любого элемента поля на нулевой элемент \mathfrak o=(0,0,0,0) даст снова нулевой элемент. Очевидно также, что при любом выборе полинома f_{}(x), элемент \mathfrak e=(0,0,0,1) будет играть роль единицы относительно умножения: \mathfrak e\cdot \mathfrak a = \mathfrak a \cdot \mathfrak e=\mathfrak a. Действительно, a(x)\cdot 1 \equiv a(x). Далее, рассмотрим операцию умножения на элемент (0,0,1,0).

a(x) \cdot x \equiv A_0x^4+A_1x^3+A_2x^2+A_3x \equiv
\equiv A_0f(x)+ (A_1+A_0a_1)x^3+(A_2+A_0a_2)x^2+(A_3+A_0a_3)x+A_0a_4 \quad \Rightarrow
\Rightarrow \quad \mathfrak (A_0,A_1,A_2,A_3) \cdot (0,0,1,0) = \left\{ \begin{array}{lr} (A_1,A_2,A_3,0) & npu \ A_0=0, \\ (A_1+a_1,A_2+a_2,A_3+a_3, a_4) \pmod{2} & npu \ A_0=1. \end{array} \right.

Иначе говоря, результатом умножения будет либо сдвиг разрядов вектора \mathfrak a влево, либо тот же сдвиг с прибавлением строки коэффициентов полинома f_{}.

?

Проверьте выполнимость свойства дистрибутивности: \mathfrak a (\mathfrak b+\mathfrak c)= \mathfrak a \mathfrak b+ \mathfrak a \mathfrak c.

Деление

Итак, с операцией умножения проблем не возникает. Хуже обстоит дело с операцией деления. Операция деления векторов нам неизвестна, но вот для полиномов операция деления имеется. Так, полином x^3+1 делится нацело на полином x+1:

\mathfrak a = x^3+1, \mathfrak b=x+1 \quad \Rightarrow \quad \mathfrak a / \mathfrak b = \frac{x^3+1}{x+1}=\frac{(x+1)(x^2-x+1)}{x+1} \equiv x^2-x+1 \equiv_{2} x^2+x+1 \ .

Таким образом, можно считать, что

(1,0,0,1)/(0,0,1,1)=(0,1,1,1) \ .

Заметим, что этот результат не будет зависеть от выбора полинома f_{}(x), задействованного в предыдущем пункте для введения операции умножения. К сожалению, распространение полиномиального деления на все возможные комбинации векторов сталкивается с проблемой: полином x^3+1 не делится нацело на x^2+1:

x^3+1\equiv x(x^2+1)+(x+1) \ .

Либо надо вводить операцию деления векторов «с остатком», либо… А чего, собственно, мы хотим от операции деления? — А хотим мы, чтобы она любой упорядоченной паре элементов \mathfrak a , \mathfrak b ставила в соответствие элемент \mathfrak c так, чтобы \mathfrak a= \mathfrak b \cdot \mathfrak c. Тут же выводится ограничение на выполнимость поставленного требования: \mathfrak b \ne \mathfrak o=(0,0,0,0). Итак, мы хотим, чтобы множество \mathbf{GF}(16) \setminus \mathfrak o было замкнуто относительно операции деления. Иными словами: хотим иметь аналог свойства делимости целых чисел (или полиномов) без остатка. В только что разобранном примере для пары \mathfrak a = (1,0,0,1), \mathfrak b = (0,0,1,1) это требование удалось удовлетворить, но мы хотим выполнения его и для переставленной пары: хотим иметь возможность разделить \mathfrak b на \mathfrak a — и в ответе иметь снова вектор!

Для решения этой задачи приходится обращаться к операции умножения, введенной в предыдущем пункте. Мы хотим найти элемент \mathfrak c_1, удовлетворяющий равенству \mathfrak b= \mathfrak a \cdot \mathfrak c_1. Операция умножения вводится посредством операции умножения по двойному модулю 2, f(x), где f_{}(x), выбирается, например, как в предыдущем пункте f(x)=x^4+x^3+x. Тогда полиномиальное представление \mathfrak c_1 можно попробовать искать методом неопределенных коэффициентов:

x+1 \equiv (x^3+1)(\hat c_0 x^3 +\hat c_1 x^2+\hat c_2 x+\hat c_3) \quad (\operatorname{modd} \ 2, x^4+x^3+x) \ .

Ну уж операция вычисления остатка от деления полинома на полином нам известна

x+1 \equiv (-\hat c_0+\hat c_1-\hat c_2+ \hat c_3)\,x^3+\hat c_0\,x^2+(\hat c_1-\hat c_0)x+\hat c_3 \pmod {2} \ .

Полином, стоящий справа, совпадает с полиномом, стоящим слева при условии выполнения системы линейных сравнений:

0\equiv_{2}-\hat c_0+\hat c_1-\hat c_2+ \hat c_3, \ 0 \equiv_{2} \hat c_0,\ 1 \equiv_{2} \hat c_1-\hat c_0,\ 1 \equiv_{2} \hat c_3 \ .

Эта система оказывается совместной и имеет единственное решение: \hat c_0 =0, \hat c_1=1, \hat c_2=0, \hat c_3=1. Таким образом:

(0,0,1,1)/(1,0,0,1)=(0,1,0,1) \ .

Сработает ли подобная схема рассуждений для произвольных элементов \mathfrak a и \mathfrak b? — Не обязательно! Возьмем \mathfrak a = (0,0,1,1), \mathfrak b=(0,0,1,0). Применение метода неопределенных коэффициентов приведет к несовместной системе сравнений. Почему это произошло? Какое условие на выбор полинома f_{}(x) гарантирует нам выполнимость операции деления для произвольных элементов поля (исключая деление на нулевой элемент)?

Для ответа на эти вопросы сведем задачу к более простой: нам, фактически, необходимо выполнять операцию нахождения обратного к элементу \mathfrak a относительно операции умножения: \mathfrak a^{-1} для \forall \mathfrak a \ne \mathfrak o. Переведем эту задачу на язык полиномов:

1 \equiv \tilde c(x) a(x) \quad (\operatorname{modd} \ 2, f(x))

что эквивалентно

1 \equiv_{2} \tilde c(x) a(x)+ q(x) f(x) \ ;

при некотором полиноме q_{}(x). Последнее соотношение требует пояснения. Оно представляет собой не просто сравнение по модулю 2_{}, оно представляет собой полиномиальное тождество: полином слева, тождественно равный 1_{}, должен быть равен полиному справа. Следовательно, коэффициенты при одинаковых степенях x_{} у этих полиномов должны быть одинаковыми.

Для отыскания полинома f_{}(x), который удовлетворяет условию c(x) a(x)+ q(x) f(x) \equiv_{2} 1 для любого полинома a(x)\not\equiv 0, \deg a(x)\le 3, обратимся к теории полиномов над бесконечными полями — т.е. полиномов с коэффициентами из \mathbb R_{} или \mathbb C_{}. Для таких полиномов тождество c(x) a(x)+ q(x) f(x) \equiv 1 известно как тождество Безу. Оно будет иметь место тогда и только тогда, когда полиномы f_{}(x) и a_{}(x) взаимно просты, т.е. когда их наибольший общий делитель тождественно равен 1_{}: \operatorname{HOD}(f(x),a(x)) \equiv 1. Если же мы требуем выполнения последнего условия для любого полинома a(x)\not\equiv 0, \deg a < \deg f, то это требование приводит к свойству полинома f_{}(x), известному под названием неприводимость над полем \mathbb R_{} или \mathbb C_{}. Оно означает, что полином f_{}(x) не делится нацело ни на какой из полиномов меньшей степени, отличный от константы. Так, полином f(x)=x^4+x^3+x, очевидно, не является неприводимым над \mathbb R_{} и над \mathbb C_{} :

f(x)\equiv x(x^3+x^2+1) ;

чем, собственно, и объясняется неудача при попытке использовать этот полином для генерации операции деления в поле \mathbf{GF}(16). Элементу поля \mathfrak b=(0,0,1,0) соответствует полином b(x)\equiv x, но тождеству c(x) b(x)+ q(x) f(x) \equiv 1 не удастся удовлетворить ни при каком выборе полиномов c_{}(x) и q_{}(x), поскольку — при любом выборе этих полиномов — полином, стоящий в тождестве слева, делится на x_{}, а справа — на x_{} не делится.

Идем дальше. Свойство неприводимости полинома определяется в зависимости от того множества, над которым мы рассматриваем полином. Если мы имеем дело с полиномами, коэффициенты которых являются целыми числами, и результат операции деления также хотим иметь целочисленным, то неприводимость следует рассматривать над множеством \mathbb Z_{}. Полиномы, неприводимые над множеством \mathbb Z_{} можно отыскать, их достаточно много — даже, если мы дополнительно потребуем требуем, чтобы их коэффициенты были из множества \{0,1\}. Вот примеры таких полиномов степени 4_{}:

x^4+1,\ x^4+x+1,\ x^4+x^3+1,\ x^4+x^3+x^2+1;

но вот полиномы

x^4+x^3+x+1,\ x^4+x^2+1,\ x^4+x

оказываются приводимыми над \mathbb Z_{}.

Итак, свойство неприводимости полинома f_{}(x) для порождения поля с замкнутостью относительно операции деления является необходимым. Тем не менее, оно не является достаточным. Причина этого заключается в том, что мы накладываем дополнительное условие на коэффициенты рассматриваемых полиномов — все они равны 0_{} или 1_{}. И тождество Безу следует рассматривать по модулю 2_{}. Иными словами, полином f_{}(x) может быть неприводимым над \mathbb Z_{}, но выполнения тождества

c(x) a(x)+ q(x) f(x) \equiv 1

не удастся добиться ни при каких c_{}(x) и q_{}(x) если мы все коэффициенты полинома слева усечем по модулю 2_{}. Так, к примеру, для пары полиномов f(x)=x^4+1, a(x)=x+1 последнее тождество не будет выполнено: при подстановке x=1 получим 2\,c(x)+2\, q(x) \equiv_2 0, а не 1_{}, как мы желали бы.

Поэтому из множества неприводимых над \mathbb Z_{} полиномов степени 4_{} с коэффициентами 0_{}^{} или 1_{}, мы должны выбрать полиномы, дополнительно неприводимые по модулю 2_{}. Из приведенных выше примеров неприводимых над \mathbb Z полиномов, приходится отбрасывать следующие:

x^4+1 \equiv_{2} (x^2+1)^2 \equiv_{2} (x+1)^4,\ x^4+x^3+x^2+1 \equiv_{2} (x+1)(x^3+x+1) \ .

Тотальным перебором можно убедиться, что существует всего только 3_{} полинома степени 4_{} неприводимых по модулю 2_{}:

x^4+x+1,\ x^4+x^3+1,\ x^4+x^3+x^2+x+1 \ .

§

Доказывается, что существуют неприводимые полиномы любой степени; для каждой степени известно их количество. Отдельная проблема — построение этих полиномов достаточно больших степеней ( 64, 128 и т.п.) Пока можно оценить сложность задачи на примере нахождения таких полиномов 6_{}-й степени ЗДЕСЬ, а общие подходы попозже опишу. Причем с точки зрения приложений в теории помехоустойчивого кодирования, интерес представляют разреженные неприводимые полиномы, т.е. полиномы с большим количеством нулевых коэффициентов. См. примеры таких полиномов ЗДЕСЬ.


Построение поля \mathbf{GF}(16) завершено. Операция деления в этом поле будет определена, если порождающим полиномом для определения операции умножения выбрать любой из трех приведенных выше. Осталось только привести алгоритм вычисления частного. Поскольку операция деления \mathfrak b / \mathfrak a сводится к операции умножения \mathfrak b \cdot \mathfrak a^{-1}, то возвращаемся к тождеству Безу, которое и позволило нам ввести операцию нахождения

(A_0x^3+A_1x^2+A_2x+A_3)^{-1} \quad (\operatorname{modd} \ 2, f(x)) \ .

Имеются различные алгоритмы решения этого тождества. Они абсолютно конструктивны, но, к сожалению, громоздки в изложении. Самый главный из них основан на алгоритме Евклида вычисления наибольшего общего делителя полиномов f_{}(x) и a_{}(x). Собственно сам \operatorname{HOD} (f(x),A_0x^3+A_1x^2+A_2x+A_3) нас не интересует: при любых значениях коэффициентов \{A_j\}_{j=0}^3 он будет равен 1_{}. Откуда такая уверенность? — Она вытекает из неприводимости полинома f_{}(x). А интересуют нас выражения для частных из алгоритма Евклида вычисления этого (уже предсказанного) \operatorname{HOD}.

П

Пример. Для f(x)=x^4+x+1, a(x)=x^3+x+1 имеем:

\left. \begin{array}{lcl} f(x) &\equiv & x\cdot a(x) + (x^2+1); \\ a(x) &\equiv & x \cdot (x^2+1)+ 1 \end{array} \right\} \pmod{2}

Единица в последней формуле и представляет значение \operatorname{HOD} (f(x),a(x)). На основании получившихся частных:

q_1(x)=x,\ q_2(x)=x,

составляем континуанту:

b(x)= q_1q_2+1=x\cdot x +1 \equiv_{_2} x^2+1 \ .

Проверяем:

(x^3+x+1)(x^2+1) \equiv x^5+2\,x^3+x^2+x+1 \equiv 1 \quad (\operatorname{modd} \ 2,f(x)) \ .

Итак, обратный к элементу поля \mathfrak a=(1,0,1,1) относительно умножения по двойному модулю равен (0,1,0,1).

Этот элемент определяется единственным образом. Если хочется получить универсальное его представление — для произвольного \mathfrak a= (A_0,A_1,A_2,A_3) и произвольного f(x)=x^4+a_1x^3+a_2x^2+a_3x+a_4, а континуанта кажется слишком сложным объектом, могу предложить альтернативную форму записи — посредством определителя:

b(x)= \left|\begin{array}{ccccccl} 1&a_1&a_2&a_3&a_4& & \\ &1&a_1&a_2&a_3&a_4&\\ &&1&a_1&a_2&a_3&0\\ &&&A_0&A_1&A_2&1\\ &&A_0&A_1&A_2&A_3&x\\ &A_0&A_1&A_2&A_3&0&x^2\\ A_0&A_1&A_2&A_3&0&0&x^3 \end{array}\right|_{7\times 7} \pmod{2} ,

(все неуказанные элементы считаются равными нулю). Разложите определитель по последнему столбцу — миноры 6_{}-го порядка, соответствующие x^3,x^2,x,1 и будут формировать \mathfrak a^{-1}.

Слишком велик порядок определителя? — Уменьшим его до порядка равного \deg f_{}. Вычисляем

a(x),\ x\cdot a(x),\ x^2 \cdot a(x),\ x^3 \cdot a(x) \quad (\operatorname{modd} \ 2,f(x)) \ ,

что можно организовать рекурсивно, положив a_0(x)\equiv a(x)= A_0x^3+A_1x^2+A_2x+A_3:

\left. \begin{array}{lll} a_1(x)\equiv x a_0(x) & \equiv & K_0x^3+K_1x^2+K_2x+K_3,\\ a_2(x)\equiv x a_1(x) & \equiv & L_0x^3+L_1x^2+L_2x+L_3 ,\\ a_3(x)\equiv x a_2(x) & \equiv & M_0x^3+M_1x^2+M_2x+M_3 \ , \end{array} \right\} \quad (\operatorname{modd} \ 2,f(x)) \ .

Составляем из коэффициентов полиномов \{a_j(x) \}_{j=0}^3 матрицу 4_{}-го порядка:

\mathbf{A}= \left(\begin{array}{llll} M_0 & M_1 & M_2 & M_3 \\ L_0 & L_1 & L_2 & L_3 \\ K_0 & K_1 & K_2 & K_3 \\ A_0 & A_1 & A_2 & A_3 \end{array} \right)

заменяем последний столбец на [x^3,x^2,x,1]^{\top}. Вычислим определитель — он и будет искомым полиномом. Так, для настоящего примера имеем:

\mathfrak a=a_0(x)=x^3+x+1,\ a_1(x)=x^2+1,\ a_2(x)=x^3+x,\ a_3(x)=x^2+x+1

и

\mathfrak a^{-1}= \left|\begin{array}{cccl} 0 & 1 & 1 & x^3 \\ 1 & 0 & 1 & x^2 \\ 0 & 1 & 0 & x \\ 1 & 0 & 1 & 1 \end{array} \right| \pmod{2} .

§

Матрица \mathbf A_{} из последнего примера снова возникнет в одном из последующих ПУНКТОВ.

§

Подведем итог: в конечном поле \mathbf{GF}(16) операцию умножения можно ввести тремя разными способами — в зависимости от выбора неприводимого по модулю 2_{} полинома 4_{}-й степени. Назовем этот полином порождающим полиномом поля. В дальнейшем, в настоящем разделе, говоря о неприводимом полиноме, будем иметь в виду именно свойство неприводимости по модулю 2_{}.

Имеется ли принципиальное различие между тремя полями, порождаемыми тремя неприводимыми полиномами? — Оказывается, нет. Можно доказать, что поля Галуа одного порядка все изоморфны, т.е. между любыми двумя такими полями можно установить взаимно-однозначное соответствие их элементов и при этом соответствие такое, что будут сохраняться результаты операций сложения и умножения. Проверку этого утверждения для \mathbf{GF}(16) см. ЗДЕСЬ.

П

Пример. Для поля \mathbf{GF}(16), порожденного полиномом f(x)=x^4+x+1, определить частное от деления элемента \mathfrak b = (0,0,1,1) на элемент \mathfrak a= (1,1,1,1).

Решение. Здесь a(x)=x^3+x^2+x+1, b(x)=x+1. Имеем: тождество Безу

u(x)a(x)+v(x) f(x) \equiv 1

(по модулю 2_{}) будет выполнено при u(x)=x^3, v(x)=... Таким образом,

a^{-1}(x) \quad (\operatorname{modd} \ 2,f(x)) = x^3

и

b(x) a^{-1}(x) \quad (\operatorname{modd} \ 2,f(x)) = x^3+x+1 \ \Rightarrow \ \mathfrak c= \mathfrak b / \mathfrak a = (1,0,1,1) .

Возведение в степень

Итак, с операцией умножения разобрались. Почти разобрались. — Дело в том, что имеется один неожиданный момент, который не имеет аналогов в теории полиномов над бесконечными полями. Рассмотрим произвольный элемент \mathfrak a \ne \mathfrak o поля и начнем возводить его в степени:

\mathfrak a^{0}=\mathfrak e, \mathfrak a^{1}, \mathfrak a^2,\dots

Все элементы этой последовательности будут элементами поля \mathbf{GF}(16). Но, поскольку последних — конечное число, то последовательность через некоторое количество шагов должна выйти на цикл.

П

Пример. Для f(x)=x^4+x+1 имеем:

\begin{array}{ll} npu \quad a(x)=x^3+x+1: & 1,\ x^3+x+1,\ x^3+1, x^3+x^2,\ x^3+x^2+1,\ x^2+x,\ x^3+x^2+x+1, \\ & x+1,\ x^3+x^2+x,\ x^3,\ x^2+x+1,\ x^2,\ x^3+x,\ x,\ x^2+1,\ 1,\dots \\ npu \quad a(x)=x^2+x+1: & 1,\ x^2+x+1,\ x^2+x,\ 1,\dots \\ npu \quad a(x)=x^3+x: & 1,\ x^3+x,\ x^3,\ x^3+x^2+x+1,\ x^3+x^2,\ 1,\dots \end{array}

Можно проверить, что для любого элемента поля (кроме единичного) его степени будут периодическими последовательностями с длинами циклов равными одному из чисел \{3,5,15\}. Что это за числа? — Это делители числа 2^4-1.

Это — проявление общего правила для конечного поля. Поскольку оно (после выбрасывания нулевого элемента) образует группу относительно умножения, то порядок этой группы должен делиться на порядок любого ее элемента. Гарантированно будет выполнено равенство

\mathfrak a^{15}=\mathfrak e \quad npu \quad \forall a \ne \mathfrak o \ ,

(в общем случае известное под названием обобщенной теоремы Ферма ). Нас будет очень интересовать порождающий элемент этой группы — тот, степени которого пробегают по всем ненулевым элементам поля. Этот элемент называется примитивным элементом поля. Доказывается, что эти элементы всегда существуют, известно их число — и это число не зависит от выбора полинома f_{}(x). Так, для поля \mathbf{GF}(16) число примитивных элементов равно \phi(15)= 8; здесь \phi_{} обозначает функцию Эйлера. В приведенном выше примере элемент (1,0,1,1) будет примитивным, а элементы (0,1,1,1) или (1,0,1,0) примитивными не будут.

!

Выражения для примитивных элементов будут зависеть от выбора порождающего поле полинома f_{}(x).

Обозначим какой-то из этих примитивных элементов через \mathfrak A. Для заданного элемента \mathfrak a \ne \mathfrak o поля найдем минимально возможный показатель степени k \in \mathbb N такой, что \mathfrak A^k= \mathfrak a. Этот показатель k_{} называют дискретным логарифмом элемента \mathfrak a по основанию примитивного элемента \mathfrak A. Плохо только, что, в отличие от своего непрерывного аналога, дискретный логарифм ведет себя совершенно хаотичным образом и выписать его выражение в общем виде — т.е. в виде явной функции разрядов элемента \mathfrak a=(A_0,A_1,A_2,A_3) весьма затруднительно.

П

Пример. f(x)=x^4+x+1. Через \mathfrak A обозначен элемент поля (0,0,1,0)=x.


"Таблица логарифмов".

\begin{array}{l|rrrr|c|c|c} \mathfrak A^0 & & & & \mathfrak e & 0001 & & \\ \mathfrak A^1 & & & \mathfrak A & & 0010 & \Pi & f=0 \\ \mathfrak A^2 & & \mathfrak A^2 & & & 0100 & \Pi & f=0 \\ \mathfrak A^3 & \mathfrak A^3 & & & & 1000 & & f_3=0 \\ \hline \mathfrak A^4 & & & \mathfrak A & +\mathfrak e & 0011 & \Pi & f=0 \\ \mathfrak A^5 & & \mathfrak A^2 & +\mathfrak A & & 0110 & & f_4=0 \\ \mathfrak A^6 & \mathfrak A^3 & +\mathfrak A^2 & & & 1100 & & f_3=0\\ \mathfrak A^7 & \mathfrak A^3 & & + \mathfrak A & +\mathfrak e & 1011 & \Pi & f^{\ast}=0 \\ \hline \mathfrak A^8 & & \mathfrak A^2 & & +\mathfrak e & 0101 & \Pi & f=0 \\ \mathfrak A^9 & \mathfrak A^3 & & +\mathfrak A & & 1010 & & f_3=0 \\ \mathfrak A^{10} & & \mathfrak A^2 &+\mathfrak A & +\mathfrak e & 0111 & & f_4=0 \\ \mathfrak A^{11} & \mathfrak A^3 & +\mathfrak A^2 & +\mathfrak A & & 1110 & \Pi & f^{\ast}=0 \\ \hline \mathfrak A^{12} & \mathfrak A^3 & +\mathfrak A^2 & + \mathfrak A& +\mathfrak e & 1111 & & f_3=0 \\ \mathfrak A^{13} & \mathfrak A^3 & +\mathfrak A^2 & & +\mathfrak e & 1101 & \Pi & f^{\ast}=0 \\ \mathfrak A^{14} & \mathfrak A^3 & & & +\mathfrak e & 1001 & \Pi & f^{\ast}=0 \end{array}

Обоснование таблицы ЗДЕСЬ.


Получается, что действительно, \mathfrak A=x является примитивным элементом поля. В четвертом столбце отмечены все примитивные элементы поля. На последний столбец пока не обращаем внимания. Удивительно то, что элементы второго столбца таблицы не изменятся, если взять в качестве \mathfrak A любой из элементов x^2, x^4, x^8.

Поскольку это поле часто использую для иллюстраций, приведу еще одну таблицу — для степенных представлений элементов:


"Таблица сложения".

\begin{array}{l||l|l|l|l|l|l|l|l|l|l|l|l|l|l|l} & \mathfrak A^0 & \mathfrak A^1 & \mathfrak A^2 & \mathfrak A^3 & \mathfrak A^4 & \mathfrak A^5 & \mathfrak A^6 & \mathfrak A^7 & \mathfrak A^8 & \mathfrak A^9 & \mathfrak A^{10} & \mathfrak A^{11} & \mathfrak A^{12} & \mathfrak A^{13} & \mathfrak A^{14} \\ \hline \hline \mathfrak A^0 & \mathfrak o & \mathfrak A^4 & \mathfrak A^8 & \mathfrak A^{14} & \mathfrak A & \mathfrak A^{10} & \mathfrak A^{13} & \mathfrak A^{9} & \mathfrak A^{2} & \mathfrak A^{7} & \mathfrak A^{5} & \mathfrak A^{12} & \mathfrak A^{11} & \mathfrak A^{6} & \mathfrak A^{3} \\ \hline \mathfrak A^1 & & \mathfrak o & \mathfrak A^5 & \mathfrak A^9 & \mathfrak A^0 & \mathfrak A^2 & \mathfrak A^{11} & \mathfrak A^{14} & \mathfrak A^{10} & \mathfrak A^{3} & \mathfrak A^{8} & \mathfrak A^{6} & \mathfrak A^{13} & \mathfrak A^{12} & \mathfrak A^{7} \\ \hline \mathfrak A^2 & & & \mathfrak o & \mathfrak A^{6} & \mathfrak A^{10} & \mathfrak A^{1} & \mathfrak A^{3} & \mathfrak A^{12} & \mathfrak A^0 & \mathfrak A^{11} & \mathfrak A^{4} & \mathfrak A^{9} & \mathfrak A^{7} & \mathfrak A^{14} & \mathfrak A^{13} \\ \hline \mathfrak A^3 & & & & \mathfrak o & \mathfrak A^{7} & \mathfrak A^{11} & \mathfrak A^{2} & \mathfrak A^{4} & \mathfrak A^{13} & \mathfrak A^{1} & \mathfrak A^{12} & \mathfrak A^{5} & \mathfrak A^{10} & \mathfrak A^{8} & \mathfrak A^0 \\ \hline \mathfrak A^4 & & & & & \mathfrak o & \mathfrak A^8 & \mathfrak A^{12} & \mathfrak A^3 & \mathfrak A^5 & \mathfrak A^{14} & \mathfrak A^2 & \mathfrak A^{13} & \mathfrak A^6 & \mathfrak A^{11} & \mathfrak A^9 \\ \hline \mathfrak A^5 & & & & & & \mathfrak o & \mathfrak A^9 & \mathfrak A^{13} & \mathfrak A^4 & \mathfrak A^6 & \mathfrak A^0 & \mathfrak A^3 & \mathfrak A^{14} & \mathfrak A^7 & \mathfrak A^{12} \\ \hline \mathfrak A^6 & & & & & & & \mathfrak o & \mathfrak A^{10} & \mathfrak A^{14} & \mathfrak A^{5} & \mathfrak A^{7} & \mathfrak A & \mathfrak A^{4} & \mathfrak A^{0} & \mathfrak A^{8} \\ \hline \mathfrak A^7 & & & & & & & & \mathfrak o & \mathfrak A^{11} & \mathfrak A^0 & \mathfrak A^{6} & \mathfrak A^{8} & \mathfrak A^2 & \mathfrak A^{5} & \mathfrak A \\ \hline \mathfrak A^8 & & & & & & & & & \mathfrak o & \mathfrak A^{12} & \mathfrak A & \mathfrak A^{7} & \mathfrak A^{9} & \mathfrak A^{3} & \mathfrak A^{6} \\ \hline \mathfrak A^9 & & & & & & & & & & \mathfrak o & \mathfrak A^{13} & \mathfrak A^{2} & \mathfrak A^{8} & \mathfrak A^{10} & \mathfrak A^{4} \\ \hline \mathfrak A^{10} & & & & & & & & & & & \mathfrak o & \mathfrak A^{14} & \mathfrak A^{3} & \mathfrak A^{9} & \mathfrak A^{11} \\ \hline \mathfrak A^{11} & & & & & & & & & & & & \mathfrak o & \mathfrak A^0 & \mathfrak A^{4} & \mathfrak A^{10} \\ \hline \mathfrak A^{12} & & & & & & & & & & & & & \mathfrak o & \mathfrak A^{1} & \mathfrak A^{5} \\ \hline \mathfrak A^{13} & & & & & & & & & & & & & & \mathfrak o & \mathfrak A^{2} \\ \hline \mathfrak A^{14} & & & & & & & & & & & & & & & \mathfrak o \end{array}


§

Беглый взгляд на обе приведенные таблицы вызывает ощущение хаотичности их формирования. В самом деле, для обычного (классического) логарифма по произвольному основанию, например \log_{2} a, имеет место хотя бы непрерывность по a_{}: если значение \log_{2} a известно, то \log_{2}(a+1) находится «где-то рядом». Для дискретного логарифма этой предсказуемости в помине нет. И в этом заключается основная проблема использования аппарата дискретных логарифмов.

Подводя итоги: любой ненулевой элемент поля \mathbf{GF}(16) имеет три представления (ипостаси1)):

1. Это — строка, элемент векторного пространства (A_0, A_1, A_2, A_3).

2. Это — полином A_0x^3+ A_1x^2+A_2x+ A_3.

3. Это — некоторая степень \mathfrak A^k примитивного элемента поля.

Какое из этих представлений использовать — зависит от конкретной задачи. Так, складывать проще элементы поля в их представлении в виде 1 или 2 (в сравнении с альтернативным вариантом, представленным последней таблицей). С другой стороны, если известна таблица представлений любого элемента (A_0, A_1, A_2, A_3) поля по степеням примитивного (типа первой из приведенных в последнем примере), то операцию умножения кажется проще выполнять с элементами поля в виде 3 :

\quad \mathfrak a= (A_0, A_1, A_2, A_3) = \mathfrak A^k,\ \mathfrak b= (B_0, B_1, B_2, B_3) = \mathfrak A^{\ell} \quad \Rightarrow \quad \mathfrak a \cdot \mathfrak b = \mathfrak A^{k+\ell} \ .

Показатель k+\ell берется «честно» при k+\ell<15 и по модулю 15_{} при k+\ell\ge 15.

§

Замечание для тех, кто заканчивал школу «во времена далёкие, уже почти забытые»: принцип работы тот же, что и при работе с таблицами логарифмов Брадиса.

П

Пример. Разберем еще раз алгоритм умножения элементов \mathfrak a=(A_0,A_1,A_2,A_3) и \mathfrak b=(1,1,0,1) при f(x)=x^4+x+1.

Решение 1 . Умножение соответствующих полиномов a(x)=A_0x^3+A_1x^2+A_2x+A_3 и b(x)=x^3+x^2+1 традиционно производится «в столбик»:

Фактически, за счет того, что разрядами элемента \mathfrak b являются либо 0_{}, либо 1_{}, умножение сводится к действию исключительно только со строкой (A_0,A_1,A_2,A_3) — она может быть «сдвинута» на одну или более позиций влево по отношению к предыдущей строке. Стоящие друг под другом разряды суммируются по модулю 2_{} (без переноса результата в следующий разряд2)). Заметим, что полученный результат — произведение полиномов a(x) b(x) — еще не является окончательным, поскольку конечной целью является остаток от деления этого произведения на f_{}(x) (по модулю 2_{}). Исходя из этой цели, имеет смысл организовать умножение по другой схеме:

a(x)(B_0x^3+B_1x^2+B_2x+B_3)= (a(x)B_0)x^3+(a(x)B_1)x^2+(a(x)B_2)x+(a(x)B_3)=
=\left\{\left[\left(a(x)B_0 \right)\cdot x +a(x)B_1 \right]\cdot x+a(x)B_2 \right\}\cdot x+a(x)B_3
=\left\{\left[\left(a(x)\cdot x\right) + a(x) \right]\cdot x+0 \right\}\cdot x+a(x) \ ,

а результат каждой последовательно вычисленной операции \big( \ast \big)\cdot x, \big[ \ast \big]\cdot x, \big\{ \ast \big\}\cdot x «усекать» по модулю 2,f(x):

a(x) b(x) \quad (\operatorname{modd} \ 2,f(x)) =
= \left\{\left[\left(a(x)\cdot x \quad (\operatorname{modd} \ 2,f(x)) \right) + a(x) \right]\cdot x \quad (\operatorname{modd} \ 2,f(x)) \right\}\cdot x \quad (\operatorname{modd} \ 2,f(x)) +a(x) \ .

Тем более, что операция умножения на полином x_{} по двойному модулю 2,f(x) допускает простую программную реализацию (см. концовку пункта УМНОЖЕНИЕ ).

?

Вопрос для тех, кто у меня учился: вам ничего этот алгоритм не напоминает?

Решение 2 . Тот же самый пример решим с помощью таблицы из предыдущего примера. Итак, \mathfrak b=(1,1,0,1)= \mathfrak A^{13}; аналогичное представление для элемента \mathfrak a можно получить только при конкретном его выборе. Пусть, к примеру, \mathfrak a=(1,0,1,1). Тогда \mathfrak a = \mathfrak A^{7}. Имеем, следовательно,

\mathfrak a \cdot \mathfrak b=\mathfrak A^{7}\cdot \mathfrak A^{13}=\mathfrak A^{20}=\mathfrak A^{5} \ ,

и, снова подсмотрев в таблицу, получаем (0,1,1,0).

А как упрощается для степенного представления элемента его обращение! ^_^ — В самом деле:

\mathfrak a^{15} = \mathfrak e \quad \Rightarrow \quad \mathfrak a^{-1}=\mathfrak a^{14},\ \mathfrak a^{-2}=\mathfrak a^{13},\dots \quad npu \quad \forall \mathfrak a \ne \mathfrak o \ .

Словом, наличие заранее вычисленной «таблицы логарифмов» существенно упрощает жизнь вычислителю. Хуже, если такой таблицы нет или вычисление (хранение) ее слишком затратно…

П

Пример. Здесь для иллюстрации возьму поле побольше3) \mathbf{GF}(64). Вычислить x^{-11} \quad (\operatorname{modd} \ 2,x^6+x^5+1).

Решение. Полином f_{}(x)=x^6+x^5+1 — неприводимый, а x_{} — примитивный элемент поля \mathbf{GF}(64) (см. ЗДЕСЬ ), по обобщенной теореме Ферма имеем x^{-11} \equiv x^{2^6-1-11}\equiv x^{52} \quad (\operatorname{modd} \ 2,x^6+x^5+1). Далее используем идею алгоритма квадрирования-умножения: переводим 52 в двоичную систему счисления \underline{52}_{_{10}}=\underline{110100}_{_2} и начинаем вычислять остатки

\begin{array}{|c|c|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 & 5 &6 \\ \hline 52 & 1 & 1 & 0 & 1 & 0 &0 \\ \hline r_j(x) & x & x^2\times x & x^6 & (x^5+1)^2\times x & (x^4+x^3+x^2+1)^2 & (x^4+x^2+x+1)^2 \\ & \equiv_{_{2,f}} x & \equiv_{_{2,f}} x^3 & \equiv_{_{2,f}} x^5+1 & \equiv_{_{2,f}} x^4+x^3+x^2+1 & \equiv_{_{2,f}} x^4+x^2+x+1 & \equiv_{_{2,f}} x^5+x^4+x \\ \hline \end{array}

Ответ. x^5+x^4+x.

Уравнения линейные

Пусть заданы элементы поля \mathfrak a_1,\dots,\mathfrak a_N, \mathfrak b. Линейным уравнением над полем \mathbf{GF}(16) относительно неизвестных \mathfrak x_1,\dots,\mathfrak x_N назовем

\mathfrak a_1 \mathfrak x_1+\dots+\mathfrak a_N \mathfrak x_N = \mathfrak b \ .

Этот объект вполне определен, поскольку определена операция умножения. Решением уравнения в поле \mathbf{GF}(16) назовем любой набор элементов из \mathbf{GF}(16)

\mathfrak x_1=\alpha_1,\dots, \mathfrak x_N=\alpha_N \ ,

обращающий уравнение в верное равенство.

Системой линейных уравнений над \mathbf{GF}(16) называется совокупность (набор) из нескольких уравнений от одного и того же набора переменных (неизвестных) \mathfrak x_1,\dots,\mathfrak x_N:

\left\{ \begin{array}{lllll} \mathfrak a_{11} \mathfrak x_1 &+\mathfrak a_{12}\mathfrak x_2&+ \ldots&+\mathfrak a_{1N}\mathfrak x_N &=\mathfrak b_1,\\ \mathfrak a_{21}\mathfrak x_1 &+\mathfrak a_{22}\mathfrak x_2&+ \ldots&+\mathfrak a_{2N}\mathfrak x_N &=\mathfrak b_2,\\ \dots & & & & \dots \\ \mathfrak a_{M1}\mathfrak x_1 &+\mathfrak a_{M2}\mathfrak x_2&+ \ldots&+\mathfrak a_{MN}\mathfrak x_N &=\mathfrak b_M. \end{array} \right.

Здесь \left\{\mathfrak a_{j k} \right\}_{j=1,\dots,M \atop k=1,\dots,N } и \{ \mathfrak b_{j} \}_{j=1,\dots,M} — фиксированные элементы поля \mathbf{GF}(16); они называются коэффициентами системы.

Посмотрим, насколько переносимы в конечное поле результаты, полученные для систем уравнений над бесконечными полями (\mathbb Q, \mathbb R_{} или \mathbb C_{}). Прежде всего, отметим, что один из сценариев, возможных для бесконечных полей, неактуален для полей конечных: система уравнений над конечным полем не может иметь бесконечного множества решений. Поэтому теоретически допустим способ решения системы линейных уравнений, заключающийся в простом переборе всех возможных комбинаций из 16_{} элементов поля. Так, для системы из двух уравнений от двух неизвестных

\left\{ \begin{array}{lcl} \mathfrak a_{11} \mathfrak x_1 +\mathfrak a_{12}\mathfrak x_2 &= & \mathfrak b_1, \\ \mathfrak a_{21} \mathfrak x_1 +\mathfrak a_{22}\mathfrak x_2 &= & \mathfrak b_2 \end{array} \right.

надо проверить 16^2 комбинаций (\mathfrak x_1,\mathfrak x_2). Отложив этот способ «про запас» — ввиду очевидной его неконструктивности, обратимся к другим, которые можно перенести из бесконечных полей.

Справедливы ли формулы Крамера? — Умножим первое уравнение системы на \mathfrak a_{22} и вычтем из него ( \equiv_{_2} прибавим к нему) второе, умноженное на \mathfrak a_{12}:

\overbrace{(\mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21})}^{\Delta}\mathfrak x_1= \overbrace{\mathfrak a_{22} \mathfrak b_1 - \mathfrak a_{12} \mathfrak b_2}^{\Delta_1} \ .

Аналогично:

(\mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21})\mathfrak x_2= \overbrace{-\mathfrak a_{21} \mathfrak b_1 + \mathfrak a_{11} \mathfrak b_2}^{\Delta_2} \ .

Если элемент поля \Delta= \mathfrak a_{11}\mathfrak a_{22}- \mathfrak a_{12} \mathfrak a_{21} отличен от нулевого, то у него существует обратный и, следовательно, решение системы уравнений единственно и оно записывается в виде

\mathfrak x_1=\Delta_1\cdot \Delta^{-1},\quad \mathfrak x_2=\Delta_2\cdot \Delta^{-1} \ .
П

Пример. Решить систему уравнений в поле \mathbf{GF}(16) с умножением, определенным по модулю 2,f(x)=x^4+x+1:

\left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(0,1,0,1)\mathfrak x_2 &= & (1,0,0,0), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,1,0). \end{array} \right.

Решение. Имеем4)

\Delta\equiv x^2(x+1)-(x^2+1)(x^3+x^2+x+1)\equiv x^3+x,
\Delta_1 \equiv x^3(x+1)-(x^3+x^2+x)(x^2+1) \equiv x^3,\quad \Delta_2 \equiv x^2(x^3+x^2+x)-(x^3+x^2+x+1)x^3 \equiv x^3+x^2 \ ,

и

\mathfrak x_1\equiv x^3(x^3+x)^{-1}\equiv x^3(x^3+x^2) \equiv x^3+x=(1,0,1,0), \quad \mathfrak x_2\equiv (x^3+x^2)(x^3+x)^{-1} \equiv x^3+x^2+x+1=(1,1,1,1) \ .

?

В поле предыдущего примера решить системы уравнений

\mathbf{a)} \left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(1,0,1,0)\mathfrak x_2 &= & (1,0,0,0), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,0,1); \end{array} \right. \qquad \mathbf{b)} \left\{ \begin{array}{lcl} (0,1,0,0) \mathfrak x_1 +(1,0,1,0)\mathfrak x_2 &= & (0,1,0,1), \\ (1,1,1,1) \mathfrak x_1 +(0,0,1,1)\mathfrak x_2 &= & (1,1,0,1). \end{array} \right.

Теперь можно ввести и аналог определителя — как полиномиальной функции элементов поля; существенным упрощением стандартного определения является то обстоятельство, что в разложении определителя с элементами из \mathbf{GF}(16) всем слагаемым можно приписывать одинаковый знак. Так, например, определитель третьего порядка введем формулой

\left| \begin{array}{lll} \mathfrak a_{11} & \mathfrak a_{12} & \mathfrak a_{13}\\ \mathfrak a_{21} & \mathfrak a_{22} & \mathfrak a_{23} \\ \mathfrak a_{31} & \mathfrak a_{32} & \mathfrak a_{33} \end{array} \right| =\mathfrak a_{11} \mathfrak a_{22} \mathfrak a_{33}+\mathfrak a_{12}\mathfrak a_{23} \mathfrak a_{31} + \mathfrak a_{21}\mathfrak a_{32} \mathfrak a_{13} + \mathfrak a_{31} \mathfrak a_{22} \mathfrak a_{13} + \mathfrak a_{21}\mathfrak a_{12}\mathfrak a_{33} + \mathfrak a_{11} \mathfrak a_{32} \mathfrak a_{23} \ .

А уж если ввели определитель, то самое время ввести понятие матрицы из элементов поля — хотя бы для того, чтобы иметь возможность выписать решение системы л.у. с помощью обратной матрицы. Но пока повременим с развитием этой идеи, а попробуем взглянуть на решение предыдущего примера альтернативным взглядом.

Рассмотрим подробнее операцию умножения элемента поля \mathfrak a_1= (0,1,0,0) на произвольный элемент \mathfrak x =(x_0,x_1,x_2,x_3) этого же поля5):

x^2(x_0x^3+x_1x^2+x_2x+x_3) \equiv x_0(x^2+x)+x_1(x+1)+x_2x^3+x_3x^2 \equiv x_2 x^3+(x_0+x_3)x^2+(x_0+x_1)x+x_1 \ .

Таким образом, умножение на (0,1,0,0) определяет отображение строк в поле \mathbf{GF}(16):

\mathfrak x=(x_0,x_1,x_2,x_3) \ \mapsto \ \mathfrak y =(x_2,x_0+x_3,x_0+x_1,x_1) \ .

Это отображение, очевидно, является линейным. Следовательно, его можно задать с помощью матрицы:

\mathfrak x \ \mapsto \ \mathfrak y=(x_0,x_1,x_2,x_3) \left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right) \ .
§

Способ записи этого отображения несколько непривычен в сравнении с традиционным — когда матрица умножается слева на столбец координат. Однако в теории кодирования больше любят действовать со строками, так что приходится перестраиваться… Не очень принципиально, один способ с другим связан операцией транспонирования.

Теперь рассмотрим умножение произвольного элемента \mathfrak x поля на другой элемент, например на \mathfrak a_2=(0,1,0,1). Соответствующая цепочка рассуждений приводит уже к другой матрице:

\mathfrak x \ \mapsto \ \mathfrak y=(x_0,x_1,x_2,x_3) \left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \ .

Теперь первое уравнение системы из предыдущего примера

(0,1,0,0) \mathfrak x_1 +(0,1,0,1)\mathfrak x_2 = (1,0,0,0)

также можно переписать в матричном виде если положить \mathfrak x_1=(x_{10},x_{11},x_{12},x_{13}), \mathfrak x_2=(x_{20},x_{21},x_{22},x_{23}) и использовать операцию поразрядного сложения по модулю 2_{} (XOR):

(x_{10},x_{11},x_{12},x_{13}) \underbrace{\left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right)}_{=\mathbf{A}_{11}} \oplus (x_{20},x_{21},x_{22},x_{23}) \underbrace{\left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right)}_{=\mathbf{A}_{12}} =(1,0,0,0) \ .

Вывод: линейное уравнение относительно 2_{}-х элементов поля \mathbf{GF}(16) эквивалентно системе из 4_{}-х линейных уравнений относительно 8_{}-ми неизвестных двоичных разрядов. Но если в первом случае уравнение понималось по двойному модулю 2,f(x), то во втором случае каждое из уравнений — это сравнение по одному только числовому модулю 2_{}; о подобных уравнениях будем говорить как об уравнениях над GF(2).

Второе уравнение системы перепишется в аналогичной форме:

(x_{10},x_{11},x_{12},x_{13}) \underbrace{\left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{21}} \oplus (x_{20},x_{21},x_{22},x_{23}) \underbrace{\left(\begin{array}{cccc} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{22}} =(1,1,1,0) \ ;

а вся система из 2_{}-х уравнений над \mathbf{GF}(16) эквивалентна системе из 8_{}-ми уравнений над \mathbf{GF}(2). Эта система записывается в блочной форме6):

\left\{ \begin{array}{lcl} \mathfrak x_1 \mathbf{A}_{11} +\mathfrak x_2 \mathbf{A}_{12}&= & \mathfrak b_1, \\ \mathfrak x_1\mathbf{A}_{21} + \mathfrak x_2 \mathbf{A}_{22} &= & \mathfrak b_2, \end{array} \right. \qquad \iff \qquad (\mathfrak x_1,\mathfrak x_2)_{1\times 8} \left( \begin{array}{ll} \mathbf A_{11} & \mathbf A_{21} \\ \mathbf A_{12} & \mathbf A_{22} \end{array} \right)_{8 \times 8}= (\mathfrak b_1,\mathfrak b_2)_{1\times 8} \ .

Мы хотим решить эту систему именно в таком разбиении 8_{}-миразрядной строки неизвестных на две составляющих компоненты \mathfrak x_1 и \mathfrak x_2. Попробуем сделать это с помощью матричного формализма, повторив ход решения системы из двух уравнений в поле \mathbf{GF}(16). Домножим первое уравнение системы справа на матрицу \mathbf A_{22}, второе уравнение системы — справа же на матрицу \mathbf A_{12}, и вычтем одно получившееся равенство из другого:

\mathfrak x_1 (\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})+ \mathfrak x_2 (\mathbf A_{12}\mathbf A_{22}- \mathbf A_{22}\mathbf A_{12}) =\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12} \ .

Матрица, стоящая коэффициентом при \mathfrak x_2, — нулевая, поскольку \mathbf A_{12}\mathbf A_{22}=\mathbf A_{22}\mathbf A_{12}… Стоп. Стоп! Умножение матриц — некоммутативно! Для произвольных квадратных матриц \mathbf A_{} и \mathbf B, как правило, не будет выполнено \mathbf A \mathbf B = \mathbf B \mathbf A! На всякий случай, всё же проверим7):

\mathbf A_{12}\mathbf A_{22}=\left(\begin{array}{cccc} 2 & 2 & 2 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)\equiv_{_2} \underbrace{\left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)}_{=\mathbf{A}_{21}} = \mathbf A_{22}\mathbf A_{12} \ .

А наши матрицы-то коммутируют! Более того, совершенно неожиданно результат умножения оказался соответствующим результату умножения элементов поля:

(0,1,0,1) \leftrightarrow \mathbf A_{12},\ (0,0,1,1) \leftrightarrow \mathbf A_{22} \quad \Rightarrow (0,1,0,1)\cdot (0,0,1,1)=(1,1,1,1) \leftrightarrow \mathbf A_{21} \ .

Проверяем свойство коммутативности умножения для всех построенных нами матриц: оно выполняется :!: Идем дальше. Если \mathbf A_{12}\mathbf A_{22}=\mathbf A_{22}\mathbf A_{12}, то можем корректно завершить наши рассуждения по решению системы уравнений, разбитой на блоки, с помощью матричного формализма:

\mathfrak x_1 (\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})=\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12} \quad \Rightarrow \quad \mathfrak x_1=(\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12})(\mathbf A_{11}\mathbf A_{22}- \mathbf A_{21}\mathbf A_{12})^{-1} \ .

Останавливаемся еще раз: где гарантия, что существует обратная матрица? Проверяем:

\left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right) \left(\begin{array}{cccc} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right)- \left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right) \left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right)\equiv_{_2} \overbrace{\left(\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)}^{= \mathbf A_{00}} \ .

Поскольку \det \mathbf A_{00}=-1\equiv_{2} +1, обратная матрица существует:

\mathbf A_{00}^{-1}= \left(\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right) \ .

Ну и последний шаг:

\mathfrak x_1=(\mathfrak b_1 \mathbf A_{22}- \mathfrak b_2 \mathbf A_{12})\mathbf A_{00}^{-1} =((1,0,1,1)-(0,0,1,1))\mathbf A_{00}^{-1}=(1,0,1,0) \ .

И этот результат совпадает с ответом примера.

Матрицы

Перевод формализма полей Галуа на язык матриц наводит на мысль о существовании более тесной связи между этими двумя объектами. Возникает подозрение, что поле Галуа \mathbf{GF}(16) изоморофно некоторому подмножеству квадратных матриц 4_{}-го порядка. Осталось только указать соответствие:

\mathfrak a=(A_0,A_1,A_2,A_3) \ \leftrightarrow \ a(x)=A_0x^3+A_1x^2+A_2x+A_3 \ \leftrightarrow \ \mathbf{A} \ ,

а потом установить, что оно сохраняет результаты сложения и умножения. Последняя строка матрицы \mathbf{A} угадывается из примеров — она совпадает со строкой \mathfrak a:

\mathbf{A}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ A_0& A_1 & A_2 & A_3 \end{array} \right) \ .

Что представляют собой остальные строки? — Это коэффициенты полиномов

a(x) x,\ a(x)x^2,\ a(x)x^3 \quad (\operatorname{modd} \ 2,x^4+x+1) ,

т.е. коэффициенты по модулю 2_{} остатков указанных полиномов от деления на полином f(x)=x^4+x+1. Эти коэффициенты расположены в матрице по схеме:

\begin{array}{ll} \mathbf{A}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ A_0& A_1 & A_2 & A_3 \end{array} \right) & \begin{array}{lc} \leftarrow a(x)x^3 & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x)x^2 & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x)x & (\operatorname{modd} \ 2,x^4+x+1) \\ \leftarrow a(x) & (\operatorname{modd} \ 2,x^4+x+1) \end{array} \\ { } \qquad \quad \ \uparrow \quad \ \ \uparrow \quad \ \ \uparrow \quad \ \uparrow & \\ { } \qquad \quad \ x^3 \quad \ x^2 \quad \ x \ \quad 1 & \end{array} \ .

Откуда возникает эта матрица? Разберем еще раз процедуру вычисления произведения полиномов по двойному модулю, несколько схем для которой были рассмотрены в ВЫШЕ. Пусть

a(x)=A_0x^3+A_1x^2+A_2x+A_3, \ B(x)=B_0x^3+B_1x^2+B_2x+B_3 \ .

Организуем вычисления a(x)b(x) \ (\operatorname{modd} \ 2,f(x)) по иной схеме:

\begin{array}{ll} a(x)b(x) \ (\operatorname{modd} \ 2,f(x)) & = \left[ a(x)x^3 \ (\operatorname{modd} \ 2,f(x))\right]B_0+ \\ &+\left[ a(x)x^2 \ (\operatorname{modd} \ 2,f(x))\right]B_1+ \\ &+\left[ a(x)x \ (\operatorname{modd} \ 2,f(x))\right]B_2+\\ &+\left[ a(x) \right]B_3. \end{array}

Коэффициенты полиномов в каждой скобке [ \ ] образуют строки матрицы \mathbf{A}, а, следовательно, линейной комбинации этих полиномов, образуемой домножением на скаляры B_0,B_1,B_2,B_3, соответствует умножение строки этих скаляров на матрицу \mathbf{A}:

(B_0,B_1,B_2,B_3) \mathbf{A} \ .

Понятно, что матрица \mathbf A строится снизу вверх, начиная с последней строки: так, 3_{}-я строка матрицы

\mathbf{A}= \left(\begin{array}{llll} M_0 & M_1 & M_2 & M_3 \\ L_0 & L_1 & L_2 & L_3 \\ K_0 & K_1 & K_2 & K_3 \\ A_0 & A_1 & A_2 & A_3 \end{array} \right)

получается из 4_{}-й по правилу умножения на x8) и вычисления остатка по модулю 2_{} при делении на f(x)=x^3+a_1x^2+a_2x+a_3

\mathfrak (K_0,K_1,K_2,K_3) = \left\{ \begin{array}{lr} (A_1,A_2,A_3,0) & npu \ A_0=0, \\ (A_1+a_1,A_2+a_2,A_3+a_3, a_4) \pmod{2} & npu \ A_0=1. \end{array} \right.

После этого, 2_{}-я строка получается из 3_{}-й по аналогичному правилу и т.д.

П

Пример.

\mathfrak a = \mathfrak e=(0,0,0,1) \ \leftrightarrow \ \mathbf{A}=E=\left(\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0& 0 & 1 & 0 \\ 0& 0 & 0 & 1 \end{array} \right) ,

т.е. единичному элементу поля соответствует единичная матрица 4_{}-го порядка. Далее,

(0,0,1,0) \ \leftrightarrow \ \mathbf{F}= \left(\begin{array}{llll} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0& 1 & 0 & 0 \\ 0& 0 & 1 & 0 \end{array} \right) ,\ (0,0,1,1) \ \leftrightarrow \ \left(\begin{array}{llll} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0& 1 & 1 & 0 \\ 0& 0 & 1 & 1 \end{array} \right),\ (0,1,0,0) \ \leftrightarrow \ \left(\begin{array}{llll} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1& 0 & 0 & 0 \\ 0& 1 & 0 & 0 \end{array} \right),\dots

Теперь убедимся, что третья матрица является степенью первой, она равна \mathbf{F}^2 \pmod{2}. Но вторая матрица также является степенью первой: она равна \mathbf{F}^4 \pmod{2}. Откуда это взялось? 8-o — Пока непонятно, но, по крайней мере, мы не входим в противоречие с «таблицей логарифмов» из пункта ВОЗВЕДЕНИЕ В СТЕПЕНЬ:

{.} если \ (0,0,1,0) \leftrightarrow \ x, то \ (0,0,1,1) \leftrightarrow \ x^4 \quad и \quad (0,1,0,0) \leftrightarrow \ x^2 \ .

Что же за чудесные матрицы нами получены? Начнем идентификацию с более простой матрицы, именно с матрицы \mathbf{F}, фактически задающей умножение элемента поля на полином, тождественно равный x_{}. Какую структуру будет она иметь в случае произвольного поля \mathbf{GF}(2^n), с операцией умножения, задаваемой по модулю 2, f(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\dots+ a_n? — Это легко установить:

\mathbf{F}= \left( \begin{array}{lllllll} a_1 & a_{2} & a_{3} & \dots & & a_{n-1} & a_n \\ 1 & 0 & 0 &\dots & 0 & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 & 0 \\ \vdots& && \ddots && & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & 1 & 0 \end{array} \right)_{n \times n} \ .

Эта матрица9) известна как матрица Фробениуса.


Сложнее с общим видом матрицы \mathbf{A}, соответствующей полиному a(x)=A_0x^3+A_1x^2+A_2x+A_3. В случае бесконечных полей ( \mathbb Q, \mathbb R_{} или \mathbb C_{}) это — матрица из метода Безу представления результанта полиномов f_{}(x) и a(x). Что известно про подобные матрицы? Если \mathbf{B} — матрица, соответствующая полиному b(x)=B_0x^3+B_1x^2+B_2x+B_3, то

\mathbf{A} \mathbf{B}=\mathbf{B} \mathbf{A} \ ,

т.е. матрицы коммутируют. Более того, общий результат такого произведения представляет аналогичную матрицу, составленную для полинома a(x)b(x) \pmod{f(x)}, т.е. для остатка от деления a(x)b(x) на f_{}(x). Доказательство когда-нибудь выложу ЗДЕСЬ. Определитель матрицы \mathbf{A} равен результанту полиномов f_{}(x) и a(x), и он отличен от нуля при условии, что эти полиномы взаимно просты.


Переносим эти результаты в конечное поле. Коммутативность умножения матриц сохранится и при переходе к сравнению по модулю 2_{}; этот же переход даст в результате умножения матриц матрицу, соответствующую полиному a(x)b(x) \ (\operatorname{modd} \ 2,x^4+x+1). Таким образом, установленное соответствие

\mathfrak a=(A_0,A_1,A_2,A_3) \ \leftrightarrow \ a(x)=A_0x^3+A_1x^2+A_2x+A_3 \ \leftrightarrow \ \mathbf{A}

сохранит результат умножения: произведению элементов поля будет соответствовать произведение соответствующих матриц. Поэтому элементу \mathfrak a^{-1} будет соответствовать \mathbf{A}^{-1}. Этот факт подтвержает представление для \mathfrak a^{-1} в полиномиальной форме, данное в конце ПУНКТА. Действительно,

. если \quad \mathbf{A}^{-1}= \left(\begin{array}{llll} \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast \\ B_0& B_1 & B_2 & B_3 \end{array} \right) \quad то \quad \mathfrak a^{-1} =B_0x^3+B_1x^2+B_2x+ B_3

С другой стороны, по способу построения обратной матрицы с помощью алгебраических дополнений, элементы последней строки матрицы \mathbf{A}^{-1} являются алгебраическими дополнениями к элементам последнего столбца матрицы \mathbf{A}, поэтому

\mathfrak a^{-1}= \left|\begin{array}{llll} M_0 & M_1 & M_2 & x^3 \\ L_0 & L_1 & L_2 & x^2 \\ K_0 & K_1 & K_2 & x \\ A_0 & A_1 & A_2 & 1 \end{array} \right| \ .

Сохранится ли сложение: будет ли сумма \mathbf{A}+ \mathbf{B} соответствовать элементу поля \mathfrak a+\mathfrak b или, что то же, a(x)+b(x)? — Да, будет, поскольку остаток от суммы полиномов совпадает с суммой их остатков:

(a(x)+b(x))x^k \quad (\operatorname{modd} \ 2,x^4+x+1) \equiv a(x) x^k (\operatorname{modd} \ 2,x^4+x+1) + b(x) x^k \quad (\operatorname{modd} \ 2,x^4+x+1)

для \forall k \in \{0,1,2,3\}. Итак, изоморфизм между полем Галуа и множеством матриц установлен.

Из этого утверждения следует, что любая матрица \mathbf{A}, соответствующая полиному a(x)=A_0x^3+A_1x^2+A_2x+A_3 может быть, с одной стороны, представлена в виде линейной комбинации степеней матрицы Фробениуса, т.е. полинома от матрицы \mathbf{F}

\mathbf{A} = A_0 \mathbf{F}^3\oplus A_1 \mathbf{F}^2\oplus A_2\mathbf{F}\oplus A_3 E = a (\mathbf{F}) \ ,

а, с другой стороны, должна быть некоторой степенью все той же матрицы Фробениуса:

\mathbf{A} = \mathbf{F}^m \quad при некотором \quad m\in \{0,1,2,\dots \} .

Последовательность \mathbf{F}^0=E, \mathbf{F}^1, \mathbf{F}^2,\dots, будет цикличной: \mathbf{F}^{15}=E.

Подводя итог: в дополнение к упомянутым ВЫШЕ интерпретациям поля Галуа, добавим еще одно. Ненулевой элемент поля Галуа — это

4. некоторая степень матрицы Фробениуса \mathbf{F} или же полином a(\mathbf{F}) ( \deg a(x) \le 3) от этой матрицы. Операция сложения определена как поэлементная по модулю 2_{}, а операция умножения совпадает с операцией умножения матриц10).

В такой интерпретации пропадает необходимость в формализме вычисления произведения элементов поля посредством перемножения полиномов и вычисления остатков по модулю полинома f_{}(x), порождающего поле Галуа. А, кстати, куда этот полином пропал в новом, т.е. матричном, формализме? — Его коэффициенты составили первую строчку матрицы Фробениуса \mathbf{F}, и это его единственное проявление.

Восстановление утерянной информации

Собранного в предыдущих пунктах алгебраического формализма достаточно, чтобы попытаться объяснить «на пальцах» его применения для решения задач помехоустойчивого кодирования.

Предположим, что у нас имеется строка из 20_{} информационных двоичных разрядов (x_1,\dots,x_{20}), которая участвует в процессе коммуникации — либо пересылается по каналу связи, либо записывается на носитель информации. Предположим, что этот процесс подвержен влиянию помех, и часть информационных разрядов могут оказаться потерянными (или испорченными). Задача заключается в такой организации процесса коммуникации, которая позволяла бы восстанавливать потерянное (или исправлять ошибки).

Для решения этой задачи нужны ресурсы. И этими ресурсами являются, во-первых, дополнительные — служебные — разряды, которые подсоединяются к информационным разрядам (и, следовательно, тоже участвуют в процессе коммуникации), и, во-вторых, имеющиеся в нашем распоряжении вычислительные мощности, позволяющие наполнять содержимое служебных разрядов — в зависимости от содержимого разрядов информационных, а также выполнять собственно задачу восстановления утраченного.

Места потерь известны

Поясню на примерах. Составим контрольную сумму

s=\sum_{i=1}^{20} x_i \pmod{2} \ .

Объектом коммуникации делаем строку (x_1,\dots,x_{20},s). Если в результате коммуникации возможно уничтожается содержимое ровно одного информационного разряда и номер j_{} этого разряда становится нам известным, то однозначное восстановление содержимого возможно испорченного разряда производтся по формуле

x_j = s+ \sum_{i=1 \atop i\ne j}^{20} x_i \pmod{2} \ .

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

Существенно сложнее организовать восстановление содержания поврежденных разрядов в случае, когда их несколько. Если бы мы заранее знали их номера, то решение проблемы было бы тривиальным. Например, две контрольные суммы

\left\{ \begin{array}{lcl} s_1&=& x_1+x_3+\dots+x_{19}, \\ s_2 &=&x_2+x_4+\dots+x_{20} \end{array} \right. \pmod{2}

позволят однозначно восстановить содержимое разрядов x_{j} и x_{k}, если j_{} и k_{} — числа разной четности11). Но мы не можем предполагать от нашей техники гарантированного выполнения последнего условия. Так что, если при коммуникации строки (x_1,\dots,x_{20},s_1,s_2) возникает подозрение об уничтожении информационных разрядов с номерами j_{} и k_{} одинаковой четности, то гарантировать их восстановление с помощью указанных контрольных сумм мы не сможем.

Что делать? Очевиден подход к решению задачи: нужно выписать набор (систему) линейных соотношений (уравнений) относительно величин x_1,\dots,x_{20} так, чтобы имелась возможность разрешить полученную систему относительно любых двух величин x_{j} и x_{k}. Проблема за малым — как построить такие соотношения?

Будем решать задачу путем ее усложнения. Допустим, что в процессе коммуникации возможно уничтожение содержимого \le 8_{} информационных разрядов строки X=(x_1,\dots,x_{20}). Для обеспечения возможности восстановления этого содержимого, создаются 8_{} служебных разрядов S= (s_1,\dots,s_8) (назовем их синдромами) , содержимое которых вычисляется по правилу

s_i=a_{i1} x_1+\dots+a_{i,20}x_{20} \pmod{2} \quad npu \quad i\in \{1,\dots,8\}

и при некоторых — пока неопределенных — значениях коэффициентов \{a_{i\ell}\} \subset \{0,1\}.

Сделаем дополнительное предположение: пусть 8_{} потенциально ошибочных информационных разрядов расположены не совсем хаотично в информационной строке, а локализуются в двух составляющих ее 4_{}-хразрядных блоках X_j и X_k: X=(X_1,X_2,X_3,X_4,X_5).

Перепишем 8_{} линейных соотношений для синдромов в матричном виде:

X_{1\times 20} \mathbf{A}_{20\times 8}=S_{1\times 8}

и перейдем в этом матричном уравнении к составляющим блокам. Если

\mathbf{A}= \left( \begin{array}{ll} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \\ \mathbf{A}_{31} & \mathbf{A}_{32} \\ \mathbf{A}_{41} & \mathbf{A}_{42} \\ \mathbf{A}_{51} & \mathbf{A}_{52} \end{array} \right) \quad u \quad S=(S_1,S_2),

то

\left\{ \begin{array}{lcl} X_1\mathbf{A}_{11}\oplus X_2\mathbf{A}_{21}\oplus X_3\mathbf{A}_{31} \oplus X_4\mathbf{A}_{41} \oplus X_5\mathbf{A}_{51}&=&S_1, \\ X_1\mathbf{A}_{12}\oplus X_2\mathbf{A}_{22}\oplus X_3\mathbf{A}_{32} \oplus X_4\mathbf{A}_{42} \oplus X_5\mathbf{A}_{52}&=&S_2. \end{array} \right.

Задача заключается в подборе таких составляющих матрицу \mathbf{A} блоков, чтобы последняя система была однозначно разрешима относительно любой пары информационных блоков X_{j} и X_k.

Выберем все эти матрицы \{\mathbf{A}_{i,\ell}\} из множества \{ \mathbf F^{m} \}_{m=0}^{15} степеней матрицы Фробениуса, рассмотренной в предыдущем пункте. Поскольку эти матрицы коммутируют, то с ними возможно действовать как с обычными числами. Так, к примеру, если взять систему в виде12)

\left\{ \begin{array}{lcl} X_1E + X_2E+ X_3 E + X_4E + X_5E&=&S_1, \\ X_1E+ X_2\mathbf F+ X_3\mathbf F^2 + X_4\mathbf F^3 + X_5\mathbf F^4&=&S_2, \end{array} \right.

то решение ее относительно любой пары блоков X_{j} и X_{k} возможно по схеме, которую мы проиллюстрируем на случае j=2, k=4:

1. умножим первое уравнение справа на матрицу \mathbf F^3 и прибавим ко второму:

X_{2}( \mathbf F + \mathbf F^3 ) =S_2+S_1\mathbf F^3 +X_1(E+\mathbf F^3)+X_3(\mathbf F^2 + \mathbf F^3 )+X_5(\mathbf F^4 + \mathbf F^3) \ ;

2. найдем матрицу обратную матрице \mathbf F + \mathbf F^3 — любым из известных способов:

( \mathbf F + \mathbf F^3 )^{-1}= \left( \begin{array}{llll} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)^{-1} = \left( \begin{array}{llll} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right)=\mathbf F^2 + \mathbf F^3 \ ;

3. домножим последнее уравнение на эту матрицу справа, получим:

X_{2}=S_2(\mathbf F^2 + \mathbf F^3)+S_1(\mathbf F^5 + \mathbf F^6) +X_1(\mathbf F^2+\mathbf F^3+\mathbf F^5+\mathbf F^6)+X_3(\mathbf F^4 + \mathbf F^6 )+X_5(\mathbf F^5 + \mathbf F^7);

4. после нахождения X_{2} выражение для X_{4} вычисляем из первого линейного соотношения.

П

Пример. Пусть

X_1=(1,0,1,0),\ X_2=(0,1,1,1),\ X_3=(0,1,0,1),\ X_4=(1,0,1,0),\ X_5=(0,0,1,1) \ .

Вычисляем S_1 и S_2:

S_1=(0,0,0,1), S_2=(1,0,0,1) \ .

Если предположить, что мы потеряли значения X_2 и X_4, то, действуя по предложенному алгоритму, получим:

S_2 \left( \begin{array}{llll} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right)+S_1 \left( \begin{array}{llll} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)+X_1 \left( \begin{array}{llll} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{array} \right)+X_3 \left( \begin{array}{llll} 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)+X_5 \left( \begin{array}{llll} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{array} \right)=
=(0,1,1,1)= X_2 \ .

§

В настоящем пункте были сделаны все теоретические «заготовки» необходимые для понимания теории построения отказоустойчивых дисковых массивов; последний разобранный пример соответствует последнему примеру из ПУНКТА.

?

Пусть информационная строка X_{} состоит из 21_{} информационного разряда. Разобьем ее на 3_{}-хразрядные блоки X=(X_1,\dots,X_7). Используя поле \mathbf{GF}(2^3) придумать схему построения синдромов с возможностью восстановления любых трех блоков. Сработает ли та же схема для строки из 24_{} разрядов?

Места потерь неизвестны

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

Начнем с самого простого случая: предположим, что испорчено содержание одного-единственного блока, но его местоположение нам неизвестно. Итак, предположим, что до процесса коммуникации мы вычислили значения синдромов по предложенной выше схеме:

\left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5&=&S_1, \\ X_1&+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+ X_5\mathfrak a^4&=&S_2. \end{array} \right.

Здесь \mathfrak a — произвольный элемент поля \mathbf{GF}(16) с единственным условием, что все элементы \{\mathfrak a^{\ell} \}_{\ell=0}^5 различны. Причем нас не интересует пока в какой форме представлен этот элемент — полиномиальной, матричной или любой иной. Пусть в процессе коммуникации строки X_{} произошла ошибка в единственном блоке X_{j}, но номер j_{} этого блока нам неизвестен. В результате пересчитанные синдромы получают новые значения

\left\{ \begin{array}{lllllcl} \tilde X_1& + \tilde X_2 &+ \tilde X_3& + \tilde X_4& + \tilde X_5 &=& \tilde S_1, \\ \tilde X_1 &+ \tilde X_2\mathfrak a&+ \tilde X_3 \mathfrak a^2&+ \tilde X_4\mathfrak a^3&+ \tilde X_5\mathfrak a^4&=& \tilde S_2. \end{array} \right.

Просуммируем по частям соответствующие равенства. Поскольку все элементы \tilde X_i = X_i при всех i \ne j, то получаем:

X_j + \tilde X_j = S_1+ \tilde S_1,\ (X_j + \tilde X_j) \mathfrak a^{j-1} = S_2+ \tilde S_2 \ .

При условии S_1 \ne \tilde S_1, факт наличия ошибки подтверждается. Тогда

(S_1+ \tilde S_1)\mathfrak a^{j-1} = S_2+ \tilde S_2

и элемент поля \mathfrak a^{j-1} может быть выражен из последнего уравнения:

\mathfrak a^{j-1} = (S_2+ \tilde S_2)(S_1+ \tilde S_1)^{-1} \ ;

надо только понимать, что все наши действия (сложение, умножение, обращение) производились над элементами поля \mathbf{GF}(16). Таким образом, для определения места ошибки j_{} мы должны вычислить правую часть последнего равенства и найти в «таблице логарифмов», аналогичной той, что приведена в ПУНКТЕ, показатель j_{}-1 которому этот элемент соответствует (т.е. вычислить «дискретный логарифм по основанию» \mathfrak a). После установления значения j_{} исправляем содержимое блока с этим номером по формуле

X_j = \tilde X_j + (S_1+ \tilde S_1) \ .
П

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

\tilde X_1=(1,0,1,0),\ \tilde X_2=(1,1,0,0),\ \tilde X_3=(1,1,1,1),\ \tilde X_4=(0,1,1,0),\ \tilde X_5=(0,0,0,1).

В предположении единственности испорченного блока, найти его место и исправить его содержимое, если значения синдромов:

S_1= (0,1,0,0), \tilde S_1= (1,1,1,0),\ S_2= (0,0,0,1), \tilde S_2= (1,1,1,0)

подсчитаны в поле \mathbf{GF}(16) по указанной выше схеме при выборе \mathfrak a=(0,0,1,0)=x и операции умножения, определенной по двойному модулю 2,x^4+x+1.

Решение.

x^{j-1}=(1,1,1,1)\cdot(1,0,1,0)^{-1}=(1,1,1,1) \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right)^{-1}=(1,0,0,0)=x^3 \ .

Таким образом, j=4_{}, а истинное значение блока: X_4=(0,1,1,0)+(1,0,1,0)=(1,1,0,0).

Распространение предложенного подхода на большее количество испорченных блоков потребует уже существенной изощренности. Предположим, что в процессе коммуникации информационной строки X_{} испортилось содержимое блоков с номерами j_{} и k_{} при j \ne k. Поскольку теперь количество неизвестных в задаче возрастает до четырех ( j,k,X_j,X_k), то можно ожидать, что для восстановления значений этих неизвестных нам потребуются столько же уравнений, т.е. необходимо вычислять значения (как минимум) четырех синдромов. Действуя по аналогии с предыдущим, будем вычислять эти синдромы по правилам:

\left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5&=&S_1, \\ X_1&+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+ X_5\mathfrak a^4&=&S_2, \\ X_1&+ X_2\mathfrak a^2&+ X_3 \mathfrak a^4&+ X_4\mathfrak a^6&+ X_5\mathfrak a^8&=&S_3,\\ X_1&+ X_2\mathfrak a^3&+ X_3 \mathfrak a^6&+ X_4\mathfrak a^{9}&+ X_5\mathfrak a^{12}&=&S_4. \end{array} \right.

Если величины тех же синдромов на выходе канала связи стали равны \{\tilde S_i\}_{i=1}^4 и хотя бы для одного из них \tilde S_i \ne S_i, то получаем уравнения для определения испорченных блоков X_j,X_k в виде:

\left\{ \begin{array}{llcl} (X_j+\tilde X_j)& + (X_k+\tilde X_k) &=&S_1 +\tilde S_1, \\ (X_j+\tilde X_j)\mathfrak a^{j-1}& + (X_k+\tilde X_k)\mathfrak a^{k-1} &=&S_2 +\tilde S_2, \\ (X_j+\tilde X_j)\mathfrak a^{2(j-1)}& + (X_k+\tilde X_k)\mathfrak a^{2(k-1)} &=&S_3 +\tilde S_3, \\ (X_j+\tilde X_j)\mathfrak a^{3(j-1)}& + (X_k+\tilde X_k)\mathfrak a^{3(k-1)} &=&S_4 +\tilde S_4. \end{array} \right.

Определим сначала из этой системы величины j_{} и k_{}. Поскольку последние входят в уравнения существенно нелинейным образом, будем искать их через посредство \mathfrak a^{j-1} и \mathfrak a^{k-1}: найдем уравнение, которому удовлетворяют эти элементы поля \mathbf{GF}(16). Будем искать его в виде квадратного уравнения

\sigma_0\mathfrak e + \sigma_1\mathfrak x + \sigma_2\mathfrak x^2 = \mathfrak o

с пока неопределенными коэффициентами \{ \sigma_0, \sigma_1, \sigma_2 \}\subset \mathbf{GF}(16). Для определения этих коэффициентов домножим равенства, которые получаются из этого уравнения подстановками \mathfrak x =\mathfrak a^{j-1} и \mathfrak x =\mathfrak a^{k-1}:

\left\{ \begin{array}{rl|llc} \sigma_0\mathfrak e+\sigma_1\mathfrak a^{j-1}+\sigma_2\mathfrak a^{2(j-1)}&=0, & \times (X_j+\tilde X_j) & & \\ & & & & + \\ \sigma_0\mathfrak e+\sigma_1\mathfrak a^{k-1}+\sigma_2\mathfrak a^{2(k-1)}&=0 & \times (X_k+\tilde X_k) & & \end{array} \right.

и сложим. С учетом приведенных выше соотношений, получим:

\sigma_0(S_1 +\tilde S_1)+\sigma_1(S_2 +\tilde S_2)+\sigma_2(S_3 +\tilde S_3)= \mathfrak o \ .

Еще раз домножим уравнения:

\left\{ \begin{array}{rl|llc} \sigma_0\mathfrak e+\sigma_1\mathfrak a^{j-1}+\sigma_2\mathfrak a^{2(j-1)}&=0, & \times (X_j+\tilde X_j)\mathfrak a^{j-1} & & \\ & & & & + \\ \sigma_0\mathfrak e+\sigma_1\mathfrak a^{k-1}+\sigma_2\mathfrak a^{2(k-1)}&=0 & \times (X_k+\tilde X_k)\mathfrak a^{k-1} & & \end{array} \right.

и сложим — получаем уравнение

\sigma_0(S_2 +\tilde S_2)+\sigma_1(S_3 +\tilde S_3)+\sigma_2(S_4 +\tilde S_4)= \mathfrak o \ .

Из двух уравнений можно определить набор коэффициентов \sigma_0, \sigma_1, \sigma_2 с точностью до общего сомножителя; получившееся уравнение можно представить с помощью определителя третьего порядка:

\left| \begin{array}{ccc} S_1 +\tilde S_1 & S_2 +\tilde S_2 & S_3 +\tilde S_3 \\ S_2 +\tilde S_2 & S_3 +\tilde S_3 & S_4 +\tilde S_4 \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o \ .

Если нам удастся найти решения \mathfrak x_1, \mathfrak x_2 этого уравнения, то позиции ошибок найдутся из уравнений \mathfrak a^{j-1}=\mathfrak x_1, \mathfrak a^{k-1}=\mathfrak x_2 с помощью «таблицы логарифмов» из ПУНКТА.

После нахождения значений j_{} и k_{} истинные значения испорченных блоков восстанавливаются из системы линейных уравнений

\left\{ \begin{array}{llcl} (X_j+\tilde X_j)& + (X_k+\tilde X_k) &=&S_1 +\tilde S_1, \\ (X_j+\tilde X_j)\mathfrak x_1& + (X_k+\tilde X_k)\mathfrak x_2 &=&S_2 +\tilde S_2. \end{array} \right.
П

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

\tilde X_1=(1,1,1,1),\ \tilde X_2=(1,1,1,1),\ \tilde X_3=(1,1,1,1),\ \tilde X_4=(1,0,1,1),\ \tilde X_5=(0,1,1,0)\ .

В предположении, что количество испорченных блоков равно двум, найти их позиции и исправить их содержимое, если значения синдромов:

\begin{array}{|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 \\ \hline S_j & (0,1,0,0) & (0,1,1,1) & (1,1,0,1) & (0,1,1,0) \\ \hline & & & & \\ \tilde S_j & (0,0,1,0) & (0,1,1,0) & (0,1,0,0) & (0,0,0,0) \\ \hline \end{array}

Вычисления произведены в поле Галуа из предыдущего примера.

Решение. Составляем уравнение

\left| \begin{array}{ccc} S_1 +\tilde S_1 & S_2 +\tilde S_2 & S_3 +\tilde S_3 \\ S_2 +\tilde S_2 & S_3 +\tilde S_3 & S_4 +\tilde S_4 \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o \quad \iff \quad \left| \begin{array}{ccc} (0,1,1,0) & (0,0,0,1) & (1,0,0,1) \\ (0,0,0,1) & (1,0,0,1) & (0,1,1,0) \\ 1 & \mathfrak x & \mathfrak x^2 \end{array} \right|= \mathfrak o
\iff \quad \mathfrak x^2 (0,0,1,0)+ \mathfrak x (1,1,1,0)+(1,0,1,1) = \mathfrak o \quad \iff \quad \mathfrak x^2 \cdot x + \mathfrak x \cdot x^{11}+ x^7 = \mathfrak o \ .

Подстановкой убеждаемся, что корнями этого уравнения являются \mathfrak x_1 = x^2 и \mathfrak x_2 = x^4. Следовательно, j=3 и k=5 — номера испорченных блоков.

Теперь из системы уравнений

\left\{ \begin{array}{llcl} (X_3+\tilde X_3)& + (X_5+\tilde X_5) &=&x^2+x, \\ (X_3+\tilde X_3)x^2& + (X_5+\tilde X_5)x^4 &=&1 \end{array} \right.

находим выражения для X_3+\tilde X_3 и X_5+\tilde X_5.

Ответ. X_3=(0,0,0,0), X_5=(1,1,1,1).

В приведенных выше рассуждениях имеется, однако, один изъян. Мы неявно предполагали, что в процессе коммуникации искажению подвергаются исключительно только блоки информационной строки, но никак не значения синдромов S_1,S_2,\dots Между тем, эти блоки тоже должны участвовать в процессе коммуникации и, следовательно, подвергаются искажениям наряду с X_1,X_2,\dots Алгоритм же корректировки ошибок, предложенный выше, предполагает достоверное знание значений синдромов — до коммуникации и после нее13). Как преодолеть это препятствие?

Для пояснения идеи подвергнем предложенный алгоритм вспомогательной формализации. Введем в рассмотрение переменную \mathfrak x, которая может принимать значения из поля \mathbf{GF}(16). Рассмотрим выражение

G(\mathfrak x)= X_1 + X_2 \mathfrak x+X_3 \mathfrak x^2+ X_4 \mathfrak x^3+ X_5 \mathfrak x^4 \ .

По аналогии с объектом из бесконечных полей, его можно назвать полиномом по переменной \mathfrak x над полем \mathbf{GF}(16). Тогда величины синдромов S_j представляют собой значения полинома G(\mathfrak x):

S_1 = G(\mathfrak e),\ S_2 = G(\mathfrak a),\ S_3 = G(\mathfrak a^2),\dots

Ключевая идея помехоустойчивого кодирования заключается в том обстоятельстве, что к процессу коммуникации допускаются только строки с заранее предписанными значениями \{ g(\mathfrak a^{\ell}) \}, например те, для которых g(\mathfrak a^{\ell})=\mathfrak o при заранее заданном полиноме g(\mathfrak x). Как этого можно добиться? — Например, в нашем дежурном примере коммуникации 5_{} четырехбитных информационных блоков (X_1,X_2,X_3,X_4,X_5) по каналу связи с возможностью исправления одного блока, строкой для пересылки можно взять строку (Y_1,Y_2,Y_3,Y_4,Y_5,Y_6,Y_7), формируемую по правилу:

Y_1+Y_2\mathfrak x+Y_3\mathfrak x^2+\dots+ Y_7\mathfrak x^6 \equiv G(\mathfrak x)(\mathfrak x + \mathfrak e)(\mathfrak x + \mathfrak a)\equiv (X_1 + X_2 \mathfrak x+X_3 \mathfrak x^2+ X_4 \mathfrak x^3+ X_5 \mathfrak x^4)(\mathfrak x + \mathfrak e)(\mathfrak x + \mathfrak a)

при произвольном примитивном элементе поля \mathfrak a. Содержимое блока Y_{i} зависит линейно от информационных блоков \{X_{\ell}\}_{\ell=1}^5; коэффициентами в этих зависимостях являются элементы поля \mathbf{GF}(16). Таким образом, избыточность сообщения оказывается такой же, как и в разобранном выше случае вычисления двух синдромов по правилу

\left\{ \begin{array}{lllllcl} X_1& + X_2 &+ X_3& + X_4& + X_5 &=& S_1, \\ X_1 &+ X_2\mathfrak a&+ X_3 \mathfrak a^2&+ X_4\mathfrak a^3&+X_5\mathfrak a^4&=& S_2. \end{array} \right.

Вместо строки (X_1,X_2,X_3,X_4,X_5,\, S_1,S_2) к процессу коммуникации допускается строка (Y_1,Y_2,Y_3,Y_4,Y_5,Y_6,Y_7), которая, хотя и формируется более сложным способом, тем не менее является более подходящей с точки зрения восстановимости утерянной информации. Если по прохождении по каналу связи на выходе получаем строку (\tilde Y_1, \tilde Y_2, \tilde Y_3, \tilde Y_4, \tilde Y_5, \tilde Y_6, \tilde Y_7), для которой не выполняется хотя бы одно из условий

\left\{ \begin{array}{lllllllcll} \tilde Y_1& + \tilde Y_2 &+ \tilde Y_3& + \tilde Y_4& + \tilde Y_5& + \tilde Y_6& + \tilde Y_7 &=& \tilde S_1 &= \mathfrak o, \\ \tilde Y_1 &+ \tilde Y_2\mathfrak a&+ \tilde Y_3 \mathfrak a^2&+ \tilde Y_4\mathfrak a^3&+\tilde Y_5\mathfrak a^4 & + \tilde Y_6\mathfrak a^5 & + \tilde Y_7 \mathfrak a^6 &=&\tilde S_2 &= \mathfrak o, \end{array} \right.

то делаем заключение о наличии ошибки передачи. Далее, в предположени единственности испорченного блока, ищем его местоположение по разобранному выше алгоритму.

§

В настоящем пункте сделан набросок метода помехоустойчивого кодирования известного под названием кода Рида-Соломона. Для выхода на необходимый уровень строгости изложения нам потребуется узаконить объект, который был тихой сапой перетащен из теории бесконечных полей — это полином с коэффициентами из поля Галуа.

Уравнения нелинейные

Рассмотрим 5_{} различных элементов поля \mathbf{GF}(16); воспользуемся их изначальным представлением в виде 4-хразрядных строк \mathfrak a_j=(A_{j0},A_{j1},A_{j2},A_{j3}) при j\in \{0,1,2,3,4\},\{ A_{jk} \}_{j,k} \subset \{0,1\}. Рассматриваемые как векторы линейного пространства \mathbb R^4, они должны быть линейно зависимыми: существуют скаляры \{ \tilde{\alpha}_j \}_{j=0}^4 \subset \mathbb R такие, что

\tilde{\alpha}_0 \mathfrak a_0+\tilde{\alpha}_1 \mathfrak a_1+\tilde{\alpha}_2 \mathfrak a_2+ \tilde{\alpha}_3 \mathfrak a_3+\tilde{\alpha}_4 \mathfrak a_4=(0,0,0,0) \ .

Можно быстро доказать что, ввиду целочисленности разрядов строк, скаляры \{\tilde{\alpha}_j\} также могут быть выбраны целочисленными. Тогда, переходя в векторном равенстве к сравнению по модулю 2_{}, получим равенство для элементов поля \mathbf{GF}(16)

\alpha_0 \mathfrak a_0+\alpha_1 \mathfrak a_1+\alpha_2 \mathfrak a_2+\alpha_3 \mathfrak a_3+\alpha_4 \mathfrak a_4 = \mathfrak o \ ,

справедливое при некоторых значениях скаляров \{ \alpha_{j} \}_{j=0}^4 \subset \{0,1\}.

Если теперь возьмем в качестве элементов поля степени одного-единственного: \mathfrak a_j = \mathfrak a^j при \mathfrak a \ne \mathfrak o и j\in \{0,1,2,3,4\}, то придем к заключению, что элемент \mathfrak a должен удовлетворять некоторому алгебраическому уравнению F(\mathfrak x) = \mathfrak o степени \le 4 при

F(\mathfrak x)= \alpha_0 \mathfrak e+\alpha_1 \mathfrak x+\alpha_2 \mathfrak x^2+\alpha_3 \mathfrak x^3+\alpha_4 \mathfrak x^4 \quad u \quad \{ \alpha_{j} \}_{j=0}^4 \subset \{0,1\} \ .
§

Переменную в полиноме обозначил готической буквой \mathfrak x чтобы отличать от переменной в полиномиальном представлении элементов поля.

Представление для полинома F_{} можно получить разными способами, я привожу самое наглядное14):

F(\mathfrak x)= \left| \begin{array}{lllll} A_{00} & A_{01} & A_{02} & A_{03} & \mathfrak e\\ A_{10} & A_{11} & A_{12} & A_{13} & \mathfrak x\\ A_{20} & A_{21} & A_{22} & A_{23} & \mathfrak x^2\\ A_{30} & A_{31} & A_{32} & A_{33} & \mathfrak x^3\\ A_{40} & A_{41} & A_{42} & A_{43} & \mathfrak x^4 \end{array} \right| \pmod{2} \ .

Разложив этот определитель по последнему столбцу, получим требуемое.

Теперь проверим на примерах, насколько эти рассуждения конструктивны — не получится ли так, что все коэффициенты F(\mathfrak x) обратятся в нуль?

П

Пример. Пусть поле \mathbf{GF}(16) построено на основе умножения по двойному модулю 2, f(x) при f(x)=x^4+x+1, и пусть \mathfrak a = (0,1,0,1). Имеем:

\mathfrak a^2=(0,0,1,0),\ \mathfrak a^3=(1,0,1,0),\ \mathfrak a^4=(0,1,0,0) \ ,

и

F(\mathfrak x)\equiv_{_2} \left| \begin{array}{ccccl} 0 & 0 & 0 & 1 & \mathfrak e\\ 0 & 1 & 0 & 1 & \mathfrak x\\ 0 & 0 & 1 & 0 & \mathfrak x^2\\ 1 & 0 & 1 & 0 & \mathfrak x^3\\ 0 & 1 & 0 & 0 & \mathfrak x^4 \end{array} \right| \equiv_{_2}
\equiv_{_2} \mathfrak e \left| \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x \left| \begin{array}{ccccl} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^2 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^3 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array} \right|+ \mathfrak x^4 \left| \begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ \end{array} \right| \equiv_{_2}
\equiv_{_2} \mathfrak x^4+\mathfrak x+\mathfrak e \ .

То есть мы получили тот же полином f_{}, с помощью которого было построено поле! — Неожиданный результат, который хочется подвергнуть дополнительной проверке. Проверка для элементов \mathfrak a^2=(0,0,1,0) и \mathfrak a^4=(0,1,0,0) приводит к тому же полиному f_{}, но вот для \mathfrak a^3=(1,0,1,0) получаем другой результат:

F(\mathfrak x) =\mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+ \mathfrak e \ .

Еще пара проверок:

\mathfrak a=(1,0,1,1) \quad \Rightarrow \quad F(\mathfrak x) =\mathfrak x^4+\mathfrak x^3+ \mathfrak e \ ;
\mathfrak a=(0,1,1,0) \quad \Rightarrow \quad F(\mathfrak x) =\mathfrak x^2+\mathfrak x+ \mathfrak e \ .

В последнем случае приходится немного повозиться, потому как построение полинома F(\mathfrak x) в виде определителя 5_{}-го порядка приводит к тождественно нулевому полиному…

Теперь подтвердим полученные результаты, основываясь на матричном формализме поля Галуа. Фундаментальным результатом теории матриц является теорема Гамильтона-Кэли: матрица A_{n\times n} является корнем своего характеристического полинома, т.е. если

\det (A-xE) \equiv (-1)^n(x^n+a_1x^{n-1}+\dots+a_n)

при E_{}единичной матрице порядка n_{}, то

A^n+a_1A^{n-1}+\dots+a_nE \equiv \mathbb O_{n\times n} \ .
П

Пример. Поле \mathbf{GF}(16) — то же, что и в предыдущем примере. Элементу поля \mathfrak a = (0,1,0,1) сопоставляется матрица

\mathbf A= \left( \begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \ .

Вычислим ее характеристический полином:

\det (\mathbf A-\mathfrak x E) = \left| \begin{array}{cccc} 1- \mathfrak x & 1 & 1 & 0 \\ 0 & 1-\mathfrak x & 1 & 1 \\ 1 & 0 & 1-\mathfrak x & 0 \\ 0 & 1 & 0 & 1-\mathfrak x \end{array} \right| \equiv \mathfrak x^4 -4\, \mathfrak x^3+ 4\, \mathfrak x^2 - \mathfrak x +1 \equiv_{_2} \mathfrak x^4 + \mathfrak x +1 \ .

Получили тот же самый полином, что и в предыдущем примере. Но вот с другим элементом получается результат, отличный от полученного ранее:

\mathfrak a=(0,1,1,0) \quad \Rightarrow \quad \det (\mathbf A-\mathfrak x E)\equiv_{_2} \mathfrak x^4 + \mathfrak x^2 +1 \ .

Тем не менее, и для этого результата найдется объяснение из теории матриц:

\mathfrak x^4 + \mathfrak x^2 +1 \equiv_{_2} (\mathfrak x^2+\mathfrak x+1)^2 ,

и полином \mathfrak x^2+\mathfrak x+1 является минимальным аннулирующим для матрицы \mathbf A_{}.

Вполне предсказуем и результат для элемента поля \mathfrak a=(0,0,1,0)=x — матрица Фробениуса \mathbf F имеет просто вычисляемый характеристический полином:

\left| \begin{array}{cccc} - \mathfrak x & 0 & 1 & 1 \\ 1 & 1-\mathfrak x & 0 & 0 \\ 0 & 1 & 1-\mathfrak x & 0 \\ 0 & 0 & 1 & 1-\mathfrak x \end{array} \right| \equiv \mathfrak x^4+\mathfrak x+1

Основываясь на этих (весьма неполных) экспериментальных данных, сделаем общие выводы:

1. Любой ненулевой элемент поля является корнем некоторого полинома F(\mathfrak x), степень которого равна одному из чисел: \{1,2,4\}.

2. Если \mathfrak a — корень полинома F(\mathfrak x), то и \mathfrak a^2, \mathfrak a^4,\mathfrak a^8,\dots будут корнями этого полинома15).

3. Все возможные полиномы, корнями которых могут быть элементы поля, являются делителями по модулю 2_{} полинома x^{15}-1:

x^{15}-1 \equiv_{_{2}} (x-1)\underbrace{(x^2+x+1)}_{f_{_4}(x)}\underbrace{(x^4+x+1)}_{\equiv f(x)}\underbrace{(x^4+x^3+1)}_{\equiv f^{\ast}(x)} \underbrace{(x^4+x^3+x^2+x+1)}_{\equiv f_{_3}(x)}\ .

Нечто подобного можно было бы ожидать, если вспомнить упомянутую выше обобщенную теорему Ферма: для любого элемента поля \mathfrak a \ne \mathfrak o выполняется \mathfrak a^{15} = \mathfrak e. Не столь очевиден следующий вывод:

4. Полиномы, стоящие в правой части разложения полинома x^{15}-1, являются неприводимыми полиномами. Степени неприводимых полиномов являются делителями числа 4_{}.

§

Именно эти полиномы указаны в последнем столбце таблицы, приведенной в примере из ПУНКТА.

Попробуем теперь обсудить полученные в настоящем пункте выводы, переведя их на язык альтернативного представления элементов поля \mathbf{GF}(16), а именно — как полиномов A_0x^3+A_1x^2+A_3x+1. Получилось, что эти полиномы сами являются корнями некоторых полиномов от другой переменной \mathfrak x!

В самом деле, подставим \mathfrak x=x^3+1 в полином \mathfrak x^4+\mathfrak x^3+\mathfrak e и проведем все вычисления по двойному модулю 2,f(x)=x^4+x+1 с использованием таблицы из ПУНКТА:

(x^3+1)^4+(x^3+1)^3+1 \equiv_{_2} x^{12}+1+x^{9}+x^{6}+x^3+1+1\equiv_{_2,f}
\equiv_{_2,f}\underbrace{(x^3+x^2+x+1)}_{\equiv x^{12}}+\underbrace{(x^3+x)}_{\equiv x^{9}}+\underbrace{(x^3+x^2)}_{\equiv x^{6}}+x^3+1 \equiv_{_2} 0 \ .

Теперь попробуем провести проверку с другой стороны — попробуем разложить какой-нибудь из неприводимых полиномов на линейные множители. Возьмем, к примеру полином f_3(\mathfrak x)=\mathfrak x^4+\mathfrak x^3+\mathfrak x^2+\mathfrak x+\mathfrak e. Согласно последнему столбцу таблицы из ПУНКТА, его корнями являются полиномы x^3,\ x^6,\ x^9,\ x^{12}. Вычислим произведение

(\mathfrak x+x^3)(\mathfrak x+x^6)(\mathfrak x+x^9)(\mathfrak x+x^{12}) =
= \mathfrak x^4+(x^3+x^6+x^9+x^{12})\mathfrak x^3+(x^9+x^{12}+x^{15}+x^{15}+x^{18}+x^{21})\mathfrak x^2+ (x^{18}+x^{21}+x^{24}+x^{27})\mathfrak x + x^{30} \ .

Имеем,

x^{30} \equiv_{_{2,f}} 1,\ x^3+x^6+x^9+x^{12} \equiv_{_{2,f}} x^3+(x^3+x^2)+(x^3+x)+(x^3+x^2+x+1)\equiv_{_2} 1,\dots ,

т.е. противоречий не получаем.

Идем далее. До сих пор примеры полиномов F(\mathfrak x), которые нам попадались в настоящем пункте, имели коэффициенты 0_{} или 1_{}, или, как говорят, были полиномами над полем \mathbf{GF}(2). А нам в предыдущем ПУНКТЕ пришлось столкнуться с необходимость решения уравнений F(\mathfrak x)= \mathfrak o, коэффициентами которых были элементы поля \mathbf{GF}(16). Что можно сказать о таких уравнениях? — Можно ли утверждать, что они имеют решения в том же поле? Если да, то как эти решения найти?

П

Пример. В поле \mathbf{GF}(16) с умножением, определенным по модулю любого неприводимого (по модулю 2_{}) полинома f_{}(x) степени 4_{}, существует решение уравнения \mathfrak x^2 + \mathfrak a = \mathfrak o относительно \mathfrak x при любом значении \mathfrak a \in \mathbf{GF}(16). Иными словами, существует «корень квадратный» из любого элемента поля. Для доказательства, вспомним, что элемент \mathfrak a можно представить в виде степени примитивного элемента поля: \mathfrak a = \mathfrak A^k. Очевидно, что

\sqrt{\mathfrak a}= \left\{ \begin{array}{rl} \mathfrak A^{k/2} & npu \ k\ 4ETHOM , \\ \mathfrak A^{(15+k)/2} & npu \ k\ HE4ETHOM , \end{array} \right.

и это — единственное значение квадратного корня.

С другой стороны, не существует корней у уравнения \mathfrak x^2+x\cdot \mathfrak x+ \mathfrak e= \mathfrak o при выборе в качестве «генерирующего умножение» неприводимого полинома f(x)=x^4+x+1. Проверить это утверждение удается только перебором всех элементов поля: формула дискриминанта для квадратного уравнения в \mathbf{GF}(16) не работает16). У того же уравнения существуют два корня, именно \mathfrak x=x^2 и \mathfrak x=x^{13}, при выборе в качестве неприводимого полинома f(x)=x^4+x^3+1.

?

Доказать, что полином \mathfrak x^2+\mathfrak a_1 \mathfrak x+ \mathfrak a_2 над \mathbf{GF}(16) при \mathfrak a_1 \ne \mathfrak o либо не имеет корней в этом же поле, либо имеет два различных.

Какие результаты можно перенести из теории полиномов над бесконечными полями? — Прежде всего, проверим один полезный результат, связанный с делимостью полиномов. Допустим, что для полинома F(\mathfrak x) степени \ge 2 найден корень \mathfrak x=\mathfrak x_1, т.е. F(\mathfrak a_1)= \mathfrak o. Будет ли справедлива теорема Безу:

F(\mathfrak x) \equiv (\mathfrak x + \mathfrak a_1) F_1(\mathfrak x) \ ?

Здесь \equiv_{} означает тождественное равенство (т.е. равенство справедливое при \forall \mathfrak x \in \mathbf{GF}(16)), а F_1(\mathfrak x) — полином над \mathbf{GF}(16) степени, равной \deg F-1. Ответ оказывается положительным и доказательство основывается на схеме Хорнера.

П

Пример. В \mathbf{GF}(16) с умножением, определенным по модулю x^4+x+1 полином F(\mathfrak x) =\mathfrak x^3+(x^2+x)\,\mathfrak x^2+(x^2+x+1)\, \mathfrak x+ (x^3+x+1) имеет корень x_{}+1. Проверить это утверждение и найти полином F_1(\mathfrak x) из предыдущего тождества.

Решение. Строим схему Хорнера:

\begin{array}{c|cccc} & 1& x^2+x & x^2+x+1 & x^3+x+1 \\ \hline x_{}+1 & 1 & x^2+1 & x^3 & 0 \end{array}

Таким образом, действительно

F(x+1)=\mathfrak o \quad u \quad F_1(\mathfrak x)=\mathfrak x^2+(x^2+1)\mathfrak x+x^3 \ .

Т

Теорема. Полином F(\mathfrak x) над полем \mathbf{GF}(16) степени \deg F \ge 1 имеет не более \deg F корней в этом поле.

Задачи

1) \upsilon \pió\sigma \tau \tilde{\alpha} \sigma \iota \varsigma (др.греч.) — сущность.
2) «С выключенными цепями переносов»
3) «Ну вот нашли большое поле…» (Кто-то из классиков ;-)).
4) , 5) Все дальнейшие сравнения — по модулю 2,f(x)=x^4+x+1.
6) , 12) В оставшейся части пункта будем считать +_{} совпадающим с \oplus.
7) Напомню: операция +_{} идет по модулю 2_{}.
8) Имеется в виду «умножение на «икс»», а не то, что может придти в голову ;-)
9) с точностью до перестановки строк и столбцов
10) Поскольку составной частью операции умножения матриц является операция сложения, то последнюю, опять же, выполняем по модулю 2_{}.
11) Например, содержимое двух соседних разрядов.
13) Если только не предполагать наличие дополнительного канала связи повышенной помехоустойчивости, выделенного для передачи значений синдромов.
14) Хотя и не оптимальное с вычислительной точки зрения
15) Понятно, что эта последовательность является циклической?
16) Почему? — А попробуйте ее вывести! (Если забыли как выводится — см. ЗДЕСЬ ).

2018/03/20 00:01 редактировал au