Back to the on-screen lesson · Print

Symmetric channels

Rows and columns that are permutations of each other; C = log|Y| − H(row) at the uniform input.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to recognise symmetric and weakly symmetric channels from their transition matrices, prove that the uniform input is optimal for them and compute their capacity as $\log_2 |\mathcal{Y}|$ minus a row entropy, and explain through the noisy typewriter how non-overlapping output sets give error-free communication at capacity. You will combine capacities correctly for channels used in parallel, in cascade and over time, using data processing to bound cascades and independence to add parallel channels, and you will reduce two symmetric channels in series to a single equivalent channel.

2. Symmetric channels

A channel is symmetric when every row of its transition matrix is a permutation of every other row and every column is a permutation of every other column; it is weakly symmetric when the rows are permutations of one another and the column sums are all equal. In either case every row has the same entropy $H(\text{row})$, so $H(Y \mid X) = H(\text{row})$ whatever the input, and the uniform input makes the output uniform, so $$C = \log_2 |\mathcal{Y}| - H(\text{row}),$$ attained at the uniform input. The BSC is the case $|\mathcal{Y}| = 2$, row $(1 - \varepsilon, \varepsilon)$. The noisy typewriter with $m$ keys, each printing itself or its neighbour with probability $\tfrac{1}{2}$, has $C = \log_2 m - 1$, and shows the idea behind all channel coding: use only inputs whose output sets do not overlap (every other key), and zero-error communication at capacity follows. For a channel that is not symmetric, such as the Z-channel, the noise entropy depends on the input and the maximisation must be done in earnest.

3. Spotting a symmetric channel

A channel is symmetric when the rows of its transition matrix are permutations of one another and so are the columns; weakly symmetric when the rows are permutations of one another and all the column sums are equal. Either condition gives the same two facts, and those two facts give the capacity in one line. First, every row has the same entropy, so $H(Y \mid X) = H(\text{row})$ whatever the input. Second, a uniform input makes the output uniform (that is what the column condition buys), so $H(Y) = \log_2 |\mathcal{Y}|$ is attainable. Hence $$C = \log_2 |\mathcal{Y}| - H(\text{row}),$$ at the uniform input.

The noisy typewriter is the picture worth keeping. With $m$ keys, each printing itself or the next with probability $\tfrac{1}{2}$, every row is a permutation of $(\tfrac{1}{2}, \tfrac{1}{2}, 0, \ldots)$, so $H(\text{row}) = 1$ and $C = \log_2 m - 1 = \log_2 (m/2)$.

And here the capacity has a constructive meaning that the general theorem does not: use only every other key. With $m = 4$, sending only $A$ and $C$ gives outputs $\{A, B\}$ and $\{C, D\}$, disjoint sets, so the receiver never confuses them — $\log_2 (4/2) = 1$ bit per use, with no coding, no block length and no probability of error at all. That is unusual; for most channels capacity is only reached in the limit of long blocks.

4. Solving the practice problems

1. $2^k$ inputs and outputs, each input received as one of $2^j$ equally likely outputs: the row is uniform on $2^j$ values, so $H(\text{row}) = j$ and $C = k - j$ bits per use.
2. Noisy typewriter with $2^k$ keys: $H(\text{row}) = 1$, so $C = k - 1$.
3. Rows $(0.7, 0.2, 0.1)$ and its rotations: rows and columns are permutations, so the channel is symmetric, the uniform input is optimal, and $C = \log_2 3 - H(0.7, 0.2, 0.1) = 1.585 - 1.157 = 0.428$.

Common mistakes

• Using $\log_2 |\mathcal{X}|$ where the formula wants $\log_2 |\mathcal{Y}|$; they differ whenever the alphabets do.
• Computing the entropy of a column instead of a row.
• Assuming any channel with equal row entropies is symmetric: the columns matter too, or the uniform input may not make the output uniform.

5. A ternary symmetric channel

1. Rows $(0.8, 0.1, 0.1)$ and its rotations: symmetric, with $H(\text{row}) = 0.8 \cdot 0.322 + 2 \cdot 0.1 \cdot 3.322 = 0.922$ bits.

   Row entropy.

2. $C = \log_2 3 - 0.922 = 1.585 - 0.922 = 0.663$ bits per use at the uniform input.

6. Weakly symmetric

1. Rows $(\tfrac{1}{3}, \tfrac{1}{6}, \tfrac{1}{2})$ and $(\tfrac{1}{3}, \tfrac{1}{2}, \tfrac{1}{6})$: permutations of each other; column sums $\tfrac{2}{3}, \tfrac{2}{3}, \tfrac{2}{3}$, all equal.

   Columns are not permutations, but their sums agree.

2. The uniform input still gives a uniform output, so $C = \log_2 3 - H(\tfrac{1}{3}, \tfrac{1}{6}, \tfrac{1}{2}) = 1.585 - 1.459 = 0.126$ bits.

7. A symmetric channel with a uniform row

1. $16$ inputs, $16$ outputs, each input received as one of $4$ equally likely outputs.

2. Each row is uniform on $4$ values, so $H(\text{row}) = \log_2 4 = 2$ bits.

3. $C = \log_2 16 - 2 = 4 - 2 = 2$ bits per use: the noise costs exactly the two bits it scrambles.

8. A ternary symmetric channel

1. Rows $(0.8, 0.1, 0.1)$ and its two rotations.

2. $H(\text{row}) = 0.8 \cdot 0.322 + 2 \cdot 0.1 \cdot 3.322 = 0.258 + 0.664 = 0.922$ bits.

   Every row has this entropy; the order of the entries does not matter.

3. $C = \log_2 3 - 0.922 = 1.585 - 0.922 = 0.663$ bits per use at the uniform input.

9. Your turn: $16$ inputs, each received as one of $4$ equally likely outputs, symmetric

1. $H(\text{row}) = \log_2 4 = 2$; $\log_2 |\mathcal{Y}| = 4$.

2. Your turn: work this step out. Its working is at the end of the packet.

   $C = 4 - 2 = 2$ bits per use.

10. Guided practice

A channel has $8$ inputs and $8$ outputs. Each input is received as one of $2$ equally likely outputs, and the channel is symmetric. What is its capacity in bits per use?

Computed value: _answer

11. Guided practice

A noisy typewriter has $64$ keys; each key prints itself or the next key (cyclically), each with probability $\tfrac{1}{2}$. What is the capacity in bits per use?

Computed value: _answer

12. Practice

A channel has $32$ inputs and $32$ outputs. Each input is received as one of $4$ equally likely outputs, and the channel is symmetric. What is its capacity in bits per use?

Computed value: _answer

13. Practice

A noisy typewriter has $4$ keys; each key prints itself or the next key (cyclically), each with probability $\tfrac{1}{2}$. What is the capacity in bits per use?

Computed value: _answer

14. Somewhere new

A channel has transition matrix with rows $(0.7, 0.2, 0.1)$, $(0.1, 0.7, 0.2)$, $(0.2, 0.1, 0.7)$. Which is true?

• It is symmetric, so $C = \log_2 3 - H(0.7, 0.2, 0.1) \approx 0.428$ bits at the uniform input
• It is not symmetric because the rows are different
• Its capacity is $\log_2 3$ because it has three inputs

15. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

16. Test question

A channel has $32$ inputs and $32$ outputs. Each input is received as one of $2$ equally likely outputs, and the channel is symmetric. What is its capacity in bits per use?

Computed value: _answer

17. What you can do now

You can compute the capacity of any symmetric channel and of combinations of channels. Next: the theorem that makes capacity the true speed limit of reliable communication.

Working for the steps left to you

9. Your turn: $16$ inputs, each received as one of $4$ equally likely outputs, symmetric, step 2