Q8Digital Communication

(a) SNR-Bandwidth Trade-off for Constant Channel Capacity

The Shannon-Hartley capacity formula C=B·log2(1+S/N) directly shows that for a fixed target channel capacity C, bandwidth B and signal-to-noise ratio S/N can be traded off against each other, though not in a simple linear (directly proportional) manner, since the relationship involves a logarithm.

Rearranging for S/N as a function of B (with C fixed):

This expression reveals that as the available bandwidth B is reduced (while keeping the target capacity C fixed), the exponent C/B increases, and the required signal-to-noise ratio S/N grows exponentially — meaning that for narrow-bandwidth channels, achieving a given target capacity requires a very large signal-to-noise ratio, with the required SNR increasing extremely rapidly (exponentially) as bandwidth is further reduced.

Conversely, as bandwidth B is increased (for the same fixed target capacity C), the exponent C/B decreases toward zero, and the required S/N decreases correspondingly — but with strongly diminishing returns: since 2^x - 1 ≈ x·ln2 for small x, at sufficiently large bandwidth, the required S/N decreases only linearly (rather than exponentially) with further increases in bandwidth, and as derived in an earlier answer, the required S/N eventually approaches a fixed minimum value (S/N)min = C·ln2/B as B→∞, below which no further capacity gain is possible no matter how much additional bandwidth is provided (for a fixed total signal power).

Practical significance: this trade-off is of central practical importance in communication system design — wideband systems (such as spread-spectrum and Ultra-Wideband systems) deliberately use excess bandwidth specifically to reduce the required signal-to-noise ratio (transmit power) needed to achieve a given data rate, which is valuable in power-constrained applications (battery-powered devices, satellite links with limited transmit power) or in interference-limited/low-SNR environments; conversely, narrowband systems operating with limited available spectrum must instead achieve their required data rate by employing higher transmit power and/or highly spectrally-efficient modulation and coding schemes (approaching the Shannon limit as closely as practically feasible) to compensate for their more limited bandwidth resource — this fundamental bandwidth-SNR-capacity trade-off, quantified precisely by the Shannon-Hartley theorem, underlies essentially all practical spectrum-allocation, power-budget, and modulation-scheme-selection decisions in modern communication system engineering.

(b) Shannon-Fano and Huffman Coding for the Given DMS

Given: DMS with 5 symbols and probabilities P(x1)=0.4, P(x2)=0.19, P(x3)=0.16, P(x4)=0.15, P(x5)=0.1.

Source entropy:

(i) Shannon-Fano Code Construction

The Shannon-Fano algorithm recursively splits the symbol list (sorted in decreasing order of probability) into two groups with cumulative probabilities as close to equal as possible, assigning a '0' prefix bit to one group and '1' to the other at each split. Applying this procedure: Level 1 split: comparing candidate splits, {x1,x2} (cumulative 0.59) vs {x3,x4,x5} (cumulative 0.41) gives the most balanced division (difference 0.18, better than splitting after just x1 alone, which gives 0.4 vs 0.6, difference 0.2). Level 2 splits: within {x1,x2}, split into {x1}(0.4) vs {x2}(0.19); within {x3,x4,x5}(0.41), the most balanced split is {x3}(0.16) vs {x4,x5}(0.25). Level 3 split: within {x4,x5}, split into {x4}(0.15) vs {x5}(0.1).

This gives the resulting Shannon-Fano code assignment: x1=00, x2=01, x3=10, x4=110, x5=111.

(ii) Huffman Code Construction

The Huffman algorithm repeatedly combines the two lowest-probability nodes into a single merged node (with combined probability), assigning a 0/1 bit to distinguish the two merged branches at each step, continuing until only a single root node remains, then reading each symbol's code by tracing the path of assigned bits from the root down to that symbol's leaf.

Applying this procedure to the given probabilities (0.4, 0.19, 0.16, 0.15, 0.1): merge x4(0.15) and x5(0.1) → node of 0.25; merge x3(0.16) and this new 0.25 node → node of 0.41; merge x2(0.19) and x1(0.4) → node of 0.59; finally merge the 0.41 node and the 0.59 node → root of 1.0. Tracing back the resulting bit assignments gives: x1=0, x2=111, x3=110, x4=101, x5=100 (the exact code word values depend on the specific 0/1 convention chosen at each merge, but the resulting code word lengths are uniquely determined by the algorithm).

Comparison

The Huffman code achieves a lower average code word length (2.2 bits/symbol) and correspondingly higher coding efficiency (97.72%) compared to the Shannon-Fano code (2.25 bits/symbol, 95.54% efficiency), for this same source. This result is consistent with the well-established general theoretical property that Huffman coding is provably optimal (achieves the minimum possible average code word length among all uniquely-decodable, prefix-free binary codes for a given source) — Huffman coding always performs at least as well as, and in many cases (as demonstrated here) strictly better than, Shannon-Fano coding for the same source statistics, which is precisely why Huffman coding, despite its greater algorithmic complexity (requiring a full sort/merge procedure rather than Shannon-Fano's simpler recursive splitting), is the standard, preferred choice for practical optimal prefix-free source coding in modern digital compression and communication systems.

Why Huffman Outperforms Shannon-Fano: the Root Cause

The reason Huffman coding achieves a shorter average length than Shannon-Fano in this example (and, more generally, is never worse) lies in the fundamentally different, and in a specific sense more myopic, strategy used by the Shannon-Fano top-down splitting procedure compared to Huffman's bottom-up merging procedure. Shannon-Fano makes its partitioning decision at each stage based only on locally balancing cumulative probability at that particular split, without any guarantee that this locally-optimal split leads to a globally optimal code word length assignment overall — in this problem, the level-1 split placed x3 (probability 0.16) into a 2-bit code alongside x1 and x2, while x4 and x5 (with smaller, though closely comparable, probabilities of 0.15 and 0.1) were pushed down to a 3-bit code, which is not necessarily the length assignment that a globally-optimal code would produce. Huffman's bottom-up approach, by contrast, always merges the two globally lowest-probability nodes at each step, which can be proven (via an exchange argument in the standard optimality proof for Huffman coding) to always yield an average code word length that is less than or equal to that of any other uniquely-decodable prefix code for the same symbol probabilities, including Shannon-Fano.

Relating the Entropy Bound (Source Coding Theorem)

Both results in this problem should also be interpreted against the backdrop of Shannon's source coding theorem, which establishes that H (the source entropy, ≈2.1498 bits/symbol here) is the absolute theoretical lower bound on the average number of bits per symbol required by any uniquely-decodable code for this source — no code, however cleverly constructed, can achieve an average length below this entropy value without loss of information. Both the Shannon-Fano code (2.25 bits/symbol) and the Huffman code (2.2 bits/symbol) computed above necessarily satisfy Lavg ≥ H, and their respective efficiencies (95.54% and 97.72%) are precisely a direct measure of how closely each code approaches this fundamental entropy bound. The remaining efficiency gap for even the optimal Huffman code (97.72%, rather than a full 100%) arises because Huffman coding is constrained to assign each symbol an integer number of bits, whereas the ideal, entropy-achieving code word length for a symbol of probability p would be the generally non-integer value -log2(p) bits; techniques such as extending the code to operate on blocks of multiple source symbols at once (n-th order extension coding) can push the achieved average length per original symbol arbitrarily close to the entropy bound H, at the cost of exponentially increasing code-book size and encoder/decoder complexity as the block length n grows.