Артюх Р.Ю.
ИТ-07м
Лабораторная работа № 7
Тема: Изучение различных видов кодирования
Цель: Изучить алгоритмы, применяемые в различных видах кодирования.
Задание
1 Изучить теоретический материал по теме лабораторной работы .
2 Решить 2 задачи в соответствии с индивидуальным вариантом.
Выбор варианта: студент выбирает № варианта задачи, определив значение t, где t = [N/ 10] – остаток от деления нацело числа N (порядковый номер в списке преподавателя).
,
Задача № 1
Разработать самокорректирующийся код (код Хэмминга) в соответствии с вариантом для бинарных слов длины m и привести примеры декодирования искаженных элементарных кодов (для всех вариантов – источник помех может исказить не более одной позиции элементарного кода).
Разработать самокорректирующийся код (код Хэмминга) в соответствии с вариантом для бинарных слов длины m и привести примеры декодирования искаженных элементарных кодов (для всех вариантов – источник помех может исказить не более одной позиции элементарного кода).
Таблица вариантов к задаче 3
Вариант |
m |
1 |
10 |
Р Е Ш Е Н И Е
1 Определим длину l элементарных кодов
2k–1 ≤ l , а 2k l+1, где l = m + k (по условию задачи m = 10 )
Оба неравенства выполняются для k = 4 ( 8 ≤ 13, 16 14), т.е для 10 информационных членов понадобятся 4 контрольных члена в элементарных кодах, общая длина которых будет равна 14.
В множестве натуральных чисел {1,2,3,…, l }выделим следующие подмножества:
1, 3, 5, 7, 9 ….(содержатся все числа, у которых при переводе в двоичную запись в последнем разряде 1);
2, 3, 6, 7, 10 ….(содержатся все числа, у которых при переводе в двоичную запись в предпоследнем разряде 1);
. . . . . . . . . .
2k–1, 2k–1 +1, ….(содержатся все числа, у которых при переводе в двоичную запись в k–ом, считая справа, разряде 1).
Наименьшие члены этих подмножеств являются степенями 2: 1 = 20 ; 2 = 21;
4 = 22;…., причем 2k–1 ≤ l , а 2k+1 l+1.
Члены i набора 1 2 3 …l , у которых индекс i принадлежит множеству {1, 2, 4,… 2k–1}, называются контрольными членами, остальные – информационными. Таким образом, контрольных членов будет k, а информационных l – k = m. Сформулируем правило построения набора …l по набору 1 2 3…..m.
Сначала определяются информационные члены:
3 = 1
5 = 2
6 = 3
. . . . .
Таким образом, набор информационных членов, расположенных в естественном порядке, совпадает с набором 1 2 3…..m . Затем определяются контрольные члены,
1 = 3+ 5 + 7 + …(mod 2),
2 = 3+ 6 + 7 + …(mod 2), (3)
4= 3+ 6 + 7 + …(mod 2),
2 Контрольные члени элементарного кода будут вычисляться так:
Ряд 1 1 = 3+ 5 + 7 + 9 + 11 + 13 (mod 2),
Ряд 2 2 = 3+ 6 + 7 + 10 + 11 (mod 2
Ряд 3 4= 5+ 6 + 7 + 12 + 13 (mod 2),
Ряд 4 8= 9+ 10 + 11 + 12 + 13 (mod 2),
3 Кодирование исходного элементарного сообщения (длина 10 позиций т.е m = 10)
В таблице ниже происходит определение контрольных членов элементарного кода (контрольный член равен 1, если число единиц соответствующего ему ряда нечетно и 0 – если четно). Значения контрольных членов в таблице выделены курсивом.
b3 =1, b5 = 1, b6 = 0, b7=1, b9=0, b10 =0, b11=0, b12=1, b13= 1, b14=0;
Номера позиций |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Код сообщения |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Ряд 1 |
1 |
|
1 |
|
1 |
|
1 |
|
0 |
|
1 |
|
1 |
|
Ряд 2 |
|
1 |
1 |
|
|
0 |
1 |
|
|
0 |
1 |
|
|
0 |
Ряд 3 |
|
|
|
0 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
Ряд 4 |
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
4 Корректировки искаженного в одной позиции элементарного кода (пусть в процессе передачи по каналу связи элементарный код, представленный в строке 2 предыдущей таблицы искажен в позиции 5 вместо 1 получен 0 )
Номера позиций |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Si |
Код сообщения |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
Ряд 1 |
1 |
|
1 |
|
0 |
|
1 |
|
0 |
|
1 |
|
1 |
|
1= S1 |
Ряд 2 |
|
1 |
1 |
|
|
0 |
1 |
|
|
0 |
1 |
|
|
0 |
0= S2 |
Ряд 3 |
|
|
|
0 |
0 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
1= S3 |
Ряд 4 |
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0= S4 |
В результате подсчета кода ошибки получен следующий результат:
S = S4 S3S2 S1 = 0101 (в бинарном представлении), что соответствует 5 (т.е. ошибка в позиции 5 и для корректировки нужно 0 (поз. 5) заменить на 1). Результат восстановления приведен ниже.
Номера позиций |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Код полученного сообщения |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Код сообщения после коррекции |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Сообщение (удалены контрольные члены) |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |