you will implement an encoder-decoder system based on joint typicality. You need to write a function

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

The Typical Set Encoder

To transmit k bits of information, we can draw a symbol from a 2’-ary source alphabet {1, 2, 3, . . . , 2k} uniformly at random. lfthe 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 Yl , 112 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 thatthe channel is discrete and memoryless. and that we can completely

characteflze the channel using its conditional probability p(YX). 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 proofwe presented for Shannon’s noisy coding theorem, the encoder functions as an “adapter’ that bridges the

-ary source alphabet {1, 2, 3, . . . , 2’} to the input alphabet 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 X. The process followed by

typical-set encoder system is outlined as follows:

. Create a 2kbyn matrixlcodebook where each entry is drawn from the channel input alphabet X using a distribution

p(X).

. Draw a symbol 2kary source alphabet {1, 2, 3, . . . , 2’} uniformly at random.

. From the codebook. transmit the row corresponding to the source symbol.

Itwe 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

Zn. 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 Yz , where 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 conditionalltransition probability p(YX) . 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 distributionS

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  from the received vector Y” Formally, our candidates for X’1 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 e.

. Find all codewords z” from the transmission codebook that are c-typical with the received sequence yl’a

. lfthere is only one such codeword, report the row number as the decoder output.

. lfthere is no such codeword or ifthere are more than one codewords found, declare a decoding error.

Pait 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 list s. such that channel[xj [y] is the probability thatthe channel will output y given an

input X .

. x_dist : a list of float s, standing for the probability distribution to be used for generating the random

codebook.

. frame_len : an mt indicating the number of bits to be passed as input to the typical set encoder

. block_len : an mt 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

. nurn_frames : an mt 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 perfunction call, e.g., if\code{num_frames}=100. then all lOOtransmissions over the

channel must use the same codebook.

Python test script for execution

import random,, math

def exact_entropy(dist):

return sum([p*math.log2(p) for p in dist.values() if p > 0])

def estimated_entropy(sarnples, 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] 1= row_length[0] for i in range(1.,

len(row_length))]):

Header 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 - estiniated_entropy(x, x_prob))., abs(Hy -

estimated_entropy(y, y_prob))., abs(Hxy - estimated_entropy(xy, xy_prob))]) <

epsilon

def typical_set_codec(channel, x_dist, frame_len, block_len, num_frames,

epsilon):

Student # Your code goes here

submission # More code..

return ans

Maintest # Main test script goes here, and wILL not be visibLe to students.

. # The script wiLL test if the submitted code does the prescribed functionaLity.

script # 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 probabilityp = io3 and

decoded using c-typical sets where e = 2 x 10 2 using equiprobable binary input X. The value reported is the median

valueoutoflOindependentrunswith num_frames=10000 .

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of