Код Хэмминга.

Дата добавления: 2014-12-01; просмотров: 1785; Нарушение авторских прав

Сущность кода Хэмминга заключается в том, что контрольные разряды, определяемые на основе информационной части, определяются с помощью вычисления контрольных сумм по модулю 2. Для каждого контрольного разряда своя контрольная сумма. Контрольные разряды могут размещаться как справа информационной части, так и внутри нее.

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

Используются два варианта размещения контрольных разрядов:

1.контрольные разряды располагаются отдельно от информационных;

2.контрольные разряды чередуются с информационными.

Позиции контрольных разрядов:

...X₁₂	X₁₁	X₁₀	X₉	X₈	X₇	X₆	X₅	X₄	X₃	X₂	X₁
... И	И	И	И	К	И	И	И	К	И	К	К

К - контрольный разряд, И - информационный разряд.

Место контрольного разряда определяется формулой: 2ⁱ =1,2,4,8,16,...

где i – номер контрольного разряда.

Условия проверки на четность.

Для определения контрольных разрядов используется сумма по модулю 2 (проверка на четность). Количество условий проверки на четность равно количеству контрольных разрядов. Эти условия сводятся к вычислению контрольных сумм: S₁,S₂,S₃...

- через 1 по 1 - через 2 по 2 - через 4 по 4

Вычисление 1-ого контрольного разряда:

Вычисление 2-ого контрольного разряда:

Вычисление 3-его контрольного разряда:

Условия проверки на четность позволяют установить место ошибочного разряда ( обнаружить и устранить ошибку ).

Опознаватель места ошибки – это кодовая комбинация, составленная из контрольных сумм: S₀=...S₄,S₃,S₂,S₁ , где S₀ - число, указывающее на номер ошибочного разряда. Если S₀=0, то ошибки в кодовой комбинации нет.

Для исправления ошибки необходимо заменить 0 на 1 и наоборот.

Пример. Закодируем кодом Хэмминга число 11.

Q(X)=(1011)₂=(11)₁₀ – безызбыточный код.

1. Определение мест информационных разрядов.

И	К	И	И	И	К	И	К	К
--	--

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

Результат : H(X)=1010101 – код Хемминга.

2. Обнаружение и исправление ошибок.

Пусть H_ош (X)=1011101

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

Опознаватель S₀ = 100, т. е. ошибка в 4-ом разряде.

<== предыдущая лекция	\|	следующая лекция ==>
Формирование циклического кода.	\|	Определение количества контрольных разрядов в коде Хэмминга.