Teoria_informatsii_i_kodirovania
.pdfКорректирующий код Хемминга
•Коды Хемминга позволяют исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа проверочных
символов 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)= =1 − .
•Для двоичного кода расстояние равно числу кодовых элементов, в которых одна комбинация отличается от другой.
•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, проверочных векторов можно составить 2 . Этого количества
должно быть достаточно для исправления n ошибок. Таким образом 2 ≥ n+1.
Формальное описание избыточных кодов
•Если m=3, то n=10, 23 < 7 + 3 + 1 = 11.
•Если m=4, то n= 24 > 7+4+1 =12..
Следовательно, порождающая матрица кода (12,4) может иметь вид:
•1000000 0011
•0100000 1001
•0019999 1100
•0001000 0110
•0000100 0101
•00000101010
•00000011110
•Так как нам достаточно дополнить матрицей с
d=1, а это можно сделать различным образом.