Definitions:
A channel is a medium that accepts strings of symbols from
a finite alphabet
A = {a1,
. . . , an}
and
produces strings of symbols from a finite alphabet B = {b1, . . . , bm}.
Let Xi denote the ith
input symbol and let Yi denote the ith
output symbol. The channel is said to be memoryless
if the probability P(Yi =bj |Xi =ak) = pjk
(for 1≤ j ≤ m and 1≤ k ≤ n) is independent of i.
A binary symmetric channel (BSC) is a memoryless channel with input and output alphabets {0, 1}, and probability p
that a symbol is transmitted incorrectly. The probability p is
called the symbol error probability of the channel. See the following figure.

A q-ary symmetric channel is a memoryless channel with input and output alphabets each of
size q and such that the probability that an error occurs on symbol
transmission is a constant p. Furthermore, if an error does occur then
each of the q−1 symbols different
from the correct symbol is equally likely to be received.
The capacity of a binary symmetric channel with symbol
error probability p is
C(p) = 1 + p log2
p + (1 − p) log2(1 − p).
Facts:
1. The capacity of a communications channel is a (unitless) measure of its ability to transmit information
reliably.
2. The capacity of a BSC with symbol error probability p
is a monotone decreasing function of p for 0 ≤ p ≤ 1/2 , with 1 ≥ C(p) ≥ 0. Moreover, C(0) = 1 and C( 1/2)
= 0.
Example:
1. The capacity of a BSC with symbol error probability 0.01
is given by
C(0.01) = 1 +
0.01 log2(0.01) + 0.99 log2(0.99) ≈ 0.92.