Файл: Зелигер Н.Б. Основы передачи данных учеб. пособие.pdf

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

ВЫ БОР ЭЛЕМЕНТОВ П РО ВЕРО ЧН Ы Х ГРУПП КО М БИ Н А Ц И И

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

11, ..., в третьем разряде — числа 4, 5, 6, 7, 12, 13, 14, 15, ..., в четвертом разряде — числа 8, 9, 10, 11, 12, 13, 14, 15 .... и т. д.

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

ВЫ БОР ПОЗИЦИИ П РО ВЕРО ЧН Ы Х ЭЛЕМЕНТОВ

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

63

верочных те элементы, которые участвуют только в одной из про­ верок. Номера этих элементов 1, 2, 4, 8 , 16, ... .

В таблице 2.7 указаны номера элементов проверочных групп для каждой из четырех проверок. Позиции проверочных элементов выделены жирным шрифтом.

Пример. Пусть т = 5. Тогда согласно (2.27) п = 9 и k=4. Процедуры переда­ чи и приема при построении кода с исправлением одиночной ошибки рассмотрим применительно к пяіиэлементной кодовой комбинации <10110. Так как 1, 2, 4 и 8 -я позиции заняты проверочными элементами, то информационные элементы комбинации должны быть расположены на позициях 3, 5, 6 , 7 и 9. Заполнение проверочных позиций 1, 2, 4 и 8 единицами и нулями производится с учетом

требования четности в проверочных группах. Для того чтобы сумма единиц в четырех проверочных группах кодовой комбинации была четной, следует на первой позиции поместить 0 , на второй— 1, на четвертой — 0 и на восьмой — 0 .

Тогда девятиэлементная кодовая комбинация запишется в виде 011001100. Предположим теперь, что элемент, расположенный на пятой позиции, за­

верок— 101. Четвертая проверка 8 и 9-й позиций дает четность, а результат

четырех проверок — 0101. Проверочной двоичной комбинации 0101 отвечает чи­ сло 5, и поэтому должен быть исправлен пятый элемент. Исправлением ошиб­ ки восстанавливается действительно переданная комбинация.

М А ТР И Ч Н А Я З А П И С Ь КО ДО ВЫ Х КО М Б И Н А Ц И И И ЗБ Ы Т О Ч Н Ы Х КОДОВ

Запись кодовых комбинаций избыточных кодов, как и первич­ ных, можно произвести в матричной форме.

Определяющая матрица избыточного кода Ап,т составляется из единичной матрицы Ат (где т — число информационных элементов комбинации) и дополнительной матрицы проверочных элементов Ak, т, состоящей из k = n—т столбцов (где k — число проверочных элементов комбинации) и т строк.

Определяющая матрица избыточного кода в общем виде мо-.

64

На основании (2.28) определяющая матрица девятиэлементного кода Хемминга может быть представлена в виде

Строки дополнительной матрицы проверочных элементов запол­ няются в соответствии с табл. 2.7. Из таблицы видно, что третий информационный элемент проверяется совместно с первым и вто­ рым проверочными элементами, и поэтому на первой и второй по­ зициях первой строки матрицы проверочных элементов поставлены единицы, а на четвертой и восьмой позициях — нули. Аналогично заполняются остальные строки матрицы проверочных элементов.

Сложив по модулю два в различных сочетаниях строки матри­ цы Ад,5, получим все (2 5—1 ) разрешенных комбинаций избыточного (9,5) кода. Для получения, например, комбинации 011001100 до­ статочно сложить по модулю два первую, третью и четвертую стро­ ки определяющей матрицы АВі5 и элементы полученной суммы рас­ положить в порядке возрастания их номеров.

Рассматривая матрицу A9i5, легко установить, что наименьшее кодовое расстояние между двумя любыми ее строками d ^ . 3, и вес каждой строки со^З, чем подтверждается возможность кода испра­ влять одиночные ошибки.

ВЕРОЯТНОСТЬ ОШ ИБОЧНОГО П Р И ЕМ А КОДОВОЙ КО М БИ Н А Ц И И

В коде Хемминга вероятность Рк неправильного приема кодо­ вой комбинации равна вероятности того, что число ошибочных эле­ ментов в комбинации больше одного. Поэтому, в соответствии с (1.41), вероятность правильного приема кодовой комбинации

вии с (.1.40) получим Рк= 'li—(.1— 10—5) ° = 9 - 10-5, т. е. на каждые переданные.іІО*

кодовых комбинаций приходится 9 ошибочных. Таким образом, для ро—Ы0~* вероятность .неправильного приема кодовой комбинации при неизбыточном ходе повышается примерно на ива порядка.

КО Д И Р У Ю Щ Е Е И Д Е КО Д И Р У Ю Щ Е Е УСТРОЙСТВА

Кодирующее и декодирующее устройства для кода Хемминга могут быть реализованы более экономично, если в качестве прове­ рочных выбрать не 1, 2, 4 и 8 -ю посылки девятиэлементной ком­ бинации, а 6 , 7, 8 и 9-ю посылки. Такая замена допустима, по­ скольку выбор позиций проверочных посылок не обусловлен прин­ ципиальными соображениями и может быть осуществлен произ­ вольно.

На рис. 2.11 приведена схема кодирующего устройства для ко­ да Хемминга. Устройство состоит из трех сумматоров по модулю

Рис. 2.11. Схема кодирующего устройства для кода Хемминга

Два и регистра сдвига (PC), выполняющего функции передаю­ щего распределителя. Кодовые посылки от источника информации поступают одновременно на первые пять ячеек передающего реги­ стра и на сумматоры по модулю два.

Сумматоры предназначены для формирования проверочных по­ сылок с учетом четности суммы единиц в проверочных группах.

позиций и в третьем сумматоре.— единицы 2, 3 и 4-й позиций.

С выходов сумматоров сформированные проверочные посылки записываются в 6 , 7 и 8 -ю ячейки регистра; единица 5-й пози­ ции непосредственно записывается в 9-ю ячейку регистра. Затем

связи.

На рис. 2.12 приведена схема декодирующего устройства для кода Хемминга.

■.Устройство состоит: из регистра сдвига, выполняющего функ­ ции приемного распределителя (ПР); считывающего устройства (СУ), состоящего из девяти логических ячеек И; устройства для обнаружения ошибок (УОО), в состав которого входят четыре сум­ матора по модулю два fSj, Sz, S3 и St) и индикатор ошибки (ИО); устройства для исправления ошибок (УИО), содержащего дешиф-

66

ратор (пять ячеек И и девять ячеек НЕ) и регистр сдвига (PC), между ячейками которого включены сумматоры по модулю два.

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

ти

Рис. 2:\2. Схема декодирующего устройства для кода Хемминга

тактовый импульс, посылки комбинации одновременно считывают­ ся и отдельными проверочными группами направляются соответ­ ственно в четыре сумматора по модулю два. Каждый из сумма­ торов предназначен для проверки на четность суммы единиц од­ ной из четырех проверочных групп кодовой комбинации. В первом сумматоре производится сложение по модулю два единиц 1, 2, 4, 5 и 6 -й позиций, во втором сумматоре — единиц 1, 3, 4 и 7-й пози­ ций, в третьем сумматоре — единиц 2, 3, 4 и 8 -й позиций и в чет­ вертом сумматоре — единиц 5 и 9-й позиций.

Импульсы с выходов сумматоров записываются на индикаторе ошибок (ИО) в виде единиц и нулей, образующих шесть возмож­

ных четырехразрядных чисел. Одно из этих чисел, состоящее из четырех нулей, указывает на отсутствие ошибок в информационных посылках кодовой комбинации. Каждое из остальных пяти чисел (ООН, 0 1 0 1 , ОНО, 0 1 1 1 , 1 0 0 1 ) указывает на наличие ошибки в од­ ной из пяти информационных посылок данной комбинации (со­ ответственно в 1, 2, 3, 4 или 5-й посылке). Ошибки проверочных посылок рассматриваемой схемой не обнаруживаются.

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

Пример. Пусть третья информационная посылка кодовой комбинации при­ нята с ошибкой. При считывании информации с приемного регистра ошибочная посылка попадет на входы сумматоров и S3 и на выходах этих сумматоров

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

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

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

При отсутствии ошибки в кодовой комбинации на выходе соот­ ветственной ячейки И дешифратора сигнала не будет, и кодовая посылка поступит в приемник информации без изменений. При наличии ошибки на выходе ячейки И дешифратора появится сигнал, и в результате сложения по модулю два (1 0 1 = 0 , 0 0 1 = = 1 ) ошибочная посылка будет инвертирована; в приемник инфор­ мации поступит исправленная кодовая комбинация.

■•я Регистр сдвига устройства для исправления ошибки состоит из шеетиячеек. Одновременно со считыванием девятиэлементной ком­ бинации с регистра приема информационные посылки этой ком­ бинации переписываются на 2', 3', 4', 5' и 5-ю ячейки регистра устройства для исправления ошибок. После инвертирования оши­ бочной посылки пятиэлементная комбинация под действием так­ тового импульса продвигается на один шаг и записывается в ячей­ ках регистра 1', 2', 3', 4' и 5' уже в исправленном виде. Следую­ щим тактовым импульсом исправленная комбинация направляет­ ся в приемник информации.

68