Ёмкость Шеннона

Ёмкость Шеннона (шенноновская ёмкость) — характеристика неориентированного графа, описывающая предельную плотность кодирования с возможностью гарантированного отслеживания ошибок в канале связи, модель которого представляет данный граф.

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

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

Мотивация к изучению

Граф $C_5$ с выделенным максимальным независимым множеством

Пусть по каналу связи передаётся текст, записанный с помощью алфавита из пяти символов: $\{0,1,2,3,4\}$, причём физически чтение передаваемых символов реализовано через дискретизацию аналогового сигнала (взятие ближайшего из граничных значений). Из-за погрешностей в передаче сигнала могут перепутываться соседние символы, а также последний ($4$) перепутываться с первым ($0$). Граф $G$, описывающий возможные ошибки этого канала связи, будет циклом длины 5.

Если передавать текст "как есть", то, получив символ $2$, получатель не сможет понять, был ли передан отправителем символ $2$ или это был переданный отправителем символ $1$, при передаче которого произошла ошибка и он превратился в символ $2$.

Такая неоднозначность может возникать всегда когда используются хотя бы два символа, соединённые ребром в графе ошибок. Чтобы этого не происходило, можно выбрать независимое множество вершин этого графа и кодировать текст только с помощью символов, соответствующих этим вершинам. При этом, чтобы информационная ценность каждого символа страдала как можно меньше, уместно брать максимальное по размеру из таких множеств (его размер обозначается как $\alpha (G)$).

В рассматриваемом примере, очевидно, $\alpha (G)=2$ и поэтому текст нужно кодировать двумя символами (например, $1$ и $3$). Если длина передаваемого текста (количество символов исходного алфавита) равна $n$, то существует всего $5^n$ вариантов этого текста и чтобы закодировать их все символами двубуквенного алфавита понадобится не менее ${\log }_2(5^n)=n{\log }_{2}5$ бит, то есть размер текста увеличится не менее чем в ${\log }_{2}5$ раз.

Граф $C_5^2$ c выделенным максимальным независимым множеством

Этот результат можно улучшить если рассматривать не множество ошибок передачи каждого отдельного символа, а ошибки при передаче пары символов. Граф пар символов, которые могут подменяться друг другом (его обозначают как $G^2$) будет иметь не меньшее число независимости.

В рассматриваемом примере $\alpha (G^2)=5$ и одно из максимальных независимых множеств - $\{(0,3),(1,0),(2,2),(3,4),(4,1)\}$. Это означает, что в передаваемом сообщении можно использовать все пять символов, но с условием, что при объединении их в последовательные пары будут образовываться только пары из этого множества (например, текст $00$ использовать нельзя, потому что он может быть образован из текста $10$, который тоже используется). Если изначально в передаваемом тексте было $n$ символов, то каждый из них можно перевести в одну из этих пар и получить текст длины $2n$ с требуемыми свойствами отслеживания ошибок. Поскольку $2<{\log }_{2}5$, то этот способ кодирования эффективнее первого.

Естественным образом возникает вопрос, можно ли улучшить этот результат, рассматривая не пары, а последовательные тройки, четвёрки и бо́льшее количество символов, и какого наилучшего результата можно достичь этим методом. Формализация этого вопроса и приводит к понятию ёмкости Шеннона.

Формальное определение

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

$G_1\times G_2=(V_1,E_1)\times (V_2,E_2)=(V^{\prime },E^{\prime })$, где

$V^{\prime }=V_1\times V_2$

$((v_1,w_1),(v_2,w_2))\in E^{\prime }⟺((v_1,v_2)\in E_1\vee v_1=v_2)\wedge ((w_1,w_2)\in E_2\vee w_1=w_2)\wedge ((v_1,w_1)=(v_2,w_2))$

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

$G^k=G\times G^{k-1}$

Шаблон:Рамка Определение

Ёмкость Шеннона графа $G$ равна

$c(G)=\sup {\mathrm{\backslash limits}}_{n\in \mathbb{N}}\sqrt[n]{\alpha (G^n)}=\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\sqrt[n]{\alpha (G^n)}$

Последнее равенство обусловлено тем, что $\alpha (G\times H)\ge \alpha (G)\alpha (H)$.

Характер сходимости

Достижимость предела

Предел последовательности $\sqrt[n]{\alpha (G^n)}$ достигается не всегда. Например, когда $G$ представляет собой объединение цикла длины 5 ($C_5$) и изолированной вершины, то $c(G)=\sqrt{5}+1$, но $\sqrt[n]{\alpha (G^n)}<\sqrt{5}+1$

Это обусловлено тем, что $\alpha (G^n)=\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k})\alpha ({C_5}^k)+1$ и $\alpha (C_5)<c(C_5)$, так что аналогичное верно для объединения изолированной вершины с любым графом $H$, для которого $\alpha (H)<c(H)$

Скорость роста

Актуален вопрос о том, насколько быстро значения ${\alpha }_n=\sqrt[n]{\alpha (G^n)}$ приближаются к $c(G)$. В 2006 году Алон и Любецкий показали. что при достаточно большом размере графа конечного числа значений ${\alpha }_n$ недостаточно чтобы узнать $G$ с точностью хотя бы до $|G{|}^{\epsilon }\mathrm{\forall }ϵ>0$. В той же работе они выдвинули несколько гипотез на эту тему.

Шаблон:Рамка Теорема

Для любого целого $v$ существует сколь угодно большое $N$ и граф $G$ размера $N$ такие, что

${\alpha }_k=O(\log N)$ при $k<v$

${\alpha }_v=N^{\frac{1}{v}}$ Шаблон:Конец рамки

Оценки и методы изучения

Общих алгоритмов вычисления шенноновской ёмкости по состоянию на 2019 год неизвестно. Это связано не только с тем, что сама задача о числе независимости NP-полна и потому вычислительно трудна, но и с тем, что при вычисленных значениях $\alpha (G^k)$ для малых $k$ задача предсказания дальнейшего роста этих величин также остаётся нетривиальной.

Более того, неизвестно даже точное значение ёмкости для цикла длины 7 или большей нечётной длины. Однако для циклов нечётной длины известен предельный закон:

$c(C_{2n+1})=n+\frac{1}{2}+o(1)$

Число Ловаса

Ласло Ловас в 1979 году показал, что $c(C_5)=\sqrt{\alpha (C_5^2)}=\sqrt{5}$. Для доказательства он вывел общую верхнюю оценку для ёмкости Шеннона через характеристику системы векторов $(u_i{)}_{i\in V}$, структура которой связана со структурой графа $G=(V,E)$, а именно

$u_i^{\mathrm{T}}{u}_j=\{\begin{array}{cc}1,& i=j,\\ 0,& (i,j)\notin E.\end{array}$

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

В конструкции Ловаса с размером графа должно совпадать только количество векторов, но не размерность пространства. Например, для доказательства $c(C_5)=\sqrt{5}$ использовались трёхмерные вектора.

Алгебраические оценки

Haemers получил оценку ёмкости через ранг матриц, похожих по структуре на матрицу смежности, а именно

$c(G)\le R(G)=\underset{B}{\min }\mathrm{rank}(B),$

где минимум берётся по всем матрицам $B$ размера $n\times n$ в произвольном поле таким, что:

• $b_{ii}=0$
• $(i,j)\in ̸E\Rightarrow b_{ij}=0$

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

См. также

• Задача о независимом множестве