Корректирующие коды.
Линейные групповые коды.
Код Хэмминга

Тип работы:
Контрольная
Предмет:
Коммуникации, связь, цифровые приборы и радиоэлектроника


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Вариант 24

??

??

??

И

И

И

И

И

И

Л

Л

И

Л

И

И

И

Л

Л

И

Л

И

И

Л

Л

И

Л

Л

Л

Л

И

И

Л

Л

Л

Л

В дизъюнктивной нормальной форме:

1б. Система множеств {x1, x2, …, xn} наз. разбиением множества А, если она удовлетворяет след. условиям:

1) Любое множество X{x1, x2, …, xn} явл. помножеством мн-ва А.

2) Любые два мн-ва Xi, Xj{x1, x2, …, xn}явл. непересекающимися.

3) Объединение всех мн-в, входящих в разбиение, дает мн-во А.

Задано мн-во ?? = {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).

Для заданного графа невозможно построить цикл

Идея алгоритма Уоршелла состоит в расширении множества промежуточных вершин по следующему правилу: на каждом шаге в рассмотрение добавляется одна новая вершина, после чего достижимости вершин пересчитываются «через нее». Если 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.

3

?? =, ?? =

U =? =

?? =? =

= =

4

???(4) = GF (22)? p = 2, q = 4 (p — хар-ка поля, q — кол-во эл-тов в поле)

2? +

?? + 2? = 3

y = 1, x = 1.

5

,.

б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.

Таблица смежных классов:

0000

0011

0101

0110

1000

1011

1101

1110

0100

0111

0001

0010

1100

1111

1001

1010

Для кода Адамара: 0 = 1, 1 = -1.

Получено сообщение

, т. е.

— это разрешенная кодовая комбинация, т. е. ошибок нет.

Получено сообщение

, т. е.

— ошибка произошла в первом разряде, кодовое слово без ошибки: (1 -1 -1 1).

— ошибок нет.

— есть однократная ошибка.

Т.к. кодовое расстояние для данного кода dmin = 2, то по синдрому можно определить только наличие или отсутствие однократной ошибки (to + 1? dmin, 2tи + 1? dmin).

8

символ

а

б

с

д

е

и

к

р

т

частота

7

12

3

2

9

4

5

8

1

,, ,

,, ,

,, .

б

0,2353

0,2353

0,2353

0,2353

0,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

8б. Код Хаффмана:

Символ

а

б

с

д

е

и

к

р

т

Вероятность

0,1373

0,2353

0,0588

0,0392

0,1765

0,0784

0,098

0,1569

0,0196

Код

101

01

1001

10 001

00

1110

1111

110

10 000

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

ПоказатьСвернуть
Заполнить форму текущей работой