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

Asymptotically optimal low-complexity sequential lossless coding for piecewise-stationary memoryless sources - Part I: The regular case

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2000年第7期46卷 2444-2467页

作者： Shamir, GI Costello, DJ Univ Notre Dame Dept Elect Engn Notre Dame IN 46556 USA

The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistics is shown to be asymptotically achievable using a fixed per-letter computational complexity sequential compression scheme with fixed storage complexity. The scheme which outperforms any other known fixed-complexity scheme when regularity conditions hold is presented, and its redundancy is upper-bounded. Although the upper bounds are merely asymptotic, simulation results show that even for relatively short sequences, the redundancy obtained by asymptotically optimal schemes of higher complexity can still be achieved with fixed per-letter complexity. Furthermore, in practice, a fixed-complexity scheme based on the proposed scheme can in most cases achieve optimal redundancy even when the regularity conditions do not hold.

关键词： change detection piecewise-stationary memoryless source redundancy sequential coding transition path typical sets universal coding weighting

来源：评论

学校读者我要写书评

暂无评论

Low-complexity sequential lossless coding for piecewise-stationary memoryless sources

Low-complexity sequential lossless coding for piecewise-stat...

引用

IEEE International Symposium on Information Theory

作者： Shamir, GI Merhav, N Univ Notre Dame Dept Elect Engn Notre Dame IN 46556 USA Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel

ISBN: (纸本)0780350006

Three strongly sequential, lossless compression schemes, one with linearly growing per-letter computational complexity, and two with fixed per-letter complexity, are presented and analyzed for memoryless sources with abruptly changing statistics. The first method, which improves on Willems' weighting approach, asymptotically achieves a lower bound on the redundancy, and hence is optimal, The second scheme achieves redundancy of O(log N/N) when the transitions in the statistics are large, and O (log log N/ log N) otherwise. The third approach always achieves redundancy of O(root log N/N). Obviously, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the analytical bounds derived for all the coding schemes.

关键词： change detection ideal code length minimum description length piecewise-stationary memoryless source redundancy segmentation sequential coding source block code strongly sequential coding transition path universal coding weighting

来源：评论

学校读者我要写书评

暂无评论

Streaming Universal Distortion-Free Entanglement Concentration

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第1期60卷 334-350页

作者： Blume-Kohout, Robin Croke, Sarah Gottesman, Daniel Sandia Natl Labs Albuquerque NM 87123 USA Univ Glasgow Sch Phys & Astron Glasgow G12 8QQ Lanark Scotland Perimeter Inst Theoret Phys Waterloo ON N2L2Y5 Canada

This paper presents a streaming (sequential) protocol for universal entanglement concentration at the Shannon bound. Alice and Bob begin with N identical (but unknown) two-qubit pure states, each containing E ebits of entanglement. They each run a reversible algorithm on their qubits, and end up with Y perfect EPR pairs, where Y = NE +/- O(root N). Our protocol is streaming, so the N input systems are fed in one at a time, and perfect EPR pairs start popping out almost immediately. It matches the optimal block protocol exactly at each stage, so the average yield after n inputs is < Y > = nE - O(log n). So, somewhat surprisingly, there is no tradeoff between yield and lag-our protocol optimizes both. In contrast, the optimal N-qubit block protocol achieves the same yield, but since no EPR pairs are produced until the entire input block is read, its lag is O(N). Finally, our algorithm runs in O(log N) space, so a lot of entanglement can be efficiently concentrated using a very small (e. g., current or near-future technology) quantum processor. Along the way, we find an optimal streaming protocol for extracting randomness from classical i.i.d. sources and a more space-efficient implementation of the Schur transform.

关键词： Entanglement concentration partially entangled states quantum algorithms quantum information sequential coding

来源：评论

学校读者我要写书评

暂无评论

The interactions between ergodic theory and information theory

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1998年第6期44卷 2079-2093页

作者： Shields, PC Univ Toledo Dept Math Toledo OH 43606 USA

Information theorists frequently use the ergodic theorem;likewise entropy concepts are often used in information theory, Recently, the two subjects have become partially intertwined as deeper results from each discipline find use in the other. A brief history of this interaction is presented in this paper, together with a more detailed look at three areas of connection, namely, recurrence theory, blowing-up bounds, and direct sample-path methods.

关键词： data compression entropy probability sequential coding source coding stochastic processes

来源：评论

学校读者我要写书评

暂无评论

Successively Structured Gaussian Two-terminal Source coding

引用

WIRELESS PERSONAL COMMUNICATIONS 2009年第4期48卷 485-510页

作者： Behroozi, Hamid Soleymani, M. Reza Queens Univ Dept Math & Stat Kingston ON K7L 3N6 Canada Concordia Univ Dept Elect & Comp Engn Montreal PQ H3G 1M8 Canada

Multiterminal source coding refers to separate encoding and joint decoding of multiple correlated sources. Joint decoding requires all the messages to be decoded simultaneously which is exponentially more complex than a sequence of single-message decodings. Inspired by previous work on successive coding, we apply the successive Wyner-Ziv coding, which is inherently a low complexity approach of obtaining a prescribed distortion, to the two-terminal source coding scheme. First, we consider 1-helper problem where one source provides partial side information to the decoder to help the reconstruction of the main source. Our results show that the successive coding strategy is an optimal strategy in the sense of achieving the rate-distortion function. By developing connections between source encoding and data fusion steps, it is shown that the whole rate-distortion region for the 2-terminal source coding problem is achievable using the successive coding strategy. Comparing the performance of the sequential coding with the performance of the successive coding, we show that there is no sum-rate loss when the side information is not available at the encoder. This result is of special interest in some applications such as video coding where there are processing and storage constraints at the encoder. Finally, we provide an achievable rate-distortion region for the m-terminal source coding.

关键词： Multiterminal source coding m-helper problem Partial side information Rate-distortion region Successive coding sequential coding

来源：评论

学校读者我要写书评

暂无评论

sequential Channel Synthesis

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第5期69卷 2779-2795页

作者： Yu, Lei Anantharam, Venkat Nankai Univ Sch Stat & Data Sci LPMC KLMDASR Tianjin 300071 Peoples R China Nankai Univ LEBPS Tianjin 300071 Peoples R China Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

The channel synthesis problem has been widely investigated over the last decade. In this paper, we consider the sequential version in which the encoder and the decoder work in a sequential way. Under a mild assumption on the target joint distribution we provide a complete (single-letter) characterization of the solution for the point-to-point case, which shows that the canonical symbol-by-symbol mapping is not optimal in general, but is indeed optimal if we make some additional assumptions on the encoder and decoder. We also extend this result to the broadcast scenario and the interactive communication scenario. We provide bounds in the broadcast setting and a complete characterization of the solution under a mild condition on the target joint distribution in the interactive communication case. Our proofs are based on a Renyi entropy method.

关键词： Symbols Encoding Random variables Decoding Entropy Delays Receivers Channel synthesis sequential coding Renyi entropy hybrid digital-analog coding symbol-by-symbol mapping

来源：评论

学校读者我要写书评

暂无评论

On limited-delay lossy coding and filtering of individual sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2002年第3期48卷 721-733页

作者： Weissman, T Merhav, N Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel

We continue the study of adaptive schemes for the sequential lossy coding of individual sequences which was recently initiated by Linder and Lugosi. Specifically, we consider fixed-rate lossy coding systems of fixed (or zero) delay where the encoder (which is allowed to use randomization) and the decoder are connected via a noiseless channel of a given capacity. It is shown that for any finite set of such coding schemes of a given rate, there exists a source code (adhering to the same structural and delay limitations) with the same rate whose distortion is with high probability almost as small as that of the best scheme in that set, uniformly for all individual sequences. Applications of this result to reference classes of special interest are outlined. These include the class of scalar quantizers, trellis encoders with sliding block decoders, and differential pulse code modulator (DPCM)-based source codes. In particular, for the class of all scalar quantizers, a source code is obtained with (normalized) distortion redundancy relative to the best scheme in the reference class of order n(-1/3) log n (where n is the sequence length). This improves the n(-1/5) log n rate achieved by Linder and Lugosi. More importantly, the decoder here is deterministic and, in particular, does not assume a common randomization sequence available at both encoder and decoder. Finally, we consider the case where the individual sequence is corrupted by noise prior to reaching the coding system, whose goal now is to reconstruct a sequence with small distortion relative to the clean individual sequence. It is shown that for the case of a finite alphabet and an invertible channel transition probability matrix, for any finite set of sliding-window schemes of a given rate, there exists a source code (allowed to use randomization yet adhering to the same delay constraints) whose performance is, with high probability, essentially as good as the best scheme in the class, for all individual sequenc

关键词： individual sequences limited-delay coding lossy source coding noisy source coding sequential coding universal coding

来源：评论

学校读者我要写书评

暂无评论

Tracking the best quantizer

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第4期54卷 1604-1625页

作者： Gyorgy, Andras Linder, Tamas Lugosi, Gabor Hungarian Acad Sci Inst Comp & Automat Machine Learning Res Grp H-1111 Budapest Hungary Queens Univ Dept Math & Stat Kingston ON K7L 3N6 Canada Pompeu Fabra Univ ICREA Barcelona 08005 Spain Pompeu Fabra Univ Dept Econ Barcelona 08005 Spain

An algorithm is presented for online prediction that allows to track the best expert efficiently even when the number of experts is exponentially large, provided that the set of experts has a certain additive structure. As an example, we work out the case where each expert is represented by a path in a directed graph and the loss of each expert is the sum of the weights over the edges in the path. These results are then used to construct universal limited-delay schemes for lossy coding of individual sequences. In particular, we consider the problem of tracking the best scalar quantizer that is adaptively matched to the source sequence with piecewlse different behavior. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm that is matched to the sequence and is allowed to change the employed quantizer for a given number of times. The complexity of the algorithm is quadratic in the sequence length, but at the price of some deterioration in performance, the complexity can be made linear. Analogous results are obtained for sequential multiresolution and multiple description scalar quantization of individual sequences.

关键词： algorithmic efficiency individual sequences lossy source coding multiple description quantization multiresolution coding nonstationary sources scalar quantization sequential coding sequential prediction

来源：评论

学校读者我要写书评

暂无评论

coding of sources with two-sided geometric distributions and unknown parameters

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2000年第1期46卷 229-236页

作者： Merhav, N Seroussi, G Weinberger, MJ Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel Hewlett Packard Labs Israel Haifa Israel Hewlett Packard Labs Palo Alto CA 94304 USA

Lossless compression is studied for a countably infinite alphabet source with an unknown, off-centered, two-sided geometric (TSG) distribution, which is a commonly used statistical model for image prediction residuals. In this correspondence, we demonstrate that arithmetic coding based on a simple strategy of model adaptation, essentially attains the theoretical lower bound to the universal coding redundancy associated with this model. We then focus on more practical codes for the TSG model, that operate on a symbol-by-symbol basis, and study the problem of adaptively selecting a code from a given discrete family. By taking advantage of the structure of the optimum Huffman tree for a known TSG distribution, which enables simple calculation of the codeword of every given source symbol, an efficient adaptive strategy is derived.

关键词： exponential distribution geometric distribution Golomb codes infinite alphabet lossless image compression prediction residual sequential coding universal coding universal modeling

来源：评论

学校读者我要写书评

暂无评论

The necessity and sufficiency of anytime capacity for stabilization of a linear system over a noisy communication link - Part I: Scalar systems

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第8期52卷 3369-3395页

作者： Sahai, Anant Mitter, Sanjoy Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

In this paper, we review how Shannon's classical notion of capacity is not enough to characterize a noisy communication channel if the channel is intended to be used as part of a feedback loop to stabilize an unstable scalar linear system. While classical capacity is not enough, another sense of capacity (parametrized by reliability) called "anytime capacity" is necessary for the stabilization of an unstable process. The required rate is given by the log of the unstable system gain and the required reliability comes from the sense of stability desired. A consequence of this necessity result is a sequential generalization of the Schalkwijk-Kailath scheme for communication over the additive white Gaussian noise (AWGN) channel with feedback. In cases of sufficiently rich information patterns between the encoder and decoder, adequate anytime capacity is also shown to be sufficient for there to exist a stabilizing controller. These sufficiency results are then generalized to cases with noisy observations, delayed control actions, and without any explicit feedback between the observer and the controller. Both necessary and sufficient conditions are extended to continuous time systems as well. We close with comments discussing a hierarchy of difficulty for communication problems and how these results establish where stabilization problems sit in that hierarchy.

关键词： anytime decoding control over noisy channels error exponents feedback real-time information theory reliability functions sequential coding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：