Computer Science – Information Theory
Scientific paper
2012-04-16
Computer Science
Information Theory
Submitted to IEEE Transaction on Information Theory
Scientific paper
Given an independent and identically distributed source $X = \{X_i \}_{i=1}^{\infty}$ with finite Shannon entropy or differential entropy (as the case may be) $H(X)$, the non-asymptotic equipartition property (NEP) with respect to $H(X)$ is established, which characterizes, for any finite block length $n$, how close $-{1\over n} \ln p(X_1 X_2...X_n)$ is to $H(X)$ by determining the information spectrum of $X_1 X_2...X_n $, i.e., the distribution of $-{1\over n} \ln p(X_1 X_2...X_n)$. Non-asymptotic equipartition properties (with respect to conditional entropy, mutual information, and relative entropy) in a similar nature are also established. These non-asymptotic equipartition properties are instrumental to the development of non-asymptotic coding (including both source and channel coding) results in information theory in the same way as the asymptotic equipartition property to all asymptotic coding theorems established so far in information theory. As an example, the NEP with respect to $H(X)$ is used to establish a non-asymptotic fixed rate source coding theorem, which reveals, for any finite block length $n$, a complete picture about the tradeoff between the minimum rate of fixed rate coding of $X_1...X_n$ and error probability when the error probability is a constant, or goes to 0 with block length $n$ at a sub-polynomial, polynomial or sub-exponential speed. With the help of the NEP with respect to other information quantities, non-asymptotic channel coding theorems of similar nature will be established in a separate paper.
Meng Jin
Yang En-hui
No associations
LandOfFree
Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-288738