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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: реферат эволюция, курсовые работы
| Добавил(а) на сайт: Lada.

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

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

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

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

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

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

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

[pic]

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

[pic]

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

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

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

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

(4)

(12.5)

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

[pic] или

[pic]

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

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

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

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

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

Таблица 1