Контроль передачи информации
разряд, которому присвоим нечетный порядковый номер и
который установим при кодировании таким образом, чтобы сумма 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
[pic]
Пусть X — слово, записанное в ОП. а X' — считанное из ОП слово, в
котором обнаружены две ошибки. Тогда по сигналу схемы контроля инициируется
следующая процедура.
В неисправную ячейку ОП записывается обратный код считанного слова X'
и затем производится его считывание. Над получаемым при этом кодом (Х) и
кодом X' производится операция
[pic]
Код Z содержит 1 в разрядах, в которых имеются ошибки.
Схемы управления ОП по коду Z корректируют одну ошибку. После этого
схема коррекции одной ошибки исправляет вторую ошибку.
Использованная литература:
1. А.Я. Савельев «Основы информатики»;Моск. ; изд. МГТУ имени
Н.Э.Баумана.
2.
| | скачать работу |
Контроль передачи информации |