Лабораторные 101-104 (Методичка по лабам), страница 3

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

Из общего числа возможных ошибок, групповой код может исправить всего разновидностей ошибок [1].

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

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

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

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

Если, например, мы желаем исправлять все одиночные ошибки, то исправлению подлежит n ошибок. Вектора ошибок имеют в этом случае следующий вид :

Различных ненулевых опознавателей должно быть не менее n.

Необходимое число проверочных разрядов, следовательно, должно определяться из соотношения :

.

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

.

В общем случае это неравенство записывается следующим образом: , где Q число ошибок, кеоторые необходимо исправить. Например, для исправления пачек в 3 и менее символов

, где

n – одиночные ошибки,

(n-1) – пачки в 2 соседних символа (… 0110…)

2(n-2) – пачки в 3 соседних символа (…01110…) и в два символа через один (…01010…).

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

2.2. Составление таблицы опознавателей

Начнем для простоты с установления опознавателей для случая исправления одиночных ошибок. Допустим, необходимо закодировать 15 команд (букв).

Таблица 2.1

Тогда к=4, n=7. Три избыточных разряда позволяют использовать в качестве опознавателей трехразрядные двоичные последовательности. В принципе они могут быть сопоставлены подлежащим исправлению ошибкам в любом порядке. Однако, более целесообразно опознаватели сопоставлять с номерами разрядов, в которых произошли ошибки (табл. 2.1).

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

Возьмем теперь более сложный случай исправления всех одиночных и двойных независимых ошибок, то есть две ошибки в любых разрядах. В качестве опознавателей одиночных ошибок в первом и втором разрядах можно принять, как и ранее две комбинации 0...001 и 0...010 (табл. 2.2).

Подлежащий исправлению вектор ошибки 0...011 может рассматриваться как результат суммарного воздействия двух векторов ошибок 0...010 и 0...001 и, следовательно, ему должен быть сопоставлен опознаватель, представляющий собой сумму по модулю два опознавателей этих ошибок, т.е. 0...011.

Вектору ошибки 0...0100 сопоставляем опознаватель 0...0100 и т.д. Выбирая в качестве опознавателя единичной ошибки в i-м разряде комбинацию с числом разрядов меньшим i, необходимо убедиться в том, что для всех остальных подлежащих исправлению векторов ошибок, имеющих единицы в i-м и более младших разрядах, получаются опознаватели, отличные от уже использованных. В результате имеем:

Таблица 2.2

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

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

Для построения кодов, исправляющих двойные независимые ошибки, пачки ошибок в двух и трех разрядах опознаватели одиночных ошибок в каждом из разрядов сведены в табл. 2.3, 2.4, 2.5, которые составлены с помощью ЭВМ.

Таблица 2.5 Опознаватели одиночных ошибок для кода, исправляющего пачки ошибок в трех и менее разрядах

2.3. Определение проверочных равенств

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

Возьмем в качестве примера табл. 2.1 опознавателей для кодов, предназначенных исправлять одиночные ошибки. В принципе можно построить код, усекая эту таблицу на любом уровне. Однако оптимальными будут коды, которые среди кодов, имеющих одно и то же число проверочных символов, допускают наибольшее число информационных символов, например код (7,4) n=7, к=4.

То есть при трех проверочных разрядах опознавателя мы можем передавать четыре информационных символ. Найдем места и значения проверочных разрядов.

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 1-го, 3-го, 5-го и 7-го разрядов :

.

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

.

Аналогично находим и третье равенство :

.