Теорема Шеннона для канала без шума

Теория информации
Собственная информация Информационная энтропия Дифференциальная энтропия Условная энтропия Энтропия объединения Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Избыточность информации Скорость передачи информации Пропускная способность канала
Теорема Шеннона для канала без шума Теоремы Шеннона для канала с шумом Теорема Шеннона — Хартли

Теорема Шеннона для канала без шума (теорема кодирования для дискретного канала без шума^[1], теорема Шеннона о кодировании источника^[2], первая теорема Шеннона для канала без шума^[3]) — теорема, которая определяет максимальную скорость передачи символов (сообщений) источника в канале без шума^[4]. При фиксированной скорости передачи символов, определяет максимальную производительность источника (энтропию в единицу времени), при которой можно закодировать символы на выходе источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шума, исходя из известной пропускной способности канала^[5].

Также теорема определяет наименьшее среднее число кодовых символов, приходящихся на один символ (сообщение) источника, которыми может быть закодирована информация источника без потерь^[6].

Для случая, если производить кодирование символов источника посимвольно, то есть отдельно кодировать каждый символ источника, Роберт Фано в 1961 году сформулировал основную теорему кодирования следующим образом^[7]:

При заданном ансамбле ${\displaystyle A}$ из ${\displaystyle M}$ сообщений (символов) с энтропией ${\displaystyle H(A)}$ и алфавитом, состоящем из ${\displaystyle D}$ символов, возможно так закодировать сообщения (символы) ансамбля посредством последовательности символов, принадлежащих заданному алфавиту, что среднее число символов на сообщение (символ) ${\displaystyle {\bar {n}}}$ удовлетворяет следующему неравенству:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+1.}$

Число ${\displaystyle {\bar {n}}}$ не может быть сделано меньше, чем ${\displaystyle {\frac {H(A)}{\log _{2}(D)}}}$.

Такая формулировка может называться теоремой Шеннона для источника общего вида^[8].

Если объединять символы источника в группы по ${\displaystyle N}$ символов и производить кодирование этих групп последовательностями кодовых символов, то наименьшее среднее число кодовых символов на один символ можно ещё более уменьшить. В этом случае теорема кодирования выглядит следующим образом^[9]:

При любом заданном сколь угодно малом положительном числе ${\displaystyle \epsilon }$ можно найти такое натуральное число ${\displaystyle N}$ и соответствующее множество ${\displaystyle M^{N}}$ кодовых слов, такое, что среднее число символов на символ ${\displaystyle {\bar {n}}}$ удовлетворяет неравенству:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+\epsilon ,}$

где ${\displaystyle M}$ — число различных символов источника.

Этот результат можно достичь только в случае, если число символов источника ${\displaystyle N}$ в каждой группе стремится к бесконечности^[10].

Теорема о наименьшем среднем числе кодовых символов на один символ источника была сформулирована Клодом Шенноном при доказательстве своей теоремы о наибольшей скорости передачи символов источника для случая, когда основание кодового алфавита равно двум (${\displaystyle D=2}$)^[6].

В статье Клода Шеннона «Математическая теория связи», опубликованная в 1848 году, основная теорема для канала без шума сформулирована следующим образом^[4][11]:

Пусть источник сообщений имеет энтропию ${\displaystyle H(A)}$ (бит на символ), а канал имеет пропускную способность ${\displaystyle C}$ (бит в секунду). Тогда можно закодировать сообщения (символы) на выходе источника таким образом, чтобы передавать их по каналу со средней скоростью ${\displaystyle \nu =C/H(A)-\epsilon }$ символов в одну секунду, где ${\displaystyle \epsilon }$ — сколь угодно мало. Передавать со средней скоростью, большей ${\displaystyle C/H(A)}$, невозможно.

Для источника, у которого скорость передачи символов задана, эту теорему можно сформулировать следующим образом^[5]:

Пусть источник сообщений имеет энтропию ${\displaystyle H(A)}$ (бит на символ), а канал имеет пропускную способность ${\displaystyle C}$ (бит в секунду). Тогда можно закодировать символы на выходе источника таким образом, чтобы передавать их сколь угодно точно по дискретному каналу без шума при условии, что ${\displaystyle H'(A)<C}$ и невозможно, если ${\displaystyle H'(A)>C}$,

где ${\displaystyle H'(A)=\nu H(A)}$ — производительность источника, ${\displaystyle \nu }$ — средняя скорость передачи символов источника.

Сначала докажем следующее неравенство для случая, когда символы источника кодируются по отдельности:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+1,}$

где ${\displaystyle H(A)}$ — энтропия источника, ${\displaystyle D}$ — основание кодового алфавита, то есть число различных символов кода, ${\displaystyle {\bar {n}}}$ — среднее число кодовых символов на символ источника.

Cреднее число кодовых символов на одно символ источника определяется по формуле^[12]:

${\displaystyle {\bar {n}}=\sum _{i=1}^{M}p_{i}n_{i},}$

где ${\displaystyle M}$ — основание алфавита источника (число различных символов источника), ${\displaystyle p_{i}}$ — вероятность передачи ${\displaystyle i}$-го символа источника, ${\displaystyle n_{i}}$ — число кодовых символов, приходящихся на ${\displaystyle i}$-ый символ источника.

Величину ${\displaystyle n_{i}}$ можно представить в виде^[13]:

${\displaystyle n_{i}=\log _{D}(1/q_{i})-\log _{D}(z),}$

где

${\displaystyle q_{i}=D^{-n_{i}}/z}$, ${\displaystyle z=\sum _{k=1}^{M}D^{-n_{k}}}$

Используя неравенство Гиббса^[англ.]:

${\displaystyle \sum _{i=1}^{M}p_{i}\log _{D}(1/q_{i})\geq \sum _{i=1}^{M}p_{i}\log _{D}(1/p_{i})}$

и неравенство Крафта

${\displaystyle z\leq 1}$

получаем^[12]:

${\displaystyle {\begin{aligned}{\bar {n}}&=\sum _{i=1}^{M}{p_{i}n_{i}}=\sum _{i=1}^{M}{p_{i}(\log _{D}(1/q_{i})-\log _{D}(z)})=\sum _{i=1}^{M}p_{i}\log _{D}(1/q_{i})-\log _{D}(z)\geq \\&\geq \sum _{i=1}^{M}p_{i}\log _{D}(1/p_{i})-\log _{D}(z)\geq \sum _{i=1}^{M}p_{i}\log _{D}(1/p_{i})=\sum _{i=1}^{M}p_{i}\log _{2}(1/p_{i})/\log _{2}(D)={\frac {H(A)}{\log _{2}(D)}}.\end{aligned}}}$

Равенство достигается только для случая, когда ${\displaystyle z=1}$ и ${\displaystyle n_{i}=-\log _{D}(p_{i})}$^[12].

Переведём длины кодов в целые числа, с помощью округления вверх^[14]:

${\displaystyle n_{i}=\lceil -\log _{D}(p_{i})\rceil }$,

где ${\displaystyle \lceil x\rceil }$ обозначает наименьшее целое число, большее или равное ${\displaystyle x}$.

Можно проверить, что существует префиксный код с такими длинами, так как неравенство Крафта для него выполняется^[14]:

${\displaystyle z=\sum _{i=1}^{M}{D^{-n_{i}}}=\sum _{i=1}^{M}D^{-\lceil \log _{D}(p_{i})\rceil }\leq \sum _{i=1}^{M}D^{-\log _{D}(p_{i})}=\sum _{i=1}^{M}p_{i}=1}$.

Затем можно доказать, что^[14][15]

${\displaystyle {\bar {n}}=\sum _{i=1}^{M}p_{i}n_{i}=\sum _{i=1}^{M}p_{i}\lceil -\log _{D}(p_{i})\rceil <\sum _{i=1}^{M}p_{i}(-\log _{D}(p_{i})+1)={\frac {H(A)}{\log _{2}(D)}}+1}$.

Таким образом, получаем выполнение неравенства:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+1.}$

Если объединять символы источника в группы по ${\displaystyle N}$ символов и производить кодирование этих групп последовательностями кодовых символов, то среднее число кодовых символов, приходящихся на один символ источника равно^[9][16]:

${\displaystyle {\bar {n}}={\frac {1}{N}}\sum _{i=1}^{M}p_{i}n_{i}={\frac {{\bar {n}}_{N}}{N}},}$

где ${\displaystyle p_{i}}$ — вероятность передачи ${\displaystyle i}$-ой группы, ${\displaystyle n_{i}}$ — число кодовых символов, приходящихся на ${\displaystyle i}$-ую группу, ${\displaystyle {\bar {n}}_{N}}$ — среднее число кодовых символов на одну группу.

Тогда, подставляя в полученное неравенство для среднего числа кодовых символов на один символ вместо ${\displaystyle {\bar {n}}}$ величину ${\displaystyle {\bar {n}}_{N}=N{\bar {n}}}$ и вместо энтропии на один символ источника ${\displaystyle H(A)}$ энтропию группы символов ${\displaystyle H(A^{N})}$, а затем разделив на ${\displaystyle N}$, получаем:

${\displaystyle {\frac {H(A^{N})}{N\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A^{N})}{N\log _{2}(D)}}+{\frac {1}{N}}}$

Величины ${\displaystyle \lim _{N\to \infty }{\frac {H(A^{N})}{N}}}$ равны энтропии источника ${\displaystyle H(A)}$^[17], поэтому при ${\displaystyle N\rightarrow \infty }$ получаем^[6]:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+\epsilon ,}$

где ${\displaystyle \epsilon }$ — сколь угодно мало.

Таким образом, при стремлении длины кодируемой группы символов к бесконечности среднее число кодовых символов, приходящихся на один символ источника стремится к ${\displaystyle {\frac {H(A)}{\log _{2}(D)}}}$.

Докажем прямую часть теоремы, показывающую, что можно закодировать символы на выходе источника таким образом, чтобы передавать их по каналу со средней скоростью ${\displaystyle C/H(A)-\epsilon }$ символов в секунду, где ${\displaystyle \epsilon }$ — сколь угодно мало.

Пропускная способность канала связи без шума (между выходом кодера источника и входом декодера источника) равна:

${\displaystyle C={\frac {1}{T_{c}}}\max\{H(X)\},}$

где

${\displaystyle H(X)}$ — энтропия кодовых символов ${\displaystyle X}$, ${\displaystyle \max\{H(X)\}=\log _{2}(D)}$,

${\displaystyle T_{c}}$ — время, затрачиваемое на передачу одного кодового символа, которое равно ${\displaystyle T_{c}=T_{s}/{\bar {n}}}$, где ${\displaystyle T_{s}}$ — среднее время, затрачиваемое на передачу одного символа источника, ${\displaystyle \nu =1/T_{s}}$ — средняя скорость передачи символов источника. Так как ${\displaystyle {\bar {n}}\rightarrow {\frac {H(A)}{\log _{2}(D)}}}$ получаем:

${\displaystyle C\rightarrow \nu H(A)}$, то есть ${\displaystyle \nu \rightarrow C/H(A)}$.

Таким образом, выполнив кодирование символов источника с минимальным числом кодовых символов на символ, можно передавать символы со средней скоростью ${\displaystyle C/H(A)-\epsilon }$ символов в секунду.

Обратная часть теоремы, утверждающая, что средняя скорость передачи символов источника ${\displaystyle \nu }$ не может превзойти значение ${\displaystyle C/H(A)}$, доказывается тем, что пропускная способность канала — это максимальная скорость передачи информации по каналу связи.

Так как ${\displaystyle T_{c}=T_{s}/{\bar {n}}=1/({\bar {n}}\nu )}$ и ${\displaystyle {\bar {n}}\geq {\frac {H(A)}{\log _{2}(D)}}}$ для любого кода, то получаем:

${\displaystyle C=\nu {\bar {n}}\log _{2}(D)\geq \nu H(A)}$.

Следовательно, для любого кода должно выполняться неравенство: ${\displaystyle \nu \leq C/H(A)}$. Поэтому передавать символы источника со скоростью большей ${\displaystyle C/H(A)}$ невозможно.