Channels

The dit.example_channels module is a catalog of canonical discrete memoryless channels (DMCs). Each constructor returns a conditional Distribution \(p(Y \mid X)\) – the representation consumed by channel_capacity() and by the channel-coding evaluation layer in dit.coding. Alphabets are integer-valued; an erasure is the integer just past the input alphabet (binary erasure 2, q-ary erasure q).

The catalog

Binary-input channels:

binary_symmetric_channel() – each bit is flipped with probability p; capacity \(1 - H_b(p)\),
binary_erasure_channel() – each bit is erased with probability \(\epsilon\); capacity \(1 - \epsilon\),
z_channel() – a 0 is received perfectly while a 1 is flipped to 0 with probability p (the canonical asymmetric channel),
binary_asymmetric_channel() – independent crossover probabilities for 0 and 1 (the BSC and Z-channel are special cases),
binary_symmetric_erasure_channel() – errors and erasures together.

q-ary channels:

q_ary_symmetric_channel() – correct with probability 1 - p, else a uniform wrong symbol; capacity \(\log_2 q - H_b(p) - p \log_2(q - 1)\),
q_ary_erasure_channel() – erased with probability \(\epsilon\); capacity \((1 - \epsilon) \log_2 q\),
noisy_typewriter() – each letter maps to itself or the next, each with probability one half; capacity \(\log_2(n / 2)\).

Trivial endpoints:

identity_channel() – the noiseless channel, capacity \(\log_2 n\),
useless_channel() – output independent of input, capacity 0.

Example

A channel can be fed directly to channel_capacity() or to a code’s probability_of_error():

In [1]: from dit.example_channels import binary_symmetric_channel

In [2]: from dit.algorithms import channel_capacity

In [3]: bsc = binary_symmetric_channel(0.1)

In [4]: channel_capacity(bsc)[0]
Out[4]: 0.5310044064107188

In [5]: from dit.coding import hamming

In [6]: hamming(3).probability_of_error(bsc, method='exact')
Out[6]: 0.14969440000000186

APIs

binary_symmetric_channel(p)[source]

The binary symmetric channel with crossover probability p.

Each transmitted bit is independently flipped with probability p. Its capacity is \(1 - H_b(p)\).

Parameters:: p (float) – The probability that a transmitted bit is flipped.
Returns:: channel – The conditional distribution p(Y | X) over {0, 1}.
Return type:: Distribution

binary_erasure_channel(epsilon)[source]

The binary erasure channel with erasure probability epsilon.

Each transmitted bit is independently erased with probability epsilon and otherwise received unchanged. Its capacity is \(1 - \epsilon\).

Parameters:: epsilon (float) – The probability that a transmitted bit is erased.
Returns:: channel – The conditional distribution p(Y | X) with output alphabet {0, 1, 2}, where 2 denotes an erasure.
Return type:: Distribution

z_channel(p)[source]

The Z-channel with crossover probability p.

A 0 is always received correctly; a 1 is flipped to 0 with probability p. This is the canonical binary asymmetric channel.

Parameters:: p (float) – The probability that a transmitted 1 is received as 0.
Returns:: channel – The conditional distribution p(Y | X) over {0, 1}.
Return type:: Distribution

binary_asymmetric_channel(p0, p1)[source]

The binary asymmetric channel.

A 0 is flipped to 1 with probability p0; a 1 is flipped to 0 with probability p1. The binary symmetric channel is the case p0 == p1 and the Z-channel is the case p0 == 0.

Parameters:

p0 (float) – The probability that a transmitted 0 is received as 1.
p1 (float) – The probability that a transmitted 1 is received as 0.

Returns:

channel – The conditional distribution p(Y | X) over {0, 1}.

Return type:

Distribution

binary_symmetric_erasure_channel(p, epsilon)[source]

The binary symmetric error-and-erasure channel.

A transmitted bit is erased with probability epsilon and flipped with probability p; the two events are disjoint, so p + epsilon <= 1.

Parameters:

p (float) – The probability that a transmitted bit is flipped.
epsilon (float) – The probability that a transmitted bit is erased.

Returns:

channel – The conditional distribution p(Y | X) with output alphabet {0, 1, 2}, where 2 denotes an erasure.

Return type:

Distribution

q_ary_symmetric_channel(q, p)[source]

The q-ary symmetric channel.

A symbol is received correctly with probability 1 - p and is otherwise received as one of the other q - 1 symbols, chosen uniformly. Its capacity is \(\log_2 q - H_b(p) - p \log_2(q - 1)\). The binary symmetric channel is the case q == 2.

Parameters:

q (int) – The alphabet size (q >= 2).
p (float) – The total probability that a symbol is received incorrectly.

Returns:

channel – The conditional distribution p(Y | X) over {0, ..., q - 1}.

Return type:

Distribution

q_ary_erasure_channel(q, epsilon)[source]

The q-ary erasure channel.

A symbol is erased with probability epsilon and otherwise received unchanged. Its capacity is \((1 - \epsilon) \log_2 q\). The binary erasure channel is the case q == 2.

Parameters:

q (int) – The alphabet size (q >= 2).
epsilon (float) – The probability that a symbol is erased.

Returns:

channel – The conditional distribution p(Y | X) with output alphabet {0, ..., q - 1, q}, where q denotes an erasure.

Return type:

Distribution

noisy_typewriter(n=26)[source]

The noisy typewriter channel (Cover & Thomas).

Each of the n letters is received either unchanged or as the next letter (cyclically), each with probability one half. Its capacity is \(\log_2(n / 2)\), achieved by using every other input letter.

Parameters:: n (int) – The alphabet size (n >= 2).
Returns:: channel – The conditional distribution p(Y | X) over {0, ..., n - 1}.
Return type:: Distribution

identity_channel(n=2)[source]

The noiseless channel over an n-symbol alphabet.

Every symbol is received unchanged, so the channel has capacity \(\log_2 n\).

Parameters:: n (int) – The alphabet size (n >= 1).
Returns:: channel – The conditional distribution p(Y | X) over {0, ..., n - 1}.
Return type:: Distribution

useless_channel(n=2)[source]

The zero-capacity channel over an n-symbol alphabet.

The output is uniform and independent of the input, so the channel carries no information and has capacity 0.

Parameters:: n (int) – The alphabet size (n >= 1).
Returns:: channel – The conditional distribution p(Y | X) over {0, ..., n - 1}.
Return type:: Distribution

Capacity

channel_capacity() takes a list of conditionals \(p(Y \mid X=x)\) (or a channel from this catalog) and returns the capacity together with a capacity-achieving input. For a joint distribution, use channel_capacity_joint().

The capacity is computed with the Blahut-Arimoto algorithm [Ari72, Bla72] (see also [CT06], Section 10.8). Write \(q = r P\) for the output distribution induced by an input \(r\), and \(D_x = D(P_x \| q)\). Then

\[\sum_x r(x) D_x = \I{X : Y} \leq C \leq \max_x D_x,\]

and the iteration stops once these two bounds agree to within max(atol, rtol * C) bits. The returned capacity is therefore certified rather than merely stationary. Three options trade speed for generality:

method='accelerated' (the default) takes the step \(r \leftarrow r\, e^{\mu D}\) of [MD04] with the adaptive \(\mu_k = D(r_k \| r_{k-1}) / D(q_k \| q_{k-1}) \geq 1\). When that step would decrease the mutual information, the classic step \(\mu = 1\) is taken instead. (The paper prints the reciprocal ratio, which is at most 1 by data processing and contradicts its own monotonicity bound.) method='ba' is the classic iteration.
eliminate=True iterates on a growing active set of inputs [Say00]. It adds inputs that violate the Kuhn-Tucker condition \(D_x \leq C\) and stops when none do. That condition is the upper bound above, taken over the full alphabet. This pays off when only a few of many inputs are used at capacity.
Weakly symmetric channels ([CT06], Theorem 7.2.1) are solved in closed form. So are square nonsingular channels whose optimal input uses every symbol: there \(D_x = C\) for all \(x\) is a linear system in \(\log q\). That closed form is used only when its own bound gap certifies it. No canonical reference for it is cited here.

Duplicate inputs and outputs that are never produced are removed before iterating.

channel_capacity_cost() adds an average cost constraint \(\mathbb{E}[c(X)] \leq B\) through Blahut’s Lagrangian form [Bla72], and sibson_capacity() computes Sibson’s capacity of order \(\alpha\). The latter is the maximum over inputs of sibson_mutual_information(), and it equals the Rényi radius \(\min_q \max_x D_\alpha(P_x \| q)\) [Csiszar95].

In [7]: from dit.algorithms import channel_capacity_cost, sibson_capacity

In [8]: channel_capacity_cost(bsc, cost=[0, 1], budget=0.2)[0]
Out[8]: 0.3577507789033368

In [9]: sibson_capacity(bsc, order=2)[0]
Out[9]: 0.713695814843359

channel_capacity(cdists, marginal=None, rtol=None, atol=None, max_iters=100000, method='accelerated', eliminate=False)[source]

Calculates the channel capacity from conditional distributions P(Y|X).

The capacity is computed with the Blahut-Arimoto algorithm [Ari72, Bla72], stopping once Blahut’s lower and upper bounds on the capacity agree to within tolerance, so the returned value is within max(atol, rtol * C) bits of the true capacity. Weakly symmetric [CT06] and square nonsingular channels are solved in closed form when the closed form certifies.

Parameters:

cdists (list, ndarray, Distribution) – A list of conditional distributions, a 2D array where rows are inputs and columns are outputs, or a conditional Distribution such as p(Y|X).
marginal (distribution | None) – The marginal distribution P(X). If provided, P*(X) is returned as a distribution object. If None, P*(X) is returned as a numpy array.
rtol (float or None) – Relative tolerance on the capacity. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance on the capacity, in bits. Defaults to ditParams[‘atol’].
max_iters (int) – Maximum number of Blahut-Arimoto iterations. A RuntimeWarning is raised if the bounds have not met by then.
method ({'accelerated', 'ba'}) – 'ba' is the classic iteration; 'accelerated' takes the step r <- r exp(mu D) of [MD04] with the adaptive mu = D(r_k || r_{k-1}) / D(q_k || q_{k-1}), falling back to the classic step whenever the mutual information would decrease.
eliminate (bool) – If True, iterate on a growing active set of inputs [Say00]. This helps when only a few of many inputs carry probability at capacity.

Returns:

cc (float) – The channel capacity.
marginal_opt (distribution or ndarray) – The optimal marginal P*(X).

channel_capacity_joint(dist, input_, output, marginal=False)[source]

Compute the channel capacity from input_ to output.

Parameters:

dist (Distribution) – The joint distribution.
input (iterable) – The random variables that are the input of the channel.
output (iterable) – The random variables that are the output of the channel.
marginal (bool) – Whether to return the marginal distribution. Defaults to False.

channel_capacity_cost(cdists, cost, budget, rtol=None, atol=None, max_iters=100000, method='accelerated')[source]

Capacity of a channel whose inputs carry a cost, under an average budget.

Computes C(B) = max { I[X : Y] : E[cost(X)] <= B } through Blahut’s Lagrangian form [Bla72]: for a multiplier s >= 0 the iteration maximizes I[X : Y] - s E[cost(X)] (the offset divergences D(P_x || q) - s cost(x) keep the bound-gap certificate), and C(B) = min_s max_p I - s (E[cost] - B). The multiplier is found by root-finding E[cost] = B.

Parameters:

cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().
cost (array_like) – The cost of each input, in the same order as the channel’s rows.
budget (float) – The maximum average cost.
rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
max_iters (int) – Maximum Blahut-Arimoto iterations per value of the multiplier.
method ({'accelerated', 'ba'}) – As in channel_capacity().

Returns:

cc (float) – The cost-constrained capacity, in bits.
pmf (np.ndarray) – An input distribution achieving it. If the optimal input at the final multiplier is not unique its cost may differ slightly from budget.
s (float) – The Lagrange multiplier, in bits per unit cost; the slope of C(B). 0 when the budget does not bind and inf when only the cheapest inputs are affordable.

Raises:

ditException – If the budget is below the cheapest input’s cost.

sibson_capacity(cdists, order, rtol=None, atol=None, max_iters=100000)[source]

Sibson’s capacity of order alpha, C_alpha = max_p I_alpha(X : Y).

Sibson’s alpha-mutual information is

I_alpha(X : Y) = alpha / (alpha - 1) log2 sum_y (sum_x p(x) P(y|x)^alpha)^(1/alpha),

and its maximum over inputs equals the Rényi radius min_q max_x D_alpha(P_x || q) [Csiszar95]. Every input r therefore gives the bounds I_alpha(r) <= C_alpha <= max_x D_alpha(P_x || q_r), where q_r is Sibson’s optimal output for r. The iteration r <- r exp(mu D_alpha(P_x || q_r)) with mu = max(1, alpha) reduces to Blahut-Arimoto at alpha = 1; the step is halved whenever I_alpha would decrease, and the iteration stops once the bounds meet.

Parameters:

cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().
order (float) – The order alpha > 0. 1 gives the Shannon capacity and numpy.inf the maximal leakage capacity log2 sum_y max_x P(y|x).
rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].
atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].
max_iters (int) – Maximum number of iterations.

Returns:

cc (float) – The capacity of order alpha, in bits.
pmf (np.ndarray) – An optimal input distribution.