11.2. Контроль по четности / нечетности, контроль Хэмминга.

 

Контроль на чётность (нечётность) заключается в следующем: к передаваемым байтам данных (8 бит) добавляется 1 контрольный бит. Контрольный бит вычисляется по следующему правилу: если в информационном байте число единиц четное, то контрольный бит равен 1. При этом общее число единиц передаваемой информации должно быть нечетным. Данный способ контроля не позволяет обнаружить ошибки четной кратности (т.е. ошибки одновременно в двух, четырех и т.д. битах) и поэтому используется при невысоких требованиях к достоверности принимаемых данных (или при малой вероятности ошибок в линии передачи).

Хэммингом предложен способ добавления контрольных разря­дов, при котором путем определенных проверок на четность доста­точно просто находится в принятом слове ошибочный разряд. Рас­смотрим этот способ.

Первый, второй, четвертый, восьмой и т. д. разряды (т. е. раз­ряды с номерами, выражаемыми числами вида 2^k) используются в качестве контрольных. Последующее изложение будем вести на примере так называемого 7/4 кода Хэмминга (общее число разря­дов в словах равно 7, из них 4 разряда — информационные, 3 раз­ряда — контрольные). Пусть а₄, а₃, а₂, a₁ — цифры информацион­ных разрядов слова; k₃,  k₂,  k₁  —  цифры контрольных разрядов:

номера разрядов     7     6     5    4     3    2     1

цифры разрядов      а₄   а₃   а₂   k₃   a₁    k₂   k₁

Запишем представления номеров разрядов:

десятичное представление     7        6        5       4       3        2        1

двоичное представление      111    110    101    100   011    010    001

Значения цифр k₃, k₂, k₁ контрольных разрядов находятся по следующему правилу.

Цифра контрольного разряда k₁ должна обеспечивать четность числа единиц в разрядах, номера которых в двоичном представле­нии содержат единицу в первом разряде (это условие выполняет­ся для первого, третьего, пятого и седьмого разрядов слова). Учи­тывая, какая информация хранится в указанных разрядах, полу­чим условие k₁(+)a₁(+)а₂ (+)a₄ = 0.

Цифра контрольного разряда k₂ должна обеспечивать четность числа единиц в разрядах, двоичные номера которых имеют едини­цы во втором разряде (это условие выполняется для второго, третьего, шестого и седьмого разрядов слова). Следовательно, k₂(+)a_l(+)a₃(+)a₄ = 0.

Цифра контрольного разряда k₃ обеспечивает четность единиц в разрядах, двоичные номера которых имеют единицу в третьем разряде (это условие выполняется, для четвертого, пятого, шестого и седьмого разрядов слова). Отсюда k₃(+)а₂(+)а₃(+)a₄ = 0.

Прибавляя к обеим частям приведенных равенств соответствен­но k₁, k₂, k₃ и учитывая, что k₁(+)k₁ = 0; k₂(+)k ₂= 0; k₃(+)k₃ = 0, усло­виям для цифр контрольных разрядов можно придать следующую форму:

k₁ = a₁(+)a₂(+)a₄;  k₂ = a₁(+)a₃(+)a₄;   k₃ = а₂(+)а₃(+)а₄.

Пусть информационная часть слова равна

1     0     1     0

а₄   а₃     а₂   а₁

Пользуясь приведенными выше выражениями, находим  значения контрольных разрядов:

k₁ = 0(+)1(+)1 = 0;  k₂ = 0(+)0(+)1 = 1;   k₃ = 1(+)0(+)1 = 0.

Следовательно, в данном примере слово имеет вид 1010010.

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

Пусть, например, вместо правильного значения слова 1010010 принято слово с ошибкой в пятом разряде, т. е. 1000010.

Результат проверки первого условия для принятого слова

k₁(+)a₁(+)а₂ (+)a₄ = 0(+)0(+)0 (+)1 = 1.

Нарушена четность, в первый разряд синдрома записывается 1. Результат проверки второго условия

k₂(+)a_l(+)a₃(+)a₄ = 1(+)0(+)0 (+)1 = 0.

Четность не нарушена, во второй разряд синдрома записывается 0. Результат проверки третьего условия

k₃(+)а₂(+)а₃(+)a₄ = 0(+)0(+)0 (+)1 = 1.

Четность нарушена, в третий разряд синдрома записывается 1. Итак, получен синдром 101₂ = 5₁₀, который указывает номер раз­ряда, содержащего ошибку (ошибка в пятом разряде принятого слова).

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

Определим необходимое число контрольных разрядов k.

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