Module 7. Channel and capacity

Let $X\sim\operatorname{Bernoulli}(p)$ and let $Y\in\{0,1,?\}$ be the output of BEC$(\varepsilon)$.

1. Conditional entropy

If $Y\in\{0,1\}$, no erasure occurred and the input is known exactly:

If $Y=?$, the erasure event is independent of the input value, so the posterior of $X$ is the prior:

Since $\Pr(Y=? )=\varepsilon$,

2. Mutual information

3. Maximization

Binary entropy is maximized at $p=1/2$ and equals one bit. Therefore

4. Why equal numerical $\varepsilon$ does not mean equally severe noise

At $\varepsilon=0.1$,

The difference is not that a BEC is physically “better” under every comparison. The parameters describe different observations. A BEC receiver knows the corruption location; a flipped BSC bit looks like an ordinary valid symbol. Thus the same numerical $\varepsilon$ is not a universal channel-severity scale.

The channel matrix is

1. Formula for $I(p)$

The output is one only when $X=1$ and no error occurs:

Hence

For $X=0$ the output is deterministic, while for $X=1$ its entropy is $h_2(\alpha)$. Thus

and

2. Stationary point

For $0<u<1$,

Therefore

Put

The condition $I'(p)=0$ becomes

so

and

Mutual information is concave in the input distribution, so the interior stationary point is the global maximum.

3. Numbers for $\alpha=0.25$

4. Uniform input

At $p=1/2$,

The uniform input is close but not optimal. Because symbol $1$ is the vulnerable one, it is used slightly less often.

Let $J$ be uniform over $M$ messages and let $\widehat J$ be reconstructed from $Y^n$.

1. Upper bound on codebook size

Fano's inequality gives

Then

We used the Markov chain $J\to X^n\to Y^n$, data processing, and

for a DMC.

2. Lower bound on error

Rearranging,

Since $R=(1/n)\log_2M$,

Therefore

3. Weak versus strong converse

For fixed $R>C$, this gives

This is a weak converse: it rules out vanishing error but does not prove convergence to one.

The strong converse for a DMC says

Thus $1-C/R$ is not the asymptotic error of an optimal code above capacity; it is only the weak lower bound obtained from Fano.

Let $Y$ be uniform over $K$ classes. Conditional on $Y=i$, the observed label equals $i$ with probability $1-\eta$, and each incorrect class has probability $\eta/(K-1)$.

1. Mutual information

The channel is weakly symmetric, so a uniform input produces a uniform output:

Each transition row holds the probabilities

Its entropy is

Therefore

The uniform input achieves capacity for this weakly symmetric channel, so the same expression is its capacity.

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

Therefore

3. Zero capacity

All rows coincide exactly when every output class has probability $1/K$. Thus

and

For $K=10$, this is $\eta=0.9$.

4. What remains at $\eta=1$

At $\eta=1$, the observed label is always wrong, but it still tells us one class that the example is guaranteed not to belong to. Substituting into the formula gives

For $K=10$,

Thus zero accuracy does not imply zero mutual information: a systematically wrong signal can still be partially invertible. Capacity need not be monotone after the full-randomization point.

5. Why one matrix does not describe instance-dependent noise

A fixed matrix $T_{ij}=\Pr(\widetilde Y=j\mid Y=i)$ assumes

For instance-dependent noise one needs

which changes with $x$. An averaged matrix can hide error concentration on difficult, ambiguous, or systematically biased subpopulations.

The codewords are

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

1. Pairwise distances

Every pair has Hamming distance four:

Hence

2. Guaranteed correction

Nearest-codeword decoding guarantees correction of

bit error.

3. Decode 1111010

Therefore

4. Why the coding guarantee is not a classifier guarantee

The distance argument treats arbitrary bit flips in an already formed codeword. In ECOC those “bits” are outputs of learned binary classifiers. Their errors can be correlated, unequal, example-dependent, concentrated in particular columns, and represented by continuous scores rather than ideal bits. Thus $d_{\min}$ provides useful geometric robustness, but actual performance also depends on the class partitions, component learners, and decoding rule.

The implementation below stores binary codewords as packed integers. For $n\le20$, this makes nearest-Hamming decoding fast through np.bitwise_count without changing the mathematical experiment.

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()

With the fixed seed, one run gives

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

Interpretation

Blahut–Arimoto reproduces the analytical values:

• BSC$(0.1)$: $C\approx0.5310044$, uniform maximizing input;
• BEC$(0.1)$: $C=0.9$, uniform maximizing input;
• Z$(0.25)$: $C\approx0.5582386$ and $$P_X^*\approx(0.5721744,0.4278256).$$

In the BSC experiment:

• at $R=0.25<C$, ensemble-average error decreases over these blocklengths;
• at $R=0.80>C$, it moves upward toward one, consistently with the strong converse;
• individual values need not be monotone for every seed or every codebook;
• a finite simulation is not a proof of an asymptotic theorem;
• exhaustive decoding scans all $M\approx2^{nR}$ codewords and is exponential in $n$.

The last point is the gap between an existence proof based on random codes and an engineering-ready coding system.

Let

with $Z$ independent of $X$.

For every admissible input,

because conditional on $X$, $Y$ is a shift of $Z$.

The noise entropy is

Also,

The Gaussian maximizes differential entropy at fixed variance, hence

Therefore

To attain the bound it is enough to choose

Then

the upper bound on $h(Y)$ holds with equality, and

This is bits per real discrete channel use. The continuous-time formula $B\log_2(1+S/N)$ bits/s uses a different normalization and should not be conflated with it.