Ёмкость Шеннона (@btkvm, Oyuukug)
Ёмкость Шеннона (шенноновская ёмкость) — характеристика неориентированного графа, описывающая предельную плотность кодирования с возможностью гарантированного отслеживания ошибок в канале связи, модель которого представляет данный граф.
В этой модели вершины графа соответствуют символам алфавита, а наличие ребра между двумя вершинами означает, что при передаче первый символ может быть заменён на второй, а второй — на первый. Вероятности или частота, с которыми это происходит, в модели не рассматриваются, целью является построение оптимального способа кодирования, устойчивого к сколь угодно непредсказуемым ошибкам такого рода.
Несмотря на "практичную" формулировку, задача определения шенноновской ёмкости того или иного графа на текущий момент носит сугубо теоретический характер.
Мотивация к изучению
[править | править код]Пусть по каналу связи передаётся текст, записанный с помощью алфавита из пяти символов: , причём физически чтение передаваемых символов реализовано через дискретизацию аналогового сигнала (взятие ближайшего из граничных значений). Из-за погрешностей в передаче сигнала могут перепутываться соседние символы, а также последний () перепутываться с первым (). Граф , описывающий возможные ошибки этого канала связи, будет циклом длины 5.
Если передавать текст "как есть", то, получив символ , получатель не сможет понять, был ли передан отправителем символ или это был переданный отправителем символ , при передаче которого произошла ошибка и он превратился в символ .
Такая неоднозначность может возникать всегда когда используются хотя бы два символа, соединённые ребром в графе ошибок. Чтобы этого не происходило, можно выбрать независимое множество вершин этого графа и кодировать текст только с помощью символов, соответствующих этим вершинам. При этом, чтобы информационная ценность каждого символа страдала как можно меньше, уместно брать максимальное по размеру из таких множеств (его размер обозначается как ).
В рассматриваемом примере, очевидно, и поэтому текст нужно кодировать двумя символами (например, и ). Если длина передаваемого текста (количество символов исходного алфавита) равна , то существует всего вариантов этого текста и чтобы закодировать их все символами двубуквенного алфавита понадобится не менее бит, то есть размер текста увеличится не менее чем в раз.
Этот результат можно улучшить если рассматривать не множество ошибок передачи каждого отдельного символа, а ошибки при передаче пары символов. Граф пар символов, которые могут подменяться друг другом (его обозначают как ) будет иметь не меньшее число независимости.
В рассматриваемом примере и одно из максимальных независимых множеств - . Это означает, что в передаваемом сообщении можно использовать все пять символов, но с условием, что при объединении их в последовательные пары будут образовываться только пары из этого множества (например, текст использовать нельзя, потому что он может быть образован из текста , который тоже используется). Если изначально в передаваемом тексте было символов, то каждый из них можно перевести в одну из этих пар и получить текст длины с требуемыми свойствами отслеживания ошибок. Поскольку , то этот способ кодирования эффективнее первого.
Естественным образом возникает вопрос, можно ли улучшить этот результат, рассматривая не пары, а последовательные тройки, четвёрки и бо́льшее количество символов, и какого наилучшего результата можно достичь этим методом. Формализация этого вопроса и приводит к понятию ёмкости Шеннона.
Формальное определение
[править | править код]Для определения ёмкости Шеннона используется вспомогательное определение прямого произведения графов:
, где
Это операция с точностью до изоморфизма является ассоциативной и коммутативной, так что можно естественным образом определить степень графа:
Определение Ёмкость Шеннона графа равна[1] |
Последнее равенство обусловлено тем, что [2].
Характер сходимости
[править | править код]Достижимость предела
[править | править код]Предел последовательности достигается не всегда. Например, когда представляет собой объединение цикла длины 5 () и изолированной вершины, то , но
Это обусловлено тем, что и , так что аналогичное верно для объединения изолированной вершины с любым графом , для которого
Скорость роста
[править | править код]Актуален вопрос о том, насколько быстро значения приближаются к . В 2006 году Алон и Любецкий показали. что при достаточно большом размере графа конечного числа значений недостаточно чтобы узнать с точностью хотя бы до . В той же работе они выдвинули несколько гипотез на эту тему.[3]
Теорема Для любого целого существует сколь угодно большое и граф размера такие, что при
|
Доказательство Алона и Любецкого было вероятностным (то есть конкретной конструкции какого-то одного графа из него вывести нельзя, но существование таковых доказано).
Они рассматривали полный граф из вершин ( - достаточно большое целое), рёбра которого поделены на группы и из каждой группы случайным образом (равновероятно по всем рёбрам группы) удалено одно ребро.
Если индексировать вершины графа парами , то два ребра и относятся к одной группе если:
Визуально это можно представить при изображении графа на торе как объединение в группу рёбер, получающихся друг из друга параллельным переносом по одной прямой (см. картинку).
Оценки и методы изучения
[править | править код]Общих алгоритмов вычисления шенноновской ёмкости по состоянию на 2019 год неизвестно. Это связано не только с тем, что сама задача о числе независимости NP-полна и потому вычислительно трудна, но и с тем, что при вычисленных значениях для малых задача предсказания дальнейшего роста этих величин также остаётся нетривиальной.
Более того, неизвестно даже точное значение ёмкости для цикла длины 7 или большей нечётной длины.[4][5] Однако для циклов нечётной длины известен предельный закон[6]:
Число Ловаса
[править | править код]Ласло Ловас в 1979 году показал, что .[7] Для доказательства он вывел общую верхнюю оценку для ёмкости Шеннона через характеристику системы векторов , структура которой связана со структурой графа , а именно
При таком подходе чтобы получить верхнюю оценку достаточно предъявить хотя бы одну систему векторов c нужными свойствами, то есть происходит переход от задачи доказательства к задаче предъявления контрпримера.
В конструкции Ловаса с размером графа должно совпадать только количество векторов, но не размерность пространства. Например, для доказательства использовались трёхмерные вектора.
Алгебраические оценки
[править | править код]Haemers получил оценку ёмкости через ранг матриц, похожих по структуре на матрицу смежности, а именно
где минимум берётся по всем матрицам размера в произвольном поле таким, что:
Таким образом, для верхней оценки также достаточно предъявить хотя бы одну матрицу , имеющую малый ранг.[8]
См. также
[править | править код]Примечания
[править | править код]- ↑ Иногда также используется обозначение
- ↑ Слайды лекции МФТИ "Графовая модель канала связи. Шенноновская ёмкость" . Дата обращения: 30 декабря 2019. Архивировано 13 января 2017 года.
- ↑ Alon, Noga; Lubetzky, Eyal (2006), "The Shannon capacity of a graph and the independence numbers of its powers", IEEE Transactions on Information Theory, 52: 2172—2176, arXiv:cs/0608021, doi:10.1109/tit.2006.872856.
- ↑ см. например, arXiv:1504.01472 Архивная копия от 30 декабря 2019 на Wayback Machine, где численное улучшение оценок на них представляется как тема отдельной работы
- ↑ Shannon capacity of the seven-cycle . Дата обращения: 30 декабря 2019. Архивировано 30 декабря 2019 года.
- ↑ Bohman, Tom (2003), "A limit theorem for the Shannon capacities of odd cycles", Proceedings of the American mathematical society, 131 (11): 3559–3569
- ↑ Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory, IT-25 (1), doi:10.1109/TIT.1979.1055985, Zbl 0395.94021
- ↑ Haemers, Willem H. (1978), "An upper bound for the Shannon capacity of a graph" (PDF), Colloquia Mathematica Societatis János Bolyai, 25: 267—272, Архивировано (PDF) 4 марта 2016, Дата обращения: 30 декабря 2019 Источник . Дата обращения: 30 декабря 2019. Архивировано 4 марта 2016 года.. The definition here corrects a typo in this paper.