TechShape.ru

Информационные технологии

Основные разделы

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

𝑝	𝑞	𝑟
И	И	И	И
И	И	Л	Л
И	Л	И	И
И	Л	Л	И
Л	И	И	Л
Л	И	Л	Л
Л	Л	И	И
Л	Л	Л	Л

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

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]). Таким образом, получаем матрицу достижимости:

Перейти на страницу: 1 2 3 4 5

Еще статьи

Проектирование волоконно-оптической линии передачи
волоконная оптическая линия передача Одним из наиболее перспективных направлений развития многоканальных систем передачи является использование оптического диапазона частот. Длительное время практическая реализация оптических систем передачи сдерживалась несовершенством элементной базы и, особенно, отсут ...