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

Пусть $X\sim\operatorname{Bernoulli}(p)$, а $Y\in\{0,1,?\}$ — выход BEC$(\varepsilon)$.

1. Условная энтропия

Если $Y\in\{0,1\}$, стирания не произошло и вход известен точно:

Если $Y=?$, событие стирания независимо от значения входа, поэтому апостериорное распределение $X$ совпадает с исходным:

Поскольку $\Pr(Y=? )=\varepsilon$,

2. Взаимная информация

3. Максимизация

Бинарная энтропия максимальна при $p=1/2$ и равна одному биту. Следовательно,

4. Почему BEC и BSC с одинаковым $\varepsilon$ нельзя понимать как одинаково тяжёлый шум

При $\varepsilon=0.1$:

Разница возникает не потому, что BEC «физически лучше» при любом сравнении, а потому, что параметры описывают разные наблюдения. В BEC приёмник знает позицию повреждения; в BSC перевёрнутый бит выглядит как обычный допустимый символ. Поэтому одно и то же численное $\varepsilon$ не является универсальной шкалой тяжести канала.

Канал имеет матрицу

1. Формула для $I(p)$

Выход равен единице только когда $X=1$ и канал не совершил ошибку:

Следовательно,

При $X=0$ выход детерминирован, а при $X=1$ имеет бинарную энтропию $h_2(\alpha)$. Поэтому

Итак,

2. Стационарная точка

Для $0<u<1$

Поэтому

Положим

Условие $I'(p)=0$ эквивалентно

откуда

и

Функция $I(p)$ вогнута по входному распределению, поэтому внутренняя стационарная точка является глобальным максимумом.

3. Числа для $\alpha=0.25$

Подстановка даёт

4. Равномерный вход

При $p=1/2$:

Равномерный вход близок к оптимальному, но не оптимален. Асимметричный канал выгоднее использовать немного реже посылая символ $1$, который подвержен ошибке.

Пусть $J$ равномерно распределено по $M$ сообщениям, а $\widehat J$ восстанавливается из $Y^n$.

1. Верхняя оценка на размер кодовой книги

По неравенству Фано

Далее

Здесь использованы марковская цепь $J\to X^n\to Y^n$, неравенство обработки данных и оценка

для DMC.

2. Нижняя граница на ошибку

Переносим последний член в левую часть:

Так как $R=(1/n)\log_2M$,

Следовательно,

3. Слабая и сильная обратные теоремы

При фиксированном $R>C$ полученная граница отделяет ошибку от нуля в пределе:

Это слабая обратная теорема (weak converse). Она доказывает невозможность исчезающей ошибки, но не её стремление к единице.

Сильная обратная теорема (strong converse) для DMC утверждает более сильный результат:

Поэтому число $1-C/R$ нельзя интерпретировать как предельную ошибку оптимального кода выше пропускной способности: это только слабая нижняя оценка, полученная через Фано.

Пусть $Y$ равномерно распределена по $K$ классам. При условии $Y=i$ наблюдаемая метка равна $i$ с вероятностью $1-\eta$, а каждый неверный класс получает вероятность $\eta/(K-1)$.

1. Взаимная информация

Канал слабосимметричен, поэтому при равномерном входе выход тоже равномерен:

Каждая строка матрицы переходов содержит вероятности

Её энтропия равна

Следовательно,

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

2. $K=10$, $\eta=0.2$

Поэтому

3. Когда пропускная способность равна нулю

Строки канала совпадают тогда и только тогда, когда каждый выходной класс имеет вероятность $1/K$. Для диагонального элемента это требует

то есть

Для $K=10$ это $\eta=0.9$.

4. Что остаётся при $\eta=1$

При $\eta=1$ наблюдаемая метка всегда неверна, но она гарантированно сообщает, каким классом объект не является. Подстановка в формулу даёт

Для $K=10$

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

5. Почему одной матрицы недостаточно для шума, зависящего от объекта

Матрица $T_{ij}=\Pr(\widetilde Y=j\mid Y=i)$ предполагает

При шуме, зависящем от объекта, правильнее писать

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

Кодовые слова:

c1 = 0000000
c2 = 1111000
c3 = 1100110
c4 = 1010101

1. Попарные расстояния

Следовательно,

2. Гарантированное исправление

Декодер ближайшего кодового слова гарантированно исправляет

битовую ошибку.

3. Декодирование 1111010

Расстояния до кодовых слов:

Ближайшее слово — $c_2$, поэтому

4. Почему кодовая гарантия не равна гарантии классификатора

Классическая оценка по $d_{\min}$ рассматривает произвольное число ошибочных битов в уже сформированном кодовом слове. В ECOC эти «биты» производятся обученными бинарными классификаторами. Их ошибки могут:

• коррелировать;
• иметь разные вероятности;
• зависеть от объекта;
• систематически поражать одни и те же столбцы;
• выдавать непрерывные оценки, а не идеальные биты.

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

Ниже приведена воспроизводимая реализация. Кодовые слова хранятся как упакованные целые числа: при $n\le20$ это позволяет быстро считать расстояния Хэмминга через np.bitwise_count и не менять математическую постановку.

from __future__ import annotations

import math
import numpy as np


def binary_entropy(p: float) -> float:
    """Binary entropy in bits."""
    if p <= 0.0 or p >= 1.0:
        return 0.0
    return -p * math.log2(p) - (1.0 - p) * math.log2(1.0 - p)


def mutual_information(p_x: np.ndarray, channel: np.ndarray) -> float:
    """I(X;Y) in bits for an input distribution and a DMC matrix."""
    p_y = p_x @ channel
    joint = p_x[:, None] * channel
    x, y = np.nonzero(joint > 0)
    # Only positive joint mass contributes; unreachable outputs have p_y=0.
    return float(np.sum(joint[x, y] * np.log2(channel[x, y] / p_y[y])))


def blahut_arimoto(
    channel: np.ndarray,
    tol: float = 1e-12,
    max_iter: int = 100_000,
) -> tuple[float, np.ndarray, int]:
    """Return DMC capacity, a maximizing input distribution, and iterations."""
    channel = np.asarray(channel, dtype=float)
    if channel.ndim != 2 or np.any(channel < 0):
        raise ValueError("channel must be a nonnegative 2D array")
    if not np.allclose(channel.sum(axis=1), 1.0):
        raise ValueError("each row of channel must sum to one")

    p_x = np.full(channel.shape[0], 1.0 / channel.shape[0])
    for iteration in range(1, max_iter + 1):
        p_y = p_x @ channel
        ratio = np.divide(
            channel,
            p_y[None, :],
            out=np.ones_like(channel),
            where=channel > 0,
        )
        d_x = np.sum(
            np.where(channel > 0, channel * np.log(ratio), 0.0),
            axis=1,
        )
        p_new = p_x * np.exp(d_x)
        p_new /= p_new.sum()
        if np.max(np.abs(p_new - p_x)) < tol:
            p_x = p_new
            break
        p_x = p_new
    else:
        raise RuntimeError("Blahut-Arimoto did not converge")

    return mutual_information(p_x, channel), p_x, iteration


def random_noise_mask(
    rng: np.random.Generator,
    n: int,
    epsilon: float,
) -> np.uint32:
    """Generate an n-bit BSC noise mask packed into uint32."""
    bits = rng.random(n) < epsilon
    powers = np.left_shift(np.uint32(1), np.arange(n, dtype=np.uint32))
    return np.sum(bits.astype(np.uint32) * powers, dtype=np.uint32)


def simulate_random_codebook(
    rng: np.random.Generator,
    n: int,
    rate: float,
    epsilon: float,
    trials: int = 300,
) -> float:
    """Estimate block error for one distinct random binary codebook."""
    universe = 1 << n
    m = max(2, int(round(2 ** (n * rate))))
    if m > universe:
        raise ValueError("rate requires more distinct codewords than exist")

    codebook = rng.choice(universe, size=m, replace=False).astype(np.uint32)
    errors = 0

    for _ in range(trials):
        message = int(rng.integers(m))
        received = codebook[message] ^ random_noise_mask(rng, n, epsilon)
        distances = np.bitwise_count(codebook ^ received)
        min_distance = distances.min()
        candidates = np.flatnonzero(distances == min_distance)
        decoded = int(rng.choice(candidates))
        errors += decoded != message

    return errors / trials


def main() -> None:
    bsc = np.array([[0.9, 0.1], [0.1, 0.9]])
    bec = np.array([[0.9, 0.0, 0.1], [0.0, 0.9, 0.1]])
    z_channel = np.array([[1.0, 0.0], [0.25, 0.75]])

    print("Blahut-Arimoto")
    for name, channel in [
        ("BSC(0.1)", bsc),
        ("BEC(0.1)", bec),
        ("Z(0.25)", z_channel),
    ]:
        capacity, p_x, iterations = blahut_arimoto(channel)
        print(
            f"{name:9s}: C={capacity:.9f}, "
            f"p_X={p_x}, iterations={iterations}"
        )

    epsilon = 0.1
    capacity = 1.0 - binary_entropy(epsilon)
    print(f"\nBSC(0.1) capacity: {capacity:.9f} bits/use")

    rng = np.random.default_rng(7)
    blocklengths = [8, 12, 16, 20]
    rates = [0.25, 0.80]
    n_codebooks = 10
    trials = 300

    for rate in rates:
        side = "below" if rate < capacity else "above"
        print(f"\nR={rate:.2f} ({side} capacity)")
        for n in blocklengths:
            estimates = np.array(
                [
                    simulate_random_codebook(rng, n, rate, epsilon, trials)
                    for _ in range(n_codebooks)
                ]
            )
            m = max(2, int(round(2 ** (n * rate))))
            print(
                f"n={n:2d}, M={m:6d}: "
                f"mean P_e={estimates.mean():.6f}, "
                f"std={estimates.std(ddof=1):.6f}"
            )


if __name__ == "__main__":
    main()

Один запуск с указанным seed даёт:

Blahut-Arimoto
BSC(0.1) : C=0.531004406, p_X=[0.5 0.5], iterations=1
BEC(0.1) : C=0.900000000, p_X=[0.5 0.5], iterations=1
Z(0.25)  : C=0.558238627, p_X=[0.5721744 0.4278256], iterations=26

BSC(0.1) capacity: 0.531004406 bits/use

R=0.25 (below capacity)
n= 8, M=     4: mean P_e=0.082333, std=0.044055
n=12, M=     8: mean P_e=0.061000, std=0.020248
n=16, M=    16: mean P_e=0.046667, std=0.008165
n=20, M=    32: mean P_e=0.036000, std=0.011089

R=0.80 (above capacity)
n= 8, M=    84: mean P_e=0.462333, std=0.033740
n=12, M=   776: mean P_e=0.594667, std=0.022233
n=16, M=  7132: mean P_e=0.674333, std=0.031113
n=20, M= 65536: mean P_e=0.714000, std=0.030217

Как читать результат

Алгоритм Блахута—Аримото воспроизводит аналитические значения:

• BSC$(0.1)$: $C\approx0.5310044$, оптимальный вход равномерен;
• BEC$(0.1)$: $C=0.9$, оптимальный вход равномерен;
• Z$(0.25)$: $C\approx0.5582386$, а $$P_X^*\approx(0.5721744,0.4278256).$$

В моделировании BSC:

• при $R=0.25<C$ средняя ошибка по выбранному ансамблю кодовых книг уменьшается с ростом $n$;
• при $R=0.80>C$ она растёт в направлении единицы, что согласуется с сильной обратной теоремой;
• отдельные значения не обязаны быть монотонными для каждого seed и каждой кодовой книги;
• эксперимент не доказывает асимптотическую теорему: он показывает только поведение конкретного конечного ансамбля;
• декодер перебирает все $M\approx2^{nR}$ кодовых слов, поэтому его стоимость экспоненциальна по $n$.

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

Пусть

и $Z$ независимо от $X$.

Для любого допустимого входа

поскольку при фиксированном $X$ величина $Y$ является сдвигом $Z$.

Шум имеет энтропию

Кроме того,

При фиксированной дисперсии гауссовское распределение максимизирует дифференциальную энтропию. Поэтому

Следовательно,

Чтобы достичь границы, достаточно выбрать

Тогда

верхняя оценка на $h(Y)$ достигается с равенством, и

Это пропускная способность в битах на одно вещественное дискретное использование канала. Формула $B\log_2(1+S/N)$ бит/с относится к непрерывному каналу с полосой $B$ Гц и не должна смешиваться с этой нормировкой.