Лекция по "Информатике"

     Лекция  №9

     Раздел №1. Множества и отображения 

     Тема: Кодирование и декодирование в передаче информации 

     В теории передачи информации существенным является вопрос кодирования и декодирования, при наличии «шума» в канале связи.

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

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

     Блочный (т, п) код определяется двумя функциями К: и Д: ; К – функция кодирования, Д – функция декодирования. Если Т – функция ошибок, то К, Д, Т выбираются так, что бы композиция с большей вероятностью была близка к тождественной. Двоичный (т, п) код имеет 2^т кодовых слов.

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

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

     На  множестве двоичных слов длины  т расстоянием Хемминга d (a, b) между словами a и b называется число несовпадающих позиций этих слов. Например, расстояние между словами a = 10101 и b = 00111 равно 2. 

     Аксиомы расстояний:

       тогда и только тогда,  когда  .

     Более экономичным способом описания схемы  кодирования является матричный.

     Пусть G = - матрица порядка т × п, элементами которой являются 0 и 1, соответствующая (т, п) коду, называемая порождающей матрицей кода;

      - вектор, соответствующий переданному сообщению;

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

     Например, порождающей матрицей (1, s) кода с повторениями будет матрица   G = (1…1), так как 1…1 = 1G, 0…0 = 0G.

     Одним из распространенных видов кодов  являются коды Хемминга, исправляющие однократную ошибку; (т, п) код Хемминга – код, где т = 2^s – 1 – s,   п = 2^s – 1, для любого s ≥ 2. Запишем матричное уравнение: Здесь матрицы М порядка s × 2^s – 1 для кода Хемминга (при s = 2, 3, 4) имеют вид: 

     Если  принято слово  , где е – ошибка, то , так как Если = 0, то считают, что ошибки нет. Если е имеет 1 в i-й позиции, то в слове с нужно изменить символ b в i-й позиции, и полученное слово будет результатом декодирования. Если единицы есть больше, чем в одной позиции, то результат декодирования неверен.

     Например, найдем порождающую матрицу для (4, 7) кода Хемминга. Фундаментальная  система решений линейных уравнений, полученных из уравнения  , имеет вид

       Тогда порождающей является матрицей, составленная из этих векторов: