Методы и средства передачи информации. Лекция 4. Часть 1

Код с повторением
Сколько раз повторять?
Код проверки на чётность (избыточность 1 разряд)
Избыточные символы называют контрольными или проверочными.
1010 -> 101010101010

Прямоугольный код

Прямоугольный код

Прямоугольный код
Исправление 1 ошибки и обнаружение двух ошибок

Избыточность
r = n-k k (контрольные биты)
(информ)
Cколько бит добавить чтобы исправлять одну ошибку
r бит и k контрольных
2k >= r + k + 1
r = 10, k = 4
r = 4, k = ?
n

Избыточность

Код Хэмминга
Выпишем те х , у которых единичка в крайнем правом разряде
x1 + x3 + x5 + x7 = 0 (mod 2)
Выпишем те х , у которых единичка посередине
x2 + x3 + x6 + x7 = 0 (mod 2)
Выпишем те х , у которых единичка в крайнем левом разряде
x4 + x5 + x6 + x7 = 0 (mod 2)
Пусть дано двоичное число
(x1 x2 x3 x4)
Дополним его 3-мя контрольными разрядами
(x5 x6 x7) и получим число:
(x1 x2 x3 x4 x5 x6 x7)

Код Хэмминга
x1 + x3 + x5 + x7 = 0 (mod 2)
x2 + x3 + x6 + x7 = 0 (mod 2)
x4 + x5 + x6 + x7 = 0 (mod 2)
x5 = x2 + x3+ x4 (mod 2)
x6 = x1 + x3 + x4 (mod 2)
x7 = x1 + x2 + x4 (mod 2)
001 | 1011001
110 | 0010100
000 | 0110011
111 | 1110001

Код Хэмминга
s3 = x1 + x3 + x5 + x7 mod 2
s2 = x2 + x3 + x6 + x7 mod 2
s1 = x4 + x5 + x6 + x7 mod 2
Номер одиночной ошибки k определяется числом с двоичной записью s1 s2 s3?
Т.е. k = (s1 s2 s3)2
(x1 x2 x3 x4 x5 x6 x7)
(x001 x010 x011 x100 x101 x110 x111)

Код Хэмминга (обнаружение двойной ошибки)
s3 = x1 + x3 + x5 + x7 mod 2
s2 = x2 + x3 + x6 + x7 mod 2
s1 = x4 + x5 + x6 + x7 mod 2
s0 = (x1 + x2 + x3 + x4 + x5 + x6 + x7 ) mod 2
Почему обнаруживаются две ошибки и исправляется одна?

Код Хэмминга

Код Хэмминга

Код Хэмминга

Код Хэмминга

Код Хэмминга

Расстояние Хэмминга