ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 121
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Контрольные вопросы
1. Что такое система счисления? Какие системы счисления сейчас при- меняются?
2. Как осуществляется перевод из десятичной системы счисления в двоичную и обратно?
3. Как осуществляется перевод между двоичной и шестнадцатеричной системами счисления?
4. Что такое двоично-десятичная система счисления?
5. Что такое конъюнкция?
6. Что такое дизъюнкция?
7. Нарисуйте схему сумматора по модулю 2.
8. Как работает полный двоичный сумматор? Нарисуйте схему.
9. Как строится полный двоичный многоразрядный сумматор?
10. Как производится перемножение многоразрядных двоичных чисел?
26
3. МАТРИЦЫ И ДЕЙСТВИЯ НАД НИМИ
3.1. Понятие матрицы
Матрицей называется прямоугольная таблица чисел из некоторого чис- лового поля, имеющая m строк и n столбцов [
7
,
8
]:
a
11
a
12
. . . a
1n a
21
a
22
. . . a
2n a
m
1
a m
2
. . . a mn
В общем случае такая матрица называется прямоугольной размера m × n или m
× n-матрицей. Если m = n, то матрица называется квадратной порядка n.
Числа, составляющие матрицу, называются ее элементами. При двухиндекс- ном обозначении элементов, например a
12
, первый индекс всегда указывает номер строки, а второй индекс — номер столбца, на пересечении которых стоит данный элемент [
7
,
8
].
Каждой m × n-матрице A с элементами a i j соответствует n × m-матрица с элементами a ji
. Она называется транспонированной к A и обозначается че- рез A
T
. (A
T
)
T
= A. Строки матрицы A становятся столбцами в A
T
и столбцы матрицы A становятся строками в A
T
[
8
]:
A =
1 3
5
−3 3
5 12 6
7 −4 −8 2
−→
A
T
=
1 3
7 3
5
−4 5
12 −8
−3 6 2
Прямоугольная матрица размера m × 1, т. е. состоящая из одного столб- ца, называется вектор-столбцом или столбцевой матрицей. Прямоугольная матрица размера 1 × n, т. е. состоящая из одной стороки, называется вектор- строкой или строчной матрицей [
7
,
8
].
Квадратная матрица, в которой все элементы ниже или выше главной диагонали равны нулю, называется треугольной. Соответственно, если все элементы ниже главной диагонали равны нулю, то матрица является верх- нетреугольной, а если все элементы выше главной диагонали равны нулю,
то нижнетреугольной. Определитель треугольной матрицы равен произведе- нию элементов на её главной диагонали. Треугольная матрица, в которой все элементы на главной диагонали равны единице, получила название верхней или нижней унитреугольной. Соответственно, определитель такой матрицы
27
равен единице [
7
,
8
].
Верхнетреугольная матрица :
Нижнетреугольная матрица :
a
11
a
12
. . . a
1n
0
a
22
. . . a
2n
0 0
. . . a nn
a
11 0
0
a
21
a
22 0
a n
1
a n
2
. . . a nn
Квадратную матрицу, у которой все элементы, расположенные вне глав- ной диагонали, равны нулю, называют диагональной. Эта матрица являет- ся частным случаем как верхнетреугольной, так и нижнетреугольной матриц
[
7
,
8
]:
d
1 0
0 0
d
2 0
0 0
. . . d n
Диагональная матрица, в которой все элементы главной диагонали рав- ны 1, называется единичной [
8
]:
1 0
0 0
1 0
0 0
1
Еще одним частным случаем квадратной матрицы является диагональ- но-постоянная матрица или матрица Тёплица, названная в честь немецко- го математика Отто Тёплица (1881–1940). Это матрица, в которой на всех диагоналях, параллельных главной, стоят равные элементы, т. е. выполняется соотношение a i j
= a i
−1, j−1
[
9
].
В общем виде n × n матрица Тёплица имеет вид:
a
0
a
−1
a
−2
a
−n+1
a
1
a
0
a
−1
a
2
a
1
. . . ... ... a
−1
a
−2
. . . a
1
a
0
a
−1
a n
−1
a
2
a
1
a
0
По аналогии с треугольными матрицами выделяют верхнетреугольные и нижнетреугольные матрицы Тёплица.
28
7
,
8
].
Верхнетреугольная матрица :
Нижнетреугольная матрица :
a
11
a
12
. . . a
1n
0
a
22
. . . a
2n
0 0
. . . a nn
a
11 0
0
a
21
a
22 0
a n
1
a n
2
. . . a nn
Квадратную матрицу, у которой все элементы, расположенные вне глав- ной диагонали, равны нулю, называют диагональной. Эта матрица являет- ся частным случаем как верхнетреугольной, так и нижнетреугольной матриц
[
7
,
8
]:
d
1 0
0 0
d
2 0
0 0
. . . d n
Диагональная матрица, в которой все элементы главной диагонали рав- ны 1, называется единичной [
8
]:
1 0
0 0
1 0
0 0
1
Еще одним частным случаем квадратной матрицы является диагональ- но-постоянная матрица или матрица Тёплица, названная в честь немецко- го математика Отто Тёплица (1881–1940). Это матрица, в которой на всех диагоналях, параллельных главной, стоят равные элементы, т. е. выполняется соотношение a i j
= a i
−1, j−1
[
9
].
В общем виде n × n матрица Тёплица имеет вид:
a
0
a
−1
a
−2
a
−n+1
a
1
a
0
a
−1
a
2
a
1
. . . ... ... a
−1
a
−2
. . . a
1
a
0
a
−1
a n
−1
a
2
a
1
a
0
По аналогии с треугольными матрицами выделяют верхнетреугольные и нижнетреугольные матрицы Тёплица.
28
3.2. Операции с матрицами
3.2.1. Сложение матриц
Складываются только матрицы одного размера. Сложение матриц про- изводится поэлементно [
8
]:
a
11
a
12
. . . a
1n a
21
a
22
. . . a
2n a
m
1
a m
2
. . . a mn
+
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
m
1
b m
2
. . . b mn
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i j
+ b i j
Например,
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
a
41
a
42
a
43
+
b
11
b
12
b
13
b
21
b
22
b
23
b
31
b
32
b
33
b
41
b
42
b
43
=
a
11
+ b
11
a
12
+ b
12
a
13
+ b
13
a
21
+ b
21
a
22
+ b
22
a
23
+ b
23
a
31
+ b
31
a
32
+ b
32
a
33
+ b
33
a
41
+ b
41
a
42
+ b
42
a
43
+ b
43
или
1 3
5
−3 3
5 12 6
7 −4 −8 2
+
4 −2 3
1 8 −6 1
4 2
4 13 5
=
5 1
8
−2 11 −1 13 10 9
0 5
7
3.2.2. Умножение матрицы на число
При умножении матрицы на число, каждый элемент матрицы умножа- ется на это число [
8
]:
b
·
a
11
a
12
. . . a
1n a
21
a
22
. . . a
2n a
m
1
a m
2
. . . a mn
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= b · a i j
Например,
3 ×
1 3
5
−3 3
5 12 6
7 −4 −8 2
=
3 9
15
−9 9
15 36 18 21 −12 −24 6
3.2.3. Произведение матриц
Матрицы умножаются по правилу «строка-на-столбец». Для того, что- бы матрицу A можно было умножить на матрицу B, количество столбцов в A
29
должно быть равно количеству строк в B. Таким образом, результатом про- изведения m × l-матрицы A на l × n-матрицу B будет m × n-матрица C [
8
]:
a
11
a
12
. . . a
1l a
21
a
22
. . . a
2l a
m
1
a m
2
. . . a ml
·
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
l
1
b l
2
. . . b ln
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i
1
· b
1 j
+ a i
2
· b
2 j
+ . . . + a il
· b l j
Например,
1 3
5
−3 3
5 12 6
7 −4 −8 2
×
4 −2 3
1 8 −6 1
4 2
4 13 5 4
1 0
2
=
26
−3 71 32 100 18 170 95
−12 −20 −87 −45
Для примера рассмотрим умножение первой строки матрицы A на пер- вый столбец матрицы B:
(1 · 4) + (3 · 8) + (5 · 2) + (−3 · 4) = 26.
3.2.4. Сложение двоичных матриц по модулю 2
Сложение двоичных матриц (т. е. матриц, элементы которых являются двоичными цифрами 0 или 1) по модулю 2, производится поэлементно и, как и обычное сложение, осуществляется над матрицами одного размера:
a
11
a
12
. . . a
1n a
21
a
22
. . . a
2n a
m
1
a m
2
. . . a mn
⊕
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
m
1
b m
2
. . . b mn
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i j
⊕ b i j
Например,
1 0 1 1 1 1 0 1 0 0 1 1
⊕
0 1 0 1 1 1 1 0 0 1 1 1
=
1 1 1 0 0 0 1 1 0 1 0 0
3.2.5. Произведение двоичных матриц
Произведение двоичных матриц A и B осуществляется по обычному правилу «строка-на-столбец». Соответственно, как и при умножении обыч- ных матриц, количество столбцов в A должно быть равно количеству строк
30
8
]:
a
11
a
12
. . . a
1l a
21
a
22
. . . a
2l a
m
1
a m
2
. . . a ml
·
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
l
1
b l
2
. . . b ln
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i
1
· b
1 j
+ a i
2
· b
2 j
+ . . . + a il
· b l j
Например,
1 3
5
−3 3
5 12 6
7 −4 −8 2
×
4 −2 3
1 8 −6 1
4 2
4 13 5 4
1 0
2
=
26
−3 71 32 100 18 170 95
−12 −20 −87 −45
Для примера рассмотрим умножение первой строки матрицы A на пер- вый столбец матрицы B:
(1 · 4) + (3 · 8) + (5 · 2) + (−3 · 4) = 26.
3.2.4. Сложение двоичных матриц по модулю 2
Сложение двоичных матриц (т. е. матриц, элементы которых являются двоичными цифрами 0 или 1) по модулю 2, производится поэлементно и, как и обычное сложение, осуществляется над матрицами одного размера:
a
11
a
12
. . . a
1n a
21
a
22
. . . a
2n a
m
1
a m
2
. . . a mn
⊕
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
m
1
b m
2
. . . b mn
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i j
⊕ b i j
Например,
1 0 1 1 1 1 0 1 0 0 1 1
⊕
0 1 0 1 1 1 1 0 0 1 1 1
=
1 1 1 0 0 0 1 1 0 1 0 0
3.2.5. Произведение двоичных матриц
Произведение двоичных матриц A и B осуществляется по обычному правилу «строка-на-столбец». Соответственно, как и при умножении обыч- ных матриц, количество столбцов в A должно быть равно количеству строк
30
в B. Отличием является то, что при вычислении элементов результирующей матрицы C используется не обычное сложение, а сложение по модулю 2:
a
11
a
12
. . . a
1l a
21
a
22
. . . a
2l a
m
1
a m
2
. . . a ml
·
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
l
1
b l
2
. . . b ln
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i
1
· b
1 j
⊕ a i
2
· b
2 j
⊕ . . . ⊕ a il
· b l j
Например,
1 0 1 1 1 0
·
0 1 0 1 1 1 1 0 0 1 1 1
=
0 0 1 0 1 0 1 1
Контрольные вопросы
1. Что такое матрица? Какие виды матриц бывают?
2. Что такое транспонированная матрица?
3. Как производится умножение матриц?
31
a
11
a
12
. . . a
1l a
21
a
22
. . . a
2l a
m
1
a m
2
. . . a ml
·
b
11
b
12
. . . b
1n b
21
b
22
. . . b
2n b
l
1
b l
2
. . . b ln
=
c
11
c
12
. . . c
1n c
21
c
22
. . . c
2n c
m
1
c m
2
. . . c mn
,
где c i j
= a i
1
· b
1 j
⊕ a i
2
· b
2 j
⊕ . . . ⊕ a il
· b l j
Например,
1 0 1 1 1 0
·
0 1 0 1 1 1 1 0 0 1 1 1
=
0 0 1 0 1 0 1 1
Контрольные вопросы
1. Что такое матрица? Какие виды матриц бывают?
2. Что такое транспонированная матрица?
3. Как производится умножение матриц?
31
4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Любая совокупность элементов произвольного рода образует множе- ство. Множество, состоящее из конечного числа элементов, называется ко- нечным множеством [
10
].
Если существует два множества A и B, и при этом каждый элемент множества B принадлежит множеству A, то B называется подмножеством множества A. Все возможные k-элементные комбинации из элементов n-эле- ментного множества представляют собой подмножества n-элементного мно- жества, которые называют сочетаниями из n по k элементов. Иногда вместо слова «сочетание» употребляют термин — комбинация из n элементов по k
[
10
]. Число сочетаний (комбинаций) из n по k обозначают C
k n
[
10
] или (
n k
) [
11
].
В пособии будем использовать первое обозначение. Число сочетаний рассчи- тывается по формуле (
4.1
) [
10
]:
C
k n
= (
n k
) =
n
!
k
!(n − k)!
(4.1)
Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от
1 до n, где n — число элементов множества, так что различным элементам соответствуют различные числа. Упорядоченные множества считаются раз- личными, если они отличаются либо своими элементами, либо их порядком.
Различные упорядоченные множества, которые отличаются лишь порядком элементов (т. е. могут быть получены из того же самого множества), называ- ются перестановками этого множества. Число перестановок обозначается P
n и рассчитывается по формуле (
4.2
) [
10
]:
P
n
= n!.
(4.2)
Упорядоченные k-элементные подмножества множества из n элементов называются размещениями из n элементов по k. Различные размещения из n по k отличаются количеством элементов либо их порядком [
10
]. Число раз- мещений из n по k обозначают A
k n
и рассчитывают по формуле (
4.3
) [
10
]:
A
k n
= k! ·C
k n
=
n
!
(n − k)!
= n(n − 1) . . . (n − k + 1).
(4.3)
Контрольные вопросы
1. Что такое сочетания? Как рассчитывается число сочетаний?
2. Что такое упорядоченное множество?
3. Что такое перестановки? Как рассчитывается число перестановок?
4. Что такое размещения? Как рассчитывается число размещений?
32
5. ПОЛИНОМЫ И ДЕЙСТВИЯ НАД НИМИ
При изучении помехоустойчивых кодов под полиномом (многочленом)
будем понимать многочлен от одной переменной, т. е. конечную сумму вида f
(x) = a
0
+ a
1
x
+ a
2
x
2
+ . . . + a n
x n
,
где a k
— коэффициент многочлена f (x) при x k
[
12
]. Каждый из элементов многочлена вида a k
x k
называется одночленом степени k.
Многочлен, все коэффициенты которого равны нулю, называется нуле- вым многочленом. Если многочлен не является нулевым, то наибольшее из таких чисел k, что a k
6= 0, называется степенью этого многочлена [
12
].
При изучении помехоустойчивого кодирования мы в основном будем сталкиваться с полиномами следующих трех видов.
1. Полином с десятичными коэффициентами.
2. Полином с коэффициентами 0 или 1 (простое поле GF(2)).
3. Полином с коэффициентами, принадлежащими конечному полю
GF(2
p
).
В этом разделе рассмотрим операции с полиномами первых двух видов.
Полиномы с коэффициентами, принадлежащими конечному полю GF(2
p
), за- тронем при рассмотрении математики конечных полей Галуа.
Полиномы можно записывать в виде вектор-строки коэффициентов. На- пример, полином f
(x) = 2 + 4x + 5x
2
+ 3x
4
+ 2x
6
можно записать как f
(x) =
−→
[2 4 5 0 3 0 2]
или f
(x) =
←−
[2 0 3 0 5 4 2],
в зависимости от того, записывать его по возрастанию или по убыванию сте- пеней. Часто такая форма записи применяется для полиномов с коэффициен- тами, принадлежащими простому полю GF(2). Такая запись внешне совпада- ет с записью двоичного числа. Также при работе с литературой необходимо уточнять используется запись по возрастанию или по убыванию степеней. По- лином f
(x) = x
4
+ x + 1
может быть записан как f
(x) =
−→
1 1 0 0 1
или f
(x) =
←−
1 0 0 1 1.
33