Корректирующие коды. Линейные групповые коды. Код Хэмминга
Вариант 24
а
𝑝
|
𝑞
|
𝑟
|
|
И
|
И
|
И
|
И
|
И
|
И
|
Л
|
Л
|
И
|
Л
|
И
|
И
|
И
|
Л
|
Л
|
И
|
Л
|
И
|
И
|
Л
|
Л
|
И
|
Л
|
Л
|
Л
|
Л
|
И
|
И
|
Л
|
Л
|
Л
|
Л
|
В дизъюнктивной нормальной форме:
1б. Система множеств {x1,
x2,
…, xn} наз. разбиением множества А, если
она удовлетворяет след. условиям:
) Любое множество X{x1,
x2,
…, xn} явл. помножеством мн-ва А.
) Любые два мн-ва Xi,
Xj{x1,
x2,
…, xn}явл. непересекающимися.
) Объединение всех мн-в, входящих в разбиение,
дает мн-во А.
Задано мн-во 𝐴
= {1, 2, 3, 4, 5, 6, 7}:
а) {{1, 2}, {3, 4, 5}, {6, 7}} - эта
совокупность элементов составляет разбиение мн-ва А, т.к. удовлетворяет всем
условиям, приведенным выше.
б) {{1, 5}, {3, 4, 5}, {2, 6, 7}} - эта
совокупность элементов не явл. разбиением А, т.к. не удовлетворяет условию
непересекаемости.
2а. Ориентированные пути графа (с
указанием длины пути):
v1v2(1),
v1v4(1),
v1v2v3(2),
v1v2v4(2),
v1v2v3v4(3),
v2v3(1),
v2v4(1),
v2v3v4(2),
v3v4(1),
v5v1(1),
v5v3(1),
v5v3v4(2),
v5v2(1),
v5
v1v2(2),
v5v1v4(2),
v5
v1v2v3(3),
v5
v1v2v4(3),
v5
v1v2v3v4(4),
v5
v2v3(2),
v5
v2v4(2),
v5v2v3v4(3).
Для заданного графа невозможно
построить цикл
2б
Идея алгоритма Уоршелла состоит в
расширении множества промежуточных вершин по следующему правилу: на каждом шаге
в рассмотрение добавляется одна новая вершина, после чего достижимости вершин
пересчитываются “через нее”. Если w - промежуточная вершина, то достижимость
вершины v из вершины u через w пересчитывается по правилу:
D[u;v] = D[u;v] ИЛИ (D[u;w] И D[w;v]). Таким образом, получаем матрицу
достижимости:
Пути ориентированного графа:
v1v2v3v1,
v1v2,
v1v2v3,
v1v2v3v4,
v2v3v1,
v2v3v1v2,
v2v3,
v2v3v4,
v3v1,
v3v1v2,
v3v1v2v3,
v3v4,
v5v1,
v5v1v2,
v5v3,
v5v3v4.
𝐴 = ,
𝐵
=
U = ∨
=
𝐼 = ∧
=
=
=
4
𝐺𝐹(4) = GF(22)
⇒
p = 2, q
= 4 (p - хар-ка поля, q
- кол-во эл-тов в поле)
2𝑥
+
𝑥 + 2𝑦
= 3
y = 1, x
= 1.
, .
α0
= 1;
α1
= α;
α2
= α2;
α3
= α2
+ 1;
α4
= α3
+ α = α2
+ α + 1;
α5
= α3
+ α2
+ α = α
+ 1;
α6
= α2
+ α;
α7
= α3
+ α2
= 1;
Минимальный многочлен элемента β
поля
GF(qm)
определяется по формуле:
Найдем l:
условие выполняется
при l = 3: α48
= α6.
Найдем минимальный многочлен элемента α6:
Проделав преобразования, получим:
M6(x)
= x3
+ x + 1.
6a
Линейный групповой код с повторением с
параметрами [𝑛; 1; 𝑛],
𝑛
= 6.
Длина кодового слова n
= 6, кол-во информационных символов k
= 1, кодовое расстояние dmin
=
6, кол-во проверочных символов r
= n - k
= 5.
Порождающая матрица:
Проверочная матрица:
б
Минимальное расстояние Хэмминга
(кодовое расстояние) кода, порождаемого матрицей Адамара
dmin = 2.
а
Таблица смежных классов:
0000
|
0011
|
0101
|
0110
|
1000
|
1011
|
1101
|
1110
|
0100
|
0111
|
0001
|
0010
|
1100
|
1111
|
1001
|
1010
|
Для кода Адамара: 0 = 1, 1 = -1.
Получено сообщение
, т.е.
- это разрешенная кодовая комбинация, т.е.
ошибок нет.
Получено сообщение
, т.е.
- ошибка произошла в первом разряде, кодовое
слово без ошибки: (1 -1 -1 1).
7б
- ошибок нет.
-
есть однократная ошибка.
Т.к. кодовое расстояние для данного кода dmin
=
2, то по синдрому можно определить только наличие или отсутствие однократной
ошибки (to
+
1 ≤ dmin,
2tи +
1 ≤ dmin).
8
символ
|
а
|
б
|
с
|
д
|
е
|
и
|
к
|
р
|
т
|
частота
|
7
|
12
|
3
|
9
|
4
|
5
|
8
|
1
|
, ,, ,
, , ,
, ,
.
б0,23530,23530,23530,23530,2549*0,3333*0,4118*0,5882*1*
|
|
|
|
|
|
|
|
|
|
е
|
0,1765
|
0,1765
|
0,1765
|
0,1765
|
0,2353
|
0,2549
|
0,3333
|
0,4118
|
|
р
|
0,1569
|
0,1569
|
0,1569
|
0,1764*
|
0,1765
|
0,2353
|
0,2549
|
|
|
а
|
0,1373
|
0,1373
|
0,1373
|
0,1569
|
0,1764
|
0,1765
|
|
|
|
к
|
0,098
|
0,098
|
0,1176*
|
0,1373
|
0,1569
|
|
|
|
|
и
|
0,0784
|
0,0784
|
0,098
|
0,1176
|
|
|
|
|
|
с
|
0,0588
|
0,0588
|
0,0784
|
|
|
|
|
|
|
д
|
0,0392
|
0,0588*
|
|
|
|
|
|
|
|
т
|
0,0196
|
|
|
|
|
|
|
|
|
б. Код Хаффмана:
Символ
|
а
|
б
|
с
|
д
|
е
|
и
|
к
|
р
|
т
|
Вероятность
|
0,1373
|
0,2353
|
0,0588
|
0,0392
|
0,0784
|
0,098
|
0,1569
|
0,0196
|
Код
|
101
|
01
|
1001
|
10001
|
00
|
1110
|
1111
|
110
|
10000
|
9. Даны последовательности длин
L = 4 и M
= 3, соответственно. Апериодическая (линейная) взаимная корреляция определяется
по формуле:
. В матричном виде:
линейный код информационный сигнал
10. Алгоритм Горнера:
Произвольный полином степени N:
.
Представим полином p(z) в виде
.
Вычисление начнем с произведения , затем
суммы , далее
произведения и т.д.
Метод Горнера требует не более N операций умножения и N операций
сложения.
Пример: пусть дан полином p(z) степени
N = 4: p(z) = 4z4 - 2z3 + 3z2 + z - 5.
P (z) = (4z3 - 2z2 + 3z + 1)z - 5 = ((4z2 - 2z + 3)z + 1)z - 5 = (((4z - 2)z +
+ 3) z + 1)z - 5.
Пусть
z = -1: 4·z = 4·(-1) =
-4, -4 - 2 = -6, -6·z = -6·(-1) = 6, 6 + 3 = 9, 9·z = 9·(-1)
= -9, -9 + 1 = -8, -8·z= = -8·(-1)
= 8, 8 - 5 = 3.
Мультипликативная сложность = 4, аддитивная = 4.
Если бы полином считался прямо, то мультипликативная сложность составила бы 6
операций.
Вычисление полинома в точках с
помощью алгоритма «разделяй и властвуй»:
Пусть необходимо вычислить полином в нескольких
точках а1, а2, …, аk,
k ≤
N. Положим сначала
z = a1.
Тогда можно записать
p(z)
= (z - a1)
q(z)
+ r(z),
где q(z)
и r(z)
- частное и остаток от деления p(z)
на (z - a1).
Этот результат можно распространить на большее число точек. Рассмотрим
произведение и запишем p(z)
= m(z)
q(z)
+ r(z).
В точке z = ai
полином m(z)
равен нулю, поэтому p(ai)
= r(ai).
Теперь вычисление полинома p(z)
свелось к вычислению полинома r(z),
степень которого меньше.
Этот подход можно использовать для построения
алгоритма вычисления полинома степени N
- 1 в N точках. Положим N
= 2l.
Разделим N точек на две
половины и образуем полиномы
и.
Разделим p(z)
на m1(z)
и m2(z).
При этом получим остатки r1(z)
и r2(z)
степени N/2. Теперь осталось
вычислить эти остатки в N/2
точках. Для вычисления остатков можно воспользоваться аналогичным приемом,
повторяя его многократно.
Пример: Пусть требуется вычислить полином
p(z)
= 4z3
- 2z2
- 2z + 1 в точках z,
равных -2, 2, 1, -1.
Образуем
m1(z)
= (z + 2)(z
- 2) = z2
- 4, m2(z)
= (z - 1)(z
+ 1) = z2
- 1
После деления p(z)
на m1(z)
и m2(z)
получим остатки
r1(z)
= 14z - 7, r2(z)
= 2z - 1
Далее остатки следует поделить на
соответствующие образующие части полиномов m1(z)
и m2(z):
r1(z)/(z
+ 2) = -35 ⇒ p(-2)
= -35
Аналогично получим
p(2) = 21, p(-1)
= -3, p(1) = 1