проба страницы

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

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

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

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

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

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

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

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

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

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

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

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