Декодирование

После получения закодированного сообщения происходит его разбивка на элементарные коды, вычисление для каждого кода S и в случае его неравенства 0 – корректировка соответствующего информационного члена (если S указывает на контрольный член, то корректировка не нужна). После удаления всех контрольных членов получаем исходное сообщение.

Примечание: Рассмотрено построение кодов Хемминга для бинарного кодирования и числе ошибок в элементарных кодах не более одной. Существует теория для построения таких кодов для равномерного кодирования любой арности и числе ошибок не более 2, 3,… и. д.

Пример решения задачи разработки кода Хемминга

Пример:

Разработать самокорректирующийся код (код Хэмминга) в соответствии с вариантом для бинарных слов длины m= 9 и привести примеры декодирования искаженных элементарных кодов (для всех вариантов – источник помех может исказить не более одной позиции элементарного кода).

Р Е Ш Е Н И Е

1 Определим длину l элементарных кодов

2^k–1 ≤ l, а 2^k ³ l+1, где l = m + k (по условию задачи m = 9)

Оба неравенства выполняются для k = 4 (8 ≤ 13, 16 ³ 13), т.е для 10 информационных членов понадобятся 4 контрольных членов в элементарных кодах, общая длина которых будет равна 14.

2 Контрольные члени элементарного кода будут вычисляться так:

Ряд 1 b₁ = b₃+ b₅ + b₇ + b₉ + b₁₁ + b₁₃ (mod 2),

Ряд 2 b₂ = b₃+ b₆ + b₇ + b₁₀ + b₁₁ (mod 2

Ряд 3 b₄= b₅+ b₆ + b₇ + b₁₂ + b₁₃ (mod 2),

Ряд 4 b₈= b₉+ b₁₀ + b₁₁ + b₁₂ + b₁₃ (mod 2),

3 Пример кодирования исходного элементарного сообщения (длина 10 позиций т.е m = 10)

В таблице ниже приведен пример определения контрольных членов элементарного кода (контрольный член равен 1, если число единиц соответствующего ему ряда нечетно и 0 – если четно). Значения контрольных членов выделены курсивом.

4 Пример корректировки искаженного в одной позиции элементарного кода (пусть в процессе передачи по каналу связи элементарный код, представленный в строке 2 предыдущей таблицы искажен в позиции 5 вместо 1 получен 0)

В результате подсчета кода ошибки получен следующий результат:

S = S_k… S₂ S₁ = 0101 (в бинарном представлении), что соответствует 5 (т.е. ошибка в позиции 5 и для корректировки нужно 0 (поз. 5) заменить на 1). Результат восстановления приведен ниже.

Осталось удалить контрольные биты в позициях 1,2,4,8.

Лекция 8

Примеры решения задач

Задача № 3

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

Таблица вариантов к задаче 3

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