In this paper, we propose two schemes, which enable any VF code to realize direct- or fast-access decoding for any long source sequence. Direct-access decoding means that any source symbol of any position can be directly decoded within constant time, not depending on the length of source sequence N, without decoding the whole codeword sequence. We also evaluate the memory size necessary to realize direct-access decoding or fast-access decoding with decoding delay O(log log N), O(log N), and so on, in the proposed schemes.

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.

The coding rate of a one-shot Tunstall code for stationary and memoryless sources is investigated in non-universal situations so that the probability distribution of the source is known to the encoder and the decoder. When studying the variable-to-fixed length code, the average coding rate has been defined as (i) the codeword length divided by the average block length. We define the average coding rate as (ii) the expectation of the pointwise coding rate, and prove that (ii) converges to the same value as (i).

The VF (Variable-to-Fixed length) arithmetic coding method combines the advantage of an ordinary stream arithmetic code with the simplicity of a block code. One of the advantages of VF codes is that the transmission errors or channel errors do not propagate infinitely and are restricted to the block in question. In this paper, we propose a modified type of non-proper VF arithmetic coding method that defines an input alphabet subset according to both the number of codewords in the current codeword set and input symbol probability and that splits the codeword set completely for a newly defined alphabet subset when the codeword set becomes smaller by each splitting. The proposed coding method carrys out independence of each codeword and guarantees that there is no collision while there is a waste of codeword(s) in conventional AB-coding due to collision. We examine the performance of the proposed method and compare it with that of other VF codes in terms of compression ratio and algorithmic complexity.