基于 Fountain 编码的无线通信数据压缩技术

需积分: 4 156 浏览量更新于2024-09-21 收藏 202KB PDF 举报

"无线通信基础：一本关于无线通信的权威书籍" 《无线通信基础》是由David Tse（加州大学伯克利分校）和Pramod Viswanath（伊利诺伊大学厄巴纳-香槟分校）合作编著的一本经典教材，深入浅出地介绍了无线通信领域的基本原理和关键技术。本书涵盖了无线通信系统的各个方面，包括信号传输、频谱利用率、编码与解码技术等，是学习无线通信理论和技术的重要参考资料。在书中的部分内容，作者提到了一种基于喷泉码的通用可变长度数据压缩方法，用于二进制源的无损压缩。这种方法结合了Burrows-Wheeler块排序变换（BWT）、喷泉编码器以及闭合循环迭代掺杂算法。解压过程则利用了信念传播算法，配合迭代掺杂算法和逆BWT进行操作。这种压缩算法实现了线性时间的压缩和解压复杂度，并且在性能上与最先进的压缩算法相媲美。介绍部分指出，对于无限大的块长度，线性固定长度编码可以达到无记忆源的最小压缩率，这是根据[1]中的理论得出的。而对于任意（不一定是平稳或遍历）的源，同样可以实现有效的压缩，这在[2]中有详细阐述。这些理论基础是理解本文中提出的可变长度压缩算法的关键，因为它们展示了在不同条件下的信息编码效率。喷泉码是一种创新的纠错编码方式，它允许接收端通过接收到的任意数量的码字恢复原始数据，无需事先知道完整的编码结构。BWT是一种文本压缩技术，通过重新排列输入序列来减少重复和相似性，从而提高压缩效率。而信念传播算法则在信息处理和概率推理中广泛应用，特别是在图模型和解码过程中，能够有效地估计变量的后验概率。该压缩算法的闭合循环迭代掺杂算法可能是为了进一步优化编码效率，通过反馈机制动态调整编码参数，以适应数据的统计特性。这样的设计使得算法能够自适应地处理不同类型的输入数据，提供高效且灵活的压缩方案。《无线通信基础》不仅提供了无线通信的基本理论，还展示了实际应用中的创新技术，如本文提到的数据压缩方法。这本书对于无线通信专业的学生、研究人员以及工程师来说，都是不可或缺的学习和参考资源，帮助他们理解和掌握无线通信系统的设计和优化。

Universal variable-length data compression

of binary sources using fountain codes

Giuseppe Caire Shlomo Shamai Amin Shokrollahi Sergio Verd´u

Institut Eurecom Technion EPFL Princeton University

giuseppe.caire@eurecom.fr, sshlomo@ee.technion.ac.il,amin.shokrollahi@epfl.ch,verdu@princeton.edu

Abstract — This paper proposes a universal

variable-length lossless compression algorithm based

on fountain codes. The compressor concatenates

the Burrows-Wheeler block sorting transform (BWT)

with a fountain encoder, together with the closed-

loop iterative doping algorithm. The decompressor

uses a Belief Propagation algorithm in conjunction

with the iterative doping algorithm and the inverse

BWT. Linear-time compression/decompression com-

plexity and competitive performance with respect to

state-of-the-art compression algorithms are achieved.

I. Introduction

It is known that linear ﬁxed-length encoding can achieve

for asymptotically large blocklength the minimum compres-

sion rate for memoryless sources [1] and for arbitrary (not

necessarily stationary/ergodic) sources [2].

After initial attempts [3, 4, 5] to construct linear lossless

co des were nonuniversal, limited to memoryless sources and

failed to reach competitive performance with standard data

compression algorithms, the interest in linear data compres-

sion waned. Recently [6, 7, 8] came up with a universal loss-

less data compression algorithm based on irregular low-density

parity-check codes which has linear encoding and decoding

complexity, can exploit source memory and in the experiments

for binary sources presented in [6, 7, 8] showed competitive

p erformance with respect to standard compressors such as

gzip, PPM and bzip.

The scheme of [6, 7, 8] was based on the important class

of sparse-graph error correcting codes called low-density par-

ity check (LDPC) codes. The block-sorting transform (or

Burrows-Wheeler transform (BWT)) [9] is a one-to-one trans-

formation, which performs the following operation: it gener-

ates all cyclic shifts of the given data string and sorts them

lexicographically. The last column of the resulting matrix is

the BWT output from which the original data string can be

recovered, knowing the BWT index which is the location of

the original sequence in the matrix. The BWT shifts redun-

dancy in the memory to redundancy in the marginal distribu-

tions. The redundancy in the marginal distributions is then

much easier to exploit at the decoder as the decoding com-

plexity is independent of the complexity of the source model

(in particular, the number of states for Markov sources). The

output of the BWT (as the blocklength grows) is asymptoti-

cally piecewise i.i.d. for stationary ergodic tree sources. The

length, location, and distribution of the i.i.d. segments depend

on the statistics of the source. The existing universal BWT-

based methods for data compression generally hinge on the

idea of compression for a memoryless source with an adaptive

pro cedure that learns implicitly the local distribution of the

piecewise i.i.d. segments, while forgetting the eﬀect of distant

symbols.

In the data compression algorithm of [6, 7], the compression

is carried out by multiplication of the Burrows-Wheeler Trans-

form of the source string with the parity-check matrix of an

error correcting code. Of particular interest are LDPC codes

since the belief propagation (BP) decoder is able to incorpo-

rate the time-varying marginals at the output of the BWT

in a very natural way. The nonidentical marginals produced

at the output of the BWT have a synergistic eﬀect with the

BP algorithm which is able to iteratively exploit imbalances

in the reliability of variable nodes. The universal implementa-

tion of the algorithm where the encoder identiﬁes the source

segmentation and describes it to the decompressor is discussed

in [8].

An important ingredient in the compression scheme of

[6, 7, 8] is the ability to do decompression at the compres-

sor. This enables to tune the choice of the codebook to the

source realization and more importantly it enables the use of

the Closed-Loop Iterative Doping (CLID) algorithm of [6, 2].

This is an eﬃcient algorithm which enables zero-error variable-

length data compression with performance which is quite com-

p etitive with that of standard data compression algorithms.

In this paper, instead of adopting irregular low-density par-

ity check codes of a given rate approximately matched to the

source we adopt a diﬀerent approach based on rateless foun-

tain codes. This class of codes turns out to be more natural for

variable-length data compression applications than standard

blo ck codes and achieves in general comparable p erformance

to the LDPC-based scheme of [6, 7, 8].

The rest of the paper is organized as follows. Section II

reviews the main features of fountain codes for channel co d-

ing. Section III gives a brief summary of the principle of

b elief propagation decoding which is common to both chan-

nel and source decoding. Our scheme for data compression

with fountain codes is explained in detail in Section IV in the

setting of nonuniversal compression of binary sources. For fur-

ther background on linear codes for data compression and the

closed-lo op iterative doping algorithm the reader is referred to

[2]. The modelling module necessary for universal application

is discussed in Section V. Section VI shows several experi-

ments and comparisons of redundancy with oﬀ-the-shelf data

compression algorithms run with synthetic sources. Through-

out the discussion we limit ourselves to binary sources. The

generalization to nonbinary alphabets is treated in [10].

II. Fountain Codes for Channel Coding

Fountain codes [11] form a new class of sparse-graph codes

designed for protection of data against noise in environments

where the noise level is not known a-priori. To achieve this, a

fountain code produces a potentially limitless stream of out-

put symbols for a given vector of input symbols. In practical

applications, each output symbol is a linear function of the

input symbols, and the output symbols are generated inde-

p endently and randomly, according to a distribution which is

下载后可阅读完整内容，剩余5页未读，立即下载

swordest5

粉丝: 0
资源: 3

基于 Fountain 编码的无线通信数据压缩技术

无线通信基础：理论与系统实现

Siebel Fundamentals 8.1中文译本：登陆与权限解析

"无线通信基础习题解答PDF及坐标转换

fundamentals of wireless communication无线通信基础

Fundamentals of wireless communication

Fundamentals of Wireless Communication

fundamentals of wireless communication

Fundamentals Of Wireless Communication

Fundamentals of Wireless Communication-pdf

Fundamentals of Wireless Communication.pdf

最新资源