Основные понятия выше упоминались теоремы шеннона о кодировании сообщений. Основные теоремы кодирования

02.05.2019 Windows 7, XP

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

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

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

Пусть 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 | |

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

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

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

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

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

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

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

Для любого разделимого кода с длинами 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, Медфорд, Массачусетс, США) американский математик и электротехник, один из создателей математической теории информации, в… … Википедия

Работа добавлена на сайт сайт: 2016-03-30

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. Кодирование информации

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. Основные понятия

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

Пусть 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 кодирование будет двоичным). Обратное отображение называют декодированием. Приведем примеры кодирований.

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 натуральных чисел в двоичной системе счисления.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.1

" xml:lang="ru-RU" lang="ru-RU"> Кодирование " xml:lang="en-US" lang="en-US">e " xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n " xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

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.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5. " xml:lang="en-US" lang="en-US">2

" xml:lang="ru-RU" lang="ru-RU"> Кодирование " xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n " xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0000	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">0100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">0001	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">0101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">0010	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">0110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">0011	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">0111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

Пусть 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.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) перепишем неравенство Крафта в следующем виде:

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

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

Тогда

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

где.

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

Теорема о кодировании источников II позволяет утверждать, что существуют такие способы кодирования для достаточно длинного сообщения, что средняя длина кодового слова может быть сделана сколь угодно близкой к величине. Действительно, при L  ∞, H L (X )  H , где H энтропия источника сообщений на один символ, справедливо неравенство

, (5.3)

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

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

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. Оптимальное кодирование

Задача построения оптимального кода заключается в отыскании целых положительных чисел n 1 , n 2 , …, n N , минимизирующих среднюю длину кодового слова при условии выполнения неравенства Крафта:

При построении кодов в случае алфавита A = { a i , i = 1, 2, …, N } с известным распределением вероятностей P = { p i , i = 1, 2, …, N } без ограничения общности можно считать, что буквы алфавита A занумерованы в порядке убывания их вероятностей, т.е. p 1 ≥ p 2 ≥ … ≥ p N . Кроме того, будем рассматривать только двоичные коды.

Известны два метода (Фано и Шеннона) построения кодов, близких к оптимальным. Метод Фано заключается в следующем. Упорядоченный в порядке убывания вероятностей список букв делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части символ 1. Далее точно также поступают с каждой из полученных частей, если она содержит, по крайней мере, две буквы. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве. Каждой букве ставится в соответствие последовательность символов, приписанных в результате этого процесса данной букве. Легко видеть, что полученный код является префиксным.

Метод Шеннона применим лишь в том случае, когда все вероятности положительны. Он состоит в том, что букве a i , имеющей вероятность p i > 0, ставится в соответствие последовательность из n i = ] log (1/ p i )[ первых после дробной точки цифр разложения числа в бесконечную дробь (для a 1 полагаем, что q 1 = 0). Поскольку при l > k (в силу того, что p l ≤ p k ) n l ≥ n k и, то полученный таким образом код является префиксным. На основе полученного префиксного кода строится усеченный префиксный код, который и является результатом кодирования по методу Шеннона.

Пусть, например, имеется множество букв A = { a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 } с распределением вероятностей P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}. Выполним кодирование букв по методу Фано.

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

A 1 = { a 1 , a 2 , a 3 }, P 1 = {0.2, 0.2, 0.19};

A 2 = { a 4 , a 5 , a 6 , a 7 }, P 2 = {0.12, 0.11, 0.09, 0.09}.

2. Припишем буквам из первой части символ 0, а буквам второй части символ 1:

A 1 = { a 1 /0, a 2 /0, a 3 /0} ;

A 2 = { a 4 /1, a 5 /1, a 6 /1, a 7 /1}.

3. Повторим последовательно указанные действия для каждой из частей по отдельности. В результате получим :

A 1 1 = { a 1 /00};

A 121 = { a 2 /010};

A 122 = { a 3 /011};

A 211 = { a 4 /100};

A 212 = { a 5 /101};

A 221 = { a 6 /110};

A 222 = { a 7 /111}.

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

Процесс кодирования по методу Фано удобно оформлять в виде таблицы. Для рассматриваемого примера он приведен в таблице 5.3.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.3

" xml:lang="ru-RU" lang="ru-RU"> Кодирование по методу Фано

" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0.20	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU"> 0	" xml:lang="ru-RU" lang="ru-RU"> 00
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">2	" xml:lang="ru-RU" lang="ru-RU">0.20		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">010
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">3	" xml:lang="ru-RU" lang="ru-RU">0.19			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">011
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">4	" xml:lang="ru-RU" lang="ru-RU">0.12	" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">100
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">5	" xml:lang="ru-RU" lang="ru-RU">0.11			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">101
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">6	" xml:lang="ru-RU" lang="ru-RU">0.09		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">110
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">7	" xml:lang="ru-RU" lang="ru-RU">0.09			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">111

Определим среднюю длину кодового слова:

Теперь выполним кодирование по методу Шеннона. Процесс кодирование приведено в таблице 5.4.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.4

" xml:lang="ru-RU" lang="ru-RU"> Кодирование по методу Шеннона

" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">n ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">q ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Код " xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Усеченный код " xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="en-US" lang="en-US">]2.321…[ = 3	" xml:lang="en-US" lang="en-US">0	000	000
a 2	]2.321…[ = 3	0.2	001	001
a 3	]2.395…[ = 3	0.4	011	01
a 4	]3.058…[ = 4	0.59	1001	100
a 5	]3.183…[ = 4	0.71	1011	101
a 6	]3.472…[ = 4	0.82	1101	110
a 7	]3.472…[ = 4	0.91	1110	111

Как и предыдущего случая найдем среднюю длину кодового слова:

Как можно видеть результаты кодирования по методам Фано и Шеннона с точки зрения минимизации средней длины кода практически совпали. Поэтому часто эти методы рассматривают как один (в формулировке Фано) и называют методом Шеннона-Фано.

В 1952 г. Давид Хаффмен предложил метод оптимального префиксного кодирования для дискретных источников, который в отличие от методов Шеннона и Фано до сих пор применяется на практике. Д.Хаффмен доказал, что средняя длина кодового слова, полученная с помощью его метода, будет минимальна. Кодирование Хаффмена производится за три шага.

1. Упорядочение: буквы располагаются в порядке убывания их вероятностей.

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

3. Кодирование: начиная с последнего объединения, последовательно приписываются одной компоненте составной буквы символ 0, а второй символ 1; процесс продолжается до тех пор, пока все исходные буквы не будут закодированы.

Выполним кодирование по методу Хаффмена для множества, рассматривавшегося в примерах применения методов Фано и Шеннона.

1. Исходный список букв A = { a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 } уже упорядочен, так как P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Объединим буквы a 6 и a 7 в одну букву a 1 с вероятностью 0.18 и переупорядочим список :

P 1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A 1 = { a 1 , a 2 , a 3 , a 1 , a 4 , a 5 }.

3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:

P 2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A 2 = { a 2 , a 1 , a 2 , a 3 , a 1 };

P 3 = {0.37, 0.23, 0.2, 0.2}, A 3 = { a 3 , a 2 , a 1 , a 2 };

P 4 = {0.4, 0.37, 0.23}, A 4 = { a 4 , a 3 , a 2 };

P 5 = {0.6, 0.4}, A 5 = { a 5 , a 4 };

P 6 = {1}, A 6 = { a 6 }.

4. Присвоим двоичные коды символам :

a 6 : a 5 = 0, a 4 = 1;

a 5 : a 3 = 00, a 2 = 01;

a 4 : a 1 = 10, a 2 = 11;

a 3 : a 3 = 000, a 1 = 001;

a 2 : a 4 = 010, a 5 = 011;

a 1 : a 6 = 0010, a 7 = 0011.

Таким образом, исходным буквам присвоены следующие двоичные коды: a 1 = 10, a 2 = 11, a 3 = 000, a 4 = 010, a 5 = 011, a 6 = 0010, a 7 = 0011, что дает среднюю длину кода, меньшую, чем в случае кодирования Фано и Шеннона.

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

Тогда коды имеют следующую избыточность:

код Фано: ;

код Шеннона: ;

код Хаффмена: .

Таким образом, избыточность кода Хаффмена минимальна.

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

PAGE 43

Достигнутая степень близости среднего числа 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 указывает наибольшее количество единиц информации, которое можно передать по линии связи за единицу времени. Она называется пропускной способностью линии связи.

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

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

Доказательство теоремы. Пусть H(x) и H(x| y) – априорная и апостериорная энтропии на символ (со стороны приемного конца) для системы, реализующей пропускную способность С канала. В силу свойства Е при достаточно большой длительности (п символов) передачи все возможные любого ансамбля распадаются на высоковероятную и маловероятную группы; при этом о количестве сигналов в соответствующих группах можно сделать следующие утверждения:

а) Группа высоковероятных передаваемых сигналов содержит около 2 пН(х) последовательностей.

б) Группа высоковероятных принимаемых сигналов содержит около 2 пН(у) последовательностей.

в) Каждый высоковероятный принимаемый сигнал мог (с приблизительно одинаковыми вероятностями) произойти от примерно 2 пН(х | у) передаваемых сигналов высоковероятной группы.

г) Каждому отправляемому сигналу из высоковероятной группы может (с приблизительно одинаковыми вероятностями) соответствовать примерно 2 пН(у | х) принимаемых высоковероятных сигналов.

В силу свойства Е энтропии дискретных процессов, при увеличении п все соответствующие e и d будут стремиться к нулю.

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

Пусть принят некоторый сигнал у к. Вероятность ошибки при этом равна вероятности того, что данный сигнал может происходить более чем от одного из 2 пН разрешенных сигналов. Поскольку код получается случайным (равновероятным) выбором 2 пН последовательностей из 2 пН(х) , то вероятность того, что заданный сигнал на входе канала попадет в число разрешенных, равна

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

Это есть средняя вероятность безошибочного приема. Далее, так как Н < С = Н(х) – Н(х| у), то

Н – Н(х) = - Н(х| у) - h, (8.23)

Где h > 0. Подставляя (8.23) в (8.22), получаем

Можно показать , что

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

Отметим, что равенство (8.25) справедливо при любом, сколь угодно малом положительном h. Это означает, что теорема допускает условие Н £ С.

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

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

Теорема. При условии Н £ С среди кодов, обеспечивающих (согласно Первой теореме) сколь угодно малую вероятность ошибки, существует код, при котором скорость передачи информации R сколь угодно близка к скорости создания информации Н.

Скорость передачи информации (на символ) определяется как

R = H – H(x| y), (8.26)

где Н(х| у) – апостериорная энтропия отправленного сигнала на символ, или рассеяние информации в канале.

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

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

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

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

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

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

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

Фундаментальное значение теорем состоит в том, что они позволяют, зная предельные (теоретические) значения скорости передачи информации С С , оценить эффективность используемых методов кодирования.

Итак, приведенные теоремы являются теоремами существования.

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

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

Теорема. Если скорость создания информации Н больше пропускной способности канала С, то никакой код не может сделать вероятность ошибки сколь угодно малой. Минимальное рассеяние информации на символ, достижимое при Н > С, равно Н – С; никакой код не может обеспечить меньшего рассеяния информации.

С доказательством Обратной теоремы Шеннона можно ознакомиться в .

Обратная теорема утверждает, что при Н > С безошибочная передача невозможна; при этом чем больше отношение Н / C, тем больше остаточная неопределенность Н(х| у). Последняя связана с вероятностью ошибки при приеме. Естественно возникает вопрос о том, как связана минимальная вероятность ошибки, достигаемая при наилучшем кодировании, с отношением Н/ С. Для бинарного канала решение приведено в . При к = Н/C < 1 вероятность ошибки e(к ) = 0 согласно первой теореме. При к ® ¥ e(к ) ® 0,5, что означает, что доля передаваемой информации из всей поступающей на вход канала стремится к нулю при к ® ¥; чем быстрее ведется передача, тем меньшее количество информации передается.

Контрольные вопросы

1. Дайте обоснование необходимости введения избыточности при кодировании в канале с помехами.

2. Как определяется среднее количество информации (на один символ), переданной по дискретному каналу с шумами?

3. Как определяется скорость передачи и пропускная способность канала с помехами?

4. Сформулируйте и поясните прямую и обратную теоремы Шеннона о кодировании для канала с помехами.

5. Какие соотношения следуют из теоремы об асимптотической равновероятности достаточно длинных типичных цепочек для стационарных каналов с шумами?

6. Какова причина целесообразности кодирования длинных последовательностей символов?

7. Какой формулой определяется пропускная способность двоичного симметричного канала без памяти, при каком условии пропускная способность этого канала обращается в нуль?