Галкин В.А., Григорьев Ю.А. Телекоммуникации и сети

Подождите немного. Документ загружается.

Основы

телекоммуникации

Под эффективным кодом понимают код, коэффициент избыточности кото-

рого равен нулю, т. е. для эффективньпс кодов Яср= п . или с учетом (2.81),

(2.82) и (2.83):

t n^p{x)\og т=-± р{х)\о% р(х). (2.89)

/ =1 / =1

Объединив суммы левой и правой части, получим:

± p(x)[nAog т + logpix)] = 0. (2.90)

Если/7(л:.) ^

О,

то необходимо, чтобы

log/?(x)

п.= длявсех/= 1,2,

...,г.

(2.91)

log/w

Однако отношение (2.91) не всегда является целым числом и, следователь-

но,

не для любого набора сообщений ^=

{лг^

х^,...,

х^}

с заданным распреде-

ле1шем вероятности/7(л:^),/7(л:2), ,..,р(х^) можно построить эффективный код с

минимальной избыточностью К^ = 0. Всегда можно обеспечить вьшолнение

неравенства:

logpix) logp(x)

..U^<n < -li^\ 1, (2.92)

log m ""^ log m

или умножая части неравенства на р(х) и суммируя по /, получим критерий

оценки эффективности реального кода:

Н(Х) Н(Х)

<п < + 1. (2.93)

log т ''Р log т

Выражение для коэффициента избыгочности равномерного двоичного кода

определим по формуле (2.85), в которой под максимальной энтропией

Н^^

бу-

дем понимать максимальную энтропию равномерного «-разрядного кода,

п^

= п,т = 2. При этом максимальная энтропия

Н^^

п^

log т =

п.

Под энтро-

пией

сообщений

Н(Х) буцем

понимать энтропию разрешенных кодовых комби-

наций, число которьк обозначим через N, тогда Н(Х) = log N.

Подставляя выражения для

Н^^

и Н(Х) в (2.85 ), имеем

K^=^(n-logN)/n=l- XogN/n, (2.94)

Для разделимых кодов формула упрощается:

/:^ = 1 - (log 20 / « = 1 - к/п, (2.95)

где

- длина кодовой комбинации;

- число информационных разрядов.

100

2.2.

Методы защиты от ошибок

сжатия данных

Анализ формулы (2.85) показьшает, что коэффициент избыточности прини-

мает значения от

(отсутствие избыточности) до 1 (избыточность неограни-

ченно велика). Коэффициент избыточности характеризует качество помехоус-

тойчивого кода - чем меньше избыточность кода при прочих равных условиях,

тем код лучше.

Алгоритм Хаффмена. Этот алгоритм применяют для построения кодов с

минимальной избыточностью. Пусть Х- {Xj, х^, ..., х^} - входной алфавит

кода

/",

а 5{0, 1} - выходной алфавит. С каждым символом х. связана вероят-

ность его появления/>(х.). Необходимо каждому символу алфавита Jf сопоста-

вить кодовую комбинацию в алфавите В таким образом, чтобы обеспечить

минимальную избыточность кода Г,

Поставленную задачу можно решить построением кодового дерева. Пост-

роение графа-дерева начинают с висячих вершин, которым в качестве весов

назначают вероятности/7(л:.), / =

1,2,...,

г. Висячие вершины графа упорядочи-

вают в соответствии с их весом, что позволяет в дальнейшем уменьшить чис-

ло пересечений ребер или вовсе исключить их. Само дерево строится по сле-

дующему алгоритму.

Шаг 7. Определяют число поддеревьев графа. Если оно меньше двух, то

дерево построено, и на этом действие алгоритма заканчивается. Если число

поддеревьев равно или больше двух, то переходят к шагу 2 (Замечание: в на-

чале построения имеется г изолированных вершин графа, являющихся подде-

ревьями и одновременно корнями поддеревьев).

Шаг 2, Выбирают корни двух поддеревьев графа с минимальными весами

и осуществляется сращивание выбранных поддеревьев

добавлением при этом

одной вершины и двух ребер. Вес вновь образованной вершины определяется

как сумма весов корней выбранных поддеревьев. Левому добавленному ребру

приписьюается вес, равный единице,

правом}^

- равный

нулю.

Осуществляется

переход к шагу 1.

В результате образуется кодовое дерево - граф с взвешенными ребрами.

Для получения кода символа х. достаточно выписать веса ребер, составляю-

щих путь из корня дерева в соответствующую висячую вершину.

Пример. Пусть входной алфавит содержит восемь различных символов

дг,, дг^,...,

^g,

выход-

ной

алфавит является двоичным

JB{0,1},

число символов выходного алфавита

Известна

вероятность (частота) появления

каждого символа в

передаваемом сообщении:

р(дг,) =

0,19;

р{х^ -

р{х^)

=0,16; р{х^ =0,15;

р{х^)

=0,12; р(х^

=0,11;

р{х^)

=0,09; р{х^ = 0,02. Необходимо

разработать

код и

определить коэффициент избыточности кода.

Процесс построения

кодового

дерева содержит

семь

циклов последовательного выполнения

шагов

1 и 2

алгоритма

(рис.

2.15).

Для

оценки

эффективности

кода

промежуточные вычисления

занесем

табл.

2.4.

Средняя

длина

кодовой

комбинации

''cp=Z"/M^.) = 2,92;

101

Основы телекоммуникации

Цикл

Рис. 2.15. Построение кодового дерева

энтропия сообщения, составленного

из

символов входного алфавига, равна

ЩХ)

= -Z p{x)\og^p{x)

2,855.

Таблица

2.4.

Промежуточные значения вычисления энтропии для кода Хаффмена

Символ

хг

х^

Х5

Хб

х%

Кодовая

комбинация

000

001

010

011

110

1110

1111

Длина кодовой

комбинации (w,)

riipix)

0.38

0.48

0.45

0.36

0.33

0.36

0.08

- p{x)\og2p(x)

0.455

0.423

0.411

0.367

0.350

0.313

0.113 1

Минимальная длина кодовой комбинации выходного алфавита, необходимая для передачи

сообщения, составленного

из

символов входного алфавига, без потери информации:

HjX) _

2,855

log

log 2

= 2,855.

Коэффициент избьпх>чности

кода,

построенного по алгоритму Хаффмена, в соответствии с

(2.88) равен

п -п

К^

= —^

= 0,022,

т.

е.

построенный

код

практически избьпочности

не

имеет.

102

2.2.

Методы защиты

от

ошибок

сжатия

данных

Корневые

узлы

Листьевые

узлы

Рис.

2.16. Представление

части

словаря,

содержащего

строки:

А,

AN,

ANGEL,

AND,

В,

С,

СА,

CAR,

CACHE,

Наряду с рассмотренным алгоритмом Хаффмена, который требует допол-

нительного просмотра данных

для

вычисления значенийp(x.), существуют его

адаптивные модификации, позволяющие строить кодовое дерево «на ходу», по

мере поступления данных от источника.

Протоколы

сэюатия

MNP5 и

V.42bis.

В отличие от протокола MNP5 про-

токол V.42bis не заменяет конкретные, наиболее часто встречающиеся симво-

лы на более короткие кодовые слова, а делает это для последовательностей

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

встречающихся строк вместе с кодовыми словами, которые их представляют.

Словарь строится

модифицируется динамически. Размер словаря может быть

различным, стандартизировано только минимальное значение - 512 элементов

(строк). Конкретное значение выбирается обоими модемами

при

установлении

соединения. Кроме того, согласовывается максимальная длина строки, кото-

рая может быть сохранена в словаре, в диапазоне от 6 до 250 CHMBOJIOB.

Словарь может быть представлен как набор деревьев, в котором корню

каждого дерева соответствует символ алфавита и, наоборот, каждому симво-

лу соответствует дерево в словаре. Каждое дерево представляет набор извест-

ных (уже встретившихся) строк, начинающихся с символа, соответствующего

корню. Каждый узел дерева соответствует набору строк в словаре, а каждый

листьевой узел соответствует одной известной строке. Набор деревьев пред-

ставленный на рис. 2.16, представляет строки А, AN, ANGEL, AND, В, С, С А,

CAR, CACHE, D, Е. Каждый листьевой узел не имеет подчиненных узлов и

фактически соответствует последнему символу в строке. И наоборот, узел,

который не имеет родительского узла, соответствует первому символу в стро-

ке.

В самом начале каждое дерево

словаре состоит только из корневого узла.

103

Основы

телекоммуникации

которому присвоено уникальное кодовое слово. По мере поступления символов

из присоединенного к модему терминала, вьшолняется процедура отождеств-

ления накопленной (отождествленной)

предьщущему шагу строки и текуще-

го символа (string-matcMng ргоседш"е). Фактически эта процедура сводится к

поиску строки, дополненной текущим символом, в словаре. Она начинается с

единственного символа (и

этом случае всегда завершается успешно, так как

в словаре всегда есть односимвольные строки, соответствующие каждому

символу алфавита). Если отождествленная на предьщущем шаге строка плюс

символ соответствует элементу словаря (найдена в нем), и этот элемент не

бьш создан при предьщущем выполнении процедуры отождествления строки

(весьма

важное,

принципиальное и тонкое ограничение, позволяющее приемни-

ку поддерживать адекватное состояние словаря в некоторых частных случаях

комбинаций повторяющихся подстрок

во

входном

потоке),

строка

дополняется

текущим символом и будет использована при следующем вызове процедуры

отождествления. Процесс продолжается до тех пор, пока строка не достигнет

максимально возможной длины (согласованной модемами при установлении

соединения), либо дополненная строка не найдена в словаре, либо она была

найдена, но этот элемент бьш создан при предьщущем вызове. В этом случае,

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

ствленным» (unmatched), строка кодируется кодовым словом, а на следующем

шаге будет состоять только из неотождествленного символа. Во время про-

цесса сжатия словарь динамически дополняется новыми элементами (строка-

ми),

которые соответствуют подстрокам, встречающимся в потоке данных.

Новые строки образуются добавлением неотождествленного символа к суще-

ствующей строке, что означает создание нового узла дерева. Например, в слу-

чае,

если текущая отождествленная строка С4, а последнее переданное кодо-

вое слово соответствовало строке

AN^

появление символа Т приводит к

добавлению в словарь строки CAT (рис. 2.17). На следующем шаге текущая

строка соответствует неотождествленному символу Г.

Словари должны бьггь модифицированы в обоих модемах: на передающей

(передатчик) и принимающей (приемник) сторонах соединения. Важно пони-

мать, что передатчик всегда находится на один шаг (на одну строку) впереди

приемника в цикле модификации словаря. Таким образом, в принимающем

модеме первый символ принятого кодового слова (который будет

равен

С) дол-

жен быть

использован

для

модификации

словаря

приемника. Приемник V.42bis

всегда полагает, что первый символ каждой строки (соответствующей приня-

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

строки и создания нового элемента словаря. Состояние фрагмента словаря

приемника после приема кодового слова, соответствующего СА, при том, что

предьщущее кодовое слово соответствовало строке AN, показано на рис. 2.18.

При приеме приемником первого символа Т следующего кодового слова его

словарь будет иметь вид, изображенный на рис. 2.17.

104

2.2. Методы защиты от ошибок и сжатия данных

Корневые узлы

Рис.

2.17.

Изменения

части словаря передатчика

после

последовательного

получения от терминала символов

А,

С,

А и

Корневые узлы

Рис.

2.18.

Изменения

части словаря приемника

после

последовательного

получения

кодовых

слов,

соответствуюпщх строкам

AN и СА

В протоколе сжатия V.42bis реализованы и другие возможности. К наиболее

важным из которых относятся следующие.

Определен механизм удаления элементов словаря при его переполнении.

На понятийном уровне он заключается в том, чтобы после создания нового

элемента удалить самый «старый» (по времени создания) листьевой элемент

вне зависимости от частоты его использования. Кажущийся недостаток - не-

105

Основы

телекоммуникации

ВОЗМОЖНОСТЬ

учесть частоту появления подстрок и не удалять наиболее часто

встречающиеся - частично устраняется логикой дополнения словаря: если в

потоке данных часто встречаются подстроки, которые уже есть в словаре, то

новые элементы словаря создаются редко и словарь медленно переполняется.

Реализован механизм постепенного увеличершя длины кодового слова.

Для представления максимального номера элемента (строки) словаря требу-

ется 9 бит для словаря в 512 элементов, 10 - для словарей, содержащих до

1024 элементов, 11 - до 2048 элементов и т. д. Однако не все номера должны

быть представлены максимальным количеством бит, и этот механизм означа-

ет, что размер кодового слова увеличивается с 9 до максимального значения

по мере заполнения словаря. Это снижает накладные расходы на первоначаль-

ных этапах.

Существуют два режима работы передатчика: Прозрачный и режим Сжа-

тия.

Режим Сжатия описан выше. Прозрачный режим отличается от него тем,

что передача кодовых слов не осуществляется, а каждый приходящий на вход

передатчика символ транслируется в линию и далее в приемник. Если на вход

передатчика поступают хорошо перемешанный (в статистическом смысле)

поток символов, то высока вероятность, что каждый следующий символ будет

«неотождествленным» (такая же ситуация складывается сразу после ишпща-

лизации словаря - он еще пуст). На каждый принятый и «неотождествленный»

символ на выход передается кодовое слово. Длина символа, как правило, 8 бит

(здесь и далее предполагается, что символы представляют из себя октеты,

хотя стандарт и допускает реализацию на нетрадиционных аппаратных сред-

ствах),

минимальная длина кодового слова - 9 бит. В этом случа эффектив-

ность сжатия будет отрицательной, и потери могут составлять десятки про-

центов.

Сравнивая качественные и количественные характеристики протоколов сжа-

тия V.42bis и Microcom MNP5, следует отметить, что оба алгоритма использу-

ют адаптивную технологию

замеш>1

определенной входной последовательнос-

ти на выходную битовую последовательность. Протокол V.42bis кодирует

последовательность символов кодовым словом постепенно нарастающего и

всегда большего, чем длина символа, размера. Протокол MNP5 устраняет длин-

ные последовательности одинаковых символов конструкцией со счетчиком по-

вторения и затем кодирует отдельные символы в соответствии с частотой их

повторения кодовыми словами переменной длины. Кодовые слова могут быть

короче длины символа для часто повторяющихся символов и длиннее в про-

тивном случае. Этот протокол не определяет Прозрачного режима, и следова-

тельно возможны ситуации, приводящие к значительному расширению выход-

ного потока. В случае корректной реализации V.42bis это практически

невозможно, кроме того, V.42bis поддерживает возможность переинициализа-

ции словарей, что позволяет алгоритму лучше адаптироваться к хорошо пере-

106

2.3.

Методы и

технологии

передачи

данных

мешанному потоку. Несомненным преимуществом протокола V.42bis является

возможность параметризации протокола, что позволяет создавать более гиб-

кие реализащш.

Реальное сжатие по протоколу V.42bis на 20...30 % эффективнее, чем сжа-

тие по MNP5 и на

5...

% эффективнее, чем по MNP7.

2.3.

Методы и технологии передачи данных

Виды связи и режимы передачи данных

При передаче данных между двумя взаимодействующими объектами воз-

можны три вида связи:

симплексный - используется, когда передача данных должна осуществлять-

ся только в одном направлении, например в системах контроля, в которых ин-

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

промежутки времени;

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

тят обмениваться информащ1ей поочередно,

т.е.

канал используется поочередно

для передачи данных в обоих направлениях. Ясно, в таком режиме каждый

объект должен иметь возможность переключаться от состояния передачи к

состоянию приема;

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

дейст-вующими объектами (устройствами) в обоих направлениях одновременно,

например, когда пропускная способность канала позволяет потоку данных осу-

ществляться в обоих направлениях независимо.

При обмене данными на физическом уровне единицей информации является

бит, поэтому средства физического уровня всегда поддерживают побитовую

синхронизацию между приемником и передатчиком. Чтобы приемник мог пра-

вильно декодировать и интерпретировать получаемый набор битов, он должен

знать:

скорость передачи битов, определяемую интервалом времени, вьщеляемым

на один битовый разряд;

начало и конец каждого элемента (символа или байта);

начало и конец каждого полного блока сообщения или кадра.

Эти три фактора называют соответственно побитной или тактовой синхро-

низацией, побайтной или посимвольной синхронизацией и поблочной или покад-

ровой синхронизацией.

Канальный уровень оперирует кадрами данных и обеспечивает синхрониза-

цию между приемником и передатчиком на уровне кадров. В обязанности при-

емника входит распознавание начала первого байта кадра, границ полей кадра

и признака окончания кадра. Обычно достаточно обеспечить синхронизацию

на указанных двух уровнях - битовом и кадровом, - чтобы передатчик и при-

емник обеспечили устойчивый обмен информацией. Однако при плохом каче-

стве линии связи (как правило это относится к телефонным коммутируемым

107

Основы телекоммуникации

Направление передачи

8-битный

символ

у"

Младший бит

Приемник

обнаруживает

начало нового

символа

10 01010 О

С>

Время

Стартовый бит

1,5 или 2 стоп-бита

обеспечивают отрицательный

фронт в начале каждого нового

символа

Рис.

2.19.

Асинхронная передача

каналам) для

удешевления аппаратуры

повьппения надежности передачи дан-

ных

вводят дополнительные средства синхронизации на уровне

байт.

Такой

ре-

жим работы называется

асинхронным

или

старт-стопным.

Использование

такого режима работы обусловлено наличием устройств, которые генерируют

байты данных в случайные моменты времени. Так работает клавиатура дисп-

лея или другого терминального устройства, с которого человек вводит данные

для обработки их компьютером.

В асинхронном режиме каждый байт данных сопровождается специальны-

ми

сигналами «старт»-стартовый

бит и

«стоп»-стоповый(ые) бит(ы)

(рис.

2.19/

Назначение этих сигналов состоит в том, чтобы, во-первых, известить прием-

ник

приходе данных и, во-вторых, чтобы дать приемнику достаточно време-

ни для вьшолнения

некоторых

функций,

связанных

синхронизацией,

до

поступ-

ления следующего байта. Сигнал «старт» имеет продолжительность в один

тактовый интервал, а сигнал «стоп» может длиться один, полтора или два так-

та, поэтому говорят, что используется один, полтора или два бита в качестве

стопового сигнала,

хотя эти

сигналы

не

несут

информации.

Асинхронным

дан-

ный режим называют

потому,

что каждый байт может быть несколько смещен

во времени относительно побитовых тактов предьщущего байта. Такая асинх-

ронность передачи байт не влияет на корректность принимаемых данных, так

как в

начале каждого байта происходит дополнительная синхронизация прием-

ника с источником за счет стартового бита. Более «свободные» временные

допуски определяют

низкую

стоимость оборудования асинхронной системы.

При

синхронном

режиме передачи старт-стопные биты между каждой па-

рой байт отсутствуют

и весь

блок или

кадр

данных передается как одна цепоч-

ка битов без каких-либо задержек между

8-битными

элементами. Чтобы при-

емник обеспечивал различные

уровни

синхронизации,

необходимо вьпюлнение

следующих требований:

108

2.3.

Методы и технологии передачи данных

3 Направление передачи

Передаваемый кадр

Синхро- Старговый(ые)

байты или байт(ы) кадра

символы

простоя

Синхро-

Конечный(ые) байш или

байт(ы) кадра символы

простоя

Рис.

2.20.

Синхронная передача

• передаваемая цепочка битов должна быть закодирована так, чтобы при-

емник

мог

осуществлять побитовую синхронизацию;

• каждому кадру должен предшествовать один или более зарезервирован-

ных байтов или символов, благодаря чему приемник может надежно разде-

лить

полученную цепочку битов

по

границам байтов или символов (побайтная

или посимвольная синхронизация);

• содержимое каждого кадра обрамляется парой зарезервированных бай-

тов или символов.

Благодаря последнему требованию приемник оповещается о поступлении

кадра

данных

и об

окончании кадра

(рис.

2.20).

При

наличии промежутков вре-

мени между передачей двух последовательных кадров в этот период либо не-

прерывно передаются синхробайты бездействия

(простоя),

что позволяет

при-

емнику

поддерживать

побитную

или побайтную

синхронизацию,

либо

каждому

кадру

предшествует

один или несколько

специальных синхронизирующих бай-

тов

или

символов,

например

01111110,

что позволяет приемнику вновь войти в

байтовый синхронизм с передатчиком.

Для

обеспечения побитовой синхронизации используют самосинхронизиру-

ющиеся коды.

Методы передачи данных канального уровня

Канальный уровень обеспечивает передачу пакетов данных, поступающих

от

протоколов верхних

уровней,

узлу

назначения,

адрес которого также указы-

вает протокол верхнего

уровня.

Протоколы канального уровня оформляют пе-

реданные им пакеты в кадры собственного формата, помещая указанный ад-

рес назначения в одно из полей такого кадра, а также сопровождая кадр

контрольной

суммой.

Протокол канального уровня предназначен

для

доставки

109