Согласно теореме о кодировании канала с шумом , пропускная способность данного канала — это наивысшая скорость передачи информации (в единицах информации в единицу времени), которая может быть достигнута со сколь угодно малой вероятностью ошибки. [1] [2]
Теория информации , разработанная Клодом Э. Шенноном в 1948 году, определяет понятие пропускной способности канала и предоставляет математическую модель, с помощью которой ее можно вычислить. Ключевой результат гласит, что пропускная способность канала, как определено выше, определяется максимумом взаимной информации между входом и выходом канала, причем максимизация осуществляется по отношению к входному распределению. [3]
Понятие пропускной способности канала стало центральным в развитии современных систем проводной и беспроводной связи с появлением новых механизмов кодирования с коррекцией ошибок , которые привели к достижению производительности, очень близкой к пределам, обещанным пропускной способностью канала.
Формальное определение
Базовая математическая модель системы связи следующая:
где:
какое сообщение необходимо передать;
– входной символ канала ( последовательность символов), взятый в алфавите ;
– выходной символ канала ( последовательность символов), взятый в алфавите ;
что, в свою очередь, вызывает взаимную информацию . Пропускная способность канала определяется как
где верхняя грань принимается по всем возможным выборам .
Аддитивность пропускной способности канала
Пропускная способность канала суммируется по независимым каналам. [4] Это означает, что совместное использование двух независимых каналов обеспечивает ту же теоретическую пропускную способность, что и их независимое использование. Более формально, пусть и будут двумя независимыми каналами, смоделированными, как указано выше; наличие входного алфавита и выходного алфавита . То же самое для . Мы определяем канал продукта как
Эта теорема гласит:
Доказательство
Сначала мы это покажем .
Пусть и — две независимые случайные величины. Пусть – случайная величина, соответствующая выходу через канал , и для через .
По определению .
Так как и независимы, так же как и , не зависит от . Мы можем применить следующее свойство взаимной информации :
На данный момент нам нужно только найти такое распределение, что . В действительности, и , достаточно двух вероятностных распределений для и достижения и :
то есть.
Теперь давайте покажем это .
Пусть это некоторое распределение для определения канала и соответствующего выхода . Позвольте быть алфавитом , для , и аналогично и .
По определению товарного канала, . Для данной пары мы можем переписать так:
Суммируя это равенство по всем , получаем .
Теперь мы можем дать верхнюю границу взаимной информации:
Это соотношение сохраняется в супремуме. Поэтому
Объединив два доказанных нами неравенства, получаем результат теоремы:
Шенноновская емкость графа
Если G — неориентированный граф , его можно использовать для определения канала связи, в котором символы являются вершинами графа, а два кодовых слова можно спутать друг с другом, если их символы в каждой позиции равны или соседние. Вычислительная сложность определения пропускной способности Шеннона такого канала остается открытой, но она может быть ограничена сверху другим важным инвариантом графа — числом Ловаса . [5]
Теорема о кодировании зашумленного канала
Теорема кодирования шумного канала утверждает, что для любой вероятности ошибки ε > 0 и для любой скорости передачи R, меньшей, чем пропускная способность канала C , существует схема кодирования и декодирования, передающая данные со скоростью R , вероятность ошибки которой меньше ε, для достаточно большая длина блока. Кроме того, для любой скорости, превышающей пропускную способность канала, вероятность ошибки в приемнике достигает 0,5, поскольку длина блока стремится к бесконечности.
C измеряется в битах в секунду , если логарифм берется по основанию 2, или в нацах в секунду, если используется натуральный логарифм , предполагая, что B находится в герцах ; мощности сигнала и шума S и N выражаются в линейных единицах мощности (например, в ваттах или вольтах 2 ). Поскольку значения сигнал/шум часто приводятся в дБ , может потребоваться преобразование. Например, отношение сигнал/шум 30 дБ соответствует линейному отношению мощности .
Оценка пропускной способности канала
Для определения пропускной способности канала необходимо найти распределение достижения пропускной способности и оценить взаимную информацию . Исследования в основном были сосредоточены на изучении каналов аддитивного шума при определенных ограничениях по мощности и распределениях шума, поскольку аналитические методы неосуществимы в большинстве других сценариев. Следовательно, в литературе были предложены альтернативные подходы, такие как исследование входной поддержки, [6] релаксации [7] и ограничений емкости [8] .
Пропускную способность дискретного канала без памяти можно вычислить с помощью алгоритма Блахута-Аримото .
Глубокое обучение можно использовать для оценки пропускной способности канала. Фактически, пропускная способность канала и распределение пропускной способности любого непрерывного векторного канала без памяти в дискретном времени могут быть получены с использованием CORTICAL, [9] совместной структуры, вдохновленной генеративно-состязательными сетями . CORTICAL состоит из двух кооперативных сетей: генератора с целью обучения выборке из входного распределения, обеспечивающего пропускную способность, и дискриминатора с целью научиться различать парные и непарные выборки и оценки ввода-вывода каналов .
Пропускная способность канала беспроводной связи
В этом разделе [10] основное внимание уделяется сценарию «точка-точка» с одной антенной. О пропускной способности канала в системах с несколькими антеннами читайте в статье о MIMO .
Канал AWGN с ограниченной полосой пропускания
Если средняя принимаемая мощность равна [Вт], общая полоса пропускания указана в Герцах, а спектральная плотность мощности шума равна [Вт/Гц], то пропускная способность канала AWGN равна
[бит/с],
где – полученное отношение сигнал/шум (SNR). Этот результат известен как теорема Шеннона-Хартли . [11]
Когда SNR велико (SNR ≫ 0 дБ), пропускная способность является логарифмической по мощности и приблизительно линейной по полосе пропускания. Это называется режимом с ограниченной полосой пропускания .
Когда отношение сигнал/шум мало (SNR ≪ 0 дБ), пропускная способность линейна по мощности, но нечувствительна к полосе пропускания. Это называется режимом ограничения власти .
На рисунке показаны режим с ограниченной полосой пропускания и режим с ограниченной мощностью.
где и - коэффициент усиления подканала , выбранный с учетом ограничения мощности.
Медленно затухающий канал
В канале с медленным замиранием , где время когерентности превышает требования к задержке, не существует определенной пропускной способности, поскольку максимальная скорость надежной связи, поддерживаемая каналом, зависит от случайного коэффициента усиления канала , который неизвестен передатчику. Если передатчик кодирует данные со скоростью [бит/с/Гц], существует ненулевая вероятность того, что вероятность ошибки декодирования не может быть сделана сколь угодно малой.
,
в этом случае говорят, что система отключена. При ненулевой вероятности того, что канал находится в состоянии глубокого замирания, пропускная способность канала с медленным замиранием в строгом смысле равна нулю. Однако можно определить наибольшее значение, при котором вероятность отключения будет меньше . Это значение известно как пропускная способность.
Быстрозатухающий канал
В канале с быстрым замиранием , где требования к задержке превышают время когерентности, а длина кодового слова охватывает множество периодов когерентности, можно усреднить по множеству независимых замираний канала путем кодирования по большому количеству временных интервалов когерентности. Таким образом, можно достичь надежной скорости передачи данных [бит/с/Гц], и об этой величине имеет смысл говорить как о пропускной способности канала с быстрым замиранием.
Обратная связь
Пропускная способность обратной связи — это наибольшая скорость, с которой информация может надежно передаваться в единицу времени по каналу связи «точка-точка», при котором приемник передает выходные данные канала передатчику. Теоретико-информационный анализ коммуникационных систем, включающих обратную связь, является более сложным и сложным, чем без обратной связи. Возможно, именно по этой причине К.Э. Шеннон выбрал обратную связь в качестве темы первой лекции Шеннона, прочитанной на Международном симпозиуме IEEE по теории информации в 1973 году в Ашкелоне, Израиль.
Пропускная способность обратной связи характеризуется максимумом направленной информации между входами канала и выходами канала, причем максимизация связана с причинно-следственной обусловленностью входа с учетом выхода. Направленная информация была придумана Джеймсом Мэсси [12] в 1990 году, который показал, что это верхняя граница пропускной способности обратной связи. Для каналов без памяти Шеннон показал [13] , что обратная связь не увеличивает пропускную способность, а пропускная способность обратной связи совпадает с пропускной способностью канала, характеризуемой взаимной информацией между входом и выходом. Пропускная способность обратной связи известна как выражение в замкнутой форме только для нескольких примеров, таких как: канал-лазейка, [14] канал Изинга, [15] [16] канал двоичного стирания с ограничением на вход без последовательных единиц, каналы NOST. .
Базовая математическая модель системы связи следующая:
Вот формальное определение каждого элемента (где единственной разницей в отношении пропускной способности без обратной связи является определение кодера):
сообщение, которое должно быть передано, записано в алфавите ;
– входной символ канала ( последовательность символов), взятый в алфавите ;
– выходной символ канала ( последовательность символов), взятый в алфавите ;
– оценка передаваемого сообщения;
— функция кодирования в момент времени для блока длиной ;
То есть каждый раз, когда существует обратная связь о предыдущем выходе, так что кодер имеет доступ ко всем предыдущим выходам . Код представляет собой пару отображений кодирования и декодирования с , и он распределен равномерно. Скорость называется достижимой, если существует такая последовательность кодов , что средняя вероятность ошибки: стремится к нулю при .
Пропускная способность обратной связи обозначается и определяется как супремум по всем достижимым скоростям.
Основные результаты по возможности обратной связи
Пусть и моделируются как случайные величины. Причинная обусловленность описывает данный канал. Выбор причинно-условного распределения определяет совместное распределение благодаря цепному правилу причинной обусловленности [17] , которое, в свою очередь, индуцирует направленную информацию .
Пропускная способность обратной связи определяется выражением
,
где верхняя грань принимается по всем возможным выборам .
Гауссовая обратная связь
Когда гауссов шум окрашен, канал имеет память. Рассмотрим, например, простой случай шумового процесса авторегрессионной модели, где – процесс iid.
Методы решения
Емкость обратной связи в общем случае решить сложно. Существуют некоторые методы, связанные с теорией управления и марковскими процессами принятия решений , если канал дискретен.
Пропускная способность канала AWGN с различными ограничениями на вход канала (интерактивная демонстрация)
Рекомендации
^ Салим Бхатти. «Пропускная способность канала». Конспекты лекций для магистра наук. Сети передачи данных и распределенные системы D51 – Базовые коммуникации и сети . Архивировано из оригинала 21 августа 2007 г.
^ Джим Лесурф. «Сигналы похожи на шум!». Информация и измерения, 2-е изд .
^ Томас М. Кавер, Джой А. Томас (2006). Элементы теории информации. Джон Уайли и сыновья, Нью-Йорк. ISBN9781118585771.
^ Обложка, Томас М.; Томас, Джой А. (2006). «Глава 7: Пропускная способность канала». Элементы теории информации (второе изд.). Уайли-Интерсайенс. стр. 206–207. ISBN978-0-471-24195-9.
^ Смит, Джоэл Г. (1971). «Информационная емкость склар-гауссовских каналов с ограничением по амплитуде и дисперсии». Информация и контроль . 18 (3): 203–219. дои : 10.1016/S0019-9958(71)90346-9.
^ Хуанг, Дж.; Мейн, СП (2005). «Характеристика и расчет оптимальных распределений для канального кодирования». Транзакции IEEE по теории информации . 51 (7): 2336–2351. дои : 10.1109/TIT.2005.850108. ISSN 0018-9448.
^ Маккеллипс, Ал. (2004). «Простые жесткие границы пропускной способности канала дискретного времени с ограничением пиковой нагрузки». Международный симпозиум по теории информации . ИИЭР: 348–348. дои : 10.1109/ISIT.2004.1365385. ISBN978-0-7803-8280-0.
^ Дэвид Це, Прамод Вишванат (2005), Основы беспроводной связи, Cambridge University Press, Великобритания, ISBN9780521845274
^ Справочник по электротехнике. Ассоциация исследований и образования. 1996. с. Д-149. ISBN9780878919819.
^ Мэсси, Джеймс (ноябрь 1990 г.). «Причинность, обратная связь и направленная информация» (PDF) . Учеб. 1990 Международный. Симп. По теории информации и ее приложениям (ISITA-90), Waikiki, HI. : 303–305.
^ Шеннон, К. (сентябрь 1956 г.). «Пропускная способность зашумленного канала с нулевой ошибкой». Транзакции IEEE по теории информации . 2 (3): 8–19. дои : 10.1109/TIT.1956.1056798.
^ Пермутер, Хаим; Кафф, Пол; Ван Рой, Бенджамин; Вайсман, Цахи (июль 2008 г.). «Пропускная способность люка с обратной связью» (PDF) . IEEE Транс. Инф. Теория . 54 (7): 3150–3165. arXiv : cs/0610047 . дои : 10.1109/TIT.2008.924681. S2CID 1265.
^ Элишко, Охад; Пермутер, Хаим (сентябрь 2014 г.). «Пропускная способность и кодирование канала Изинга с обратной связью». Транзакции IEEE по теории информации . 60 (9): 5138–5149. arXiv : 1205.4674 . дои :10.1109/TIT.2014.2331951. S2CID 9761759.
^ Ахарони, Зив; Сабаг, Орон; Пермутер, Хаим Х. (сентябрь 2022 г.). «Пропускная способность каналов Изинга с большим алфавитом обратной связи посредством обучения с подкреплением». Транзакции IEEE по теории информации . 68 (9): 5637–5656. дои : 10.1109/TIT.2022.3168729. S2CID 248306743.
^ Пермутер, Хаим Генри; Вайсман, Цахи; Голдсмит, Андреа Дж. (февраль 2009 г.). «Каналы конечных состояний с инвариантной во времени детерминированной обратной связью». Транзакции IEEE по теории информации . 55 (2): 644–662. arXiv : cs/0608070 . дои : 10.1109/TIT.2008.2009849. S2CID 13178.