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

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

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

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

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

 

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

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

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

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

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

 

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

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

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

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

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

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

$G_1\times <!--\; \times \; -->G_2=(V_1,E_1)\times <!--\; \times \; -->(V_2,E_2)=(V^{\prime },E^{\prime })$$G_{1}\times G_{2}=(V_{1},E_{1})\times (V_{2},E_{2})=(V',E')$ , где

$V^{\prime }=V_1\times <!--\; \times \; -->V_2$$V'=V_{1}\times V_{2}$ 

$((v_1,w_1),(v_2,w_2))\in <!--\; \in \; -->E^{\prime }⟺<!--\; ⟺\; -->((v_1,v_2)\in <!--\; \in \; -->E_1\vee <!--\; \vee \; -->v_1=v_2)\wedge <!--\; \wedge \; -->((w_1,w_2)\in <!--\; \in \; -->E_2\vee <!--\; \vee \; -->w_1=w_2)\wedge <!--\; \wedge \; -->((v_1,w_1)\ne (v_2,w_2))$$((v_{1},w_{1}),(v_{2},w_{2}))\in E'\iff ((v_{1},v_{2})\in E_{1}\lor v_{1}=v_{2})\land ((w_{1},w_{2})\in E_{2}\lor w_{1}=w_{2})\land ((v_{1},w_{1})\not =(v_{2},w_{2}))$ 

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

$G^k=G\times <!--\; \times \; -->G^{k-<!--\; -\; -->1}$$G^{k}=G\times G^{k-1}$ 

Определение Ёмкость Шеннона графа $G$$G$  равна $c(G)=\underset{n\in <!--\; \in \; -->\mathbb{N}}{sup}\sqrt[n]{\mathrm{\alpha <!--\; \alpha \; -->}(G^n)}=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\sqrt[n]{\mathrm{\alpha <!--\; \alpha \; -->}(G^n)}$$c(G)=\sup \limits _{n\in {\mathbb {N} }}{\sqrt[{n}]{\alpha (G^{n})}}=\lim \limits _{n\to \infty }{\sqrt[{n}]{\alpha (G^{n})}}$

Последнее равенство обусловлено тем, что $\mathrm{\alpha <!--\; \alpha \; -->}(G\times <!--\; \times \; -->H)\ge <!--\; \ge \; -->\mathrm{\alpha <!--\; \alpha \; -->}(G)\mathrm{\alpha <!--\; \alpha \; -->}(H)$$\alpha (G\times H)\geq \alpha (G)\alpha (H)$ .

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

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

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

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

Скорость ростаПравить

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

Теорема Для любого целого $v$$v$  существует сколь угодно большое $N$$N$  и граф $G$$G$  размера $N$$N$  такие, что ${\mathrm{\alpha <!--\; \alpha \; -->}}_k=O(\log <!--\; \; -->N)$$\alpha _{k}=O(\log N)$  при $k<v$  ${\mathrm{\alpha <!--\; \alpha \; -->}}_v=N^{\frac{1}{v}}$$\alpha _{v}=N^{\frac {1}{v}}$

Описание конструкции

 

Группы рёбер в примере Алона-Любецкого. Из каждой группы удаляется одно (случайное) ребро.

Доказательство Алона и Любецкого было вероятностным (то есть конкретной конструкции какого-то одного графа из него вывести нельзя, но существование таковых доказано).

Они рассматривали полный граф из $nv$$nv$  вершин ($n$$n$  - достаточно большое целое), рёбра которого поделены на группы и из каждой группы случайным образом (равновероятно по всем рёбрам группы) удалено одно ребро.

Если индексировать вершины графа парами $(i,k),i\in <!--\; \in \; -->[1;n],k\in <!--\; \in \; -->[1;v]$$(i,k),i\in [1;n],k\in [1;v]$ , то два ребра $((i_1,k_1),(j_1,l_1))$$((i_{1},k_{1}),(j_{1},l_{1}))$  и $((i_2,k_2),(j_2,l_2))$$((i_{2},k_{2}),(j_{2},l_{2}))$  относятся к одной группе если:

• $i_1=i_2$$i_{1}=i_{2}$ 
• $j_1=j_2$$j_{1}=j_{2}$ 
• $l_1-<!--\; -\; -->k_1=l_2-<!--\; -\; -->k_2$$l_{1}-k_{1}=l_{2}-k_{2}$ 

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

Оценки и методы изученияПравить

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

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

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

Число ЛовасаПравить

Основная статья: Число Ловаса

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

$u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&(i,j)\notin E.\end{cases}}$ 

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

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

Алгебраические оценкиПравить

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

$c(G)\le <!--\; \le \; -->R(G)=\underset{B}{min}\mathrm{rank}<!--\; \; -->(B),$$c(G)\leq R(G)=\min _{B}\operatorname {rank} (B),$ 

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

• $b_{ii}\ne 0$$b_{ii}\not =0$ 
• $(i,j)\notin E\Rightarrow <!--\; \Rightarrow \; -->b_{ij}=0$$(i,j)\not \in E\Rightarrow b_{ij}=0$ 

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

См. такжеПравить

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