The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper proposes a new class of grammar-based lossless source code. Grammar-based code is a class of universal data compression algorithm using a context-free grammar. A Semi-Chomsky Normal Form (semi-CNF) of context free grammar, which is a modified form of the context free grammar (CNF), is newly introduced. The proposed algorithm encodes a given sequence to a binary codeword in three step....
In this paper we define the average coding rate of a variable-to-fixed length (VF) lossless source code as the expectation of the pointwise coding rate, which is called average pointwise coding rate. It has been shown that the Tunstall code is asymptotically optimal under the criterion optimizing the average pointwise coding rate. In this paper, we propose a new VF code attaining optimal average pointwise...
In this paper, some theorems which give relationships between a sufficient statistic and the universality of a VV source code are presented. These theorems can be used as a methodology to construct a new two-step universal code using a sufficient statistic. As an example, the parsing tree of LZY code, which is a variation of LZ78 code, is investigated. It is proved that LZY parsing tree is an asymptotically...
Dube and Beaudoin have proposed a technique of lossless data compression called compression via substring enumeration (CSE) for a binary source alphabet. Dube and Yokoo proved that CSE has a linear complexity both in time and in space worst-case performance for the length of string to be encoded. Dubé and Yokoo have specified appropriate predictors of the uniform and combinatorial prediction models...
The coding rate of a multishot Tunstall code for stationary memoryless sources is investigated in non-universal situation so that the probability distribution of a source is known to the encoder and the decoder. Tunstall code is the original and an optimal variable-to-fixed length (VF) source code. A multishot VF code parses a given source sequence to variable-length blocks and encodes them to fixed-length...
A converse coding theorem for a variable-to-fixed length (VF) source code is proved for a general source with count-ably infinite alphabet. In this result, redundancy is defined by the difference of the symbolwise codeword length and the symbolwise ideal codeword length. It is proved that the redundancy is nonnegative in probability for the codes such that the decoding error probability vanishes and...
Dubé and Beaudoin proposed a new technique of lossless data compression called compression via substring enumeration (CSE) in 2010. We present an upper bound of the amount of bits used by lossless compression via the CSE technique to encode any given binary string from the class of independent and identically distributed (i.i.d.) sources. We compare the worst case maximum redundancy obtained by the...
We consider a situation where n-tuples generated from a general source are encoded by a fixed-length code and discuss coding theorems on the worst-case redundancy, where the worst-case redundancy is defined as the maximum of the difference between the rate and the ideal codeword length per symbol with respect to all the correctly decodable n-tuples. We treat the four cases where the decoding error...
This paper is concerned with the redundancy rate of fixed length source code for a general source with a countably infinite alphabet. We evaluate the minimum achievable redundancy rate R of fixed-to-fixed length (FF) and variable-to-fixed length (VF) codes with two definitions of redundancy rates, which are (i) the difference between the coding rate and the spectral sup-entropy rate and (ii) the difference...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.