Прямая теорема шеннона для источника общего вида. «Теория информации и кодирования

30.03.2019

Кодирование информации

Основные понятия

Выше упоминались теоремы Шеннона о кодировании сообщений. Интуитивно понятно, что кодирование – это операция преобразования информации в форму, требуемую для последующей обработки (передачи по каналу связи, хранения в памяти вычислительной системы, использования для принятия решения и т.д.). Также понятно, что при построении любой информационной системы обойтись без кодирования невозможно: любое представление информации подразумевает использование каких-нибудь кодов. Поэтому далее подробно разберем теоретические основы кодирования информации.

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

Слово α 1 называют началом (префиксом) слова α , если существует слово α 2 , такое, что α = α 1 α 2 ; при этом слово α 1 называют собственным началом слова α , если α 2 – не пустое слово. Длина слова – это число букв в слове (пустое слово имеет длину 0). Запись α 1 α 2 обозначает соединение (конкатенацию) слов α 1 и α 2 . Слово α 2 называют окончанием (суффиксом) слова α , если существует слово α 1 , такое, что α = α 1 α 2 ; при этом слово α 2 называют собственным окончанием слова α , если α 1 – не пустое слово. Пустое слово по определению считается началом и окончанием любого слова α .

Рассмотрим алфавит B = {0, 1, …, D – 1}, где D ≥ 2, и произвольное множество C . Произвольное отображение множества C в множество слов в алфавите B называют D -ичным кодированием множества C (при D = 2 кодирование будет двоичным). Обратное отображение называют декодированием. Приведем примеры кодирований.

1. Кодирование множества натуральных чисел, при котором числу n = 0 ставится в соответствие слово e (0) = 0, а числу n ≥ 1 двоичное слово

e (n ) = b 1 b 2 … b l ( n )

наименьшей длины, удовлетворяющее условию

Очевидно, что b 1 = 1, 2 l ( n ) – 1 ≤ n < 2 l ( n ) и, следовательно

l (n ) = + 1 = ]log(n + 1)[,

где [x ] и ]x [ обозначает соответственно наибольшее целое число, не превосходящее x , и наименьшее целое число, превосходящее x . Слово e (n ) называют двоичной записью числа n , а данное кодирование – представление чисел в двоичной системе счисления. Данное кодирование является взаимно однозначным, поскольку при n 1 ≠ n 2 слова e (n 1) и e (n 2) различны. В таблице 5.1 приведено представление первых 16 натуральных чисел в двоичной системе счисления.

Таблица 5.1

Кодирование e (n )

n	e (n )	n	e (n )	n	e (n )	n	e (n )

2. Кодирование первых 2 k натуральных чисел, при котором каждому числу n (0 ≤ n < 2 k ) ставится в соответствие слово

e k (n ) = 0 k – l ( n ) e (n ),

где запись 0 k – l ( n ) обозначает слово, состоящее из k – l (n ) нулей, e (n ) – представление числа n в двоичной системе счисления, рассмотренное выше. Данное кодирование для первых 16 натуральных чисел (k = 4) приведено в таблице 5.2.

Таблица 5.2

Кодирование e k (n )

n	e k (n )	n	e k (n )	n	e k (n )	n	e k (n )

Пусть A = {a i , i = 1, 2, …} – конечный или счетный алфавит, буквы которого занумерованы натуральными числами. В этом случае кодирование букв алфавита A можно задать последовательностью D -ичных слов V = {v i , i = 1, 2, …}, где v i есть образ буквы a i . Такие последовательности слов (из множества V ) называют кодами (алфавита А ). Если задан код V алфавита А , то кодирование слов, при котором каждому слову a i 1 a i 2 …a ik ставится в соответствие слово v i 1 v i 2 …v ik , называют побуквенным кодированием.

При переходе от взаимно однозначного кодирования букв алфавита к побуквенному кодированию слов в алфавите свойство взаимной однозначности может не сохраниться. Например, кодирование e (n ) не сохраняет данное свойство, а кодирование e k (n ) его сохраняет. Свойство взаимной однозначности сохраняют разделимые коды. Код V = {v i , i = 1, 2, …} называют разделимым, если из каждого равенства вида

v i 1 v i 2 …v ik = v j 1 v j 2 …v jl

следует, что l = k и v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = v jl . Разделимые коды называют также однозначно декодируемыми кодами.

К классу разделимых кодов принадлежат префиксные коды. Код V = {v i , i = 1, 2, …} называют префиксным, если никакое слово v k не является началом (префиксом) никакого слова v l , l ≠ k . Если каждое слово префиксного кода заменить наименьшим его началом, которое не является началом других кодовых слов, то полученный код также будет префиксным. Такую операцию называют усечением префиксного кода.

Для произвольного кода V , состоящего из различных слов, можно построить кодовое дерево. Это ориентированный граф, не содержащий циклов, в котором вершина β 1 соединена с вершиной β 2 ребром, направленным от β 1 к β 2 , тогда и только тогда, когда β 2 = β 1 b , где b Î B = {0, 1, …, D – 1}, D ≥ 2. Для префиксных кодов (и только для них) множество кодовых слов совпадает с множеством концевых вершин (вершин, из которых не исходят ребра) кодового дерева.

Основные теоремы кодирования

Свойства кодов, полезные для их практического применения, определяются основными теоремами кодирования.

Теорема 5.1. Неравенство Крафта. Для существования однозначно декодируемого (разделимого) кода, содержащего N кодовых слов в множестве {0, 1, D – 1} с длинами n 1 , n 2 , …, n N , необходимо и достаточно, чтобы выполнялось неравенство

Доказательство. Представим, что имеется кодовое дерево для префиксного кода. Корень кодового дерева образует уровень 0, вершины, связанные с корнем, – уровень 1 и т.д. Возможное количество вершин на k -м уровне обозначим как D k . Каждая вершина k -го уровня порождает точно D n – k вершин n -го уровня.

n 1 ≤ n 2 ≤…≤ n N = n .

Очевидно, что кодовое слово длины k запрещает в точности D n – k возможных концевых вершин (вершин последнего уровня). Тогда все кодовые слова префиксного кода запрещают концевых вершин. Так как общее число концевых вершин равно D n , то справедливо неравенство

из которого следует, что

Таким образом, неравенство Крафта доказано.

В результате доказательства теоремы 5.1 делается вывод о том, что существуют хотя бы префиксные коды, которые являются однозначно декодируемыми кодами, с длинами кодовых слов n 1 , n 2 , …, n N , удовлетворяющими неравенству Крафта. Следующая теорема, называемая утверждением Мак-Миллана, обобщает данный вывод на все однозначно декодируемые коды.

Теорема 5.2. Неравенство Мак-Миллана. Каждый однозначно декодируемый код удовлетворяет неравенству Крафта.

Доказательство. Возведем сумму в степень L :

. (5.1)

Пусть A k – число комбинаций, содержащих L кодовых слов с суммарной длиной k . Тогда выражение (6.1) можно представить в виде

где L max – максимальная длина сообщения, содержащего L кодовых слов. Если код является однозначно декодируемым, то все последовательности из L кодовых слов суммарной длины k различны. Так как имеется всего D k возможных последовательностей, то A k ≤ D k и тогда

Так как L – это число независимых кодовых слов, которые используются для построения всех возможных последовательностей длины, не превышающей L max . Поэтому L ≤ L max и . А из этого следует, что

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

Следующие теоремы связывают энтропию источника сообщений и среднюю длину кодового слова.

Теорема 5.3. Теорема кодирования источников I. Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H (X ) существует D -ичный префиксный код, в котором средняя длина кодового слова удовлетворяет неравенству

. (5.2)

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

Для этого используем определение энтропии и неравенство Крафта:

Для доказательства правой части неравенства (6.2) перепишем неравенство Крафта в следующем виде:

Затем выберем для каждого слагаемого такое наименьшее целое n i , при котором

Так как неравенство Крафта при таком выборе сохраняется, то можно построить соответствующий префиксный код. Так как n i – наименьшее целое, то для n i – 1 справедливо

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

Теорема 5.4. Теорема кодирования источников II. Для блока длины L существует D -ичный префиксный код, в котором средняя длина кодового слова на один символ удовлетворяет неравенству

где .

Доказательство. Здесь в качестве единиц сообщений рассматриваются блоки символов и H (X 1 , X 2 , …, X L) – это энтропия источника сообщений, приходящаяся на блок из L символов. Для доказательства теоремы можно воспользоваться теоремой о кодировании источников I:

Кроме того, так как минимально достижимой длиной кодового слова на символ является величина , то при D = 2 избыточность кода можно определить по формуле .

1 | |

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

Теорема: При кодировании сообщения,разбитого наN -буквенные блоки можно,вы-брав N достаточно большим добиться того, чтобы среднее число k элементарных дво-ичных сигналов, приходящихся на одну букву исходного сообщения было сколь угодно близко к H . Замечание: Очень длинное сообщение из M букв может быть закодировано

при помощи сколь угодно близкого к числу MH (но большего) числа элементарных сиг-налов, если только предварительно разбить это сообщение на достаточно длинные блоки из N букв и сопоставлять отдельные кодовые обозначения сразу целым блокам. Методы кодирования блоков могут быть самыми различными (например, можно использовать методы Шеннона - Фано, Хаффмана)

m-ичные коды

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

Ввиду важности кодов Хаффмана остановимся на этом вопросе подробнее. Сжатие ал-фавита, при котором m букв заменяются на одну приводит к уменьшению числа букв на m − 1.Так,как для построения m -ичного кода,очевидно,требуются,чтобы последова-тельность сжатий привела нас к алфавиту из m букв (сопоставляемых m сигналам кода), то необходимо, чтобы число n букв первоначального алфавита было представимо в виде n = m + s (m − 1),где s -целое число сжатий.

Этого всегда можно добиться, добавив, если нужно, к первоначальному алфавиту ещё несколько "фиктивных букв", вероятности появления которых считаются равными 0. По-сле этого, построение m -ичного кода Хаффмана производится точно так-же, как и в случае двоичного кода.

Пример: В случае алфавита из6букв,имеющих вероятности0: 4; 0: 2; 0: 2; 0: 1; 0: 05; 0: 05.Для построения троичного кода Хаффмана надо присоединить к нашему алфавиту ещё одну фиктивную букву с нулевой вероятностью и поступать, как указано в таблице:

Номер буквы

Вероятности и кодовые обозначения

Исходный алфавит A

Сжатый алфавит A 1

Сжатый алфавит A 2

0: 4 - 0

0: 2 - 2

0: 4 - 1

0: 2 - 10

0: 2 - 2

0: 1 - 11

0: 2 - 11

0: 05 - 120

0: 05 - 121

0 - ---

Теорема:Любыеn чиселk 1 ; k 2 ; : : : ; k n ,удовлетворяющие неравенству

+ : : : +

6 1 (∗ ):

Любые из k n чисел являются длинами сообщений некоторого m -ичного

m k n

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

Это утверждение (∗ ) впервые было доказано в 1949 году американским учёным Л.Крафтом и позднее было обобщено Б. Макмилланом, поэтому неравенство (∗ ) часто называют неравенством Крафта - Макмиллана. Используя неравенство (∗ ) можно полу-чить следующий результат:

Теорема: основная теорема о кодировании дляm -ичных кодов.При любом методе коди-рования, использующем m -мчнный код среднее число k элементарных сигналов, прихо-дящихся на одну букву сообщения никогда не может быть меньше отношения log H m , где H - энтропия одной букв сообщения. Однако, оно всегда может быть сделано сколь угодно близким к этой величине, если кодировать сразу достаточно длинные блоки из N букв.

Следствие: Если по линии связи за единицу времени можно передатьL элементарныхсигналов, принимающих m различных значений, то скорость передачи сообщений по

скоростью, сколь угодно близкой к v (но меньшей v ) является возможной. Величина C = L · log m зависит лишь от характеристик самой линии связи,в то время,как знаме-натель H характеризует передаваемое сообщение. Величина C указывает наибольшее количество единиц информации, которое можно передать по линии связи за единицу времени. Она называется пропускной способностью линии связи.

Прямая теорема Шеннона для источника общего вида Не следует путать с другими теоремами Шеннона .

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

Прямая теорема

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

В качестве доказательства теоремы исследуются характеристики кода Шеннона-Фано . Данный код удовлетворяет условиям теоремы, и он обладает указанными свойствами.

Обратная теорема

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

Для любого разделимого кода с длинами w 1 ,w 2 ,...,w K средняя длина сообщений больше или равна энтропии источника U , нормированный на двоичный логарифм от числа букв D в алфавите кодера:

Литература

Габидулин, Э. М. , Пилипчук, Н. И. §3.4 Теоремы Шеннона для источника // Лекции по теории информации. - М .: МФТИ , 2007. - С. 49-52. - 214 с. - ISBN 5-7417-0197-3

Wikimedia Foundation . 2010 .

Смотреть что такое "Прямая теорема Шеннона для источника общего вида" в других словарях:

Не следует путать с другими теоремами Шеннона. Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности… … Википедия

В Википедии есть статьи о других людях с такой фамилией, см. Шеннон. Клод Элвуд Шеннон Claude Elwood Shannon … Википедия

Клод Элвуд Шеннон (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории… … Википедия

- (англ. Claude Elwood Shannon; родился 30 апреля 1916, Петоцки (Petoskey, Michigan) Мичиган, США, умер 24 февраля 2001, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории информации, в… … Википедия

Программа курса

«Теория информации и кодирования»

Лекции читаются на 4-м курсе, VII-семестр,

51 час, лектор доцент

Понятие информации, энтропии. Системы связи. Дискретные источники. Описание источника при помощи случайного процесса. Статистическая независимость. Марковские источники. Эргодичность. Эргодичность бернуллиевского источника.

Вывод формулы энтропии (по Фадееву). Взаимная информация, и её свойства. Свойства энтропии. Теорема о максимальном значении энтропии. Энтропия в единицу времени источника сообщений.

Задача кодирования дискретного источника кодами равной длины. Скорость кодирования. Высоковероятностные множества. Прямая и обратная теоремы кодирования дискретного источника кодами равной длины.

Задача кодирования источника кодами неравной длины. Стоимость кодирования. Однозначно дешифрируемые коды. Префиксные коды. Побуквенное кодирование. Необходимое и достаточное условие однозначной дешифрируемости кода. Полные коды. Теорема кодирования дискретного источника кодами неравной длины. Алгоритмы построения оптимальных кодов (Фано, Шеннона, Хаффмена). Построение бинарного оптимального кода при равновероятностном распределении входных вероятностей. Приложение результатов теории информации при доказательстве нижних и верхних оценок сложности реализации булевых функций в некоторых классах управляющих систем. Метод построения оптимального кода при условии, что неизвестно распределение вероятностей букв источника. Теорема Маркова об однозначной дешифрируемости кода. Адаптивные алгоритмы сжатия информации.

Дискретный канал без памяти. Двоичный симметричный канал. Скорость передачи информации в канале. Пропускная способность канала. Расширенный канал и его пропускная способность. Решающие схемы и группировки наблюдений. Вероятность ошибочной передачи информации. Неравенство Файнстейна. Прямая теорема кодирования канала без памяти. Неравенство Фано. Теорема обработки информации . Обращение теоремы кодирования.

Теория помехоустойчивого кодирования. Критерий максимального правдоподобия. Кодовое расстояние. Коды с проверкой на четность. Порождающая и проверочные матрицы. Синдром. Алгоритм декодирования для кодов с проверкой на четность. Линейные коды и алгоритм их декодирования. Граница Хэмминга. Код Хэмминга. Циклические коды. Кодирования и декодирование циклических кодов.

ЛИТЕРАТУРА

1. Галлагер Р. Теория информации и надежная связь., М., Сов. Радио, 1979.

2. Кричевский Е. Лекции по теории и информации, Новосибирск, НГУ, 1966.

3. Колесник В., Полтырев Г. Курс теории информации, Наука, 1982.

4. Файнстейн А. Основы теории информации, М., ИЛ, 1960.

5. Питерсон В., Уэлдон Ф. Коды, исправляющие ошибки, М., Мир, 1976.

6. Бэрлекамп Алгебраическая теория кодирования, М., Мир, 1971.