Файл: Основы технической эксплуатации ЭЦВМ..pdf

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

В помехоустойчивых кодах с 3 можно не только обнаруживать одиночные ошибки, но и определять по­ зицию разряда, в котором появилась ошибка, а следова­ тельно, и исправлять ее. Пояснить это можно следую­ щим образом. При появлении одиночной ошибки код исказится так, что ошибочная комбинация будет отли­ чаться от истинной только в одном разряде, а от всех остальных разрешенных комбинаций не менее чем в двух разрядах. Такое положение позволяет определить по­ зицию разряда, в котором произошла ошибка и испра­ вить ее. Исправление ошибки в этом случае можно вести путем поочередного изменения значений символов (ну­ ля на единицу и наоборот), записанных в разрядах кодовой комбинации. После каждого изменения символа в одном из разрядов производится проверка и, если комбинация остается запрещенной, символ в данном разряде восстанавливается. Поочередное изменение зна­ чений символов ведется до тех пор, пока не будет получе­ на разрешенная комбинация. Для обнаружения двойных ошибок необходимо иметь код с d = 3, а для их исправ­ ления— с <і=5.

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

где t — число ошибок.

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

При выборе помехоустойчивого кода следует иметь в виду, что, во-первых, вероятность появления ошибок одновременно в двух, трех и более разрядах значительно меньше, чем вероятность появления ошибки ■в одном разряде (37), и, во-вторых, что коды, предназначенные для уверенного обнаружения, например, одиночных оши-

105

бок, будут обнаруживать и некоторую часть двойных, тронных ошибок и т. д.

В качестве простейшего помехоустойчивого кода молшо использовать код с проверкой «а четность. Этот код основан на добавлении к обычному «-разрядному числу или слову одного дополнительного (контрольного) /і+ 1-го разряда, значение которого івыбирается таким, чтобы общее количество единиц в изображении любого числа или слова было четным. В случае /появления оди­ ночной ошибки в каком-либо разряде, включая и конт­ рольный, при передаче кодовой комбинации общее коли­ чество единиц в кодовой комбинации станет нечетным. При этом должен выдаваться сигнал ошибки.

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

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

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

* Операция суммирования двоичной последовательности по мо­

106

открывает входы сумматора по модулю 2. Если число единиц в поступившей на вход сумматора комбийации было четным, то на выходе его будет нуль, если нечет­ ным — единица.

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

а)

Рис. 3-3. Структурная схема кодирующего устройства для определе­ ния знака четности при последовательном вводе и передаче инфор­ мации.

писана в выходной регистр. Закодированное таким об­ разом число или слово будет готово к передаче. Много­ входовый сумматор по модулю 2 может собираться на базе однотипных схем типа «исключительно ИЛИ», каж­ дая из которых определяет признак четности двухразряд­ ного кода. Такой сумматор строится обычно по пирами­ дальному принципу. На рис. 3-3,6 показана структурная схема сумматора по модулю 2 на четыре входа.

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

107

Декодирующее устройство для проверки на чет­ ность представлено на рис. 3-5. Выходы разрядов инфор­ мационного регистра связаны со входами сумматора по модулю 2. При нечетном количестве единиц в 'кодовой

Рис. 3-4. Структурная схема кодирующего устройства для определения знака четности при параллельном вво­ де и передаче информации.

Рис. 3-5. Структурная схема декодирующего устройства для проверки на'четность.

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

Для исправления одиночной ошибки, как было пока­ зано выше, одного контрольного разряда недостаточно.

108

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

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

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

Минимальное количество контрольных разоядов г, необходимое для построения корректирующего кода при заданном' количестве информационных разрядов т, вы­ бирается из условия соблюдения неравенства

Неравенства (3-3) и (3-4) составлены исходя из того, что г контрольных разрядов должны позволить записать в двоичном коде номер любого из т + г разрядов кодо­ вой комбинации числа или слова.

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

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

109

Из табл. 3-1 следует, что для получения корректиру­ ющего кода десятпразрядное число должно содержать шесть .информационных и четы.ре контрольных разряда.

Следовательно, вся кодовая комбинация должна быть разбита на четыре контрольных группы. Пронумеруем все десять разрядов и присвоим каждому из них свой номер от 0 до 9. Запишем номера этих Разрядов в два вертикальных столбца в десятичной и двоичной систе­ мах счисления в табл. 3-2.

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

Разряды 3, 5, 6, 7 и 9, принадлежащие одновременно

1І0