检索结果-内蒙古大学图书馆

Second-order asymptotics in fixed-length source coding and intrinsic randomness

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第10期54卷 4619-4637页

作者： Hayashi, Masahito JST ERATO Quantum Computat & Informat Project Tokyo 1130033 Japan

There is a difference between the optimal rates of fixed-length source coding and intrinsic randomness when we care about the second-order asymptotics. We prove this difference for general information sources and then investigate independent and identically distributed (i.i.d.) random variables and Markovian variables as examples. The difference is demonstrated through an investigation of the second-order asymptotic behavior of the rates. A universal fixed-length source code attaining the second-order optimal rate is also proposed. The difference between the rates of fixed-length source coding and intrinsic randomness proves that the outputs of fixed-length source codes are not uniformly distributed.

关键词： fixed-length source coding information spectrum intrinsic randomness second-order asymptotics source coding folklore

来源：评论

学校读者我要写书评

暂无评论

Probability of error for the fixed-length source coding of general sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2001年第4期47卷 1537-1543页

作者： Iriyama, K Nagoya Univ Grad Sch Human Informat Nagoya Aichi 4648601 Japan

We consider general sources in the sense of Han and Verdu. The information spectrum approach developed by Hen and Verdu has played a central role in the analyses of general sources. We investigate the asymptotic behavior of the probability of error for the fixed-length source coding of general sources. Recently, Han characterized the minimum r-achievable fixed-length coding rate. Our aim is to give an alternative expression for the minimum r-achievable rate.

关键词： countably infinite alphabet error exponent fixed-length source coding general source information spectrum large deviation

来源：评论

学校读者我要写书评

暂无评论

The reliability functions of the general source with fixed-length coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2000年第6期46卷 2117-2132页

作者： Han, TS Univ Electrocommun Grad Sch Informat Syst Chofu Tokyo 1828585 Japan

The reliability function problems with fixed-length source coding for the general source are studied for all rates R. Our fundamental philosophy in doing so is to convert all of the reliability function problems to the pertinent computation problems in the large deviation-probability theory. It turns out that this kind of new methodology, which was recently developed by Han, enables us to establish quite compact general formulas of the reliability function for general sources including all nonstationary and/or nonergodic sources with countably infinite alphabet, Such general formulas are presented from the information-spectrum point of view.

关键词： countably infinite alphabet fixed-length source coding general source information spectrum information spectrum slicing large deviation reliability function

来源：评论

学校读者我要写书评

暂无评论

The role of the asymptotic equipartition property in noiseless source coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1997年第3期43卷 847-857页

作者： Verdu, S Han, TS UNIV ELECTROCOMMUN GRAD SCH INFORMAT SYST CHOFU TOKYO 182 JAPAN

The (noiseless) fixed-length source coding theorem states that, except for outcomes in a set of vanishing probability, a source can be encoded at its entropy but not more efficiently, It is well known that the Asymptotic Equipartition Property (AEP) is a sufficient condition for a source to be encodable at its entropy, This paper shows that the AEP is necessary for the source coding theorem to hold for nonzero-entropy finite-alphabet sources, Furthermore, we show that a nonzero-entropy finite-alphabet source satisfies the direct coding theorem if and only if it satisfies the strong converse, In addition, we introduce the more general setting of nonserial information sources which need not put out strings of symbols, In this context, which encompasses the conventional serial setting, the AEP is equivalent to the validity of the strong coding theorem, Fundamental limits for data compression of nonserial information sources are shown based on the flat-top property-a new sufficient condition for the AEP.

关键词： asymptotic equipartition property entropy fixed-length source coding noiseless data compression Shannon theory source coding theorem

来源：评论

学校读者我要写书评

暂无评论

Weak variable-length source coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2000年第4期46卷 1217-1226页

作者： Han, TS Univ Electrocommun Grad Sch Informat Syst Chofu Tokyo 1828585 Japan

Given a general source X = {X-n}(n=1)(infinity), source coding is characterized by a pair (phi(n), psi(n)) of encoder phi(n) and decoder psi(n) together with the probability of error epsilon(n) = Pr{psi(n)(phi(n)(X-n)) not equal X-n}. If the length of the encoder output phi(n)(X-n) is fixed, then it is called fixed-length source coding, while if the length of the encoder output phi(n)(X-n) is variable, then it is called variable-length source coding. Usually, in the context of fixed-length source coding the probability of error epsilon(n) is required to asymptotically vanish (i.e., lim(n-->infinity) epsilon(n) = 0), whereas in the context of variable-length source coding the probability of error epsilon(n) is required to be exactly zero (i.e., epsilon(n) = 0 For All n = 1, 2,....) In contrast to these, we consider in the present paper the problem of variable-length source coding with asymptotically vanishing probability of error (i.e., lim(n-->infinity) epsilon(n) = 0), and establish several fundamental theorems on this new subject.

关键词： countably infinite source alphabet fixed-length source coding general source uniform integrability variable-length source coding weak sup-entropy rate weak variable-length source coding

来源：评论

学校读者我要写书评

暂无评论

coding theorems on the threshold scheme for a general source

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第6期54卷 2658-2677页

作者： Koga, Hiroki Univ Tsukuba Grad Sch Syst & Informat Engn Tsukuba Ibaraki 3058573 Japan

In this paper, coding theorems on the (t, m)-threshold scheme for a general source are discussed, where m. means the number of the shares and t means a threshold. The (t, m)-threshold scheme treated in this paper encrypts n source outputs X-n to m. shares at once and is required to satisfy the two conditions that 1) X-n is reproduced from arbitrary t shares, and 2) almost no information of X-n is revealed from any t - 1 shares. It is shown that the (t, m)-threshold scheme must satisfy certain inequalities including the limit inferiors in probability. One of the inequalities is closely related to the minimum length of the fair random bits needed to a dealer for realizing the (t, m)-threshold scheme. In addition, it is shown that a certain variation of Shamir's threshold scheme meets the two conditions. The same approach can be taken to the problems of Shannon's cipher system with the perfect secrecy and fixed-length source coding with vanishing decoding error probability. It is shown that the same kind of inequalities, which indicate the converse coding theorems, hold in both two cases.

关键词： fixed-length source coding information-spectrum methods secret sharing scheme Shannon's cipher system threshold scheme

来源：评论

学校读者我要写书评

暂无评论

coding theorems on the threshold scheme for a general source

Coding theorems on the threshold scheme for a general source

引用

IEEE Information Theory Workshop

作者： Koga, Hiroki Univ Tsukuba Grad Sch Syst & Informat Engn Tsukuba Ibaraki 3058573 Japan

ISBN: (纸本)0780394917

关键词： fixed-length source coding information-spectrum methods secret sharing scheme Shannon's cipher system threshold scheme

来源：评论

学校读者我要写书评

暂无评论

An information-spectrum approach to classical and quantum hypothesis testing for simple hypotheses

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第2期53卷 534-549页

作者： Nagaoka, Hiroshi Hayashi, Masahito Univ Electrocommun Grad Sch Informat Syst Tokyo 1828585 Japan RIKEN Lab Math Neurosci Brain Sci Inst Saitama 3510198 Japan

The information-spectrum analysis made by Han for classical hypothesis testing for simple hypotheses is extended to a unifying framework including both classical and quantum hypothesis testing. The results are also applied to fixed-length source coding when loosening the normalizing condition for probability distributions and for quantum states. We establish general formulas for several quantities relating to the asymptotic optimality of tests/codes in terms of classical and quantum information spectra.

关键词： classical hypothesis testing fixed-length source coding information spectrum optimal exponent quantum hypothesis testing

来源：评论

学校读者我要写书评

暂无评论

Csiszar's cutoff rates for arbitrary discrete sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2001年第1期47卷 330-338页

作者： Chen, PN Alajaji, F Natl Chiao Tung Univ Dept Commun Engn Hsinchu Taiwan Queens Univ Dept Math & Stat Kingston ON K7L 3N6 Canada

Csiszar's forward beta -cutoff rate (given a fixed beta > 0) for a discrete source is defined as the smallest number Ro such that for every R > R-0, there exists a sequence of tired-length codes of rate R with probability of error asymptotically vanishing as e(-n beta (R-R0)). For a discrete memoryless source (DMS), the forward beta -cutoff rate is shown by Csiszar [6] to be equal to the source Renyi entropy. An analogous concept of reverse beta -cutoff rate regarding the probability of correct decoding is also characterized by Csiszar in terms of the Renyi entropy. In this work, Csiszar's results are generalized by investigating the beta -cutoff rates for the class of arbitrary discrete sources with memory. It is demonstrated that the limsup and liminf Renyi entropy rates provide the formulas for the forward and reverse beta -cutoff rates, respectively. Consequently, new fixed-length source coding operational characterizations for the Renyi entropy rates are established.

关键词： arbitrary sources with memory cutoff rates fixed-length source coding probability of error Renyi's entropy rates source reliability function

来源：评论

学校读者我要写书评

暂无评论

GENERATING RANDOM BITS FROM AN ARBITRARY source - FUNDAMENTAL LIMITS

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1995年第5期41卷 1322-1332页

作者： VEMBU, S VERDU, S PRINCETON UNIV DEPT ELECT ENGN PRINCETON NJ 08544 USA

Suppose we are given a random source and want to use it as a random number generator;at what rate can we generate fair bits from it? We address this question in an information-theoretic setting by allowing for some arbitrarily small but nonzero deviation from ''ideal'' random bits. We prove our results with three different measures of approximation between the ideal and the obtained probability distributions: the variational distance, the d-bar distance, and the normalized divergence. Two different contexts are studied: fixed-length and variable-length random number generation. The fixed-length results of this paper provide an operational characterization of the inf-entropy rate of a source, defined in Han and Verdu [1] and the variable-length results characterize the liminf of the entropy rate, thereby establishing a pleasing duality with the fundamental limits of source coding. A feature of our results is that we do not restrict ourselves to ergodic or to stationary sources.

关键词： SHANNON THEORY RANDOM NUMBER GENERATION ENTROPY fixed-length source coding VARIABLE-length source coding APPROXIMATION THEORY

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：