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 .

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

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

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

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


 

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

45919. Классификация баз 84.48 KB
  Классификация баз КОНСТРУКТОРСКАЯ БАЗА это база используемая для определения положения детали или сборочной единицы в изделии ГОСТ 2149576. ОСНОВНАЯ конструкторская база принадлежит данной детали или сборочной единице и определяет ее положение в изделии. ВСПОМОГАТЕЛЬНОЙ называется конструкторская база принадлежащая данной детали или сборочной единице используемая для определения положения присоединяемых к ней деталей или сборочных единиц. ТЕХНОЛОГИЧЕСКАЯ БАЗА это база используемая для определения положения заготовки...
45920. Правила (принципы) базирования. Определенность и неопределенность базирования 11.85 KB
  В практике достигнутое правильное положение детали может измениться если возникнут силы или моменты сил нарушающие контакт поверхности детали с опорными точками приспособлений. Поэтому для сохранения полученного при базировании правильного положения детали необходимо обеспечить непрерывность контакта баз. ОПРЕДЕЛЕННОСТЬ БАЗИРОВАНИЯ детали неизменность ее положения относительно поверхностей другой детали или деталей с которыми она соединена и которые определяют ее положение в процессе изготовления. НЕОПРЕДЕЛЕННОСТЬ...
45921. Индивидуальное проектирование тех. процессов 10.84 KB
  Подготовительный этап А анализ конструкторской информации Б определение типа прва В выбор метода получения заготовок 2. Синтетический этап А синтез вариантов маршрута обки отдельных повей Б синтез вариантов схем базиия В синтез маршрута обки заготовок Г синтез структуры операции 3.Аналитический этап а размерный анализ тех. Заключительный этап: Оформление документации.
45922. Структура временных связей в операциях технологического процесса. Техническое нормирование 27.58 KB
  Структура оперативного времени в операциях могут отличаться в зависимости от способов выполнения основных переходов степени совмещения выполнения основных и вспомогательных переходов; числа потоков дублирующих выполнение одинаковых переходов при изготовлении одноименных изделий. Время затраченное на две группы основных переходов составит сумма времени выполнения наиболее длительных переходов в каждой из групп основных переходов: где – число групп основных переходов. Поэтому основное технологическое время равно наибольшему времени...
45923. Пути сокращения затрат времени на выполнение операции 25.95 KB
  Пути сокращения затрат времени на выполнение операции Анализ формул по определению штучнокалькуляционного времени : показывает что его можно уменьшить либо путем сокращения подготовительнозаключительного и штучного времени либо увеличением объема партии изготовляемых изделий . Пути сокращения подготовительно заключительного времени Затраты времени на подготовку к работе складываются из времени получения и ознакомления рабочего с заданием получения и установки на станке инструментов и приспособлений а по окончании работы их...
45924. Технологичность конструкции 14.3 KB
  Конструкция изделия в первую очередь определяется его служебным назначением. Однако конструктивное исполнение изделия может быть разным при этом будут разными и затраты ресурсов. Эта разница и является результатом разного уровня технологичности изделия. Технологичность это совокупность свойств изделия определяющих приспособленность его конструкции к достижению оптимальных затрат ресурсов при его производстве ремонте и утилизации.
45925. Выявление маршрута обработки отдельных поверхностей детали 18.51 KB
  Выявление маршрута обработки отдельных поверхностей детали. 2 Аналогичные действия выполняются при планировании обработки всех других поверхностей. 3 Расчленяют операции и переходы на черновые получистовые и чистовые а затем формируют примерный маршрут обработки. 4 Внедряют передовые методы механической обработки ППД РСО ЭЭО и т.
45926. Основные функциональные элементы приспособлений. Назначение и краткая характеристика 13.69 KB
  Конструкции всех станочных приспособлений основываются на использовании типовых элементов которые можно разделить на следующие группы: аустановочные опорные элементы определяющие положение детали в приспособлении; бзажимные элементы устройства и механизмы для крепления деталей или подвижных частей приспособлений; в настроичные элементы г элементы обеспечивающие точное расположение приспособления на месте эксплуатации. д делительные устройства екорпуса крепежные элементы и вспомогательные устройства. Зажимные...
45927. Способы базирования заготовок с базами в виде плоских поверхностей 329.69 KB
  Базирование главной базы имеет 3 точки осуществляется на: 3 штыря опоры 2 пластины опорные штыри в сочетании с плавающими и сблокированными опорами на плоскость опорного элемента. При этом погрешность базирования близко равно 0. Для необработанных баз следует учитывать дополнительно погрешность связанную с отклонением плоскостности базы.