Введение.

Данная работа представляет собой описание методов, легших в основу систем автоматического диагностирования и контроля ЭВМ. Эти методы - общие для многих современных средств связи. Это основа всех схем контроля передачи информации(например в ЭВМ между периферийными устройствами).

1.  Контроль передачи информации.

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

Если длина кода п разрядов, то таким двоичным кодом можно представить максимум 2ⁿ различных слов. Если все разряды слова служат для представления информация код называется простым (неизбыточным). Коды, в которых

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

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

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

Способность кода обнаруживать или исправлять ошибки  определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов несовпадают.  Если длина слова п, то кодовое расстояние может принимать  значения от 1 до п. Минимальным кодовым расстоянием данного  кода называется минимальное расстояние между двумя любыми  словами в этом коде. Если имеется хотя бы одна пара слов,  отличающихся друг от друга только в одном разряде, то минимальное  расстояние данного кода равно 1. Простой (неизбыточный) код имеет минимальное расстояние dmin=1. Для разделимых избыточных кодов: dmin>1.  Если dmin>=2, то любые два слова в данном коде отличаются не менее  чем в двух разрядах, следовательно любая одиночная ошибка приведет  к появлению запрещенного слова и может быть обнаружена. Если dmin>=З, то любая одиночная ошибка создает запрещенное слово, отличающееся от  правильного в одном разряде, а от любого другого  разрешенного слова — не менее чем в двух разрядах. Заменяя запрещенное  слово ближайшим к нему (в смысле кодового расстояния) разрешенным  словом, можно исправить одиночную ошибку. В общем случае, чтобы избыточный код позволял обнаруживать ошибки  кратностью r, должно выполняться условие dmin >=r+1.                 (1)

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

dmin>=2r-1.                 (2) 

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

   Минимальное расстояние кода dmin=2, поэтому код с проверкой четности (нечетности) обнаруживает все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5 и т.д.). При одновременном возникновении двух или любого другого четного числа ошибок код с проверкой четности (нечетности) не обнаруживает ошибок. 

    При контроле по нечетности контролируется полное пропадание информации, так как кодовое слово, состоящее из 0, относится к запрещенным.

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

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

   На рис. 1, в показана схема определения признака четности байта.

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

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

Рис. 1. Схема определения четности

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

   Контроль по совпадению. При передачах можно использовать и другой вид контроля — контроль по совпадению. После передачи информации из одного регистра в другой правильность передачи можно проверить путем поразрядного сравнения содержимого всех разрядов регистров.

   При контроле по совпадению не требуется формирования каких-либо дополнительных контрольных разрядов, следовательно, этот метод основывается не на информационной, а на схемной избыточности. Один из вариантов схемы контроля передач по совпадению  показан на рис. 2. После передачи информации из регистра А в регистр Б (или из Б в А) через время, несколько большее времени установления переходных процессов в триггерах регистров, на выходе схемы появляется сигнал 1 при несовпадении содержимого А и Б п 0 в противном случае.  При контроле передачи по совпадению обнаруживаются ошибки любой кратности. Затраты оборудования при контроле по совпадению меньше, чем при контроле по четности. Контроль по совпадению  является быстродействующим, так как используется одна ступень  формирования. В схеме проверки четности /Регистр/ 5

Рис. 2. Схема контроля по совпадению.  

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

2.  Корректирующие коды. Код Хэмминга. 

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

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

   Рассмотрим более подробно процесс кодирования с использованием кода Хэмминга с коррекцией одиночной ошибки (минимальное кодовое расстояние dmin=3). Если кодовое слово не содержит ошибок, то корректирующее число должно быть равно 0. При наличии ошибки это число должно содержать номер ошибочного разряда. Если в младшем разряде корректирующего числа появится 1 то это означает ошибку в одном из тех разрядов слова порядковые номера которых имеют 1 в младшем разряде (разрядов с нечетными номерами). Введем первый контрольный разряд, которому присвоим нечетный порядковый номер и который установим при кодировании таким образом, чтобы сумма единиц всех разрядов с нечетными порядковыми номерами была равна 0. Эта операция может быть записана в виде: 

E₁=x₁ + x₃ + x₅ +... 

где x_1,x₃  и т. д. двоичные символы, размещенные в п разрядах с порядковыми номерами 1, 3 и т. д.

   Появление единицы во второю разряде (справа) корректирующего числа означает ошибку в тех разрядах слова, порядковые номера которых (2, 3, 6, 7, 10, II, 14, 15 т.д.) имеют единицу во втором разряде справа. Поэтому вторая операция кодирования, позволяющая найти второй контрольный разряд, которому должен быть присвоен какой-либо порядковый номер из группы 2, 3, 6, 7, 10, II и т. д., имеет вид: 

    E₂ = X₂ + X₃ + X₆ + X₇ + X₁₀ + X₁₁ +... = 0  

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

   E₃ = X₄ + X₅ + X₆ + X₇ + X₁₂ + X₁₃  + X₁₄ + X₁₅ + ...  = 0

   E₄ = X₈ + X₉ + X₁₀ + X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + ...  = 0  

   и т. д. После приема кодового слова (совместно со сформированными  контрольными разрядами) выполняются те же операции подсчета, которые были описаны выше, а образующееся  число E_k E_k-1 ... E₃ E₂ E₁ считается корректирующим. При отсутствии ошибок е_k е_k-1 ... е₂е₁=0, при наличии  ошибок не равными нулю будут те суммы Еi  в образовании  которых участвовал ошибочный разряд; корректирующее число  при этом будет равно порядковому номеру ошибочного разряда. Выбор места для контрольных разрядов производится таким образом, чтобы контрольные разряды участвовали только в одной операции подсчета четности. Это упрощает процесс кодирования. Рассмотрение выражений для E₁, E₂ E₃ и т.д. показывает, что такими позициями являются разряды  с номерами, являющимися целыми степенями двойки: 1,2,4,8, 16 и т.д. Требуемое число контрольных разрядов (разрядность корректирующего числа) определяется из следующих соображений. Пусть кодовое слово длиной п разрядов имеет т информационных и k = n — т контрольных разрядов. Корректирующее  число длиной k разрядов описывает 2^k состояний, соответствующих отсутствию ошибки и появлению ошибки в i-м разряде. Таким образом,  должно соблюдаться соотношение

   2^k>n+1                  (3)

   или

   2^k-k-1>=m,           (4) 

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