Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Построение кодов Хемминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется элемент такой, чтобы число единичных символов в получившейся последовательности было четным
Предположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. В качестве примера возьмём 15-битовое кодовое слово x1...x15, хотя алгоритм пригоден для кодовых слов любой длины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй — условное обозначение битов, в третьей — значения битов.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
x15 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
Вставим в информационное слово контрольные биты r0...r4 таким образом, чтобы номера их позиций представляли собой целые степени двойки: 1, 2, 4, 8, 16... Получим 20-разрядное слово с 15 информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равными нулю. На рисунке контрольные биты выделены розовым цветом.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
r0 |
r1 |
x1 |
r2 |
x2 |
x3 |
x4 |
r3 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
r4 |
x12 |
x13 |
x14 |
x15 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа бит кодового слова (включая контрольные биты), округлённому в большую сторону до ближайшего целого. Например, информационное слово длиной 1 или 2 бита требует двух контрольных разрядов, 3- или 4-битовое информационное слово — трёх, 5...11-битовое — четырёх, 12...26-битовое — пяти и т.д.
Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования. Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова. В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
||
|
r0 |
r1 |
x1 |
r2 |
x2 |
x3 |
x4 |
r3 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
r4 |
x12 |
x13 |
x14 |
x15 |
||
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
||
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
r0 |
|
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
r1 |
|
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
r2 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
r3 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
r4 |
|
В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r0) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если произведение получилось больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.
Если описывать этот процесс в терминах матричной алгебры, то операция представляет собой перемножение матрицы преобразования на матрицу-столбец кодового слова, в результате чего получается матрица-столбец контрольных разрядов, которые нужно взять по модулю 2.
Нехай при передачі коду b = b1b2...bl відбулася помилка в розряді з номером t, тобто на виході каналу отримано слово b' = b1b2…bt-1btbt+1…bl.
Представимо t у вигляді к-розрядного двійкового числа: t = Vk-1...V1V0. Покажемо, як за кодом b' знайти розряди Vi числа t.
Розглянемо t' = V'k-1...V'1V'0 де:
V'0= ⊕ ∑b'j ; j ∈ L0 ,
V'1= ⊕ ∑b'j ; j ∈ L1 ,
…
V'k-1= ⊕ ∑b'j ; j ∈ Lk-1.
Покажемо, що t' = t, тобто V'0= V0 ; V'1=V1 ; … ; V'k-1= Vk-1 .
Розглянемо ситуації:
1. Нехай Vi = 0; це означає, що t ∉ Li = {j ∈ Li : Vi = 1}.
Отже, всі розряди з номерами з Li отримані на виході каналу без спотворення, тобто b't = bt ; t ∈ Li .
2. Нехай Vi = 1, тоді t ∈ Li = {j ∈ Li : Vi = 1}, і деякий розряд з номером з Li отриманий на виході каналу із спотворенням, тобто для деякого q з Li , а для всіх j ∈ Li, j≠q, b'j = bj.
Звідси отримуємо V'i= ⊕ ∑b'j = (⊕ ∑bj) ⊕ 1= 0 ⊕ 1 = 1. Отже, і в цьому випадку Vi=V'i.
Нехай в розглянутому вище прикладі помилка при передачі кодового слова b = b1b2b3b4b5b6b7b8b9b10b11b12b13 = 1010011010111 відбулася в 11 розряді (t = 11). Тобто на виході каналу отримано повідомлення b' = b'1b'2b'3b'4b'5b'6b'7b'8b'9b'10b'11b'12b'13 = 1010011010011.
Для цього кодового повідомлення отримуємо:
V0 = b'1 ⊕ b'3 ⊕ b'5 ⊕ b'7 ⊕ b'9 ⊕ b'11 ⊕ b'13 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
V1 = b'2 ⊕ b'3 ⊕ b'6 ⊕ b'7 ⊕ b'10 ⊕ b'11 =0 ⊕1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0= 1
V2 = b'4 ⊕ b'5 ⊕ b'6 ⊕ b'7 ⊕ b'12 ⊕ b'13 = 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
V3 = b'8 ⊕ b'9 ⊕ b'10 ⊕ b'11 ⊕ b'12 ⊕ b'13 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1
Таким чином, двійкове представлення номера розряду, в якому відбулася помилка, є 1011. Але це не що інше, як двійкове представлення числа 11. Отже, помилковий розряд 11.
Для виправлення помилки необхідно біт помилкового розряду змінити протилежним.
Декодування (отримання початкового повідомлення) здійснюється так: після виправлення помилки виписати послідовно зліва направо з коду повідомлення інформаційні символи, тобто a1a2…am = b3b5b6b7b9b10b11b12b13. У нашому прикладі з коду b = 1010011010111 виписуємо а = 101110111. Це і є початкове повідомлення.