Меню
Главная
Авторизация/Регистрация
 
Главная arrow Техника arrow Анализ систем телемеханики

Код Хэмминга

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

,

где N - число сообщений, которое нужно передать. Длина кода определяется из неравенства

,

тогда число контрольных разрядов .

Рассмотрим построение кода Хэмминга на следующем примере. Пусть необходимо передать слово 10110, представленное в обыкновенном коде. С помощью пятиэлементного обыкновенного кода можно передать слова. Тогда длина кода определится следующим образом:

.

В нашем случае , т.е. искомое слово Хэмминга имеет девять разрядов, из них контрольных разрядов, соответственно .

За контрольные разряды принимаются разряды, десятичный номер которых равен степени числа 2. Это разряды Двоичные номера контрольных разрядов имеют только одну 1. Остальные разряды являются информационными, и в них записывается передаваемое слово.

Для того чтобы определить значения контрольных разрядов, составляют контрольные суммы .

Сумма - это сумма по модулю два значений разрядов, двоичные номера которых имеют единицу на i- м месте справа.

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

Тогда

В нашем примере . Таким образом, процедура кодирования закончена и получено следующее соответствие 10110 011001100.

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

двоичное число , т.е. произошла ошибка в 5 разряде. Исправление ошибки состоит в изменении значения искаженного разряда на противоположное.

Для определения параметров кода Хэмминга выразим число m через n:

.

Отсюда

;

;

.

Тогда

; .

Описанный код имеет кодовое расстояние d=3. Этот код способен исправлять ошибки кратности 1 и обнаруживать ошибки кратности 2. Однако одновременно исправлять одиночные и обнаруживать двойные ошибки код не может, так как эти ошибки могут оказаться неразличимыми. Например, в передаваемом слове происходит двойная ошибка в разрядах а2 и а5, и принятое слово имеет вид 001011100.

Контрольные суммы соответственно

Такой же результат получится, если произойдет одиночная ошибка в седьмом разряде и будет принято слово 011001000. В этом случае

Чтобы код Хэмминга одновременно исправлял одиночные ошибки и обнаруживал двойные, необходимо придать ему кодовое расстояние d=4. Для этого добавляется еще один десятый контрольный разряд, который проверяет четность единиц в информационных и основных контрольных разрядах, т.е. :

При приеме такого кода возможно:

  • - ошибки нет - все суммы , и проверка на четность подтверждается;
  • - есть одиночная ошибка в информационных и основных контрольных разрядах, она исправляется - хотя бы одна сумма , и проверка на четность не подтверждается;
  • - есть ошибка дополнительного контрольного разряда, и он исправляется - все суммы , и проверка на четность не подтверждается;
  • - есть двойная ошибка; она обнаруживается, но не исправляется - хотя бы одна сумма , и проверка на четность подтверждается.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Право
Психология
Религиоведение
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее