Корректирующий код Хемминга

•Коды Хемминга позволяют исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа

проверочных символов m = 3, 4, 5… существует классический код Хемминга

•С маркировкой

•При других значениях числа информационных символов k получаются так называемые усеченные (укороченные) коды Хемминга.

•Так для кода имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося

усеченным от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается (укорачивается) на 6.

Классический код Хемминга (7,4)

k = 4, m = 3. Равенства проверки на

блок-схема кодера

схема декодера

Формальное описание избыточных кодов

•Метрическое пространство – такое множество элементов, что для любой пары его элементов определено вещественное число d(ab), обладающее свойствами:

•1. d(ab)= d(ba);

•2. d(ab) ≥ 0

•3. d(ab)=0 при a=b

•4. d(ab)≤ d(ac)+ d(cb)

•Элементы a,b,c называются точками n- мерного пространства, а d(ab) расстоянием в пространстве.

Формальное описание избыточных кодов

•В теории кодирования наиболее употребительной является метрика

•d(ij)=

•Для двоичного кода расстояние равно числу кодовых элементов, в которых одна комбинация отличается от другой.

•n- мерное пространство порождается матрицей

Формальное описание избыточных кодов

10……0

01……0 I = 001….0 000…01 000….1)

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

Формальное описание избыточных кодов

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

•d=r+1

•d=2s+1

•d=r+s+1

•d=e+1

Формальное описание избыточных кодов

•Порождающая матрица кода -G=(n,k). Здесь k –число информационных символов кода. Так как в единичной матрице кодовое расстояние равно 2, тоиз это следует

•построение порождающей матрицы кода с d=3 и 4.

•Пусть k= 7. Если количество проверочных символов m=n-k, проверочных векторов можно составить . Этого количества должно быть достаточно для исправления n ошибок. Таким образом n+1. ≥

Формальное описание избыточных кодов

•Если m=3, то n=10,

•Если m=4, то n= > 7+4+1 =12.. Следовательно, порождающая матрица кода (12,4) может иметь вид:

•1000000 0011

•0100000 1001

•0019999 1100

•0001000 0110

•0000100 0101

•00000101010

•00000011110

•Так как нам достаточно дополнить матрицей с

d=1, а это можно сделать различным образом.