30 January 2018 in IEEE Transactions on Information Theory
This paper presents an extension of GolombRice (GR) code for coding low-entropy sources, which the gap between their entropy and the conventional GR code length gets larger. We mention here the following four facts related to the proposed code, extended-domain GR (XDGR) code: it is represented by multiple code trees, based on the idea of almost instantaneous fixed-to-variable length codes, with its algorithm being a generalization of unary coding; its structure naturally contains run-length coding; the gap between the entropy and its average code length is theoretically guaranteed to be asymptotically negligible as the entropy of the exponentially distributed sources tends to zero; and its coding parameter, corresponding to the negative-domain Rice parameter of GR code, can be estimated from the input source-symbol sequence. Experimental evaluations are also presented supporting the theorems. The proposed XDGR code, having simple algorithm and high compression performance, is expected to be used for many coding applications, which deals with exponentially distributed sources at low bit rates.
13 September 2023 in IEEE Transactions on Information Theory
A general class of the almost instantaneous fixed-to-variable-length (AIFV) codes is proposed, which contains every possible binary code we can make when allowing finite bits of decoding delay. The contribution of the paper lies in the following. (i) Introducing N -bit-delay AIFV codes, constructed by multiple code trees with higher flexibility than the conventional AIFV codes. (ii) Proving that the proposed codes can represent any uniquely-encodable and uniquely-decodable variable-to-variable length codes. (iii) Showing how to express codes as multiple code trees with minimum decoding delay. (iv) Formulating the constraints of decodability as the comparison of intervals in the real number line. The theoretical results in this paper are expected to be useful for further study on AIFV codes.
1 September 2025 in IEEE Transactions on Information Theory
This paper presents an optimal construction of N-bit-delay almost instantaneous fixed-to-variable-length (AIFV) codes, the general form of binary codes we can make when finite bits of decoding delay are allowed. The presented method enables us to optimize lossless codes among a broader class of codes compared to the conventional FV and AIFV codes. The paper first discusses the problem of code construction, which contains some essential partial problems, and defines three classes of optimality to clarify how far we can solve the problems. The properties of the optimal codes are analyzed theoretically, showing the sufficient conditions for achieving the optimum. Then, we propose an algorithm for constructing N-bit-delay AIFV codes for given stationary memory-less sources. The optimality of the constructed codes is discussed both theoretically and empirically. They showed shorter expected code lengths when N ≥ 3 than the conventional AIFV-m and extended Huffman codes. Moreover, in the random numbers simulation, they performed higher compression efficiency than the 32-bit-precision range codes under reasonable conditions.
7 October 2019 in IEEE/ACM Transactions on Audio, Speech, and Language Processing
Entropy coding, which is an essential part of audio compression, is always required to manage the tradeoffs between compression efficiency and computational complexity, and the strategy to achieve them highly depends on the distributions of inputs. In this paper, we present a method of controlling them for enhancing the compression efficiency of Golomb-Rice (GR) encoding, one of the simplest entropy coding methods optimal for Laplacian distributions. We will show that the proposed invertible and low-complexity mapping of integers enables the GR encoding to assign nearly the optimal code length for a wider range of distributions, generalized Gaussian distributions, maintaining low computational cost. A simulation by random numbers reveals that the proposed coder based on this scheme works about 6 times faster than the state-of-the-art arithmetic coder for Gaussian-distributed integers maintaining the increase in relative redundancy around 2.6%, which is much lower than that of a conventional GR coder. Additionally, an application to a practical speech and audio coding scheme is presented, and an objective evaluation for real speech and audio signals confirms the advantages of the proposed method in compression. The method is expected to widen the capability of low-complexity entropy coding, providing us with more flexible codec designs.