Реферат: Контроль передачи информации
КОНТРОЛЬ ПЕРЕДАЧИ ИНФОРМАЦИИПри контроле передачи информациинаибольшее распространение получили методыинформационной избыточности, использующиекоды с обнаружением и коррекцией ошибок.
Если длина кода п разрядов, то такимдвоичным кодом можно представить максимум 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 и т. д.). При одновременном возникновениидвух или любого другого четного числа ошибок код с проверкой четности необнаруживает ошибок.
При контроле понечетности контролируется полное пропадание информации,поскольку кодовое слово, состоящее из О, относится к запрещенным.
<img src="/cache/referats/13062/image002.jpg" v:shapes="_x0000_s1026">
Код с проверкой четности имеет небольшую избыточность и не требует больших затрат оборудования нареализацию контроля. Этот код широко применяется в вычислительных машинах для контроля передач информации междурегистрами и для контролясчитываемой информации в оперативной памяти.
При построении схем определения четности суммы 1слова используют логические элементы с парафазным выходом, подобныеизображенному на рис. 1, a) и б). Показанные схемы выполняют операцию сложения по модулю 2 (условноеобозначение М2) для двоичных переменных х и у. На рис. 1, в показанасхема определения признака четности байта.
Рис. 1. Схемыопределения четности
Каждый информационный символ должен быть задан прямым и инверсным кодом. Структура схемы проверкичетности является многоступенчатой,т. е. слово делится на несколько групп разрядов, в каждой из которыхпроверка четности производится прямым способом (первая ступень), далее производитсяпроверка четности для групп второй ступени, образованных из групп первойступени, четности которых в этом случаерассматриваются как обычные двоичные разряды, и т. д. до окончательной проверки четности суммы 1 всегослова. В последней ступени четностьбайта сравнивается со значением контрольного разряда КР.
<img src="/cache/referats/13062/image004.jpg" align=«left» hspace=«12» v:shapes="_x0000_s1028">
Рис 2. Схема контроля по совпадению
Легко установить связь кодирования при контролепо четности с выполнением сложения по модулю 2. Если количество 1 в словедолжно быть четным, то в контрольный разряд записывается прямой код суммы помодулю 2 всех информационных разрядов слова. При контроле на нечетность в контрольныйразряд заносится обратный код указанной суммы.
Контроль по совпадению. Припередачах можно использовать и другой вид контроля — контроль по совпадению.После передачи информации из одного регистра в другой правильность передачи можно проверить поразряднымсравнением содержимого всех разрядов регистров.
При контроле по совпадению не требуетсяформирования каких-либо дополнительныхконтрольных разрядов, следовательно, этот метод основывается не наинформационной, а на схемной избыточности.
Один из вариантов схемы контроля передач посовпадению показан на рис.2. После передачи информации из регистра А врегистр Б (или из Б в А) через время, несколько большее времени установления переходных процессов втриггерах регистров, на выходесхемы появляется сигнал 1 при несовпадении содержимого А и Б в0 в противном случае. При контроле передачипо совпадению обнаруживаются ошибки любой кратности. Затраты оборудования при контроле по совпадению меньше,чем при контроле по четности.
Контроль по совпадениюявляется быстродействующим, так как используется одна ступеньформирования, в то время как в схеме проверки четности многоразрядного числа,как правило, больше одной ступени.
Однако контроль по совпадению обладает существеннымнедостатком. Этот метод позволяет проверить правильность передачи числа врегистр и отсутствие сбоев при его хранении только до тех пор, пока не изменитсвоего состояния регистр, из которогопередавалась информация. При контроле по четности проверяется не толькоправильность передачи, но и отсутствие сбоев при хранении числа в регистре(памяти) в течение сколь угодно большого времени.
Корректирующий кодХэмминга. В оперативной памяти применяюткод Хэмминга, позволяющий исправлять ошибки.
Код Хэмминга строится таким образом, что кимеющимся информационным разрядам слова добавляется определенное числоконтрольных разрядов, которые формируются перед записью слова в ОП и вместе синформационными разрядами слова записываются в память.
При считывании слова контрольная аппаратураобразует из прочитанных информационных и контрольных разрядов корректирующеечисто, которое равно 0 при отсутствии ошибки либоуказывает место ошибки, например двоичный порядковый номер ошибочногоразряда в слове. Ошибочный разряд автоматическикорректируется изменением его состояния на противоположное.
Рассмотрим процесскодирования для кода Хэмминга с коррекцией одиночнойошибки (минимальное кодовое расстояние dmin=3). Если кодовое слово не содержит ошибок, то корректирующее число должно быть равно 0. При наличии ошибки корректирующеечисто должно содержать номер ошибочного разряда. Если в младшемразряде корректирующего числа появится 1, то это означает ошибку в одном изтех разрядов слова, порядковые номера которых имеют 1 в младшем разряде (т. е.разрядов с нечетными номерами). Введем первый контрольный разряд, которомуприсвоим нечетный порядковый номер и который установим при кодировании такимобразом, чтобы сумма 1 всех разрядов с нечетными порядковыми номерами была равна0. Эта операция может быть записана в виде
<img src="/cache/referats/13062/image006.jpg" v:shapes="_x0000_i1025">
где x1,х3 и т. д. — двоичные символы,размещенные в разрядах с порядковыми номерами 1, 3 и т. д.
Появление 1 во втором разряде (справа)корректирующего числа означает ошибку в техразрядах слова, порядковые номера которых (2, 3, 6, 7, 10, 11, 14, 15 ит. д.) имеют 1 во втором справа разряде. Поэтому вторая операция кодирования,позволяющая найти второй контрольный разряд, которому должен быть присвоен какой-либо порядковый номер изгруппы 2, 3, 6, 7, 10, 11 и т. д., имеет вид
<img src="/cache/referats/13062/image008.jpg" v:shapes="_x0000_i1026">
Рассуждаяаналогичным образом, можно определить все другиеконтрольные разряды путем выполнения операций
<img src="/cache/referats/13062/image010.jpg" v:shapes="_x0000_i1027">
После приема кодового слова (совместно сосформированными контрольными разрядами)выполняются те же операции подсчета, которые были описаны выше, аобразующееся число<img src="/cache/referats/13062/image012.jpg" v:shapes="_x0000_i1028">
считается корректирующим.
При отсутствии ошибок EkEk-1 … E2E1=0приналичии ошибки не равными нулюбудут те суммы Еi,в образовании которых участвовал ошибочный разряд; корректирующее числопри этом будет равно порядковому номеру ошибочного разряда.
Выбор места для контрольныхразрядов производится таким образом, чтобыконтрольные разряды участвовали только водной операции подсчета четности. Это упрощает процесс кодирования. Рассмотрение выражений для E1, Е2,Е3 и т. д. показывает, что такимипозициями являются разряды с номерами, являющимися целымистепенями двойки: 1, 2, 4, 8, 16 и т. д.
(4)
(12.5)
Требуемое число контрольных разрядов (или,что то же самое, разрядность корректирующегочисла) определяется из следующихсоображений. Пусть кодовое слово длиной п разрядов имеет mинформационных и k= п— т контрольныхразрядов. Корректирующее число длиной kразрядов описывает 2kсостояний, соответствующих отсутствию ошибки и появлениюошибки в i-мразряде. Таким образом, должно соблюдаться соотношение
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA"><img src="/cache/referats/13062/image014.jpg" v:shapes="_x0000_i1029">
или
<div v:shape="_x0000_s1027">
(5)
<img src="/cache/referats/13062/image016.jpg" v:shapes="_x0000_i1030">
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">
Изэтого неравенства следует, например, что пять контрольныхразрядов позволяют передавать в коде Хэмминга до 26 информационных разрядов ит. д.
Если в ОП одновременно записываются илисчитываются восемь информационных байт (64разряда), то при использовании кодаХэмминга потребуется семь дополнительных контрольных разрядов.
Контроль по коду Хэмминга реализуется с помощьюнабора схем подсчета четности (см. рис.1),которые при кодировании определяют контрольные разряды, а придекодировании формируют корректирующее число.
Модифицированный код Хэмминга. Кконтрольным разрядам Хэмминга добавляетсяеще один (в последнем примере восьмой) разряд КР контроля четности всеходновременно считываемых (записываемых)информационных и контрольных разрядов. При считывании формируютсякорректирующее число EkEk-1… E1,и разряд общей четности КР' для всехсчитанных разрядов, включая КР. Модифицированный код Хэмминга позволяет устранять одиночные и обнаруживать двойныеошибки, как это следует из табл. 1.
Коррекция двойных ошибок в ОП. Прииспользовании в ОП модифицированного кодаХэмминга может производиться коррекция двойных ошибок.
Таблица1
<img src="/cache/referats/13062/image018.jpg" v:shapes="_x0000_i1031">
Пусть X— слово, записанное в ОП. а X' — считанное из ОП слово, в котором обнаружены две ошибки. Тогда по сигналу схемы контроля инициируется следующая процедура.
В неисправную ячейку ОП записывается обратный код считанного слова X' и затем производится его считывание. Над получаемым при этом кодом (Х) и кодом X' производится операция
<img src="/cache/referats/13062/image020.jpg" v:shapes="_x0000_i1032">
Код Zсодержит 1 в разрядах, в которых имеются ошибки.
Схемы управления ОП по коду Zкорректируют одну ошибку. После этого схема коррекции одной ошибки исправляет вторую ошибку.
<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Использованная литература:
А.Я. Савельев «Основы информатики»; Моск.; изд. МГТУ имени Н.Э.Баумана.