DAC Spectrum of Binary Sources with Equally-Likely Symbols
DAC Spectrum of Binary Sources with Equally-Likely Symbols
复制标题
具有等似符号的二进制源的 DAC 谱
DOI：
10.1109/tcomm.2013.012913.120486
复制
发表时间：
2013-04-01
影响因子：
8.3
通讯作者：
Fang, Yong
中科院分区：
文献类型：
--
作者：
Fang, Yong
虽然分布式算术编码(DAC)是Slepian-Wolf编码的一种有效实现，但与其译码复杂度密切相关的性能还没有得到深入的分析。本文以符号相似的二进制源为研究对象，发展了DAC谱，并将其作为工具来回答理想DAC解码器的复杂性问题。在深入分析DAC译码过程的基础上，定义了DAC谱，并提出了递归求谱的方法。首先，用函数方程约束初始DAC谱，并利用傅里叶变换得到其一般显式形式。其次，给出了由第I级DAC谱推导出第i+1级DAC谱的公式。文中还提出了一种计算DAC谱的数值方法，并证明了该方法的收敛。为了衡量理想的DAC解码器的复杂度，我们定义了扩展因子，并将其与DAC谱相关联。证明了如果将二进制码元0和1分别映射到部分重叠的区间[0，q)和[1-q，1]上，扩展因子将收敛到2q，即理想的码率-αDAC译码的复杂度约为O(2(n(1-α)。
Though distributed arithmetic coding (DAC) is an effective implementation of Slepian-Wolf coding, its performance, which is closely linked with its decoding complexity, has not received a thorough analysis. With binary sources with equally-likely symbols as the research object, this paper develops the DAC spectrum and makes use of it as a tool to answer the complexity problem of the ideal DAC decoder. Based on an in-depth analysis on DAC decoding process, we define the DAC spectrum and propose to find it by a recursive formulation. Firstly, the initial DAC spectrum is constrained by a functional equation and the Fourier transform is utilized to obtain its general explicit form. Secondly, an equation is given through which stage-(i+1) DAC spectrum can be deduced from stage-i DAC spectrum. A numerical method is also proposed for calculating DAC spectrum, whose convergency is proved. To measure the complexity of the ideal DAC decoder, we define the expansion factor and relate it to DAC spectrum. It is proved that if binary symbols 0 and 1 are mapped onto partially overlapped intervals [0, q) and [1 - q, 1) respectively, the expansion factor will converge to 2q, i.e., the complexity of the ideal rate-alpha DAC decoder is approximately O(2(n(1-alpha))).