Первая теорема шеннона. Основная теорема шеннона о кодировании для канала без помех. Кодирование речевой информации
Лекция 6. Постановка задачи кодирования. Первая теорема Шеннона.
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе информатики, необходимо отнести следующие:
разработка принципов наиболее экономичного кодирования информации;
согласование параметров передаваемой информации с особенностями канала связи;
разработка приемов, обеспечивающих надежность передачи информации по каналам связи, то есть отсутствие потерь информации.
Как отмечалось при рассмотрении исходных понятий информатики, для представления дискретных сообщений используется некоторый алфавит. Однако часто однозначное соответствие между содержащейся в сообщении информацией и его (сообщения) алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения из одного алфавита в другой, причем такое преобразование не должно приводить к потере информации.
Введем ряд определений.
Будем считать, что источник информации представляет информацию в форме дискретного сообщения, используя для этого алфавит, который мы условимся называть первичным алфавитом . Далее это сообщение попадает в устройство, преобразующее и представляющее сообщение в другом алфавите – этот алфавит мы назовемвторичным алфавитом .
Код – это правило, описывающее соответствие знаков или сочетаний знаков первичного алфавита знакам или сочетаниям знаков вторичного алфавита.
При этом существует и другое определение:
Код – это набор знаков или сочетаний знаков вторичного алфавита, используемый для представления знаков или сочетаний знаков первичного алфавита.
Кодирование – это перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование – это операция, обратная кодированию, то есть восстановление информации в первичном алфавите по полученной последовательности кодов.
Кодер – это устройтство, обеспечивающее выполнение операции кодирования.
Декодер – это устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми , если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление (получателем) после передачи.
Примером необратимого кодирования может служить перевод с одного естественного языка на другой. При этом обратный перевод, вообще говоря, не восстанавливает исходного текста. Здесь важно понимать, что исходная информация восстанавливается с потерями как в смысловом отношении, так и в смысле искажения в форме представления (полученная после обратного перевода последовательность знаков первичного алфавита практически всегда уже другая по сравнению с исходным текстом).
Безусловно, для практических задач, связанных со знаковым представлением информации, возможность восстановления информации по ее коду является необходимым условием применимости кода, поэтому в дальнейшем мы ограничимся только рассмотрением обратимого кодирования.
Кодирование информации предшествует передаче и хранению информации. При этом хранение информации связано с фиксацией некоторого состояния носителя информации, а передача информации связана с процессом изменения состояния носителя информации (среды), то есть с сигналами. Эти состояния или сигналы мы будем называть элементарными сигналами .Совокупность элементарных сигналов и составляет вторичный алфавит .
Сейчас мы не будем обсуждать технические стороны передачи и хранения сообщения, то есть не будем обсуждать то, каким образом технически реализованы передача и прием последовательности сигналов или фиксация состояний носителя информации (запись информации).
Попробуем сделать математическую постановку задачи кодирования информации.
Пусть первичный алфавит
состоит из
,
а вторичный алфавит
состоит из
знаков со средней информацией на знак
.
Пусть также исходное сообщение,
представленное в первичном алфавите,
содержит
знаков, а закодированное сообщение
(представленное во вторичном алфавите)
содержит
знаков. Таким образом, исходное сообщение
содержит
информации, а закодированное сообщение
содержит
информации.
Операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить :
.
Это неравенство можно переписать как
или
.
Отношение
характеризует среднее число знаков
вторичного алфавита, которое приходится
использовать для кодирования одного
знака первичного алфавита
.
Величину
будем называть длиной кода или длиной
кодовой цепочки
:
.
Из предыдущего неравенства
следует, что
,
поэтому:
. (7.1)
Обычно на практике процедуру кодирования реализуют таким образом, что выполняется условие
,
поэтому
,
то есть один знак первичного алфавита
представляется несколькими знаками
вторичного алфавита.
Способов построения кодов при фиксированных
алфавитах
и
существует множество. Поэтому возникает
проблема выбора (или построения)
наилучшего варианта кода – будем
называть егооптимальным кодом
.
Выгодность применения оптимального кода при передаче и хранении информации – это экономический фактор, так как более эффективный код может позволить затратить на передачу сообщения меньше энергии и времени. В случае применения оптимального кода при передаче информации может меньшее время заниматься линия связи. Применение оптимального кода при хранении информации может позволить использовать меньше площади поверхности (объема) носителя информации.
При этом следует осознавать, что выгодность кода не всегда идентична временной выгодности всего процесса «кодирование–передача– декодирование». Возможна ситуация, когда за использование эффективного кода при передаче информации придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и/или иных ресурсов (памяти технического устройства, если эти операции производятся с его помощью).
Как следует из условия (7.1), минимально возможное значение средней длины кода равно:
. (7.2)
Данное выражение следует воспринимать
как соотношение оценочного
характера,
устанавливающее нижний предел длины
кода. Однако, из (7.2) неясно, в какой
степени в реальных схемах кодирования
возможно приближение величины
к значению
.
По этой причине для теории кодирования и теории связи важное значение имеют теоремы, доказанные Шенноном. Первая теорема Шеннона затрагивает ситуацию с кодированием при отсутствии помех, искажающих сообщение. Вторая теорема Шеннона относится к реальным линиям связи с помехами и будет обсуждаться нами позже.
Первая теорема Шеннона , илиосновная теорема о кодировании при отсутствии помех , формулируется так:
При отсутствии помех всегда возможен такой вариант кодирования, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.
Данная теорема утверждает принципиальную
возможность оптимального кодирования,
то есть построения кода со средней
длиной, имеющей значение
.
Однако необходимо сознавать, что из самой этой теоремы никоим образом не следует, как такое кодирование осуществить практически. Для разработки практической реализации оптимального кодирования должны привлекаться дополнительные соображения, которые мы обсудим далее.
Из (7.2) видно, что имеются два пути
сокращения величины
:
К. Шеннон подробно рассмотрел следующую
частную ситуацию. В этой ситуации при
кодировании сообщения учитывается
различная вероятность появления знаков
в первичном алфавите, то есть величина
информации, приходящейся на знак
первичного алфавита, рассчитывается в
первом приближении:
. Однако корреляции знаков первичного
алфавита не учитываются. Источники
подобных сообщенийназываются
источниками без памяти
(на корреляции
знаков первичного – своего – алфавита).
Если при этом обеспечена равная
вероятность появления знаков вторичного
алфавита, то, как следует из (7.2), для
минимальной средней длины кода
оказывается справедливым соотношение:
. (7.3)
В качестве меры превышения
над
можно ввестиотносительную избыточность
кода
:
С учетом (7.2) последнюю формулу можно переписать в виде
причем
.
Величина
показывает, как сильно операция
кодирования увеличила длину исходного
сообщения. Очевидно, что
при
.
Таким образом, решение проблемы
оптимизации кодирования состоит в
нахождении таких схем кодирования,
которые обеспечили бы приближение
средней длины кода к значению
,
а относительной избыточности
кода – к нулю. Чем меньше значение
,
тем возникает меньше избыточной
информации, то есть информации, связанной
с кодированием; более выгодным оказывается
код и более эффективной становится
операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку первой теоремы Шеннона :
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Наиболее важной для практики оказывается
ситуация, когда во вторичном алфавите
,
то есть когда для представления кодов
в линии связи используется лишь два
типа сигналов. Такое кодирование
называетсядвоичным кодированием
.
Технически это наиболее просто реализуемый
вариант. Например, существование
напряжения в проводе (импульс) или его
отсутствие (пауза); наличие или отсутствие
отверстия на перфокарте; наличие или
отсутствие намагниченной области на
дискете и так далее
Знаки двоичного алфавита принято обозначать «0» и «1», эти знаки нужно воспринимать как буквы. Удобство двоичных кодов также и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе ровно 1 бит информации ().
В случае двоичного вторичного алфавита
(обозначим
)
из формулы (7.3) получаем:
,
и первая теорема Шеннона получает еще одну (третью) формулировку :
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Таким образом, при кодировании сообщений источника без памяти двоичными знаками равной вероятности по формуле (7.4) находим:
. (7.5)
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксируетинтенсивность идлительность сигналов, а также может соотносить последовательность поступающих сигналов с эталонными последовательностями (стаблицей кодов ).
Отметим следующие особенности двоичного вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей вторичного алфавита определяют основу конкретного способа кодирования сообщений. Однако, даже при одинаковой основе возможны различные варианты построения кодов, которые будут отличаться своей эффективностью.
Основное значение результатов Шеннона в этой области состоит в том, что они дают универсальный критерий, позволяющий сравнивать технически различные устройства и системы с точки зрения их возможностей по передаче информации. Технически источники сообщений и каналы связи могут быть существенно разными устройствами по используемым сигналам, способам кодирования сообщений, форматам данных, скоростным характеристикам. В этих условиях информационная мера Шеннона и теоремы идеального кодирования позволяют оценить, в какой степени технически различные системы соответствуют друг другу для решения задачи передачи сообщений. Для этого требуется, исходя из технических показателей источника и канала, оценить их информационные показатели: информационную производительность и информационную пропускную способность. Соотношение информационных показателей и является той идеальной мерой, по которой можно судить о степени соответствия реальных систем.
Особая заслуга Шеннона состоит в том, что он первым осознал действительную картину влияния случайных помех на процесс передачи сообщений. Принципиальное действие помех выражается в той степени, в какой они влияют на информационные показатели системы. Поэтому каналы с одинаковой пропускной способностью эквивалентны по возможности безошибочной передачи сообщений не зависимо от того, действуют ли в них помехи или нет.
Для наглядного пояснения роли теоремы Шеннона прибегнем к следующему сравнению. Пусть имеется трубопровод для доставки от источника некоторого жидкого продукта. Технические возможности трубопровода определяются количеством жидкости, которое можно передать по нему в единицу времени. Производительность источника определим количеством чистого продукта, поступающего от него в единицу времени, а пропускную способность трубопровода - как максимально возможную скорость передачи чистого продукта, соответствующую условию, что от источника поступает чистый продукт без примесей. Аналогом канала с помехами может служить трубопровод с утечкой. Пропускная его способность будет меньше. Чем в трубопроводе без утечки, на величину утечки продукта за единицу времени. Можно теперь представить, какой эффект вызвало бы утверждение, что существует такой способ введения примеси («избыточности») в продукт, при котором, введя количество примеси, равное утечке в трубопроводе, можно по нему доставлять продукт без потерь со скоростью, отвечающей пропускной способности трубопровода с утечкой. Именно такой смысл имеет теорема Шеннона применительно к задаче передачи информации. Продолжая аналогию этого примера, можно сказать, что такой способ введения примеси требует наличия некоего «отстойника», в котором примесь будет отстаиваться в течении определенного времени перед подачей в трубопровод (в идеале - бесконечное время). После такого «отстоя» при движении жидкости по трубопроводув утечку будет уходить только примесь.
Интерпретация результатов Шеннона для задач хранения и поиска информации. Результаты теорем Шеннона, традиционно формулируемые для задачи передачи сообщений, легко распространяются на задачи хранения и поиска информации.
Рассмотрим задачу хранения данных в следующей обобщенной форме. Пусть данные в виде последовательности записей размещаются в ячейках запоминающего устройства (ЗУ); каждая запись помещается в отдельную ячейку. Записи, предназначенные для хранения, характеризуются некоторой совокупностью технических особенностей: размерами, способами кодирования данных, форматами кодов и т.п. Ячейки ЗУ, в которых размещаются записи, также характеризуются некоторой совокупностью своих технических особенностей: внутренним представлением данных, способом доступа, системой меток и рядом технических ограничений на процесс размещения данных. Кроме того, информация, размещаемая в ячейках ЗУ, может подвергаться воздействию помех, из-за чего в записях появляются ошибки.
Возникает вопрос, при каких условиях возможно достоверное хранение информации, т.е. получение из ЗУ данных в том виде, в каком они были туда помещены.
Для ответа на этот вопрос в соответствии с шенноновским подходом необходимо перейти от технических характеристик к информационным:
Для запоминаемых данных определить среднюю энтропию записи;
Для ЗУ определить максимальное количество информации, которое может быть размещено в ячейке с учетом ее технических ограничений и действующих в ней помех, то есть определить информационную емкость ячейки.
Тогда для информационных пользователей будет справедлива следующая формулировка теоремы Шеннона для задачи хранения информации: для запоминающего устройства (с помехами и без помех) существует способ сколь угодно достоверного кодирования и декодирования хранимых данных, если только средняя энтропия записи меньше информационной емкости ячейки.
Если рассмотреть применение идеального кодирования к задаче хранения информации, то станет ясно, что для этого потребуется ЗУ с потенциально бесконечным числом ячеек, чтобы разместить в нем типичные последовательности записей сколь угодно большой длины. В этом проявляется техническая нереализуемость идеального кодирования применительно к задаче хранения информации.
К идеальному результату можно приблизиться, укрупняя хранимые записи. На практике в устройствах хранения данных для ЭВМ (например, в накопителях на магнитных лентах и дисках) широко применятся так называемое блокирование записей. При этом группы записей объединяются в блоки, которые размещаются в ЗУ как некоторые единые укрупненные записи. Этим достигается более экономное использование информационной емкости ячеек.
Практическая реализация помехоустойчивого хранения информации основана на методах помехоустойчивого кодирования. Перед помещением записей в ЗУ искусственно увеличивается их избыточность за счет введения дополнительных контрольных символов. После считывания записей из ЗУ производится обнаружение и коррекция ошибок.
Рассмотрим теперь задачу поиска в следующей обобщенной форме. Пусть имеется файл, записи которого идентифицируются ключами. Множество запросов записей образуют последовательность аргументов поиска. Знания ключей и аргументов поиска могут подвергаться искажением из-за действия случайных помех при формировании файла и при подготовке запросов.
Возникает вопрос, при каких условиях возможен достоверный поиск информации, т.е. получение на каждый запрос именно тех записей которые требуются.
В соответствии с шенноновским подходом перейдем к информационным характеристикам:
Для последовательностей аргументов поиска определим среднюю энтропию аргументов. Если на аргументы действуют ошибки, то необходимо учесть увеличение средней энтропии вследствие ошибок;
Для множества записей файла определим информационную емкость ключа - максимальное количество информации, которое может содержаться в ключе файла. Если ключи файла могут содержать случайные ошибки, то необходимо учесть уменьшение информационной емкости ключа вследствие ошибок.
Тогда для информационных показателей будет справедлива следующая формулировка теоремы Шеннона для задачи поиска информации:
Для поиска в файле (с помехами и без помех) существует способ сколь угодно достоверного поиска нужных записей, если только средняя энтропия аргумента меньше информационной емкости ключа.
Применение алгоритма идеального кодирования в данной задаче потребует потенциально бесконечного укрупнения файла, чтобы производить поиск в качестве аргумента выступают типичные последовательности исходных аргументов. В этом проявляется техническая нереализуемость идеального кодирования применительно к задаче поиска информации.
Как упоминалось во второй главе, разработка технически реализуемых способов помехоустойчивого поиска в настоящее время находится в зачаточном состоянии своего развития. Имеющиеся здесь результаты существенно скромнее, чем, например, в помехоустойчивом кодировании, где создана обширная и глубокая математическая теория кодирования. В чем здесь дело? Почему бы не воспользоваться результатами теории кодирования для решения родственной задачи поиска.
Основная идея помехоустойчивого кодирования состоит в искусственном введении избыточности в сообщения по подачи их в канал с помехами. В большинстве задач поиска мы имеем дело с естественной избыточностью сообщений, на которую мы не можем активно воздействовать. Мы получаем уже искаженный аргумент поиска, например, невнятно произнесенную по телефону фамилию клиента, и можем рассчитывать только на естественную избыточность языка (естественная избыточность русского языка, как и большинства европейских языков, оставляет примерно 60 %).
Однако, учитывая принципиальную разрешимость этой задачи в свете результатов Шеннона, а также последние публикации по проблемам помехоустойчивого поиска можно надеяться, что эта проблема будет решена и технически.
Сжатие данных.
Закодированные сообщения передаются по каналам связи, хранятся в запоминающих устройствах, обрабатываются процессором. Объемы данных, циркулирующих в АСУ, велики, и поэтому в о многих случаях важно обеспечить такое кодирование данных, которое характеризуется минимальной длиной получающихся сообщений. Эта проблема сжатия данных. Решение её обеспечивает увеличение скорости передачи информации и уменьшение требуемой памяти запоминающих устройств. В конечном итоге это ведет к повышению эффективности системы обработки данных.
Существует два подхода (или два этапа) сжатия данных:
Сжатие, основанное на анализе конкретной структуры и смыслового содержания данных;
Сжатие, основанное на анализе статистических свойств кодируемых сообщений. В отличие от первого второй подход носит универсальный характер и может использоваться во всех ситуациях, где есть основания полагать, что сообщения подчиняются вероятностным законам. Далее мы рассмотрим оба этих подхода.
4.1. Сжатие на основе смыслового содержания данных
Эти методы носят эвристический, уникальный характер, однако основную идею можно пояснить следующим образом. Пусть множество содержит элементов. Тогда для кодирования элементов множества равномерным кодом потребуется двоичных знаков. При этом будут использованы все двоичные кодовые комбинации. Если используются не все комбинации, код будет избыточным. Таким образом, для сокращения избыточности следует попытаться очертить множество возможных значений элементов данных и с учетом этого произвести кодирование. В реальных условиях это не всегда просто, некоторые виды данных имеют очень большую мощность множества возможных значений. Посмотрим, как же поступают в конкретных случаях.
Переход от естественных обозначений к более компактным. Значения многих конкретных данных кодируются в виде, удобном для чтения человеком. При этом они содержат обычно больше символов, чем это необходимо. Например, дата записывается в виде «26 января 1982 г.» или в самой краткой форме: «26.01.82». при этом многие кодовые комбинации, например «33.18.53» или «95.00.11», никогда не используются. Для сжатия таких данных день можно закодировать пятью разрядами, месяц - четырьмя, год - семью, т.е. вся дата займет не более двух байтов. Другой способ записи даты, предложенный еще в средние века состоит в том, чтобы записывать общее число дней, прошедших к настоящему времени с некоторой точки отсчета. При этом часто ограничиваются четырьмя последними цифрами этого представления. Например, 24 мая 1967 года записывается в виде 0000 и отсчет дней от этой даты требует, очевидно, два байта в упакованном десятичном формате.
КОДИРОВАНИЕ ИНФОРМАЦИИ.
АБСТРАКТНЫЙ АЛФАВИТ
Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые будем называть буквами, не вкладывая в это слово привычного ограниченного значения (типа «русские буквы» или «латинские буквы»). Буква в данном расширенном понимании - любой из знаков, которые некоторым соглашением установлены для общения. Например, при привычной передаче сообщений на русском языке такими знаками будут русские буквы - прописные и строчные, знаки препинания, пробел; если в тексте есть числа - то и цифры. Вообще, буквой будем называть элемент некоторого конечного множества (набора) отличных друг от друга знаков. Множество знаков, в котором определен их порядок, назовем алфавитом (общеизвестен порядок знаков в русском алфавите: А, Б,..., Я).
Рассмотрим некоторые примеры алфавитов.
1, Алфавит прописных русских букв:
А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
2. Алфавит Морзе:
3. Алфавит клавиатурных символов ПЭВМ IBM (русифицированная клавиатура):
4. Алфавит знаков правильной шестигранной игральной кости:
5. Алфавит арабских цифр:
6. Алфавит шестнадцатиричных цифр:
0123456789ABCDEF
Этот пример, в частности, показывает, что знаки одного алфавита могут образовываться из знаков других алфавитов.
7. Алфавит двоичных цифр:
Алфавит 7 является одним из примеров, так называемых, «двоичных» алфавитов, т.е. алфавитов, состоящих из двух знаков. Другими примерами являются двоичные алфавиты 8 и 9:
8. Двоичный алфавит «точка, «тире»:. _
9. Двоичный алфавит «плюс», «минус»: + -
10. Алфавит прописных латинских букв:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
11. Алфавит римской системы счисления:
I V Х L С D М
12. Алфавит языка блок-схем изображения алгоритмов:
13. Алфавит языка программирования Паскаль (см. в главе 3).
^
КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ
В канале связи сообщение, составленное из символов (букв) одного алфавита, может преобразовываться в сообщение из символов (букв) другого алфавита. Правило, описывающее однозначное соответствие букв алфавитов при таком преобразовании, называют кодом. Саму процедуру преобразования сообщения называют перекодировкой. Подобное преобразование сообщения может осуществляться в момент поступления сообщения от источника в канал связи (кодирование) и в момент приема сообщения получателем (декодирование). Устройства, обеспечивающие кодирование и декодирование, будем называть соответственно кодировщиком и декодировщиком. На рис. 1.5 приведена схема, иллюстрирующая процесс передачи сообщения в случае перекодировки, а также воздействия помех (см. следующий пункт).
Рис. 1.5. Процесс передачи сообщения от источника к приемнику
Рассмотрим некоторые примеры кодов.
1. Азбука Морзе в русском варианте (алфавиту, составленному из алфавита русских заглавных букв и алфавита арабских цифр ставится в соответствие алфавит Морзе):
2. Код Трисиме (знакам латинского алфавита ставятся в соответствие комбинации из трех знаков: 1,2,3):
| А | 111 | D | 121 | G | 131 | J211 | M221 | P231 | S311 | V321 | Y331 |
| В | 112 | E | 122 | H | 132 | K212 | N222 | Q232 | T312 | W322 | Z332 |
| С | 113 | F | 123 | I | 133 | L213 | О223 | R233 | U313 | X323 | .333 |
Код Трисиме является примером, так называемого, равномерного кода (такого, в котором все кодовые комбинации содержат одинаковое число знаков - в данном случае три). Пример неравномерного кода - азбука Морзе.
3. Кодирование чисел знаками различных систем счисления см. §3.
ПОНЯТИЕ О ТЕОРЕМАХ ШЕННОНА
Ранее отмечалось, что при передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Так, например, если вы попытаетесь в ветреную погоду передать речевое сообщению человеку, находящемуся от вас на значительном расстоянии, то оно может быть сильно искажено такой помехой, как ветер. Вообще, передача сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны. При работе с кодированной информацией, искажаемой помехами, можно выделить следующие основные проблемы: установления самого факта того, что произошло искажение информации; выяснения того, в каком конкретно месте передаваемого текста это произошло; исправления ошибки, хотя бы с некоторой степенью достоверности.
Помехи в передачи информации - вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры - разговор по телефону, в трубке которого «трещит», вождение автомобиля в тумане и т.д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большойизбыточностью (в европейских языках - до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.
Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К.Шеннон.
^ Первая теорема Шеннона декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее число двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
Задача эффективного кодирования описывается триадой:
Х = {X 4i } - кодирующее устройство - В.
Здесь X, В - соответственно входной и выходной алфавит. Под множеством х i можно понимать любые знаки (буквы, слова, предложения). В - множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению х i изХ кодовую комбинацию, составленную из п i символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.
Для решения данной задачи должна быть известна вероятность Р i появления сообщения х i , которому соответствует определенное количество символов п i алфавита В. Тогда математическое ожидание количества символов из В определится следующим образом:
n cр = п i Р i (средняя величина).
Этому среднему числу символов алфавита В соответствует максимальная энтропия Нтаx = n ср log т. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H4mах ≥ Н(х), или п cр log т ≥ - Р i log Р i . В этом случае закодированное сообщение имеет избыточность п cр ≥ H(x) / log т, n min = H(x) / log т.
Коэффициент избыточности
К u = (H max – H (x )) / H max = (n cp – n min) / n cp
Выпишем эти значения в виде табл. 1.8. Имеем:
N min = H (x ) / log2 = 2,85, K u = (2,92 - 2,85) / 2,92 = 0,024,
Т.е. код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.
^ Таблица 1.8 Пример к первой теореме Шеннона
| N | Рх i | x i | Код | n i | п i - ∙ Р i | Рх i ∙ log Рх i |
| 1 | 0,19 | X 1 | 10 | 2 | 0,38 | -4,5522 |
| 2 | 0,16 | X 2 | 001 | 3 | 0,48 | -4,2301 |
| 3 | 0.16 | X 3 | 011 | 3 | 0,48 | -4,2301 |
| 4 | 0,15 | X 4 | 101 | 3 | 0,45 | -4,1054 |
| 5 | 0,12 | X 5 | 111 | 3 | 0,36 | -3,6706 |
| 6 | 0,11 | X 6 | 111 | 3 | 0,33 | - 3,5028 |
| 7 | 0,09 | X 7 | 1011 | 4 | 0,36 | -3,1265 |
| 8 | 0,02 | X 8 | 1001 | 4 | 0,08 | -3,1288 |
| Σ=1 | Σ=2,92 | Σ=2,85 |
^ Вторая теорема Шеннона гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. Таким образом, вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если скорость создания сообщений меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу со сколь угодно мглой частотой ошибок.
Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность Х = {xi} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины п вводится r символов и по каналу передается новая последовательность из п + r символов. Число возможных последовательностей длины и + т больше числа возможных последовательностей длины п. Множество всех последовательностей длины п + r может быть разбито на п подмножеств, каждому из которых сопоставлена одна из последовательностей длины п. При наличии помехи на последовательность из п + r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.
Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины п + r, и тем самым восстановить исходную последовательность длины п.
Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой проблемы.
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:
разработка принципов наиболее экономичного кодирования информации;
согласование параметров передаваемой информации с особенностями канала связи;
разработка приемов, обеспечивающих надежность передачи информации по каналам связи, т.е. отсутствие потерь информации.
Две последние задачи связаны с процессами передачи информации - они будут рассмотрены в гл. 5. Первая же задача - кодирование информации - касается не только передачи, но и обработки, и хранения информации, т.е. охватывает широкий круг проблем; частным их решением будет представление информации в компьютере. С обсуждения этих вопросов и начнем освоение теории кодирования.
3.1. Постановка задачи кодирования. Первая теорема Шеннона
Как отмечалось при рассмотрении исходных понятий информатики, для представления дискретных сообщений используется некоторый алфавит. Однако однозначное соответствие между содержащейся в сообщении информацией и его алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения хода из одного алфавита к другому, причем, такое преобразование не должно приводить к потере информации.
Введем ряд с определений.
Будем считать, что источник представляет информацию в форме дискретного сообщения, используя для этого алфавит, который в дальнейшем условимся называть первичным. Далее это сообщение попадает в устройство, преобразующее и представляющее его в другом алфавите - этот алфавит назовемвторичным .
Код - (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита .
(2) набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита .
Кодирование - перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов .
Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов .
Кодер - устройство, обеспечивающее выполнение операции кодирования .
Декодер - устройство, производящее декодирование .
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь .
Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление после передачи. Примером кодирования необратимого может служить перевод с одного естественного языка на другой - обратный перевод, вообще говоря, не восстанавливает исходного текста. Безусловно, для практических задач, связанных со знаковым представлением информации, возможность восстановления информации по ее коду является необходимым условием применения кода, поэтому в дальнейшем изложении ограничим себя рассмотрением только обратимого кодирования.
Кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а передача - с изменением состояния с течением времени (т.е. процессом). Эти состояния или сигналы будем называть элементарными сигналами - именно их совокупность и составляет вторичный алфавит.
Не обсуждая технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), попробуем дать математическую постановку задачи кодирования.
Пусть первичный алфавитА состоит из N знаков со средней информацией на знакI (A) , а вторичный алфавитВ- изМ знаков со средней информацией на знакI (В) . Пусть также исходное сообщение, представленное в первичном алфавите, содержитп знаков, а закодированное сообщение -т знаков. Если исходное сообщение содержитI st (A) информации, а закодированное - I fin (B),то условие обратимости кодирования, т.е.неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т.е.:
Отношение т/n, очевидно, характеризуетсреднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита - будем называть егодлиной кода илидлиной кодовой цепочки и обозначимК(А,В). Следовательно
Обычно N>M и I(А) > I(B), откуда К(А,В) > 1 , т.е. один знак первичного алфавита представляется несколькими знаками вторичного. Поскольку способов построения кодов при фиксированных алфавитахА и Б существует множество, возникает проблема выбора (или построения) наилучшего варианта - будем называть егооптимальным кодом. Выгодность кода при передаче и хранении информации - это экономический фактор, так как более эффективный код позволяет затратить на передачу сообщения меньше энергии, а также времени и, соответственно, меньше занимать линию связи; при хранении используется меньше площади поверхности (объема) носителя. При этом следует сознавать, что выгодность кода не идентична временной выгодности всей цепочки кодирование-передача-декодирование; возможна ситуация, когда за использование эффективного кода при передаче придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства, если эти операции производятся с его помощью).
Как следует из β.1), минимально возможным значением средней длины кода будет:
Данное выражение следует воспринимать как соотношение оценочного характера, устанавливающее нижний предел длины кода, однако, из него неясно, в какой степени в реальных схемах кодирования возможно приближение К(А,В) кK min (A,B). По этой причине для теории кодирования и теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. Первая - ее мы сейчас рассмотрим - затрагивает ситуацию с кодированием при отсутствии помех, искажающих сообщение. Вторая теорема относится к реальным линиям связи с помехами и будет обсуждаться в гл. 5.
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов .
Приведенное утверждение является теоремой и, следовательно, должно доказываться. Мы опустим его, адресовав интересующихся именно доказательной стороной к книге А. М. Яглома и И. М. Яглома . Для нас важно, что теорема открывает принципиальную возможность оптимального кодирования, т.е. построения кода со средней длиной К min (А,В). Однако необходимо сознавать, что из самой теоремы никоим образом не следует, как такое кодирование осуществить практически - для этого должны привлекаться какие-то дополнительные соображения, что и станет предметом нашего последующего обсуждения.
Из (3.2) видно, что имеются два пути сокращения K min (A,B):
уменьшение числителя - это возможно, если при кодировании учесть различие частот появления разных знаков в сообщении, корреляции двухбуквенные, трехбуквенные и т.п. (в п.2.3. было показано, что I 0 >I 1 >I 2 >…>I ∞);
увеличение знаменателя - для этого необходимо применить такой способ кодирования, при котором появление знаков вторичного алфавита было бы равновероятным, т.е. I (B) =log 2 M.
В частной ситуации, рассмотренной подробно К. Шенноном, при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков (то, что в п.2.3. мы назвали "первым приближением"), однако, их корреляции не отслеживаются - источники подобных сообщений называютсяисточниками без памяти. Если при этом обеспечена равная вероятность появления знаков вторичного алфавита, то, как следует из β.2), для минимальной средней длины кода оказывается справедливым соотношение:
В качестве меры превышения К(А,В) над K min (A, B) можно ввестиотносительную избыточность кода (Q(A,B):
Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, Q(A,B) → 0 приК(А,В) →К min (А,В). Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению K min (AB),равному отношению средних информации на знак первичного и вторичного алфавитов. Легко показать, что чем меньшеQ(A,B), тем I fin (B) ближе к Ist(A)) ,т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю .
Наиболее важной для практики оказывается ситуация, когдаМ = 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов - технически это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть этоимпульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называетсядвоичным. Знаки двоичного алфавита принято обозначать "О" и "1", но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1); тогда из β.3)
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита .
Применение формулы (3.4) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности дает:
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность идлительность сигналов, а также может соотносить некоторую последовательность сигналов с эталонной (таблицей кодов ).
Возможны следующие особенности вторичного алфавита, используемого при кодировании:
элементарные сигналы (0 и 1) могут иметь одинаковые длительности (τ 0 =τ 1) или разные (τ 0 ≠τ 1);
длина кода может быть одинаковой для всех знаков первичного алфавита (в этом случае код называется равномерным) или же коды разных знаков первичного алфавита могут иметь различную длину (неравномерный код);
коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов ).
Комбинации перечисленных особенностей определяют основу конкретного способа кодирования, однако, даже при одинаковой основе возможны различные варианты построения кодов, отличающихся своей эффективностью. Нашей ближайшей задачей будет рассмотрение различных схем кодирования для некоторых основ.
1.2. Первая теорема Шеннона
Ранее отмечалось, что при передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Так, например, если вы попытаетесь передать речевое сообщению в ветреную погоду человеку, находящемуся от вас на значительном расстоянии, то оно может быть сильно искажено такой помехой как ветер. Вообще, передача сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны.
При работе с кодированной информацией, искажаемой помехами, можно выделить следующие основные проблемы: установления самого факта того, что произошло искажение информации; выяснения того, в каком конкретно месте передаваемого текста это произошло; исправления ошибки – хотя бы с некоторой степенью достоверности.
Помехи в передачи информации - свойство отнюдь не только технических систем. Это - вполне обычное дело в быту. Пример был выше; другие примеры - разговор по телефону, в трубке которого "трещит", вождение автомобиля в тумане и т.д. Чаще всего человек вполне прилично справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 70%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение "в словох всо глосноо зомононо боквой о". Здесь 26% символов "поражены", однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.
Например, каждый фрагмент текста ("предложение") передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Отсюда следует задача устранения избыточности, или эффективного кодирования. Впервые теоретическое исследование такого рода проблем предпринял К.Шеннон.
Первая теорема Шеннона о передаче информации, которая называется также основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак кодируемого алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.
Используя понятие избыточности кода, можно дать более короткую формулировку теоремы:
При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Данные утверждения являются теоремами и, следовательно, должны доказываться, однако доказательства мы опустим. Для нас важно, что теорема открывает принципиальную возможность оптимального кодирования. Однако необходимо сознавать, что из самой теоремы никоим образом не следует, как такое кодирование осуществить практически – для этого должны привлекаться какие-то дополнительные соображения, что и станет предметом последующего обсуждения.
Таким образом, оптимальное кодирование принципиально возможно.
Наиболее важна для практики ситуация, когда М=2, то есть информацию кодируют лишь двумя сигналами 0 и 1.
Шенноном была рассмотрена ситуация, когда при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков, а также равная вероятность появления знаков вторичного алфавита. Тогда:
К min (А, В)= I (A) / log 2 M= I (A) ,
здесь I (A) - средняя информация на знак первичного алфавита.
Ограничим себя ситуацией, когда M = 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов – наиболее просто реализуемый вариант. Подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1. Удобство двоичных кодов и в том, что каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1); тогда из (1), теоремы Шеннона:
I 1 (A) ≤ K (2)
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех передачи средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Определение количества переданной информации при двоичном кодировании сводится к простому подсчету числа импульсов (единиц) и пауз (нулей). При этом возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть одинаковым (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:
Таблица 1. Варианты сочетаний
|
Длительности элементарных сигналов |
Кодировка первичных символов (слов) |
Ситуация |
|
одинаковые |
равномерная |
|
|
одинаковые |
неравномерная |
|
|
равномерная |
||
|
неравномерная |
В случае использования неравномерного кодирования или сигналов разной длительности (ситуации (2), (3) и (4)) для отделения кода одного знака от другого между ними необходимо передавать специальный сигнал – временной разделитель (признак конца знака) или применять такие коды, которые оказываются уникальными, т.е. несовпадающими с частями других кодов. При равномерном кодировании одинаковыми по длительности сигналами (ситуация (1)) передачи специального разделителя не требуется, поскольку отделение одного кода от другого производится по общей длительности, которая для всех кодов оказывается одинаковой (или одинаковому числу бит при хранении).
Длительность двоичного элементарного импульса показывает, сколько времени требуется для передачи 1 бит информации. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время. Таким образом, задачу оптимизации кодирования можно сформулировать в иных терминах: построить такую систему кодирования, чтобы суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.
Если имеется источник информации с энтропией Н(х) и канал связи с пропускной способностью С, то если С > H(X), то всегда можно закодировать достаточно длинное сообщение таким образом, что оно будет передано без задержек. Если же, напротив, С
Первая теорема Шеннона декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее количество двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
Первая теорема Шеннона (переформулировка).
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Какие же могут быть особенности вторичного алфавита при кодировании:
Элементарные коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (≠).
Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)
Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).
1.3 Вторая теорема Шеннона
Отношение пропускной способности канала связи к скорости неискаженной передачи символов алфавита передаваемого сообщения должно быть больше или равно энтропии передачи одного символа.
Вторая теорема Шеннона гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. Вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если скорость создания сообщений меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу со сколь угодно малой частотой ошибок.
Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность X={x i } кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины n вводится r символов по каналу передается новая последовательность из n + r символов. Число возможных последовательностей длины n + r больше числа возможных последовательностей длины n. Множество всех последовательностей длины n + r может быть разбито на n подмножеств, каждому из которых сопоставлена одна из последовательностей длины n. При наличии помехи на последовательность из n + r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.Кодирование информации (4)Реферат >> Информатика
Сожержание I. История кодирования информации………………………………..3 II. Кодирование информации…………………………………………4 III. Кодирование текстовой информации…………………………….4 IV. ... , и человечество в целом. Но решать задачу кодирования информации человечество начало задолго до...
Кодирование и шифрование информанции
Реферат >> ИнформатикаДрузей. Тогда-то и возникла задача защиты этой переписки от чрезмерно... пытались использовать для решения этой задачи самые разнообразные методы, и... программных средств на универсальную систему кодирования . Кодирование графических данных Если рассмотреть с...
Кодирование чисел, символов и графической информации, единицы измерения данных
Контрольная работа >> Информатика... №2………………………………………..8 ПРАКТИЧЕСКОЕ ЗАДАНИЕ №3………………………………………..9 СПИСОК ЛИТЕРАТУРЫ………………………………………………..11 КОДИРОВАНИЕ ЧИСЕЛ, СИМВОЛОВ И ГРАФИЧЕСКОЙ ИНФОРМАЦИИ, ЕДИНИЦЫ... вычисление функции: Y = Алгоритм решения данной задачи будет иметь вид: По полученному...
Кодирование речевой информации
Реферат >> Информатика... задача , с которой метод частотной селекции принципиально не может справиться. Описание метода кодирования ... Вступление 2 Система кодирования речи 4 Обоснование выбора метода кодирования 4 Описание метода кодирования 5 Генератор псевдослучайных...
Пусть имеется источник информации Х и приёмник У, связанные каналом К. Известна производительность источника информации Н 1 (Х), т.е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источником в единицу времени). Известна пропускная способность канала С 1 , т.е. максимальное количество информации, которое способен передать канал в ту же единицу времени. Возникает вопрос: какой должна быть пропускная способность канала, чтобы он справлялся со своей задачей, т.е. чтобы информация от источника к приёмнику поступала без задержки?
Несмотря на то, что ответ и так очевиден, он даётся в первой теореме Шеннона.
1-я теорема Шеннона:
Если пропускная способность канала связи С 1 больше энтропии источника информации в единицу времени
С 1 > Н 1 (Х),
то всегда можно закодировать достаточно длинное сообщение так, чтобы оно передавалось каналом связи без задержки.
Если же, напротив,
С 1 < Н 1 (Х),
то передача информации без задержек невозможна.
Передача информации с искажениями.
Пропускная способность канала с помехами.
И 1-я теорема Шеннона, и оба рассмотренные нами методы кодирования относятся к передаче информации без ошибок. В действительности это процесс неизбежно сопровождается ошибками (искажениями). Канал передачи, в котором возможны искажения, называется каналом с помехами (или шумами).
Совершенно очевидно, что наличие помех приводит к потере информации. Чтобы в условиях наличия помех получить на приёмнике требуемый объём информации, необходимо принимать специальные меры. Одной из таких мер является введение так называемой «избыточности». Известно, что все живые языки обладают некоторой избыточностью, доходящей до 50% (т.е.50% букв мы могли бы вообще не произносить или перепутывать их местами:-)).
Вот пример: По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бквуы мгоут селдовтаь в плоонм бсепордяке, всё-рвано ткест чтаитсея без побрелм.
Надеюсь, вы поняли, что здесь написано))))
Однако для безошибочной передачи естественная избыточность языка может оказаться как чрезмерной, так и недостаточной: всё зависит от того, насколько велика опасность искажений. С помощью методов теории информации можно для каждого уровня помех найти нужную степень избыточности источника информации.
Рассмотрим, например, такую задачу. Канал связи К передаёт от источника информации Х к приёмнику У элементарные символы 0 и 1 в количестве k символов в единицу времени. В процессе передачи каждый символ, независимо от других, с вероятностью μ может быть искажён (т.е. заменён противоположным). Требуется найти пропускную способность канала.
Определим сначала максимальную информацию на один символ, которую может передавать канал. Пусть источник производит символы 0 и 1 с вероятностями p и 1-p.
Тогда энтропия источника будет
Н(Х)=-p log p - (1-p) log (1-p).
Если бы передача сообщений не сопровождалась ошибками, то количество информации на один символ было бы равно самой энтропии системы Х. При наличии ошибок оно будет меньше:
I = H(Y) - H(Y/X).
Чтобы найти полную условную энтропию Н(У/Х), найдём сначала частные условные энтропии: Н(У/х 1) и Н(У/х 2).
Вычислим Н(У/х 1); для этого предположим, что передан символ 0. Найдём условные вероятности того, что при этом система У находится в состоянии у 1 =0 и в состоянии у 2 =1. Первая из них равна вероятности того, что сигнал не перепутан:
Р(у 1 /х 1)=1-µ;
вторая - вероятности того, что сигнал перепутан:
Р(у 2 /х 1)=µ.
Условная энтропия Н(У/х 1) будет:
Н(У/х 1)=-Σ Р(у i /x 1) log P(y i /x 1) = -(1-µ) log (1-µ) - µ log µ.
Найдём теперь условную энтропию системы У при условии, что передан сигнал 1:
Р(у 1 /х 2)=µ; Р(у 2 /х 2)=1-µ,
Н(У/х 2)= - µ log µ - (1-µ) log (1-µ).
Таким образом
Н(У/х 1)= Н(У/х 2).
Полная условная энтропия Н(У/Х) получится, если осреднить условные энтропии с учётом вероятностей р и 1-р. Так как частные условные энтропии равны, то
Н(У/Х)= - µ log µ - (1-µ) log (1-µ).
Вывод: условная энтропия Н(У/Х) совсем не зависит от того, с какими вероятностями встречаются символы 0 и 1 в передаваемом сообщении, а зависит только от вероятности ошибки µ.
Теперь вычислить информацию, передаваемую одним символом:
I = H(Y) - H(Y/X) = - r log r - (1-r) log (1-r) - - µ log µ - (1-µ) log (1-µ) =
= [η(r) + η(1-r)] - [η(µ) + η(1-µ)],
Где r - вероятность того, что на выходе появится символ 0.
Мы знаем, что энтропия и количество информации максимально при равновероятных сигналах, т.е. (в нашем случае) при р=1/2. Следовательно, максимальное количество информации, передаваемое одним символом
I max = 1 - [η(µ) + η(1-µ)],
А пропускная способность канала связи будет равна
С= k(1 - [η(µ) + η(1-µ)]).
Заметьте, что η(µ) + η(1-µ) - это энтропия системы, имеющей 2 возможных состояния с вероятностями µ и 1-µ. Она характеризует потерю информации на один символ, связанную с наличием помех.
Пример 1. Определить пропускную способность канала связи, способного передавать 100 символов 0 или 1 в единицу времени, причем каждый из символов искажается (заменяется противоположным) с вероятностью µ=0,001.
η(µ) = η(0,001) = 0,0664
η(1-µ) = 0,0144
η(µ) + η(1-µ) = 0,0808
На один символ теряется информация 0,0808 бит. Пропускная способность канала равна
С = 100(1-0808) = 91,92 ≈ 92 бит в единицу времени.
Зная пропускную способность канала, можно определить верхний предел скорости передачи информации по каналу с помехами. К этому случаю относится вторая теорема Шеннона.
2-я теорема Шеннона:
Пусть имеется источник информации Х, энтропия которого в единицу времени равна Н 2 (Х), и канал с пропускной способностью С 2 . Тогда, если
Н 2 (Х) >С 2 ,
То при любом кодировании передача сообщений без задержек и искажений невозможна. Если же
Н 2 (Х) < С 2 ,
То всегда можно достаточно длинное сообщение закодировать так, чтобы оно было передано без задержек и искажений с вероятностью, сколь угодно близкой к единице.
Пример 2. Имеются источник информации с энтропией в единицу времени Н(Х) = 100 бит и 2 канала связи; каждый из них может передавать в единицу времени 70 двоичных знаков (0 или 1); каждый двоичный знак заменяется противоположным с вероятностью µ=0,1. Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником?
Решение: Определяем потерю информации на один символ:
η(µ) + η(1-µ) = 0,332+0,137=0,469 бит
Максимальное количество информации, передаваемое по одному каналу в единицу времени:
С = 70(1-0,469) = 37,2 бит.
Максимальное количество информации, которое может быть передано по двум каналам в единицу времени:
37,2*2 = 74,7 бит,
чего недостаточно для обеспечения передачи информации от источника.
| 2 |
