Channel coding
Shannon channel capacity limit
Sistemas de Comunicaciones I
W. Warzanskyj García
1
Shannon capacity limit - Introduction
• The Shannon capacity limit is an upper bound on the error-free
information transfer rate that can be achieved over a noisy band-
limited channel
• There will be a set of possible messages (a message is a succession
of symbols) and a channel bandwidth. After transmission, a
message will be contaminated with noise. Shannon capacity
indicates how many messages can be detected without error
• The number 𝑃 of different messages that can be detected without
error indicates the number of bits that can be transmitted,
𝑙𝑜𝑔!(𝑃)
• The bits to message assignment process (translating bits into
message) is called coding
2
Shannon capacity limit - getting started
• We try to transmit 𝑀 successive symbols, 𝑀 → ∞, symbol duration 𝑇,
!
through a channel whose bandwidth is 𝐵 = and transfer function
"#
$ $ 𝐻 𝑓
𝐻 𝑓 = ∏ =∏ !⁄
"% " 𝐵
f
−1 1
2𝑇 2𝑇
• According to the Nyquist theorem, the maximum symbol rate is achieved
&
when the signal is of the form ∑$ (
!"# 𝑎!· 𝑠𝑖𝑛𝑐(' − 𝑘) , 𝐸 𝑎! = 𝑆 is the
signal power (see SC-I T2 (2) “Nyquist condition: the full picture”)
& *
If the basis function is a 𝑠𝑖𝑛𝑐('), then the shaping filter 𝐻&) 𝑓 = 𝑇 ∏(!⁄ ) is a pulse,
"
*-,' ,
then ∑.
,"-. 𝑇 ∏( !⁄ ) 𝐻/0,! 𝑓 −' = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 → 𝐻 𝑓 = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡
"
-# # * #
for ('
< 𝑓 < (' → 𝐻 𝑓 = ∏ (1
=∏ 2$
3
# #
(and the raised cosine shaping filter will need double bandwidth, flat from − ' 𝒕𝒐 ')
This must make us suspect that this maximum rate is unfeasible, as
sinc signals are not physically possible 3
Shannon capacity limit - getting started
• We build the message vector
𝑀 = 𝑎! , 𝑎" , . . . 𝑎+
symbol 1, duration 𝑇 symbol M, duration 𝑇
in the corresponding M-dimensional message vector space.
The M vector components are the symbols amplitudes (using some basis
function, e.g. a sinc), which are uncorrelated. 𝑆 is the message power.
• We build an M-dimensional hypersphere in the message space with radius
𝑅4 = ∑$ (
!"# 𝑎! = 𝑀 · 𝑎!(
coefficients mean value
• As 𝑀 → ∞ the radius becomes 𝑅% = 𝑀 · 𝐸 𝑎<!( = 𝑀 · 𝑆 , i.e., the
hypersphere radius is exactly 𝑀 · 𝑆
Note: to be precise, 𝐸 𝑎#$ is the message energy, to obtain the power we must divide by 𝑀. 𝑇 but
the same process will apply to the noise component, so the terms will cancel out at their division
4
Shannon capacity limit - Hyperspheres
• In an M-dimensional hypersphere, volume V “tends to concentrate near
the surface”
𝑉 = 𝐴 𝑅$ 𝑅 𝑡ℎ𝑒 ℎ𝑦𝑝𝑒𝑟𝑠𝑝ℎ𝑒𝑟𝑒 𝑟𝑎𝑑𝑖𝑢𝑠 𝑎𝑛𝑑 𝐴 𝑎 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡
56 $ 57 56
= Δ𝑅, 𝑖𝑓 𝑀 = 10,000 𝑎𝑛𝑑 = 0.01, = 100 !
6 7 7 6
• If the signal is contaminated by random noise with power 𝑁, we can also
build a noise vector whose components 𝑛0 are the noise samples at the
sampling instants 𝑘. 𝑇. We define the noise hypersphere radius as
𝑅8 = ∑$ (
!"# 𝑛! = 𝑀 · 𝑛!( 𝑖𝑓 𝑀 → ∞ 𝑡ℎ𝑒𝑛 𝑅8 = 𝑀 · 𝑁
• Even though noise is random, in the M-dimensional message vector
space the noise hypersphere radius tends to 𝑅8 = 𝑀 · 𝑁 , it is a
hypersphere with a sharply defined boundary
• Finally, we can also build a signal plus noise M component vector. Signal
and noise, being uncorrelated, add in power and the S+N corresponding
hypersphere has a radius 𝑅498 = 𝑀 · (𝑆 + 𝑁)
5
Shannon capacity limit - definition
• The signal plus noise hypersphere, with radius 𝑀 · (𝑆 + 𝑁) , contains
all the possible message vectors 𝑎! , 𝑎" , . . . 𝑎+ , whose components are
random and uncorrelated, then their information content is maximum by
definition of information
• Inside the signal plus noise hypersphere we can build noise hyperspheres
with radius 𝑀 · 𝑁 . The center of each noise hypersphere can be made
to coincide with the tip of a message vector, and we choose the
messages so that the noise hyperspheres de not overlap
• The messages that can be identified without error are the centers of
those non overlapping noise hyperspheres
𝑀 · (𝑆 + 𝑁)
Messages that can be
𝑀𝑆
identified without error
𝑀𝑁
6
Shannon capacity limit - Conclusion
• The number of messages that can be identified without error is the
number of 𝑀 · 𝑁 radius noise hyperspheres that fit in the
𝑀 · (𝑆 + 𝑁) radius signal plus noise hypersphere. This number 𝑃 is
bound by the ratio of hyperspheres volumes
) $
$·(498) 498
𝑃≤ ) = 8
$·8)
+ 1
• 𝑃 messages can be codified with 𝑙𝑜𝑔" (𝑃) bits, 𝑙𝑜𝑔" (1 + ) bits
" 2
• Since these bits are sent over a 𝑀. 𝑇 time interval, the number of bits per
second that on average can be transmitted is bound by
# $ 4 4
lim 𝑙𝑜𝑔( 1 + 8 = 𝐵(𝐻𝑧) · 𝑙𝑜𝑔( 1 + 8 bits/s
$→. $.' (
𝑇 = 1@2𝐵
𝑆
Shannon capacity limit (bits/s) 𝐶 = 𝐵(𝐻𝑧) · 𝑙𝑜𝑔( 1 +
𝑁
C is unattainable save for infinitely long sequences: Bit Rate ≤ 𝐶
7
How to approach the Shannon limit
• Considering the previous analysis, a code that allows getting
close to the Shannon limit must fulfill the following
conditions:
• Given a set of bits, it must generate long messages: these are
the codewords
• The messages (their bits) must be as random as possible
• The distance (difference) between codewords must be
patterned to the signal to noise ratio. If they are too close, noise
will prevent detection without errors. Too far, and there will be
room for more different messages
https://eee.guc.edu.eg/Courses/Communications/COMM1003%20Information%20Theory/Projects/ProjectDescription.pdf
8
