Русская Википедия:Ёмкость Шеннона

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

Файл:Independent set in C 5.png

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

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

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

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

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

Файл:Square of C 5 with max independent set.png

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

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

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

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

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

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

<math>G_1 \times G_2 = (V_1, E_1) \times (V_2, E_2) = (V', E')</math>, где

<math>V' = V_1 \times V_2</math>

<math>((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))</math>

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

<math>G^k = G \times G^{k-1}</math>

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

Ёмкость Шеннона графа <math>G</math> равна

<math>c(G) = \sup \limits_{n \in {\mathbb N}} {\sqrt[n]{\alpha(G^n)}} = \lim \limits_{n \to \infty} {\sqrt[n]{\alpha(G^n)}}</math>

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

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

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

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

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

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

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

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

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

<math>\alpha_k = O(\log N)</math> при <math>k < v</math>

<math>\alpha_v = N^{\frac{1}{v}}</math> Шаблон:Конец рамки

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

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

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

<math>

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

</math>

Число Ловаса

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

<math>

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

</math>

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

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

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

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

<math>

c(G) \leq R(G) = \min_{B} \operatorname{rank}(B), </math>

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

• <math>b_{ii} \not = 0</math>
• <math>(i,j) \not \in E \Rightarrow b_{ij} = 0</math>

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

См. также

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