Главная страница  Алгебраическая теория кодирования 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [ 11 ] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

Продолжая этот процесс, находим следующее уравнение, содержащее только два неизвестных, а именно уравнение с номером 7: 2 -(- = 0. Соответственно отмечаем в уравнении 7 координату 7 кружком и подставляем 2 вместо 7 в уравнения 1, 5 и 8. При этом в уравнении 5 координата 2 взаимно уничтожается с ранее уже имевшейся координатой 2.

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

уравнения

Переменные

®

®

Следующим уравнением, содержащим только две координаты, является уравнение 9. Отметим в нем кружком координату 5 и заменим ее координатой О во всех остальных уравнениях.

Ншер уравнения

Переменные

О 1 2 3 4 5 6 7

4 Ж 8 4 X 2 4 8

13X0 X X X О

2 3 6 2 (7)

6 X 8 2 О ®

Номер уравнения

Переменные

0 Ж 4 Ж 8

1 14X2

2 X. 4 8

3 8 (9)

4 1 3 Ж Ж

5 X X X ©

6 2 3 6

7 2 @

8 6 X 8 2

9 Ж (D

Еще раз просмотрим систему и отметим кружками (с соответствующими заменами) координату 8 в уравнении номер О и координату 3 в уравнении номер 4.

Номер уравнения

Переменные

Номер уравнения

Переменные

®

®

®

®

®

®

2 4

2 4

®

©



Гл. 2. Арифметические операции по модулю многочлена

Теперь мы пришли к системе только из трех уравнений: Уравнение 1: + Z4 + = О, Уравнение 6: Zg + Zg + Z = О, Уравнение 8: Zg + Z + Z4 = 0.

Каждое из этих уравнений содержит три неизвестных, и так как ;<аждая пара уравнений содержит только два общих неизвестных, го дальнейшее уменьшение числа переменных можно осуществлять разными способами. Одним из возможных путей является определе-аие Z4 из уравнения 1 в виде Z4 = Zj + Zj и подстановка этого зыражения в уравнение 8:

Номер уравнения

Переменные

®

®

®

®

©

X X 1

®

Тогда Ze будет определяться уравнением 8, а Zj - уравнением 6:

Номер {/равнения

Пспгменные

Номер уравнения

Переменные

®

®

®

®

®

®

X >

®

®

®

. 4

®

®

®

®

X X 1

®

На этом приведение матрицы заканчивается. Каждое Z, за исключением Zi, определяется через координаты с меньшими индексами. Значение Z может быть, очевидно, произвольным. Если выбрать Zi = О, то получим тривиальное решение Z = 0. Выбор Z = 1 приводит к нетривиальному решению. Из уравнения 5 определяем, что Zfl = 0. Решение Zj = О получается из уравнения 6. В силу уравнения 4 выполняется равенство Z3 = Zj, и так как Z = 1, то и Z3 = 1. Аналогичным образом находятся и все остальные координаты к,

для которых Zk = О

О 2 5 7

для которых Zk = 1

1 3 4 6 8 9

Можно проверить, что 2 = [О 101101011] действительно является решением рассматриваемой системы.

После небольшой практики читатель сможет быстро решать примеры следующего типа.

2.61. Пример. Решить уравнение = О, где

ООО о 1 1

0 о 1

ООО ООО ООО ООО ООО

1 1 О

о о 1

ООО ООО ООО ООО ООО

L0 о о

ООО ООО

0 1 о

1 о о о 1 о

0 о 1

ООО ООО ООО

1 О о о 1 1 ООО ООО ООО ООО ООО

ООО ООО ООО 1 О о

0 о 1 ОО о

1 о О О 1 о

0 о 1

ООО ООО

1 1 о

о о 1

ООО ООО ООО

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 10 0

0 0 0 1

0 0 0 0

0 0 0 0

10 0 0

0 10 0

0 0 10

10 0 1

0 110

0 0 0 1

0 0 0 0

о о 01

6 0 0

0 1 о ООО ООО ООО ООО ООО

1 о О 1 1 о о 1 о



Гл. 2. Арифметические операции по модулю многочлена

е ш е н и е

Задачи

2.3. Найти все решения двоичного уравнения ZJG = О, где

18 ® X

2 1 9 2 Ж ®

3 9 (D Ж 2

4 2 10 X Ж М ®

5 10 5 (g)

6 3 11 ® X X 2 Ж

7 И 7 (и)

8 4 12 X 4 (g)

9 12 Ж X Д ® 10 5 13 М X (IB)

U 13 XX®

12 6 И X X М X Ж

13 14 X @ U 7 15 К X (15)

.2? =

0 0 0 0 0 0 110 0

0 0 10 1

0 0 0 1 0

0 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 10 0 0

0 0 0 1 0

0 0 0 0 0

0 0 0 0 0

1 0 0 0 0 0 0 10 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 10 0 0

0 0 0 1 0

1 0 0 0 0 0 10 0 0 0 0 10 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0

1 0 0 0 0 0 0 10 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 10 0 0

ООО ООО ООО ООО ООО 1 О о

0 о 1

ООО ООО ООО

1 1 о О 1 о

0 о 1

1 1 о о о 1 ООО

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 0 10 0 0 0 0 10 10 0 0 0 10 0 10 10 0 111

Zi = Zs = Z, = Zg = Zio = Zn = Z9 = Zi2=l- Если Z2 = " -" = 0.* в любом случае Z„ произвольно.

Zu = = 0

Если m очень велико, то оказывается Цразным составл

НИИ, содержащих Z, не надо просматривать всю систему, а достаточ но просмотреть дополнительную таблицу.

Задачи

2.1. используя вариант непрерывных дробей алгоритма Евклида, найти такие двоичные многочлены А и В, что

(5 + 3 + 1) + В (х) (х» + х5 + + + 1) = 1-

2 2 Найти все решения (если таковые существуют) уравнения = U, где I есть 4 X 4-матрица над полем классов вычетов по модулю 7.

13 3 6 0 4 0 2 5 12 6

L2 О 4 5

и = [0014].




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [ 11 ] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

0.0159