Р е ш е н и е. На основании (2.6) вычислим количество информационных разрядов помехоустойчивого кода:

На основании (2.6) вычислим количество информационных разрядов помехоустойчивого кода:

2^k-1=15 k=4.

На основании (2.7) определяем длину кодовых слов n:

2^n-4-1=n n =7.

Таким образом, требуется (n-k)=(7-4)=3 избыточных (проверочных) разряда. Сопоставим их значения возможным ошибкам (таблица 2) по следующему правилу: значение синдрома в двоичной позиционной системе счисления должно определять номер разряда кода, в котором произошла ошибка. Разряды пронумерованы справа налево. Нулевое значение синдрома означает отсутствие ошибки.

Коды, которые строятся по этому принципу, известны как коды Хэмминга.

В таблице 2 разряды кода a_i, i= пронумерованы справа налево от 1 до n=7, а разряды синдрома c_j - от 1 до (n-k)=3. В соответствии с таблицей 2, поскольку младший разряд синдрома равен 1 при ошибках в 1, 3, 5 и 7 разрядах,

с₁=а₁ а₃ а₅ а₇. (2.10)

Если ошибка в указанных разрядах не произошла, значение первого разряда синдрома c₁ =0; в противном случае, если ошибка произойдёт в одном из разрядов a₁, a₃, a₅, a₇, то приведённая выше сумма по модулю 2 будет равна 1, что и будет признаком ошибки.

Таблица 2 - Таблица опознавателей

Равенство (2.10) определит на приёмном конце значение младшего разряда синдрома. Аналогично строятся два других проверочных равенства для второго и третьего разрядов синдрома, в итоге получим:

(2.11)

Проверочные равенства (2.11) определяют значения разрядов синдрома на приемном конце системы связи. Если значение синдрома С=(с₃с₂с₁)=000, ошибка при передаче очередного кодового слова не произошла, в противном случае значению синдрома в двоичной системе счисления надо поставить в соответствие десятичную цифру, которая определяет номер разряда, в котором произошла одиночная ошибка.

В семиразрядном кодовом слове в качестве проверочных удобно выбрать разряды, каждый из которых входит только в одно проверочное равенство с₁=а₁, с₂=а₂, с₃=а₄. В качестве информационных используются разряды а₃, а₅, а₆, а₇.

Тогда, в соответствии с (2.11), вычисление проверочных разрядов осуществляется по следующим формулам:

(2.12)

Равенства (2.12) используются на передающем конце системы связи для преобразования безызбыточного четырехразрядного кодового слова в семиразрядную комбинацию помехоустойчивого кода.

Таким образом, получены проверочные равенства для построения кода Хэмминга (7, 4), исправляющего все одиночные ошибки. В соответствии с (2.2) минимальное кодовое расстояние (по Хэммингу) равно d_min=2×1+1=3. А в соответствии с (2.1) кратность обнаруживаемых ошибок R=3-1=2, следовательно, этот код может также использоваться для обнаружения ошибок кратности 2.

Аналогично можно строить код Хэмминга для любого n, но наиболее эффективен он для n=2^t -1, где t=3, 4, 5,… Для этих значений величина k/n (норма кода) достигает своего предельного значения. В этом случае в соответствии с (2.5) достигается оценка Хэмминга Q=2ⁿ/(n+1). Оптимальные значения n и k представлены в таблице 3.

Таблица 3 - Норма кода Хэмминга,

исправляющего одиночные ошибки

Поиск по сайту: