Arithmetic Code Spectrum Of General Binary Sources

Distributed arithmetic code(DAC) is an extension of arithmetic code, which has excellent performance for short data. DAC is widely used because of this characteristics. The research about DAC, especially about encoding efficiency and decoding complexity analysis is relatively small. Codebook cardinality spectrum(CCS) can effectively improve the encoding performance and reduce the decoding complexity for DAC, and has important guiding significance for the smooth development of DAC related researches. But the existing research findings of codebook cardinality spectrum are only applicable to equiprobable binary sources, limiting the application of codebook cardinality spectrum. In the paper, the codebook cardinality spectrum is extended to nonuniform binary sources on the basis of the research findings. And we also propose an improved algorithm based on spectrum numerical algorithm and an improved scheme of arithmetic coder. The main research contents of this study are as follows:(1) Arithmetic encoder optimization. The classical arithmetic encoder appends enough bits to the encoding bitstream after coding all symbols. A new method is proposed in this paper. In the new method, only ?01?? or ?10?? is appended to the encoding bitstream after coding all symbols. The new method ensures the encoding results fall in the final encoding interval, reduces the workload in the encoder and improves the encoding efficiency.(2) An improved algorithm based on spectrum numerical algorithm. Spectrum is a very complicated problem. We usually use the numerical algorithm to calculate spectrum. But numerical algorithm is very complex to calculate spectrum directly as it contains the iterative calculation. We simplify the numerical algorithm by removing an unnecessary function and propose an improved algorithm based on spectrum numerical algorithm. In the paper, we verify the correctness of the new numerical algorithm. And the experimental results show that the new numerical algorithm can effectively improve the computational efficiency of spectrum.(3) Codebook cardinality spectrum of DAC for nonuniform binary sources. In the paper,we define the initial spectrum and obtain a general explicit form of the initial CCS by utilizing the Fourier transform. We also define the evolution of CCS and the ultimate CCS. We define the expansion factor for nonuniform binary sources to measure the complexity of the DACdecoder. In the paper we use the improved algorithm to calculate the CCS. Finally, the paper presents some experimental results to analysis the basic properties of the CCS based on nonuniform binary sources and prove the theoretical reasoning process is correct.