Контрольная работа Ковырзин А.А.(Хэмминг). Алгоритмы кодирования и декодирования по Хэммингу для обучающихся по специальности

• Название: Алгоритмы кодирования и декодирования по Хэммингу для обучающихся по специальности
• Дата: 15.11.2021
• Размер: 50.01 Kb.
• Имя файла: Контрольная работа Ковырзин А.А.(Хэмминг).docx
• Тип: Контрольная работа; #272438
• страница: 2 из 3

Алгоритм кодирования

В соответствии с заданным вариантом, требуется сгенерировать код Хемминга для следующего информационного кодового слова:

1

1

1

1

1

1

0

1

0

0

0

1

1

1

0

В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй – условное обозначение битов, в третьей – значения битов:

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	1	1	1	1	1	0	1	0	0	0	1	1	1	0

Вставим в информационное слово контрольные биты слово r₀...r₄ таким образом, чтобы номера их позиций представляли собой целые степени числа два: 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	1	1	1	0	1	1	0	1	0	0	0	0	1	1	1	0

Добавим к таблице 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	1	1	1	0	1	1	0	1	0	0	0	0	1	1	1	0
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

В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r₀) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если произведение получилось больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.

r₀=(1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·1+0·1+1·0+0·1+1·0+0·0+1·0+0·0+1·1+0·1+1·1+0·0) mod 2 = 6 mod 2 = 0
r₁=(0·0+1·0+1·1+0·0+0·1+1·1+1·1+0·0+0·1+1·1+1·0+0·1+0·0+1·0+1·0+0·0+0·1+1·1+1·1+0·0) mod 2 = 6 mod 2 = 0
r₂=(0·0+0·0+0·1+1·0+1·1+1·1+1·1+0·0+0·1+0·1+0·0+1·1+1·0+1·0+1·0+0·0+0·1+0·1+0·1+1·0) mod 2 = 4 mod 2 = 0

r₃=(0·0+0·0+0·1+0·0+0·1+0·1+0·1+0·1+1·1+1·1+1·0+1·1+1·0+1·0+1·0+0·0+0·1+0·1+0·1+0·0) mod 2 = 3 mod 2 = 1
r₄=(0·0+0·0+0·1+0·0+0·1+0·1+0·1+0·1+0·1+0·1+0·0+0·1+0·0+0·0+0·0+1·0+1·1+1·1+1·1+1·0) mod 2 = 3 mod 2 = 1

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	1	1	1	1	1	1	0	1	0	0	0	1	1	1	1	0
1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	r0	0
0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	r1	0
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	0	1	1	1	1	1	1	1	1	0	0	0	0	0	r3	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	r4	1

Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей. Кодирование по Хэммингу завершено. Полученное кодовое слово: 00101111110100011110.