1. Теперь вычисляют значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит, но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N.
| Ав | |||||||||||||||||||||
| х | х | х | х | х | х | х | х | х | х | х | |||||||||||
| х | х | х | х | х | х | х | х | х | х | ||||||||||||
| х | х | х | х | х | х | х | х | х | х | ||||||||||||
| х | х | х | х | х | х | х | х | ||||||||||||||
| х | х | х | х | х | х |
Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
2. Для вычисления значение каждого контрольного бита берётся каждый контрольный бит и считается сколько среди контролируемых им битов единиц, получается некоторое целое число и, если оно чётное, то ставится ноль, если оно нечётное ставится единица. Или наоборот.
| Контрольные биты | |||||||||||||||||||||
| х | х | х | х | х | х | х | х | х | х | х | 0(четное) | ||||||||||
| х | х | х | х | х | х | х | х | х | х | 0(четное) | |||||||||||
| х | х | х | х | х | х | х | х | х | х | 1(нечетное) | |||||||||||
| х | х | х | х | х | х | х | х | 0(четное) | |||||||||||||
| х | х | х | х | х | х | 1(нечетное) |
Следовательно «Ав» равно последовательности 00 1 1 000 0 0000101 1 00010
3. Вторая пара букв вычисляется аналогично
| Контрольные биты | |||||||||||||||||||||
| тД | |||||||||||||||||||||
| х | х | х | х | х | х | х | х | х | х | х | 0(четное) | ||||||||||
| х | х | х | х | х | х | х | х | х | х | 0(четное) | |||||||||||
| х | х | х | х | х | х | х | х | х | х | 1(нечетное) | |||||||||||
| х | х | х | х | х | х | х | х | 0(четное) | |||||||||||||
| х | х | х | х | х | х | 1(нечетное) |
Следовательно «тД» равно последовательности 00 1 1 110 0 0010100 1 00100
4. Исходная последовательность: 10000000101000101110001010000100
После кодирования: 00 1 1 000 0 0000101 1 00010 00 1 1 110 0 0010100 1 00100
Порядок выполнения работы.
7. Взять данные для расчета согласно варианта задания в приложении.
8. Представить слово в бинарном виде с помощью кода ASCII.
9. Разделить исходное сообщение на блоки по 16 бит.
10. Вставить контрольные биты.
11. Вычислить контрольные биты.
12. Представить слово в виде исходной и закодированной последовательностей.
Контрольные вопросы:
1. Для чего нужно кодирование?
2. В чем отличие КХ от кодов Шенно-Фано и Хаффмана?
3. Какова длинна закодированного сообщения из 3-х слов по 40 бита?
4. В какие позиции вставляются контрольные биты в слове из 40 бит?
5. Как вычисляется значение контрольного бита?
Приложение.Варианты задания
| Номер п\п | Слово | Номер п\п | Слово |
| РпОз | ЖеаВ | ||
| ДЮаЫ | рПЕн | ||
| ГтиЕ | ВсМА | ||
| ЭдЛш | шЬрЕ | ||
| ЖнЕА | эЕтГ | ||
| ОРПм | ДпуЦ | ||
| МцЫч | лРнЕ | ||
| Тимс | ЧФвы | ||
| НОПЩ | юЕшЗ | ||
| ОуЦй | бСмУ | ||
| ЭЪшс | рУНщ | ||
| АВсЫ | ДмеН | ||
| ФЫцл | БвгН | ||
| ьнГр | иЕгР | ||
| уАнИ | ВфКт |
Практическая работа №8
Тема: Декодирование информации по алгоритму Хэмминга.
Цель: Научиться декодированию и исправление ошибки в тестовом слове по алгоритму Хэмминга.
Теоретические сведения
Исправлять ошибки труднее, чем их обнаруживать или предотвращать. Процедура коррекции ошибок предполагает два совмещенные процесса: обнаружение ошибки и определение места (идентификация сообщения и позиции в сообщении). После решения этих двух задач, исправление просто - надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется метод детектирования ошибок и повторной пересылки фрагмента, содержащего дефект. Для спутниковых каналов с типичными для них большими задержками системы коррекции ошибок становятся привлекательными. Здесь используют коды Хэмминга.
В данном примере используется длина информационного сообщения 16 бит, но длину можно взять любую.
Для каждого числа проверочных символов используется специальная маркировка вида (k,i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (15, 11), (31, 26).
Код (7,4) является минимально возможным кодом с достаточно большой избыточностью. Эффективность кода (k/n) растет с увеличением длины кода.
Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле: k/(i+k), где k — количество проверочных бит, i — количество информационных бит. Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).
Пример работы
Допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нам с ошибкой. К примеру, мы получили такое «Ав» (11-ый бит передался неправильно):
10 1 1 000 0 00 1 0101 1 00010
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые получены.