Source Coding Theory
In what follows we shall refer to a communication system as schematized by the block-diagram of Fig. 1.1. Such a block-diagram is actually an over-simplification for most of real communication system, but its usefulness has been largely recognized since t
- PDF / 4,492,503 Bytes
- 82 Pages / 481.92 x 691.68 pts Page_size
- 43 Downloads / 217 Views
A ND
L E C T U R ES
-
No.
32
GIUSEPPE LONGO UNIVERSITY
OF
TRIESTE
SOURCE CODING THEORY
LECfURES HELD AT THE DEPARTMENT FOR AUTOMATION AND INFORMATION JUNE 1970
UDINE 1970
SPRINGER-VERLAG WTEN GMBH
This work is subject to copyright AlI rights are reserved, whether the whole or part of the material is concemed specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. © 1972 Springer-Verlag Wien Originally published by Springer-Verlag Wien-New York in 1972
ISBN 978-3-211-81090-3 ISBN 978-3-7091-2842-8 (eBook) DOI 10.1007/978-3-7091-2842-8
P R E F AC E Most of the leature notes was aovered held at the International aes Udine, in June - July
material aontained in these by the author during a aourse Centre for Meahaniaal SaienI9?0.
The topia is aoding for disarete memoryless souraes without any distortion measure. The results are partly new, at least as regards the approaah through the I - divergenae aonaept. Previous knonwledge of Information Theory or of Statistias is not required, although some familiarity with those fields would help the reader in appreaiating how self-aontained the notes are, espeaially as a aonsequenae of the aonaise eleganae of the Preliminaries for whiah I am indebted to Prof. I. Csiszar. I am grateful to all Authorities of CISM for g~v~ng me the opportunity of delivering the aourse, and espeaially to Prof. L. Sobrero whose astonishingly energetia aativity is keeping the Centre at an unrivalled standard.
Udine, June 1970
Preliminaries In this section we summarize some basic definitions and relations which will be used freely in the sequel : the simple proofs will be sketched only. The term "random variable" will be abbreviated as RV ; for the sake of simplicity, attention will be restricted to the case of discrete RV's,i.e., to RV's with values in a finite or countably infinite set. ~.~.~will
denote RV's with values in the
(finite or countably infinite) sets X, Y, Z . All random variables considered at the same time will be assumed to be defined on the same probability space. Recall that a probability space is a triplet(!L.~ 1 P) where 0 is a set (the set of all conceivable outcomes of an experiment), Tis a ~-algebra of subsets of !l (the class of observable events) and
P is a measure (non-negative countably additive set function) defined on t such that P(n)=1.RV 1 s are functions
T}(oo) etc. (u>E:.O.).The probability
~(w),
P { ~ = ~} is the measure of the set of those which
;,~etc.
W 's for
~ ((I)) =JC; similarly, 'P { ;:x.,ll =y} is the measure of
the set of those
W
1
s for which ~(oo)=:X: and 'l'l(oo)=y.
6
Preliminaries
The conditional probabilityP{~=XI11 =Y} is defined as
P{;=x,ll=Y}
P{ 11=Y} ( 1)
t
(if
'P{ll=Y}=O, P{;=XIll=Y}
Definition 1. The RV 1 s defined by
~ = - tog 2 P { ~ = x. }
if
;
=X
if
;
= :X: ,
are called the entropy density of tion density
is undefined).
of~ and~'
~
1} =
y
and the informa-
respectively.
if
are
Data Loading...
