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

Mismatched Rate-Distortion Theory: Ensembles, Bounds, and General Alphabets

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第3期70卷 1525-1539页

作者： Kanabar, Millen Scarlett, Jonathan Ecole Polytech Fed Lausanne EPFL Sch Comp & Commun Sci CH-1015 Lausanne Switzerland Natl Univ Singapore NUS Dept Comp Sci Dept Math Singapore 117417 Singapore Natl Univ Singapore NUS Inst Data Sci Singapore 117417 Singapore

In this paper, we consider the mismatched rate-distortion problem, in which the encoding is done using a codebook, and the encoder chooses the minimum-distortion codeword according to a mismatched distortion function that differs from the true one. For the case of discrete memoryless sources, we establish achievable rate-distortion bounds using multi-user coding techniques, namely, superposition coding and expurgated parallel coding. We study examples where these attain the matched rate-distortion trade-off but a standard ensemble with independent codewords fails to do so. On the other hand, in contrast with the channel coding counterpart, we show that there are cases where structured random codebooks can perform worse than their unstructured counterparts. In addition, in view of the difficulties in adapting the existing and above-mentioned results to general alphabets, we consider a simpler i.i.d. random coding ensemble, and establish its achievable rate-distortion bounds for general alphabets.

关键词： Mismatched encoding rate-distortion theory random coding

来源：评论

学校读者我要写书评

暂无评论

Achievable Rates for Low-Complexity Posterior Matching Over the Binary Symmetric Channel

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第8期70卷 5471-5497页

作者： Antonini, Amaael Gimelshein, Rita Wesel, Richard D. Univ Calif Los Angeles Dept Elect & Comp Engn Los Angeles CA 90095 USA

Horstein, Burnashev, Shayevitz and Feder, Naghshvar et al. and others have studied sequential transmission of a k-bit message over the binary symmetric channel (BSC) with full, noiseless feedback using posterior matching. Yang et al. provide an improved lower bound on the achievable rate using martingale analysis that relies on the small-enough difference (SED) partitioning introduced by Naghshvar et al. SED requires a relatively complex encoder and decoder. To reduce complexity, this paper replaces SED with relaxed constraints that admit the small enough absolute difference (SEAD) partitioning rule. The main analytical results show that achievable-rate bounds higher than those found by Yang et al. (2021) are possible even under the new constraints, which are less restrictive than SED. The new analysis does not use martingale theory for the confirmation phase and applies a surrogate channel technique to tighten the results. An initial systematic transmission further increases the achievable rate bound. The simplified encoder associated with SEAD has a complexity below order O(K-2) and allows simulations for message sizes of at least 1000 bits. For example, simulations achieve 99% of of the channel's 0.50-bit capacity with an average block size of 200 bits for a target codeword error rate of 10 (-3) .

关键词： Symbols Complexity theory Transmitters Systematics Receivers Partitioning algorithms Error analysis Posterior matching binary symmetric channel noiseless feedback random coding

来源：评论

学校读者我要写书评

暂无评论

A Refinement of Expurgation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第12期70卷 8419-8422页

作者： Cocco, Giuseppe Guillen i Fabregas, Albert Font-Segura, Josep Univ Politecn Cataluna Dept Signal Theory & Commun Barcelona 08034 Spain Univ Cambridge Dept Engn Cambridge CB2 1PZ England Univ Pompeu Fabra Dept Informat & Commun Technol Barcelona 08018 Spain

We show that for a wide range of channels and code ensembles with pairwise-independent codewords, with probability tending to 1 with the code length, expurgating an arbitrarily small fraction of codewords from a rando... 详细信息

关键词： Reliable communications error exponents expurgated error exponent random code ensembles random coding

来源：评论

学校读者我要写书评

暂无评论

Identification over quantum broadcast channels

引用

QUANTUM INFORMATION PROCESSING 2023年第10期22卷 1-31页

作者： Rosenberger, Johannes Deppe, Christian Pereg, Uzi Tech Univ Munich Sch Computat Informat & Technol Dept Comp Engn Munich Germany Munich Ctr Quantum Sci & Technol Munich Germany Technion Israel Inst Technol Dept Elect & Comp Engn Haifa Israel Technion Israel Inst Technol Helen Diller Quantum Ctr Haifa Israel

Identification over quantum broadcast channels is considered. As opposed to the information transmission task, the decoder only identifies whether a message of his choosing was sent or not. This relaxation allows for a double-exponential code size. An achievable identification region is derived for a quantum broadcast channel, and a full characterization for the class of classical-quantum broadcast channels. The identification capacity region of the single-mode pure-loss bosonic broadcast channel is obtained as a consequence. Furthermore, the results are demonstrated for the quantum erasure broadcast channel, where our region is suboptimal, but improves on the best previously known bounds.

关键词： Identification capacity Broadcast communication Bosonic channels random coding Pool-selection coding Hypergraph covering

来源：评论

学校读者我要写书评

暂无评论

D-Semifaithful Codes That are Universal Over Both Memoryless Sources and Distortion Measures

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第7期69卷 4746-4757页

作者： Merhav, Neri Technion Israel Inst Technol Andrew & Erna Viterbi Fac Elect Engn IL-32000 Haifa Israel

We prove the existence of codebooks for d-semifaithful lossy compression that are simultaneously universal with respect to both the class of finite-alphabet memoryless sources and the class of all bounded additive rational distortion measures. By applying independent random selection of the codewords according to a mixture of all memoryless sources, we achieve redundancy rates that are within O(log n/n) close to the empirical rate-distortion function of every given source vector with respect to every bounded, rational distortion measure.

关键词： Lossy compression rate-distortion theory universal coding random coding

来源：评论

学校读者我要写书评

暂无评论

Codeword or Noise? Exact random coding Exponents for Joint Detection and Decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第9期60卷 5077-5094页

作者： Weinberger, Nir Merhav, Neri Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel Technion Israel Inst Technol IL-32000 Haifa Israel

We consider the problem of coded communication, where in each time frame, the transmitter is either silent or transmits a codeword from a given (randomly selected) codebook. The task of the decoder is to decide whether transmission has taken place, and if so, to decode the message. We derive the optimum detection/decoding rule in the sense of the best tradeoff among the probabilities of decoding error, false alarm, and misdetection. For this detection/decoding rule, we then derive single-letter characterizations of the exact exponential rates of these probabilities for the average code in the ensemble. It is shown that previously proposed decoders are in general strictly suboptimal.

关键词： Joint detection/decoding error exponent false alarm misdetection random coding synchronization unequal error protection

来源：评论

学校读者我要写书评

暂无评论

Index coding via random coding

Index Coding via Random Coding

引用

Iran Workshop on Communication and Information Theory (IWCIT)

作者： Arbabjolfaei, Fatemeh Bandemer, Bernd Kim, Young-Han Univ Calif San Diego Dept Elect & Comp Engn San Diego CA 92103 USA Bosch Res & Technol Ctr North Amer Palo Alto CA USA

ISBN: (纸本)9781479948772

The index coding problem is a simple distributed source coding problem in which a sender broadcasts multiple messages to their respective receivers with side information about other messages. This problem arises in many applications such as content broadcasting, distributed caching, and wireless interference management. At the same time, it is a canonical instance of the multiple-unicast network coding problem that captures the essence of broadcasting multiple interfering streams. Reflecting the importance as well as the difficulty of the index coding problem, several coding schemes have been proposed that are built on tools from graph theory, linear network coding, combinatorial optimization, and interference alignment. This paper studies the composite coding scheme based on random coding in information theory. Despite its conceptual simplicity that allows for rather straightforward analysis, the scheme uniformly outperforms the existing coding schemes by Birk and Kol (1998), Blasiak, Kleinberg, and Lubetzky (2013), and Shanmugam, Dimakis, and Langberg (2013), and is optimal for all index coding problems with up to five messages.

关键词： random coding Messages broadcasting Information Theory Graph theory Essences coding

来源：评论

学校读者我要写书评

暂无评论

Concentration Properties of random Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第12期69卷 7499-7537页

作者： Truong, Lan V. Cocco, Giuseppe Font-Segura, Josep Fabregas, Albert Univ Essex Sch Math Stat & Actuarial Sci Colchester CO4 3SQ England Univ Politecn Cataluna Signal Theory & Commun Dept Barcelona 08034 Spain Univ Pompeu Fabra Dept Informat & Commun Technol Barcelona Spain Univ Cambridge Dept Engn Cambridge CB2 1PZ England

This paper shows that, for discrete memoryless channels, the error exponent of a randomly generated code with independent codewords converges in probability to its expectation-the typical error exponent. For high rates, the result follows from the fact that the random-coding error exponent and the sphere-packing error exponent coincide. For low rates, instead, the convergence is based on the fact that the union bound accurately characterizes the error probability. The paper also zooms into the behavior at asymptotically low rates, and shows that the normalized error exponent converges in distribution to the standard Gaussian or a Gaussian-like distribution. We also state several results on the convergence of the error probability and error exponent for generic ensembles and channels.

关键词： Error exponent typical error exponent random coding concentrations maximum likelihood decoder

来源：评论

学校读者我要写书评

暂无评论

Complete traceability multimedia fingerprinting codes resistant to averaging attack and adversarial noise with optimal rate

引用

DESIGNS CODES AND CRYPTOGRAPHY 2022年第4期91卷 1183-1191页

作者： Vorobyev, Ilya Syst Univ Munich Munich Germany

In this paper we consider complete traceability multimedia fingerprinting codes resistant to averaging attacks and adversarial noise. Recently it was shown that there are no such codes for the case of an arbitrary linear attack. However, for the case of averaging attacks complete traceability multimedia fingerprinting codes of exponential cardinality resistant to constant adversarial noise were constructed in Egorova et al. (Probl Inf Transm 56(4):388-398, 2020). We continue this work and provide an improved lower bound on the rate of these codes.

关键词： Multimedia fingerprinting Adversarial noise random coding

来源：评论

学校读者我要写书评

暂无评论

On Stochastic Codebook Generation for Markov Sources

On Stochastic Codebook Generation for Markov Sources

引用

Data Compression Conference (DCC)

作者： Elshafiy, Ahmed Rose, Kenneth Univ Calif Santa Barbara Santa Barbara CA 93117 USA

ISBN: (纸本)9798350347951

This paper proposes an effective universal "on-the-fly" mechanism for stochastic codebook generation in lossy coding of Markov sources. Earlier work has shown that the rate distortion bound can be asymptotically achieved by a "natural type selection" (NTS) mechanism that iteratively considers asymptotically long source strings (from an unknown distribution P) and regenerates the codebook from a distribution obtained within a maximum likelihood distribution estimation framework, based on observation of a set of K codewords that "d-match" (i.e., satisfy the distortion constraint for) a respective set of K independently generated source words. This result was later generalized, in a straightforward manner, to account for source memory, by considering the source as a vector source, i.e., a sequence of super-symbols from a corresponding super-alphabet. While ensuring asymptotic optimality, this extension suffered from a significant practical flaw: it requires asymptotically long vectors or super-symbols, hence exponentially large super-alphabet, in order to approach the rate-distortion bound, even for finite memory sources, e.g., Markov sources. Such exponentially large super-alphabet implies that even a single NTS iteration is intractable, thus compromising the promise of NTS to approach the rate-distortion function, in practice, for sources with memory. This work describes a considerably more efficient and tractable mechanism to achieve asymptotically optimal performance given a prescribed memory constraint, within a practical framework tailored to Markov sources. Specifically, the algorithm finds, asymptotically, the optimal codebook reproduction distribution, within a constrained set of distributions satisfying a prescribed Markovian property, e.g., of the same order as the source, which achieves the minimum per letter coding rate while maintaining a specified distortion level.

关键词： Markov Sources Natural Type Selection random coding Rate Distortion Theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：