Эффективное кодирование - Техника передачи дискретных сообщений
Эффективное кодирование - это процедуры направленные на устранение избыточности.
Основная задача эффективного кодирования: обеспечить, в среднем, минимальное число двоичных элементов на передачу сообщения источника. В этом случае, при заданной скорости модуляции обеспечивается передача максимального числа сообщений, а значит максимальная скорости передачи информации.
Пусть имеется источник дискретных сообщений, алфавит которого K.
При кодировании сообщений данного источника двоичным, равномерным кодом, потребуется
Двоичных элементов на кодирование каждого сообщения.
Если вероятности P(aI) появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равна
В данном случае каждое сообщение источника имеет информационную емкость бит, и очевидно, что для его кодирования (перевозки) требуется двоичная комбинация не менее элементов. Каждый двоичный элемент, в этом случае, будет переносить 1 бит информации.
Если при том же объеме алфавита сообщения не равновероятны, то, как известно, энтропия источника будет
.
Если и в этом случае использовать для перевозки сообщения lР. к. - разрядные кодовые комбинации, то на каждый двоичный элемент кодовой комбинации будет приходиться меньше чем 1 бит.
Появляется избыточность, которая может быть определена по следующей формуле:
,
Где D - избыточность.
Если средняя загрузка единичного элемента так мала, встает вопрос, нельзя ли уменьшить среднее количество элементов необходимых для переноса одного сообщения и как наиболее эффективно это сделать?
Для решения этой задачи используются неравномерные коды.
При этом, для передачи сообщения, содержащего большее количество информации, выбирают более длинную кодовую комбинацию, а для передачи сообщения с малым объемом информации используют короткие кодовые комбинации.
Учитывая, что объем информации, содержащейся в сообщении, определяется вероятностью появления
,
Можно перефразировать данное высказывание.
Для сообщения, имеющего высокую вероятность появления, выбирается более короткая комбинация и наоборот, редко встречающееся сообщение кодируется длинной комбинацией.
Таким образом, на одно сообщение будет затрачено в среднем меньшее единичных элементов
,
Чем при равномерном.
Если скорость телеграфирования постоянна, то на передачу одного сообщения будет затрачено в среднем меньше времени:
А значит, при той же скорости телеграфирования будет передаваться большее число сообщений в единицу времени, чем при равномерном кодировании, т. е. обеспечивается большая скорость передачи информации.
Каково же в среднем минимальное количество единичных элементов требуется для передачи сообщений данного источника?
Ответ на этот вопрос дал Шеннон.
Шеннон показал, что
- 1. Нельзя закодировать сообщение двоичным кодом так, что бы средняя длина кодового слова была численно меньше величины энтропии источника сообщений. 2. Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника
.
Остается выбрать подходящий способ кодирования.
Эффективность применения оптимальных неравномерных кодов может быть оценена:
- 1. Коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных элементов на сообщение, при применении методов эффективного кодирования в сравнении с равномерны 2. Коэффициент относительной эффективности. Позволяет сравнить эффективность применения различных методов эффективного кодирования.
В неравномерных кодах возникает проблема разделения кодовых комбинаций. Решение данной проблемы обеспечивается применением префиксных кодов.
Префиксным называют код, для которого никакое более короткое слово не является началом другого более длинного слова кода. Префиксные коды всегда однозначно декодируемы.
Введем понятие кодового дерева для множества кодовых слов.
Наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного кодового дерева изображен на рисунке. 3.2.1.
Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между "0" и "1" в качестве первого символа кодового слова: левая ветвь соответствует "0", а правая - "1". Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает "0", а правая - "1" и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.
Рис. 3.2.1
Формально кодовые слова могут быть приписаны также промежуточным узлам. Например, промежуточному узлу второго порядка на рис.3.2.1 можно приписать кодовое слово 11, которое соответствует первым двум символам кодовых слов, соответствующих концевым узлам, порождаемых этим узлом. Однако кодовые слова, соответствующие промежуточным узлам, не могут быть использованы для представления сообщений, так как в этом случае нарушается требование префиксности кода.
Требование, чтобы только концевые узлы сопоставлялись сообщениям, эквивалентно условию, чтобы ни одно из кодовых слов не совпало с началом (префиксом) более длинного кодового слова.
Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного кодового дерева, является префиксным, т. е. однозначно декодируемым.
Одним из часто используемых методов эффективного кодирования является так называемый Код Хаффмана.
Пусть сообщения входного алфавита A{a1,a2,a3...aK} имеют соответственно вероятности их появления p1,p2,p3...pK.
Тогда алгоритм кодирования Хаффмана состоит в следующем:
- 1. Сообщения располагаются в столбец в порядке убывания вероятности их появления. 2. Два самых маловероятных сообщения объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообщений aK-1, aK т. е. pK-1+pK. В результате получим сообщения a1,a2,a3...aK-1,b, вероятности которых p1, p2, p3...pK-2, pK-1+ pK. 3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1. 4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно
Определить, приписывая правым ветвям объединения символ "1", а левым - "0". Впрочем, понятия "правые" и "левые" ветви в данном случае относительны (Рис. 3.2.2).
На основании полученной таблицы можно построить кодовое дерево рисунок 3.2.3:
Рис. 3.2.3
Так как в процессе кодирования сообщениям сопоставляются только концевые узлы, полученный код является префиксным, и всегда однозначно декодируем.
При равномерных кодах одиночная ошибка в кодовой комбинации приводит к неправильному декодированию только этой комбинации. Одним из серьезных недостатков префиксных кодов является появление трека ошибок, т. е. одиночная ошибка в кодовой комбинации, при определенных обстоятельствах, способна привести к неправильному декодированию не только данной, но и нескольких последующих кодовых комбинаций.
Еще одним методом кодирования является Арифметическое кодирование.
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т. к. достигается теоретическая граница степени сжатия. Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0,1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке. Поясним работу метода на примере.
Математически процесс описывается следующим образом:
Кодирование:
- 1. Границы рабочего интервала D0 и U0 изначально равны 0 и 1 соответственно. Длина рабочего интервала У0=1. 2. Определяем нижнюю границу рабочего интервала (т. е. границы первого закодированного сообщения):
DI= dI-1+ QI-уI-1.
И верхнюю границу:
UI= dI-1+ QI уI-1, где QI
- - граница кодируемого сообщения на начальном интервале. А так же определяем длину нового рабочего интервала УI= UI - dI. Далее кодируем все последующие сообщения подобным образом. 3. Определяем середину конечного рабочего интервала
,
Где AN - число архив, UN, DN - верхняя и нижняя границы конечного рабочего интервала соответственно.
Декодирование:
- 1. Первое закодированное сообщение "лежит" на интервале, в который входит число архив. 2. Последующие числа архивы определяются как:
, где AJ
- новое число архив, AJ-1 - предыдущее число архив, QJ-1 - нижняя граница декодированного сообщения, P(aI) - вероятность этого сообщения.
Графически метод арифметического кодирования представлен на рисунке 3.3.1.
Рис. 3.3.1
Похожие статьи
-
Кодирование в системах ПДС, Классификация кодов - Техника передачи дискретных сообщений
Классификация кодов Эффективное кодирование - это процедуры направленные на устранение избыточности (т. е. минимизировать количество элементов,...
-
Эффективное кодирование - Основы построения телекоммуникационных систем и сетей
Эффективное кодирование - это процедуры направленные на устранение избыточности. Основная задача эффективного кодирования: обеспечить, в среднем,...
-
Формирование кодовой комбинации циклического кода (Задачи) - Техника передачи дискретных сообщений
3.4.1 Записать кодовую комбинацию циклического кода, если задан производящий полином P(х) = x3+x2+1 и кодовая комбинация, поступающая от источника...
-
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ - Расчет параметров системы передачи дискретных сообщений
В связи с тем, что при приеме сообщений необходимо обеспечить вероятность ошибки не более 10-6 , используются помехоустойчивые коды, исправляющая и...
-
Теоретические основы Сигнал, поступающий с выхода канала постоянного тока (КПТ), должен быть отождествлен на приемной стороне с "0" или "1". Необходимо...
-
Рис. 4.2.1. Временная диаграмма работы системы с РОС-ОЖ Расчет параметров систем с ОС и ожиданием 4.3.1 Построить временные диаграммы для системы с...
-
Для передачи непрерывных сообщений можно воспользоваться дискретным каналом. При этом необходимо преобразовать непрерывное сообщение в цифровой сигнал,...
-
1. Шаг коррекции ( Дц ) - смещение фазы ТИ в долях единичного интервала ( Ф 0 ) на выходе делителя частоты (ДЧ) при добавлении или вычитании одного...
-
Классификация систем синхронизации Синхронизация есть процесс установления и поддержания определенных временных соотношений между двумя и более...
-
Дискретизатор преобразует сообщение в последовательность отсчетов, взятых с интервалом по времени At. Затем каждый отсчет квантуется по уровню...
-
ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК В СООБЩЕНИЯХ - Теория и практика информации и кодирования
Задача 4 1. Чему равно кодовое расстояние между комбинацией 10010111 и комбинациями 11111111, 00000000, 00010111? Решение Для того чтобы определить...
-
Циклические коды - Техника передачи дискретных сообщений
Широкое распространение получил класс линейных кодов которые называются циклическими. Название этих кодов происходит от их основного свойства: если...
-
Данные передача сигнал сообщение Для обеспечения заданной достоверности при передаче данных применяют обратные связи и помехоустойчивое кодирование,...
-
В качестве основного параметра, характеризующего канал связи, используется вероятность ошибки р в зависимости от отношения h средних мощностей сигнала Wс...
-
Задача8 Чему равна пропускная способность канала связи, описанного следующей матрицей: ? Решение Найдем безусловные вероятности источника и приемника:...
-
Задача 3 Можно ли назвать полным информационное описание канала связи, предоставленного матрицей вида? Решение Для полного и всестороннего описания...
-
Для определения необходимого числа каналов на участках между проектируемой станцией и заданными узлами связи дороги воспользуемся номограммой. Процент...
-
При расчетах каналов и оборудования телеграфных станций сети ПС необходимо учитывать не только нагрузку по передаче и приему телеграмм, но и нагрузку в...
-
2.4.1 Коэффициент нестабильности задающего генератора устройства синхронизации и передатчика k=10-4. Исправляющая способность приемника µ=52%. Краевые...
-
При организации самостоятельной сети АТ нагрузку каналов в ЧНН между проектируемой и i-й станциями можно представить в следующем виде, Эрл , (23) Общий...
-
Системы ПДС с ОС, Классификация систем с ОС - Техника передачи дискретных сообщений
Классификация систем с ОС В системах с ОС ввод в передаваемую информацию избыточности производится с учетом состояния дискретного канала. С ухудшением...
-
Заключение, Литература - Передача дискретных сообщений
В ходе выполнения данной курсовой работы был проведен расчет нагрузки станции абонентского телеграфирования, потока телеграфного обмена по системе прямых...
-
Основным типом каналов телеграфной связи на железнодорожном транспорте являются каналы тонального телеграфирования. Они могут быть организованы по...
-
Время доставки сообщения Тд получателю складывается из времени установления цикловой tцc синхронизации, времени передачи сообщения tпр, времени...
-
ПОВЫШЕНИЕ ВЕРНОСТИ ПРИНИМАЕМЫХ СООБЩЕНИЙ - Расчет параметров системы передачи дискретных сообщений
Существуют два метода повышения верности принимаемых сообщений. Первый метод основан на улучшении качественных показателей каналов, что достигается...
-
Расчет количества резервных каналов связи по направлениям - Передача дискретных сообщений
Коэффициент готовности пучка каналов связи определяется по формуле (если каждого канала по направлению равны) , (34) Где - количество каналов в пучке...
-
Коэффициенты неравномерности и прироста телеграфной нагрузки - Передача дискретных сообщений
Одной из основных особенностей телеграфной связи является неравномерность поступления сообщений, которая обусловлена графиком движения поездов, дневной...
-
ЛИТЕРАТУРА - Расчет параметров системы передачи дискретных сообщений
Передача дискретных сообщений: учебник для вузов/Под ред. Б. П. Шувалова. М.: Радио и связь, 1990. Чернега B. C. и др. Расчет и проектирование...
-
ВВЕДЕНИЕ - Расчет параметров системы передачи дискретных сообщений
Электросвязь - это совокупность человеческой деятельности, главным образом технической, связанной с передачей сообщений на расстояние с помощью...
-
Заключение, Список литературы - Техника передачи дискретных сообщений
В данной курсовой работе рассматривались основные принципы системы ПДС. Были рассмотренные взаимозависимости различных параметров характеризующих систему...
-
Определение сметной стоимости строительства узла коммутации - Передача дискретных сообщений
При определении денежных и материальных затрат на строительство или реконструкцию сооружений электрической связи на стадии проектного задания...
-
В соответствии с исходными данными варианта в качестве приемника применяется приемник когерентного приема ДЧМ. Рассмотрим выражение временной функции...
-
Преобразование в АЦП состоит из трех операций: сначала непрерывное сообщение подвергается дискретизации по времени через интервалы ; полученные отсчеты...
-
Для повышения помехоустойчивости приема дискретных двоичных сообщений, решение о переданном символе принимается не по одному отсчету на длительности...
-
Задача 1 Какие из приведенных ниже кодовые комбинации содержат ошибку, если известно, что они передавались стандартным телеграфным кодом №3: 0101010;...
-
Классификация кодов Эффективное кодирование - это процедуры направленные на устранение избыточности (т. е. минимизировать количество элементов,...
-
МЕЖДУНАРОДНЫЕ СИСТЕМЫ БАЙТОВОГО КОДИРОВАНИЯ - Кодирование информации
Информатика и ее приложения интернациональны. Это связано как с объективными потребностями человечества в единых правилах и законах хранения, передачи и...
-
Среднесуточная нагрузка проектируемой станции АТ зависит от потока телеграфного обмена местных и иногородних абонентов. Среднесуточная нагрузка местных...
-
Определение потока телеграфного обмена по системе прямых соединений - Передача дискретных сообщений
Общий среднесуточный поток телеграфного обмена по каналам системы ПС проектируемой станции определяется из выражения QКпс =, (7) Где n - число станций, с...
-
Введение - Передача дискретных сообщений
Железнодорожный транспорт - вид наземного рельсового транспорта, представляющий собой совокупность его коммуникаций и транспортных средств,...
Эффективное кодирование - Техника передачи дискретных сообщений