5.3.1 Общие понятия
Для защиты полезной информации от помех необходимо в том или ином виде вводить избыточность: увеличивать число символов и время их передачи, повторять целые сообщения, повышать мощность сигнала - все это ведет к усложнению и удорожанию аппаратуры. В качестве исследуемой модели достаточно рассмотреть канал связи с помехами, потому что к этому случаю легко сводятся остальные. Например, запись на диск можно рассматривать как передачу данных в канал, а чтение с диска – как прием данных из канала.
Коды без избыточности обнаружить, а тем более исправлять ошибки не могут. Количество символов, в которых любые две комбинации кода отличаются друг от друга, называется кодовым расстоянием.
Минимальное количество символов, в которых все комбинации кода отличаются друг от друга, называется минимальным кодовым расстоянием. Минимальное кодовое расстояние - параметр, определяющий помехоустойчивость кода и заложенную в коде избыточность, т.е. корректирующие свойства кода.
В общем случае для обнаружения t ошибок минимальное кодовое расстояние
d0 = t + 1.
Минимальное кодовое расстояние, необходимое для одновременного обнаружения t и исправления ошибок,
d0 = t + + 1.,
Для кодов, только исправляющих ошибок,
d0 = 2 + 1.
Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода, достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц полученной комбинации.
Для обнаружения и исправления одиночной ошибки соотношение между числом информационных разрядив k и числом корректирующих разрядов должно удовлетворять следующим условиям:
,
,
при этом подразумевается, что общая длина кодовой комбинации
n = k + ρ
Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием d0 = 3 удобно пользоваться выражениями
ρ1(2) = [ log2 ( n + 1 ) ],
если известна длина полной кодовой комбинации n, и
ρ 1(2) = [log2 { ( k + 1 ) + [ log2 ( k + 1) ] } ],
если при расчетах удобнее исходить из заданного числа информационных символов k .
Для кодов, обнаруживающих все трехкратные ошибки (d0 = 4),
ρ 1(3) 1 + log2 ( n + 1 ),
или
ρ 1(3) 1 + log2 [ ( k + 1 ) + log2 ( k + 1 ) ].
Для кодов длиной в n символов, исправляющих одну или две ошибки (d0 = 5),
ρ 2 log2 (Cn2 + Cn1 + 1).
Для практических расчетов можно пользоваться выражением:
.
Для кодов, исправляющих 3 ошибки (d0 = 7),
.
- Дискретная математика
- 6.050102 “Компьютерная инженерия” содержание
- 1 Теория множеств 7
- 2 Математическая логика 15
- 3 Формальные теории 35
- 4 Теория графов 47
- 5 Элементы теории чисел 80
- 6 Теория алгоритмов 121
- Введение
- 1 Теория множеств
- 1.1 Множества и подмножества
- 1.1.1 Элементы множества
- 1.2 Аксиомы теории множеств
- 1.3 Способы задания множеств
- 1.4 Операции над множествами
- 1.5 Элементы алгебры множеств
- 1.5.1 Определение алгебры множеств
- 1.5.2 Основные законы алгебры множеств
- 1.5.3 Принцип двойственности
- 2 Математическая логика
- 2.1 Функции алгебры логики (булевые функции)
- 2.1.1 Способы задания булевых функций
- 2.1.2 Логические функции одной переменной
- 2.1.3 Логические функции двух переменных
- 2.2.6 Функционально полные системы булевых функций
- 2.3 Алгебра буля
- 2.3.1 Определение алгебры. Теорема Стоуна
- 2.3.2 Законы алгебры логики
- 2.3.3 Разложения функций по переменным
- 2.3.4 Приведение логических функций
- 2.3.5 Импликанты и имплициенты булевых функций
- 2.3.6 Методы минимизации логических функций
- 2.4 Алгебра жегалкина
- 2.4.1 Преобразование функций в алгебре Жегалкина
- 2.4.2 Переход от булевой алгебры к алгебре Жегалкина
- 3 Формальные теории
- 3.1 Основные принципы построения формальных теорий исчисления
- 3.2 Определение исчисления высказываний
- 3.2.1 Метатеоремы исчисления высказываний
- 3.2.2 Схемы исчисления высказываний
- 3.3 Исчисление предикатов
- 3.3.1 Определение формальной теории pl
- 3.3.2 Принцип резолюции в исчислении предикатов
- 3.3.3 Схемы доказательств в исчислении предикатов
- 4 Теория графов
- 4.1 История теории графов
- 4.2 Основные определения
- 4.3 Способы представления графов
- 4.3.1 Матрицей смежности
- 4.3.2 Матрицей инцидентности
- 4.4 Пути в графах
- 4.4.1 Задача о кратчайшем пути
- 4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе
- 4.5 Транспортные сети
- 4.5.1 Потоки в транспортных сетях
- 4.5.2 Задача нахождения наибольшего потока в транспортной сети
- 4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети
- 4.5.4 Транспортная задача
- 4.6 Обходы в графах
- 4.6.1 Эйлеровы графы
- 4.6.2 Алгоритм Флёри нахождения эйлерова цикла
- 4. Если получился цикл, но не ейлеров, то отбрасываем данную последнюю вершину и повторяем пункт 2.
- 4.6.3 Гамильтоновы циклы
- 4.6.4 Метод ветвей и границ.
- 4.6.5 Метод ветвей и границ в задаче о коммивояжёре
- 4.7 Деревья
- 4.7.1 Построение экономического дерева
- 4.7.2 Алгоритм Краскала
- 5 Элементы теории чисел
- 5.1 Модулярная арифметика
- 5.1.1 Алгоритм Евклида для нахождения наибольшего общего делителя
- 5.1.2 Вычисление обратных величин
- 5.1.3 Основные способы нахождения обратных величин
- 5.1.4 Китайская теорема об остатках
- 5.2 Кодирование
- 5.2.1 Оптимальное кодирование
- 5.3 Обнаружение и исправление ошибок
- 5.3.1 Общие понятия
- 5.3.2 Линейные групповые коды
- 5.3.2 Код Хэмминга
- 5.3.3 Циклические коды
- 5.3.4 Построение и декодирование конкретных циклических кодов
- 5.4 Сжатие информации
- 5.4.1 Исключение повторения строк в последующих строках
- 5.4.2 Алгоритм lzw
- 6 Теория алгоритмов
- 6.1. Основные понятия
- 6.1.1 Основные требования к алгоритмам
- 6.1.2 Блок–схемы алгоритмов
- 6.1.3 Представление данных
- 6.1.4 Виды алгоритмов
- 6.1.5 Правильность программ
- 6.1.6 Эффективность алгоритмов
- 6.1.7 Сходимость, сложность, надежность
- 6.2 Универсальные алгоритмы
- 6.2.1 Основные понятия
- 6.2.2 Машины Тьюринга
- 6.2.3 Рекурсивные функции
- 6.2.5 Тезис Черча-Тьюринга
- 6.2.6 Проблема самоприменимости
- 6.3 Языки и грамматики
- 6.3.1 Общие понятия
- 6.3.2 Формальные грамматики
- 6.3.3 Иерархия языков
- 6.4 Параллельные вычисления
- Рекомендованная литература