Теория информации
Сетевая теория информации
Цели урока
- Описать MAC-канал и вычислить его область пропускных способностей через подмножества
- Объяснить суперпозиционное кодирование для деградированного широковещательного канала
- Понять принцип сетевого кодирования и теорему max-flow min-cut
- Знать открытые задачи сетевой теории информации: канал с помехами, общий BC
Предварительные знания
- Пропускная способность канала
- Взаимная информация
Как одновременно обслуживать нескольких пользователей в одной полосе без потери ёмкости? Где теория информации для сетей остаётся открытой?
- 5G Massive MIMO: 64 антенны, 16 пользователей - совместное декодирование на границе MAC-теории
- LTE NOMA: суперпозиционное кодирование для ближних и дальних абонентов в одной полосе
- BitTorrent и RLNC: случайное линейное сетевое кодирование ускоряет P2P на 30-50%
- 5G CoMP: координация базовых станций превращает interference channel в MAC
От одного канала к сетям
Shannon (1948) решил задачу одного канала. Сетевые задачи оказались принципиально сложнее. MAC-канал: решён Ахлсведе (1971) и Ляо (1972) независимо. Широковещательный канал: частично решён Бергером и Покровски (1973), деградированный - Бергмансом (1974). Канал с помехами: открыт с работы Аббинелли (1978). Сетевое кодирование: революция Ахлсведе-Цай-Ли-Йеунга (2000). Сегодня активно исследуются: multi-hop сети, D2D, федеративное обучение с ограниченными коммуникациями.
MAC-канал: множественный доступ
Ericsson применяет теорию MAC-каналов в Massive MIMO: при 64 антеннах базовой станции и 16 одновременных пользователях совместное декодирование достигает суммарной скорости 500 Мбит/с на 20 МГц. Это на границе MAC-теории Shannon - открытой в 1971 году Ахлсведе, а не в 1948-м.
CDMA как стратегия MAC-канала
IS-95 CDMA (Qualcomm, 1995): каждый пользователь умножает сигнал на псевдослучайный код длины 64. На приёмнике: корреляция с кодом пользователя + SIC. Это реализация MAC-декодирования. При 10 пользователях и идеальном SIC достигается 90% суммарной границы C_12. Реальная эффективность - 60-70% из-за неидеального оценивания канала.
Сколько ограничений определяют область пропускных способностей K-пользовательского MAC?
По одному ограничению для каждого непустого S ⊆ {1,...,K}. При K=2: 3 ограничения - пятиугольник. При K=3: 7 ограничений. Экспоненциальный рост делает решение общей задачи сложным.
Широковещательный канал и суперпозиционное кодирование
Теорема MAC полностью доказана. Широковещательный канал - нет. После 50 лет исследований область пропускных способностей BC для общего случая до сих пор открыта. Только для гауссова BC с деградацией (degraded BC) есть полное решение - через суперпозиционное кодирование.
LTE и 5G реализуют суперпозиционное кодирование в NOMA (Non-Orthogonal Multiple Access): ближний и дальний абонент получают разные мощности в одной полосе. Ближний (высокий SNR) делает SIC, дальний - нет. Это прямая инженерная реализация теоремы BC.
Дуальность MAC-BC: область пропускных способностей гауссового BC совпадает с дуальной областью MAC при той же суммарной мощности. Это нетривиальный результат Вишванатха и Тсе (2003), позволяющий решать задачи BC через более простой MAC.
В суперпозиционном кодировании для деградированного BC кто выполняет SIC?
В деградированном BC пользователь 1 (сильный, низкий шум) видит сигнал с высоким SNR. Он может сначала декодировать U1 (предназначенный слабому), вычесть, затем декодировать U2. Слабый пользователь 2 принимает U1 напрямую без SIC - его SNR недостаточен для распознавания U2.
Сетевое кодирование и теорема Слепяна-Вольфа
2000 год: Ахлсведе, Цай, Ли и Йеунг публикуют 'Network Information Flow'. Результат: в сети с пересечением потоков простая маршрутизация (forwarding) субоптимальна. Необходимо линейное кодирование в промежуточных узлах - сетевое кодирование. Это открыло новый класс задач теории информации.
BitTorrent и сетевое кодирование
BitTorrent использует принцип, близкий к сетевому кодированию: каждый пир передаёт случайные линейные комбинации блоков файла. Получатель накапливает линейно независимые пакеты и решает систему уравнений. Это random linear network coding (RLNC). Microsoft применяла RLNC в Avalanche (2005) для P2P-распространения. Результат: скорость скачивания на 30-50% выше при том же числе сидов.
Сетевая теорема Слепяна-Вольфа: K источников с корреляциями могут передавать независимо, достигая суммарной скорости H(X1,...,XK). Это обобщение теоремы SW на многотерминальные сети. Применяется в беспроводных сенсорных сетях: 100 датчиков температуры с коррелированными показаниями могут сжиматься независимо до суммарного H(X1,...,X100) бит, экономя 40-60% батареи.
Почему простая маршрутизация (forwarding) субоптимальна в butterfly-сети?
В butterfly-сети два получателя хотят получить (x1, x2), но через среднее ребро проходит только один бит. Маршрутизация: либо x1, либо x2. Кодирование x1 XOR x2: каждый получатель имеет одно из x1, x2 и восстанавливает другое через XOR.
Канал с помехами: открытая задача
Канал с помехами (interference channel): два передатчика к двум приёмникам, каждый приёмник хочет только одно сообщение, но принимает оба. Это базовая модель Wi-Fi с интерференцией соседних точек доступа. Задача открыта с 1978 года - общая пропускная способность неизвестна.
Etkin, Tse и Wang (2008) нашли к1-близкую к оптимуму в 1 бит/с/Гц границу для всех режимов помех. Это лучший известный результат. В 5G межсотовая интерференция управляется через CoMP (Coordinated Multi-Point): несколько базовых станций координируют передачу, превращая канал с помехами в MAC. Выигрыш: до 30% прироста ёмкости на краю ячейки.
Почему канал с помехами считается одной из главных открытых задач теории информации?
Канал с помехами решён только в крайних случаях: очень слабая помеха (treat as noise) и очень сильная (декодировать оба). Общий случай - открытая задача с 1978 года. Etkin-Tse-Wang (2008) дали лучшую известную границу, но точное решение отсутствует.
Связь с другими темами
Сетевая теория информации объединяет несколько направлений. MAC-канал: SIC - алгоритмическая реализация угловых точек многопользовательской области. BC через дуальность связан с MAC. Сетевое кодирование обобщает транспортные теоремы из теории графов (max-flow min-cut). В ML: федеративное обучение с ограниченной полосой - задача MAC-канала; многоагентные системы с частичными наблюдениями используют принципы сетевой теории информации.
- Related concepts — Связанная тема
Итоги
- MAC-канал: 2^K-1 ограничений, SIC достигает угловых точек; суммарная скорость = C(sum_P/N)
- Деградированный BC: суперпозиционное кодирование + SIC на сильном пользователе
- Сетевое кодирование: XOR/линейные комбинации в узлах достигают max-flow min-cut
- Канал с помехами: открытая задача с 1978 года; решён только в крайних режимах
Вопросы для размышления
- Почему теорема MAC-канала полностью доказана, а широковещательный и interference channel - нет?
- Как сетевое кодирование меняет фундаментальное ограничение маршрутизации в сети?
- В чём сходство и различие MAC-канала и задачи совместного сжатия коррелированных источников?