Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

дов, следовательно, этот метод основывается не на ин­ формационной, а на схемной избыточности.

Один из вариантов схемы контроля передач по сов­ падению показан на рис. 12-3. После передачи информа­ ции из регистра А в регистр Б (или из Б в Л) через вре­ мя, несколько большее времени установления переход-

Регистр

ных процессов в триггерах регистров, запускается конт­ рольный сигнал.

В случае несовпадения информации в одном или не­ скольких разрядах регистров открывается схема И2 и триггер сбоя Тсб устанавливается в состояние 1.

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

637

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

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

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

Код Хэмминга

Код Хэмминга представляет собой систематический код, позволяющий не только обнаруживать, но и исправ­ лять ошибки. В соответствии с этим он имеет минималь­ ное кодовое расстояние dMин=3.

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

Рассмотрим более подробно процесс кодирования

638

и т. д.

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

Eft E k _ • • • Е Е Е Х

j 3 2

считается корректирующим.

639

При отсутствии ошибок EhEh-\ ... Е2Е Х= 0, при нали­ чии ошибки не равными нулю будут те суммы Еи в об­ разовании которых участвовал ошибочный разряд, кор­ ректирующее число при этом будет равно порядковому номеру разряда.

Выбор места для контрольных разрядов в каждой из групп разрядов определяется таким образом, чтобы контрольные разряды участвовали только в одной опе­ рации подсчета четности. Это упрощает процесс кодиро­ вания. Рассмотрение выражений для Е ь Е2, Е3 и т. д. показывает, что такими позициями являются разряды с номерами, являющимися целыми степенями двойки: 1, 2, 4, 8, 16 и т. д.

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

в t-м разряде. Таким образом, должно соблюдаться со­ отношение:

Из этого неравенства следует, что четыре контроль­ ных разряда позволяют передавать в коде Хэмминга от 4 до 11 информационных разрядов, пять контрольных разрядов позволяют передавать от 11 до 26 информаци­ онных разрядов и т. д. Таким образом, избыточность ко­ да Хэмминга значительно выше, чем в коде с проверкой четности.

Код Хэмминга может быть легко расширен для по­ лучения кода с исправлением одиночной и обнаружени­ ем двойной ошибки. С этой целью к k контрольным раз­ рядам добавляется (&-{-1)-й контрольный разряд, обес­ печивающий контроль по четности всего кодового числа, включая и контрольные разряды.

При проверке информации после ее приема возмож­ ны три случая:

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

640

2. Одиночная ошибка: контроль общей четности сло­ ва обнаруживает ошибку, корректирующее число ука­ зывает номер искаженного разряда (если корректиру­ ющее число равно нулю, ошибка произошла в контроль­ ном разряде общей четности).

3. Двойная ошибка: корректирующее число не равно нулю, контроль общей четности слова не обнаруживает ошибки.

Контроль по коду Хэмминга реализуется с помощью набора схем подсчета четности (рис. 12-1 или 12-2), с помощью которых при кодировании определяются конт­ рольные разряды, а при декодировании формируется кор­ ректирующее число.

12-4. К О Н ТРО ЛЬ АРИФМЕТИЧЕСКИХ И ЛОГИЧЕСКИХ ОПЕРАЦИИ

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

Операция сдвига информации в регистре представля­ ет собой по существу передачу информации из і-х раз­ рядов регистра в или (г—/п)-е разряды в за­

роль четности суммы единиц.

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

§41