теория информации. ТИ (Best). Лекции по предмету "Теория информации" Красноярск 2002

• Название: Лекции по предмету "Теория информации" Красноярск 2002
• Анкор: теория информации
• Дата: 10.12.2022
• Размер: 1.06 Mb.
• Имя файла: ТИ (Best).doc
• Тип: Лекции; #837351
• страница: 11 из 12

Код Хэминга

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

, n = n_u + n_k , n – значность кода,

Количество контрольных разрядов можно определить по таблице. Номера позиций контрольных символов выбирают по закону 2ⁱ, i = 0,1,2… Значения контрольных разрядов выбирают следующим образом.
Алгоритм:

1) Составляется вспомогательная таблица для ряда натуральных чисел в двоичной коде, Число строк в таблице n – значность кода. В каждой i –й строке вспомогательной таблицы ставится в соответствие a_i коэффициент, который участвует в проверке, a_i – коэффициенты, из которых составлена кодовая комбинация

n	Код	Коэффиц-иенты	n	Код	Коэффици-енты
1	0001	а1	7	0111	a7
2	0010	a2	8	1000	a8
3	0011	a3	9	1001	a9
4	0100	a4	10	1010	a10
5	0101	a5	11	1011	a11
6	0110	a6	12	1100	a12

На основании этой таблицы составляется схема проверок, которые производятся суммированием выбранных проверочных коэффициентов . Для каждой поверки выбираются свои проверочные коэффициенты. В первую проверку входят коэффициенты, которые содержат в младших разрядах единицы. Во вторую проверку входят коэффициенты содержащие единицу во втором разряде(a₂,a₃,a₆,_…). В третью проверку входят коэффициенты содержащие единицу в третьем разряде.

Схему проверок сведём в отдельную таблицу.

Nпроверок	Схема	Nконтрольных. символов
1	a1 + a3 + a5 + a7 + a9 + a11	1
2	a2 + a3 + a6 + a7 + a10 + a11	2
3	a4 + a5 + a6 + a7 + a12	3
4	a8 + a9 + a10 + a11 + a12 +…	4

Количество проверок равно количеству разрядов. Контрольные коэффициенты выбираются таким образом, чтобы проверочная сумма была равна нулю. Т.е. если количество единиц чётное, то контрольный разряд нулевой, если нечётнно, то контрольный разряд равен единице.
Пример: Построить код Хэминга по комбинации

0101 n_u = 4 n_k = 3 n_k = log(n_u + 1) + log(n_u + 1)

1 ,2,3 k = 7 2ⁱ = 1,3,4,8

К онтрольные разряды будут занимать позиции 1,2,4.
Код Хэминга

а₁a₂a₃a₄a₅a₆a₇

k₁k₂0 k₃1 0 1 - макет
1) a₁ + a₃ + a₅ + a₇ = k₁ + 0 + 1 + 1 = 0  k₁ = 0

2) a₂ + a₃ + a₆ + a₇ = k₂ + 0 + 0 + 1 = 0  k₂ = 1

3) a₄ + a₅ + a₆ + a₇ = k₃ + 1 + 0 + 1 = 0  k₃ = 0
Код Хэминга будет иметь вид 0100101