Таким образом средняя длительность кодового слова 2.92 Общее количество символов 26 Среднее число 0 – Ср=16/26=0.616 Среднее число 1 – Ср=10/26=0.384
Задача 12
Если кодовые комбинации составлены так, что отличаются друг от друга на кодовое расстояние d > 3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности не только обнаруживать, но и исправлять ошибки. Большую группу кодов, исправляющих ошибки, составляют систематические коды. Рассмотрим общие принципы построения этих кодов. Систематическими кодами называются блочные (п, к) коды, у которых к (обычно первые) разрядов представляют собой двоичный неизбыточный код, а последующие г-контрольные разряды сформированные путем линейных комбинаций над информационными. Основное свойство систематических кодов: сумма по модулю 2 двух и более разрешенных кодовых комбинаций также дает разрешенную кодовую комбинацию. Правило формирования кода обычно выбирают так, чтобы при декодировании имелась возможность выполнить ряд проверок на четность для некоторых определенным образом выбранных подмножеств информационных и контрольных символов каждой кодовой комбинации. Анализируя результаты проверок, можно обнаружить или исправить ошибку ожидаемого вида. Информацию о способе построения такого кода содержит проверочная матрица, которая составляется на базе образующей матрицы. Образующая матрица М состоит из единичной матрицы размерностью k • k и приписанной к ней справа матрицы дополнений размерностью k • r:
Разрядность матрицы дополнений выбирается из выражений
Причем вес w (число ненулевых элементов) каждой строки матрицы дополнений должен быть не меньше чем dmin -1. Проверочная матрица N строится из образующей матрицы следующим образом. Строками проверочной матрицы являются столбцы матрицы дополнений образующей матрицы. К полученной матрице дописывается справа единичная матрица размерностью (r x r). Таким образом, проверочная матрица размерностью (г х k) имеет вид
Единицы, стоящие в каждой строке, однозначно определяют, какие символы должны участвовать в определении значения контрольного разряда. Причем единицы в единичной матрице определяют номера контрольных разрядов. Код Хемминга. Данный код относится к числу систематических кодов. Но существу, это целая группа кодов, при d = 3 исправляющая все одиночные или обнаруживающая двойные ошибки, а при dmin = 4 исправляющая одиночные и обнаруживающая двойные ошибки. В качестве исходных берут двоичный код на все сочетания с числом информационных символов k, к которому добавляют контрольные символы г. Таким образом, общая длина закодированной комбинации n = k + r. Рассмотрим последовательность кодирования и декодирования кода Хемминга. Кодирование. При передаче по каналу с шумами может быть или искажен любой из n символов кода, или слово передано без искажений. Таким образом, может быть n + 1 вариантов принятых сообщений. Используя контрольные символы, необходимо различить все n + 1 вариантов. С помощью контрольных символов можно описать 2n событий. Значит, должно быть выполнено условие
Число контрольных символов г в коде Хэммиига в зависимости от числа информационных символов
Чаще всего заданными является число информационных символов, тогда число контрольных символов можно определить из выражения приведенного выше. В принципе, место расположения контрольных символов не имеет значения: их можно приписывать и перед информационными символами, и после них, и чередуя информационные символы с контрольными. Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т.е. на позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для девятиэлементной закодированной комбинации можно записать
где k5 - старший (пятый) разряд исходной кодовой комбинации двоичного кода, подлежащий кодированию; k1 — младший (первый) разряд. Рассмотрим пример. Закодируем в коде Хемминга с d = 4 кодовую комбинацию G(X) = 10011 т.е. k= 5. Согласно таблице, число контрольных символов г = 4, размещаются они на позициях 1, 2, 4 и 8, и информационные — на позициях 3, 5, 6, 7, 9. Учитывая, что G{X) необходимо закодировать в коде Хемминга с d = 4, добавляют пятый контрольный разряд общей проверки на четность. Тогда последовательность в общем виде можно записать так:
Для определения контрольных символов r1-r4 подставим составим уравнения
Контрольный символ г5 определим из выражения:
Таким образом, в линию связи будет послан код
Декодирование. Произведем Si проверки в результате получим:
Таким образом, получим синдром S4 S3 S2 S1 =0100 и SΣ =1, что указывает на то, что искажен четвертый разряд кодовой комбинации F'(X). После исправления получим F(X) - 1011001110, а следовательно, информационная последовательность будет иметь вид G(X) = 10011, что соответствует исходной кодовой комбинации примера. Варианты структурных схем кодера и декодера приведены ниже (Кл – ключ, + - сумматор по модулю 2).
