40151

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

Лекция

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

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

Русский

2013-10-15

87.5 KB

59 чел.

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 .

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

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

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

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


 

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

63166. Право як навчальний предмет. Мета, завдання, особливості курсу 22.77 KB
  Обладнання й матеріали: Конституція України Конвенція ООН про права дитини Загальна декларація прав людини плакати з висловами відомих людей про права людини. Мир прогрес права людини ці три цілі нерозривно повязані неможливо досягнути...
63167. Вступ до історії стародавнього світу 28.52 KB
  Мета: Сформувати уявлення про хронологічні межі та предмет історії стародавнього світу дати визначення понять стародавній світ історичне джерело археологічні памятки розвивати навички відліку часу до н. Після цього уроку учні зможуть...
63168. СЛОВ’ЯНИ ПІД ЧАС ВЕЛИКОГО ПЕРЕСЕЛЕННЯ НАРОДІВ 31.51 KB
  Мета: визначити територію, заняття й суспільні відносини союзів словянських племен, що стали базою, на якій виникла держава — Київська Русь; розвивати в учнів навички роботи з першоджерелами, історичною картою, блок-таблицями, схемами...
63169. Правознавство. Життя за правилами 21.63 KB
  Мета: познайомити учнів з правилами суспільного життя з ознаками правової норми сформувати розуміння необхідності дотримання законів і правил виховувати в учнів активну громадянську позицію.
63170. Виникнення людини. Залюднення Європи 27.2 KB
  Мета: дати уявлення про передумови виникнення людини; розглянути процес розселення пралюдей на території Європи; показати роль праці у виділенні людини з тваринного світу.
63171. СТАНОВЛЕННЯ ДЕРЖАВИ З ЦЕНТРОМ У КИЄВІ 42.97 KB
  Рюрик помер у Новгороді залишивши малолітнього сина Ігоря на руках його вихователя Олега. Виступ учня Правління Олега. Він вважав що Аскольд став жертвою змови київських прибічників язичництва: Убивство Аскольдове найбільш вірогідне що хрещення тому причиною було...
63172. Право. Норми права. Правовідносини 29.03 KB
  Мета: розкрити зміст поняття права визначити його особливості поміж інших соціальних норм; розтлумачити основні ознаки права; розвивати вміння учнів робити порівняльний аналіз фактів понять та подій соціального буття...
63173. Освоєння давньою людиною теренів Європи 22.56 KB
  Мета: Показати основні зміни навколишнього середовища в льодовиковий період їхній вплив на розвиток людини її господарське життя; формувати навички встановлення причиннонаслідкових звязків.
63174. Поява людини сучасного типу 22.56 KB
  Мета: ознайомити учнів із зовнішнім виглядом розселенням основними заняттями людини сучасного типу; схарактеризувати нові форми людського суспільства; визначити роль кроманьйонця в еволюції людини...