25023-1 (630370), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

10100 - -я принятая комбинация;

00110 - 3-я принятая комбинация;

10110 - накопленная комбинация.

Как видим, несмотря на то, что во всех трех принятых комбинациях были ошибки, накопленная не содержит ошибок⁸.

Принятое сообщение может также состоять из кода и его инверсии. Код и инверсия посылаются в канал связи как одно целое. Ошибка на приемном конце выделяется при сопоставлении кода и его инверсии.

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

(55)

где - число единиц в кодовом слове. Если бы не существовало условия постоянного веса, то число комбинаций кода могло бы быть гораздо большим, а именно . Примером кода с постоянным весом может служить стандартный телеграфный код № 3 (см. приложение 4). Комбинации этого кода построены таким образом, что на 7 тактов, в течение которых должна быть принята одна кодовая комбинация, всегда приходятся три токовые и четыре безтоковые посылки. Увеличение или уменьшение количества токовых посылок говорит о наличии ошибки.

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

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

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

В общем случае для обнаружения r ошибок минимальное кодовое расстояние

(56)

Минимальное кодовое расстояние, необходимое для одновременного обнаружения и исправления ошибок,

(57)

где s - число исправляемых ошибок.

Для кодов, только исправляющих ошибки,

(58)

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

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

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

Для обнаружения и исправления одиночной ошибки соотношение между числом информационных разрядов и числом корректирующих разрядов должно удовлетворять следующим условиям:

(59)

60)

при этом подразумевается, что общая длина кодовой комбинации

. (61)

Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием удобно пользоваться выражениями:

(62)

если известна длина полной кодовой комбинации п, и

(63)

если при расчетах удобнее исходить из заданного числа информационных символов ¹⁰.

Для кодов, обнаруживающих все трехкратные ошибки

(64)

или

(65)

Для кодов длиной в п символов, исправляющих одну или две ошибки

(66)

Для практических расчетов можно пользоваться выражением

(67)

Для кодов, исправляющих 3 ошибки

(68)

Для кодов, исправляющих s ошибок

(69)

Выражение слева известно как нижняя граница Хэмминга [16], а выражение справа – как верхняя граница Варшамова – Гильберта [3]¹¹

Для приближенных расчетов можно пользоваться выражением

(70)

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

Линейные групповые коды

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

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

Правила сложения по модулю 2 определяются следующими равенствами:

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

Свойство линейных кодов: сумма (разность) кодовых векторов линейного кода дает вектор, принадлежащий данному коду.

Линейные коды образуют алгебраическую группу по отношению к операции сложения по модулю 2. В этом смысле они являются групповыми кодами.

Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами группового кода равно минимальному весу ненулевых кодовых векторов.

Вес кодового вектора (кодовой комбинации) равен числу его ненулевых компонентов.

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

.

Групповые коды удобно задавать матрицами, размерность которых определяется параметрами кода и . Число строк матрицы равно , число столбцов равно + = :

(71)

Коды, порождаемые этими матрицами, известны как -коды, где , а соответствующие им матрицы называют порождающими, производящими, образующими.

Порождающая матрица С может быть представлена двумя матрицами И и П (информационной и проверочной). Число столбцов матрицы П равно , число столбцов матрицы И равно :

(72)

Теорией и практикой установлено, что в качестве матрицы И удобно брать единичную матрицу в канонической форме:

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

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

При соблюдении перечисленных условий любую порождающую матрицу группового кода можно привести к следующему виду:

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

Для кодов с =2 производящая матрица С имеет вид

Во всех комбинациях кода, построенного при помощи такой матрицы, четное число единиц.

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

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

Для кодов с соотношения п и . следующие: (3; 1), (7;4), (15; 11), (31; 26), (63; 57) и т. д.

Плотно упакованные коды, оптимальные с точки зрения минимума избыточных символов, обнаруживающие максимально возможное количество вариантов ошибок кратностью r + 1; r + 2 и т. д. и имеющие и , были исследованы Д. Слепяном в работе [10]. Для получения этих кодов матрица П должна иметь комбинации с максимальным весом. Для этого при построении кодов с последовательно используются векторы длиной п , весом . Тем же Слепяном в работе [11] были исследованы неплотно упакованные коды с малой плотностью проверок на четность. Эти коды экономны с точки зрения простоты аппаратуры и содержат минимальное число единиц в корректирующих разрядах порождающей матрицы. При построении кодов с максимально простыми шифраторами и дешифраторами последовательно выбираются векторы весом = 2, 3, ..., . Если число комбинаций, представляющих собой корректирующие разряды кода и удовлетворяющих условию , больше , то в первом случае не используют наборы с наименьшим весом, а во втором - с наибольшим.

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

Алгоритм образования проверочных символов по известной информационной части кода может быть записан следующим образом:

Характеристики

Список файлов ответов (шпаргалок)