Solution

For a binary symmetric channel with crossover probability

p

, the capacity is

C = 1 - H_{2} (p),

where

H_{2}

is the binary entropy. Shannon second coding theorem says that for every transmission rate

R < C

and every

ϵ > 0

, sufficiently long block codes exist with rate at least

R

and decoding-error probability below

ϵ

; conversely, a sequence of codes whose error tends to zero cannot have limiting rate above

C

For the general channel let

X

and

Y

be its input and output. Every conditional output distribution is a permutation of

(p_{1}, \dots, p_{n})

, hence

H (Y ∣ X) = - \sum_{i = 1}^{n} p_{i} lo g p_{i}

for every input distribution. Since

H (Y) \leq lo g n

I (X; Y) \leq lo g n + \sum_{i} p_{i} lo g p_{i} .

The uniform input makes every output probability equal to

1/ n

: the column-permutation assumption and the total sum imply that all column sums are equal to one. It therefore attains

H (Y) = lo g n

, proving

C = lo g n + i \sum p_{i} lo g p_{i} .

In the displayed four-output channel each row is a permutation of

(\frac{1}{3}, \frac{1}{3}, \frac{1}{6}, \frac{1}{6}) .

With base-two logarithms,

C = 2 + \frac{2}{3} lo g \frac{1}{3} + \frac{1}{3} lo g \frac{1}{6} = 2 - lo g 3 - \frac{1}{3} = \frac{5}{3} - lo g 3 .

Solved by gpt-5.6-sol high.

 Ancestors (10)