Модуль 7. Канал и пропускная способность

Как читать этот модуль. §§7.1–7.7 образуют классическое ядро: модель канала, пропускная способность, три базовых примера и обе части теоремы кодирования. В §7.6 стоит пройти хотя бы интуитивный подсчёт случайного кодирования — именно там становится видно, откуда берётся порог $R<I(X;Y)$. Нормальное приближение в конце §7.7 относится ко второму проходу. §§7.8–7.10 переносят канальный язык в ML: к шумным меткам, ECOC, обучаемой связи и LLM.

7.1. Надёжная передача через шум

В Модуле 6 мы старались убрать из сообщения всё предсказуемое и записать его как можно короче. Теперь задача почти противоположна: сообщение нужно провести через среду, которая меняет, стирает или зашумляет символы. И здесь избыточность, от которой мы только что избавлялись, внезапно становится полезной.

Представим двоичный канал, который независимо переворачивает каждый переданный бит с вероятностью $0.1$. Если отправить тысячу информационных бит без защиты, получатель в среднем увидит около ста ошибок. Самая очевидная защита — повторять каждый бит несколько раз и голосовать по большинству. Она действительно помогает, но быстро съедает скорость: трёхкратное повторение даёт лишь $1/3$ информационного бита на одно использование канала и всё равно не устраняет ошибку полностью.

Результат Шеннона говорит нечто гораздо более сильное. Для этого канала существует число

$$C=1-h_2(0.1)\approx0.531$$

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

$$\frac{1000}{C}\approx1883$$

использований канала, а не трёх тысяч. Это число ещё не обещает хороший короткий код длины $1883$ — конечные блоки мы обсудим отдельно. Но оно уже разрушает наивную дилемму «либо скорость, либо надёжность».

Шум не обязательно оплачивается повторением каждого символа. Хороший код раздвигает целые сообщения в пространстве длинных последовательностей так, чтобы типичный шум не перепутал их.

Отсюда полезно сразу развести две операции.

Ключевое слово здесь — структурированную. Случайно дописанные биты не помогают. Дополнительные символы должны сделать кодовые слова различимыми после характерных для канала искажений.

Именно это утверждает теорема кодирования для канала: у заданного канала есть порог $C$. Ниже него надёжная передача асимптотически достижима; выше него никакой код не заставит ошибку исчезнуть. Вторая часть особенно важна: пропускная способность — не характеристика конкретного алгоритма, а предел самой вероятностной модели канала при заданных ограничениях.

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

7.2. Дискретный канал без памяти и блочный код

Чтобы говорить о пределе надёжности, зафиксируем задачу. Нам понадобятся три объекта: сам канал, кодовая книга и декодер.

Дискретный канал без памяти

Дискретный канал без памяти (discrete memoryless channel, DMC) задаётся:

• конечным входным алфавитом $\mathcal X$;
• конечным выходным алфавитом $\mathcal Y$;
• переходным законом $$W(y\mid x)=\Pr(Y=y\mid X=x).$$

При $n$ использованиях канала условное распределение факторизуется:

$$W^n(y^n\mid x^n) = \prod_{i=1}^{n}W(y_i\mid x_i).$$

Слово «без памяти» относится к шуму при фиксированной входной последовательности. Оно не требует, чтобы сами входные символы были независимыми. Напротив, хорошее кодовое слово обычно содержит сильную зависимость между координатами: именно она и создаёт защитную структуру.

Два базовых канала

Двоичный симметричный канал (binary symmetric channel, BSC) с вероятностью инверсии $\varepsilon$ имеет матрицу

$$W_{\mathrm{BSC}} = \begin{pmatrix} 1-\varepsilon & \varepsilon\\ \varepsilon & 1-\varepsilon \end{pmatrix}.$$

Переданный бит независимо меняется на противоположный с вероятностью $\varepsilon$. Приёмник видит $0$ или $1$, но не знает, в какой позиции произошла ошибка.

Двоичный канал со стиранием (binary erasure channel, BEC) с вероятностью стирания $\varepsilon$ имеет выходной алфавит $\{0,1,?\}$:

$$W_{\mathrm{BEC}} = \begin{pmatrix} 1-\varepsilon & 0 & \varepsilon\\ 0 & 1-\varepsilon & \varepsilon \end{pmatrix}.$$

Здесь приёмник не знает значение стёртого бита, зато точно знает место потери. Позже мы увидим, насколько ценна эта дополнительная информация.

Блочный код

Пусть отправитель выбирает одно из $M$ равновероятных сообщений:

$$J\sim\operatorname{Unif}\{1,\ldots,M\}.$$

Код длины $n$ состоит из энкодера

$$f_n:\{1,\ldots,M\}\to\mathcal X^n$$

и декодера

$$g_n:\mathcal Y^n\to\{1,\ldots,M\}.$$

Энкодер отправляет кодовое слово

$$X^n=f_n(J),$$

канал выдаёт $Y^n$, а декодер строит оценку

$$\widehat J=g_n(Y^n).$$

Средняя вероятность блочной ошибки равна

$$P_e^{(n)}=\Pr(\widehat J\ne J).$$

Иногда требуется контролировать и худшее сообщение:

$$P_{e,\max}^{(n)} = \max_j\Pr(\widehat J\ne j\mid J=j).$$

Максимальная ошибка не меньше средней и предъявляет более сильное требование. Для обычного DMC обе постановки приводят к одной и той же пропускной способности; переход к максимальной ошибке требует дополнительного удаления худших кодовых слов (expurgation).

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

$$R_n=\frac{1}{n}\log_2M$$

измеряется в информационных битах на одно использование канала. Если $M=2^{nR}$, код различает $2^{nR}$ сообщений и передаёт $nR$ бит выбора за $n$ использований.

Скорость $R$ называется достижимой, если существует последовательность кодов, для которой

$$\liminf_{n\to\infty}R_n\ge R, \qquad P_e^{(n)}\to0.$$

Пропускная способность определяется как

$$C=\sup\{R:R\text{ достижима}\}.$$

Пока это только операционное определение. Оно говорит, что мы хотим измерить, но ещё не даёт способа вычислить $C$. Следующая формула связывает эту инженерную величину с взаимной информацией из Модуля 5.

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

7.3. Пропускная способность дискретного канала

Для конечного DMC без дополнительного ограничения на вход теорема Шеннона даёт

$$\boxed{ C=\max_{P_X}I(X;Y) }.$$

Распределение $P_X$ вместе с переходным законом $W(y\mid x)$ задаёт совместное распределение

$$P_{XY}(x,y)=P_X(x)W(y\mid x).$$

Для фиксированного $P_X$ величина $I(X;Y)$ отвечает на вопрос:

Сколько информации о случайном входе в среднем остаётся в одном выходе при данном способе использования канала?

Пропускная способность задаёт следующий вопрос:

Какое распределение входов использует канал лучше всего?

Это различие легко пропустить, потому что обе величины измеряются в битах на использование. Но $I(X;Y)$ — рабочая точка при выбранном $P_X$, а $C$ — оптимум по всем допустимым рабочим точкам.

Теорема состоит из двух половин.

• Достижимость (achievability): для любого $R<C$ существуют коды, у которых $P_e^{(n)}\to0$.
• Обратная часть (converse): если $R>C$, ошибка не может стремиться к нулю. Для DMC сильная обратная теорема утверждает даже $P_e^{(n)}\to1$.

Таким образом, взаимная информация получает операционный смысл. Она не просто измеряет статистическую зависимость между $X$ и $Y$: после оптимизации по входу она становится максимально возможной скоростью надёжной связи.

Как читать оптимизацию по $P_X$

Предположим, что матрица ошибок аннотатора рассматривается как канал от истинной метки $Y$ к наблюдаемой $\widetilde Y$. В реальном наборе данных распределение классов уже задано, поэтому

$$I(Y;\widetilde Y)$$

измеряет информацию, сохранившуюся при фактической частоте классов. А

$$\max_{P_Y}I(Y;\widetilde Y)$$

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

Несколько следствий

Для конечного DMC

$$0\le C\le\min\{\log_2|\mathcal X|,\log_2|\mathcal Y|\}.$$

Пропускная способность равна нулю тогда и только тогда, когда все строки переходной матрицы совпадают:

$$W(\cdot\mid x)=W(\cdot\mid x') \quad\text{для всех }x,x'.$$

В этом случае выход имеет одно и то же распределение при любом входе, а значит, не позволяет различать сообщения.

Если входы имеют разную стоимость, оптимизация получает ограничение:

$$C(\Gamma) = \max_{P_X:\,\mathbb E[c(X)]\le\Gamma}I(X;Y).$$

Эта строка особенно важна для непрерывных каналов. Без ограничения мощности можно было бы раздвигать сигналы всё дальше и получать неограниченную скорость. Ограничение ресурса — часть определения задачи, а не техническое приложение к формуле.

7.4. BSC, BEC и Z-канал

Три двоичных канала показывают, почему одного слова «шум» недостаточно. Важна не только частота повреждений, но и то, какую структуру ошибки наблюдает получатель.

Двоичный симметричный канал

Пусть $X\sim\operatorname{Bernoulli}(1/2)$. Для BSC выход также равномерен, а условная энтропия равна $h_2(\varepsilon)$. Поэтому

$$I(X;Y)=H(Y)-H(Y\mid X)=1-h_2(\varepsilon).$$

Симметрия канала гарантирует оптимальность равномерного входа:

$$\boxed{ C_{\mathrm{BSC}}=1-h_2(\varepsilon) }.$$

При $\varepsilon=0.1$ получаем

$$C_{\mathrm{BSC}}\approx0.5310 \quad\text{бит/использование}.$$

Обычно достаточно рассматривать $0\le\varepsilon\le1/2$. Если $\varepsilon>1/2$, приёмник может инвертировать каждый выход и получить эквивалентный BSC с вероятностью ошибки $1-\varepsilon$. В крайней точке $\varepsilon=1$ канал снова передаёт один бит без потери: он детерминированно меняет $0$ на $1$ и $1$ на $0$.

Двоичный канал со стиранием

Пусть $X\sim\operatorname{Bernoulli}(p)$. Если символ не стёрт, вход известен точно; если стёрт, остаётся вся исходная неопределённость. Поэтому

$$H(X\mid Y)=\varepsilon H(X)$$

и

$$I(X;Y)=(1-\varepsilon)H(X).$$

Максимум достигается при $p=1/2$:

$$\boxed{ C_{\mathrm{BEC}}=1-\varepsilon }.$$

При $\varepsilon=0.1$ это $0.9$ бит/использование — заметно больше, чем у BSC с тем же численным параметром. Причина не в том, что стирание «слабее» само по себе. BEC сообщает позицию повреждения, а BSC заставляет декодер сначала угадать, где ошибка вообще произошла.

Асимметричный Z-канал

Теперь рассмотрим канал

$$W= \begin{pmatrix} 1&0\\ \alpha&1-\alpha \end{pmatrix}.$$

Символ $0$ проходит безошибочно, а $1$ превращается в $0$ с вероятностью $\alpha$. Если

$$p=\Pr(X=1),$$

то

$$I(p)=h_2\bigl((1-\alpha)p\bigr)-p\,h_2(\alpha).$$

При $\alpha=0.25$ максимум достигается приблизительно при

$$p^*\approx0.4278, \qquad C\approx0.5582\text{ бита/использование}.$$

Равномерный вход даёт немного меньше:

$$I(1/2)\approx0.5488.$$

Разница численно невелика, но концептуально важна. Уязвимый символ следует использовать реже. Именно поэтому в формуле пропускной способности стоит максимум по $P_X$, а не автоматическое «возьмём равномерное распределение».

Для произвольной конечной матрицы этот максимум удобно находить алгоритмом Блахута—Аримото (Blahut–Arimoto); его реализация входит в вычислительное упражнение.

7.5. Гауссовский канал и ограничение мощности

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

Рассмотрим дискретновременной AWGN-канал

$$Y=X+Z, \qquad Z\sim\mathcal N(0,N),$$

где шум независим от входа, а средняя мощность сигнала ограничена:

$$\mathbb E[X^2]\le P.$$

Пропускная способность одного вещественного использования равна

$$\boxed{ C_{\mathrm{AWGN}} = \frac12\log_2\left(1+\frac PN\right) }$$

бит/использование. Оптимальный вход — гауссовский:

$$X\sim\mathcal N(0,P).$$

Механика формулы прозрачна. Поскольку $Y=X+Z$,

$$I(X;Y)=h(Y)-h(Z).$$

Шумовая энтропия фиксирована, а при заданной дисперсии $P+N$ энтропию выхода максимизирует гауссовское распределение. Гауссовский вход делает выход гауссовским и достигает верхней границы.

Для непрерывного канала с полосой $B$ Гц, средней мощностью сигнала $S$ и полной мощностью шума $N$ в этой полосе формула Шеннона—Хартли записывается как

$$\boxed{ C_{\mathrm{bps}} = B\log_2\left(1+\frac SN\right) }$$

бит/с. Первая формула измеряет биты на одно вещественное использование; вторая — биты в секунду. Совпадение логарифма не делает единицы взаимозаменяемыми.

Что говорит форма кривой

Обозначим отношение сигнал/шум (signal-to-noise ratio, SNR) через $\rho=P/N$. Тогда

• при $\rho\ll1$ $$C\approx\frac{\rho}{2\ln2};$$
• при $\rho\gg1$ $$C\approx\frac12\log_2\rho.$$

На малой SNR дополнительная мощность почти линейно увеличивает скорость. На большой SNR начинается логарифмический режим убывающей отдачи. Точное приращение при удвоении SNR равно

$$C(2\rho)-C(\rho) = \frac12\log_2\frac{1+2\rho}{1+\rho}.$$

Оно меньше $0.5$ бита/использование и лишь при высокой SNR приближается к $0.5$. Поэтому правило «удвоение мощности даёт полбита» — полезная высоко-SNR оценка, а не точное равенство для всей кривой.

Формула задаёт предел идеализированной модели. Реальная система добавляет замирания (fading), интерференцию, конечную модуляцию, ограничения оборудования, задержку, служебные данные и конечный блок. Фраза «близко к пределу Шеннона» всегда должна заканчиваться уточнением: к пределу какой именно модели и при каком критерии ошибки.

7.6. Почему случайное кодирование достигает $R<I(X;Y)$

Теперь мы подошли к самой неожиданной части теоремы. Чтобы доказать существование хорошего кода, Шеннон не начал с хитрой явной конструкции. Он предложил выбрать всю кодовую книгу случайно и оценить её среднюю ошибку.

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

Сначала полезно увидеть весь подсчёт в одной строке. Пусть в книге около $2^{nR}$ кодовых слов. Для фиксированного неверного слова вероятность случайно выглядеть правдоподобным рядом с принятым выходом имеет порядок $2^{-nI(X;Y)}$. Тогда суммарный риск ложного совпадения имеет порядок

$$2^{nR}\cdot2^{-nI(X;Y)} = 2^{-n(I(X;Y)-R)}.$$

Если $R<I(X;Y)$, количество конкурентов растёт медленнее, чем убывает вероятность ложного совпадения. В этом балансе и находится порог.

Теперь запишем аргумент точно. Зафиксируем входное распределение $P_X$ и скорость

$$R<I(X;Y).$$

Пусть $P_Y$ — выходное распределение, индуцированное $P_X$ и каналом.

Шаг 1. Случайная кодовая книга

Для каждого сообщения $j\in\{1,\ldots,M\}$, где

$$M\approx2^{nR},$$

независимо генерируем кодовое слово

$$X^n(j)\sim P_X^n.$$

Шаг 2. Информационная плотность

Для одной пары введём информационную плотность (information density)

$$\imath(x;y) = \log_2\frac{W(y\mid x)}{P_Y(y)}.$$

Её среднее под совместным распределением равно взаимной информации:

$$\mathbb E_{P_XW}[\imath(X;Y)]=I(X;Y).$$

Для канала без памяти

$$\imath(x^n;y^n) = \sum_{i=1}^{n}\imath(x_i;y_i).$$

По закону больших чисел у истинной пары

$$\frac1n\imath(X^n(J);Y^n) \xrightarrow{P} I(X;Y).$$

Шаг 3. Пороговый декодер

Декодер ищет единственное сообщение $j$, для которого

$$\imath(X^n(j);Y^n) \ge n\bigl(I(X;Y)-\delta\bigr).$$

Ошибка возникает по двум причинам.

1. Истинная пара не достигает порога. Вероятность этого стремится к нулю по закону больших чисел.
2. Какое-то неверное кодовое слово достигает порога.

Для неверного $j'\ne J$ кодовое слово $X^n(j')$ независимо от $Y^n$. Под произведением распределений $P_X^nP_Y^n$

$$\mathbb E\left[2^{\imath(X^n;Y^n)}\right]=1.$$

По неравенству Маркова

$$\Pr\left[ \imath(X^n;Y^n) \ge n(I-\delta) \right] \le 2^{-n(I-\delta)}.$$

Неверных слов около $2^{nR}$, поэтому объединение событий даёт

$$\Pr(\text{ложное совпадение}) \le 2^{nR}2^{-n(I-\delta)} = 2^{-n(I-R-\delta)}.$$

Выбираем $\delta>0$ так, чтобы

$$R<I(X;Y)-\delta.$$

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

$$C=\max_{P_X}I(X;Y).$$

Что дал этот аргумент

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

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

Но доказательство существования ещё не является удобным кодеком. Случайная книга содержит порядка $2^{nR}$ слов, её дорого хранить, а полный перебор при декодировании экспоненциален. Практические семейства — LDPC-, турбо- и полярные коды — добавляют структуру и эффективные декодеры. Теорема сначала показала, что искать имеет смысл; инженерная теория кодов научилась искать конструктивно.

7.7. Обратная теорема и конечная длина блока

Достижимость отвечает на вопрос «что можно сделать ниже $C$?». Обратная часть ставит предел любому возможному коду: выше $C$ надёжность нельзя вернуть более умным энкодером или декодером.

Короткая обратная граница через неравенство Фано

Пусть $J$ равномерно распределено по $M$ сообщениям, а

$$R=\frac1n\log_2M.$$

Неравенство Фано даёт

$$H(J\mid Y^n) \le 1+P_e^{(n)}\log_2M.$$

С другой стороны,

$$\begin{aligned} \log_2M &=I(J;Y^n)+H(J\mid Y^n)\\ &\le I(X^n;Y^n)+1+P_e^{(n)}\log_2M\\ &\le nC+1+P_e^{(n)}\log_2M. \end{aligned}$$

Последняя строка использует отсутствие памяти:

$$I(X^n;Y^n) \le \sum_{i=1}^{n}I(X_i;Y_i) \le nC.$$

Отсюда

$$\boxed{ P_e^{(n)} \ge 1-\frac{C}{R}-\frac{1}{nR} }.$$

Если $R>C$, правая часть при больших $n$ остаётся положительной. Значит, ошибка не может стремиться к нулю. Это слабая обратная теорема (weak converse).

Для DMC верна и сильная обратная теорема (strong converse): при фиксированном $R>C$

$$P_e^{(n)}\to1.$$

Иначе говоря, выше пропускной способности канал не переходит в режим «чуть хуже». При растущем блоке он почти полностью теряет способность надёжно различать сообщения на такой скорости.

Почему $R<C$ ещё не отвечает на инженерный вопрос

Пропускная способность — результат первого асимптотического порядка. Реальная система задаёт тройку

$$(n,R,\epsilon),$$

где $n$ — длина блока, $R$ — скорость, а $\epsilon$ — допустимая ошибка. Для короткого блока скорость ниже $C$ может всё ещё сопровождаться большой ошибкой. Между «асимптотически возможно» и «работает с задержкой 10 мс» лежит существенная инженерная задача.

Математическое углубление: нормальное приближение

Для многих регулярных каналов максимальная скорость при длине блока $n$ и целевой ошибке $\epsilon$ приближённо равна

$$R^*(n,\epsilon) \approx C- \sqrt{\frac{V}{n}}\,Q^{-1}(\epsilon) +O\left(\frac{\log n}{n}\right),$$

где $V$ — дисперсия канала (channel dispersion), а $Q^{-1}$ — обратная функция гауссовского хвоста.

Пропускная способность задаёт центр, а $V$ описывает флуктуации информационной плотности и тем самым цену короткого блока. Чем больше требуемая надёжность и чем меньше $n$, тем дальше приходится отступить от $C$.

7.8. Шумные метки как канал

Теперь перенесём ту же схему из линии связи в набор данных. Пусть $Y$ — истинная метка, а $\widetilde Y$ — метка, записанная после работы аннотатора или автоматического конвейера. Если ошибка зависит только от класса, переход задаётся матрицей

$$T_{ij} = \Pr(\widetilde Y=j\mid Y=i).$$

Получается буквальный вероятностный канал

$$Y\longrightarrow\widetilde Y.$$

Если признаки $X$ влияют на наблюдаемую метку только через чистую метку,

$$X\longrightarrow Y\longrightarrow\widetilde Y$$

— марковская цепь, и неравенство обработки данных даёт

$$I(X;\widetilde Y) \le I(X;Y).$$

Шумная метка не может сохранить больше информации о входе, чем чистая. Но величина потери зависит не только от доли ошибок, а от всей матрицы переходов и распределения классов.

Симметричный $K$-классовый шум

Пусть метка остаётся верной с вероятностью $1-\eta$, а при ошибке равномерно заменяется одним из $K-1$ других классов:

$$\Pr(\widetilde Y=j\mid Y=i) = \begin{cases} 1-\eta,&j=i,\\ \eta/(K-1),&j\ne i. \end{cases}$$

При равномерном $Y$ выход также равномерен, поэтому

$$\boxed{ I(Y;\widetilde Y) = \log_2K-h_2(\eta)-\eta\log_2(K-1) }.$$

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

При $K=10$ и $\eta=0.2$

$$I(Y;\widetilde Y)\approx1.9660\text{ бита}$$

из исходных $\log_2 10\approx3.3219$ бит.

Самая интересная точка — не $\eta=1$, а

$$\eta=\frac{K-1}{K}.$$

Здесь каждая строка матрицы становится равномерной, и информация исчезает полностью. При $\eta=1$ точность аннотатора равна нулю, но записанная метка сообщает одну достоверную вещь: истинный класс с ней не совпадает. Поэтому

$$I(Y;\widetilde Y) = \log_2\frac{K}{K-1}>0.$$

Для $K=10$ остаётся около $0.152$ бита. Этот пример хорошо показывает, почему точность и взаимная информация отвечают на разные вопросы: систематически неправильный сигнал может быть полностью или частично обратимым.

Где заканчивается матрица шума

Реальные ошибки разметки часто зависят от самого объекта $X$, от аннотатора, неоднозначности примера и процедуры фильтрации. Тогда одной матрицы классового шума (class-conditional noise) $T$ недостаточно.

Если $T$ известна, её можно использовать для прямой или обратной коррекции функции потерь. Однако обращение плохо обусловленной матрицы усиливает статистический шум, а оценённая $\widehat T$ добавляет собственную ошибку. Информационная потеря канала, идентифицируемость матрицы и численная устойчивость коррекции — три разные проблемы.

7.9. Канальное кодирование в ML: ECOC и DeepJSCC

В этом разделе слово «код» используется уже не как образ. В обеих конструкциях энкодер, канал и декодер являются частью алгоритма.

Коды выходов с исправлением ошибок

В кодах выходов с исправлением ошибок (error-correcting output codes, ECOC) каждому из $K$ классов назначается кодовое слово

$$c_k\in\{-1,+1\}^m.$$

Каждый столбец кодовой матрицы задаёт бинарную задачу, поэтому обучаются $m$ бинарных классификаторов. Их ответы образуют предсказанное слово $\widehat c(x)$, после чего выбирается ближайший класс-код.

Если минимальное расстояние Хэмминга между кодовыми словами равно $d_{\min}$, идеализированный декодер ближайшего слова исправляет до

$$\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$$

битовых ошибок. Геометрия та же, что в канальном кодировании: шары ошибок вокруг разных классов не должны пересекаться.

Но в классификации «канал ошибок» редко является независимым BSC. Бинарные классификаторы обучаются на одних данных, их ошибки коррелированы, столбцы имеют разную сложность, а вероятность ошибки зависит от $x$. Поэтому большой $d_{\min}$ создаёт полезный геометрический запас, но не является самостоятельной гарантией качества классификатора.

Обучаемое совместное кодирование источника и канала

Классическая цифровая система часто разделяет три этапа:

1. сжатие источника;
2. защиту от ошибок;
3. отображение кодовых символов в физический сигнал.

В совместном кодировании источника и канала (joint source-channel coding, JSCC) отображение оптимизируется целиком под меру искажения и модель канала. В DeepJSCC нейронный энкодер, дифференцируемый слой канала и нейронный декодер образуют цепочку

$$x \xrightarrow{f_\theta} z \xrightarrow{W}\widetilde z \xrightarrow{g_\phi}\widehat x.$$

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

Этот результат не отменяет теорему разделения источника и канала. При стандартных стационарных моделях, асимптотически длинных блоках и согласованных критериях раздельная схема может быть оптимальной. Если на один символ источника приходится $\kappa$ использований канала, условие достижимости искажения имеет вид $R(D)<\kappa C$; запись $R(D)<C$ предполагает $\kappa=1$ и согласованные единицы. DeepJSCC работает в том месте, где практическая постановка отличается от идеальной асимптотики: блок короток, задержка ограничена, модель канала может быть неточной, а качество измеряется непрерывным искажением, а не только безошибочным восстановлением битов.

7.10. LLM как канал: точная постановка и границы аналогии

Слово «канал» естественно возникает и вокруг языковых моделей. Здесь полезно не отказываться от аналогии, а сначала построить версию, в которой она математически точна.

Канал от промпта к ответу

Зафиксируем веса модели, правила формирования контекста и алгоритм генерации. Пусть $X$ — случайный промпт, а $Y$ — сгенерированный ответ. Тогда

$$q_\theta(y\mid x)$$

задаёт условное распределение выхода и, следовательно, стохастический канал от $X$ к $Y$. При фиксированном распределении промптов можно вычислять

$$I(X;Y).$$

Если декодирование детерминировано, канал просто становится детерминированным отображением. Если используется сэмплирование с температурой, top-$p$ или иная случайная процедура, её правила входят в переходный закон.

Чтобы говорить именно о пропускной способности, нужно добавить операционную задачу. Например, отправитель выбирает сообщение $J$, кодирует его допустимым промптом $x(J)$ длины не более $L$, модель генерирует ответ, а декодер пытается восстановить $J$. Только после задания множества промптов, стоимости, единицы использования и критерия ошибки выражение «максимальная скорость» получает точный смысл.

Такой эксперимент можно поставить. Но он будет измерять пропускную способность конкретного протокола «промпт → модель → ответ», а не универсальную величину, присущую архитектуре трансформера вне задачи.

Контекстное окно как ресурс

Окно длины $L$ токенов — реальный ресурс: оно ограничивает объём входа и вычислительную стоимость. Но из числа токенов нельзя напрямую получить количество надёжно переданных битов.

Причины теперь можно сформулировать положительно. Чтобы перевести длину окна в канальную величину, пришлось бы задать:

• распределение и допустимый набор промптов;
• стоимость разных токенов или последовательностей;
• переходное распределение ответов;
• кодер и декодер сообщений;
• критерий ошибки;
• роль знаний, уже находящихся в параметрах модели.

Без этих элементов длина контекста остаётся размером ресурса, а не шенноновской пропускной способностью.

Работа Lost in the Middle показала, что качество извлечения релевантной информации может существенно зависеть от её позиции: в исследованных задачах модели часто лучше использовали начало и конец длинного контекста, чем середину. Это важное эмпирическое свойство конкретных моделей и протоколов. Оно не выводится автоматически из DPI или из абстрактной «ёмкости окна»; механизм зависит от архитектуры, позиционного кодирования, обучения и задачи.

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

Что измеряют веса внимания

Строка весов внимания (attention weights)

$$\alpha_{i,\cdot}$$

суммируется в единицу и потому внешне похожа на распределение. Но она является коэффициентами смешивания значений, а не переходным законом от входного токена к выходному сообщению. Результат слоя зависит также от векторов значений (value vectors), нескольких голов, остаточного потока и последующих нелинейностей.

Энтропия

$$H(\alpha_{i,\cdot})$$

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

Цепочка рассуждений

Цепочка рассуждений (chain-of-thought, CoT) увеличивает число сгенерированных токенов, объём внешнего промежуточного состояния и вычисления во время вывода (test-time compute). Это может улучшать решение сложных задач. Канальная метафора — «модель получила больше последовательных использований внешнего носителя» — может быть полезна как исследовательская интуиция. Но она пока не является теоремой о росте шенноновской пропускной способности модели. В Модуле 13 мы вернёмся к этой границе подробнее.

7.11. Как формализовать канал в ML-системе

Канальный язык наиболее полезен не тогда, когда даёт эффектную метафору, а когда заставляет точно описать эксперимент. Перед вычислением MI или пропускной способности удобно заполнить короткую спецификацию.

Сравним две постановки.

Отсюда следуют два ключевых различия:

$$\boxed{ \text{пропускная способность} \ne \text{взаимная информация при фиксированном входе} \ne \text{размер тензора или окна} }$$

и

$$\boxed{ \text{теорема о канале} \ne \text{эмпирический результат} \ne \text{архитектурная аналогия} }.$$

Это не запрет на аналогии. Это способ сделать их плодотворными: сначала понять, какая часть конструкции является настоящим каналом, а затем ясно обозначить, где начинается эвристика.

7.13. Заключение

В Модуле 6 вероятностная модель превратилась в счёт в битах. В Модуле 7 взаимная информация получила второй операционный смысл: после оптимизации по входу она задаёт предельную скорость надёжной передачи через шум.

$$\boxed{ C=\max_{P_X}I(X;Y) }.$$

За короткой формулой стоит целая конструкция.

• Канал задаёт переходный закон и ограничения ресурса.
• Кодовая книга превращает сообщения в длинные, хорошо разделённые последовательности.
• При $R<C$ случайное кодирование доказывает существование кодов с исчезающей ошибкой.
• При $R>C$ обратная теорема запрещает надёжную передачу любому коду.
• При конечном $n$ одной пропускной способности недостаточно: важны допустимая ошибка и дисперсия канала.

Главная интеллектуальная перемена состоит в том, что шум перестаёт быть локальной помехой, которую нужно исправлять по одному символу. Код работает с геометрией всего блока. Ошибки отдельных использований остаются, но целое сообщение можно сделать надёжно различимым.

Для ML эта идея имеет два уровня. В шумных метках, ECOC и DeepJSCC канал является частью строгой модели или алгоритма. В рассуждениях о контексте, внимании (attention) и CoT канальный язык пока чаще служит дисциплинирующей аналогией. В обоих случаях полезен один и тот же вопрос: можем ли мы явно записать вход, выход, переходный закон, ресурс и задачу декодирования?

Так завершается классическое ядро теории Шеннона. Кодирование источника убирает предсказуемую избыточность; канальное кодирование добавляет избыточность, специально устроенную для борьбы с шумом; взаимная информация связывает обе стороны с точными пределами.

В Модуле 8 мы перейдём от описания источников и каналов к нормативному вопросу: какое распределение выбирать, когда известны лишь ограничения? Ответом станет принцип максимальной энтропии (maximum entropy).

Основные источники

1. C. E. Shannon, A Mathematical Theory of Communication, 1948.
2. T. Cover, J. Thomas, Elements of Information Theory, 2nd ed., 2006, Chapters 7–9.
3. Y. Polyanskiy, Y. Wu, Information Theory: From Coding to Learning, 2025, главы о канальном кодировании и конечной длине блока.
4. Y. Polyanskiy, H. V. Poor, S. Verdú, Channel Coding Rate in the Finite Blocklength Regime, 2010.
5. R. Blahut, Computation of Channel Capacity and Rate-Distortion Functions, 1972; S. Arimoto, An Algorithm for Computing the Capacity of Arbitrary Discrete Memoryless Channels, 1972.
6. G. Patrini et al., Making Deep Neural Networks Robust to Label Noise: A Loss Correction Approach, 2017.
7. T. Dietterich, G. Bakiri, Solving Multiclass Learning Problems via Error-Correcting Output Codes, 1995.
8. E. Bourtsoulatze, D. B. Kurka, D. Gündüz, Deep Joint Source-Channel Coding for Wireless Image Transmission, 2019.
9. N. F. Liu et al., Lost in the Middle: How Language Models Use Long Contexts, 2024.
10. S. Jain, B. C. Wallace, Attention is not Explanation, 2019; S. Wiegreffe, Y. Pinter, Attention is not not Explanation, 2019.