§2.6. Технические приложения в теории графов.

1. Планарные графы.

- планарный, если в графе нет пересечений мимо узла ветвей.

Граф G считается k-планарным, если его ветви могут быть расположены на k-пересекающихся плоскостях, причем на каждой плоскости графы могут быть только планарными.

2. Сигнальные графы.

Граф где , в которой в каждой вершине приведем в соответствие некоторый сигнал а ветви передачи этого сигнала называется сигнальным графом .

Будем рассматривать только линейные сигнальные графы, в которых передача графа определяется линейной функцией сигнала.

Сложение ветвей графов.

Глава 3. Кодирование и декодирование информации.

§3.1. Представление информации.

Кодирование – представление информации в виде сигналов и их характеристик.

Декодирование – обратный процесс.

Сигнал может представлять информацию в виде своих характеристик :

• отрицательные и положительные посылки.

- посылки различной

амплитуды

- посылки различной

длительности

- посылки различной частоты

заполнения

- отсутствие и присутствие

сигнала

- посылки различной

скважности (длительность

отсутствия сигналя).

Из элементарных сигналов создаются кодовые комбинации. Различают: - основание кода (разряд)

• длина кода (число разрядов).

§3.2. Двоичные неизбыточные коды.

Основание этого кода равно 2 и длина должна обеспечивать передачу необходимого количества информации.

Рассмотрим преобразователь перемещения в двоичный неизбыточный код.

Рассмотрим возникновение ошибки при передаче от 3х до 4х

4 – 100

3 – 011 – 011 – 111

Ошибка при этом получается равна старшему разряду кода.

Чтобы минимизировать ошибку до младшего разряда строят код т.о.:

Этот код называется кодом Грея. Покажем что этот код минимизирует ошибку до младшего разряда.

010 - 110

₁₁₀

Коды Грея могут быть построены на основании карт Карно.

§3.3. Помехоустойчивые избыточные коды.

В неизбыточных двоичных кодах, в кодах Грея и в кодах, построенных на картах Карно всякая ошибка состоит в искажении какого-либо символа или разряда кода переводит одну разрешенную комбинацию кода в другую разрешенную комбинацию кода.

Такая ошибка в коде не обнаруживается и следовательно не может быть исправлена. Для обнаружения и исправления ошибок должны быть введены дополнительные разряды, которые служат для корректировки и контроля правильности передачи информации.

Коды, в которых к разрядам несуществующей информации добавляя дополнительные разряды для добавления или корректировки дополнительной информации называются корректирующими помехоустойчивыми кодами.

Для определения требуемого количества контрольных разрядов введем понятие «вес кодовой комбинации» или

Под кодовым расстоянием d между A и B вес третьей комбинации C получается из первых двух комбинаций путем сложения по модулю 2.

4 – 110

5 – 111

d(4,5) = d(001) = 1

Среди всех новых комбинаций кода можно перечислить попарные кодовые расстояния, среди которых минимальным будет минимальное кодовое расстояние кода.

Для безизбыточного кода

Минимальное кодовое расстояние кода связано с обнаруживающей и исправляющей способностью кода.

Представим код в виде двоичного куба

d(0,1) = W(011) = 2

Код, имеющий минимальное кодовое расстояние равное двум позволяет обнаруживать одиночные кодовые ошибки, не позволяет обнаруживать двоичные ошибки или исправлять одиночные.

Это означает, что любая ошибка в разрешенной комбинации переводит эту комбинацию в неразрешенную.

Для исправления одиночных ошибок необходим код с

d(0,1) = W(111) = 3

Воспользуемся 3-х разрядным двоичным кодом для кодирования двух комбинаций.