Корректирующие коды. Линейные групповые коды. Код Хэмминга
Вариант 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.
, .
?3 = ?2 + 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.
а
Таблица смежных классов:
0000001101010110100010111101111001000111000100101100111110011010
Для кода Адамара: 0 = 1, 1 = -1.
Получено сообщение
, т.е.
- это разрешенная кодовая комбинация, т.е. ошибок нет.
Получено сообщение
, т.е.
- ошибка произошла в первом разряде, кодовое слово без ошибки: (1 -1 -1 1).
7б
- ошибок нет.
- есть однократная ошибка.
Т.к. кодовое расстояние для данного кода dmin = 2, то по синдрому можно определить только наличие или отсутствие однократной ошибки (to + 1 ? dmin, 2tи + 1 ? dmin).
8
символабсдеикртчастота7123294581
, ,, ,
, , ,
, , .
б0,23530,23530,23530,23530,2549*0,3333*0,4118*0,5882*1*е0,17650,17650,17650,17650,23530,25490,33330,4118р0,15690,15690,15690,1764*0,17650,23530,2549а0,13730,13730,13730,15690,17640,1765к0,0980,0980,1176*0,13730,1569и0,07840,07840,0980,1176с0,05880,05880,0784д0,03920,0588*т0,0196
б. Код Хаффмана:
СимволабсдеикртВероятность0,13730,23530,05880,03920,17650,07840,0980,15690,0196Код10101100110001001110111111010000
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
Больше работ по теме:
Предмет: Информатика, ВТ, телекоммуникации
Тип работы: Контрольная работа
Новости образования
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2020 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ