Добавил:
abhai2013@gmail.com Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
8
Добавлен:
30.06.2018
Размер:
25.63 Кб
Скачать

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

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

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

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

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

Задача № 1

Вариант

m

9

10

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

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

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

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

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 – если четно). Значения контрольных членов в таблице выделены курсивом.

Номера позиций

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

Задача № 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 mn )+ q nt , (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 mn)+ q nt, 11= (8 –n)+ 2 * nt (подбираем целые n и t)

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

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

l = [( q m n) m + (q nt)( m+1)]/ r

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

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

Соседние файлы в папке Второй триместр