Об одной задаче теории кодирования данных при передаче информации по каналам связи

УДК 621.391.15

В. С. Кугураков, А. П. Кирпичников

ОБ ОДНОЙ ЗАДАЧЕ ТЕОРИИ КОДИРОВАНИЯ ДАННЫХ ПРИ ПЕРЕДАЧЕ ИНФОРМАЦИИ ПО КАНАЛАМ СВЯЗИ

Ключевые слова: кодирование данных, уравнения в конечном поле, коды, исправляющие ошибки.

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

Keywords: encoding data, equations in finite field, error-correcting codes.

Solution of the problem, arising in the theory of data encoding when transmitting information over channels is obtained. The results can also be used in a number of other topics in applied computer science and computer mathematics.

Введение

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

и указаны явные формулы для его корней, лежащих в Fpt. Здесь F4 - конечное поле, содержащее q элементов (q - степень простого числа р); s и t - натуральные числа.

Отметим вкратце известные факты об уравнении (1) и сделаем некоторые замечания.

Многочлен в левой части уравнения (1) относится к так называемым аффинным (а при Ъ = 0 и к линеаризованным) многочленам. Для нахождения корней таких многочленов обычно рекомендуют метод Берлекэмпа (см., например, [1], гл. 11), в котором эта задача сводится к решению системы линейных уравнений.

При а = 0 уравнение (1) имеет единственный корень (кратности ps), равный —ЬрГ, где г> 0 -любое целое число такое, что г + s = 0 (mod t). Поэтому всюду далее будем считать, что аф 0. Полагая п = -, т = - и q = pd, где d = (s, t) — наи-d d

больший общий делитель s и t, уравнение (1) можно теперь переписать так:

xq +ax + b = 0; а, be F„m, аф 0,

(п, ш) = 1.

Последнее уравнение исследовалось в [2], где показано. что оно может иметь 0, 1 или (п, т) корней, лежащих в ; однако, какая из этих возможностей реализуется при тех или иных а и Ь, не установлено. Вопрос о разрешимости уравнения (2) рассмотрен в [3, стр. 244. Аддитивная форма теоремы Гильберта 90; см. также 4, гл.У, § 11.5], откуда можно извлечь также и формулы для корней этого уравнения.

К уравнениям типа (2) относятся квадратное уравнение над и приведённое кубическое уравнение над Р3™, а именно:

х2 +ах + Ь = 0; a, beW7

х3+ах + Ь = 0; а, Ье¥3т.

Здесь будет уместно отметить, что хорошо известная "школьная" формула для корней квадратного уравнения в случае поля характеристики 2 оказывается непригодной: в таком поле деление на 2 равносильно делению на 0. То же самое можно сказать и о кубическом уравнении над полем характеристики 3 (как, впрочем, и над полем характеристики 2) -формулы Кардано здесь также непригодны. Для указанных полей это влечёт определённые трудности и при решении уравнений четвёртой степени. Заметим, что в поле характеристики р> 5 такие проблемы не возникают и при решении уравнений степени п< 4 можно использовать известные формулы [5, § 64]. Некоторые результаты об уравнениях (3) и (4) получены соответственно в [6] и [7]. Исследуя более общее уравнение (2), мы приводим формулы, которые пригодны, конечно, и для решения указанных квадратного и кубического уравнений. В отличие от [6] (где, заметим, дано несколько формул для корней уравнения х2+х + Ь = 0; ЬЕ , соответствующих различным значениям пит) мы показываем, что корни уравнений (3) и (4) могут быть вычислены по одной - единственной формуле, которая "работает" во всех случая, когда эти уравнения имеют решения соответственно в и Р3т (см. также [8] и [9]).

Формулы для корней уравнения

Положим

А = ач~! - (-1)"

т—1

T(u) = ^

¿=о

т—1

и

где а, Ъ, п, т, q те же, что и в уравнении (2); с0 = 1, С; = — С1_1а~ч1П, ¿ = 1, 2,... Величина 5 известна как резольвента Гильберта-Лагранжа.

Отметим следующее свойство функции Т(и), называемой обычно следом элемента иЕ ¥чт относительно расширения ¥цт /¥С{: для любого гЕ найдётся иЕ ¥чт такой, что Тг(и) = г.

Лемма. Если А = 0, то в ¥цт найдётся элемент w

такой, что №чП-1 = - а.

Доказательство. Все аЕ ¥С{т, для которых А = 0, суть следующие элементы:

аг = ^(ч-1)+/, г = 0,

gm-i

-1,

где £ - первообразный элемент мультипликативной группы поля ¥чт, а / = 0 или соответственно случаям: 1) т или q чётно; 2) т и q оба нечётны. Если а = аг, то в качестве искомого w можно взять w_ где I - любое число, для которого

дп-1 цт-1

I

= 1 (mod ) q-1 q-1

(ввиду (^"-1, qm-1) = ц{т'п) -1 = ц-1 такое I существует);

5= 0, --или 11+--)/2

2(4-1) V 4-1 )'

соответственно случаям, когда 1) q чётно; 2) т чётно, а q нечётно; 3) т и q нечётны.

Теорема. Учитывая только те из корней уравнения (2), которые лежат в ¥цт, имеем:

1) если А = 0, но 5^0, то уравнение (2) не имеет корней;

2) если АФ 0, то имеется единственный корень ^ =

3) наконец, если А = 5 = 0, то имеется q корней , а именно:

Учитывая, что vq =v для любых vE ¥qm и г = 0, 1,.... и

cm-i = (-1)m-1a-^n-^2n-- - о(т~1)п = (-1)т-1а-ч1-ч2--- ч(т_1) (последнее имеет место ввиду (п, ш) = 1 и qn + q2n + ••• + q(m"Dn

= q1 + q2 + - + q<-m~V (mod qm-1)), получаем

Из тождества (8) вытекают утверждения 1) и 2) в формулировке теоремы. Убедиться в том, что ^^ -корень уравнения (2), когда АФ 0, можно непосредственно - подстановкой х = % в (2). Остаётся проверить, что в случае А= 5 = 0 любое из q значений , определяемое согласно (6), является корнем уравнения (2):

^f + a$k+b = (wkyn + awk

m—l n i-1

i=l J = 0

m—l i-1

i=l J = 0

m—l i-1 m—l i-1

= £ Cib«ln - £ cib^ln Y^^11 + b

1=2 j=0 i = l j=o

/т—1 \

= Cib^in +

V i=2

c-ib*

i-1

+b\-u + \ + b

7=0

= -uS + bT(u) + b = 0.1

$k=wk

m—l i-1

U4 ,

1=1 7 = 0 кЕ ¥ч,

где ш,и - любые элементы поля ¥чт, для которых

wчn-1 = -а и Т

Замечание 1. Существование элементов w и и, удовлетворяющих (7), было обосновано выше. Для случая А = 0 имеем = (а\м)1~ ¿ = 0, 1,..., и 5 = w7, (—-). Поэтому здесь 5 = 0 равносильно

= 0. Формула (6) переписывается так:

(т—1 цЫ 1-1 \

к

¿=1 7=0 ) Доказательство теоремы. Пусть ^ - некоторый корень уравнения (2), лежащий в ¥цт (в предположении, что он существует). Тогда

т—1

с^ + а^ + ЬУ

¿=0

т т—1

1=1 1=0 = ст-1^чтП + с0а$ + 5.

Некоторые следствия

1) Полученные формулы могу быть использованы для решения общих уравнений над и Р3т третьей и четвёртой степени. Поскольку этот вопрос уже неоднократно освещался в литературе, мы ограничимся здесь минимальными ссылками: в [6] показано, что решение указанных уравнений над ¥2т в конечном итоге сводится к решению уравнения (3); в [7] показано, что решение общего кубического уравнения над Р3т сводится к решению уравнения (4). (Вьфожденные случаи, когда такое сведение невозможно, исследуются достаточно просто.) Отметим лишь, что решение уравнения над Р3т четвёртой степени, как и в случае комплексных чисел, методом Феррари (см. [10], § 38) сводится к решению квадратного и кубического уравнений.

С уравнением (1) связаны и некоторые другие уравнения. Так, если ^ - один из корней уравнения

хр"+1 + ах + Ь = 0, а, ЬЕ ¥р(, Ъф 0, (9) то нетрудно показать, что остальные его корни суть £ + у^1, где У[,1 = 1,., рБ, - корни уравнения

уР +

f

(Р +а

У +

а

= 0.

Уравнение (10) есть уравнение типа (1), и мы можем вычислить его корни, применяя полученные формулы. Вопрос, однако, в том, как найти хотя бы один корень уравнения (9).) Покажем, как вычислить корни уравнения (9), лежащие в ¥рт, на примере уравнения

х2*+1 + ах + Ь = 0; а, ЪЕ ¥2т.

Пусть (Е — корень данного уравнения. Если + а Ф 0, то уф 0, и для вычисления у используем уравнение (2). Если + а = 0, то + а2 =0, и тогда £ = а2 , или а = %2 . Поскольку = £ для любого ¥2т, и +1 2 £ + Ь = Ъ = 0. В этом случае уравнение (11) имеет вид х2*+1 + ах = 0

и, следовательно,

х = 0 и х = от . Корни уравнения (11) удобно представить в степенном или нормальном базисах над полем Р2 . Это позволит свести вычисление корней к решению системы нелинейных квадратичных уравнений над полем Р2 .

Таблица 1 - Представление элементов поля Р24 в степенном и нормальном базисах

В виде В виде В виде В виде

степени многочлена вектора вектора

а а3а?а1а0 Ь3Ь2Ь1 ьп

а™ = 0 0 0000 0000

а0 1 0001 1111

а1 а 0010 1001

а2 а2 0100 0011

а3 а3 1000 0001

а4 а+1 0011 0110

а5 а2 +а 0110 1010

а6 а3 +а2 1100 0010

а7 а3 +а +1 1011 0111

а8 а2 +1 0101 1100

а9 а3 +а 1010 1000

а10 а2 +а+1 0111 0101

а11 а3 +а2 +а 1110 1110

а12 а3 +а2 +а + 1 1111 0100

а13 а3 +а2 +1 1101 1101

а14 а3 +1 1001 1011

В качестве простого примера рассмотрим уравнение

х9 + ах + Ь = 0; а,Ь е¥2

Поле Р24 (см. таблицу), рассматривается как факторкольцо кольца Р2 [х] по идеалу, порожденному примитивным многочленом /(х) =х4 +х + 1бР2 [х]. Элементы поля могут быть представлены в степенном базисе а = (1, а, а2,а3), и нормальном базисе р= (£>,р2,р4,р8), где р = а3,а - прими-

тивный элемент поля Р24

Любой элемент сЕ Р24

однозначно представим в виде

с = а0 •1 + а1 •а + а2 •а2 + а3 •а3

= ь0^р + ь^р2 + ь2^р4 + ь3^р8

для некоторых аь Ъ^ 6Р2 ,1 = 0,1,2,3. Переход от нормального базиса к степенному базису, и обратно, реализуется с помощью линейных преобразований

(Ь0,Ь1,Ь2,Ь3)А = (а0,а1,а2,а3) (а0,а1,а2,а3)А~1 = (Ь0,Ь1,Ь2,Ь3),

где

А =

А-1 =

Пусть в уравнении (12) а = а, Ь = а13. Тогда, записывая а, Ъ, х в нормальном базисе, а именно: а = р + р8, Ь= р +р4 +р8, х = хор + х1р2 + х2р4 +хзрв, получим следующую систему нелинейных квадратичных уравнений относительно х0,х1,х2,х3 £Р2 :

ХдХ^ "Ь х^х2 "Ь х^х3 -Ъх^ ~Ьх2х3 -(-х3 — 1, Х0Х2 + Х^Х3 ""("Хр +ххх2 +хх + Х2Х3 +х3 — 0, ХрХ^ Х^Х3 + Х1Х3 + Х2Х3 +х2 +х3 — 1,

ХрХ^ ~^Х^Х2 -|-Х0Х3 +Х1Х2 +х2 — 1.

Вычисляя редуцированный базис Грёбнера [11, гл. 2, §8] при линейном упорядочении х0 >хх > х2 >х3, получаем эквивалентную систему уравнений:

х0 +х3 + 1 = 0, ^ + 1 = 0,

х2х3 +х2 +х3 + 1 = 0. Её решениями являются:

х0 = 1, хг = 1,х2 = 1,х3 = 0, х0 = 0, хг = 1,х2 = 0,х3 = 1, х0 = 0, хг = 1,х2 = 1,х3 = 1. Соответственно решениями уравнения (12) будут: а3 + а6 + а12 = а1, а6 + а9 = а5, а6 + а12 +а9 = а14.

Если характеристика рассматриваемого поля равна 2 и (2х — 1,2т — 1) = 1 (что, заметим, выполняется для уравнения (12)), то можно использовать следующий способ вычисления корней уравнения (9). Осуществим замену х = у2*-1, затем умножим обе части полученного уравнения на у. В результате получим уравнение

у2 +ау2 +Ьу = 0.

С учетом соотношения у =у для уЕ Р24 уравнение (12) преобразуется к виду

у4 + ау8 + Ъу = 0.

Многочлены в (13) и (14) являются линеаризованными, вычисление их корней, как уже отмечалось, сводится к решению системы линейных уравнений. Возникающие  лишние  корни отбрасываются.

Полагаем у = у0р + у^Р2 +У2Р4 +УзР8. Тогда уравнение (14) сводится к решению следующей системы уравнений относительно у0, у1, у2, у3 Е

ру2 = 0, рв(у0+у1+у3) = 0. Решениями этой системы будут (Уо, У±,У2, Уз) = (0,0,0,0) (Уо, У1,У2, Уз) = (0,1,0,1) (Уо, У1,У2, Уз) = (1,0,0,1) (Уо, У1,Уг, Уз) = (1,1,0,0) Соответственно решениями уравнения (12) являются:

и

4 .

у = а5, у = а7, у = а14, приобретенное решение у = 0 является лишним. Остальные шесть корней уравнения (12) лежат в некоторых расширениях поля ¥2* . Они могут быть вычислены как корни уравнения (10).

2) Приведём ещё два следствия доказанной выше теоремы. Первое из них о разложении многочлена

д(х) = х4 + ах + Ь = 0; а, ЪЕ ¥2т, аф 0, (15) на неприводимые над ¥2т множители — уточняет (применительно к многочлену (15)) результат из [12] о разложении многочленов над ¥2т четвёртой степени; второе есть обобщение одной теоремы Диксона (см. [13], § 21 или [14], § 14).

Будем говорить, что многочлен д(х) имеет тип (14), если он разлагается в произведение линейных множителей над ¥2т; многочлен д(х) имеет тип (122х), если он разлагается в произведение двух линейных множителей над ¥2т и неприводимого над ¥2т квадратного многочлена и т.д. Элемент аЕ ¥2т будем называть кубом, если а = с3 для некоторого сЕ ¥2т, и некубом - в противном случае. Наконец, положим

т-1 т-1

Г0(£)= и Т1(Р)=^Р221, 1=0 1=0 причём 7\ определено лишь для чётного т.

Следствие 1. Для многочлена (11) возможны следующие типы:

а) (14); б) (122х); в) (^З1); г) (22); г) (41).

Условия, при которых имеет место соответствующий тип, суть следующие:

а) т чётно, а - куб и Т1_(Р) = 0;

б) т нечётно и Т0(р) = 0;

в) т чётно, а - некуб;

г) т чётно, а - куб и Тг(р) Ф0;

д.) т нечётно и Т0(р) Ф0,

где р= а w - корень уравнения ж3 = а.

Доказательство этого утверждения опускается: оно осуществляется разбором случаев и непосредственным применением доказанной выше теоремы. Отметим лишь, что в тех случаях, когда требуется вычислить w, этот элемент лежит в ¥2т.

Следствие 2. Пусть q - степень простого числа, причём цф 2; т и I - любые натуральные числа, причем (¿, ц-1) = 1, исключая случай, когда т, q и

нечётны, для которого (¿, ц-1) = 2. Пусть также Ъ - произвольный элемент поля ¥цт, и а = , где ( - первообразный элемент поля ¥чт. Тогда многочлен

д(х) = хч + ах + Ь = 0 есть произведение линейного многочлена и неприводимого над ¥чт многочлена степени ц-1.

Замечание 2. В [14] это утверждение доказано для а= - ( (т.е. ¿ = 1, если q чётно и цф 21, и

дт +1

¿= —-—, если q нечётно). В исходной работе [13] к тому же т = 1.

Доказательство следствия 2. Здесь достаточно показать, что многочлен д(х) имеет единственный корень в каждом из расширений ¥цкт, к =

1,2,..., ц- 2 , поля ¥чт, или, что равносильно ввиду доказанной теоремы,

,дкт-1

= «-1 -(-1)^*0 (16) при любом к = 1,2,... ^-2 . Для доказательства (16) предположим противное: пусть

Акд,т = 0 при некоторых к, ц, т (1 < к < 4-2).

Допустим, что хотя бы одно их к, ц или т, для которых имеет место (17), чётно. Тогда из (17) следует, что

i3-—- =0

ч-i

Так как

ik

4-1

= к (mod q-1),

то —- - целое число, что невозможно ввиду к<

q-1 и свойств числа i.

Предположим теперь, что любое из чисел к, q или т, для которых имеет место (17), нечётно. Тогда из (17) следует, что

iH _1 (mod qm-1). Если к = 1, то-делится на-и, следо-

2 д-1

вательно, (mod q-1), что, однако, невоз-

можно ввиду (¿,^р) = 1. Поэтому пусть к> 3. Нетрудно показать, что qkm-1 = k(qm-1) + c(q - 1){qm-1), где с - некоторое целое число. Тогда из (18) следует, что - нечётное число, но это

также невозможно ввиду к< q -1 и свойств числа i.

Поскольку предположение (17) приводит к противоречию, то имеет место (16).

Заключение

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

Авторы благодарны А.В. Клинову за полезное обсуждение результатов работы.

Литература

1. Э. Берлекэмп. Алгебраическая теория кодирования. -М.: Мир, 1971.

2. Кловис Виланова. О некоторых трёхчленных уравнениях над конечными полями. - Тр. Унив. дружбы народов им. П. Лумумбы, 1977, вып. 21, с. 17-31.

3. С. Ленг. Алгебра. - М.; Мир, 1968.

4. Н. Бурбаки. Алгебра. Многочлены и поля. Упорядоченные группы. - М.: Наука, 1965.

5. Ван дер Варден. Алгебра. - М.: Наука, 1976.

6. Chin-long Chen. Formulas for the solutions of quadratic equations over GF(2n). - IEEE Trans. Inform. Theory, 1982, v. 28, №5, pp. 792-794.

7. М. В. Матвеева. О решении уравнений третьей степени в поле характеристики 3. - Проблемы передачи информации, 1968, т. IV, вып. 4, с. 76-78.

8. В. С. Кугураков. Замечание о решении квадратных уравнений в конечном поле характеристики 2. Вероятностные методы и кибернетика, вып. 21, с. 107-108. -Казань: Изд-во Казанского университета, 1985.

9. В. С. Кугураков, А. П. Кирпичников Решение кубических уравнений в конечном поле характеристики 3. -

Вестник Технологического университета, т. 18, № 6, с. 221-222. - Казань: Изд-во КНИТУ, 2015.

10. А.Г. Курош Курс высшей алгебры. - М.: Физматгиз, 1962.

11. Д. Кокс, Дж. Литтл, Д.О' Ши. Идеалы, многообразия и алгоритмы. - М.: Мир, 2000.

12. P.A. Leonard. Quartics over GF(2n). - Proc. Amer. Math. Soc., 1972, v. 36, № 2, pp. 947-950.

13. L.E. Dickson. A fundamental system of invariants of the modular linear group with a solution of the form problem. -Trans. Amer. Math. Soc., 1911, v. 12, pp. 75-91.

14. А.А. Альберт. Конечные поля. - В кн.: Кибернетический Новая серия. - М.: Мир сборник., 1966, вып. 3, с. 7.

© В. С. Кугураков - канд. физ.-мат. наук, доцент кафедры теоретической кибернетики К(П)ФУ, Vladimir.Kugurakov@ksu.ru; А. П. Кирпичников - д-р физ.-мат. наук, зав. кафедрой интеллектуальных систем и управления информационными ресурсами КНИТУ, kirpichnikov@kstu.ru.

© V. S. Kugurakov - PhD, Associate Professor of the Department of Theoretical Cybernetics, K(P)FU, Vladimir.Kugurakov@ksu.ru; А. P. Kirpichnikov - Dr. Sci, Head of the Department of Intelligent Systems & Information Systems Control, KNRTU, kirpichnikov@kstu.ru.