Компрессия и декомпрессия данных.

Общие сведения.

Количество или объём передаваемых цифровых сообщений (данных) выражается следующим соотношением: V=vT, где V – скорость передачи (Кб/с); T – время передачи (сек).

Как следует из этого соотношения, уменьшение объёма V позволяет при заданной скорости v сократить время передачи T, а при заданном времени передачи Т увеличить скорость v передаваемых сообщений. В связи с этим при транспортировке данных по сетям часто поступают следующим образом. На передающем узле выполняют компрессию (сжатие) данных, уменьшающая их объём до некоторого значения Vmin чтобы передать данные по сети с большей скоростью. Поскольку уменьшение объёма сопровождается потерей информации, на приёмном узле выполняется обратная операция по восстановлению исходной информации, называется декомпрессией данных.

В сетях используют следующие виды сжатия данных:

1. статическое, когда данные сначала компрессируются программным способом, например, с помощью популярных архиваторов типа WinRAR или WinZIP, а затем отсылаются в сеть;

2. динамическое, реализуемая программно-аппаратными средствами в процессе передачи информации;

3. адаптивная, позволяющая в зависимости от типа данных выбрать тот или иной алгоритм компрессии.

Рассмотрим некоторые методы компрессии (декомпрессии) данных.

Метод десятичной упаковки. Если все данные в передаваемом кадре состоят из десятичных цифр, то можно существенно сократить одну длину. Дело в том, что 3 старших бита всех ACSII-кодов десятичных цифр содержит комбинацию 011, поэтому при обычном кодировании десятичного числа вместо 7 бит ACSII-кода потребуется только 4 бита.

Для реализации метода в заголовок кадра достаточно поместить соответствующий управляющий символ.

Метод относительного кодирования. Отличительной особенностью этого метода является то, что вместо обычного кодирования цифр кодируется отклонения между двумя последовательными цифрами. При этом передаются опорное значение и сами отклонения. Такой метод используется при цифровом кодировании голоса, когда в каждом такте передаётся только разница между соседними замерами голоса.

Статистическое кодирование. Для представления текстовых символов в ACSII-коде (равномерный код) используется постоянное количество битов. Частота появления букв в тексте при этом не учитывается. Однако статистический анализ показывает, что в стандартном тексте на русском языке, состоящем из тысячи символов, буква О встречается гораздо чаще (в среднем 95 раз), чем буква Ф (2 раза). Поэтому целесообразно часто встречающиеся символы алфавита кодировать меньшим числом битов, а редко встречающиеся – большим. При таком кодировании общее число битов в передаваемом тексте будет уменьшено, что сократит объём передаваемой информации.

Для построения неравномерных кодов алфавита используют специальный алгоритм (например, алгоритм Гофмана).

Словарный метод сжатия. При этом методе на основе обработанной информации составляется специальный словарь – таблица, в который записываются часто повторяющиеся последовательности битов (слова) и их коды (номера). При новом появлении аналогичных слов производится обращение к соответствующей ячейке таблицы и передаётся не последовательность битов, а только её номер, что значительно сокращает объём передаваемой информации. Структурная схема одного из алгоритмов сжатия, называемого LZW (по фамилиям авторов – Lempel, Ziv, Welch) приведена на рис. 3.10. В результате поток битов на выходе, направляемый в канал связи, оказывается в несколько раз меньшим по объёму, чем входной поток. Такой алгоритм по сжатию информации особенно эффективен при передаче по цифровому каналу связи цветных фотографий и телевизионныйх изображений. В частности, он использовался при передаче по узкополосному радиоканалу фотографий с поверхности Марса, позволяя получить на Земле снимки высокого качества.

Метод кодирования длины последовательности. Метод RLE основан на учёте часто повторяющихся и следующих друг за другом одинаковых символов. Например3 последовательность символов в виде AAAAAABBBCCCC будет передана как 6A3B4C, что при 8-разрядной коде сократит число передаваемых битов со 104 до 48. Этот метод даёт ощутимый выигрыш при передаче изображений с одинаковой цветовыми участками.

Следует отметить, что такие устройства коммуникационного оборудования, как модемы, мосты, коммутаторы и маршрутизаторы, поддерживают протоколы динамической компрессии с коэффициентом сжатия до 1:8, т.е. позволяет сократить объём передаваемых данных до восьми раз. Коэффициент компрессии зависит от типа передаваемых данных. Графические и текстовые данные имеют большой коэффициент сжатия, чем коды программ. Кроме того, существуют стандартные протоколы компрессии, например V.42bis, а также большое число нестандартных фирменных протоколов.

Методы доступа к сети.

Общие сведения.

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

1. Селективные методы. Особенность этих методов состоит в том, что передача начинается после получения, которого можно начать передачу. В методе с передачей маркера (или токена) разрешение передаётся от станции к станции.
2. Методы, основанные на принципе соперничества. Каждая станция перед началом передачи пытается получить доступ к линии связи. Ситуация, одновременного обращения к одному каналу передачи называется коллизией. Для её разрешения должна соблюдаться определённая дисциплина. Эту группу составляют методы состязаний: с прослушиванием линии связи до передачи; с прослушиваем до передачи и во время передачи; с прогнозированием столкновений; с обучающим прогнозированием столкновений и др.
3. Методы с резервированием времени. Передача возможна только в течение тех интервалов времени, которые заранее выделены (зарезервированы) для данной рабочей станции. Резервирование производится в начале соединения, а также в любой нужный пользователю момент.

По способу доступа различают два вида методов: со случайным и детерминированным доступом.

Методы со случайным доступом основаны на соперничестве. Они строятся с учётом возможности возникновения конфликтов и обусловливают способы их разрешения. Методы устойчивы к отказам сетевого оборудования, однако не гарантируют быстрого доступа.

Методы с детерминированным доступом определяют чёткий порядок предоставления доступа абонентам сети и практически полностью исключают конфликты. К ним относятся селективные и кольцевые методы.

По принципу управления различают централизованные и децентрализованные (распределённые) методы доступа к среде передачи.

В централизованных методах всё управление доступом сосредоточено в одном (центральном) узле сети, который всегда имеет возможность предоставить право на передачу только одному абоненту. Достоинством централизованных методов является отсутствие конфликтов, а их недостатком – возможность отказов в доступе при большом числе запросов.

В децентрализованных (распределённых) методах единый центр управления отсутствует и управление доступом полностью предоставлено абонентам сети, т.е. каждый узел самостоятельно обнаруживает и предотвращает все возможные конфликты. К достоинству методов следует отнести высокую устойчивость к отказам и большую гибкость управления (табл. 4.1).

ТАБЛИЦА