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

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

Основы

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

Скрэмблирование. Перемешивание данных скрэмблером перед переда-

чей их в

линию

помощью потенциального

кода также

является одним

из

спо-

собов логического кодирования. Методы скрэмблирования заключаются в по-

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

полученных

предьщущих тактах бит результирующего

кода.

Например,

скрэм-

блер может реализовывать соотношение:

Л,

= ^,е5.зе5_з, (2.79)

где

В.

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

ты скрэмблера,

А.

- двоичная цифра исходного

кода,

поступающая на

/-м

такте

на

вход

скрэмблера;

В^^иВ^^-

двоичные цифры результирующего

кода,

полу-

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

и на 5

тактов ранее текущего

такта;

- операция исключающего ИЛИ (сложение по

mod2).

Например,

для исходной последовательности 110110000001 скрэмблер даст

следующий результирующий

код:

В^

А^

= I (первые три цифры результирующего кода будут совпадать с

исходным, так как на вход еще не поступили необходимые цифры)

5з = ^з = 0

В^

А^®В^--

В,=А,ФВ,-

= 1е

= 0

=10 1=0

= ^^ е 5з

5, = о

о е

= 1

В^

А^ФВ^®В^=ОФО®

= 1

В^=А^@В^®В^

= ОФО®0 = 0

л,

= ^,

Л^

5, = о

Ф 1 Ф

о = 1

5,„

^,„

5, = о

Ф 1 Ф

о = 1

5„=/Г„Ф5,Ф5, = 0Ф0Ф

= 1

5,2=^,2Ф5,Ф5,=

1Ф 1Ф

= 1

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

110001101111,

которой нет шести

нулей

подряд,

присутствовавших

исходном

коде.

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

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

нии обратного

соотношения:

В®В ,®В

=(А®В

,05 Лел , ФЛ =^ . (2.80)

Различные алгоритмы скрэмблирования отличаются количеством слагае-

мых,

которые определяют цифру результирующего

кода,

сдвигом между сла-

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

2.2.

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

от

ошибок

сжатия

данных

зуется преобразование со сдвигами 5 и 23 позиции, а при передаче данных от

абонента в сеть - со сдвигами 18 и 23 ПОЗРЩИИ.

Протоколы коррекции ошибок. Протоколы коррекции ошибок как пра-

вило сочетают применение циклического кодироваигая с решающей обратной

связью. Суть этого метода состоит в следующем. Вся «полезная» информа-

ция разбивается на «порции» - кадры. Передача каждого кадра завершается

передачей специальной контрольной последовательности кадра, подсчитанной

по некоему, заранее определенному алгоритму. Этот рекуррентный алгоритм в

процессе вьщачи кадра модифицирует контрольную последовательность с по-

мощью очередного вьщаваемого байта. Принимающая сторона также подсчи-

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

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

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

сравнения приемник решает, отсюда и название «решающая обратная связь»:

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

вопроса приемник сообщает передатчику посредством некоей

«квитанции».

Отсю-

да другое название метода: «метод автоматического повтора запроса» (ARQ -

Automatic Repeat reQuest).

Основную роль в обнаружении ошибок играет алгоритм вычисления конт-

рольной последовательности кадра. Здесь использован метод циклического из-

быточного контроля (CRC - Cyclic Кес1ш1(1апсу Check), определяющее свой-

ство которого - простота кодирования: рекуррентный характер алгоритма при

минимальном расходе вычислительных

ресурсов.

Существуют по крайней мере

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

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

аппаратном уровне с помопц>ю сдвигового регистра) и байтово-табличный, в

котором модификация результата проводится после приема/передачи целого

байта (этот алгоритм больше подходит для реализации на программном уров-

не,

поскольку требует некоторого объема памяти для хранения таблиц).

Принципы циклического помехоустойчивого кодирования с решающей об-

ратной связью положены в основу всех аппаратных и программных реализаций

наиболее широко распространенных протоколов коррекции ошибок фирмы

Microcom MNP2/MNP3 и V.42 ITU-T.

Появление протоколов фирмы Microcom предшествовало выходу «Синей

Книги» ITU-T с Рекомендацией

V.42,

в которой обобщены все достижения про-

мьшшенных стандартов в этой

области.

Протоколы MNP (Microcom Networking

Protocol) - MNP2 и MNP3 являются соответственно байт-ориентированным и

бит-ориентированным протоколами.

Протокол коррекции ошибок определяет формат кадра, перечень допусти-

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

протокол,

т.

е. порядок установки режима коррекции ошибок, выхода из режима

и допустимого чередования кадров.

Основы

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

Протоколы

MNP2 и MNP3. Протокол коррекции ошибок MNP2 представ-

ляет

собой

асинхронный байт-ориентированный

протокол.

Каждый элемент кадра

- байт - состоит из 8 информационных бит и передается по каналу последова-

тельно, начиная с младшего бита; выдача первого бита предваряется старто-

вым

битом,

служащим синхросигналом

приемнику;

после передачи последнего

бита вьщается стоповый бит. Если следующий байт не готов к выдаче в ли-

нию,

то

осуществляется передача потока стоповых

битов.

Таким образом, мож-

но считать, что байт состоит как минимум из 10 бит, включая один стартовый

и один стоповый биты. Отсюда вытекает два важных следствия. Во-первых,

процедура входа

протокол прозрачна

не требует специального синхронного

переключения обоих модемов

какой-то специфический

режим

работы асинх-

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

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

MNP2,

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

вать.

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

граммного обеспечения компьютера.

Формат кадра MNP2 имеет следующий вид:

управляющее поле начального флага, включающее три байта: SYN, DLE и

STX (16h, lOh, 02h - 16-ричные коды указанных байт);

прозрачные пользовательские данные переменной длины;

управляющее поле конечного флага, включающее 2 байта: DLE и ЕТХ (lOh,

03h);

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

мощью образующего полинома

х^^

х^

+ 1.

Кодовая прозрачность управляющих полей обеспечивается байтом DLE,

сигнализирующим о специальном значении следующего за

ним

байта. Если же

этот байт встречается

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

ся,

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

дуру вставки байта DLE в пользовательские данные называют байтстаф-

фиигом).

Поскольку протокол MNP2 - байт-ориентированный, в нем нет

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

тель - поток стоповых битов. В протоколе MNP2 существуют 6 типов кадров:

LR, LD, LT, LA, LN и LNA. Каждый тип кадра в поле прозрачных пользова-

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

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

тельская информация.

Протокол коррекции ошибок MNP3 представляет собой синхронный бит-

ориентированный

протокол.

Его кадровый

формат

радикальным образом отли-

чается от MNP2 и полностью соответствует основной части Рекомендации

V.42,

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

товой контрольной последовательности кадра с точностью до образующего

полинома, обеспечение прозрачности

данньпс и

межкадровый заполнитель. Все

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

протокол - полностью идентично протоколу MNP2.

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

Несмотря на снижение накладных расходов, обусловленное переходом на

синхронный кадровый формат, MNP3 не дает экономии вычислительных ре-

сурсов по причине того, что процедура входа

протокол

MNP3

заключается в

обмене сторонами кадрами

LR в

байт-ориентированном

режиме.

Только согла-

совав с помощью этого кадра применение в дальнейшем бит-ориентирован-

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

вычислительные процедуры, присущие MNP2 (формирование кадра специфи-

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

по

специфичес-

кому образующему

полиному,

байтстаффинг

и пр.)

необходимо реализовывать

для установки протокола MNP3.

Протокол

V.42.

Протокол коррекции ошибок

V.42

является подмножеством,

называемым LAPM (Link Access Procedm-e for Modems), бит-ориентирован-

ных протоколов типа

HDLC

(High-level Data Link

Control).

отличие от асинх-

ронного кадрового формата MNP2 формат кадра LAPM синхронный.

Кадр LAPM состоит из нескольких полей, каждое из которых включает це-

лое число байт. Все байты в кадре передаются последовательно друг за дру-

гом без служебных битов: вслед за старшим битом предьщущего байта пере-

дается младший бит следующего. Все кадры начинаются и закаьгчиваются

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

ницами

подряд,

окаймленными нулями (01111110,7Eh). Кодовая прозрачность

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

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

(битстаффинг).

Межкад-

ровым

заполнителем служит флаговая

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

Завершающий флаг

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

Таким образом, обнаружение флага в потоке данньпс говорит приемнику об

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

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

кадра.

Формат кадра LAPM имеет следующий вид:

• начальный флаг (7Eh);

• поле адреса;

• управляющее поле;

• информационное

поле;

• двухбайтовая или 4-байтовая контрольная последовательность кадра;

• конечный флаг (7Eh).

Управляющее поле кадра идентифицирует один из трех форматов кадра.

Информационные кадры

(/-формат)

предназначены для передачи информации

возможностью одновременного подтверждения принятой

информации,

супер-

визорные кадры

(^-формат)

для

подтверждения принятой информации, зап-

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

ему, а ненумерованные кадры

(^/-формат)

выполняют дополнительные

управляющие сеансом процедуры,

такие,

как:

установка/прекращение работы

протокола, согласование параметров

протокола,

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

пр.

Всего

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

типов кадров:

Основы

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

ТИП

кадра /-формата;

4 типа кадра

А^-формата:

RR, RNR, REJ и SREJ;

8 типов кадров U-формата: SABME, DM, UI, DISC, UA, FRMR, XID и TEST.

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

помощью образующего полинома

х^^

л:^^

дс^

+ 1, отличного от того, который

используется

протоколе

MNP2.

Четырехбайтовая контрольная последователь-

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

х^^

л:^^

х^^

л:^^

х'^

л:^^

х^""

х""

+ х' +

х^

+ х+ \,

Выбор CRC-16 или CRC-32 проводится в процессе согласования парамет-

ров протокола с помощью кадров XID.

Вход в протокол - операция ответственная и потому ее необходимо тща-

тельно планировать. Вызывающий модем начинает установку протокола не-

прерывной передачей своему оппоненту двухбайтовых «шаблонов обнаруже-

ния

вызьгоающего»

(ODP

Originator

Detection Pattern)

байт-ориентированном

режиме, соответствующем Рекомендации V.14 ITU-T. ODP состоит из байтов

11Л

и 91

А,

разделенных 8-16 стоповыми битами. Отвечающий модем, приняв

подряд два ODP, начинает выдавать «шаблоны обнаружения отвечающего»

(ADP - Answerer Detection Pattern) в том же байт-ориентированном режиме.

ADP состоит из байтов 45Л ('Е') и 43Л ('С*), разделенных 8-16 стоповыми

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

хронный режим. Вызывающий модем, приняв подряд два ADP, прекращает

передачу ODP и переключается

синхронный режим. Выдача первого кадра в

синхронном режиме предваряется

как

минимум 16 флаговыми последователь-

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

реключения обоих сторон

синхронный

режим.

Первым кадром, как правило,

является кадр XID, с помощью которого стороны согласуют параметры прото-

кола

коррекции ошибок

сжатия.

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

щим трем критериям:

Минимизация накладных расходов. Совокупное преимущество V.42 по

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

MNP3 и

V.42

перед

MNP2,

обусловленное переходом

на

синхронный кадровый

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

по крайней мере на 20

вследствие отказа от передачи стартовьпс и стоповых

битов.

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

байт-ориентированном режи-

ме приводит к увеличению объема передаваемых данных на 100

в худшем

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

Для синхронного кадрового формата худший случай заключается в том, что

пользовательская информация состоит из одних единиц (байтов

FFh),

что при-

водит к увеличению объема передаваемых данньпс лишь на 20 % - вставки

дополнительного

нуля

после каждых

пяти

единиц.

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

сэ1сатия

данных

Накладные расходы

на

передачу пользовательской информащш посредством

кадра I протокола V.42, обусловленные структурой кадра, составляют 6 байт.

Аналогичные накладные расходы для кадров LT, осуществляющих передачу

пользовательской информащш, для протокола MNP3 составляют 8 байт, а для

протокола MNP2 - 12 байт.

При

двусторонней передаче информащш протоколы MNP будут

либо

откла-

дывать подтверждение принятой информащш, неоправданно «загромождая»

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

дут вьшуждены чередовать передачу пользовательской информащш с подтвер-

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

на 11 байт для MNP3 и на 15 байт для MNP2 (длина кадра LA). Кадр I прото-

кола V.42 в самой своей структуре несет функщпо подтверждения принятой

информащш и потому дополнительных накладных расходов не требует.

Надежность входа в протокол. Процедура входа в любой из протоколов

MNP заключается в обмене взаимодействующими сторонами кадрами LR в

байт-ориентированном режиме. Переключение в синхронный кадровый фор-

мат протокола MNP3 проводится только после вьщачи иншщатором кадра LA

(и,

соответственно, его приема отвечающим), подтверждающего прием ответ-

ного кадра LR. Длина кадра LR составляет 31 байт, а кадра LA - 15 байт.

Таким образом, установка протокола обусловлена безошибочным приемом 31

байт отвечающим модемом, затем 31 байт вызывающим модемом и, наконец,

15 байт вновь отвечающим модемом. В то время, как для установки протоко-

ла LAPM необходимо безошибочно передать всего лишь по 4 байт в каждую

сторону - по 2 ODP/ADP соответственно. Впрочем, эти 4 байт должны пере-

межаться потоком стоповых бит длиной в среднем в 1,5 байт. Поэтому для

корректности надо говорить о 10 байт. Очевидно, что при наличии помех (в

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

протоколе просто нет нужды) вероятность безошибочного

приема 10 байт значительно вьппе, чем 31 байт и, тем более, 46 байт.

Кроме того, поток ODP/ADP включает в себя не менее 10 шаблонов, т. е.

каждая пара повторяется не менее 5 раз. В то время, как в случае неудачи

приема кадра LR какой-либо из сторон, обмен этими кадрами будет повторен

по истечении тайм-^та лишь однажды (в некоторьк реализациях дважды).

Превосходство в кратности повтора процедуры еще более увеличивает разни-

цу в

вероятностях успешного входа

протокол коррекции ошибок, подчеркивая

преимущество протокола LAPM над MNP.

Гибкость. Гибкость подразумевает следующие возможности протокола:

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

кадра и размер окна - для обеих сторон. Размер окна определяет количество

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

дая их подтверждения. Оба параметра зависят от размеров оперативной памя-

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

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

редачи согласуются свои значения этих параметров. В протоколе MNP в

Основы

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

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

для передачи в обе стороны;

• кадр ХШ протокола LAPM, с помощью которого проводится согласование

параметров, позволяет модемам обмениваться дополнительной информацией,

такой, как «ID (идентификатор) изготовителя». Это предоставляет возможность

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

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

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

рехбайтовой контрольной последовательности кадра (CRC-32) в особо ответ-

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

ми.

Поддержка этой возможности необязательна;

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

подтверждения принятых данных;

• селективный повтор одного неверно принятого кадра. Реализация этой воз-

можности (тип кадра SREJ) необязательна;

• кадр

[/-формата

TEST позволяет в любой момент, не прекращая передачу

пользовательской информации, осуществить кольцевое тестирование канала

передачи даьшых. Поддержка этой возможности необязательна;

• пересогласование параметров передачи в любой момент времени после

установки протокола. Модем может инициировать пересогласование парамет-

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

ренних критериев. Например, посчитав, что качество канала связи ухудшилось,

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

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

CRC-32. MNP позволяет согласовывать параметры единожды, при входе в про-

токол.

Протокол LAPM содержит задел для его расширения в будущем. В частно-

сти,

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

единения.

Сжатие данных. Сжатие (компрессия) данных применяют для сокраще-

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

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

раты времени на разворачивание этих данных принимающей стороной, то

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

заметны только для низкоскоростных каналов (около 64 кбит/с). Многие про-

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

компрессию, совмещенную с передачей

данных.

Статическая компрессия обес-

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

архиваторов типа АЮ, RAR, WinZip), после чего они отсьшаются в сеть.

Существующие алгоритмы сжатия информации можно разделить на две

большие группы:

алгоритмы сжатия без

потерь:

алгоритм Лемпеля-Зива (Lempel-Ziv,

LZ),

RLE

(Rmi Length Encoding), кодирование Хаффмена (Huffinan Encoding);

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

сэюатия

данных

алгоритмы сжатия с потерями: JPEG (Joint Photographic Expert Group), M-

JPEG, MPEG (Motion Picture Expert Group).

Алгоритм Лемпеля-Зива лежит

основе архиваторов (pkzip,

arj,

Iha) и про-

грамм динамического сжатия дисков (Stacker, DoubleSpace). Основная идея

этого алгоритма состоит

том, что второе и последующие вхождения некото-

рой

строки символов

сообщение заменяются

ссылкой на

ее первое появление

в сообщении. Алгоритм используется для сжатия текстов и графики.

Алгоритм сжатия без потерь RLE применяют для сжатия графики (файлы

формата PCX) и видео. Непрерывная последовательность одинаковых симво-

лов заменяется 2 байтами. В первом байте - символ, во втором - счетчик, т. е.

число, которое показьгоает, сколько таких символов идет подряд.

Кодирование Хаффмена состоит

замене информационных символов кодо-

выми последовательностями различной длины. Чем чаще используется сим-

вол,

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

Алгоритм сжатия с потерями JPEG ориентирован на сжатие неподвижных

изображений.

Он

базируется на дискретном косинусном преобразовании (ДКП)

неподвижного изображения, отбрасывании

малых

высокочастотных компонен-

тов

получаемого спектра

последующем энтропийном сжатии полученных

дан-

ных.

Алгоритм

М-JPEG

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

отдельный кадр сжимается по методу JPEG.

Алгоритм MPEG ориентирован

на

обработку

видео.

При формировании по-

тока данных исходят

из

предположения о том, что два соседних кадра

видео-

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

JPEG и

передают относительно

редко.

В основном передаются изменения меж-

ду соседними кадрами.

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

да:

нет алгоритма, одинаково эффективного

для

данных разной природы;

приведенные алгоритмы рассчитаны

на

сжатие данных,

которых есть пос-

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

других.

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

меним к определенному типу данных. Некоторые модемы (называемые ин-

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

сжатие^

при котором в зависи-

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

Рассмотрим некоторые общие алгоритмы сжатия данных.

Десятичная упаковка. Когда данные состоят только из чисел, значитель-

ную экономию можно получить путем уменьшения количества используемых

на Щ1фру бит с 7 до 4, используя простое двоичное кодирование десятичных

Ш1фр вместо кода ASCII. Просмотр таблицы ASCII показывает, что старшие

три бита всех кодов десятичных

Щ1фр

содержат комбинащпо

011.

Если все дан-

ные

кадре информащш состоят из десятичных

Щ1фр

то, поместив в заголовок

Основы

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

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

длину кадра.

Относительное

кодирование.

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

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

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

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

рассмотренного выше метода импульсно-кодовой модуляции. При дифферен-

циальной (разностной) ИКМ (ДИКМ, Differencial PCM, DPCM) вместо коди-

рования отсчетов кодируются разности между соседними отсчетами. Обычно

разности отсчетов меньше самих отсчетов. Адаптивная ДИКМ (АДИКМ,

Adaptive Differencial PCM, ADPCM) - система ДИКМ с адаптацией квантова-

теля (АЦП и ЦАП) и предсказателя. При АДИКМ оцифровывается не сам

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

Символьное подавление. Часто передаваемые данные содержат большое

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

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

значений,

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

ство байт, состоящих из всех единиц. Передатчик сканирует последователь-

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

или

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

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

так-

же отмечает

начало этой

последовательности специальным управляющим сим-

волом.

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

факт, что не все символы в передаваемом кадре встречаются с одинаковой

частотой. Поэтому во многих схемах кодирования коды часто встречающихся

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

большей длины. Такое кодирование называется также

статистическим

ко-

дированием.

Одним

из

наиболее распространенных алгоритмов, на основе которых стро-

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

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

Рассмотрим его подробнее, предварительно определив критерий оценки эф-

фективности кодирования.

Эффективное кодирование. Избыточность является одной из основных

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

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

зи требуется больше времени, кроме того, они занимают больший объем

памяти при

хранешш информации. Большая избыточность не всегда оправдана

требованиями помехоустойчивости

при

передаче

хранении информации. По-

этому возникает задача устранения избыточности, получившая название эф-

фективного кодирования.

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

Определим

А^= {JCJ,

jc^,...,

JC^}

- входной алфавит кода Г\ множество В - вы-

ходной алфавит того же кода: 5 = {О, 1, ..., m - 1}, где т - число элементов

множества В, Код Г сопоставляет каждому символу из входного алфавита

X е л;'кодовую комбинацию, составленную из п символов алфавита В- Гх =

= ь,ь,...ъ„,.

Требуется оценить минимальную среднюю длину кодовой комбинации.

Обозначим через/7(л:.) вероятность появления сообщения

л:.,

тогда энтропия

сообщений А^=

{х^^х^^

-^^ху,

H(X)=^-±p{x)logp(x), (2.81)

I =1

а средняя длина кодовой комбинации:

^t'^,/^^.)-

(2.82)

^ /=1

Максимальная энтропия, которую может иметь сообщение из символов ал-

фавита В равно

^nax = «cpl0g/W. (2.83)

Для обеспечения передачи информации, содержащейся в сообщениях X, с

помопц>ю кодовых комбинаций

алфавите

должно вьшолняться неравенство

Я«ах>Я(^. (2.84)

В случае строгого неравенства

Д„ах

> Щ^ имеет место избыточность, ко-

торую определяют через коэффициент избыточности

К^^

Ли 77 • U-85)

-'''max

Оценим

минимальную среднюю длину

кодовой

комбинации,

при которой еще

возможна передача сообщения А'без потери информации. Учитывая (2.83) и

(2.84),

получим:

«ер > -^ , (2.86)

logm

т. е.

«mi„= -^. (2.87)

logm

Выражение (2.85) для коэффициента избьггочности с учетом (2.87) можно

представить в следующем виде:

п - « .

К^ = -^ — . (2.88)

ср