эффективное оптимальное кодирование информации

Эффективное кодирование без потери информации в РТС

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

Три типа кодирования которые применяются в радиотехнических системах (РТС):

Структура РТСПИ с учетом кодирования

В схеме передачи сообщений представлены все виды кодирования и соответствующие им кодирующие устройства на передающей стороне (кодеры) и декодирующие устройства на приемной стороне (декодеры).

Эффективное кодирование – процесс уменьшения избыточности информации (сжатие информации).

Смотрим на рисунок изображенный выше. Есть блок эффективное кодирование, который устраняет избыточность информации. Обычно сообщение, речь, изображение, видео, любая информация, которую мы воспринимаем из внешнего мира, вносит большую избыточность. Чтобы уменьшить избыточность, применяют сжатие.

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

Если есть такая необходимость применяется помехоустойчивое кодирование, т.е. шифрование. Если привести в пример мобильную связь, то там шифрование играет важную роль, если бы его не было, тогда наши разговоры были бы слышны всем. Без помехоустойчивого кодирования не работает ни одна РТС, которая передает цифровые сообщения.

Помехоустойчивое кодирование располагается перед модулятором, предназначено для устранения ошибок в канале связи. На этом этапе добавляется избыточная информация. Если не добавлять избыточности, тогда нельзя исправить ошибки.

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

Эффективное кодирование

Пропускная способность это ширина спектра, чем больше пропускная способность, тем быстрее передается информация и тем шире становится спектр, чем шире спектр становится, тем меньше каналов в эфире можно расположить.

Эффективное кодирование бывает:

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

Если работать с той информацией, которую можно немного исказить, то будет достигнуто лучшее сжатие. Такое сжатие применимо в аудио, сжатии речи, изображение, видео. Идет размен между степенью сжатия и качеством, но по прежнему, например картинка или звук сохранили свою информативность.

Есть несжатая звуковая информация разрядностью 16 бит, и частотой дискретизации 44100Гц имеет скорость 705 кБит/с. Для речи достаточно частоты дискретизации 8кГц, 16бит≈128кБит/с.

В таблице представлены скорости, которые обеспечивают речевые кодеки.

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

Формат передачи видео PAL и SECAM без сжатия потребовал бы информационной скорости ≈ 249 МБит/с (720×576× (3×8) × 25). Со сжатием MPEG-2 информационная скорость составляет порядка 15 Мбит/с.

Сжатие без потери информации

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

Рассмотрим на примере алфавита. Чем буква встречается чаще, тем меньше информации она в себе несет и наоборот.

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

Например, кодируем русский алфавит, кириллицу. Объединим буквы е и ё, тогда 32 буквы. Потребуется 5 бит, чтобы закодировать 32 различных символа. 2^5=32. Сжимаем на основании того, что какие-то буквы встречаются редко, а какие-то часто.

Каким-то буквам поставим 3 бита, которые часто встречаются, Буквы, которые редко встречаются, им можно поставить 9 бит. Но нас интересует не одна буква, а текст. Для примера посмотрите табличку.

Чем больше вероятность, тем чаще буква встречается. Тем меньше кодовое слово. Несмотря на то, что часть символов имеют длину кодового слова больше, чем если кодировать напрямую, все равно, за счет тех символов, которые встречаются в среднем объем информации станет меньше.

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

ИТОГ: Сжатие без потери информации осуществляется за счет того что, те символы, которые применяются часто, им ставятся короткие кодовые слова, а которые редко, там можно ставить длинные кодовые слова.

Источник

Оптимальное (эффективное) кодирование

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

Первая теорема Шеннона дает ответ на вопрос, всегда ли можно осуществить оптимальное кодирование: если есть канал с пропускной способностью С, то сообщение из любого источника с энтропией Н(х)можно закодировать так, что окажется возможным передавать эти сообщения со скоростью как угодно близкой к С/Н(х) сообщений в секунду (С двоичных единиц за секунду. Рассмотрим справедливость теоремы для двоичного канала связи.

Пусть алфавит источника сообщений создает конечную систему.

Для сообщения х_i длинна кодовой комбинации равна m_i, а вероятность ее появления Р(х_і). Количество информации что содержится в i-м сообщении равно I_xi=-logP(x_i). Пропускная способность канала будет полностью использована, если на каждыйдвоичный символ будет приходится один бит информации. Это будет в том случае, когда количество двоичных символов в кодовой комбинации будет равно количеству информации что содержится в ней. Таким образом, условием опримального кодирования является равенство.

Усреднив это сообщение повсем возможным сообщениям получим:

Меньше чем Н(х) средняя длинна сообщения быть не может.

Максимальная скорость что может быть достигнута в двоичном канале без помех равна:

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

Что отвечает условию оптимального кодирования. Пример:

При решении практических задач не всегда удается разделить таблицу на две части с одинаковой вероятностью. Этот не достаток устраняется при использовании кода Хаффмана.

Аналогично к коду Шеннона-Фано при использовании кода Хаффмана строится таблица в порядке уменьшения вероятности появления сообщений. Сообщения х_n и х_n-1 соединяются в одну группу с вероятностью Р(х)=Р(х_n)+Р(х_n-1). Такое объединение повторяется до тех пор пока Р(х) не станет равно 1.

Отличие в кодировании в том, что в коде Шеннона-Фано формирование начинается со старшого (лівого) разряда. В коде Хаффмана кодове комбинации котируються начиння с младшего (правого) разряда.

Источник

Электронные средства сбора, обработки и отображения информации

Оглавление

Оптимальное кодирование

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

Чем больше основание системы счисления, тем меньшее число разрядов требуется для представления данного числа, а следовательно, и меньшее время для его передачи. Однако с ростом основания усложняются устройства передачи и приема сигналов, так как логические элементы в этом случае должны иметь большее число устойчивых состояний. Если учитывать оба эти обстоятельства, то целесообразно выбрать систему, обеспечивающую минимум произведения основания кода т на количество разрядов п для выражения любого числа. Найдем этот минимум по графику для большого числа 60000.

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

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

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

Сложение по модулю в двоичной системе также просто:

00=0;

01=1;

11=0;

10=1

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

Чтобы сохранить преимущества двоичной системы, используют двоично-десятичные коды. В таком коде каждая цифра десятичного числа записывается в виде четырехразрядного двоичного числа. С помощью четырех разрядов можно образовать шестнадцать различных комбинаций, из которых любые десять могут составить двоично-десятичный код. Наиболее распространен код 8-4-2-1. Этот код относится к взвешенным кодам. Цифры в названии кода означают вес единиц в соответствующих двоичных разрядах. Он соответствует первым десяти комбинациям натурального двоичного кода (табл. 2.1).

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

000000000100010001200100010300110011401000111501011000601101001701111010810001011910011111

Код 8-4-2-1 обычно используется как промежуточный при введении в вычислительную машину данных, представленных в десятичном коде.

Перевод чисел из десятичного в двоично-десятичный код осуществляется перфоратором в процессе переноса информации на перфоленту или перфокарту. Последующее преобразование в двоичный код осуществляется по специальной программе в самой машине. Двоично-десятичные коды с весами 5-1-2-1 и 2-4-2-1 используются при поразрядном уравновешивании в цифровых измерительных приборах (цифровые вольтметры и т.п.).

Недостатки взвешенных кодов: при передаче информации по каналам связи под действием помех отдельные элементы кода могут так исказиться, что будут приняты неверно. Например, вместо «0» будет принят элемент «1» или наоборот. Если будет искажен старший разряд, то ошибка будет значительно больше, чем при искажении младшего разряда. С этой точки зрения лучше применять невзвешенный код, у которого ошибки, вызванные помехами, были бы одинаковыми для любого разряда.

В невзвешенных кодах позициям (разрядам) кодовой комбинации не приписывают определенных весов. Вес имеет лишь вся кодовая комбинация в совокупности. Рассмотрим невзвешенный двоичный рефлексный код Грея (табл. 2.2).

Код Грея000000000100010001200100011300110010401000110501010111601100101701110100810001100910011101...1511111000

Правило получения кода Грея: кодовую комбинацию натурального двоичного кода складывают по модулю 2 с такой же комбинацией, сдвинутой на один разряд вправо, при этом младший разряд сдвинутой комбинации отбрасывается.

Характерные особенности кода Грея:

1) каждая последующая комбинация всегда отличается от предыдущей только в одной позиции (в одном разряде);

2) смена значений элементов в каждом разряде (1 на 0 или 0 на 1) при переходе от комбинации к комбинации в коде Грея происходит вдвое реже, чем в натуральном двоичном коде. Это свойство кода Грея позволяет получить точность кодирования выше по сравнению с натуральным двоичным кодом при том же быстродействии схемы кодирования;

3) при сложении двух соседних комбинаций кода Грея по модулю 2 (mod 2) число единиц равно числу разрядов минус три (n-3). Это свойство кода Грея можно использовать для проверки правильности принятых комбинаций.

В коде Грея можно выделить оси симметрии (оси отражения), относительно которых наблюдается идентичность элементов в некоторых разрядах. Так, например, имеет место симметрия относительно оси, проведенной между числами 7 и 8 (идентичны три символа младших разрядов). Эта особенность и послужила основанием для введения термина «рефлексный», то есть отраженный код.

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

Недостатком кода Грея и других рефлексных кодов является то, что эти коды невзвешенные, их трудно обрабатывать с помощью ЭВМ, так как сложнее выполнять декодирование.

Преобразование кода Грея в натуральный двоичный код выполняется по правилу: старший разряд записывается без изменения, каждый следующий символ кода Грея нужно инвертировать, если в натуральном коде перед этим была получена «1», и оставить без изменения, если в натуральном коде был получен «0». (Пример: ).

Источник

Кодирование для чайников, ч.1

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

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

0. Начало

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

1.2 Чередующиеся сигналы

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

1.3 Контекст

2. Кодирование текста

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Источник

Эффективное оптимальное кодирование информации

Оптимальное эффективное кодирование позволяет согласовать источник с каналом и обеспечить наилучшее использование пропускной способности канала. Сущность эффективного (Кодирования заключается в том, что неравномерное распределение вероятностей появления коррелированных символов сообщений с помощью определенным образом выбранного кода переводят в равномерное распределение вероятностей появления независимых кодовых символов.

Рассмотрим оптимальное эффективное кодирование сообщений источников без памяти и с памятью.

5.3.1. Кодирование сообщений источников без памяти. Символы сообщений «источников без памяти являются независимыми. Покажем, чем определяется и как достигается минимальная длина кодовой комбинации при кодировании символов сообщений источников без памяти. Обеспечение минимальной средней длины кодовой комбинации и равновероятного появления в ней независимых кодовых символов равносильно увеличению средней скорости передачи информации до максимальной потому, что за одно и то же время коротких кодовых -комбинаций можно передать больше а. это при прочих равных условиях соответствует передаче большего (Количества информации.

Минимальная средняя длина Пот кодовой комбинации определяется совместным выполнением условий (5.29), (5.32):

Если ошибки в канале отсутствуют, то минимальная средняя длина комбинации определяется только условием (5.29) при . Поэтому для идеальных каналов

Например, при двоичном кодировании сообщений для идеального канала

Следовательно, если энтропия двоичного кодера максимальна, среднее число кодовых символов в комбинациях минимально и равно энтропии источника. Оценка (5.44) средней длины кодовой комбинации является предельной; средняя длина кодовой комбинации не может быть меньше под. Эта оценка показывает, к чему необходимо стремиться при выборе способа эффективного кодирования. Теорема Шеннона для идеального канала утверждает, что такие способы кодирования существуют.

Если двоичный канал является реальным, то из-за ошибок растет средняя длина кодовых комбинаций и избыточность кода. Это вызвано необходимостью вводить в комбинации дополнительные кодовые символы, позволяющие обнаруживать и исправлять ошибки. В этом случае оценка средней минимальной длины кодовой комбинации подчиняется условию (5.40).

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

Этого недостатка лишен код Шеннона — Фано. Он построен по следующему алгоритму. Все символы алфавита сообщений записывают в порядке убывания вероятностей их появления. Полученную ранжированную (упорядоченную) последовательность символов разбивают на две группы так, чтобы суммы вероятностей трупп были примерно одинаковыми. Для символов верхней группы в качестве первого символа кодовой комбинации присваивают кодовый символ 0, для символов нижней группы — кодовый символ 1. Полученные группы символов сообщений опять разбивают на две подгруппы по указанному принципу и опять кодируют. Такое разделение продолжают до тех пор, пока в последних подгруппах не останется по одному символу сообщений. Верхнему последнему символу в качестве последнего символа кодовой комбинации присваивается символ 0, нижнему — символ 1. При кодировании по этому алгоритму средняя длина кодовой комбинации близка к минимальной, энтропия кодера максимальна (вероятности появления кодовых символов примерно одинаковы),

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

Рассмотрим на конкретном примере особенности оптимального эффективного кодирования по алгоритму Шеннона-Фано. Предположим, что объем алфавита источника основание кода вероятности появления символов: канал идеальный. Оценим скорость передачи информации, пропускную способность и коэффициент использования идеального канала для равномерного кодирования и оптимального эффективного кодирования.

Вначале определим информационные характеристики источника сообщений. Энтропия источника

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

Найдем характеристики равномерного двоичного кода. Длину кодовых комбинаций определим из условия

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

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

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

Найдем характеристики неравномерного двоичного кода Шеннона-Фано для этого случая. Особенности процедуры кодирования показаны в табл. 2 и с помощью графа кодирования на рис. 5.2. Граф кодирования показывает, как «расщепляется» ранжированная последовательность символов на группы и отдельные

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

Энтропия эффективного кодера

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

Рис. 5.2. Граф кодирования

Анализ и сравнение результатов равномерного и оптимального эффективного (неравномерного) кодирования для идеального канала в рассмотренном примере показывают следующее. Энтропия эффективного кодера и скорость передачи информации при неравномерном кодировании примерно на 33% выше, чем при равномерном, избыточность кода — на 33% ниже, коэффициент использования канала выше на 33% и близок к единице. Средняя длина кодовых комбинаций (5.44) при неравномерном кодировании близка (к минимальной: Так как максимальное количество информации, которое может переносить двоичный кодовый сигнал, равно 1 бит, то важно отметить, что энтропия эффективного кодера близка к максимальной — каждый кодовый сигнал несет 0,97 бит информации. Следовательно, в результате кодирования символы 0 и 1 появляются почти с одинаковой вероятностью. Таким образом, эффективный кодер преобразовал неравновероятные независимые символы источника сообщений в равновероятные независимые кодовые сигналы.

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

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

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

а пропускная способность определяется количествам только кодовых посылок в 1 с (пусковая и стоповая посылки, которые используют для синхронизации, информации не несут), поэтому

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

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

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

коэффициент (использования канала

Следовательно, для обнаружения и исправления ошибок в канале и обеспечения сколь угодно малой вероятности ошибки избыточность кодирования должна быть повышена более чем на 25%. Энтропия кодера и скорость передачи информации при этом также уменьшается более чем на 25%. Интересно отметить, что избыточность, искусственно вводимая для коррекции ошибок в реальных каналах с высоким уровнем помех, может превысигь ту естественную избыточность, которая устраняется при оптимальном эффективном кодировании.

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

Следовательно, кодирование сообщений источников с памятью выполняют в два этапа: на первом этапе осуществляют разбивку сообщений на блоки длиной в результате чего блоки нового алфавита становятся независимыми, а на втором этапе используют оптимальные коды, подобные коду Шеннона — Фано.

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

где -время передачи одного символа первичного алфавита; Т — задержка блоков в канале. Производительность источника блоков

где среднее количество информации в одном блоке.

Укрупнение алфавита не изменяет избыточности сообщений. Однако избыточность, обусловленная корреляционными связями символов первичного алфавита, преобразуется в избыточность источника блоков, обусловленную неравновероятным появлением независимых блоков. Это объясняется тем, что неравномерность распределения вероятностей появления блоков больше, чем неравномерность распределения вероятностей появления символов первичного алфавита. Избыточность сообщений, составленных из блоков,

где объем укрупненного алфавита; объем первичного алфавита. Из формулы (5.54) следует, что избыточность сообщений, составленных из символов первичного и вторичного алфавита, одна и та же.

Оптимальное эффективное кодирование сообщений почти полностью устраняет их избыточность. Из-за этого процесс передачи информации становится чувствительным к воздействию помех. Особенно сильно проявляется эта особенность при кодировании

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

Источник