Сжатие методом кодирования длин повторений

Содержание

1 Расчетно-графическая работа№1
1.1 Сжатие методом кодирования длин повторений
2 Расчетно-графическая работа №2
2.1 Выбор наикратчайшего пути в сети по методу Дейкстры
Перечень сокращений
Список литературы
Приложение А
Приложение Б
Приложение В
Приложение Г

Расчетно-графическая работа №1

Сжатие методом кодирования длин повторений

1.1.1 Задание работы:

- используя исходные данные изображения, приведенные в приложении А, необходимо закодировать двоичное (двухцветное) изображение размером 8х8 элементов. При этом пустая клетка обозначает белый цвет, а клетка, в которой проставлена буква "Ч" обозначает черный цвет;

- выбор варианта заданий осуществляется по списку журнала преподавателя;

- просканируйте двухцветное изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1). В результате получите двоичный вектор данных.

1.1.2 Описать сценарии установления (завершения, регистрации, отмены регистрации и др.) связи между пунктами сети IP-телефонии. Варианты описаны в приложении Б.

1.1.3 Методические указания к выполнению задания работы 1.1.1. Кодирование сообщений может производиться с целью сокращения объема информации и повышения скорости ее передачи или сокращения полосы частот, требуемых для передачи. Такое кодирование называют экономным, безизбыточным, или эффективным кодированием, а также сжатием данных.

Целью сжатия данных является обеспечение компактного представления данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Система сжатия данных состоит из кодера и декодера источника. Кодер преобразует данные источника в сжатые данные, а декодер предназначен для восстановления данных источника из сжатых данных. Восстановленные данные, вырабатываемые декодером, могут либо абсолютно точно совпадать с исходными данными источника, либо незначительно отличаться от них.

В настоящей работе рассматривается сжатие методом кодирования длин участков (или повторений). Этот метод является достаточно эффективным при сжатии двоичных данных, например, черно-белых факсимильных изображений, черно-белых изображений, содержащих множество прямых линий и однородных участков, схем и т.п. Кодирование длин повторений является одним из элементов известного алгоритма сжатия изображений JPEG (Joint Photographic Experts Group). Идея сжатия данных на основе кодирования длин повторений состоит в том, что вместо кодирования собственно данных подвергаются кодированию числа, соответствующие длинам участков, на которых данные сохраняют неизменное значение.

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8х8 элементов, приведенное на рисунке 1.1. После сканирования этого изображения по строкам получим двоичный вектор данных Х [1].

Рисунок 1.1 – Двуцветное изображение

Х=(01111111 11000000 11111101 11111111 00000000 01000000 10000001 11111111) длиной 64 бит (скорость исходного кода составляет 1 бит на элемент изображения).

Выделим в векторе Х участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков – положительных целых чисел, соответствующих исходному вектору данных Х – будет иметь вид r =(1, 9, 6, 6, 1, 9, 9, 1, 6, 1, 6, 9). В этой последовательности заметна определенная повторяемость, которые можно закодировать каким-либо статическим кодом (таблица 1.1).

Таблица 1.1 – Кодер

Длина участка	Кодовое слово

Для того, чтобы указать, что кодируемая последовательность начинается с нуля, добавим в начале кодового слова префиксный символ 0.

В результате получим кодовое слово:

B(r) =(0 110 0 10 10 110 0 0 110 10 110 10 0)

длиной в 25 бит, то есть результирующая скорость кода R составит 25/64, или немногим более 0,39 бит на элемент изображения. При сжатии изображений большего размера и содержащих множество повторяющихся элементов эффективность сжатия может оказаться существенной.

1.1.4 Методические указания к выполнению задания работы 1.1.2.

IP-телефония – телефонная связь по протоколу IP.

Под IP-телефонией подразумевается набор коммуникационных протоколов, технологий и методов, обеспечивающих традиционные для телефонии набор номера, дозвон и двустороннее голосовое общение, а также видео общение по сети Интернет или любым другим IP-сетям. Сигнал по каналу связи передаётся в цифровом виде и, как правило, перед передачей преобразовывается (сжимается) с тем, чтобы удалить избыток информации и снизить нагрузку на сеть передачи данных.

Рассмотрим по шагам сценарий установления соединения между двумя терминалами Н.323 (см. рисунок 1.2):

Рисунок 1.2 – Сценарий установления соединения между терминалами Н.323

- оконечный пункт A (вызывающая сторона) соединяется с оконечным пунктом B (вызываемая сторона) и посылает сообщение Setup (установка), включающее тип вызова (например, только звуковые сигналы), номер вызываемой и вызывающей стороны и адрес;

- оконечный пункт B откликается сообщением уведомления (Alerting). Оконечный пункт A должен принять это сообщение прежде, чем истечет время, отведенное на установку;

- когда пользователь в оконечном пункте B отвечает на вызов (снимает трубку), сообщение Connect (соединение) передается в оконечный пункт A;

- оба терминала передают информацию о своих возможностях (типы среды, выбор кодека и информация о мультиплексировании) в сообщении TerminalCapabilitySet (установка возможностей терминала);

- каждый терминал отвечает сообщением TerminalCapabilitySetAck (подтверждение установки возможностей терминала). В случае если удаленный оконечный пункт не обладает какими-то возможностями, будет передано сообщение TerminalCapabilitySetReject (отклонение установки возможностей терминала), и терминалы продолжат передавать эти сообщения, пока не определят, что устанавливаемые возможности поддерживаются обоими оконечными пунктами;

- каждый терминал передает сообщение H.245 OpenLogicalChannel (открыть логический канал), позволяющее открыть логический канал с удаленным оконечным пунктом, чтобы настроить речевые каналы, по которым будет производиться обмен мультимедийными потоками;

- в случае готовности к приемке данных каждый терминал передает OpenLogicalChannelAck (подтверждение открытия логического канала) в удаленный оконечный пункт, определяя номер порта, на который удаленному оконечному пункту следует передавать данные RTP, и номер порта, на который следует передавать данные RTCP удаленному оконечному пункту;

- оконечные пункты обмениваются информацией в пакетах RTP. Во время этого обмена передаются пакеты RTCP для контроля качества передачи данных;

- когда оконечный пункт A дает отбой (вешает трубку), он должен передать сообщение H.245 CloseLogicalChannel (закрыть логический канал) для каждого канала, открытого с оконечным пунктом B;

- оконечный пункт B отвечает сообщением CloseLogicalChannelAck (подтверждение закрытия логического канала);

- оконечный пункт A посылает команду H.245 EndSessionCommand (команда завершения сеанса) и закрывает канал после приема такого же сообщения от оконечного пункта B;

- оба терминала посылают сообщение H.225.0 ReleaseComplete (освобождение завершено) по каналу сигнализации вызова, которое закрывает канал и завершает соединение.

Контрольные вопросы

1.2.1 Какие существуют способы уменьшения избыточности данных?

1.2.2 Поясните понятие «необратимый метод сжатия данных»?

1.2.3 Поясните понятие «обратимый метод сжатия данных»?

1.2.4 Перечислите алгоритмы сжатия без потери информации?

1.2.5 Какие факторы влияют на степень избыточности данных?

1.2.6 Приведите примеры форматов сжатия с потерями информации.

1.2.7 В чем состоит основная идея алгоритма сжатия методом длин повторений?

1.2.8 Приведите примеры кодеков сжатия голоса.

1.2.9 Установление соединения между терминалами Н.323.

1.2.10 Какие функции выполняет контроллер зоны?

1.2.11 Перечислите компоненты сети Н.323.