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

12803
знака
7
таблиц
3
изображения

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

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

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

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

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

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

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

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

dmin>r+1. (2)

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

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

dmin>2r+1. (3)

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

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

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

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


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

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

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

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


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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

(12.5)


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



или

(5)

 
 



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

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

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

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

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

Таблица 1

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

В неисправную ячейку ОП записывается обратный код счи­танного слова X' и затем производится его считывание. Над получаемым при этом кодом (Х) и кодом X' производится операция

Код Z содержит 1 в разрядах, в которых имеются ошибки.

Схемы управления ОП по коду Z корректируют одну ошиб­ку. После этого схема коррекции одной ошибки исправляет вторую ошибку.



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

А.Я. Савельев «Основы информатики»;Моск. ; изд. МГТУ имени Н.Э.Баумана.  
Информация о работе «Контроль передачи информации»
Раздел: Информатика, программирование
Количество знаков с пробелами: 12803
Количество таблиц: 7
Количество изображений: 3

Похожие работы

Скачать
48394
4
0

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

Скачать
14274
2
0

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

Скачать
118994
12
11

... 1.5 Уровни помех и линейных затуханий   1.5.1 Электрические помехи в каналах ВЧ связи по ВЛ Электрические помехи имеются в любом канале связи. Они являются основным фактором, ограничивающим дальность передачи информации из-за того, что сигналы, принимаемые приемником, искажаются помехами. Для того чтобы искажения не выходили за пределы, допустимые для данного вида информации, должно быть ...

Скачать
25824
4
4

... при управлении процессом, т.е. возникает частичная автоматизация. 1. Анализ исходных данных Рассмотрим некоторые особенности технического задания курсового проекта. Необходимо разработать систему сбора и передачи информации первой категории, что соответствует вероятности возникновения ошибки 10-8. Т.к. задан симплексный тип канала, то необходимо производить защиту информации при помощи кодов ...

0 комментариев


Наверх