|
|
|
Here are some starting points for exploration of Information Theory on the Web.
Information Theory Society Home Page Information Theory in the real world
Mathematical models of the real worldPhysics Mathematics Information Theory is a branch of mathematics Funadamental ConceptsEntropy
Relative Entropy
Mutual Information
Entropy Rate
Fundamental Properties
Fundamental Results: AEP
Typical set
Lossless Source Coding
Universal Source Coding
Fundamental results: Channel CapacityCapacity of a channel
Channel Coding theorem There exist codes with probability of error arbitrarily small for all rates less than the capacity of the channel, and all rates above capacity have a non-vanishing probability of error.
Examples of Channel Capacity Binary Symmetric Channel C= 1-H(p) Gaussian Channel
Fundamental Results: Rate Distortion TheoryDistortion measure Represent random variable X to within average distortion D. R(D) = minimum rate of code that achieves distortion Rate Distortion Theorem:
Quantization and Vector Quantization Quantization: The process of finding a discrete set of values to represent a real number. Uniform quantization: Divide range into bins. Non-uniform quanitzation: Lloyd algorithm Vector quantization: Treat blocks of random variables as vectors in high dimensional space and divide the space into regions. Sigma-delta modulation: Coding Theory
Channel capacity theorem promises the existence of codes with rates less than capacity with an arbitrarily low probability of error. Coding theory: Find efficient coding and decoding techniques. Block Codes
Key paremeters of block code: n: Block length, k: no. of information bits, d: minimum distance Convolutional Codes Block codes with memory Parameters of a convolutional code: Free distance, constraint length Viterbi Algorithm: Dynamic programming to find most likely path through trellis. Real Information SourcesModel data by a stationary ergodic stochastic process. Text and computer data: discrete valued process Speech: one-dimensional continuous valued process Images: two-dimensional continous valued process Assumptions: Source is
Computer files Computer files: Text, numbers, computer source code, binary files, etc. English text has an entropy rate of about 1.5 bits/letter. Compression algorithms:
Speech Telephone quality speech is sampled at 8 kHz, with 8 bits/sample - 64,000 bits/second. Compression schemes:
Music Human ear cannot hear above 20 KHz. CD quality music is samples at 44.1 KHz, 16 bits/sample, stereo, for a bit rate of 176.4 KBytes/sec or 1.411 Mbits/sec. CD's data capacity is about 800 MB. The new Sony Minidisc and the Phillips DCC both incorporate audio compression algorithms. MIDI: Musical Instrument Digital Interface Images: FAX 8.5 by 11 inch paper Run length encoding READ (Relative Element Address Designate) code for vertical corellation. Average transmission time after compression = 57 seconds. Group 3/Group 4 coding New standard: JBIG based on arithmetic coding using contexts. Uses progressive compression. Images: Still Images Typical images on a computer screen: 640 by 480 by 24 bit color is 921 KBytes. Compression could save a lot of space.
JPEG Compression Fractal Compression Fractal: Fixed point of recursive mapping. Video Compression: MPEG Spatial and Time Correlation. Uncompressed Video Stream: about 100 Mbits/sec. MPEG-1: 1.5 Mbits/sec. MPEG-2: 4-9 Mbits/sec Communication ChannelsDiscrete channels: Continuous input discrete time channels Waveform channels The promise of infinite bandwidth Optical networks promise large bandwidth ( > 10 Gb/s) with extremely low error
probability Issues
Storage channelsStorage channels transmit information over time. Magnetic disks Information stored in transitions (d,k) constraints: The number of 0's between any two 1's is at least d and at most k. Eg. (1,3) constraint - 0100100010010001 Capacity of the constraint State Splitting or Bounded Delay codes 100's of Mbits/sq. inch Compact disks Data is stored by mean of pits on the surface - under the layer of protective plastic. Each disk stores about 800 MB, and can output information at a data rate of 175 kB/sec. Uses a (2,10) run length limited code, and interleaved Reed-Solomon codes to correct bursts of up to 4000 errors. Oversampling D/A converters CD-ROM, CD-I, Photo-CD, CD-Video all use the same technology. 2x CD-ROM drives Low bandwidth channels Rates less than 1 MBit/sec
High Speed Channels
Putting it all together: The telephone network The Cellular Telephone Network: TDMA vs CDMA The Information Age Parkinson's Law for Communications: Demand will expand to exceed supply for
Information theory remains an active area of research and, in the information age, provides insight and direction for the design and analysis of communication and computer systems.
Sat Aug 15 06:26:30 EDT 1998 |
|
|
.
.
.
forms a Markov Chain, then 
.
for n
large enough.
. 
.
with respect to an incorrect distribution q(x)
incurs an additional cost of D(p||q) in average length.
is defined 
- eg. Hamming distortion or mean square distortion 
. 
1728 by 1186 pixels = 2.05 MBits =430 seconds at
4800 bits/sec. 
. 
where N(t) is the number of sequences satisfying
the constraint of length t. 