ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 17-18. Введение в теорию кодирования

Лекция 17-18. ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ

План лекции:

1. Предисловие.

2. Самокорректирующиеся коды.

3. Основные характеристики кода. Алгоритмы декодирования.

4. Линейные коды.

Предисловие

Вопросы кодирования играют существенную роль в математике. Кодирование позволяет изучение одних объектов сводить к изучению других. Хорошо известно, какую роль сыграло изображение чисел в десятичной системе счисления. Весьма важным в развитии математики было появление метода координат, который позволил кодировать геометрические объекты при помощи аналитических выражений. Однако, здесь средства кодирования являлись вспомогательным аппаратом и не были средством изучения. Совсем другое значение получили коды в связи с изучением управляющих систем. Появилась необходимость систематического исследования в области теории кодирования. Основной круг задач может быть рассмотрен на примере процесса передачи информации по каналу связи.

Самокорректирующиеся коды

Процесс передачи информации по каналу связи можно представить следующим образом. На вход канала поступает длинная последовательность нулей и единиц, разбитая на блоки (например, на байты). На другом конце канала эта последовательность принимается с возможными искажениями: переданная единица может быть принята как ноль и наоборот.

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

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

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

1°. Передаваемая информация – длинная последовательность нулей и единиц – разбивается на блоки по символов.

2°. Каждый блок кодируется двоичным словом из символов, где .

3°. Коды передаются по каналу связи и принимаются на другом его конце с возможными искажениями.

4°. Искаженные коды подвергаются процедуре декодирования, в результате которой восстанавливается первоначальный блок из символов.

Первым примером такой схемы передачи информации был 7-разрядный код Хемминга, исправляющий единичные ошибки.

Передаваемая информация разбивается на блоки по 4 символа (полубайты), блоки кодируются словами из 7 символов: .

Разряды кодового слова определяются так. Полубайт записывается в разряды 3, 5, 6, 7 (информационные): .

Остальные разряды кодового слова (контрольные) определяют так, чтобы выполнялись соотношения:

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

Если ошибок не было, все три суммы равны нулю. Если был искажен один разряд, то – его номер.

Основные характеристики кода. Алгоритмы декодирования

Кодом длины называется любое подмножество двоичных слов длины :

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

Чтобы описать действие помех при передаче и процедуру декодирования, на множестве двоичных слов вводится метрика. Расстоянием между двоичными словами называется количество разрядов, в которых эти слова различаются:

, , .

Определенное таким образом рас стояние удовлетворяет аксиомам метрики:

1°. , .

2°. .

3°. .

Таким образом, множество двоичных слов становится метрическим пространством и в нем возможны обычные для метрических пространств построения: шар, сфера, ближайшие к данной точки и т. д.

Если передавалось слово , а принято слово , то равно количеству разрядов, искаженных при передаче (число ошибок).

Будем предполагать, что вероятность искажения символа при передаче невелика (в противном случае таким каналом связи нельзя пользоваться). Основываясь на некоторой вероятностной модели можно строго доказать, что наилучшим алгоритмом декодирования при сделанных предположениях будет следующий:

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

Такой метод принятия решения в условиях неопределенности называют методом максимального правдоподобия. В рассматриваемой ситуации это название можно объяснить так: после того как принято слово , для каждого слова вычисляются вероятности того, что слово получено из слова , из этих вероятностей выбирается наибольшая (максимум правдоподобия).

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

Рассмотрим главные параметры, характеризующие код.

1°. Мощность кода , то есть количество кодовых точек. Если код имеет мощность , то блоки информации, которые он кодирует должны иметь длину , такую, что , то есть . Примем физическую скорость передачи канала за единицу: передача одного двоичного символа занимает одну единицу времени. Применив кодирование, получим, что двоичных символов передаются за единиц времени, то есть скорость передачи информации равна

бит/ед. вр.

Следовательно, чем больше мощность кода, тем большую скорость передачи информации он обеспечивает.

2°. Кодовое расстояние – минимальное расстояние между кодовыми словами:

Роль этого параметра состоит в следующем. Будем говорить, что код исправляет ошибок, если передаваемые слова, в которых искажено не более разрядов принимаются правильно.

Теорема 1. Если , то код исправляет ошибок.

Доказательство. Пусть – переданное слово, – принятое слово, в котором не более ошибочных разрядов, то есть .

Очевидно, что и будет ближайшим к кодовым словом, так как для любого другого кодового слова имеем

Теорема доказана.

Основной задачей теории кодирования является следующая:

Для заданных построить код максимальной мощности такой, что .

Линейные коды

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

Код называется линейным, если он является подпространством этого пространства.

Рассмотрим способы задания линейного кода. Первый способ состоит в задании базиса из векторов подпространства размерности . Тогда

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

Если эти уравнения независимы, то размерность пространства решений равна . Бинарная матрица системы имеет размер . Тогда

. (1)

Матрица называется проверочной матрицей кода .

Пример. Описанный выше 7-разрядный код Хемминга представляет собой линейный код с проверочной матрицей

Так как

то из условия , получаем соотношения, которым удовлетворяют разряды кодовых слов в коде Хэмминга

Эти соотношения представляют собой проверки на четность. Например, первое из них выполняется, когда количество единиц в разрядах 4, 5, 6 и 7.

Будем далее считать, что линейный код задается проверочной матрицей , то есть определяется по формуле (1). Рассмотрим теперь корректирующие возможности линейного кода, то есть его способность исправлять ошибки. Как было установлено выше, это зависит от параметра . Для линейного кода он вычисляется проще, чем в общем случае. Весом двоичного слова называется число разрядов слова, равных единице:

Теорема 2. Если – линейный код, то

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

Это утверждение очевидным образом следует из следующих двух фактов

Теорема 3. Линейный код исправляет ошибок, если в его проверочной матрице любые столбцов линейно независимы.

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

. (2)

Количество коэффициентов, равных единице, в выражении (2) равно , нулевые коэффициенты можно отбросить. Тогда равенство (2) представляет собой соотношение линейной зависимости между столбцами проверочной матрицы. При выполнении условия теоремы получаем, что , следовательно, код исправляет ошибок.

ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ