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.5310044064107189

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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