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

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

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

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

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

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

Способность кода обнаруживать или исправлять “ошибки” определяется так называемым минимальным кодовым расстоя­нием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значе­ния от 1 до п. Минимальным кодовым расстоянием данного ко­да называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, от­личающихся друг от друга только в одном разряде, то мини­мальное расстояние данного кода равно 1.

Простой (не избыточный) код имеет минимальное расстоя­ние d_min — 1. Для избыточных кодов d_min > 1. Если d_min > 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка при­ведет к появлению запрещенного слова и может быть обнару­жена. Если d_min = 3, то любая одиночная ошибка создает запре­щенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле ко­дового расстояния) разрешенным словом, можно исправить одиночную ошибку.

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

d_min>r+1. (2)

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

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

d_min>2r+1. (3)

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При отсутствии ошибок E_kE_k-1 ... E₂E₁=0 при наличии ошибки не равными нулю будут те суммы Е_i, в образовании которых участвовал ошибочный разряд; корректирующее чис­ло при этом будет равно порядковому номеру ошибочного разряда.

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

(4) (12.5)

Требуемое число контрольных разрядов (или, что то же самое, разрядность корректирующего числа) определяется из следующих соображений. Пусть кодовое слово длиной п разря­дов имеет m информационных и k = п — т контрольных разря­дов. Корректирующее число длиной k разрядов описывает 2^k состояний, соответствующих отсутствию ошибки и появлению ошибки в i-м разряде. Таким образом, должно соблюдаться соотношение

или

(5)

 

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

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

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

Модифицированный код Хэмминга. К контрольным разря­дам Хэмминга добавляется еще один (в последнем при­мере восьмой) разряд КР контроля четности всех одновремен­но считываемых (записываемых) информационных и кон­трольных разрядов. При считывании формируются корректи­рующее число E_kE_k-1 ... E₁, и разряд общей четности КР' для всех считанных разрядов, включая КР. Модифицированный код Хэмминга позволяет устранять одиночные и обнаруживать двойные ошибки, как это следует из табл. 1.

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

Таблица 1

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

Использованная литература:

А.Я. Савельев «Основы информатики»;Моск. ; изд. МГТУ имени Н.Э.Баумана.