Search 250 million research papers

An Adaptive Method for Tunstall Coding

FABRIS, FRANCESCO, PAULETTI R. · ArTS Archivio della ricerca di Trieste (University of Trieste https://www.units.it/) · 1994

Cited by 0

Applying Tunstall Coding in the existing SEED format for Seismographic Data

Edwin S. Hong, Shu-Fang Newman · 2007

The Standard for the Exchange of Earthquake Data (SEED) is a commonly used file format for recording seismographic data. The data description language (DDL) is part of the specification of the SEED format; it is used to describe the way in which the data has been encoded in the SEED file. All SEED files contain a piece of DDL code that describes how to read the data contained in the file. In this project, we explore the best possible way of compressing seismographic data losslessly under the constraint that it must be describable in DDL. Since DDL is not a Turing-complete language, it is impossible to implement many standard compression algorithms with it. However, we show it is possible to implement a modified Tunstall code under DDL that produces files that are on average 14% smaller than the traditionally used Steim2 compression technique. We also compare our results with a standard linear predictive coding scheme (which is not implementable in DDL) and show that our technique is on average 18% worse on the same set of files.

Cited by 0

Almost Sure Convergence Coding Theorems of One-Shot and Multi-Shot Tunstall Codes for Stationary Memoryless Sources

Mitsuharu Arimura · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2015

Almost sure convergence coding theorems of one-shot and multi-shot Tunstall codes are proved for stationary memoryless sources. Coding theorem of one-shot Tunstall code is proved in the case that the leaf count of Tunstall tree increases. On the other hand, coding theorem is proved for multi-shot Tunstall code with increasing parsing count, under the assumption that the Tunstall tree grows as the parsing proceeds. In this result, it is clarified that the theorem for the one-shot Tunstall code is not a corollary of the theorem for the multi-shot Tunstall code. In the case of the multi-shot Tunstall code, it can be regarded that the coding theorem is proved for the sequential algorithm such that parsing and coding are processed repeatedly. Cartesian concatenation of trees and geometric mean of the leaf counts of trees are newly introduced, which play crucial roles in the analyses of multi-shot Tunstall code.

Cited by 2

<title>Study of the codeword assignment for a revised Tunstall code</title>

Shih-Chieh Wei, Bormin Huang · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2009

By using fixed-length codewords and not using an adaptive dictionary, the Tunstall coding stands out as an errorresilient lossless compression technique. Our previous work has shown that use of the non-exhaustive parse tree can improve the compression ratio of the Tunstall coding without compromising its error resilience. As change of codeword assignment will only affect the error propagation, not the compression ratio, we experimented in this work the various codeword assignment methods to minimize the error propagation of our revised Tunstall coding. The result shows that the breadth first assignment of codewords to the Tunstall parse tree gives the lowest percent error rate. Also the linear prediction followed by non-exhaustive Tunstall parse tree, and the alignment marker (LP+Tunstall non-exhaustive) has the best performance in terms of compression ratio and percent error rate when compared to other LP+Bitcut+Tunstall methods, JPEG-2000 and CCSDS Rice coding schemes.

Cited by 0

Average-sense optimality and competitive optimality for almost instantaneous VF codes

H. Yamamoto, H. Yokoo · IEEE Transactions on Information Theory · 2001

One-shot coding and repeated coding are considered for the class of almost instantaneous variable-to-fixed length (AIVF) codes, C/sub AIVF/, which includes some nonproper VF codes in addition to the class of proper VF codes, C/sub PVF/. An algorithm is given to construct the average-sense optimal (a-optimal) AIVF code in one-shot coding that attains the maximum average parse length in C/sub AIVF/. The algorithm can also be used to obtain an AIVF code with multiple parse trees, which can attain good performance for repeated coding. Generally, the a-optimal code for one-shot coding and the good code for repeated coding are more efficient than the Tunstall (1967) code in A-ary cases if A/spl ges/3 although they coincide with the Tunstall code in the binary case. The competitively optimal (c-optimal) VF code is also considered for one-shot coding, and it is shown that the c-optimal code does not always exist in C/sub PVF/ and in C/sub AIVF/. Furthermore, whenever the c-optimal code exists, the Tunstall code is c-optimal in C/sub PVF/ and the a-optimal code obtained by our algorithm is c-optimal in C/sub AIVF/ if A=2 or 3, but the a-optimal code is not always c-optimal in C/sub AIVF/ if A/spl ges/4.

Cited by 34

Generalized Tunstall codes for sources with memory

Serap A. Savari, Robert G. Gallager · IEEE Transactions on Information Theory · 1997

Tunstall codes are variable-to-fixed length codes that maximize the expected number of source letters per dictionary string for discrete, memoryless sources. We analyze a generalization of Tunstall coding to sources with memory and demonstrate that as the dictionary size increases, the number of code letters per source symbol comes arbitrarily close to the minimum among all variable-to-fixed length codes of the same size. We also find the asymptotic relationship between the dictionary size and the average length of a dictionary entry.

Cited by 65

Some notes on Varn coding

Serap A. Savari · IEEE Transactions on Information Theory · 1994

A duality between Varn (1971) coding and Tunstall (1968) coding is demonstrated and new bounds on the expected transmission cost per source symbol for Varn codes are established. For binary channels, the superiority of the new upper bound over Krause's (1962) upper bound is proven.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 24

Low frame rate video coding for small bandwidth realtime multimedia tele-education systems

T. Algra · 2003

A fast and effective low frame rate video coding scheme is presented, which achieves acceptable image transfer times for application in real-time tele-education services, where the bandwidths are small to moderate (e.g., 9600 bit/s) and where a requirement exists for implementation on standard microcomputer equipment without dedicated hardware. The method applies two-level conditional replenishment in combination with MSVQ (mean separating vector quantizing), differential-pulse code modulation, and MTC (modified tunstall coding), i.e., a form of variable-to-fixed-length coding.

Cited by 1

Lectures on Statistical Modeling Theory

J. Rissanen · 2005

Contents I Introduction Part I INFORMATION AND CODING 8 8 2.1 Basics of Coding with Random Variables ......................... 8 2.2 Basic Properties of Entropy and Related Quantities .................. 11 2.3 Channel Capacity ...................................... 13 2.4 Chain Rules ......................................... 14 2.5 Jensen&amp;apos;s Inequality ..................................... 15 2.6 Theory of Types ...................................... 16 2.7 Equipartition Property ................................... 17 3.1 Random Processes ..................................... 18 3.2 Entropy of Stationary Processes .............................. 19 3.3 Markov processes ...................................... 20 3.4 Tree Machines ....................................... 21 3.5 Tunstall&amp;apos;s Algorithm .................................... 22 3.6 Arithmetic Codes ...................................... 24 Universal Coding 28 4.1 Lempel-Ziv - and Ma - Algorithms ............................ 29

Cited by 15

Code compression using variable-to-fixed coding based on arithmetic coding

Yuan Xie, Marilyn Wolf, Haris Lekatsas · 2003

Embedded computing systems are space and cost sensitive. Memory is one of the most restricted resources that post serious constraints on program size. Code compression, which is a special case of data compression where the input source is in machine instructions, has been proposed as a solution to this problem. Previous work in code compression has focused on either fixed-to-variable coding or dictionary-based algorithms. Code compression schemes that use variable-to-fixed (V2F) length coding were proposed, based on arithmetic coding. Experiments have shown that the compression ratio, using memoryless V2F coding for the TMS320C6x processor, have an average of 82.5% and decompression can be parallelized. A Markov-based V2F coding based on arithmetic coding has achieved an average compression ratio of 72% for TMS320C6x while decompression cannot be parallelized. Furthermore, the given experiments have shown that arithmetic coding based V2F coding has similar compression performance to Tunstall coding. Finally, a power reduction scheme for the instruction bus using the V2F coding scheme was presented.

Cited by 10

CRUSH: A New Lossless Compression Algorithm

Evon Abu-Taieh, Issam AlHadid · Modern Applied Science · 2018

Multimedia is highly competitive world, one of the properties that is reflected is speed of download and upload of multimedia elements: text, sound, pictures, animation. This paper presents CRUSH algorithm which is a lossless compression algorithm. CRUSH algorithm can be used to compress files. CRUSH method is fast and simple with time complexity O(n) where n is the number of elements being compressed.Furthermore, compressed file is independent from algorithm and unnecessary data structures. As the paper will show comparison with other compression algorithms like Shannon&amp;ndash;Fano code, Huffman coding, Run Length Encoding, Arithmetic Coding, Lempel-Ziv-Welch (LZW), Run Length Encoding (RLE), Burrows-Wheeler Transform.Move-to-Front (MTF) Transform, Haar, wavelet tree, Delta Encoding, Rice &amp;amp;Golomb Coding, Tunstall coding, DEFLATE algorithm, Run-Length Golomb-Rice (RLGR).

Cited by 1Open access

A Universal Data Compression Scheme based on the AIVF Coding Techniques

H. Yamamoto, Koki Imaeda, Kengo Hashimoto et al. · 2020

In the entropy coding, AIVF (almost instantaneous variable-to-fixed length) codes using multiple parsing trees can attain a better compression rate than the Tunstall code, which attains the best compression rate in the class of VF codes with a single parsing tree. Furthermore, the multiple parsing trees of an AIVF code can be multiplexed into a single parsing tree. In this paper, we propose a new universal data compression code based on the techniques of the AIVF code. The proposed universal code can also be considered as an improvement of the LZW code (Welch code). We explain how the AIVF coding techniques can be applied to universal coding by growing dynamically a single parsing tree, and we evaluate the compression rate of the proposed universal code theoretically and using several corpora.

Cited by 3

Enumerative encoding/decoding of variable-to-fixed-length codes for memoryless sources

Yuriy A. Reznik, Anatoly V. Anisimov · 2011

We offer novel algorithms for efficient encoding/decoding of variable-to-fixed length codes, requiring at most quadratic amount of space: O(L2), where L is the depth of a coding tree. This is a major improvement compared to exponential O(2L) usage of space by conventional techniques using complete representations of coding trees in computer’s memory. These savings are achieved by utilizing algebraic properties of VF coding trees constructed by using Tunstall or Khodak algorithms, and employing combinatorial enumeration techniques for encoding/decoding of codewords. The encoding/decoding complexity of our algorithms is linear with the number of symbols they process. As a side product, we also derive an exact formulae for the average redundancy of such codes under memoryless sources, and show its usefulness for analysis and design of codes with small number of codewords. 1

Cited by 0

A (Weakly) Polynomial Algorithm for AIVF Coding

Mordecai J. Golin, Reza Hosseini Dolatabadi, Arian Zamani · 2024

It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time.

Cited by 0

Rate-Distortion Optimized Coding for Efficient CNN Compression

Zhe Wang, Jie Lin, Mohamed Sabry Aly et al. · 2021

In this paper, we present a coding framework for deep convolutional neural network compression. Our approach utilizes the classical coding theories and formulates the compression of deep convolutional neural networks as a rate-distortion optimization problem. We incorporate three coding ingredients in the coding framework, including bit allocation, dead zone quantization, and Tunstall coding, to improve the rate-distortion frontier without noticeable system-level overhead introduced. Experimental results show that our approach achieves state-of-the-art results on various deep convolutional neural networks and obtains considerable speedup on two deep learning accelerators. Specifically, our approach achieves 20× compression ratio on ResNet-18, ResNet-34, and ResNet-50, and 10× compression ratio on the compact already model MobileNet-v2, without hurting the accuracy. We then examine the system level impact of our approach when deploying the compressed models to hardware platforms. Hardware simulation results show that our approach obtains up to 4.3× and 2.8× inference speedup on state-of-the-art deep learning accelerators TPU and Eyeriss, respectively.

Cited by 10

Code compression for embedded VLIW processors using variable-to-fixed coding

Yuan Xie, Marilyn Wolf, Haris Lekatsas · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2006

In embedded system design, memory is one of the most restricted resources, posing serious constraints on program size. Code compression has been used as a solution to reduce the code size for embedded systems. Lossless data compression techniques are used to compress instructions, which are then decompressed on-the-fly during execution. Previous work used fixed-to-variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we present a class of code compression techniques called variable-to-fixed code compression (V2FCC), which uses variable-to-fixed coding schemes based on either Tunstall coding or arithmetic coding. Though the techniques are suitable for both reduced instruction set computer (RISC) and very long instruction word (VLIW) architectures, they favor VLIW architectures which require a high-bandwidth instruction prefetch mechanism to supply multiple operations per cycle, and fast decompression is critical to overcome the communication bottleneck between memory and CPU. Experimental results for a VLIW embedded processor TMS320C6x show that the compression ratios using memoryless V2FCC and Markov V2FCC are around 82.5% and 70%, respectively. Decompression unit designs for memoryless V2FCC and Markov V2FCC are implemented in TSMC 0.25-/spl mu/m technology.

Cited by 30

Optimal Parsing Trees for Run-Length Coding of Biased Data

Sharon Aviran, Paul H. Siegel, Jack K. Wolf · IEEE Transactions on Information Theory · 2008

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping, and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints.

Cited by 11

Optimal Parsing Trees for Run-Length Coding of Biased Data

Sharon Aviran, Paul H. Siegel, Jack K. Wolf · 2006

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints

Cited by 4

Optimal Parsing Trees for Run-Length Coding of Biased Data

2008

Abstract — We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints. I.

Cited by 0

Quantitative Comparative Study of the Performance of Lossless Compression Methods Based on a Text Data Model

Namogo Silué, Sié Ouattara, Mouhamadou Dosso et al. · Open Journal of Applied Sciences · 2024

Data compression plays a key role in optimizing the use of memory storage space and also reducing latency in data transmission. In this paper, we are interested in lossless compression techniques because their performance is exploited with lossy compression techniques for images and videos generally using a mixed approach. To achieve our intended objective, which is to study the performance of lossless compression methods, we first carried out a literature review, a summary of which enabled us to select the most relevant, namely the following: arithmetic coding, LZW, Tunstall’s algorithm, RLE, BWT, Huffman coding and Shannon-Fano. Secondly, we designed a purposive text dataset with a repeating pattern in order to test the behavior and effectiveness of the selected compression techniques. Thirdly, we designed the compression algorithms and developed the programs (scripts) in Matlab in order to test their performance. Finally, following the tests conducted on relevant data that we constructed according to a deliberate model, the results show that these methods presented in order of performance are very satisfactory: - LZW - Arithmetic coding - Tunstall algorithm - BWT + RLE Likewise, it appears that on the one hand, the performance of certain techniques relative to others is strongly linked to the sequencing and/or recurrence of symbols that make up the message, and on the other hand, to the cumulative time of encoding and decoding.

Cited by 0Open access