161-A4.2

The Typical Set Encoder

To transmit $k$ bits of information, we can draw a symbol from a $2^{k}$-ary source alphabet $\{1,2,3,...,2^{k}\}$ uniformly at random. If the channel is noiseless, the symbol can be readily transmitted to the receiver, which will recover the information without any decoding effort. In many cases, however, the channel introduces randomness so that a given transmitted symbol $x$ may yield at least two different outputs $y_{1},y_{2}$ each with nonzero probability.

The key idea behind achieving the channel capacity is to ensure that the channel inputs follow the optimal distribution $p(X)$. In this discussion, we assume that the channel is discrete and memoryless, and that we can completely characterize the channel using its conditional probability $p(Y|X)$. In practice, the transition probabilities can be estimated by observing the channel for a long time and performing statistical analysis. As an example, some data storage systems can be modeled using the so-called $Z$ channel where zeros are always transmitted correctly, but the ones may be flipped to zeros at random. It can be shown the the optimal input distribution for most $Z$ channels will bias the transmission to have more zeros than ones, which is a fairly intuitive result.

In the proof we presented for Shannon's noisy coding theorem, the encoder functions as an "adapter" that bridges the $2^{k}$-ary source alphabet $\{1,2,3,...,2^{k}\}$ to the input alphabet ${\mathcal {X}}$ that is expected by the channel. To achieve the capacity, we must ensure the channel "sees" the optimal mix/distribution of symbols from the alphabet ${\mathcal {X}}$. The process followed by typical-set encoder system is outlined as follows:

• Create a $2^{k}$-by-$n$ matrix/codebook where each entry is drawn from the channel input alphabet ${\mathcal {X}}$ using a distribution $p(X)$.
• Draw a symbol $2^{k}$-ary source alphabet $\{1,2,3,...,2^{k}\}$ uniformly at random.
• From the codebook, transmit the row corresponding to the source symbol.

If we scale up both $k$ and $n$ high enough so as to maintain a constant code rate $r=k/n$, the asymptotic equipartition property (AEP) guarantees that the codewords will belong to some concentrated typical set.

The Typical Set Decoder

In the previous section, the typical set encoder took in $k$ bits of information and mapped it to an $n$-element vector from ${\mathcal {X}}^{n}$. The channel will then process each entry one at a time and produce a random output $Y$. Hence, the receiver will see an $n$-element vector from ${\mathcal {Y}}^{n}$, where ${\mathcal {Y}}$ is the output alphabet of the channel.

Let's review the underlying probabilities of the system described thus far. We have two main sources of randomness: the input distribution $p(X)$ and the conditional/transition probability $p(Y|X)$. By Bayes' theorem, these two probability functions specify a joint distribution $p(X,Y)$. We can think of $X$ and $Y$ as being entangled by their joint distribution. Informally, this "entanglement" becomes stronger as we draw more and more pairs of samples $(X,Y)$ from their joint distribution $p(X,Y)$. Assuming that we transmit at a rate below the channel capacity, we now interpret Shannon's random-coding argument as follows: if we allow arbitrarily large blocklengths (large $n$), then we can recover with high probability the $n$-vector $X^{n}$ from the received vector $Y^{n}$. Formally, our candidates for $X^{n}$ are those that are jointly typical with the received codeword.

The process taken by the typical set decoder is outlined as follows:

• Fix a decoding threshold $\epsilon$.
• Find all codewords $x^{n}$ from the transmission codebook that are $\epsilon$-typical with the received sequence $y^{n}$.
• If there is only one such codeword, report the row number as the decoder output.
• If there is no such codeword or if there are more than one codewords found, declare a decoding error.

Part 1: Implementation (6 points)

Task description

In the first part, you will implement an encoder-decoder system based on joint typicality. You need to write a function typical_set_codec which will take the following arguments:

• channel: a list of lists, such that channel[x][y] is the probability that the channel will output y given an input x.
• x_dist: a list of floats, standing for the probability distribution to be used for generating the random codebook.
• frame_len: an int indicating the number of bits to be passed as input to the typical set encoder.
• block_len: an int indicating the number of symbols to be output by the typical set encoder; equivalently, this is also the number of symbols to be received by the typical set decoder.
• num_frames: an int corresponding the number of frames to send over the channel.
• epsilon: a float corresponding to the threshold used for testing joint typicality.

The function must output a float corresponding to the estimated symbol error probability. For this exercise, generate the random codebook only one per function call, e.g., if \code{num_frames}=100, then all 100 transmissions over the channel must use the same codebook.

Python test script for execution

Header	import random, math def exact_entropy(dist): return sum([-p*math.log2(p) for p in dist.values() if p > 0]) def estimated_entropy(samples, dist): return sum([-samples.count(x)/len(samples) * math.log2(dist[x]) for x in set(samples) if dist[x] > 0]) def jointly_typical(x, y, joint_dist, epsilon): if len(x) != len(y): raise ValueError('x and y must have equal lengths.') elif epsilon <= 0: raise ValueError('epsilon must be strictly positive.') else: row_length = [len(joint_dist[i]) for i in range(len(joint_dist))] if any([row_length[i] != row_length[0] for i in range(1, len(row_length))]): raise ValueError('All rows of joint_dist must have equal lengths.') xy = [(x[i], y[i]) for i in range(len(x))] x_alphabet = range(len(joint_dist)) y_alphabet = range(len(joint_dist[0])) x_prob = {x: sum([joint_dist[x][y] for y in y_alphabet]) for x in x_alphabet} y_prob = {y: sum([joint_dist[x][y] for x in x_alphabet]) for y in y_alphabet} xy_prob = {(x,y): joint_dist[x][y] for x in x_alphabet for y in y_alphabet} Hx = exact_entropy(x_prob) Hy = exact_entropy(y_prob) Hxy = exact_entropy(xy_prob) return max([abs(Hx - estimated_entropy(x, x_prob)), abs(Hy - estimated_entropy(y, y_prob)), abs(Hxy - estimated_entropy(xy, xy_prob))]) < epsilon
Student submission	def typical_set_codec(channel, x_dist, frame_len, block_len, num_frames, epsilon): # Your code goes here # More code.. return ans
Main test script	# Main test script goes here, and will not be visible to students. # The script will test if the submitted code does the prescribed functionality. # For successfully validated scripts, test results will be sent via email.

Expected output

The table below shows a sample output for a binary symmetric channel (BSC) with cross-over probability $p=10^{-3}$ and decoded using $\epsilon$-typical sets where $\epsilon =2\times 10^{-2}$ using equiprobable binary input $X$. The value reported is the median value out of 10 independent runs with num_frames=10000.

Frame Length	Block Length	Median Error Probability
1	2	0.00245
1	5	0.0052
5	10	0.0101
5	25	0.0253
5	50	0.04825
10	100	0.09715

Recall that the transition probability matrix of a BSC with cross-over probability p is given by

	$Y=0$	$Y=1$
$X=0$	$1-p$	$p$
$X=1$	$p$	$1-p$

Part 2: Report (4 points)

Perform some tests on the binary erasure channel (BEC) using your function. The transition probability matrix of a BEC with erasure probability p is given by:

	$Y=0$	$Y=1$	$Y=2$
$X=0$	$1-p$	$0$	$p$
$X=1$	$0$	$1-p$	$p$

Note: The symbols have been re-labeled for compatibility with the exercise specifications. Most textbooks will label the output symbol "2" as "?" to indicate an erased symbol.

Write a 400-to-500-word report discussing your findings from implementing the typical set decoder, with answers to the following questions:

• Does the decoder perform as expected?
• Can you simulate the decoder to arbitrarily large blocklengths?
• What aspect/s of the encoder-decoder did you find to be practical/impractical?