Лабораторная работа № 4

(№ 9 по списку и инд.вариант t = 9)

Студента ИТ-14-1 Красовского Абхая

Тема: Изучение различных видов кодирования

Цель: Изучить алгоритмы, применяемые в различных видах кодирования. Задание

Задача № 1

Вариант	m
9	10

m

1 Определим длину l элементарных кодов

2^k–1≤ l , а 2^k  l+1, где l = m + k (по условию задачи m = 10 )

Оба неравенства выполняются для k = 4 ( 8 ≤ 13, 16  14), т.е для 10 информационных членов понадобятся 4 контрольных члена в элементарных кодах, общая длина которых будет равна 14.

2 Определим контрольные члени элементарного кода:

Ряд 1 ₁ = ₃+ ₅ + ₇ + ₉ + ₁₁ + ₁₃ (mod 2),

Ряд 2 ₂ = ₃+ ₆ + ₇ + ₁₀ + ₁₁ (mod 2),

Ряд 3 ₄= ₅+ ₆ + ₇ + ₁₂ + ₁₃ (mod 2),

Ряд 4 ₈= ₉+ ₁₀ + ₁₁ + ₁₂ + ₁₃ (mod 2),

3 Пример кодирования исходного элементарного сообщения (длина 10 позиций т.е m = 10)

В таблице ниже приведен пример определения контрольных членов элементарного кода (контрольный член равен 1, если число единиц соответствующего ему ряда нечетно и 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 = S₄ S₃S₂ S₁ = 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

Задача № 2

Вариант	r	q	p1, p2, …pr
9	11	2	0,26; 0,22; 0,14

Разработать схемы алфавитного кодирования с минимальной избыточностью (коды Хаффмана) для случаев (а) и (б):

а) появление букв в сообщении равновероятно;

б) вероятности появления букв в сообщении заданы.

Построить кодовые деревья. Получить схемы кодирования, определить l_ (увеличение длины закодированного сообщения над исходным)

Р Е Ш Е Н И Е

q ^m  r  q ^m+1, (1)

(для конкретных значений q и r всегда можно подобрать значение m, удовлетворяющее этому неравенству).

Обобщенный алгоритм поиска кода (схемы кодирования) с минимальной избыточностью:

• для построения элементарных кодов использовать только m и m+1 ярусы кодового дерева;

• переходить на m+1 ярус только после исчерпания всех возможностей m– го яруса.

Для реализации этого алгоритма необходимо представить r в виде уравнения:

r =(q ^m– n )+ q n – t , (2)

где n – количество неконцевых вершин яруса m ( будут ветвиться в m+1 ярус);

t (t  q).– количество вершин m+1 яруса, которые не будут задействованы при построении кода (n, t – целые неотрицательные числа).

Формула для определения l_ :

l_ = [( q ^m– n)  m + (q n – t)( m+1)]/ r (3)

q =2 r = 11 в соответствии с формулой (1) m = 3. Для кодирования будет достаточно 1–го, 2–го и 3-го ярусов обобщенного кодового дерева (см. рис. 1).

r =( q ^m – n)+ q n – t, 11= (8 –n)+ 2 * n – t (подбираем целые n и t)

Равенство выполняется для n = 5 и t= 1.

Определим l_ для полученной схемы по формуле (3)

l_ = [( q ^m– n)  m + (q n – t)( m+1)]/ r

l_ = (( 8-5) х 5 + (2х5 – 1) (3+1)) / 11 = 600/11 = 54,54.

Вывод: Изучил алгоритмы, применяемые в различных видах кодирования.

---

Смотрите также файлы

• Course.docx

• Lab1.docx

• Lab2.docx

• Lab3.docx

• Lab4.docx