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

 КОНТРОЛЬ ПЕРЕДАЧИ  ИНФОРМАЦИИ

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

Если длина кода п разрядов, то такимдвоичным кодом можно представить максимум 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">

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

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