Information Theory for ML7 / 16

Module 7. Channel and capacity

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Checked: 0 / 29 · Correct: 0

Question 7.1.1

7.1. Reliable communication through noise

What is the main difference between source coding and channel coding?

One correct optionAThe former is continuous and the latter only discreteBSource coding removes statistical redundancy; channel coding adds structured redundancy for noise protectionCOnly source coding uses probabilityDThere is no fundamental distinction

A) The former is continuous and the latter only discrete

B) Source coding removes statistical redundancy; channel coding adds structured redundancy for noise protection

C) Only source coding uses probability

D) There is no fundamental distinction

Answer and explanation

Correct answer: B. Source coding shortens descriptions, while channel coding deliberately spends extra symbols so messages remain distinguishable after corruption.

Question 7.2.1

7.2. A discrete memoryless channel and a block code

What does memorylessness of a DMC mean?

One correct optionAInput symbols must be independentBThe encoder cannot remember earlier messagesCConditional on the input sequence,

W^n(y^n\mid x^n)=\prod_iW(y_i\mid x_i)

DThe output is independent of the input

A) Input symbols must be independent

B) The encoder cannot remember earlier messages

C) Conditional on the input sequence, $W^n(y^n\mid x^n)=\prod_iW(y_i\mid x_i)$

D) The output is independent of the input

Answer and explanation

Correct answer: C. Conditional independence belongs to the channel given its inputs. Code symbols themselves can be highly dependent.

Question 7.2.2

7.2. A discrete memoryless channel and a block code

What does $R=(1/n)\log_2M$ measure?

One correct optionAInformation bits per channel useBErrors per blockCCapacity in bits per secondDTransition-matrix size

A) Information bits per channel use

B) Errors per block

C) Capacity in bits per second

D) Transition-matrix size

Answer and explanation

Correct answer: A. Choosing among M messages carries log₂M bits over n channel uses.

Question 7.2.3

7.2. A discrete memoryless channel and a block code

How do average and maximal error compare?

One correct optionAAverage error is always largerBThey are equal for every codeCMaximal error depends only on noiseDMaximal error is at least the average and imposes a stronger per-message requirement

A) Average error is always larger

B) They are equal for every code

C) Maximal error depends only on noise

D) Maximal error is at least the average and imposes a stronger per-message requirement

Answer and explanation

Correct answer: D. Average error can hide a few very poor codewords; maximal error controls the worst message.

Question 7.3.1

7.3. Capacity of a discrete channel

The capacity of a finite DMC without a cost constraint is

One correct optionA

H(X)

under a uniform inputB

\max_{P_X}I(X;Y)

\log_2|\mathcal Y|

for every channelD

I(X;Y)

under the actual input distribution

A) $H(X)$ under a uniform input

B) $\max_{P_X}I(X;Y)$

C) $\log_2|\mathcal Y|$ for every channel

D) $I(X;Y)$ under the actual input distribution

Answer and explanation

Correct answer: B. Capacity optimizes mutual information over how the channel is used; a fixed input distribution is one operating point.

Question 7.3.2

7.3. Capacity of a discrete channel

When is the capacity of a finite DMC zero?

One correct optionAWhen all transition-matrix rows are identicalBWhen the matrix contains any zeroCWhen the input alphabet is binaryDWhenever noise is nonzero

A) When all transition-matrix rows are identical

B) When the matrix contains any zero

C) When the input alphabet is binary

D) Whenever noise is nonzero

Answer and explanation

Correct answer: A. Identical rows make the output unable to distinguish inputs. Nonzero noise alone does not imply zero capacity.

Question 7.3.3

7.3. Capacity of a discrete channel

Why need $I(Y;\widetilde Y)$ under the actual class distribution not equal the capacity of the label-noise matrix?

One correct optionAMutual information requires uniform classesBCapacity ignores the channel matrixCCapacity maximizes over the clean-label distribution, while the dataset fixes that distributionDThey are identical by definition

A) Mutual information requires uniform classes

B) Capacity ignores the channel matrix

C) Capacity maximizes over the clean-label distribution, while the dataset fixes that distribution

D) They are identical by definition

Answer and explanation

Correct answer: C. One quantity describes a given dataset; the other describes the best possible use of the same channel matrix.

Question 7.4.1

7.4. BSC, BEC, and the Z-channel

What is true for a BSC with crossover probability $\varepsilon>1/2$ ?

One correct optionACapacity is necessarily zeroBThe channel cannot be decodedC

1-h_2(\varepsilon)

becomes negativeDInverting every output gives an equivalent BSC with crossover

1-\varepsilon<1/2

A) Capacity is necessarily zero

B) The channel cannot be decoded

C) $W^n(y^n\mid x^n)=\prod_iW(y_i\mid x_i)$ becomes negative

D) Inverting every output gives an equivalent BSC with crossover $1-\varepsilon<1/2$

Answer and explanation

Correct answer: D. At ε=1, the channel still carries one bit: it deterministically flips every symbol.

Question 7.4.2

7.4. BSC, BEC, and the Z-channel

The capacity of BEC $(\varepsilon)$ is

One correct optionA

1-\varepsilon

1-h_2(\varepsilon)

h_2(\varepsilon)

\varepsilon

A) $H(X)$

B) $1-h_2(\varepsilon)$

C) $h_2(\varepsilon)$

D) $\varepsilon$

Answer and explanation

Correct answer: A. An erasure leaves all input uncertainty, while a non-erased output reveals the input exactly.

Question 7.4.3

7.4. BSC, BEC, and the Z-channel

What does the Z-channel example demonstrate?

One correct optionAEvery binary channel has zero capacityBBlahut–Arimoto works only for symmetric channelsCA uniform input need not be optimal for an asymmetric channelDMutual information is linear in

P_X

A) Every binary channel has zero capacity

B) Blahut–Arimoto works only for symmetric channels

C) A uniform input need not be optimal for an asymmetric channel

D) Mutual information is linear in $P_X$

Answer and explanation

Correct answer: C. At α=0.25, the vulnerable symbol 1 is optimally used with probability about 0.4278, not 0.5.

Question 7.5.1

7.5. The Gaussian channel and a power constraint

For the real discrete AWGN channel $Y=X+Z$ , $\mathbb E[X^2]\le P$ , and $Z\sim\mathcal N(0,N)$ , capacity is

One correct optionA

\log_2(P/N)

bits/sB

\frac12\log_2(1+P/N)

bits per real useC

B\log_2(1+P/N)

bits per useD

P/N

bits per use

A) $H(X)$ bits/s

B) $\frac12\log_2(1+P/N)$ bits per real use

C) $I(X;Y)$ bits per use

D) $P/N$ bits per use

Answer and explanation

Correct answer: B. The factor 1/2 belongs to one real discrete use. Shannon–Hartley in bits/s additionally uses bandwidth B.

Question 7.5.2

7.5. The Gaussian channel and a power constraint

What is the exact capacity increment when the SNR $\rho$ of a real AWGN channel is doubled?

One correct optionAExactly one bit at every SNRBExactly half a bit at every SNRCCapacity doublesD

\frac12\log_2\frac{1+2\rho}{1+\rho}

, approaching

0.5

only at high SNR

A) Exactly one bit at every SNR

B) Exactly half a bit at every SNR

C) Capacity doubles

D) $P_X$ , approaching $\varepsilon$ only at high SNR

Answer and explanation

Correct answer: D. “Half a bit per doubling” is a high-SNR approximation, not a universal identity.

Question 7.6.1

7.6. Why random coding achieves $R<I(X;Y)$

What is the role of random coding in achievability?

One correct optionAIt immediately gives a practical linear-time decoderBSmall ensemble-average error proves that at least one good deterministic codebook existsCIt proves every code is goodDIt removes the need for growing blocklength

A) It immediately gives a practical linear-time decoder

B) Small ensemble-average error proves that at least one good deterministic codebook exists

C) It proves every code is good

D) It removes the need for growing blocklength

Answer and explanation

Correct answer: B. This is the probabilistic method: an existence proof is not an efficient engineering construction.

Question 7.6.2

7.6. Why random coding achieves $R<I(X;Y)$

Why is the proof's random codebook usually impractical?

One correct optionAIt has about

2^{nR}

words and exhaustive decoding is exponentialBIt works only above capacityCIt requires zero noiseDIts codewords are identical

A) It has about $H(X)$ words and exhaustive decoding is exponential

B) It works only above capacity

C) It requires zero noise

D) Its codewords are identical

Answer and explanation

Correct answer: A. Practical LDPC, turbo, and polar codes add structure and efficient decoding.

Question 7.7.1

7.7. Converse and finite blocklength

What does the Fano-based bound show when $R>C$ ?

One correct optionA

P_e^{(n)}

equals

1-C/R

for every

n

BError decays as

1/n

CError cannot tend to zero; the result is a weak converseDEvery code has error exactly one

A) $H(X)$ equals $1-C/R$ for every $n$

B) Error decays as $1/n$

C) Error cannot tend to zero; the result is a weak converse

D) Every code has error exactly one

Answer and explanation

Correct answer: C. The strong converse additionally yields P_e^(n)→1, which is strictly stronger.

Question 7.7.2

7.7. Converse and finite blocklength

What does the strong converse say for a DMC at fixed $R>C$ ?

One correct optionAError may converge to any constant below oneBA zero-error code existsCThe rate automatically drops to

C

DBlock error tends to one

A) Error may converge to any constant below one

B) A zero-error code exists

C) The rate automatically drops to $W^n(y^n\mid x^n)=\prod_iW(y_i\mid x_i)$

D) Block error tends to one

Answer and explanation

Correct answer: D. Above capacity, communication becomes asymptotically almost completely unreliable under the standard formulation.

Question 7.7.3

7.7. Converse and finite blocklength

Why is capacity insufficient to describe a short code?

One correct optionAAt finite

n

, target error and channel dispersion matter;

R<C

does not guarantee low error for that blockBCapacity exists only for a BSCCMutual information is always zero at short blocklengthDBlocklength has no effect

A) At finite $H(X)$ , target error and channel dispersion matter; $R<C$ does not guarantee low error for that block

B) Capacity exists only for a BSC

C) Mutual information is always zero at short blocklength

D) Blocklength has no effect

Answer and explanation

Correct answer: A. Capacity is first order. Finite-blocklength analysis treats the triple (n,R,ε) and a second-order channel-dispersion term.

Question 7.8.1

7.8. Noisy labels as a channel

Under class-conditional noise with $X\to Y\to\widetilde Y$ ,

One correct optionA

I(X;\widetilde Y)\ge I(X;Y)

I(X;\widetilde Y)\le I(X;Y)

I(X;\widetilde Y)=H(X)

DDPI does not apply to labels

A) $H(X)$

B) $n$

C) $I(X;\widetilde Y)=H(X)$

D) DPI does not apply to labels

Answer and explanation

Correct answer: B. The annotation channel cannot make the noisy label more informative about the input than the clean label.

Question 7.8.2

7.8. Noisy labels as a channel

A symmetric $K$ -class label channel has zero capacity at

One correct optionA

\eta=0

\eta=1/2

for every

K

\eta=(K-1)/K

, where every row becomes uniformD

\eta=1

A) $H(X)$

B) $1-h_2(\varepsilon)$ for every $K$

C) $\eta=(K-1)/K$ , where every row becomes uniform

D) $\varepsilon$

Answer and explanation

Correct answer: C. At η=1, the output still identifies one class the example is not; information vanishes at the uniform-row point.

Question 7.9.1

7.9. Channel coding inside ML: ECOC and DeepJSCC

What does $d_{\min}$ guarantee in idealized ECOC?

One correct optionAPerfect probability calibrationBIndependent binary-classifier errorsCOptimal component partitionsDCorrection of up to

\lfloor(d_{\min}-1)/2\rfloor

bit errors by nearest-codeword decoding

A) Perfect probability calibration

B) Independent binary-classifier errors

C) Optimal component partitions

D) Correction of up to $P_X$ bit errors by nearest-codeword decoding

Answer and explanation

Correct answer: D. Real component errors can be dependent and unequal, so this is a geometric rather than complete statistical guarantee.

Question 7.9.2

7.9. Channel coding inside ML: ECOC and DeepJSCC

How should DeepJSCC results be interpreted?

One correct optionAAs empirical advantages of jointly learned coding in some finite-blocklength, SNR, and bandwidth regimes—not as a refutation of separationBAs proof that source coding is obsoleteCAs universal dominance over every codeDAs lossless image coding with zero distortion

A) As empirical advantages of jointly learned coding in some finite-blocklength, SNR, and bandwidth regimes—not as a refutation of separation

B) As proof that source coding is obsolete

C) As universal dominance over every code

D) As lossless image coding with zero distortion

Answer and explanation

Correct answer: A. DeepJSCC optimizes a distortion task and can benefit from finite resources and mismatch; the asymptotic separation theorem retains its domain.

Question 7.10.1

7.10. An LLM as a channel: a precise model and the limits of the analogy

When can $q_\theta(y\mid x)$ be treated rigorously as a channel from prompt to response?

One correct optionAOnly for a linear modelBAfter fixing weights, decoding algorithm, and generation randomnessCOnly at context length oneDNever

A) Only for a linear model

B) After fixing weights, decoding algorithm, and generation randomness

C) Only at context length one

D) Never

Answer and explanation

Correct answer: B. Capacity would still require admissible inputs, a cost constraint, a channel-use definition, and an error criterion.

Question 7.10.2

7.10. An LLM as a channel: a precise model and the limits of the analogy

Why is context-window length not Shannon capacity by itself?

One correct optionATokens are always independentBCapacity is measured only in bytesCA context contains no informationDThe transition law, resource constraint, coding task, and channel-use unit are unspecified; tensor dimension is not reliable transmitted bits

A) Tokens are always independent

B) Capacity is measured only in bytes

C) A context contains no information

D) The transition law, resource constraint, coding task, and channel-use unit are unspecified; tensor dimension is not reliable transmitted bits

Answer and explanation

Correct answer: D. Context length is a genuine resource, but converting it to capacity requires an operational probabilistic model.

Question 7.10.3

7.10. An LLM as a channel: a precise model and the limits of the analogy

What is the accurate conclusion about lost in the middle?

One correct optionAIt follows mathematically from strong DPIBIt proves the middle of a context has zero capacityCIt is an empirical positional sensitivity, not automatically a channel-theorem consequenceDIt is fully explained by head_dim

A) It follows mathematically from strong DPI

B) It proves the middle of a context has zero capacity

C) It is an empirical positional sensitivity, not automatically a channel-theorem consequence

D) It is fully explained by head_dim

Answer and explanation

Correct answer: C. The mechanism can depend on architecture, positional encoding, data, and the evaluation protocol.

Question 7.10.4

7.10. An LLM as a channel: a precise model and the limits of the analogy

Why are attention weights not automatically channel transition probabilities?

One correct optionAThey can only be negativeBOutputs also depend on value vectors, the residual stream, multiple heads, and later nonlinearities; row normalization is insufficientCTheir rows never sum to oneDAttention does not use softmax

A) They can only be negative

B) Outputs also depend on value vectors, the residual stream, multiple heads, and later nonlinearities; row normalization is insufficient

C) Their rows never sum to one

D) Attention does not use softmax

Answer and explanation

Correct answer: B. Attention entropy describes routing-weight concentration, not transmitted bits or causal influence.

Question 7.C.1

Computational block

A binary symmetric channel has crossover probability $\varepsilon=0.2$ . Compute its capacity in bits per channel use. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 0.278 (tolerance 0.002). Capacity is 1 − h₂(0.2) = 1 − 0.722 = 0.278 bits, attained by a uniform input. At ε = 0.5 it would be 0, and at ε = 1 it returns to a full bit, so capacity is not monotone in the crossover probability.

Question 7.C.2

Computational block

A binary erasure channel erases each symbol with probability $0.3$ . Compute its capacity in bits per channel use. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 0.7 (tolerance 0.002). Capacity is 1 − 0.3 = 0.7 bits. Compare this with the BSC above: an erasure that announces itself costs far less than a flip of the same probability, because the receiver knows which positions are unreliable.

Question 7.C.3

Computational block

Signal power and noise power satisfy $P/N=7$ in an AWGN channel. Compute the capacity in bits per real channel use. (tolerance 0.002)

AnswerAbsolute tolerance: ±0.002

Answer and explanation

Numeric answer: 1.5 (tolerance 0.002). Capacity is ½ log₂(1 + 7) = ½ · 3 = 1.5 bits. The factor of one half belongs to one real discrete use of the channel; the bandwidth form in bits per second uses a different normalization.

Question 7.C.4

Computational block

A Z-channel flips input 1 to output 0 with probability $\alpha=0.25$ and leaves input 0 untouched. The optimal input uses symbol 1 with probability about $0.4278$ . Compute the capacity in bits per channel use. (tolerance 0.003)

AnswerAbsolute tolerance: ±0.003

Answer and explanation

Numeric answer: 0.558 (tolerance 0.003). The capacity is about 0.558 bits. Note that the optimal input is not uniform: the vulnerable symbol is used less than half the time, because the channel treats the two inputs asymmetrically.