# Capacity of a discrete memoryless channel

For an integer $$I$$, the input-output relationship of a discrete memoryless channel is given by:

$$Y = X + Z$$ (mod $$I$$, i.e. sum indicates a modular addition)

where $$I ≥ 2$$, and

$$X$$ is an integer chosen from the alphabet $$A_x = \{1,\dots,2I\}$$,

$$Z$$ is noise which is a uniform Bernoulli random variable. This means that $$A_z = \{0,1\}$$, and

$$\Pr\{Z = 0\} = \Pr\{Z = 1\} = 0.5.$$

How can we calculate the capacity of this channel?

## 1 Answer

This answer assumes that $$Y = X + Z \bmod 2I$$, which seems more reasonable than the current $$Y = X + Z \bmod I$$, which would mean that $$X$$ is effectively chosen from an alphabet of size $$I$$ rather than $$2I$$.

The capacity is $$\log I$$.

For the upper bound, $$I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(Z) = H(Y) - 1 \leq \log(2I) - 1 = \log I.$$

For the lower bound, if $$X$$ is chosen uniformly among the $$I$$ values $$1,3,\ldots,2I-1$$ then you can recover $$X$$ from $$Y$$ (without any error!), and so $$I(X;Y) = H(X) = \log I$$.

• One thing though, for mod $I$ we will have $I$ possible "different " values for $Y$. Shouldn't we take this into consideration? – Niousha Feb 8 '20 at 22:31
• My answer actually assumes that the calculation is modulo $2I$. Otherwise the input alphabet has effective size $I$ rather than $2I$. – Yuval Filmus Feb 8 '20 at 22:42