Entropy 2.16 2001/07/03 2005/10/24 14:50:45.538 GMT-5 Behnaam Aazhang aaz@ece.rice.edu Dinesh Rajan dinesh@ece.rice.edu Mohammad Jaber Borran mohammad@ece.rice.edu Roy Ha rha@rice.edu Shawn Stewart mrshawn@alumni.rice.edu Behnaam Aazhang aaz@ece.rice.edu conditional entropy entropy entropy rate information joint entropy This module presents a quantification of information by the use of entropy. Entropy, or average self-information, measures the uncertainty of a source and hence provides a measure of the information it could reveal. Information sources take very different forms. Since the information is not known to the destination, it is then best modeled as a random process, discrete-time or continuous time. Here are a few examples: Digital data source (e.g., a text) can be modeled as a discrete-time and discrete valued random process X 1 , X 2 , …, where X i A B C D E … with a particular p X 1 x , p X 2 x , …, and a specific p X 1 X 2 , p X 2 X 3 , …, and p X 1 X 2 X 3 , p X 2 X 3 X 4 , …, etc. Video signals can be modeled as a continuous time random process. The power spectral density is bandlimited to around 5 MHz (the value depends on the standards used to raster the frames of image). Audio signals can be modeled as a continuous-time random process. It has been demonstrated that the power spectral density of speech signals is bandlimited between 300 Hz and 3400 Hz. For example, the speech signal can be modeled as a Gaussian process with the shown power spectral density over a small observation period.

These analog information signals are bandlimited. Therefore, if sampled faster than the Nyquist rate, they can be reconstructed from their sample values. A speech signal with bandwidth of 3100 Hz can be sampled at the rate of 6.2 kHz. If the samples are quantized with a 8 level quantizer then the speech signal can be represented with a binary sequence with the rate of 6.23 2 8 18600 bits sample samples sec 18.6 kbits sec

The sampled real values can be quantized to create a discrete-time discrete-valued random process. Since any bandlimited analog information signal can be converted to a sequence of discrete random variables, we will continue the discussion only for discrete random variables. The random variable x takes the value of 0 with probability 0.9 and the value of 1 with probability 0.1. The statement that x 1 carries more information than the statement that x 0 . The reason is that x is expected to be 0, therefore, knowing that x 1 is more surprising news!! An intuitive definition of information measure should be larger when the probability is small. The information content in the statement about the temperature and pollution level on July 15th in Chicago should be the sum of the information that July 15th in Chicago was hot and highly polluted since pollution and temperature could be independent. I hot high I hot I high An intuitive and meaningful measure of information should have the following properties: Self information should decrease with increasing probability. Self information of two independent events should be their sum. Self information should be a continuous function of the probability. The only function satisfying the above conditions is the -log of the probability. Entropy The entropy (average self information) of a discrete random variable X is a function of its probability mass function and is defined as H X i 1 N p X x i p X x i where N is the number of possible values of X and p X x i X x i . If log is base 2 then the unit of entropy is bits. Entropy is a measure of uncertainty in a random variable and a measure of information it can reveal. A more basic explanation of entropy is provided in another module. If a source produces binary information 0 1 with probabilities p and 1 p . The entropy of the source is H X p 2 p 1 p 2 1 p If p 0 then H X 0 , if p 1 then H X 0 , if p 12 then H X 1 bits. The source has its largest entropy if p 12 and the source provides no new information if p 0 or p 1 .

An analog source is modeled as a continuous-time random process with power spectral density bandlimited to the band between 0 and 4000 Hz. The signal is sampled at the Nyquist rate. The sequence of random variables, as a result of sampling, are assumed to be independent. The samples are quantized to 5 levels -2 -1 0 1 2 . The probability of the samples taking the quantized values are 1 2 1 4 1 8 1 16 1 16 , respectively. The entropy of the random variables are H X 1 2 2 1 2 1 4 2 1 4 1 8 2 1 8 1 16 2 1 16 1 16 2 1 16 1 2 2 2 1 4 2 4 1 8 2 8 1 16 2 16 1 16 2 16 1 2 1 2 3 8 4 8 15 8 bits sample There are 8000 samples per second. Therefore, the source produces 8000 15 8 15000 bits sec of information. Joint Entropy The joint entropy of two discrete random variables (X, Y) is defined by H X Y i i j j p X Y x i y j p X Y x i y j The joint entropy for a random vector X X 1 X 2 … X n is defined as H X x 1 x 1 x 2 x 2 … x n x n p X x 1 x 2 … x n p X x 1 x 2 … x n Conditional Entropy The conditional entropy of the random variable X given the random variable Y is defined by H X | Y i i j j p X Y x i y j p X | Y x i | y j It is easy to show that H X H X 1 H X 2 | X 1 … H X n | X 1 X 2 … X n-1 and H X Y H Y H X | Y H X H Y | X If X 1 , X 2 , …, X n are mutually independent it is easy to show that H X i 1 n H X i Entropy Rate The entropy rate of a stationary discrete-time random process is defined by H n H X n | X 1 X 2 … X n The limit exists and is equal to H n 1 n H X 1 X 2 … X n The entropy rate is a measure of the uncertainty of information content per output symbol of the source. Entropy is closely tied to source coding. The extent to which a source can be compressed is related to its entropy. In 1948, Claude E. Shannon introduced a theorem which related the entropy to the number of bits per second required to represent a source without much loss.