Теорема Шеннона для канала без шума (теорема кодирования для дискретного канала без шумаВаргаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 22., теорема Шеннона о кодировании источника, первая теорема Шеннона для канала без шума) — теорема, которая определяет максимальную скорость передачи символов (сообщений) источника в канале без шумаШеннон К. Работы по теории информации и кибернетике, 1963. — С. 270.. При фиксированной скорости передачи символов, определяет максимальную производительность источника (энтропию в единицу времени), при которой можно закодировать символы на выходе источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шума, исходя из известной пропускной способности каналаФинк Л. М. Теория передачи дискретных сообщений, 1970. — С. 67..
Также теорема определяет наименьшее среднее число кодовых символов, приходящихся на один символ (сообщение) источника, которыми может быть закодирована информация источника без потерьШеннон К. Работы по теории информации и кибернетике, 1963. — С. 272..
Теоремы О наименьшем среднем числе кодовых символов на символ источника Для случая, если производить кодирование символов источника посимвольно, то есть отдельно кодировать каждый символ источника, Роберт Фано в 1961 году сформулировал основную теорему кодирования следующим образом: При заданном ансамбле из сообщений (символов) с энтропией и алфавитом, состоящем из символов, возможно так закодировать сообщения (символы) ансамбля посредством последовательности символов, принадлежащих заданному алфавиту, что среднее число символов на сообщение (символ) удовлетворяет следующему неравенству:
Число не может быть сделано меньше, чем .
Такая формулировка может называться теоремой Шеннона для источника общего видаГабидулин Э. М., Пилипчук Н. И. Лекции по теории информации, 2007. — С. 49—52..
Если объединять символы источника в группы по символов и производить кодирование этих групп последовательностями кодовых символов, то наименьшее среднее число кодовых символов на один символ можно ещё более уменьшить. В этом случае теорема кодирования выглядит следующим образомФано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 93—94.: При любом заданном сколь угодно малом положительном числе можно найти такое натуральное число и соответствующее множество кодовых слов, такое, что среднее число символов на символ удовлетворяет неравенству:
где — число различных символов источника.
Этот результат можно достичь только в случае, если число символов источника в каждой группе стремится к бесконечностиФано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 94..
Теорема о наименьшем среднем числе кодовых символов на один символ источника была сформулирована Клодом Шенноном при доказательстве своей теоремы о наибольшей скорости передачи символов источника для случая, когда основание кодового алфавита равно двум ().
О максимальной скорости передачи символов источника В статье Клода Шеннона «Математическая теория связи», опубликованная в 1948 году, основная теорема для канала без шума сформулирована следующим образом:
Пусть источник сообщений имеет энтропию (бит на символ), а канал имеет пропускную способность (бит в секунду). Тогда можно закодировать сообщения (символы) на выходе источника таким образом, чтобы передавать их по каналу со средней скоростью символов в одну секунду, где — сколь угодно мало. Передавать со средней скоростью, большей , невозможно.
Для источника, у которого скорость передачи символов задана, эту теорему можно сформулировать следующим образом:
Пусть источник сообщений имеет энтропию (бит на символ), а канал имеет пропускную способность (бит в секунду). Тогда можно закодировать символы на выходе источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шума при условии, что и невозможно, если ,
где — производительность источника, — средняя скорость передачи символов источника.
Доказательство Теорема о среднем числе кодовых символов на символ источника Сначала докажем следующее неравенство для случая, когда символы источника кодируются по отдельности:
где — энтропия источника, — основание кодового алфавита, то есть число различных символов кода, — среднее число кодовых символов на символ источника.
Cреднее число кодовых символов на одно символ источника определяется по формуле:
где — основание алфавита источника (число различных символов источника), — вероятность передачи -го символа источника, — число кодовых символов, приходящихся на -ый символ источника.
Величину можно представить в виде:
где ,
Используя :
и неравенство Крафта
получаем:
Равенство достигается только для случая, когда и .
Переведём длины кодов в целые числа, с помощью округления вверх: , где обозначает наименьшее целое число, большее или равное .
Можно проверить, что существует префиксный код с такими длинами, так как неравенство Крафта для него выполняется: .
Затем можно доказать, что .
Таким образом, получаем выполнение неравенства:
Если объединять символы источника в группы по символов и производить кодирование этих групп последовательностями кодовых символов, то среднее число кодовых символов, приходящихся на один символ источника равноШеннон К. Работы по теории информации и кибернетике, 1963. — С. 271.:
где — вероятность передачи -ой группы, — число кодовых символов, приходящихся на -ую группу, — среднее число кодовых символов на одну группу.
Тогда, подставляя в полученное неравенство для среднего числа кодовых символов на один символ вместо величину и вместо энтропии на один символ источника энтропию группы символов , а затем разделив на , получаем:
Величины равны энтропии источника Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 266., поэтому при получаем:
где — сколь угодно мало.
Таким образом, при стремлении длины кодируемой группы символов к бесконечности среднее число кодовых символов, приходящихся на один символ источника стремится к .
Теорема о максимальной скорости передачи символов источника Докажем прямую часть теоремы, показывающую, что можно закодировать символы на выходе источника таким образом, чтобы передавать их по каналу со средней скоростью символов в секунду, где — сколь угодно мало.
Пропускная способность канала связи без шума (между выходом кодера источника и входом декодера источника) равна:
где — энтропия кодовых символов , , — время, затрачиваемое на передачу одного кодового символа, которое равно , где — среднее время, затрачиваемое на передачу одного символа источника, — средняя скорость передачи символов источника. Так как получаем:
, то есть . Таким образом, выполнив кодирование символов источника с минимальным числом кодовых символов на символ, можно передавать символы со средней скоростью символов в секунду.
Обратная часть теоремы, утверждающая, что средняя скорость передачи символов источника не может превзойти значение , доказывается тем, что пропускная способность канала — это максимальная скорость передачи информации по каналу связи.
Так как и для любого кода, то получаем: .
Следовательно, для любого кода должно выполняться неравенство: . Поэтому передавать символы источника со скоростью большей невозможно.
Примечания
Категория:Теоремы теории информации Категория:Теория кодирования Категория:Сжатие данных