40151

ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ ИНФОРМАЦИИ

Лекция

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

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

Русский

2013-10-15

87.5 KB

57 чел.

PAGE   \* MERGEFORMAT 1

ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ ИНФОРМАЦИИ

Типы кодирования

 

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

1. Кодирование источника информации состоит в дискретизации по времени и уровню и в случае непрерывных сообщений при максимально возможном сжатии информации до дискретизации или после нее в целях экономии ресурсов каналов связи или памяти. Получаемый при этом код называется первичным или натуральным. Примеры: ЦАП, цифровая телефония, программы архиваторы RAR, ZIP и т.д.

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

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

4. Криптографическое кодирование состоит в засекречивании данных в целях исключения несанкционированного доступа к информации в процессе ее хранения и передачи.

4.2 Избыточность сообщений и ее роль.

Кодирование сообщений в системах связи

При чтении какого-либо текста можно по смыслу найти и исправить неверно напечатанные, буквы. В теоретическом плане эта возможность основывается на наличии избыточности сообщения.

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

.                                                   

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

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

 .

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

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

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

Пусть требуется по каналу связи передать равновероятные сообщения "да" и "нет". В сообщении будет отсутствовать избыточность, если выбрать двоичный однопозиционный код (m = 2, n = 1), приписав "да" символу 1 и "нет" - символу 0. Энтропия кода будет равна бит/символ. В канале связи из-за действия помех может произойти замена или, как говорят, инвертирование символов с вероятностью ошибки Рe = 0,1. Это означает, что с такой вероятностью обеспечивается прием передаваемого сообщения.

Теперь выбираем двоичный трёхпозиционный код (m = 2, n = 3), приписав "да" кодовой комбинации 111 и "нет" комбинации 000. В этом случае для передачи информации в 1 бит потребуется три символа, Н = 1/3 бит/символ. Налицо избыточность, так как , что приводит к уменьшению скорости передачи информации в три раза и, соответственно, к увеличению в три раза времени, потребного для передачи одного сообщения. На приёмном конце наряду с комбинациями 111, 000 могут возникнуть из-за действия помех комбинации 001, 010, 011, 100, 101, 110. Принимаемые кодовые комбинации, содержащие две или три единицы, будем воспринимать как сообщение "да", а принимаемые кодовые комбинации, содержащие два или три нуля, - как сообщение "нет". В этом случае инвертирование помехой одного символа комбинации не приводит к ошибке. Ошибка появляется лишь тогда, когда под действием помехи произойдет замена двух или трёх символов. Рассчитаем вероятность Pош этой ошибки, пользуясь формулой Бернулли, когда число испытаний равно числу позиций в коде n = 3, вероятность осуществления события в одном испытании равно вероятности ошибки   Имеем

Заметим, что вероятность ошибки в трехпозиционном коде с избыточностью при вероятности инвертирования из-за помехи одного символа Ре= 0.1 получилась приблизительно 0.1/0.028 3,5 раза меньше по сравнению с однопозиционным кодом без избыточности при том же уровне помех.

4.3 Теоремы кодирования для каналов без помех и с помехами

 

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

бит/с,

где Fс  - средняя частота появления символа в единицу времени;  - энтропия сообщения.

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

бит/с ,

где m - число символов в алфавите сообщения; F - полоса пропускания канала.

В общем плане согласование источника сообщений с каналом состоит не в том, чтобы обеспечить согласование Fс с F, а в том, чтобы обеспечить согласование R с С.

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

,

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

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

.

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

C > R .

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

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

Теория кодирования развивается в двух главных направлениях: во-первых, поиски кодов, позволяющих в каналах без помех максимально устранить избыточность источника и тем самым повысить скорость передачи информации. Этим занимается теория экономического кодирования. Её теоретической основой является первая теорема Шеннона. Во-вторых, поиски кодов, повышающих достоверность передачи информации в каналах с помехами. Этим занимается теория помехоустойчивого кодирования. Её теоретической основой является вторая теорема Шеннона.

Практическая реализация кодирования на передающей стороне всегда предполагает применение обратной процедуры – декодирования – для восстановления принятого сообщения. Устройства, осуществляющие кодирование и декодирование, называются соответственно кодер и декодер. Выполняются они обычно в одной микросхеме и образуют устройство, называемое  кодеком.


 

А также другие работы, которые могут Вас заинтересовать

32228. Составление плана расследования. Основные и вспомогательные формы планов 35 KB
  Составление плана расследования. Это приводит к необходимости планирования расследования различных дел во времени подготовка документов отчётов и т. 2 План расследования по конкретному преступлению. Составляется план расследования по версиям.
32229. Каноническое представление уравнения Эйлера 137.5 KB
  Например требуется определить закон изменения якорного тока и скорости вращения двигателя постоянного тока который поворачивает платформу экскаватора. Динамика двигателя описывается уравнением равновесия моментов – момент развиваемый двигателем уравновешивается динамическим моментом и моментом сопротивления: п.1 где Мдв=Смi – момент развиваемый двигателем См – постоянная двигателя i – якорный ток J – момент инерции приведенный к валу двигателя скорость вращения...
32230. Синтез оптимального управления при ограничениях на управляющее воздействие 163 KB
  Более эффективно решение задач синтеза оптимального управления при ограничениях управляющих воздействий осуществляется путем использования принципа максимума предложенного в 1956 году академиком Л. Принцип максимума является дальнейшим развитием вариационного исчисления. Это условие положено в основу принципа максимума. Рассмотрим применение принципа максимума Понтрягина для решения задач оптимизации.
32231. Метод динамического программирования Р. Беллмана 1.14 MB
  6 величина определяется в соответствии с уравнениями 7.10 При условиях ; Оптимальное уравнение определяется в результате решения уравнения 7.10 можно заменить уравнениями в частных производных 7.4 получим Из уравнения получим П 7.
32232. Связь между принципами максимумами и динамическим программированием 359.5 KB
  17 является скалярным произведением векторов Ψ и X: Н = ψ 8. Вектор касателен к траектории t и нормален к векторам ψ и –ψ что определяет оптимальный процесс перехода из в . Максимальное быстрое уменьшение J будет происходить очевидно что если вектор скорости Хточка в направлении убывании убывание J будет максимальным. Для обеспечения этого необходимо чтобы проекция вектора скорости движения изображающей точки Хточка на вектор отрицательной нормалям к поверхности J...
32233. Синтез оптимального по быстродействию программного управления 211 KB
  3 Где уравнение динамики объекта управления Поскольку то максимум функции Н реализуется одновременно с максимумом функции: 9. Решим задачу определения оптимального по быстродействию программного управления на примере объекта второго порядка: .1 То структурная схема объекта представлена на рис. Структурная схема объекта управления В соответствии со структурной схемой на рис.
32234. Синтез замкнутых систем управления, оптимальных по быстродействию 147 KB
  невозможно путём интегрирования уравнений объекта найти уравнения траекторий в nмерном пространстве.6 в этом случае можно представить относительно других координат: где i = 12n Тогда уравнения проекций фазовых траекторий на координатные плоскости при U = const будут иметь вид: Интегрируя это выражение получим: где ; координаты точек через которые проходит проекция 10.2 С помощью уравнений проекций фазовых траекторий определяем координаты точек переключений U.6 получим выражение...
32235. Аналитическое конструирование регуляторов (АКОР) 137.5 KB
  он ограничивает и отклонение переменных состояния объекта управления и управляющего воздействие данная задача определения оптимального регулятора получила широкое распространение. Задана динамика объекта управления: ; 1 или 1 где А=[nn] коэффициентная матрица динамики объекта B=[nm] – матрица коэффициентов управляющих воздействий xiн=xi0 xiк=xitк – граничные условия. Критерий...
32236. Системы, оптимальные по расходу ресурсов 199 KB
  Все они имеют ограничения по величине управляющего воздействия что довольно очевидно.4 В качестве критерия выберем интегральный критерий обеспечивающий одновременно ограничение переходного процесса по времени и по расходу управляющего воздействия п1.16 Системы из исходного состояния х10х20 в начале координат х1к=0х2к=0 должно производится следующим путем изминения управляющего воздействия: п1.17 Следовательно необходимо найти...