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

interactive encoding and decoding for One Way Learning: Near Lossless Recovery With Side Information at the Decoder

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第4期56卷 1808-1824页

作者： Yang, En-Hui He, Da-Ke Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

A source coding paradigm called interactive encoding and decoding (IED) is considered for a source network where a finite alphabet source X is to be encoded, and another finite alphabet source Y correlated with is available only to the decoder as a helper. The optimal performance achievable asymptotically (OPAA) by IED is investigated, where the performance is measured as the average number of bits per symbol exchanged by the encoder and decoder until the decoder learns with high probability. First, it is shown that for any stationary (X, Y), the OPAA by IED is given by the conditional entropy rate H (X vertical bar Y) of X given Y. This is in contrast with noninteractive Slepian-Wolf (SW) coding, where the OPAA is shown in general to be strictly greater than H (X vertical bar Y) when (X, Y) is not ergodic. Second, for a memory-less source pair (X, Y), it is shown that IED approaches H (X vertical bar Y) faster than SW coding does. Finally, it is demonstrated that one can convert any classical universal data compression algorithm with side information to a universal IED algorithm for the class A of all stationary ergodic source pairs. In contrast, universal SW coding algorithms for the class A do not exist.

关键词： Distributed source coding entropy interactive encoding and decoding source networks universal data compression

来源：评论

学校读者我要写书评

暂无评论

interactive encoding and decoding based on Syndrome Accumulation over Binary LDPC Ensembles: Universality and Rate-Adaptivity

Interactive Encoding and Decoding based on Syndrome Accumula...

引用

47th Annual Allerton Conference on Communication, Control, and Computing

作者： Meng, Jin Yang, En-hui Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9781424458707

In this paper we investigate the performance of linear interactive encoding and decoding based on syndrome accumulation(SA-IED) over binary LDPC ensembles. Assume that the source alphabet is GF(2), and the side information alphabet is finite. It is shown that we can construct universal SA-LED schemes, which are asymptotically optimal for any stationary ergodic source-side information pair. Our analysis further shows that the word error probability will approach 0 sub-exponentially with respect to the block length, while at the same time, the rate approaches H(X vertical bar Y) as the average variable node degree of the LDPC ensemble approaches infinity. Further, if the source and side information are correlated through a binary symmetrical memoryless channel, but the cross-over probability of the channel is not known to either the encoder or the decoder, our result on the performance of SA-IED can be further improved for LDPC ensembles with finite average variable node degree. Simulation results on binary source-side information pairs confirm the theoretical analysis above, and further show that SA-IED schemes using LDPC codes coupled with linear time belief propagation decoding consistently outperform Slepian-Wolf coding schemes based on LDPC codes.

关键词： interactive encoding and decoding rateless Slepian-Wolf coding LDPC code syndrome accumulation belief propagation decoding

来源：评论

学校读者我要写书评

暂无评论

interactive encoding and decoding Based on Syndrome Accumulation Over a Binary Regular LDPC Ensemble

Interactive Encoding and Decoding Based on Syndrome Accumula...

引用

11th Canadian Workshop on Information Theory

作者： Meng, Jin Yang, En-hui He, Da-ke Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada Res Mot SlipStream Waterloo ON N2L 5Z5 Canada

ISBN: (纸本)9781424434008

In this paper we investigate the performance of linear interactive encoding and decoding (IED) based on syndrome accumulation(SA-IED) over a binary regular LDPC ensemble. Assume that the source alphabet is GF(2), and the side information alphabet is finite. It is shown that we can construct universal SA-IED schemes, which are asymptotically optimal for any stationary ergodic source-side information pair. Our analysis further shows that the word error probability will approach 0 sub-exponentially with respect to the block length, while at the same time, the rate approaches H(X|Y) whenever H(X|Y) is within the rate region (epsilon, 1), where c can be made arbitrarily small by increasing the variable degree of the LDPC code used. Simulation results on binary source-side information pairs show that SA-IED schemes using LDPC codes coupled with linear time belief propagation decoding consistently outperform Slepian-Wolf coding schemes based on LDPC codes.

关键词： interactive encoding and decoding rateless Slepian-Wolf coding LDPC code syndrome accumulation belief propagation decoding

来源：评论

学校读者我要写书评

暂无评论

Linear interactive encoding and decoding for Lossless Source Coding With Decoder Only Side Information

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第8期57卷 5281-5297页

作者： Meng, Jin Yang, En-Hui He, Da-Ke Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada Res In Mot SlipStream Waterloo ON N2L 5Z5 Canada

Linear interactive encoding and decoding (IED) for near lossless source coding with decoder only side information is considered, where the interactive encoder uses linear codes (described by parity-check matrices over a finite field chi) for encoding. It is first demonstrated how to convert any classical universal lossless code C(n) (with block length n and with side information available to both the encoder and decoder) into a universal random linear IED scheme based on Gallager's parity check ensemble. It is then shown that there is no performance loss by restricting IED to linear IED, and that the universal random linear IED scheme based on Gallager's parity check ensemble achieves essentially the same rate performance as does C(n) for each and every individual sequence pair (x(n), y(n)) while the word decoding error probability goes to 0 as n --> infinity. Define the density of a linear IED scheme as the percentage of nonzero entries in its parity-check matrix. To reduce the encoding complexity of linear IED, low density linear IED is further investigated in terms of the trade-off among its rate, decoding error probability, and density.

关键词： Distributed source coding entropy and conditional entropy individual sequences interactive encoding and decoding parity-check matrix Slepian-Wolf coding stationary and ergodic sources

来源：评论

学校读者我要写书评

暂无评论

Linear interactive encoding and decoding Schemes for Lossless Source Coding with Decoder Only Side Information

Linear Interactive Encoding and Decoding Schemes for Lossles...

引用

作者： Meng, Jin University of Waterloo

学位级别：master

Near lossless source coding with side information only at the decoder, was first considered by Slepian and Wolf in 1970s, and rediscovered recently due to applications such as sensor network and distributed video coding. Suppose X is a source and Y is the side information. The coding scheme proposed by Slepian and Wolf, called SW coding, in which information only flows from the encoder to the decoder, was shown to achieve the rate H(X|Y) asymptotically for stationary ergodic source pairs, but not for non-ergodic case, shown by Yang and He. Recently, a new source coding paradigm called interactive encoding and decoding(IED) was proposed for near lossless coding with side information only at the decoder, where information flows in both ways, from the encoder to the decoder and vice *** results by Yang and He show that IED schemes are much more appealing than SW coding schemes to applications where the interaction between the encoder and the decoder is possible. However, the IED schemes proposed by Yang and He do not have an intrinsic structure that is amenable to design and implement in practice. Towards practical design, we restrict the encoding method to linear block codes, resulting in linear IED schemes. It is then shown that this restriction will not undermine the asymptotical performance of IED. Another step of practical design of IED schemes is to make the computational complexity incurred by encoding and decoding feasible. In the framework of linear IED, a scheme can be conveniently described by parity check matrices. Then we get an interesting trade-off between the density of the associated parity check matrices and the resulting symbol error probability. To implement the idea of linear IED and follow the instinct provided by the result above, Low Density Parity Check(LDPC) codes and Belief Propagation(BP) decoding are utilized. A successive LDPC code is proposed, and a new BP decoding algorithm is proposed, which applies to the case where the correlati

关键词： interactive encoding and decoding Linear Block Code LDPC Codes and Belief Propogation decoding

来源：评论

学校读者我要写书评

暂无评论

Low-Density Linear IED Schemes for Lossless Source Coding with Decoder Only Side Information

Low-Density Linear IED Schemes for Lossless Source Coding wi...

引用

46th Annual Allerton Conference on Communication, Control and Computing

作者： Meng, Jin Yang, En-hui He, Da-ke Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada Res MotionSlipStream Waterloo ON N2L 5Z5 Canada

ISBN: (纸本)9781424429257

In this paper we investigate the performance of linear interactive encoding and decoding (EED) for lossless source coding with decoder only side information. Assume that the source alphabet X is a finite field and that the side information alphabet is finite. It is shown that there exist universal linear EED schemes which are asymptotically optimal for any stationary, ergodic source-side information pair. Our analysis of low-density IED schemes further reveals that as long as epsilon(n)p(n)* = Omega(log n/n), where epsilon(n) and p(n)* are real numbers, one can always construct a sequence of universal linear IED schemes {I-n} such that the average density of the parity check matrices associated with I-n is concentrated around (|X| - 1)p(n)*, and the resulting symbol error probability is upper bounded by epsilon(n) + o(epsilon(n)).

关键词： interactive encoding and decoding Linear Block Code Low Density Parity Check Matrix Slepian-Wolf Coding

来源：评论

学校读者我要写书评

暂无评论

Coding Theorems via Jar decoding

Coding Theorems via Jar Decoding

引用

作者： Meng, Jin University of Waterloo

学位级别：master

In the development of digital communication and information theory, every channel decoding rule has resulted in a revolution at the time when it was invented. In the area of information theory, early channel coding theorems were established mainly by maximum likelihood decoding, while the arrival of typical sequence decoding signaled the era of multi-user information theory, in which achievability proof became simple and intuitive. Practical channel code design, on the other hand, was based on minimum distance decoding at the early stage. The invention of belief propagation decoding with soft input and soft output, leading to the birth of turbo codes and low-density-parity check (LDPC) codes which are indispensable coding techniques in current communication systems, changed the whole research area so dramatically that people started to use the term "modern coding theory'''' to refer to the research based on this decoding rule. In this thesis, we propose a new decoding rule, dubbed jar decoding, which would be expected to bring some new thoughts to both the code performance analysis and the code design. Given any channel with input alphabet X and output alphabet Y, jar decoding rule can be simply expressed as follows: upon receiving the channel output y^n ∈ Y^n, the decoder first forms a set (called a jar) of sequences x^n ∈ X^n considered to be close to y^n and pick any codeword (if any) inside this jar as the decoding output. The way how the decoder forms the jar is defined independently with the actual channel code and even the channel statistics in certain cases. Under this jar decoding, various coding theorems are proved in this thesis. First of all, focusing on the word error probability, jar decoding is shown to be near optimal by the achievabilities proved via jar decoding and the converses proved via a proof technique, dubbed the outer mirror image of jar, which is also quite related to jar decoding. Then a Taylor-type expansion of optimal channel coding rat

关键词： channel capacity non-asymptotic equipartition property channel coding jar decoding non-asymptotic coding theorems Taylor-type Expansion LDPC codes interactive encoding and decoding

来源：评论

学校读者我要写书评

暂无评论

Low-Density Linear IED Schemes for Lossless Source Coding with Decoder Only Side Information

Low-Density Linear IED Schemes for Lossless Source Coding wi...

引用

Annual Allerton Conference on Communication, Control, and Computing

作者： Jin Meng En-hui Yang Da-ke He Dept. of Electrical and Computer Engineering University of Waterloo Research In Motion/SlipStream

ISBN: (纸本)9781424429257

In this paper we investigate the performance of linear interactive encoding and decoding (BED) for lossless source coding with decoder only side information. Assume that the source alphabet X is a finite field and that the side information alphabet is finite. It is shown that there exist universal linear BED schemes which are asymptotically optimal for any stationary, ergodic source-side information pair. Our analysis of low-density IED schemes further reveals that as long as ε_np_n~* = Ω (log n/n), where ε_n and p_n~* are real numbers, one can always construct a sequence of universal linear IED schemes {I_n} such that the average density of the parity check matrices associated with I_n is concentrated around (|x| - 1)p_n~*, and the resulting symbol error probability is upper bounded by ε_n + o(ε_n).

关键词： interactive encoding and decoding Linear Block Code Low Density Parity Check Matrix Slepian-Wolf Coding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：