WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

«САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ В. Ф. ГОРЬКОВОЙ ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ САНКТ– ПЕТЕРБУРГ 2004 УДК 519.8 Р е ц е н з е н т ы: проф. Чернецкий В. И. (Петрозав.гос. ун-т) проф. ...»

-- [ Страница 2 ] --

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

Пусть (m) = {C1, C2,..., Cm} минимальная m раскраска связного графа G = (X, F ), где X множество вершин графа G, Ci, i = 1, m, классы одноцветных вер шин, а F : X X отображение, при котором каждому x X отвечает подмножество F x X.

Пусть задан граф G = (Y, P ) и (m) его минималь ная раскраска. Будем говорить, что граф G = (X, F ) является гомоморфным образом графа G, если G по лучается из G в результате склеивания некоторых вер шин, принадлежащих одним и тем же классам раскрас ки (m). Описанное преобразование будем называть го моморфизмом : Y X.

Если G критический граф и m) его минимальная раскраска, приведенная относительно Cm, то Cm содер жит всего одну вершину x. Действительно, если бы в Cm имелось две вершины x и y, то, в силу инвариант ности фактор-степеней x и y относительно любых пре образований над (m) - Cm, одну из них можно было бы удалить из Cm, что не повлияло бы на хроматическое число графа G.

В частности, если G 3-критический граф и m = 3, 1r 2r то x C3 опирается на Z-ку r = (C12ZC12), кото 1r 2r рая содержит вершины y C12 и z C12 смежные с x, и вместе они образуют простой цикл нечетной длины.

А так как хроматическое число любого простого цик ла нечетной длины равно трем, то все 3-критические графы исчерпываются циклами нечетной длины.

Пусть теперь G = (X, F ) 4-критический граф и (4) = {C1, C2, C3, C4} его 2-приведенная относительно C4 и C1 минимальная раскраска.

Обозначим k GW(3) = x1kZx2kRx3kZx1k, k = 1, и k G(4)(x) = {x C4, GW(3) : x31Zx22, (5.2.1) x11SxSx21, x12SxSx32}.

На рисунке 5.5. изображен граф G(4)(x), у которого Z-ки обозначены ребрами.

Теорема 29. Если G = (X, F ) 4-критический граф, то он содержит подграф, с точностью до го моморфизма совпадающий с G(4)(x).

Д о к а з а т е л ь с т в о. Так как G критичес кий, то класс C4 содержит всего одну вершину x. В силу 2-приведенности (4), вершина x C4 опирается над каждой парой классов (C1, C2), (C1, C3), (C2, C3) на соответствующие Z-ки. А так как (4) приведена от носительно C1, то любая вершина из C1 опирается на Z-ку над (C2, C3).

11 21 11 Пусть Z-ки 1 = (C12ZC12), 1 = (C13ZC13), 2 = 12 13 12 22 12 (C12ZC12), 2 = (C13ZC13) такие, что (x11 = 11 11 12 C12 C13)Sx и (x12 = C12 C13)Sx, а Z-ки 2 = 22 32 21 (C23ZC23), 1 = (C23ZC23) такие, что x11Z(x21 = 21 21 32 32 C12 C23)Sx, x12Z(x32 = C13 C23)Sx, x11Z(x31 = C 31 22 C23), x12Z(x22 = C12 C23).

Очевидно, x31Zx11Zx21Rx31 и x32Zx12Zx22Rx32. Так как фактор-степень x C4 инвариантна относительно любых преобразований над (C1, C2, C3), то инверсия Z ки x11Zx31 не должна изменить фактор-степень x. Сле довательно, так как вершина x должна опираться после инверсии на Z-ку над (C1, C2), а в исходном графе она опирается на Z-ку над (C2, C3), должно выполняться, с точностью до гоморфизма (т.е.

склеивания всех вершин из C23 с вершинами из x31), соотношение x22Zx31, где x31 — результат указанного склеивания вершин.

Аналогично обстоит дело и с инверсией Z-ки x12Zx22. Только здесь склеиваются вершины из C23 с вершинами из x22.

Из приведенных соотношений следует, что k x3kZx1kZx2kRx3k = GW(3), k = 1, 2, и, с точностью до гомоморфизма, x31Zx22.

Следует заметить, что инверсия Z-ки, например, x12Zx22, превращает G(4)(x) в граф, гомеоморфный G(4)(x) = {x C4, GW(3) : x11SxSx31SxSx21}, во-первых. А во-вторых, из того, что x31Zx22, и x C должна опираться над (C2, C3) на Z-ку, следует, что вершина x может быть смежной со всеми вершинами 21 из C23 и C23.

Теорема 30. Граф G(4)(x) содержит подграф, стягиваемый к полному четырех вершинному графу F4.

Д о к а з а т е л ь с т в о. Пусть G(4)(x) зада ется формулой (5.2.1) (рис. 5.5), и (y x11)Sx, (z x21)Sx. Так как x32Rx22Zx31, то существует вершина t x31, связанная с x C4 простой цепью. А так как x11Zx21Rx31Zx11, то существует простой цикл над (C1, C2, C3) и вершины y x11, z x21, t x31, принад лежащие этому циклу, такие, что вершины y и y, z и z, t и t связаны между собой непересекающимися прос тыми цепями. Следовательно, вершина x связана с y, z и t непересекающимися простыми цепями. Таким обра зом, простой цикл, содержащий вершины y, z, t вместе с простыми цепями, связывающими эти вершины с x, образуют конструкцию, стягиваемую к F4.

k Обозначим через GW(4) k-ю конструкцию G(4)(x), у которой ребра инцидентные вершине x C5 заменены Z-ми 1, 1, 2, 2. Через k(r ) будем обозначать 41 42 43 41 ij k Z-ку над парой классов (Ci, Cj), принадлежащую GW(4).

j pr ir Пусть k(r ) = (k(Cij )Zk(Cijr)), где k(Cij ) подмно ij жество вершин из класса Cp, p = ij, порожденное раз биением двудольного подграфа графа G над (Ci, Cj) на некоторое количество Z-связных подмножеств, принад k лежащее GW(4), причем r = 1, 2 есть номер конструк r k ции GW(3), принадлежащей GW(4). Будем обозначать ее r k(GW(3)).

Положим k(1 ) k(1 ) k(2 ) k(2 ) = k(x41), 41 42 43 C4 C4 C где пересечение берется над C4.

В соответствии с вновь введенными обозначениями, k GW4 будет иметь вид k r GW4 = {k(x41) =, k(GW3 ) : k(x31)Zk(x22), k(x11)Z Zk(x41)Zk(x21), k(x12)Zk(x41)Zk(x32)}, r где k(GW3 ) = k(x3r)Zk(x1r)Zk(x2r)Rk(x3r), r = 1, 2.

Положим k GW(5)(x) = {x C5, GW(4) : 1(x41)SxS1(x11), k= 2(x41)SxS2(x21), 3(x41)SxS3(x32), 4(x41)SxS4(x12), (5.2.2) 2(x31)Z4(x22)Z1(x31)Z3(x22), 1(x21)Z2(x11), 3(x12)Z4(x32)}.

На рисунке 5.6. изображен граф G(5)(x), где ребра ми обозначены Z-ки, связывающие соответствующие k(xij), а светлыми кружочками обозначены вершины, смежные x C5.

Теорема 31. Если G 5-критический граф, то он содержит подграф, с точностью до гомоморфизма совпадающий с G(5)(x).

Д о к а з а т е л ь с т в о. Пусть (5) = {C1, C2, C3, C4, C5} 3-приведенная последовательно от носительно C5, C4, C1 минимальная раскраска графа G.

Так как G критический граф, то C5 содержит все го одну вершину x. В силу 3-приведенности (5), вер шина x C5 опирается над каждой парой классов (Ci, Cj), i > j, i, j {1, 4}, по крайней мере на одну Z-ку. В частности, так как (4) = {C1, C2, C3, C4} при ведена относительно C4, то предположим, что x C 41 опирается на Z-ки 1(1 ) = (1(C41)Z1(C41)), 2(1 ) = 41 41 21 42 (2(C42 )Z2(C42)), 3(2 ) = (3(C43)Z3(C43)), 4(2 ) = 43 42 (4(C41 )Z4(C41)).

Для каждой из указанных Z-к k(r ), существует 4j по крайней мере еще три Z-ки k(1 ), k(2 ) и k(2 ) 42 43 такие, что [k(x41)Sx] = k(1 ) k(1 ) k(2 ) k(2 ), 41 42 43 где пересечение берется над C4, опирается на конструк k цию, которая вместе с k(x41) есть GW(4).

3 Так как раскраска (5) - C3 = (4) является 2 приведенной последовательно относительно C5 и C4, то согласно теореме 31 имеем (xS1(x11))R(2(x21)Sx).

В силу тех же причин для раскраски (5) - C имеем 2(x21)R3(x32), а для раскраски (5) - C2 имеем 3(x32)R4(x12).

Так как фактор-степень x инвариантна относитель но любых преобразований над (C1, C2, C3, C4), то и ин версия Z-ки 1(x11)Z1(x31) не должна изменить фактор степень x. А это будет тогда, когда будет выполняться, с точностью до гомоморфмзма, соотношение [xS2(x21)]Z2(x11)Z1(x21)R1(x31)Z4(x22)Z[4(x12)Sx].

(5.2.3) Фактор-степень x C5 должна быть инвариантна и относительно инверсии Z-ки [xS1(x11)]R[2(x21)Sx]. В этом случае должно выполняться (с точностью до го моморфизма) соотношение [xS1(x11)Z1(x31)Z3(x22)R[3(x32)Sx], (5.2.4) так как (как и в первом случае над (C1, C2)) вершина x должна опираться над (C2, C3) после указанных инвер сий на Z-ку.

Точно так же инверсия Z-ки 3(x32)R4(x12) влечет (с точностью до гомоморфизма) соотношение [xS4(x12)]Z4(x22)Z2(x31)R[2(x21)Sx]. (5.2.5) Итак, из (5.2.3), (5.2.4), (5.2.5) имеем, с точностью до гомоморфизма, 2(x31)Z4(x22)Z1(x31)Z3(x22) и 1(x21)Z2(x11), 3(x12)Z4(x32).

Учитывая, что x C5 опирается на Z-ки 1(1 ), 2(1 ), 41 3(2 ), 4(2 ), имеем 43 1(x41)SxS1(x11), 2(x41)SxS2(x21), 3(x41)SxS3(x32), 4(x41)SxS4(x12).

Что и требовалось.

Теорема 32. Граф G(5)(x) содержит подграф, стягиваемый к F5.

Д о к а з а т е л ь с т в о. Пусть G(5)(x) задает k ся формулой (5.2.2). Рассмотрим GW(4) при k = 1. Так как 1(x11)SxS1(x41), то имеются некоторые вершины y1 1(x41) и z1 1(x11) такие, что y1SxSz1. Из того, что (xS2(x21))Z2(x11)Z1(x21), следует существование прос той цепи из вершины x C5 в вершину z2 1(x21). А из того, что (xS3(x32))R3(x22)Z1(x31) существует прос тая цепь из вершины x C5 в вершину z3 1(x31). Все указанные простые цепи не имеют общих вершин.

Так как 1(x41)Z1(x11), 1(x41)Z1(x32)R1(x22)Z1(x31), 1(x41) Z1(x21), то существуют непересекающиеся прос тые цепи из вершины y1 в вершины z1, z2 и z3, принад лежащие пересечениям Z-ок 1(1 ) 1(1 ) 1(1 ), 1(1 ) 1(1 ) 41 13 12 42 C1 C1 C 1(1 ), 1(1 ) 1(1 ) 23 13 C2 C соответственно.

А так как 1(x11)Z1(x31)R1(x21)Z1(x11), то существу ет простой цикл, содержащий вершины z1 1(x11), z 1(x21), z3 1(x31). Очевидно, z1 и z1, z2 и z2, z3 и z связаны непересекающимися простыми цепями. Таким образом, вершины x, y1, z1, z2, z3 вместе с простыми це пями, связывающими их, образуют подграф графа G, стягиваемый к F5.

АЛГЕБРА ЛОГИКИ 6.1. Функции алгебры логики Пусть U = {u1, u2,..., um,...} —исходный алфавит перемен ных. Будем рассматривать функции f(ui, ui,..., ui )(ui = ui при 1 2 n j k j = k), аргументы которых определены на множестве E2 = {0, 1}, и такие, что f(1, 2,..., n) E2, когда i E2(i = 1, 2,..., n).

Эти функции будем называть функциями алгебры логики или бу левыми функциями. В качестве переменных будем использовать символы x, y, z,..., а также эти символы с индексами. Функции алгебры логики будем задавать с помощью таблиц x1...xn-1xn f(x1,..., xn-1, xn) 0... 0 0 f(0,..., 0, 0) 0... 0 1 f(0,..., 0, 1) 0... 1 0 f(0,..., 1, 0).............

1... 1 1 f(1,..., 1, 1) Обозначим через P2 систему функций алгебры логики над ал фавитом U, содержащую константы 0 и 1.

О п р е д е л е н и е 53. Функция f(x1,..., xi-1, xi, xi+1,..., xn) из P2 зависит существенным образом от аргумента xi, ес ли существуют такие значения 1,..., i-1, i+1,..., n пере менных x1,..., xi-1, xi+1,..., xn, что f(1,..., i-1, 0, i+1,..., n) = f(1,..., i-1, 1, i+1,..., n).

В этом случае переменная xi называется существенной. Если xi не является существенной переменной, то она называется несу щественной или фиктивной.

О п р е д е л е н и е 54. Функции f1(x1,..., xn) и f2(x1,..., xn) называются равными, если функцию f2 можно получить из f путем добавления или изъятия фиктивных аргументов.

Функции тождественно равные 0 и тождественно равные 1 не содержат существенных переменных.

Приведем примеры ««элементарных»» функций 1) f1(x) = 0 — константа 0;

2) f2(x) = 1 — константа 1;

3) f3(x) = x — тождественная функция;

4) f4(x) = x — отрицание x;

5) f5(x1, x2) = (x1&x2) — конъюнкция x1 и x2 или логическое умножение;

6) f6(x1, x2) = (x1x2) — дизъюнкция x1 и x2 или логическое сложение;

7) f7(x1, x2) = (x1 x2) —импликация x1 и x2 или логичес кое следование;

8) f8(x1, x2) = (x1 + x2) — сложение по mod 2;

9) f9(x1, x2) = (x1/x2) —функция Шеффера.

В следующих таблицах приводятся значения перечисленных функций.

x 0 1 x x 0 0 1 0 1 0 1 1 x1 x2 (x1&x2) (x1 x2) (x1 x2) (x1 + x2) (x1|x2) 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 Здесь (x1&x2) = min(x1, x2) = (x1 · x2), (x1 x2) = max(x1, x2).

6.2. Формулы и функции О п р е д е л е н и е 55. Пусть P — некоторое подмно жество функций из P2.

a) Б а з и с и н д у к ц и и. Каждая функция f(x1,..., xm) из P называется формулой над P.

б) И н д у к т и в н ы й п е р е х о д. Пусть f(x1,..., xm) — функция из P и A1,..., Am — выражения, являющиеся либо форму лами над P, либо символами переменных из U. Тогда выражение f(A1,..., Am) называется формулой над P.

П р и м е р 20. Пусть P — множество ««элементарных»» функций. Следующие выражения являются формулами над P:

1) {[(x1x2) + x1] + x2};

2) [xx(x2 + x3)];

3) {x1 [(x2 x3)(x3 x2)]}.

В дальнейшем запись A[f1,..., fs] означает, что формула A по строена из f1,..., fs. А запись A(x1,..., xn) означает, что при по строении формулы A использовались переменные x1,..., xn. Пусть A — произвольная формула над P, тогда формулы, которые ис пользовались для ее построения, будем называть подформулами формулы A.

О п р е д е л е н и е 56. Говорят, что формула B = B[g1,..., gs], gi = gi(x1,...xn) имеет то же строение, что и фор мула A = A[f1,..., fs], fi = fi(x1,..., xn), i = 1, s, если формула B f1 f2....fs получена из формулы A путем замены g1 g2....gs.

П р и м е р 21.

1) D = {x1, (x1&x2)}, A = [x1&(x2&x3)];

2) D = {x1, (x1 x2)}, B = [x1 (x2 x3)].

Очевидно, что A и B имеют одинаковое строение.

Строение формулы будем обозначать через C и писать A = C[f1,..., fs]. Каждая формула однозначно определяется своим стро ением и упорядоченной совокупностью {f1, f2,..., fs}.

Сопоставим теперь каждой формуле A(x1,..., xn) над P функ цию f(x1,..., xn) из P2 с помощью индукции следующим образом.

а) Б а з и с и н д у к ц и и. Если A(x1,..., xn) = f(x1,..., xn), где f P, то формуле A(x1,..., xn) сопоставим функ цию f(x1,..., xn).

б) И н д у к т и в н ы й п е р е х о д. Пусть A(x1,..., xn) = f0(A1,..., Am), где Ai(i = 1,..., m) являются либо формулами над P, либо символами переменной xj(i). Тогда по предположению ин дукции Ai сопоставлена либо функция fi из P2, либо тождествен ная функция fi = xj(i). Сопоставим формуле A(x1,...xn) функцию f(x1,..., xn) = f0(f1,..., fm).

Если функция f соответствует формуле A, то говорят, что фор мула A реализует функцию f.

Функцию f, соответствующую формуле A, будем называть су перпозицией функций из P, а процесс получения функции f из P будем называть операцией суперпозиции.

П р и м е р 22. Пусть f3(x1, x2, x3) = {x1 [(x2 x3)(x3 x2)]} функция, соответствующая формуле из примера 17.

Для нахождения функции f3, будем искать те наборы значе ний переменных x1, x2, x3, на которых функция принимает значе ние 1. Очевидно, это равносильно определению значений перемен ных, при которых формула {x1 [(x2 x3)(x3 x2)]} равна 0. Последнее имеет место при x1 = 0 и в тех случаях, когда [(x2 x3)(x3 x2)] обращается в 0. Наконец, формула [(x2 x3)(x3 x2)] обращается в 0, когда по крайней мере одна из формул (x2 x3), (x3 x2) обращается в 0, что имеет мес то при x2 = 1, x3 = 0, или при x2 = 0, x3 = 1. Таким образом, f(x1, x2, x3) равна 1 на наборах (001) и (010).

6.3. Эквивалентность. Принцип двойственности.

О п р е д е д е л е н и е 57. Формулы A и B над P называются эквивалентными, в этом случае мы пишем A = B, если соответствующие им функции fA и fB равны.

П р и м е р 23.

0 = (x&x), (x1(x2 + x3)) = {x1 [(x2 x3)(x3 x2)]}, (x y) = (y x).

Обозначим через (x1 x2) любую из функций (x1&x2), (x x2), (x1 + x2).

1. Функция (x1 x2) обладает свойством ассоциативности:

((x1 x2) x3) = (x1 (x2 x3)).

2. Функция (x1 x2) обладает свойством коммутативности:

(x1 x2) = (x2 x1).

3. Для конъюнкции и дизъюнкции выполняются дистрибутив ные законы:

((x1 x2)&x3) = ((x1&x3) (x2&x3)), ((x1&x2) x3) = ((x1 x3)&(x2 x3)).

4. Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:

x = x, (x1&x2) = (x1 x2), (x1 x2) = (x1&x2).

5. Выполняются следующие свойства конъюнкции и дизъюнк ции:

(x&x) = x, (x x) = x, (x&x) = 0, (x x) = 1, (x&0) = 0, (x 0) = x, (x&1) = x, (x 1) = 1.

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

П р и м е р 24.

x1 x1x2 = x1 · 1 x1x2 = x1(x2 x2) x1x2 = = x1x2 x1x2 x1x2 = x1x2 x1x2 x1x2 = = x1x2 x1x2 = x1(x2 x2) = x1 · 1 = x1.

Таким образом, x1 x1x2 = x1, т.е. получаем правило поглоще ния произведения x1x2 множителем x1. Здесь x1x2 = x1&x2.

Существует еще один способ получения тождеств. Он основан на использовании так называемого принципа двойственности.

О п р е д е л е н и е 58. Функция [f(x1,..., xn)] = f(x1,..., xn), называется двойственной функцией к функции f(x1,..., xn).

Для простоты будем обозначать двойственную функцию через f(x1,..., xn).

Легко видеть, что функция 0 двойственна 1, функция 1 двойственна 0, функция x двойственна x, функция x двойственна x, функция x1&x2 двойтсвенна x1 x2, функция x1 x2 двойственна x1&x2.

Из определения двойственности вытекает, что f = (f) = f, т.е. функция f является двойственной к f.

Пусть (x1i,..., x1p ) (x1,..., xn), i = 1, m.

i Теорема 33. Если (x1,..., xn) = f(f1(x11,..., x1p ),..., fm(xm1,..., xmp )) 1 m, то (x1,..., xn) = f(f1 (x11,..., x1p ),..., fm(xm1,..., xmp )).

1 m Д о к а з а т е л ь с т в о.

(x1,..., xn) = (x1,..., xn) = = f(f1(x11,..., x1p ),...fm(xm1,..., xmp )) = 1 m = f(f1(x11,..., x1p ),..., fm(xm1,..., xmp )) = 1 m = f(f1(x11,..., x1p ),..., fm(xm1,..., xmp )) = 1 m = f(f1 (x11,..., x1p ),...fm(xm1,..., xmp )).

1 m Из теоремы вытекает П р и н ц и п д в о й с т в е н н о с т и. Если форму ла A = C[f1,..., fs] реализует функцию f(x1,..., xn), то формула C[f1,..., fs ] реализует функцию f(x1,..., xn).

Эту формулу мы будем называть формулой, двойственной к A, и обозначать через A. Таким образом, A = C[f1,..., fs ].

П р и м е р 25.

1) A1(x1, x2) = x1&x2, A(x1, x2) = x1 x2;

2) A2(x1, x2) = x1x2 x1x2, A(x1, x2) = (x1 x2)(x1 x2).

6.4. Совершенная дизъюнктивная нормальная форма Введем обозначение x = x x, где — параметр, равный 0, либо 1. Очевидно, что x при = 0, x = x при = 1.

Очевидно, что x = 1 тогда и только тогда, когда x =.

Теорема 34 (о разложении функций по переменным). Каж дую функцию алгебры логики f(x1,..., xn) при любом m(1 m n) можно представить в следующей форме:

f(x1,..., xm, xm+1,..., xn) = (*) m = x &... &x &f(1,..., m, xm+1,..., xn), 1 m (1,...,m) где дизъюнкция берется по всевозможным наборам значений переменных x1,..., xm.

Д о к а з а т е л ь с т в о. Рассмотрим произвольный набор значений переменных (1,..., n) и покажем, что левая и правая части соотношения () принимают на нем одно и то же значение.

Левая часть дает f(1,..., n). Правая — m 1 &... &m &f(1,..., m, m+1,..., n) = (1,...,m) 1 m = 1 &... &m &f(1,..., m, m+1,..., n) = f(1,..., n).

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

1) Разложение по одной переменной:

f(x1,..., xn-1, xn) = = xn&f(x1,..., xn-1, 1) xn&f(x1,..., xn-1, 0).

2) Разложение по всем переменным:

n f(x1,..., xn) = x &... &x &f(1,..., n).

1 n (1,...,n) При f(x1,..., xn) 0 оно может быть преобразовано:

1 n n x &...&x &f(1,..., n) = x &...&x.

1 n 1 n (1,...,n) (1,...,n) f(1,...,n)= В результате окончательно получим 1 n f(x1,..., xn) = x &... &x. () 1 n (1,...,n) f(1,...,n)= Такое разложение носит название совершенной дизъюнктивной нормальной формы (совершенной д.н.ф.).

Теорема 35. Каждая функция алгебры логики может быть выражена в виде формулы через отрицание, конъюнкцию и дизъ юнкцию.

Д о к а з а т е л ь с т в о. 1) Пусть f(x1,..., xn) 0. Тогда, очевидно, f(x1,..., xn) = x1&x1.

2) Пусть f(x1,..., xn) 0. Представим ее в совершенной д.н.ф.:

1 n f(x1,..., xn) = x &... &x.

1 n (1,...,n) f(1,...,n)= Таким образом, в обоих случаях функция f выражается в виде формулы через отрицание, конъюнкцию и дизъюнкцию.

П р и м е р 26. Записать совершенную д.н.ф. для функции, заданной следующей таблицей x1 x2 x3 f(x1, x2, x3) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Согласно теореме имеем f(x1, x2, x3) = x1x2x3 x1x2x3 x1x2x3 x1x2x3.

Это разложение есть выражение типа. Построим разложе ние типа, при условии, что f(x1,..., xn) 1. Для этого разло жим функцию f в совершенную д.н.ф.:

1 n f(x1,..., xn) = x &... &x.

1 n (1,...,n) f(1,...,n)= Применим операцию * к данному равенству, получим 1 n f(x1,..., xn) = & (x... x ).

1 n (1,...,n) f(1,...,n)= Левая часть есть f(x1,..., xn), а правая может быть преобразо вана далее:

1 n 1 n & (x... x ) = & (x... x ) = 1 n 1 n (1,...,n) (1,...,n) f(1,...,n)=1 f(1,...,n)= 1 n = & (x... x ).

1 n (1,...n) f(1,...,n)= Таким образом, получаем разложение 1 n f(x1,..., xn) = & (x... x ).

1 n (1,...,n) f(1,...,n)= Это выражение носит название совершенной конъюктивной нор мальной формы (совершенной к.н.ф.).

П р и м е р 27. Построить совершенную к.н.ф. для функции f(x1, x2, x3), заданной таблицей в примере 26.

Имеем f(x1,..., xn) = = (x1 x2 x3)(x1 x2 x3)(x1 x2 x3)(x1 x2 x3).

6.5. Полнота. Замкнутость О п р е д е л е н и е 59. Система функций {f1, f2,..., fs,..} из P2 называется (функционально) полной, если любая булева функ ция может быть записана в виде формулы через функции этой системы.

Рассмотрим примеры полных систем.

1. Система P2 — множество всех булевых функций — является полной системой.

2. Система P = {x, x1&x2, x1 x2} представляет полную систему.

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

Теорема 36. Пусть даны две системы функций из P2:

P = {f1, f2,...}, (I) Q = {g1, g2,...}, (II) относительно которых известно, что система (I) полна и каж дая ее функция выражается в виде формулы через функции сис темы (II). Тогда система (II) является полной.

Д о к а з а т е л ь с т в о. Пусть h — произвольная функция из P2. В силу полноты системы (I), функцию h можно выразить формулой над P, т.е.

h = C[f1, f2,..., fs,...] По условию теоремы f1 = C1[g1, g2,... ], f2 = C2[g1, g2,... ],.........

Поэтому мы можем в формуле C[f1, f2,...] исключить вхождения функций f1, f2,..., заменив их формулами над Q. Это можно зпи сать так:

C[f1, f2,...] = C[C1[g1, g2,...], C2[g1, g2,...],...].

Последнее выражение определяет формулу над Q со строением C. Мы получаем C[C1[g1, g2,...], C2[g1, g2,...],...] = C[g1, g2,...], или, окончательно, h = C[g1, g2,...], т.е. мы варазили h в виде формулы над Q. Теорема доказана.

Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем.

3. Система P = {x, x1&x2} является полной. Для доказатель ства возьмем за систему (I) систему 2., а за систему (II) — сис тему 3. и используем тождество x1 x2 = x1&x2, которое выткает из свойства 4 элементарных функций.

4. Система P = {x, x1 x2} является полной.

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

5. Система P = {x1/x2} является полной.

Для доказательства за систему (I) возьмем систему 3., а за сис тему (II) — систему 5. Легко видеть, что x1/x1 = x1, (x1/x2)/(x1/x2) = x1/x2 = x1&x2.

6. Система P = {0, 1, x1x2, x1 + x2( mod 2)} является полной.

Для доказательства опять за систему (I) возьмем систему 3., а засистему (II) — систему 6. Мы имеем x1 + 1 = x1, x1x2 = x1&x2.

Так как формула, построенная из констант 0, 1 и функций x1x и x1 + x2, после раскрытия скобок и несложных алгебраических преобразований переходит в полином по mod 2, мы получаем сле дующую теорему, принадлежащую И. И. Жегалкину.

Теорема 37. Каждая функция из P2 может быть выражена при помощи полинома по mod 2 (полинома Жегалкина).

a x x..., x mod 2.

i1...is i1 i2 is (i1,...,is) Д о к а з а т е л ь с т в о. Доказательство теоремы сводится к подсчету числа полиномов Жегалкина от переменных x1, x2,..., xn.

Если их число окажется равным числу функций из P2, то теорема будет доказана. Действительно, с одной стороны, если f P2, f = f(x1, x2,..., xn), то всего наборов (1,..., n) значений переменных (x1,..., xn) столько, сколько функций из множества X = (x1,..., xn) в множество 2 = {0, 1}, т.е. |2X| = |2||X| = 2n.

Каждой функции f P2 можно сопоставить во взаимно одно значное соответствие набор из 2n компонент значений функции f.

Таким образом, всего функций алгебры логики столько, сколько функций из множества Y = 2X в множество 2, т.е. |2Y | = |2||Y | = n 22.

С другой стороны, количество слагаемых у полинома Же галкина столько, сколько подмножеств (i1, i2,..., is) в множестве (1,..., n). Каждому набору (i1,..., is) поставим в соответствие на бор (1,..., n)s, содержащий s единиц на местах i1,...is, s = 1, n.

Тогда подмножеств (i1,..., is) (1,..., n) столько, сколько наборов (1,..., n) из нулей и единиц. А их столько, сколько функций из множества X, содержащего n элементов в множество 2 = {0, 1}, т.е. |2X| = 2n. Каждому полиному можно поставить в соответствие набор из 2n компонент — коэффициентов полинома. Всего полино мов столько, сколько функций из множества Y = 2X в множество n 2, т.е. |2Y | = |2||Y | = 22. Теорема доказана.

П р и м е р 28. Выразить функцию x1 x2 в виде полинома Жегалкина.

Общий вид полинома Жегалкина от двух переменных имеет вид x1 x2 = ax1x2 + bx1 + cx2 + d.

При x1 = x2 = 0 имеем 0 = d, при x1 = 0, x2 = 1 имеем 1 = c, при x1 = 1, x2 = 0 имеем 1 = b, при x1 = x2 = 1 имеем 1 = a + d + c, т.е. a = 1.

Таким образом, x1 x2 = x1x2 + x1 + x2.

С понятием полноты тесно связано понятие замыкания и замк нутого класса.

О п р е д е л е н и е 60. Пусть M — некоторое подмно жество функций из P2. Замыканием M называется множество всех булевых функций, представимых в виде формул через функ ции из множества M. Замыкание множества M обозначается через [M].

П р и м е р 29.

1) M = P2. Очевидно, [M] = P2.

2) M = {1, x1 + x2}. Замыканием этого множества будет класс L всех линейных функций, т.е. функций, имеющих вид f(x1,..., xn) = c0 + c1x1 +... + cnxn( mod 2), где ci = 0 1 (i = 0, 1,..., n).

Отметим некоторые свойства замыкания:

1) [M] M;

2) [[M]] = [M];

3) если M1 M2, то [M] [M];

4) [M1 M2] [M1] [M2].

О п р е д е л е н и е 61. Множество M называется замк нутым, если [M] = M.

1) Класс M = P2 является замкнутым классом.

2) Класс M = {1, x1 + x2} не замкнут.

3) Класс L замкнут, так как линейная комбинация линейных функций является линейной функцией.

Система функций M является полной, если [M] = P2.

6.6. Важнейшие замкнутые классы. Теорема о полноте Перечислим некоторые важнейшие замкнутые классы в P2.

1. Обозначим через T0 класс всех булевых функций f(x1,..., xn), сохраняющих константу 0, т.е. функций, для которых выполнено равенство f(0,..., 0) = 0.

Легко видеть, что функции 0, x, x1&x2, x1 x2, x1 + x2 принад лежат классу T0, а функции 1, x не входят в T0.

Поскольку таблица для функций f из класса T0 в первой строке n содержит значение 0, то в T0 содержится ровно (1/2)22 булевых функций, зависящих от переменных x1,..., xn.

Покажем, что T0 — замкнутый класс. Так как T0 содержит тож дественную функцию, то для обоснования замкнутости T0 доста точно показать, что функция = f(f1,..., fm) принадлежит классу T0, если f, f1,..., fm принадлежат классу T0.

Последнее вытекает из цепочки равенств (0,..., 0) = f(f1(0,..., 0),..., fm(0,..., 0)) = = f(0,..., 0) = 0.

2. Обозначим через T1 класс всех булевых функций f(x1,..., xn), сохраняющих константу 1, т.е. функций, для которых выполнено равенство f(1,..., 1) = 1.

Легко видеть, что функции 1, x, x1&x2, x1 x2 принадлежат классу T1, а функции 0, x не входят в класс T1.

В силу того, что класс T1 состоит из функций, двойственных функциям из класса T0, нетрудно перенести результаты о классе n T0 на класс T1. Класс T1 содержит (1/2)22 функций, зависящих от переменных x1,..., xn, и является замкнутым классом.

3. Обозначим через S класс всех самодвойственных функций, т.е. функций f из P2, таких, что f = f.

Очевидно, что самодвойственными функциями будут x, x. Ме нее тривиальным примером самодвойственной функции является функция h(x1, x2, x3) = x1x2 x1x3 x2x3:

h(x1, x2, x3) = (x1 x2)(x1 x3)(x2 x3) = = x1x2 x1x3 x2x3 = h(x1, x2, x3).

Для самодвойственных функций имее место тождество f(x1,..., xn) = f(x1,..., xn);

иначе говоря, на противоположных наборах (1,..., n) и (1,..., n) самодвойственная функция принимает противоположные значе ния. Отсюда следует, что самодвойственная функция полностью определяется своими значениями на половине строк таблицы, зада ющей функцию. Поэтому число самодвдойственных функций, за n- n висящих от переменных (x1,..., xn), равно 22 = 22.

Докажем теперь, что класс S замкнут. Поскольку класс S содер жит тождественную функцию, достаточно показать, что функция = f(f1,..., fm) является самодвойственной, если f, f1,..., fm самодвойственны. По следнее устанавливается непосредственно:

= f(f1,..., fm) = f(f1,..., fm) =.

Лемма 7. (о несамодвойственной функции). Если f(x1,..., xn) / S, то из нее путем подстановки функций x и x можно получить константу.

Д о к а з а т е л ь с т в о. Так как f S, то найдется набор / (1,..., n), такой, что f(1,..., n) = f(1,..., n).

i Рассмотрим функции i(x) = x (i = 1,..., n) и положим (x) = f(1(x),..., n(x)).

Мы имеем 1 n (0) = f(1(0),..., n(0)) = f(0,..., 0 ) = 1 n = f(1,..., n) = f(1,..., n) = f(1,..., 1 ) = = f(1(1),..., n(1)) = (1).

Лемма доказана.

4. Обозначим = (1,..., n), = (1,..., n) и f(1,..., n) = f().

О п р е д е л е н и е 62. Для двух наборов = (1,..., n) и = (1,..., n) выполнено отношение предшествования, если 1 1,..., n n.

Например, (0, 1, 0, 1) (1, 1, 0, 1).

Очевидно, что если и, то.

О п р е д е л е н и е 63. Функция f(x1,..., xn) называется монотонной, если для любых двух наборов и ( ), имеет место неравенство f() f().

Монотонными функциями, очевидно, будут 0, 1, x, x1&x2, x1 x2.

Обозначим через M множество всех монотонных функций. По кажем, что класс монотонных функций замкнут. Поскольку тож дественная функция принадлежит классу M, то для установления замкнутости M достаточно показать, что = f(f1,..., fm) является монотонной, если f, f1,..., fm монотонны. Пусть m x = (x1,..., xn), x = (x11,..., x1p ),..., x = (xm1,..., xmp ) 1 m — наборы переменных функций, f1,..., fm, причем множество пе ременных функции состоит из тех и только тех переменных, которые встречаютсч у функций f1,..., fm. Пусть и — два на бора длины n значений переменных x, причем. Эти на m m боры определяют наборы,,...,, значений переменных m m m 1 x,..., x, такие, что,...,. В силу монотонности функций f1,..., fm m m f1( ) f1( ),..., fm( ) fm( ).

Поэтому m m (f1( ),..., fm( )) (f1( ),..., fm( )), и в силу монотонности f имеем m m f(f1( ),..., fm( )) f(f1( ),..., fm( )), Откуда получаем () ().

Будем называть наборы и соседними по i-ой координате, если = (1,..., i-1, i, i+1,..., n), = (1,..., i-1, ii+1,..., n).

Лемма 8. ( о немонотонной функции). Если f(x1,..., xn) M, / то из нее путем подстановки констант 0 и 1 и функции x можно получить функцию x.

Д о к а з а т е л ь с т в о. Сначала покажем, что найдется пара соседних наборов и, таких, что и f() > f() В самом деле, так как f M, то существуют наборы и / 1 1 1 1 1, такие, что и f( ) > f( ). Если наборы и — соседние, то наша цель достигнута. Если и не являются соседними, то набор отличается от набора в t координатах, где t > 1, причем эти t координат в наборе имеют значение 0, а 1 в наборе — 1. В силу этого между и можно вставить t - t 2 промежуточных наборов,,...,, Таких, что t 1 2....

Очевидно, что наборы, стоящие в этой цепочке рядом, будут со седними. Так как f( ) > f( ), то по крайней мере на одной из этих пар соседних наборов — обозначим их через и ( ) — будет f() > f(). Предположим, что данные наборы имеют соседство по i-ой координате и, следовательно, = (1,..., i-1, 0, i+1,..., n), = (1,..., i-1, 1, i+1,..., n).

Рассмотрим функцию (x) = f(1,..., i-1, x, i+1,..., n).

Мы имеем (0) = f(1,..., i-1, 0, i+1,..., n) = f() > f() = = f(1,..., i-1, 1, i+1,..., n) = (1).

Последнее означает, что (0) = 1, а (1) = 0, т.е. (x) = x.

Лемма доказана.

5. Последним классом является класс L всех линейных функ ций.

Он, очевидно, содержит константы 0, 1, тождественную функ цию x, функции x, x1 + x2 и не содержит функции x1&x2 и x1 x2.

Ранее было показано, что этот класс также замкнут.

Лемма 9. (о нелинейной функции). Если f(x1,..., xn) L, то / из нее путем подстановки констант 0 и 1 и функции x и x, а также, может быть, путем навешивания отрицания над f, можно получить функцию x1&x2.

Д о к а з а т е л ь с т в о. Возьмем полином Жегалкина для f:

f(x1,..., xn) = ai...isxi · · · xi.

1 1 s (i1,...,is) В силу нелинейности полинома в нем найдется член, содержащий не менее двух множителей. Без ограничения общности можно счи тать, что среди этих множителей присутствуют x1 и x2. Тогда можно преобразовать полином следующим образом:

ai...isxi · · · xi = x1x2f1(x3,..., xn)+ 1 1 s (i1,...,iis ) +x1f2(x3,..., xn) + x2f3(x3,..., xn) + f4(x3,..., xn), где, в силу единственности полинома, f1(x3,..., xn) 0.

Пусть 3,..., n таковы, что f1(3,..., n) = 1. Тогда (x1, x2) = f(x1, x2, 3,..., n) = x1x2 + x1 + x2 +, где,, — константы, равные 0 или 1. Рассмотрим функцию (x1, x2), получаемую из (x1, x2) следующим образом:

(x1, x2) = (x1 +, x2 + ) + +.

Очевидно, что (x1 +, x2 + ) + + = (x1 + )(x2 + )+ +(x1 + ) + (x2 + ) + + + = x1x2.

Следовательно, (x1, x2) = x1&x2.

Лемма доказана.

Теорема 38. (о функциональной полноте). Для того, чтобы система функций P из P2 была полной необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкну тых классов T0, T1, S, M и L.

Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. Пусть система P полна, т.е. [P] = P2. Допустим, что P содержится в одном из указанных классов — обозначим его через N, т.е. P N. Тогда в силу свойств замыкания и замкнутости N имеем P2 = [P] [N] = N.

Значит N = P2, что не так. Необходимость доказана.

Д о с т а т о ч н о с т ь. Пусть P целиком не содержится ни в одном из пяти указанных классов. Тогда из P можно выде лить подсистему P, содержащую не более пяти функций, которая также обладает этим свойством. Для этого возмем в P функции fi, fj, fk, fm, fl, которые не принадлежат соответственно классам T0, T1, S, M и L, и положим P = {fi, fj, fk, fl, fm}.

Можно считать, что все эти функции зависят от одних и тех же переменных x1,..., xn.

Доказательство достаточности будет проводится в три этапа.

I. Построение при помощи функций fi, fj, и fk констант 0 и 1.

Рассмотрим функцию fi T0. Возможны два случая:

/ 1. fi(1,..., 1) = 1. Тогда (x) = fi(x,..., x) есть константа 1, ибо (0) = fi(0,..., 0) = 1, (1) = fi(1,..., 1) = 1.

Вторая константа получается из fj : fj(1,..., 1) = 0.

2. fi(1,..., 1) = 0. Тогда (x) = fi(x,..., x) есть x, ибо (0) = fi(0,..., 0) = 1, (1) = fi(1,..., 1) = 0.

Возьмем fk(fk S). Так как мы имеем x, то в силу леммы 7 из fk / мы можем получить константу. Поскольку мы располагаем x, то находим и вторую константу. Итак, в обоих случаях мы получаем константы 0 и 1.

II. Построение при помощи констант 0, 1 и функции fm функ ции x. Это осуществляется на основе леммы 8.

III. Построение при помощи констант 0, 1 и функции x и fl функции x1&x2. Это осуществляется на основе леммы 9.

Таким образом, мы при помощи формул над P (а значит и над P) реализовали функции x и x1&x2. Этим достаточность доказана.

С л е д с т в и е 1. Всякий замкнутый класс M функций из P2 такой, что M = P2, содержится по крайней мере в одном из построенных классов.

П р и м е р 30. Покажем, что система функций f1 = x1x2, f2 = 0, f3 = 1, f4 = x1 + x2 + x3( mod 2) является полной.

Мы имеем: f3 T0, f2 T1, f2 S, f4 M, f1 L. С другой сто / / / / / роны, удаление любой из функций приводит к неполной системе:

{f2, f3, f4} L, {f1, f3, f4} T1, {f1, f2, f4} T0, {f1, f2, f3} M.

С л е д с в и е 2. Из всякой полной в P2 системы P функ ций можно выделить полную подсистему, содержащую не более четырех функций.

Д о к а з а т е л ь с т в о. Мы видели, что из P можно выде лить полную подсистему P, содержащую не более пяти функций.

Оказывается, что функция fi T0, кроме того, либо не самодвой / ственна (случай 1)), так как fi(0,..., 0) = f(1,..., 1), либо не моно тонна (случай 2)): fi(0,..., 0) > fi(1,..., 1). Поэтому полной будет либо система {fi, fj, fm, fl}, либо система {fi, fj, fk, fl}.

ПОЛЯ ГАЛУА 7.1. Идеалы. Классы вычетов О п р е д е л е н и е 64. Группой G называется совокупность элементов, над которой определена одна операция (сложения или умножения), такая, что 1. Для любых a, b G, a · b и b · a G – замкнутость.

2. a · (b · c) = (a · b) · c — ассоциативность.

3. Существует элемент e G, такой, что для любых a G, e · a = a · e = a.

4. Для любых a G существует b G, такой, что a · b = b · a = e. Элемент b называется обратным, т.е. b = a-1.

Группа называется абелевой, если групповая операци коммута тивна, т.е. a · b = b · a.

Подгруппой группы G называется подмножество G G, обла дающее свойствами группы.

О п р е д е л е н и е 65. Кольцом R называется множество элементов, над которыми определены две операции сложение и умножение, такие, что 1. Множество R является абелевой группой относительно операции сложения, т.е. аддитивной абелевой группой.

2. Для любых a, b R произведение a · b R — замкнутость.

3. Для любых a, b, c R выполняется равенство a · (b · c) = (a · b) · c — ассоциативность.

4. Для любых a, b, c R справедливы равенства a · (b + c) = a · b + a · c и (b + c) · a = b · a + c · a — дистрибутивность.

Кольцо называется коммутативным, если коммутативна опера ция умножения, т.е. если для любых a, b R выполняется равен ство a · b = b · a.

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

Множество, состоящее только из одного нулевого элемента, является кольцом, операции в котором определяются правилами 0 + 0 = 0, 0 · 0 = 0.

О п р е д е л е н и е 66. Полем называется коммутатив ное кольцо с единичным элементом относительно умножения, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент.

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

О п р е д е л е н и е 67. Идеалом I называется подмножес тво элементов кольца R, обладающее следующими двумя свой ствами:

1) I является подгруппой аддитивной группы кольца R, 2) для любого элемента a I и любого элемента r R произведения a · r и r · a принадлежат I.

Так как I — подгруппа, то если r — произвольный элемент из R, тогда совокупность r + I всевозможных сумм вида r + i;

i I называется левым смежным классом, или в нашем случае клас сом вычетов. Учитывая, что если r I, то r + I = I, получаем разложение аддитивной группы кольца R по подгруппе I, когда r пробегает все R. Введем обозначение r +I = {r} — класс вычетов.

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

{r} + {s} = {r + s}.

Действительно, {r} = I + r, {s} = I + s, а так как сложение коммутативно, то I + r + I + s = I + r + s = {r + s}.

Здесь {r} обозначает класс вычетов, содержащий r.

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

Пусть r и r принадлежат одному классу вычетов, а s и s дру гому, тогда K называется произведением классов вычетов {r} и {s}, если rs и rs принадлежат K.

Действительно, если r и r, s и s принадлежат соответственно своим классам, то rs и rs принадлежат одному и тому же классу тогда и только тогда, когда rs - rs принадлежат идеалу, но rs - rs = rs - rs + rs - rs = r(s - s) + (r - r)s так как s - s и r - r принадлежат идеалу, то и оба слагаемых принадлежат идеалу, т.е. и rs - rs принадлежат идеалу.

Имеет место дистрибутивность {a}({b} + {c}) = {a}{b + c} = {a(b + c)} = {ab} + {ac} = ={a}{b} + {a}{c}.

Аналогично проверяется ассоциативность.

Таким образом, классы вычетов по идеалу I образуют кольцо — кольцо классов вычетов.

Пусть R — кольцо целых чисел. Тогда Теорема 39. Подмножество из R образует идеал тогда и только тогда, когда оно состоит из чисел кратных некоторому целому числу.

Д о к а з а т е л ь с т в о. Действительно, пусть r наименьшее целое положительное число в идеале, а s — любое другое целое число идеала. Если d — наибольший общий делитель r и s, то d = ar + bs и d принадлежит идеалу, так как ar и bs принадлежат идеалу. Так как r — наименьшее целое положительное число идеала, то r d, а так как r делится на d, то r = d.

Следовательно, любое целое число из идеала делится на r.

И наоборот, любое число кратное r, принадлежит идеалу по определению идеала.

Идеал, состоящий из всех чисел, кратных положительному це лому числу m, обозначается через (m). Кольцо классов вычетов, образованное классами вычетов по идеалу (m), называется коль цом целых чисел по модулю m.

Теорема 40. Кольцо классов вычетов по модулю m образует поле тогда и только тогда, когда m — простое число.

Д о к а з а т е л ь с т в о. Если m — не простое число, то m = rs для некоторых целых чисел r и s, которые не кратны m.

Поэтому {r}{s} = {m} = 0, и если класс вычетов {r} обладает обратным {r-1}, то {r-1}{r}{s} = {s} = {r-1}0 = 0, что противо речит предположению. Поэтому класс вычетов {r} не может иметь обратного, и кольцо классов вычетов не является полем.

Остается доказать, что если m — простое число, то для каждого класса вычетов, кроме 0 (идеала), существует обратный. Каждый такой класс вычетов содержит целое число s, которое меньше чем m и не равно 0. Поскольку 1 совпадает с обратным к ней элемен том, можно предполагать, что s > 1. Так как m по предположению — простое число, то наибольший общий делитель s и m должен быть равен либо m, либо 1. Поэтому наибольший общий делитель m и s равен 1. Таким образом 1 = am + bs, и отсюда следует, что {b}{s} = 1, т.е. класс вычетов {b}, является обратным к классу вычетов {s}. Что и требовалось доказать.

Построенные таким образом поля называются простыми поля ми или полями Галуа из p элементов GF (p).

7.2. Идеалы и классы вычетов многочленов Рассмотрим теперь многочлены f(X) одного переменного X с коэффициентами из некоторого поля F :

f(X) = f0 + f1X + f2X2 +... + fnXn.

Степенью многочлена называется наибольшая степень X в слага емом с ненулевым коэффициентом. Степень нулевого многочлена равна 0.

Многочлен называется нормированным, если коэффициент при наибольшей степени X равен 1. Многочлены можно складывать и умножать обычным путем;

они образуют кольцо.

Если r(X), s(X), t(X) — многочлены и r(X)s(X) = t(X), то говорят, что многочлен t(X) делится на многочлен r(X) или что r(X) является делителем многочлена t(X) или что многочлен r(X) является множителем для t(X). Многочлен p(X) степени n, кото рый не делится ни на какой многочлен, степени меньшей чем n, но большей чем 0, называется неприводимым. Наибольшим общим делителем двух многночленов называется нормированный много член наибольшей степени, который является делителем для обоих многочленов. Говорят, что два многочлена взимно просты, если их наибольший общий делитель равен 1.

Степень произведения двух многочленов равна сумме их сте пеней. Ненулевой многочлен степени 0 является элементом поля коэффициентов и поэтому имеет обратный элемент. Но многочле нов более высоких степеней, которые имели бы обратный элемент, не существует. Если s(X) делится на r(X) и r(X) делится на s(X), то они отличаются самое большее множителем, который является элементом поля. Это утверждение можно проверить следующим образом. Пусть для неоторых многочленов a(X) и b(X) справед ливы равенства r(X) = s(X)a(X) и s(X) = r(X)b(X). Тогда, так как степень r(X) равна сумме степеней s(X) и a(X), степень r(X) больше или равна степени s(X). Аналогично, степень s(X) больше или равна степени r(X), и, таким образом, степени s(X) и r(X) должны быть равны. Следовательно, многочлены a(X) и b(X) име ют степень 0 и должны быть элементами поля.

Для любой пары многочленов s(X) и d(X) существует, согласно алгоритму деления Евклида, единственная пара многочленов q(X) — частное и r(X) — остаток, таких, что s(X) = d(X)q(X) + r(X) и степень r(X) меньше степени d(X).

Используя алгоритм деления Евклида, можно установить, что наибольший общий делитель d(X) двух многочленов r(X) и s(X) всегда может быть представлен в виде d(X) = a(X)r(X) + b(X)s(X), где a(X) и b(X) — многочлены.

Теорема 41. Совокупность многочленов образует идеал тогда и только тогда, когда она содержит все многочлены, кратные некоторому многочлену.

Кольцо классов вычетов, образованное по идеалу, состоящему из всех многочленов, кратных f(X), называется кольцом много членов по модулю f(X).

О п р е д е л е н и е 68. Множество A называется ас социативной линейной алгеброй над полем F, если выполняются следующие аксиомы:

1. Множество A является векторным пространством над F.

2. Для любых двух элементов u и v из A произведение uv принадлежит A ( замкнутость ).

3. Для любых u, v, w A имеет место равенство (uv)w = u(vw) (ассоциативный закон).

4. Если c, d F, а u, v, w A, то u(cv + dw) = cuv + duw и (cv + dw)u = cvu + dwu (билинейный закон).

Теорема 42. Классы вычетов многочленов по модулю много члена f(X) степени n образуют коммутативную линейную ал гебру размерности n над полем коэффициентов.

Д о к а з а т е л ь с т в о. Умножение на скаляр определя ется равенством a{r(X)} = {ar(X)};

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

{r(X)}({s(X)} + {t(X)} = {r(X)(s(X) + t(X))} = ={r(X)s(X) + r(X)t(X)} = {r(X)}{s(X)} + {r(X)}{t(X)}.

То, что векторное пространство имеет размерность n, можно увидеть из того, что n классов вычетов {1}, {X}, {X2},..., {Xn-1} порождают все пространство, поскольку каждый класс вычетов содержит многочлен степени, меньшей чем n, и {a0 + a1X +... + an-1Xn-1} = a0{1} + a1{X} +... + an-1{Xn-1} Кроме того, эти n классов вычетов линейно независимы, потому что в правой части последнего соотношения стоит произвольная линейная комбинация классов вычетов {1}, {X}, {X2},..., {Xn-1}, а левая часть равна нулю, только если многочлен a0 + a1X +... + an-1Xn-1 делится на f(X), что невозможно, или если все коэффи циенты ai равны 0. Что и требовалось доказать.

Обозначим {X} = S.

Теорема 43. В алгебре многочленов по модулю многочлена f(X) степени n многочлен f(S) = 0, но не существует равного нулю многочлена от S степени, меньшей чем n.

Д о к а з а т е л ь с т в о.

f(S) = f0 + f1S +... + fnSn = = f0 + f1{X} +... + fn{Xn} = = {f0 + f1X +... + fnXn} = {f(X)} = 0.

Аналогично, если g(X) — любой многочлен степени, меньшей чем n, то g(S) = {g(X)}, и этот класс вычетов не есть идеал.

Из этой теоремы следует, что различные многочлены от S, сте пени, меньше чем n, являются различными классами вычетов, так как в противном случае их разность была бы многочленом от S степени, меньшей чем n, который был бы равен 0.

Теорема 44. Пусть J — идеал в алгебре многочленов по модулю f(X), а g(X) — отличный от нуля многочлен наимень шей степени, такой, что класс вычетов {g(X)} принадлежит J.

При этом класс вычетов {s(X)} принадлежит J тогда и толь ко тогда, когда многочлен s(X) делится на g(X). Более того, многочлен g(X) является делителем f(X).

Д о к а з а т е л ь с т в о. В соответствие с алгоритмом деления Евклида s(X) = g(X)q(X) + r(X), где степень r(X) меньше степени g(X).

Следовательно, {s(X)} = {g(X)}{q(X)} + {r(X)}, и если классы вычетов {s(X)} и {g(X)} принадлежат J, то класс вычетов {s(X)} - {g(X)}{q(X)} = {r(X)} также принадлежит J. Так как степень r(X) меньше степени g(X) и по предположе нию g(X) — ненулевой многочлен наименьшей степени, такой, что класс вычетов {g(X)} принадлежит J, то многочлен r(X) должен быть равен 0. Следовательно, многочлен s(X) кратен мнонгочлену g(X). Обратно, если многочлен s(X) кратен многочлену g(X), то s(X) = g(X)q(X) и {s(X)} = {g(X)}{q(X)}, так что если класс вычетов {g(X)} принадлежит J, то класс вычетов {s(X)} также должен принадлежать J.

В соответствии с алгоритмом деления Евклида f(X) = g(X)q(X) + r(X), где степень многочлена r(X) меньше степени g(X). Поэтому {0} = {f(X)} = {g(X)}{q(X)} + {r(X)}, и, значит, класс вычетов {r(X)} принадлежит J. Поскольку сте пень r(X) меньше степени g(X), то многочлен r(X) должен быть нулевым, и, следовательно, многочлен f(X) кратен g(X). Что и требовалось доказать.

Теорема 45. Для любого идеала J в алгебре многочленов по модулю f(X) существует единственный нормированный мно гочлен g(X) минимальной степени, такой, что класс вычетов {g(X)} принадлежит идеалу J. И наоборот, каждый нормиро ванный многочлен g(X), являющийся делителем f(X), порожда ет некоторый идеал J, в котором g(X) является нормированным многочленом наименьшей степени.

Д о к а з а т е л ь с т в о. Должен существовать многочлен наи меньшей степени h(X) = h0 + h1X +... + hkXk, такой, что класс вычетов {h(X)} принадлежит J. Тогда многочлен h-1h(X) оказы k вается нормированным многочленом наименьшей степени, класс вычетов которого также принадлежит J, и, следовательно, в J су ществует по крайней мере один нормированный многочлен мини мальной степени. Предположим, что существуют два таких много члена g(X) и g(X). Тогда по предыдущей теореме многочлен g(X) делится на g(X) и многочлен g(X) делится на g(X), и, таким об разом, они отличаются самое большее на множитель, являющийся элементом поля. Поскольку по предположению оба многочлена яв ляются нормированными, этим элементом поля должна быть 1 и g(X) = g(X). Следовательно, существует единственный норми рованный многочлен минимальной степени g(X), класс вычетов которого {g(X)} принадлежит J.

Предположим теперь, что g(X) — нормированный многочлен, являющийся делителем f(X), и рассмотрим идеал J, порожденный классом вычетов g(X), т.е. идеал, содержащий все классы выче тов, кратные {g(X)}. Пусть класс вычетов {r(X)} принадлежит J. Тогда {r(X)} = {g(X)}{a(X)} = {g(X)a(X)} для некоторого многочлена a(X), и поэтому r(X) = g(X)a(X) + f(X)b(X) для некоторого многочлена b(X). Так как многочлен f(X) кратен g(X), то r(X) также кратен g(X), и поэтому, если многочлен r(X) отличен от нуля, он имеет степень, по крайней мере не меньшую, чем степень g(X). Таким образом, g(X) — нормированный много член минимальной степени, класс вычетов которого принадлежит J. Что и требовалось доказать.

Теорема 46. Пусть f(X) = g(X)h(X), где f(X) — много член степени n, а h(X) — многочлен степени k. Тогда идеал, порожденный классом вычетов {g(X)} в алгебре многочленов по модулю f(X), имеет размерность k.

Д о к а з а т е л ь с т в о. В идеале, который является некото рым подпространством, векторы {g(X)}, {Xg(X)},..., {Xk-1g(X)} линейно независимы, ибо любая линейная комбинация этих векто ров имеет вид {(a0 +... + ak-1Xk-1)g(X)} и отлична от нуля, так как каждый класс вычетов содержит некоторый многочлен степе ни, меньшей чем n. Более того, если {s(X)} принадлежит идеалу, многочлен s(X) делится на g(X), а если s(X) — многочлен наи меньшей степени в своем классе вычетов, то его степень меньше n. Таким образом, s(X) = g(X)q(X) = g(X)(q0 + q1X +... + qk-1Xk-1) и {s(X)} = q0{g(X)} + q1{Xg(X)} +... + qk-1{Xk-1g(X)}, так что k векторов {g(X)}, {Xg(X)},..., {Xk-1g(X)} порождают идеал. Следовательно, размерность идеала равна k. Что и требо валось доказать.

Будем говорить, что многочлен r(S) принадлежит нулевому подпространству идеала J, если r(S)s(S) = 0 для любого мно гочлена s(S) из J.

Теорема 47. Пусть f(X), g(X), h(X) — нормированные мно гочлены, и пусть f(X) = g(X)h(X). Тогда класс вычетов {a(X)} принадлежит нулевому подпространству идеала, порожденного многочленом h(X), тогда и только тогда, когда он принадле жит идеалу, порожденному многочленом g(X).

Д о к а з а т е л ь с т в о. Если {a(X)} принадлежит иде алу, порожденному многочленом g(X), а {b(X)} — любой класс вычетов из идеала, порожденного h(X), то многочлен a(X) кра тен g(X) и многочлен b(X) кратен h(X), а произведение a(X)b(X) кратно f(X). Следовательно, {a(X)}{b(X)} = {a(X)b(X)} = 0, и, таким образом, класс вычетов {a(X)} принадлежит нулевому под пространству идеала, порожденного многочленом h(X). Обратно, если {a(X)}{h(X)} = 0, то произведение a(X)h(X) должно быть кратно f(X). Это значит, что многочлен a(X) должен делиться на g(X), и, следовательно, класс вычетов {a(X)} принадлежит идеа лу, порожденному g(X). Что и требовалось доказать.

7.3. Поля Галуа Теорема 48. Пусть p(X) — многочлен с коэффициентами из поля F. Алгебра многочленов над полем F по модулю p(X) является полем тогда и только тогда, когда многочлен p(X) неприводим в поле F, т.е. если p(X) нельзя представить в виде произведения многочленов с коэффициентами из F.

Доказательство аналогично доказательству теоремы для слу чая целых чисел.

Рассмотрим кольцо многочленов с действительными коэффи циентами по модулю неприводимого многочлена X2 + 1 = p(X).

Обозначим через {X} = i класс вычетов, содержащий X. Тогда каждый элемент получившегося поля можно представить в виде многочлена от i степени, меньшей чем 2, т.е. в виде a + bi. Так как i удовлетворяет уравнению p(X) = 0, то i2 + 1 = 0, или i2 = -1.

Это один из способов описания поля комплексных чисел.

Поле, образованное многочленами над полем F по модулю не приводимого многочлена p(X) степени k, называется расширением поля степени k над F. Поле F называется основным полем.

Поле многочленов над F = GF (p) по модулю неприводимого многочлена степени m называется полем Галуа, состоящим из pm элементов и обозначается как GF (pm).

Поля Галуа, которые могут быть образованы классами выче тов мнонгочленов по модулю неприводимого многочлена над полем GF (p), называются полями характеристики p. Таким образом, при любом выборе m поле GF (pm) — это поле характеристики p. В по ле GF (p) элемент p = 0. Поскольку GF (p) — поле коэффициентов для GF (pm), то во всех полях характеристики p элемент p = 0.

Тогда 1 (a + b)p = ap + Cpap-1b + Cpap-2b2 +... + bp, i и так как все биномиальные коэффициенты Cp, 0 < i < p содержат p в качестве множителя и поэтому равны 0, то доказана следующая теорема:

Теорема 49. В поле характеристики p имеет место равен ство (a + b)p = ap + bp.

Рассмотрим теперь основное поле F и некоторое его расшире ние;

пусть — любой элемент расширения. Нормированный мно гочлен m(X) наименьшей степени с коэффициентами из основного поля F, такой, что m() = 0, называется минимальным многочле ном или минимальной функцией для.

Теорема 50. Минимальная функция m(X) для любого эле мента является неприводимым многочленом.

Д о к а з а т е л ь с т в о. Предположим, что, наоборот, m(X) = m1(X)m2(X). Тогда m() = m1()m2() и по крайней мере один из сомножителей m1() или m2() должен быть равен 0. Если эти сомножители нетривиальны, то это противоречит предположению о том, что m(X) — многочлен минимальной степени с корнем.

Что и требовалось доказать.

Теорема 51. Если f(X) — многочлен с коэффициентами из основного поля F и если f() = 0, то многочлен f(X) делится на m(X) — минимальную функцию для.

Д о к а з а т е л ь с т в о. В соответствии с алгоритмом Евклида f(X) = m(X)q(X) + r(X), где r(X) — многочлен степени, меньшей степени m(X). Поскольку f() = 0 и m() = 0, то r() = 0. Так как m(X) — минимальная функция для, а степень многочлена r(X) меньше степени m(X), то r() = 0, если только r(X) = 0. Что и требовалось доказать.

Из приведенной теоремы следует, что минимальная функция для единственна. Из нее следует также, что если p(X) — нор мированный неприводимый многочлен и p() = 0, то p(X) — ми нимальная функция для.

Теорема 52. Для каждого элемента из расширения поля сте пени k над F существует минимальная функция для этого эле мента степени k или меньше.

Д о к а з а т е л ь с т в о. Расширение поля является векторным пространством размерности k. Поэтому для любого элемента со вокупность из k + 1 элементов 1,, 2,..., k неможет быть линей но независимой. Следовательно, должен существовать некоторый многочлен степени k или меньше от, который равен 0, и этот многочлен можно нормировать, разделив его на коэффициент при высшей степени переменного. Что и требовалось доказать.

7.4. Мультипликативная группа поля Галуа В любой конечной группе можно рассмотреть совокупность эле ментов, образованную некоторым элементом g и всеми его степе нями gg = g2, gg2 = g3 и т. д. Может существовать самое большое конечное число таких элементов, и поэтому для некоторых i и j должно быть gj = gi. Умножая это равенство на (gi)-1, получим 1 = gj-i. Следовательно, некоторая степень элемента g равна 1.

Пусть e — наименьшее целое положительное число, такое, что ge = 1. Число e называется порядком элемента g. Совокупность элементов 1, g, g2,..., ge-1 образует подгруппу, поскольку произве дение любых двух элементов совокупности есть снова элемент это го же вида, а элемент, обратный gj, равен ge-j и, следовательно, тоже является одним из элементов этой совокупности. Группа, ко торая состоит из всех степеней одного из ее элементов, называется циклической группой.

Порядок e любого элемента g группы является делителем поряд ка группы, так как группа содержит циклическую подгруппу из e элементов, порожденную g, и некоторое число смежных классов по этой подгруппе, каждый из которых состоит тоже из e элементов.

Теорема 53. Совокупность корней многочлена Xq-1-1 явля ется совокупностью всех q - 1 ненулевых элементов поля GF (q).

Д о к а з а т е л ь с т в о. Совкупность q - 1 ненулевых элемен тов поля GF (q) образует группу. Порядок каждого элемента поля GF (q) должен быть делителем q - 1, и, следовательно, каждый из q - 1 элементов является корнем многочлена Xq-1 - 1. Но этот многочлен имеет самое большее q - 1 различных корней, так как его степень равна q - 1. Что и требовалось доказать.

Теорема 54. Многочлен Xn -1 делится на многочлен Xm - тогда и только тогда, когда n делится на m.

d Д о к а з т е л ь с т в о. Предположим, что n = md. Тогда Y - d делится на Y - 1, поскольку Y = 1 — корень многочлена Y - 1.

Подставляя Xm = Y, получаем, что Xmd - 1 делится на Xm - 1.

Теперь допустим, что n = md + r, где r < d. Тогда Xn - 1 = Xr(Xmd - 1) + Xr - 1, и в соответствии с алгоритмом деления Евклида Xn - 1 = q(X)(Xd - 1) + r(X).

Сравнивая эти равенства, находим Xr(Xmd - 1) q(X) = и r(X) = Xr - 1, Xd - так как q(X) — многочлен, а степень r(X) меньше d. Таким об разом, остаток равен 0 только тогда, когда r = 0, т.е. когда n делится на m. Что и требовалось доказать.

Теорема 55. В поле GF (q) существует примитивный эле мент, т.е. элемент порядка q - 1. Каждый ненулевой элемент поля GF (q) может быть представлен как некоторая степень, т.е. мультипликативная группа поля Галуа GF (q) является циклической.

1 r Д о к а з а т е л ь с т в о. Пусть q-1 = pe pe · · · pe, и пусть i — 1 2 r i 1 элемент поля порядка pe, i = 1, 2,..., r. Поскольку pe и pe взаим i 1 1 но просты, то существуют такие s и t, что spe +tpe = 1. Поэтому 1 e1 e1 e2 e 1 1 2 (12)sp = (2)sp = (2)1-tp = 2;

аналогично (12)tp = 1.

Таким образом 1 и 2 являются степенями 12, откуда следу 1 ет, что порядок элемента поля 12 является делителем pe pe. Но 1 e1 e если (12)p p22 /a = 1 при некотором a > 1, то либо порядок 1 меньше чем pe, либо порядок 2 меньше чем pe, что противо 1 речит нашим предположениям. Следовательно, порядок 12 ра 1 вен pe pe. Индукцией по i отсюда выводим, что порядок элемента 1 1 r = 12...r равен pe pe...pe = q - 1. Таким образом, элемен 1 2 r ты, 2,..., q-1 = 1 являются различными элементами поля, и мультипликативная группа поля GF (q) циклическая. Что и тре бовалось доказать.

Поле Галуа GF (24) из 24 элементов можт быть образовано как поле многочленов над GF (2) по модулю X4 + X + 1. Пусть обо значает класс вычетов, который содержит X. Тогда является корнем многочлена X4 + X + 1 и примитивным элементом поля.

Для этого случая 15 ненулевых элементов поля имют следующий вид:

Таблица 5.1. Представление поля GF (24) 0 = 1 = (0001) 1 = = (0010) 2 = 2 = (0100) 3 = 3 = (1000) 4 = + 1 = (0011) 5 = 2 + = (0110) 6 = 3 + 2 = (1100) 7 = 3 + + 1 = (1011) 8 = 2 + 1 = (0101) 9 = 3 + = (1010) 10 = 2 + + 1 = (0111) 11 = 3 + 2 + = (1110) 12 = 3 + 2 + + 1 = (1111) 13 = 3 + 2 + 1 = (1101) 14 = 3 + 1 = (1001) 15 = 1 = Следующие теоремы содержат более детальные сведения о взаи мосвязи между мультипликативными свойствами элементов поля, минимальными многочленами от элементов поля и многочленом Xq - X.

Теорема 56. Если f(X) — многочлен с коэффициентами из поля GF (q) и — корень f(X) в расширении GF (q), то q также является корнем f(X).

Д о к а з а т е л ь с т в о. Пусть f(X) = a0 + a1X +..., anXn.

Тогда [f(X)]q = (a0)q + (a1X)q +... + (anXn)q = aq + aqXq +... + aq (Xq)n.

0 1 n Далеее, aq-2 = 1, и поэтому aq = a для любого элемента a GF (q).

Следовательно, [f(X)]q = a0 + a1Xq +... + an(Xq)n = f(Xq)n = f(Xq), и если f() = 0, то [f()]q = f(q) = 0. Что и требовалось доказать.

Теорема 57. Рассмотрим расширение поля GF (q), которое m содержит все корни многочлена Xq - X. Тогда совокупность этих корней образует подполе.

Д о к а з а т е л ь с т в о. Если a и b — корни многочлена, то m m a + b — также корень многочлена Xq - X, так как (a + b)q = m m m m aq + bq = a + b. Кроме того, (-a)q = -(aq ) = -a, и, таким образом, -a — также корень этого многочлена, если a является его корнем. (Заметим, что -a = a, если характеристика поля равна 2). Поэтому корни многочлена образуют аддитивную группу. Если a и b — корни многочлена, то произведение ab и обратный элемент a-1 (если a = 0) также являются его корнями. Остальные аксиомы справедливы, поскольку корни принадлежат полю. Ч. т. д.

Теорема 58. Каждый многочлен p(X) степени m, неприводи m мый над полем GF (q), является делителем многочлена Xq - X.

Д о к а з а т е л ь с т в о. Если p(X) = X, то теорема, очевидно, верна. Пусть теперь p(X) = X и = 0 — корень многочлена p(X) в расширении поля многочленов по модулю p(X) над полем GF (q).

Это поле является полем из qm элементов, и совокупность всех его ненулевых элементов образует группу порядка qm - 1. Поэтому порядок должен быть делителем qm - 1 и должен быть корнем m многочлена Xq -1 - 1. Тогда многочлен p(X) является делителем m многочлена Xq - X. Ч. т. д.

m Теорема 59. Каждый делитель многочлена Xq - X, непри водимый над полем GF (q), имеет степень, равную m или мень шую m.

Д о к а з а т е л ь с т в о. Предположим, что многочлен p(X) степени k представляет собой неприводимый делитель мно m гочлена Xq - X над полем GF (q), и рассмотрим расширение по ля многочленов над GF (q) по модулю p(X). Оно состоит из qk элементов, каждый из которых может быть представлен в виде a0 + a1 +... + ak-1k-1 =, где — корень многочлена p(X), а a0,..., ak-1 — элементы поля GF (q). Тогда m m m m m m q = aq + aq q +... + aq q (k-1).

0 1 k- m m Так как aq -1 = 1 и, следовательно, aq = a для любого элемента a из поля GF (qm), поскольку a0, a1,..., ak-1 принадлежат GF (q) и, следовательно, принадлежат также расширению поля GF (qm), то m m m q = a0 + a1q +... + ak-1q (k-1).

m m m Но —корень многочлена Xq - X, поэтому q = и jq = j для всех j. Таким образом, m q = a0 + a1 +... + ak-1k-1 =, m т.е. — также корень многочлена Xq - X. Так как число таких m элементов составляет qk, тогда как Xq - X имеет не более чем qm корней, то qm qk и, следовательно, m k. Ч. т. д.

Теорема 60. Если — элемент расширения поля GF (q), то порядок e элемента является делителем числа qk - 1, но не является делителем никакого меньшего числа вида qn - 1;

здесь k — степень минимальной функции для.

Д о к а з а т е л ь с т в о. Пусть m(X) — минимальная функция для ;

предположим, что ее степень равна k. Тогда m(X) является k делителем многочлена Xq -1 - 1, а — корнем этого многочлена.

Поэтому порядок является делителем qk - 1. Предположим, что qn - 1 делится на порядок при n k. Тогда является корнем n многочлена Xq - X, а m(X) — его делителем. Таким образом, степень многочлена m(X) не превосходит n. Ч. т. д.

Теорема 61. Пусть p(X) — многочлен степени m с ко эффициентами из поля GF (q), который неприводим в этом по ле, и пусть корень многночлена p(X) в расширении поля. Тог m- да, q,..., q образуют совокупность всех корней многочлена p(X).

m- Д о к а з а т е л ь с т в о. Элементы, q,..., q являются корнями многочлена p(X). Покажем, что все они различны. Пред i j положим, что это не так и q = q, и пусть j < i. Тогда m i m-i j m-i = q = (q )q = (q )q = m+j-i, m+j-i 1 = (q -1).

Таким образом, порядок является делителем qm+j-i - 1. Но многочлен p(X) отличается от минимального многочлена для самое большое на постоянный множитель, и m + j - i < m, где m степень p(X). Это противоречит утверждению предыдущей теоре m- мы и, следовательно, элементы, q,..., q различны. Так как многочлен p(X) может иметь самое большее m корней, то этим исчерпываются все корни p(X). Ч. т. д.

Теорема 62. Все корни неприводимого многочлена имеют один и тот же порядок.

Д о к а з а т е л ь с т в о. Если — один из корней многочлена, то любой из остальных корней, по предыдушей теореме, может j быть представлен в виде q при некотором j. Пусть e — порядок j, а e — порядок q. Тогда j j j j (q )e = eq = (e)q = 1q = 1, и поэтому e делится на e. Аналогично m j j m-j m-j e = (q )e = q qm-je = [(q )e ]q = 1q = 1, так что e делится на e. Поскольку e и e — целые положительные числа, то e = e. Ч. т. д.

Порядок корней неприводимого многочлена называется показа телем, которому принадлежит этот многочлен. Если неприводи мый многочлен принадлежит показателю e, то он является дели телем многочлена Xe - 1, но не является делителем многочлена вида Xn - 1 при n < e. Неприводимый многочлен степени m над полем GF (q) называется примитивным, если его корнем является примитивный элемент поля GF (qm). Тогда этот корень и, следо вательно, все его корни имеют порядок qm - 1, и по предыдущей теореме все они — примитивные элементы. Неприводимый мно гочлен степени m является примитивным тогда и только тогда, когда он принадлежит показателю qm - 1. Наконец, неприводи мый многочлен степени m является примитивным тогда и только тогда, когда он не является делителем многочлена Xn - 1 ни при каких n, меньших чем qm - 1.

Содержание предыдущих теорем проиллюстрируем на примере разложения на множители многочлена X63 - 1 над полем GF (2).

Все ненулевые элементы поля GF (64) могут быть представлены как степени некоторого примитивного элемента. Этими элемен тами являются 1,, 2, 3,..., 62 и X63 - 1 = (X - 1)(X - )(X - 2)...(X - 62).

Далее, так как (21)3 = 63 = 1, то порядок элемента 21 равен 3.

Тот же самый порядок имеет элемент 42. Аналогично, (9)7 = 63, так что порядок элемента 9 равен 7, и таков же порядок элементов 18, 27, 36, 45 и 54. Порядок элементов 7, 14, 28, 35, 49, равен 9. Заметим, что (21)9 = 1, но порядок элемента 21 равен 3, а не 9, поскольку порядок элемента равен наименьшему e, тако му, что e = 1. Аналогично любая степень, показатель которой делится на 3, но не делится на 7 или на 9, является элементом порядка 21. Таких элементов 12. Остальные 36 элементов должны иметь порядок 63. Определим теперь круговой многочлен i(X) = (X - 1)(X - 2)...(X - r), где 1, 2,..., r — набор всех элемен тов порядка i. Тогда 1 = X - 1, 3 = (X - 21)(X - 42), 7 = (X -9)(X -18)(X -27)(X -36)(X -45)(X -54) и т.д. Кроме того, X63 - 1 = 1(X)3(X)7(X)9(X)21(X)63(X).

Корнями многочлена X21 - 1 являются все элементы, для ко торых 21 = 1, и поэтому этот многочлен содержит в качестве множителей i(X) для всех i, на которые делится 21.

Таким образом, X21 - 1 = 21(X)7(X)3(X)1(X), и аналогично X9 - 1 = 9(X)3(X)1(X), X7 - 1 = 7(X)1(X), X3 - 1 = 3(X)1(X), X - 1 = 1(X).

Эти равенства могут быть переписаны в виде 1(X) = X - 1 (степень 1), X3- 3(X) = (степень 2), 1(X) X7- 7(X) = (степень 6), 1(X) X9- 9(X) = (степень 6), 1(X)3(X) X21- 21(X) = (степень 12), 1(X)3(X)7(X) X63- 63(X) = (степень 36).

1(X)3(X)7(X)9(X)21(X) Степень i(X) совпадает с числом элементов порядка i, которое было уже вычислено. Кроме того, степень многочлена 1, очевид но, равна 1. Степень 3 равна разности между степенью X3 - 1 и степенью знаменателя 1(X) и т. д.

Элементы порядка 3 должны обладать минимальными много членами над GF (2) степени 2, поскольку они являются элементами GF (22). Это значит, что многочлен 3(X) неприводим над GF (22).

Действительно, ненулевыми элементами GF (22) являются корни многочлена X3 - 1, т.е. 1, 21 и 42. Аналогично элементы поряд ка 7 принадлежат GF (23) и обладают минимальными многочле нами степени 3, поэтому многочлен 7(X) должен разлагаться на два неприводимых многочлена степени 3. Все остальные элементы GF (26) не являются элементами какого-либо подполя, и, следова тельно, все их минимальные многочлены являются многочленами степени 6. Кроме того, заметим, что поскольку все корни непри водимого многочлена имеют один и тот же порядок, то, если один из корней неприводимого многочлена p(X) имеет порядок i, все его корни имеют порядок i и являются, следовательно, корнями i(X).

В этом случае многочлен i(X) делится на p(X). Таким образом, многочлен 9(X) должен быть неприводим. Многочлен 21(X) дол жен иметь два множителя степени 6, а многочлен 63(X) должен иметь шесть множителей степени 6.

Если — корень неприводимого многочлена p(X), то его остальные корни равны 2, 4, 8, 16, 32. Обозначим через mi(X) минимальный многочлен для i. Тогда m1(X) = (X - )(X - 2)(X - 4)(X - 8)(X - 16)(X - 32), m3(X) = (X - 3)(X - 6)(X - 12)(X - 24)(X - 48)(X - 33) Заметим, что (48)2 = 96 = 33, поскольку 63 = 1. Кроме того, заметим, что (32)2 = 64 =, поскольку 63 = 1, и, таким обра зом, процесс последовательного возведения в квадрат порождает только шесть различных корней многочлена m1(X). Аналогично (33)2 = 66 = 3. Далее, (9)2 = 18, (18)2 = 36, (36)2 = 72 = 9, и, таким образом, последовательное возведение в квадрат дает только три различных корня многочлена m9(X). Это согласуется с тем фактом, что степень многочлена m9(X) должна быть равна 3, так как все элементы порядка 7 принадлежат GF (23).

7.5. Векторные пространства и линейные преобразования конечных полей Пусть f(X) — многочлен с коэффициентами из GF (2m) следу ющего вида r i f(X) = aiXq. (7.1) i= Он задает линейное преобразование в себя поля GF (qm), рассмат риваемое как векторное пространство над GF (q). Так как преоб разование является линейным, то и совокупность корней, и сово купность различных значений являются подпространствами про странства GF (qm).

Здесь будут даны ответы на следующие вопросы:

1. Можно ли любое подпространство пространства GF (qm) опи сать как совокупность корней многочлена f(X), полностью разла гающегося на множители в поле GF (qm)?

2. Можно ли любое подпространство пространства GF (qm) опи сать как совокупность значений, которые получаются при подста новке всех элементов из GF (qm) в некоторый многочлен f(X), пол ностью разлагающийся на множители в GF (qm)?

Здесь L используется для обозначения отображения поля GF (qm) в себя, которое переводит каждый элемент поля в эле мент q:

L = q.

Теорема 64. Любое линейное преобразование пространства GF (qm) в себя может быть однозначно представлено в виде f(L), где f(X) — многочлен степени, не превосходящей m - 1.

Д о к а з а т е л ь с т в о. Поскольку число всевозможных преоб разований пространства GF (qm) в себя равно qm и число различ ных многочленов f(X) степени, не превосходящей m-1, с коэффи циентами из GF (qm) также равно qm, то достаточно показать, что f(L) = g(L), если f(X) = g(X). Это в свою очередь эквивалентно тому, что f(L) = 0, если f(X) = 0 и степень f(X) m - 1.

Итак, пусть f(X) = a0 + a1X +... + asXs, где s m - 1, ai GF (qm) и не все ai = 0. Если GF (qm), то s f(L)() = a1 + a0q +... + asq.

Так как qs < qm и не все ai = 0, то должен найтись отличный от нуля элемент GF (qm), на котором многочлен s a0X + a1Xq +... + asXq не обращается в нуль. Для этого преобразование f(L)() = 0, и, следовательно, f(L) = 0. Ч.т.д.

Введем следующие обозначения. При s f(X) = aiXi i=o Обозначим через f(X) многочлен s i f(X) = aiXq.

i= Так как каждое пространство одновременно является областью значений для некоторого линейного отображения пространства GF (qm) и нулевым пространством для этого же отображения, то справедливо следующее следствие из теоремы 64:

Следствие. Любое подпространство пространства GF (qm) может быть представлено в виде совокупности нулей и области значений некоторого многочлена вида f(X).

Рассмотрим совокупность многочленов с коэффициентами из GF (qm). Сложение многочленов определим, как обычно, а в качест ве умножения рассмотрим операцию, определенную правилами:

Xi Xj = Xi+j, (7.2) X a = aq X, если a GF (qm).

Можно доказать, что относительно этих операций совокупность многочленов образует некоммутативное кольцо. Это кольцо не со держит делителей нуля, т.е. если f(X) g(X) = 0, то ни f(X), ни g(X) не равны нулю. Заметим, что при выбранном определении умножения линейные преобразования [f(X)g(X)]X=L и f(L)·g(L) тождественны.

Теорема 65. Пусть f(X) и g(X) — многочлены с коэффици ентами из GF (qm), и пусть g(X) = 0. Тогда существуют одно значно определенные многочлены q(X) и r(X), такие, что f(X) = q(X) g(X) + r(X), причем либо r(X) = 0, либо степень многочлена r(X) меньше степени многочлена g(X).

В некомутативном кольце левый идеал определяется как под кольцо I, такое, что если f(X) принадлежит I и a(X) — про извольный многочлен кольца, то a(X) f(X) тоже принадлежит I. Далее тем же самым методом, который используется при дока зательстве теоремы об идеале многочленов, можно показать, что всякий левый идеал является главным левым идеалом, т.е. что во всяком идеале I существует единственный нормированный мно гочлен g(X) наименьшей степени и любой многочлен из I может быть представлен в виде f(X) g(X) для некоторого f(X).

Пусть теперь V — векторное k-мерное подпростарнство про странства GF (qm), рассматриваемого как векторное пространст во над GF (q). Обозначим через I совокупность всех многочленов f(X), таких, что f(L)V = 0. Тогда эта совокупность является левым идеалом, так как [a(X) f(X)]X=LV = a(L)f(L)V = 0, и, следовательно, для любого многочлена a(X) произведение a(X) f(X) принадлежит I. Кроме того, очевидно, что если f1(X) и f2(X) принадлежат I, то f1(X) + f2(X) тоже принадлежит I. Та ким образом, в совокупности I найдется единственный нормиро ванный многочлен g(X) наименьшей степени k, причем любой дру гой многочлен из I является левым кратным для g(X).

В соответствии с утверждением теоремы 64 существует мно гочлен f(L), совокупность нулей которого совпадает с подпро странством V, т.е. такой, что f(L) = 0 тогда и только тогда, когда V. Тогда f(X) принадлежит I, откуда вытекает, что f(X) = f1(X) g(X). Итак, f1(L)g(L) = 0 тогда и только тогда, когда V, и, следовательно, g(L) = 0 тогда и только тогда, когда V.

Многочлен Xm - 1 также является элементом I, поскольку для любого элемента поля m (Lm - 1) = q - = 0.

Следовательно, существует многочлен h(X), такой, что Xm - 1 = h(X) g(X) и g(X) (Xm - 1) = g(X) h(X) g(X).

Более того, для любого элемента поля справедливо равенство m q =, и поэтому Xm = Xm. Отсюда вытекает, что для любо го многочлена f(X) справедливо равенство Xmf(X) = f(X)Xm.

Таким образом, g(X) (Xm - 1) = (Xm - 1) g(X) = g(X) h(X) g(X), и поскольку ни один из сомножителей не равен нулю, то на g(X) можно сократить, так что Xm - 1 = h(X) g(X) = g(X) h(X).

Обозначим теперь через U подпространство пространства GF (qm), состоящее из всех элементов, которые появляются в ре зультате применения преобразования g(L) к элементам поля, т.е.

U = g(L)GF (qm).

Если в качестве g(L) рассматривать матрицу, то V будет нулевым пространством, и поскольку размерность V равна k, то ранг по строкам g(L) равен m-k. В этом случае U является пространством столбцов матрицы g(L), и поскольку ранги пространства строк и столбцов любой матрицы равны, то размерность U также равна m - k. Далее, h(L)g(L)GF (qm) = h(L)U = 0.

Поскольку все элементы пространства V являются корнями g(X), то степень g(X) равна по меньшей мере qk и поэтому степень мно гочлена g(X) равна по меньшей мере k.

Аналогично все элементы U являются корнями многочлена h(X), следовательно, степень h(X) равна по меньшей мере qm-k, а степень многочлена h(X) равна по меньшей мере m - k. Однако степень g(X) h(X) = Xm - 1 равна m, откуда вытекает, что сте пень g(X) должа равняться k, а степень h(X) должна быть равна m - k. Это значит, что степень g(X) должна быть равна qk, т.е.

что все элементы пространства V являются корнями g(X) и мно гочлен g(X) разлагается на qk линейных множителей в простран стве GF (qm). Аналогично корнями многочлена h(X) являются все элементы пространства U, h(X) разлагается на множители и раз мерность U равна m - k.

Окончательно имеем g(L)h(L)GF (qm) = 0, и, следовательно, h(L)GF (qm) принадлежит пространству V. По скольку U, нулевое пространство для h(L), является пространст вом размерности m - k, то размерность пространства значений должна быть равной k и, следовательно, оно должно совпадать с пространством V. Таким образом, справедлива следующая теоре ма:

Теорема 66. Пусть V -k-мерное подпространство простран ства GF (qm), рассматриваемого как векторное пространство над GF (q). Тогда существует единственное m - k-мерное под пространство U, однозначно определенные нормированные мно гочлены g(X) степени k и h(X) степени m - k, такие, что V является нулевым пространством для g(L) и областью значений h(X), а U является нулевым пространством для h(L), и облас тью значений g(L). Более того, g(X) h(X) = h(X) g(X) = Xm - 1.

Следствие. Многочлен g(X) степени qk полностью разлага ется на линейные множители, причем все элементы простран ства V являются его корнями, а все элементы простанства U являются значениями, которые многочлен g(X) принимает при подстановке в него вмместо X всех элементов GF (qm). Анало гично все элементы пространства U являются корнями много члена h(X), а элементы пространства V — его значениями. На конец, m g[h(X)] = h[g(X)] = Xq - X.

УПРАЖНЕНИЯ 7.1. Постройте таблицу сложения и умножения элементов поля GF (7). Найдите порядок каждого элемента. Какие элементы являются примитивными?

7.2. Найдите все неприводимые мнонгочлены степени 5 или меньше над полем GF (2). Заметим, что если многочлен степени m не является неприводимым, то он обладает делителем, степень которого не превосходит m/2. Найдите неприводимый многочлен степени 5 над GF (3).

7.3. Сколько идеалов существует в алгебре многочленов по модулю X6 - 1 над полем GF (2)? Перечислите порождающие их многочлены.

7.4. Многочлен X4 + X3 + X2 + X + 1 = p(X) неприводим над GF (2), и поэ тому алгебра многочленов по модулю p(X) совпадает с полем GF (24). Пусть через обозначен класс вычетов {X}. Покажите, что не является примитивным эле ментом и, следовательно, p(X) — не примитивный многочлен. Покажите, что + — примитивный элемент и найдите его минимальный многочлен, который явля ется примитивным многочленом.(Ответ: минимальный многочлен для + 1 равен X4 + X3 + 1.) 7.5. Составьте таблицы, аналогичные табл. 5.1, для полей GF (23) и GF (32).

7.6. Определите какие многочлены являются множителями в разложениях сле дующих многочленов: X15 - 1, X31 - 1, X127 - 1, X255 - 1. Для каждого из круго вых многочленов определите число и степень неприводимых множителей над полем GF (2).

7.7. Многочлен f(X), двойственный некоторому многочлену f(X), определяется как f(X) = Xmf(1/X), где m — степень f(X). Докажите следующие утветждения:

а. Многочлен f(X) неприводим тогда и только тогда, когда неприводим много член f(X).

б. Если f(X) неприводим, то f(X) и f(X) принадлежат одному и тому же пока зателю. Следовательно, f(X) примитивен тогда и только тогда, когда примитивен f(X).

в. Если f(X) = f(X) и степень f(X) больше 2, то f(X) не является примитив ным.

г. Если f(X) = g(X)h(X), g(X), h(X) — неприводимые многочлены и f(X) = f(X), то либо h(X) = g(X), либо g(X) = g(X) и h(X) = h(X).

7.8. Покажите, что в векторном пространстве наборов длины n с элементами из GF (p), где p — простое число, любая подгруппа по сложению является подпростран ством.

ЦИКЛИЧЕСКИЕ КОДЫ 8.1. Циклические коды и идеалы О п р е д е л е н и е 69. Подпространство V наборов длины n называется циклическим подпространством или цикли ческим кодом, если для любого вектора v = (an-1, an-2,..., a0) из подпространства V вектор v = (a0, an-1, an-2,..., a1), получае мый в результате циклического сдвига компонент вектора v на единицу вправо, также принадлежит подпространству V.

В этой главе наборы длины n будут рассматриваться как эле менты алгебры многочленов по модулю Xn-1, которую обозначим через An. Элементами алгебры являются классы вычетов много членов, которые здесь обозначаются через {f(x)}.

Каждому набору (an-1, an-2,..., a0) длины n соответствует мно гочлен f(X) = an-1Xn-1 + an-2Xn-2 +... + a0 степени, меньшей n;

соответствующим классом вычетов является класс {an-1Xn-1 + an-2Xn-2 +... + a0}. Этот класс вычетов и соответствующий век тор из n компонент будем рассматривать просто как различные способы представления одного и того же математического объек та — элемента алгебры An многочленов по модулю Xn - 1.

Теорема 63. В алгебре многочленов по модулю Xn - 1 под пространство является циклическим подпространством тогда и только тогда, когда оно является идеалом.

Д о к а з а т е л ь с т в о. Очевидно, что умножение на {X} эквивалентно циклическому сдвигу вектора:

X(an-1Xn-1 + an-2Xn-2 +... + a0) = = an-1(Xn - 1) + an-2Xn-1 +... + a0X + an-1, и, следовательно, {X}{an-1Xn-1 + an-2Xn-2 +... + a0} = ={an-2Xn-1 + an-3Xn-2 +... + a0X + an-1}.

Если подпространство V — идеал и элемент v принадлежит V, то произведение {X}v также принадлежит V, и поскольку {X}v — циклический сдвиг вектора v, то V — циклическое подпро странство.

Предположим, что V — циклическое подпространство. Тогда для любого вектора v, принадлежащего V, произведение {X}v принадлежит V, и, следовательно, для любого j произведение {X}jv = {Xj}v также принадлежит V. Поскольку V — подпро странство, то любая линейная комбинация cn-1{Xn-1}v + cn-2{Xn-2}v +... + c0v = ={cn-1Xn-1 + cn-2Xn-2 +... + c0}v будет принадлежать V. Таким образом, произведение любого эле мента из V на любой элемент алгебры An принадлежит V, т.е.

подпространство V — идеал. Ч. т. д.

Структура идеала алгебры An сводится к следующему. Пусть g(X) — нормированный многочлен наименьшей степени, такой, что класс вычетов {g(X)} принадлежит идеалу J. Если f(X) — многочлен степени, меньше чем n, который делится на g(X), то класс вычетов {f(X)} принадлежит J, и, наоборот, если {f(X)} принадлежит идеалу J, то многочлен f(X) делится на многочлен g(X). Кроме того, многочлен Xn - 1 делится на g(X), и любой нормированный многочлен, на который делится Xn -1, порождает свой идеал J в алгебре An.

Таким образом, циклический код полностью задается многочле ном g(X), на который делится многочлен Xn - 1. С другой сторо ны, этот же код может быть полностью определен условием, что он является нулевым подпространством идеала, порожденного много членом h(X) = (Xn - 1)/g(X). Если многочлен g(X) — многочлен степени r, то размерность кода равна k = n - r. Элемент {f(X)} принадлежит коду тогда и только тогда, когда многочлен f(X) делится на g(X).

Многочлен h(X) называется проверочным многочленом для ко да, порожденного многочленом g(X). Поскольку Xn - 1 делится на h(X), то многочлен h(X) может быть использован в качестве многочлена, порождающего циклический код.

П р и м е р 28. Пусть задан многочлен X7 - 1 = (X - 1)(X3 + X + 1)(X3 + X2 + 1) над полем Галуа GF (2). Многочлен g(X) = X3 + X2 + 1 порождает циклический (7,4)-код. Элементы {X3g(X)} = (1101000), {X2g(X)} = (0110100), G = {Xg(X)} = (0011010), {g(X)} = (0001101), можно выбрать в качестве базисных векторов, и, следовательно, матрицу G можно выбрать в качестве порождающей матрицы для этого кода. Этот код яыляется нулевым подпространством идеала, порожденного многочленом h(X) = (X - 1)(X3 + X + 1) = X4 + X3 + X2 + 1:

{X2h(X)} = (1110100), {Xh(X)} = (0111010), {h(X)} = (0011101).

Рассматриваемый код является нулевым подпространством матрицы H, образованной векторами {X2h(X)}, {Xh(X)} и {h(X)}, компоненты которых записаны в обратном порядке:

0 0 1 0 1 1 H = 0 1 0 1 1 1 1 0 1 1 1 0 Легко проверить, что GHT = 0.

Другой способ задания циклических кодов основан на исполь зовании корней (которые, возможно, лежат в расширении поля) многочлена g(X), порождающего идеал. Предположим, во-первых, что все корни 1, 2,..., r многочлена g(X) различны. Тогда цик лический код полностью определяется условием: вектор {f(X)} принадлежит коду тогда и только тогда, когда 1, 2,..., r — корни многочлена f(X). Если обозначить через mi(X) минималь ную функцию для i, то вектор {f(X)} является кодовым век тором тогда и только тогда, когда многочлен f(X) делится на m1(X), m2(X),..., mr(X) и, следовательно, на их наименьшее об щее кратное. Поэтому код является идеалом, порожденным много членом g(X) = НОК[m1(X), m2(X),..., mr(X)].

Так как многочлен Xn - 1 должен делится на многочлен g(X), то элементы 1, 2,..., r должны быть корнями многочлена Xn - 1, и, следовательно, число n должно делится на порядок каждого из элементов i. Таким образом, n можно выбирать равным наимень шему общему кратному порядков элемента i, так как при таком выборе n каждый элемент i является корнем многочлена Xn - и этот многочлен делится на g(X) без остатка.

Если корни задаются как степени одного и того же элемента i порядка e, т.е. если установлено, что i = u, где ui — задан ные целые числа, то число сомножителей и степень каждого из них в разложении многочлена g(X) для целых e и ui могут быть найдены по следующей схеме. Все корни минимальной функции i i i mi(X) содержатся в последовательности u, u q, u q2,..., так что все корни mi(X) — различные элементы этой последовательнос ти. Показатели степеней в этой последовательности — различные вычеты по модулю e чисел ui, uiq, uiq2, uiq3,..., и число различных вычетов равно степени ri минимальной функции mi(X). Вполне i j возможно, что элементы u и u имеют одну и ту же минималь ную функцию mi(X) = mj(X). В этом случае совокупности корней функции mi(X) и mj(X) будут совпадать и в качестве сомножи теля в разложении многочлена g(X) следует взять только одну из этих функций. Совокупность показателей, связанных с многочле ном mi(X), называется циклическим множеством этого многочле на.

П р и м е р 29. Код, рассмотренный в предыдущем примере, можно определить условием, чтобы каждый кодовый многочлен со держал среди своих корней любой корень многочлена X3+X2+1.

С другой стороны, предположим, что известно только, что каждый кодовый многочлен должен содержать среди своих корней неко торый примитивный элемент поля GF (23). Все примитивные эле менты поля GF (23) являются корнями либо многочлена X3+X2+1, либо многочлена X3 +X +1. Поэтому искомый код — это либо код, рассмотренный в предыдущем примере, либо эквивалентный ему код, порождаемый многочленом X3 + X + 1.

Код, корнями каждого кодового вектора которого являются еди ница и — корень многочлена X3 + X2 + 1 — порождается мно гочленом g(X) = (X - 1)(X3 + X2 + 1).

П р и м е р 30. Рассмотрим менее тривиальный пример. Пусть = 89, где — примитивный элемент GF (211). Исследуем дво ичный код, для которого, 2, 3, 4 — корни всех кодовых мно гочленов. Так как 89 23 = 211 - 1, то 23 = 1. Пусть m(X) — минимальная функция для. Тогда корни многочлена m(X) образуют последовательность, 2, 4, 8, 16, 32 = 9, 18, 36 = 13, 26 = 3, 6, 12, (24 = ).

Итак, m(X) — минимальная функция для, 2, 3, 4, и мно гочлен принадлежит кодовому пространству тогда и только тог да, когда он делится на m(X). Различным выборам примитивно го элемента из GF (211) соответствуют различные значения, каждое из которых является корнем одного из двух многочленов:

X11+X9+X7+X6+X5+X +1 или X11+X10+X6+X5+X4+X2+1.

П р и м е р 31. Пусть q = 2 и — примитивный элемент поля GF (24). Тогда 15 = 1. Рассмотрим код, такой, что век тор {f(X)} принадлежит ему тогда и только тогда, когда эле менты, 2, 3, 4, 5 и 6 являются корнями многочлена f(X).

Пусть через mi(X) обозначена минимальная функция для i. Тог да, 2, 4, 8 — корни многочлена m1(X) и m1(X) = m2(X) = m4(X) = m8(X). Аналогично 3, 6, 12, 24 = 9 — корни много члена m3(X). Это описание можно сократить, перечисляя только показатели степеней или циклические множества:

1 2 4 8 m1(X) = m2(X) = m4(X) (степень 4), 3 6 12 9 m3(X) = m6(X) (степень 4), 5 10 m5(X) (степень 2).

Отсюда g(X) = m1(X)m3(X)m5(X), и степень g(X) равна 10.

П р и м е р 32. Пусть q = 2 и — примитивный элемент поля GF (25). Тогда 31 = 1. Рассмотрим код, содержащий век тор {f(X)} тогда и только тогда, когда, 2, 3,..., 10 — корни многочлена f(X). Тогда аналогично предыдущему находим 1 2 4 8 16 m1(X) (степень 5), 3 6 12 24 17 m3(X) (степень 5), 5 10 20 9 18 m5(X) (степень 5), 7 14 28 25 19 m7(X) (степень 5).

Здесь m1(X) = m2(X) = m4(X) = m8(X), m3(X) = m6(X), m5(X) = m10(X) = m9(X). При этом все эле менты, 2, 3,..., 10 находятся среди корней многочленов m1(X), m3(X), m5(X), m7(X), и поэтому g(X) = m1(X)m3(X)m5(X)m7(X), так что степень g(X) равна 20.

Если известно, что элемент i должен быть корнем многочлена f(X) кратности ri, то в разложении многочлена g(X) минимальная функция mi(X) для i должна повторяться ri раз. Можно показать, что многочлен Xn -1 не имеет кратных корней, если n и q взаимно просты. Если n = qsn1, где n1 и q взаимно просты, то s Xn - 1 = (Xn - 1)q.

Таким образом, все корни многочлена Xn - 1 всегда повторяют ся одно и то же число раз, а именно qs раз, где qs — наиболь шая степень числа q, на которую делится n. Для кратных корней значение n можно найти следующим образом. Пусть n1 — наи меньшее общее кратное порядков элементов 1, 2,..., r. Каждый из этих элементов — простой корень многочлена Xn - 1. Пусть rm — наибольшая кратность среди кратностей всех корней, а s — наименьшее целое число, удовлетворяющее неравенству rm qs.

Тогда n = n1qs.

Приведем два способа отыскания минимальной функции для за данного элемента поля 3, где — корень примитивного много члена X4 + X + 1. (См. табл. 5.1.) 1. Элементы 3, 6, 12, 9 — корни многочлена m3(X), и, сле довательно, m3(X) = (X - 3)(X - 6)(X - 12)(X - 9). Произ водя с использованием таблицы 5.1. умножение, находим m3(X) = X4 + X3 + X2 + X + 1.

2. Известно, что степень многочлена m3(X) равна 4. Пусть m3(X) = a0+a1X +a2X2+a3X3+X4. Подставляя 3 = (1000) вмес то X, 6 = (1100) вместо X2, 9 = (1010) вместо X3 и 12 = (1111) вместо X4, получаем 0 1 1 1 0 0 1 0 a0 0 + a1 0 + a2 0 + a3 1 + = 1 0 0 0 или a1 + a2 + a3 + 1 = 0, a2 + 1 = 0, a3 + 1 = 0, a0 + 1 = 0, откуда a0 = a1 = a2 = a3 = 1.

8.2. Матричное представление циклических кодов Если многочлен g(X) = arXr + ar-1Xr-1 +... + a0 порождает код, то все векторы {Xn-r-1g(X)}, {Xn-r-2g(X)},..., {g(X)} явля ются кодовыми векторами. Таким образом, кодовыми векторами являются все строки следующей матрицы:

ar ar-1.... a0 0..... 0 ar ar-1.... a0 0..................

G =..............

..............

0 0.... ar ar-1.... a0 0 0.... 0 ar..... a Очевидно, строки этой матрицы линейно независимы, а ее ранг, совпадающий с размерностью кода, равен n - r. Следователь но пространство строк матрицы G представляет собой кодо вое пространство. Условимся, что в любом циклическом коде первые k символов, т.е. коэффициенты при Xn-1, Xn-2,..., Xn-k, — будут всегда выбираться в качестве информационных сим волов, а последние n - k симоволов, т.е. коэффициенты при Xn-k-1, Xn-k-2,..., 1, — в качестве проверочных символов.

Порождающая матрица любого циклического кода может быть следующим образом приведена к модифицированной приведенно ступенчатой форме. Пусть ri(X) — остаток от деления Xi на мно гочлен g(X):

Xi = g(X)qi(X) + ri(X).

Тогда многочлены Xi - ri(X) = g(X)qi(X) являются кодовыми векторами. Если эти многочлены при i = n 1, n-2,..., n-k выбрать в качестве строк порождающей матрицы, то G = [Ik, -R], где Ik — единичная матрица размерности k k, а -R — матрица размерности k (n - k), j-ой строкой которой является вектор из коэффициентов многочлена -rn-j(X). Этот код является также нулевым пространством матрицы H = [RT, In-k], причем j-я строка матрицы HT является вектором коэффициентов многочлена rn-j(X) даже при j n - k.

П р и м е р 33. Для двоичного циклического кода, порожденного многочленом g(X) = X3 + X2 + 1, X6 = g(X)(X3 + X2 + X) + X2 + X X5 = g(X)(X2 + X + 1) + X + + X4 = g(X)(X + 1) + X2 + X + X3 = g(X)(1) + X2 + X2 = g(X)(0) + X X1 = g(X)(0) + X X0 = g(X)(0) + 1 1 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0 1 HT = 1 0 1 и G1 = 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 Теперь рассмотрим двойственный код, т.е. код, порождааемый многочленом (X7-1)/g(X) = (X-1)(X2+X+1) = X4+X3+X2+1.

Для этого порождающего многочлена r6(X) = X3 + X2 + X 1 1 1 r5(X) = X2 + X + 1 0 1 1 r4(X) = X3 + X2 + X + 1 1 1 0 r3(X) = X3 HT = 1 0 0 r2(X) = X2 0 1 0 r1(X) = X 0 0 1 R0(X) = 1 0 0 0 и 1 0 0 1 1 1 G2 = 0 1 0 0 1 1 1.

0 0 1 1 1 0 Матрицы H1 и G2 совпадают, если в одной из них порядок рас положения строк и столбцов заменить на обратный. То же самое верно для матриц G1 и H2.

Предположим, что многочлен f(X) принадлежит кодовому про странству тогда и только тогда, когда элементы 1, 2,..., r яв ляются его корнями. Если f(X) = fn-1Xn-1 + fn-2Xn-2 +... + f0, то при i = 1, 2,..., r n-1 n- f(i) = fn-1i + fn-2i +... + f0 = 0, и это равенство может быть записано при помощи произведения матриц n-1 n- [fn-1, fn-2,..., f0][i, i,..., i]T = 0.

Это условие в точности эквивалентно условию, состоящему в том, что i — корень мнонгочлена f(X). Это условие совпадает так же с условием, состоящем в том, что многочлен f(X) делится на минимальную функцию mi(X) для элемента i. Далее, то что эле менты 1, 2,..., r являются корнями многочлена f(X), эквива лентно условию, состоящему в том, что соответствующий вектор принадлежит нулевому пространству матрицы n-1 n- 1 1 1 · · · 1 n-1 n- 1 2 2 · · · 2 H =..................

n-1 n-2 1 r r · · · r r Совокупность всех многочленов, одним из корней которых яв ляется элемент i, совпадает с нулевым пространством матрицы n-1 n-2 [i, i,..., i ], (8.1) и поскольку эта совокупность многочленов совпадает с многочле нами, которые делятся на минимальную функцию mi(X) степени mi, то они образуют идеал, размерность которого равна n - mi.

Так как размерность нулевого пространства матрицы (8.1) равна n-mi, то размерность пространства строк матрицы равна mi. За метим, что коэффициенты кодовых многочленов принадлежат по лю GF (q), а i — элемент расширения поля, если только mi = 1.

Элементы расширения поля можно рассматривать как векторы с mi компонентами над основным полем. Следовательно, размер ность пространства строк матрицы (8.1) надGF (q) равна mi.

Если i и j определяют один и тот же минимальный много член mi(X) = mj(X), то соответствующие им нулевые простран ства совпадают и, следовательно, соответствующие пространства строк определяют одно и то же пространство над полем GF (q). По этому при построении матрицы H в разложении многочлена g(X) нужно использовать только один корень каждого неприводимого сомножителя.

П р и м е р 34. Рассмотрим двоичный циклический код, со держащий вектор {f(X)} тогда и только тогда, когда элементы, 2,..., 6 являются корнями многочлена f(X). Здесь — корень многочлена p(X) = X4 + X + 1 и, следовательно, примитивный элемент GF (24). В этом случае g(X) = m1(X)m3(X)m5(X), и достаточно потребовать, чтобы корнями любого многочлена f(X), принадлежащего коду, были элементы, 3, 5. Искомым кодом является нулевое пространство матрицы H, транспониро ванная матрица к которой равна 14 · · · 42 = 12 70 = 13 · · · 39 = 9 65 = 12 · · · 36 = 6 60 = HT =......................

1 · · · 3 1 · · · 1 или 1001 1111 1101 1010 1111 1100 1110 1000 0111 0001 1010 1111 0101 1010 HT = 1011 1100 1100 1000 0110 0001 0011 1111 1000 1010 0100 1100 0010 1000 0001 0001 если подставить, пользуясь таблицей 5.1, векторное представление элементов поля.

Далее, X15 - 1 = (X - 1)(X2 + X + 1)(X4 + X3 + X2 + X + 1) (X4 + X3 + 1)(X4 + X + 1), и легко проверить, что если — корень многочлена X4 + X + 1, то 3 — корень многочлена X4 + X3 + X2 + X + 1, 5 — корень многочлена X2 + X + 1. Поэтому ранг матрицы (14, 13,..., 0) равен 4 и ранг матрицы (42, 39,..., 0) также равен 4, поскольку степени минимальных функций для каждого из элементов и равны 4. Степень минимальной функции для элемента 5, однако, равна 2, и ранг матрицы (70, 65,..., 0) должен быть равен 2.

Очевидно, что это так;

в матрице HT девятый столбец состоит из нулей, а десятый и одинадцатый столбцы полностью совпадают.

8.3. Коды Боуза – Чоудхури – Хоквингема (БЧХ) Пусть — элемент из поля GF (qm). При любых заданных зна чениях m0 и d0 код, порожденный многочленом g(X), является БЧХ-кодом тогда и только тогда, когда многочлен g(X) явля ется многочленом наименьшей степени над GF (q), для которого 0 0 m, m +1,..., m +d0-2 — корни.

Длина кода равна наименьшему общему кратному порядков корней. За исключением того случая, когда задатся только один корень m, длина кода n равна порядку e элемента. Так как 0 0 0 (m )n = m n = 1, (m +1)n = m n+n = и, следовательно, n = 1, длина кода n делится на e и n не может быть меньше чем e — порядок элемента. С другой стороны, если e = 1, то (j)e = 1, так что число e делится на порядок каждого элемента j. Поэтому n не больше e, и, следовательно, n = e.

Наибольшее значение имеют двоичные БЧХ-коды, получающи еся, если в качестве выбрать примитивный элемент поля GF (2m) и положить m0 = 1, а d0 = 2t0 + 1. Тогда вектор {f(X)} принад лежит коду тогда и только тогда, когда элементы, 2, 3,..., 2t являются корнями многочлена f(X). Однако каждая четная сте пень является корнем минимальной функции, являющейся также минимальной функцией для некоторой предшествуюющей нечет ной степени. Например, если mj(X) обозначает минимальную функцию для j, то 2, 4 — корни m1(X), 6 — корень m3(X), — корень m1(X), 10 — корень m5(X) и т.д. Следовательно, можно дать следующее эквивалентное определение кода: вектор {f(X)} принадлежит коду тогда и только тогда, когда элементы 0-, 3,..., 2t являются корнями многочлена f(X). Итак, код порождается мно гочленом g(X) = НОК(m1(X), m3(X),..., m2t (X)), (8.2) 0- причем степень каждого многочлена mi(X), как следует из теорем 51 и 59, не превосходит m. Таким образом, степень многочлена g(X) не превосходит mt0.

Другим важным подклассом БЧХ-кодов являются коды Рида Соломона, получаемые при m = m0 = 1. Пусть элемент GF (q) порядка n. (Если — примитивный элемент, то n равно своему наибольшему значению q - 1.) Пусть вектор{f(X)} является ко довым вектором тогда и только тогда, когда элементы, 2,..., d- являются корнями многочлена f(X). Минимальная функция для j равна просто X - j, так что g(X) = (X - )(X - 2)...(X - d-1). (8.3) Степень многочлена g(X) равна d - 1. В результате получается код длмны n с d - 1 проверочными символами и с минимальным расстоянием, равным d [4].

8.4 Процедура исправления ошибок Здесь рассматривается процедура исправления ошибок для БЧХ-кода. Эта процедура позволяет исправлять любые комбина ции из t0 или меньшего числа ошибок, если d0 2t0 + 1.

На первом этапе построения процедуры исправления ошибок нужно найти способ описания информации об ошибках, которую дают проверочные соотношения, т.е. синдром. Предположим, что передан кодовый вектор f(X), при передаче произошли ошиб ки и принят вектор r(X) = f(X) + e(X). Рассмотрим резуль 0 0 тат подстановки m, m +1,..., m +2t0-1 в многочлен r(X). По скольку f(X) — кодовый вектор и, следовательно, эти элемен ты будут его корнями, то в результате подстановки получим 0 0 e(m ), e(m +1),..., e(m +2t0-1).

Вектор ошибок e(X) можно задать перечнем значений его нену левых компонент и позиций, на которых они расположены. Эти по зиции будут определяться номерами позиций ошибок;

для (n-j)-го символа это просто j. Каждая ненулевая компонента e(X) описы вается парой элементов Yi (величиной ошибки) и Xi (номером по зиции ошибки);

здесь Yi — элемент GF (q), а Xi — элемент GF (qm).

Если произошло ощибок, то e(X) имеет ненулевых компонент и, следовательно, для описания ошибок требуется пар (Xi, Yi).

Тогда e(j) = YiXij = Sj (8.4) i= и значения Sj = e(j) задаются проверками при m0 j m0 + 2t0 - 1. Заметим, что согласно теоремам 49 и (Sj)q = ( YiXij)q = YiqXiiq = Siq. (8.5) i+1 i= В двоичном случае возможно некоторое упрощение. Так как ве личина Yi не равна 0, то она должна быть равна 1. Для ис правления ошибки необходимо знать лишь ее положение, и по этому вектор ошибок полностью описывается перечнем номеров позиций ошибок. Из принятого вектора вычисляются t0 величин Sj, m0 j m0 + 2t0 - 1, и, для того чтобы исправить ошибки, должна быть найдена пара (Yi, Xi) для каждой из t0 или меньшего числа ошибок. Уравнения Sj = YiXij, m0 j m0 + 2t0 - 1 (8.6) i связывают известные и искомые величины, и любой метод реше ния этих уравнений составляют основу процедуры исправления ошибок.

Предположим, что в действительности происходит t0 оши бок. Они описываются парами (Yi, Xi), причем ни Yi, ни Xi не равны 0. Пусть уравнение (X - X1)(X - X2)...(X - X) = X + 1X-1 +...

..., -1X + (8.7) определяет величины 1, 2,...,, являющимися элементарными симметрическими функциями от Xi. Заметим, что если в урав нение (8.7) вместо X подставить Xi, то обе его части обратятся в нуль. Оказывается тогда, что величины Sj и i связаны системой линейных уравннений и это позволяет определить i. Значения Xi могут быть найдены последовательной подстановкой всех элемен тов всех элементов поля в уравнение (8.7). При известных значе ниях Xi уравнения Xi уравнения (8.4) линейны относительно Yi и могут быть решены.

Следующий этап состоит в нахождении соотношения, связыва ющего SJ и i и доказательстве того, что решение всегда сущест вует. Если обе части уравнения (8.7) умножить на YiXij и затем всесто X подставить Xi, то получится следующее уравнение:

YiXij + YiXij+1-1 +... + YiXij+-11 + YiXij+ = 0. (8.8) Суммируя эти уравнения по всем значениям i, 1 i, и ис пользуя выражения (8.4), получим соотношения, связывающте i и Sj:

Sj + Sj+1-1 +... + Sj+-11 + Sj+ = 0, (8.9) где все Sj изветсны для m0 j m0 + 1t0 - 1 -.

Теорема 63. Матрица Sm Sm +1... Sm +- 0 0 Sm +1 Sm +2... Sm + 0 0......

M = (8.10)......

......

Sm +-1 Sm +... Sm +2- 0 0 невырождена, если величины Si образуются точно из раз личных ненулевых пар (Yi, Xi). Матрица вырождена, если Si об разуются из меньшего чем числа ненулевых пар (Yi, Xi).

Д о к а з а т е л ь с т в о. Используя уравнения (8.4) можно проверить, что 1 1... X1 X2... X......

M =......

......

-1 - - X1 X2... X m Y1X1 0... 0 1 X1... x- m - 0 Y2X2... 0 1 X2... X............

. (8.11)............

......

......

m0 - 0 0... YX 1 X... X Матрица M невырождена тогда и только тогда, когда каждая из матриц в (8.11) невырождена. Первая и последняя матрицы — это матрицы Вандермонда, и они не вырождены тогда и только тогда, когда X1, X2,..., X различны. Средняя матрица диагональ ная и невырождена тогда и только тогда, когда все Xi и Yi нену левые. Таким образом, матрица M невырождена тогда и только тогда, когда все пары (Yi, Xi) различны и не равны нулю.

Для того чтобы из степенных сумм и номеров позиций ошибок можно было определить значения Yi, необходимо, чтобы уравне ний (8.4) были линейно независимы. Рассмотрим первые урав нений относительно Yi:

m0 m m Y1X1 +Y2X2 +... +YX = Sm, m0+1 m0+ m0+ Y1X1 +Y2X2 +... +YX = Sm +1,..................

m0+-1 m0+- m0+- Y1X1 +Y2X2 =... +YX = Sm +-1.

(8.12) Определитель системы равен m 0 m X1 xm... X m0+1 m0+ m0+ X1 X2... X......

=......

......

m0+-1 m0+- m0+- X1 X2... X 1 1... X1 X2... X......

m0 m0 m = X1 X2...X ;

(8.13)......

......

-1 - - X1 X2... X Определитель в правой части есть определитель Вандермонда.

Поэтому, если все Xi различны и ненулевые, а в данном случае так оно и есть, то правая часть не равна нулю. Следовательно, урав нения (8.12) линейно независимы и, если X1, X2,..., X найдены, они могут быть решены относительно неизвестных Y1, Y2,..., Y.

Из (8.13) видно, что эти значения ошибок могут быть определены посредством обращения матриц.

Исправление ошибок может быть проведено следующим обра зом:

1. По принятому вектору вычисляются значения Sj, m0 j m0 +2t0 -1. По существу вычисляются проверочные соотношения.

2. Орпеделяется максимальное число последовательных уравне ний, являющихся линейно независимыми. Оно равно числу дей ствительно произошедших ошибок.

3. Все +1, +2,..., t полагаются равными нулю, и решаются первые уравнений относительно 1, 2,...,.

4. Каждый ненулевой элемент GF (qm) подставляется в много член X + 1X-1 +... +. (8.14) корни многочлена будут номерами позиций ошибок X1, X2,..., X.

5. (Этап не нужный в двоичном случае.) Номера позиций оши бок, полученные на четвертом этапе, подставляются в первые уравнений (8.4) и находятся соответствующие неизвестные вели чины Yi. Определитель матрицы коэффициентов не равен нулю.

Следовательно, эти уравнения линейно независимы. Знания зна чений Xi и Yi достаточно для исправления ошибок.

П р и м е р 35. Пусть {f(X)} принадлежит коду тогда и только тогда, когда, 2,..., 6 являются корнями многочлена f(X), при чем — примитивный элемент поля GF (24), 15 = 1. Длина кода равна 15. Было получено g(X) = m1(X)m3(X)m5(X) Это (15,5)-БЧХ-код, исправляющий все комбинации из трех или меньшего числа ошибок. Предположим, что произшло две ошибки на позициях, соответствующих 3 и 10. Тогда вычисления прове рок на четность принятонго вектора {r(X)} дают (см. табл. 5.1) S1 = r() = (1111) = 12, S3 = r(3) = (1011) = 7, (8.15) S5 = r(5) = (0111) = и S2 = S1 = 9 = (1010), S4 = S2 = 3 = (1000), (8.16) S0 = S3 = 14 = (1001).

Уравнения (8.9) принимают вид 123 + 92 + 71 = 3, 93 + 72 + 31 = 10, (8.17) 73 + 32 + 101 = 14.

Умножая первое уравнение на 8 = -7, второе — на 12 = -3 и третье — на 5 = -10, получаем 53 + 22 + 1 = 11, 63 + 42 + 1 = 7, 123 + 82 + 1 = 4.

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

(1010)3 + (0111)2 = (0101), или 93 + 102 = 8, (1001)3 + (0001)2 = (1101), или 143 + 2 = 13.

(8.18) Эти уравнения отличаются только множителем 5, и, следователь но, второе уравнение зависит от первого. Поэтому последнее из трех уравнений (8.17) должно зависить от первых двух, и, сле довательно, произошло две ошибки. Полагая в уравнениях (8.18) 3 = 0, получаем 102 = 8, или 2 = 13. Из любого уравнения (8.17) находим 1 = 12. Номера позиций ошибок будут корнями уравнения X2 + 12X + 13 = 0. (8.19) Легко проверить, что этому уравнению удовлетворяют элементы 3 и 10 и только они. Так как рассматриваемый код двоичный, знания номеров позиций ошибок достаточно для исправления этих ошибок — значения ошибочных символов нужно просто изменить на противоположные.

ЛИТЕРАТУРА 1. Биркгоф Г., Барти Т. Современная прикладная алгеб ра. М.,Мир, 1976. 400 с.

2. Ван-дер-Варден Б.Л. Алгебра. М.,Наука, 1976. 647 с.

3. Горьковой В.Ф. Графы Бержа: изоморфизм, декомпо зиция, раскраски. СПбУ, 1994. 180 с.

4. Питерсон У.,Уэлдон. Э. Коды, исправляющие ошиб ки. М.,Мир, 1976. 595 с.

5. Харари Ф. Теория графов. М., Мир, 1973. 336 с.

6. Холл М. Теория групп. М.,Изд.ин.лит., 1962. 468 с.

7. Chinal J. Design methods for digital systems. Acad. Verlag. Berlin, 1973. 506 p.

8. Arbib M.A. Algebraic Theory of Machines. Languages and Semigroups, Academic Pres,New York, 1968. 335 p.

9. Whitesitt J.E. Boolean Algebra and its Applications.

Addison-Wesley, New york, 10. Barti T.C. Digital Computer Fundamentals, 2ed.

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.