一种用于文本压缩的信源容错译码算法

LZ算法在文本压缩领域应用广泛。LZ译码以先前接收码字的译码结果形成字典,后续译码依赖于先前的重构数据,一旦压缩码字出现误码将会引起严重的误码扩散。分析了主流的LZ77算法编译码原理,讨论了输入误码对译码字典和解压数据的影响,研究了误码传播问题。在此基础上提出一种用于文本压缩数据的容错译码算法,指出容错处理对抑制误码传播及保证LZ77解压数据的完整性具有重要意义。     

An efficient compression scheme for data communication which uses a new family of self‐organizing binary search trees

In this paper, we demonstrate that we can effectively use the results from the field of adaptive self‐organizing data structures in enhancing compression schemes. Unlike adaptive lists, which have already been used in compression, to the best of our knowledge, adaptive self‐organizing trees have not been used in this regard. To achieve this, we introduce a new data structure, the partitioning binary search tree (PBST) which, although based on the well‐known binary search tree (BST), also appropriately partitions the data elements into mutually exclusive sets. When used in conjunction with Fano encoding, the PBST leads to the so‐called Fano binary search tree (FBST), which, indeed, incorporates the required Fano coding (nearly equal probability) property into the BST. We demonstrate how both the PBST and the FBST can be maintained adaptively and in a self‐organizing manner. The updating procedure that converts a PBST into an FBST, and the corresponding new tree‐based operators, namely the shift‐to‐left and the shift‐to‐right operators, are explicitly presented. The encoding and decoding procedures that also update the FBST have been implemented and rigorously tested. Our empirical results on the files of the well‐known benchmarks, the Calgary and Canterbury Corpora, show that the adaptive Fano coding using FBSTs, the Huffman, and the greedy adaptive Fano coding achieve similar compression ratios. However, in terms of encoding/decoding speed, the new scheme is much faster than the latter two in the encoding phase, and they achieve approximately the same speed in the decoding phase. We believe that the same philosophy, namely that of using an adaptive self‐organizing BST to maintain the frequencies, can also be utilized for other data encoding mechanisms, even as the Fenwick scheme has been used in arithmetic coding. Copyright © 2008 John Wiley & Sons, Ltd.     

四线和特征的快速分形图像编码

分形图像编码具有压缩比高、解码速度快、重构图像质量高等特点,但因这种算法在编码时定义域的搜索量十分巨大,导致其计算复杂度高、编码时间过长,阻碍了它的实用性和普遍应用.为解决此问题,文中提出一种基于四线和特征值编码算法,该算法根据匹配均方根误差与四线和特征间的关系,将全局搜索转化为局部搜索(近邻搜索),限定搜索空间,减少定义域块的搜索,从而提高编码速度.仿真实验结果表明:该算法解码图像质量在客观上优于1 -范数特征算法;与基本分形编码算法相比,基于四线和特征算法在主观上不改变重构图像质量,但在编码速度上却得到极大提高.     

Gzip压缩的硬件加速电路设计

硬件无损压缩技术可以发挥专用电路的速度和功耗优势,被广泛应用于大数据计算以及通信领域.本文以GNUzip（Gzip）数据无损压缩技术为原型设计了一种硬件压缩电路.通过采用双Hash函数、并行匹配处理、面向硬件存储的LZ77压缩存储格式、高效数据拼接器等加速方法,发挥并行计算和流水线结构优势,提升压缩速率.该硬件压缩电路基于Verilog HDL设计,使用现场可编程门阵列（FPGA）进行测试和验证.测试数据表明：与软件压缩方式相比,该硬件压缩电路在获得适中压缩率（65.9%）的同时,其压缩速率得到显著提升,平均压缩速率达171Mb/s,满足网络通信、数据存储等实时压缩应用需求.     

Lossless, near-lossless, and refinement coding of bilevel images

We present general and unified algorithms for lossy/lossless coding of bilevel images. The compression is realized by applying arithmetic coding to conditional probabilities. As in the current JBIG standard the conditioning may be specified by a template. For better compression, the more general free tree may be used. Loss may be introduced in a preprocess on the encoding side to increase compression. The primary algorithm is a rate-distortion controlled greedy flipping of pixels. Though being general, the algorithms are primarily aimed at material containing half-toned images as a supplement to the specialized soft pattern matching techniques that work better for text. Template based refinement coding is applied for lossy-to-lossless refinement. Introducing only a small amount of loss in half-toned test images, compression is increased by up to a factor of four compared with JBIG. Lossy, lossless, and refinement decoding speed and lossless encoding speed are less than a factor of two slower than JBIG. The (de)coding method is proposed as part of JBIG2, an emerging international standard for lossless/lossy compression of bilevel images.     

The Universal LZ77 Compression Algorithm Is Essentially Optimal for Individual Finite-Length $N$-Blocks

Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite alphabet are being compressed into binary sequences by some one-to-one mapping. No a priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that there exist a number of asymptotically optimal universal data compression algorithms (e.g., the Lempel-Ziv (LZ) algorithm, context tree algorithm and an adaptive Hufmann algorithm) such that when successively applied to N-blocks then, the best error-free compression for the particular individual sequence X is achieved as N tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. Essential optimality for the compression of finite-length sequences is defined. It is shown that the LZ77 universal compression of N-blocks is essentially optimal for finite N-blocks. Previously, it has been demonstrated that a universal context tree compression of N blocks is essentially optimal as well.     

High-speed IP routing with binary decision diagrams based hardware address lookup engine

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.     

Compression of correlated binary sources using turbo codes

We propose the use of punctured turbo codes for compression of correlated binary sources. Compression is achieved because of puncturing. The resulting performance is close to the theoretical limit provided by the Slepian-Wolf (1973) theorem. No information about the correlation between sources is required in the encoding process. The proposed source decoder utilizes iterative schemes, and performs well even when the correlation between the sources is not known in the decoder, since it can be estimated jointly with the iterative decoding process     

Match-length functions for data compression

We investigate uniquely decodable match-length functions (MLFs) in conjunction with Lempel-Ziv (1977) type data compression. An MLF of a data string is a function that associates a nonnegative integer with each position of the string. The MLF is used to parse the input string into phrases. The codeword for each phrase consists of a pointer to the beginning of a maximal match consistent with the MLF value at that point. We propose several sliding-window variants of LZ compression employing different MLF strategies. We show that the proposed methods are asymptotically optimal for stationary ergodic sources and that their convergence compares favorably with the LZ1 variant of Wyner and Ziv (see Proc. IEEE, vol.82, no.6, p.872, 1994)     

中文文本的LZSS算法实现及研究

文章通过程序设计实现了LZSS压缩算法,并对其进行了改进以适合于中文压缩,改进后的压缩程序测试结构证明改进是有效的,相比于标准LZSS12压缩算法,压缩比有了很大幅度的提高 ,对于中文文本长文件,其最大压缩比已达到20左右,对于英文文本文件的压缩效果也好于LZSS12算法。     

MARVLE: a VLSI chip for data compression using tree-based codes

Describes the architecture and design of a CMOS VLSI chip for data compression and decompression using tree-based codes. The chip, called MARVLE, implements a memory-based architecture for variable length encoding and decoding based on tree-based codes. The architecture is based on an efficient scheme of mapping the tree representing any binary code onto a memory device. A prototype 2-mm CMOS VLSI chip has been designed, verified, and fabricated by the MOSIS facility. The chip has a 512×12 static RAM with an access time of 4 ns and logic circuitry for compression as well as decompression. The chip occupies a silicon area of 6.8 mm×6.9 mm and consists of 49695 transistors. The prototype chip yields a compression rate of 95.2 Mb/s and a decompression rate of 60.6 Mb/s with a clock rate of 83.3 MHz. The VLSI hardware can be used to implement the JPEG baseline compression scheme     

Adaptive approximate nearest neighbor search for fractal imagecompression

Fractal image encoding is a computationally intensive method of compression due to its need to find the best match between image subblocks by repeatedly searching a large virtual codebook constructed from the image under compression. One of the most innovative and promising approaches to speed up the encoding is to convert the range-domain block matching problem to a nearest neighbor search problem. This paper presents an improved formulation of approximate nearest neighbor search based on orthogonal projection and pre-quantization of the fractal transform parameters. Furthermore, an optimal adaptive scheme is derived for the approximate search parameter to further enhance the performance of the new algorithm. Experimental results showed that our new technique is able to improve both the fidelity and compression ratio, while significantly reduce memory requirement and encoding time.     

On unequal error protection for LZSS compressed data

An unequal error protection scheme for Lempel–Ziv–Storer–Szymanski (LZSS) compressed data is proposed. The novel method divides the compressed data into short blocks, which allows for near-real-time operation. The error protection is obtained through the application of BCH codes and block interleavers. Compared to other methods found in the literature, the proposed scheme is either more efficiency in terms of compression efficient or in terms of decoding delay.     

Image compression by B-tree triangular coding

This paper describes an algorithm for still image compression called B-tree triangular coding (BTTC). The coding scheme is based on the recursive decomposition of the image domain into right-angled triangles arranged in a binary tree. The method is attractive because of its fast encoding, O(n log n), and decoding, Θ(n), where n is the number of pixels, and because it is easy to implement and to parallelize. Experimental studies indicate that BTTC produces images of satisfactory quality from a subjective and objective point of view, One advantage of BTTC over JPEG is its shorter execution time     

A Document Image Model and Estimation Algorithm for Optimized JPEG Decompression

The JPEG standard is one of the most prevalent image compression schemes in use today. While JPEG was designed for use with natural images, it is also widely used for the encoding of raster documents. Unfortunately, JPEG's characteristic blocking and ringing artifacts can severely degrade the quality of text and graphics in complex documents. We propose a JPEG decompression algorithm which is designed to produce substantially higher quality images from the same standard JPEG encodings. The method works by incorporating a document image model into the decoding process which accounts for the wide variety of content in modern complex color documents. The method works by first segmenting the JPEG encoded document into regions corresponding to background, text, and picture content. The regions corresponding to text and background are then decoded using maximum a posteriori (MAP) estimation. Most importantly, the MAP reconstruction of the text regions uses a model which accounts for the spatial characteristics of text and graphics. Our experimental comparisons to the baseline JPEG decoding as well as to three other decoding schemes, demonstrate that our method substantially improves the quality of decoded images, both visually and as measured by PSNR.     

On-line and off-line heuristics for inferring hierarchies ofrepetitions in sequences

Hierarchical dictionary-based compression schemes form a grammar for a text by replacing each repeated string with a production rule. While such schemes usually operate on-line, making a replacement as soon as repetition is detected, off-line operation permits greater freedom in choosing the order of replacement. In this paper, we compare the on-line method with three off-line heuristics for selecting the next substring to replace: longest string first, most common string first, and the string that minimizes the size of the grammar locally. Surprisingly, two of the off-line techniques, like the on-line method, run in time linear in the size of the input. We evaluate each technique on artificial and natural sequences. In general, the locally-most-compressive heuristic performs best, followed by most frequent, the on-line technique, and, lagging by some distance, the longest-first technique     

Combining fractal image compression and vector quantization

In fractal image compression, the code is an efficient binary representation of a contractive mapping whose unique fixed point approximates the original image. The mapping is typically composed of affine transformations, each approximating a block of the image by another block (called domain block) selected from the same image. The search for a suitable domain block is time-consuming. Moreover, the rate distortion performance of most fractal image coders is not satisfactory. We show how a few fixed vectors designed from a set of training images by a clustering algorithm accelerates the search for the domain blocks and improves both the rate-distortion performance and the decoding speed of a pure fractal coder, when they are used as a supplementary vector quantization codebook. We implemented two quadtree-based schemes: a fast top-down heuristic technique and one optimized with a Lagrange multiplier method. For the 8 bits per pixel (bpp) luminance part of the 512kappa512 Lena image, our best scheme achieved a peak-signal-to-noise ratio of 32.50 dB at 0.25 bpp.     

一种短延时Turbo编码调制系统的设计

本文设计了一种比传统体制减少了一半延时的Turbo编码调制系统,介绍了交织器的相关限制.提出了一种在译码过程中对信道值的估计方法,使得外信息的计算更加趋于精确,从而提高了译码性能.这种迭代译码算法是标准格码调制译码算法的一种自然推广,同时也类似于二元Turbo码在BPSK调制下的逐比特译码算法.采用吞吐率为2bits/s/Hz的8PSK调制,比特错误率为10^-5所需的信噪比与Shannon限相距不到0.4dB.     

Capacity-approaching turbo coding and iterative decoding for relay channels

In this paper, we design turbo-based coding schemes for relay systems together with iterative decoding algorithms. In the proposed schemes, the source node sends coded information bits to both the relay and the destination nodes, while the relay simultaneously forwards its estimate for the previous coded block to the destination after decoding and re-encoding. The destination observes a superposition of the codewords and uses an iterative decoding algorithm to estimate the transmitted messages. Different from the block-by-block decoding techniques used in the literature, this decoding scheme operates over all the transmitted blocks jointly. Various encoding and decoding approaches are proposed for both single-input single-output and multi-input multi-output systems over several different channel models. Capacity bounds and information-rate bounds with binary inputs are also provided, and it is shown that the performance of the proposed practical scheme is typically about 1.0-1.5 dB away from the theoretical limits, and a remarkable advantage can be achieved over the direct and multihop transmission alternatives.