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

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

Теорема Шеннона - Хартли

В данной теореме определено, что достичь максимальной скорости (бит/с) можно путём увеличения полосы пропускания и мощности сигнала и, в то же время, уменьшения шума.

Теорема Шеннона - Хартли ограничивает информационную скорость (бит/с) для заданной полосы пропускания и отношения «сигнал/шум». Для увеличения скорости необходимо увеличить уровень полезного сигнала, по отношению к уровню шума.

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

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

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

Значение теоремы

Пропускная способность канала и формула Хартли

Сравнивая пропускную способность канала и формулу Хартли, мы можем найти эффективное число M {\displaystyle M} различимых уровней:

Взятие квадратного корня по сути возвращает отношение мощностей к отношению напряжений, таким образом число уровней приблизительно равно отношению среднеквадратичной амплитуды сигнала к шумовому стандартному отклонению. Это подобие в форме между пропускной способностью по Шеннону и формулой Хартли не стоит понимать буквально, что для безошибочной передачи достаточно M {\displaystyle M} уровней сигнала. Избыточное кодирование для устранения ошибок потребует большего числа уровней, но предельная скорость передачи данных, к которой можно приблизиться с кодированием, эквивалентна использованию того самого M {\displaystyle M} из формулы Хартли.

Передача информации

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

Для осуществления такого процесса информация должна быть некоторым образом оформлена (представлена). Для представления информации используются различные знаковые системы - наборы заранее оговоренных смысловых символов: предметов, картинок, написанных или напечатанных слов естественного языка. Представленная с их помощью семантическая информация о каком-либо объекте, явлении или процессе называется сообщением.

Первая теорема Шеннона о передаче информации, которая называется также основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:

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

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

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

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

Далее в основном ограничим себя ситуацией, когда M = 2 , т.е. для представления кодов в линии связи используется лишь два типа сигналов – с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1", но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1) ; тогда из (1), теоремы Шеннона:

I 1 (A) K (2)

и первая теорема Шеннона получает следующую интерпретацию:

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

Применение формулы (2) для двоичного кодирования дает:

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

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

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

Лекция 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)

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

Отметим следующие особенности двоичного вторичного алфавита, используемого при кодировании:

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