Основы теории кодирования

1.

3
СЕВАСТОПОЛЬСКИЙ
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
ПРЕДЛОЖЕНИЯ
КОМПЛЕКС
АНПА“САРМА”
Лекция № 3
«Основы теории кодирования»
Ведущий преподаватель: канд. техн. наук, доцент кафедры ИУТС Альчаков Василий Викторович

2.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
2
Основные определения
Кодирование сигнала – процесс преобразования сообщения в сигнал
Аналоговый сигнал
(непрерывное сообщение)
Цифровой сигнал
(дискретное сообщение)
Кодирование относят обычно к
дискретным сигналам
Кодирование – представление дискретных сообщений сигналами в
виде определенных сочетаний символов
Совокупность правил, в соответствии с которыми производятся эти
операции, называется кодом

3.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
3
Виды кодирования
В зависимости от цели кодирования, различают следующие виды кодирования
(1)
Кодирование по образцу
(2)
Криптографическое
кодирование (шифрование)
(3)
Эффективное (оптимальное)
кодирование
(4)
Помехоустойчивое
кодирование

4.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
4
Цели кодирования
I - Сообщения представляют в системе символов, обеспечивающей простоту
аппаратной реализации информационных устройств.
Основание кода – число различных элементарных
сигналов
Значность кода – число элементов образующих
кодовую комбинацию
Равномерный код – значность комбинаций кода
одинакова
Неравномерный код – значность комбинаций кода
различна
II - Кодирование используется для наилучшего согласования свойств источника
сообщений со свойствами канала связи.
Оптимальное статистическое кодирование – коды, которые обеспечивают минимизацию
среднего количества кодовых комбинаций на один элемент сообщения

5.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
5
Цели кодирования
III - Кодирование позволяет уменьшить влияние помех на процесс приемапередачи (помехоустойчивое кодирование).
IV - Кодирование обеспечивает защиту информации от несанкционированного
доступа.

6.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
6
Двоичное кодирование
Исходный аналоговый сигнал
Дискретный сигнал
Цифровой (двоичный) сигнал
Основной принцип – используются два
элементарных сигнала, которые легко
сформировать технически

7.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
7
Помехоустойчивое кодирование
Одна из важнейших зада при проектировании систем связи –
обеспечение высокой достоверности передачи данных.
↓↓↓↓↓
Оптимальное кодирование – получение наиболее коротких кодовых
групп + исключение возможности появления ошибок, связанных с
неоднозначностью кодирования.
Помехоустойчивость системы связи – способность системы
передавать (и получать) сообщения в условиях помех.
Помехоустойчивое кодирование – применяется для обнаружения и
исправления ошибок.

8.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
8
Помехоустойчивое кодирование – основные
определения
Количество разрядов n в кодовой комбинации называется значностью
кода.
Количество единиц в коде называется весом кодовой комбинации.
Степень отличия кодовых комбинаций характеризуется кодовым
расстоянием d – выражается числом позиций, по которым комбинации
различаются, и определяется как вес суммы по модулю 2 кодовых
комбинаций.
ПРИМЕР:
Приняты комбинации 0001 и 1111. Определить значность кодовых
комбинаций их вес и кодовое расстояние между комбинациями.
0001: значность = 4, вес = 1.
1111: значность = 4, вес = 4.
Кодовое расстояние:
0001
1111
1 1 1 0 – вес суммы по мод 2 → d = 3

9.

ОСНОВЫ
ТЕОРИИ
КОДИРОВАНИЯ
9
Помехоустойчивое кодирование – основные
определения
С ошибкой связано понятие ее кратности q – число искаженных
разрядов.
-- Исходная комбинация
-- Искаженная комбинация (q = 2)
-- Вектор ошибки
Вес вектора ошибки характеризует ее кратность

10.

10 ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Помехоустойчивое кодирование –
систематические коды
Помехоустойчивые коды характеризуются корректирующей способностью,
которая определяется вероятностью обнаружения или исправления ошибки.
Помехоустойчивость кодов обеспечивается за счет введения избыточности.
m
k n
Код, содержащий информационные и контрольные разряды, называется
систематическим.
Контрольные разряды содержат код, характеризующий состояние
информационных разрядов. При этом абсолютная избыточность выражается
количеством контрольных разрядов k, а относительная избыточность –
отношением k / n.

11.

11 ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Простейшие коды – Кодирование с проверкой
на четность (нечетность)
Выполняется суммирование по модулю 2 разрядов, входящих в контролируемый
код. Вместе с информационной частью кода передается один контрольный разряд.
Его значений «0» или «1» выбирается с условием, чтобы сумма цифр в
предаваемом коде была равна 0 по модулю 2 (для случая четности) или 1 (для
случая нечетности). Допускается что может возникнуть только одна ошибка.
Увеличение избыточности приводит к тому, что появляется возможность не
только обнаружить ошибку, но и исправить ее.

12.

12 ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Простейшие коды – Код с удвоением
элементов
Метод кодирования с удвоением
дополнительного символа для
передаваемого кода.
элементов характеризуется наличием
каждого информационного символа
-- Исходная комбинация
-- Закодированная комбинация
-- Комбинация с ошибкой
1 → 10
0 → 01
Показателем искажения являются сочетания типа 00 или 11 в парных элементах.
Код не способен исправлять ошибки, приводящие к двукратным
противоположным
изменениям
разрядов
в
парных
элементах.
Помехоустойчивость кода выше, чем кода с проверкой на четность, но
существенно возрастает избыточность.

13.

13 ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Простейшие коды – Инверсное кодирование
В основе метода лежит повторение кодовой комбинации.
Если исходная комбинация содержит четное число единиц, то повторная
комбинации в точности повторяет исходную. Иначе повторение происходи в
инверсном виде.
01010 → 0101001010
11010 → 1101000101
Проверка производится суммированием единиц основной комбинации. Если их
число четно, то элементы второй части принимаются в том же виде, после чего
обе части комбинации сравниваются поэлементно – первый элемент первой
части с первым элементом второй части. При несовпадении хотя бы одного
элемента принятая комбинация считается неверной.
Инверсный код позволяет обнаружить практически все ошибки приема-передачи.
Не обнаруживается лишь одновременное искажение парных элементов в обеих
частях кодовой комбинации.