Analysis on tailed distributed arithmetic codes for uniform binary sources

Yong Fang, Vladimir Stankovic, Samuel Cheng, En-hui Yang

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Distributed Arithmetic Coding (DAC) is a variant of Arithmetic Coding (AC) that can realise Slepian-Wolf Coding (SWC) in a nonlinear way. In the previous work, we defined Codebook Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS) for DAC. In this paper, we make use of CCS and HDS to analyze tailed DAC, a form of DAC mapping the last few symbols of each source block onto non-overlapped intervals as traditional AC. We first derive the exact HDS formula for tailless DAC, a form of DAC mapping all symbols of each source block onto overlapped intervals, and show that the HDS formula previously given is actually an approximate version. Then the HDS formula is extended to tailed DAC. We also deduce the average codebook cardinality, which is closely related to decoding complexity, and rate loss of tailed DAC with the help of CCS. The effects of tail length are extensively analyzed. It is revealed that by increasing tail length to a value not close to the bitstream length, closely-spaced codewords within the same codebook can be removed at the cost of a higher decoding complexity and a larger rate loss. Finally, theoretical analyses are verified by experiments.
LanguageEnglish
Pages4305-4319
Number of pages15
JournalIEEE Transactions on Communications
Volume64
Issue number10
Early online date12 Aug 2016
DOIs
Publication statusPublished - 31 Oct 2016

Fingerprint

Hamming distance
Decoding
Experiments

Keywords

  • distributed source coding
  • Slepian-Wolf coding
  • distributed arithmetic coding
  • hamming distance spectrum
  • codebook cardinality spectrum
  • tail length
  • codebooks

Cite this

Fang, Yong ; Stankovic, Vladimir ; Cheng, Samuel ; Yang, En-hui. / Analysis on tailed distributed arithmetic codes for uniform binary sources. In: IEEE Transactions on Communications. 2016 ; Vol. 64, No. 10. pp. 4305-4319.
@article{0efb28b09f034be0835978fa00c2f6db,
title = "Analysis on tailed distributed arithmetic codes for uniform binary sources",
abstract = "Distributed Arithmetic Coding (DAC) is a variant of Arithmetic Coding (AC) that can realise Slepian-Wolf Coding (SWC) in a nonlinear way. In the previous work, we defined Codebook Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS) for DAC. In this paper, we make use of CCS and HDS to analyze tailed DAC, a form of DAC mapping the last few symbols of each source block onto non-overlapped intervals as traditional AC. We first derive the exact HDS formula for tailless DAC, a form of DAC mapping all symbols of each source block onto overlapped intervals, and show that the HDS formula previously given is actually an approximate version. Then the HDS formula is extended to tailed DAC. We also deduce the average codebook cardinality, which is closely related to decoding complexity, and rate loss of tailed DAC with the help of CCS. The effects of tail length are extensively analyzed. It is revealed that by increasing tail length to a value not close to the bitstream length, closely-spaced codewords within the same codebook can be removed at the cost of a higher decoding complexity and a larger rate loss. Finally, theoretical analyses are verified by experiments.",
keywords = "distributed source coding, Slepian-Wolf coding, distributed arithmetic coding, hamming distance spectrum, codebook cardinality spectrum, tail length, codebooks",
author = "Yong Fang and Vladimir Stankovic and Samuel Cheng and En-hui Yang",
note = "{\circledC} 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works",
year = "2016",
month = "10",
day = "31",
doi = "10.1109/TCOMM.2016.2599535",
language = "English",
volume = "64",
pages = "4305--4319",
journal = "IEEE Transactions on Communications",
issn = "0090-6778",
number = "10",

}

Analysis on tailed distributed arithmetic codes for uniform binary sources. / Fang, Yong; Stankovic, Vladimir; Cheng, Samuel; Yang, En-hui.

In: IEEE Transactions on Communications, Vol. 64, No. 10, 31.10.2016, p. 4305-4319.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Analysis on tailed distributed arithmetic codes for uniform binary sources

AU - Fang, Yong

AU - Stankovic, Vladimir

AU - Cheng, Samuel

AU - Yang, En-hui

N1 - © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

PY - 2016/10/31

Y1 - 2016/10/31

N2 - Distributed Arithmetic Coding (DAC) is a variant of Arithmetic Coding (AC) that can realise Slepian-Wolf Coding (SWC) in a nonlinear way. In the previous work, we defined Codebook Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS) for DAC. In this paper, we make use of CCS and HDS to analyze tailed DAC, a form of DAC mapping the last few symbols of each source block onto non-overlapped intervals as traditional AC. We first derive the exact HDS formula for tailless DAC, a form of DAC mapping all symbols of each source block onto overlapped intervals, and show that the HDS formula previously given is actually an approximate version. Then the HDS formula is extended to tailed DAC. We also deduce the average codebook cardinality, which is closely related to decoding complexity, and rate loss of tailed DAC with the help of CCS. The effects of tail length are extensively analyzed. It is revealed that by increasing tail length to a value not close to the bitstream length, closely-spaced codewords within the same codebook can be removed at the cost of a higher decoding complexity and a larger rate loss. Finally, theoretical analyses are verified by experiments.

AB - Distributed Arithmetic Coding (DAC) is a variant of Arithmetic Coding (AC) that can realise Slepian-Wolf Coding (SWC) in a nonlinear way. In the previous work, we defined Codebook Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS) for DAC. In this paper, we make use of CCS and HDS to analyze tailed DAC, a form of DAC mapping the last few symbols of each source block onto non-overlapped intervals as traditional AC. We first derive the exact HDS formula for tailless DAC, a form of DAC mapping all symbols of each source block onto overlapped intervals, and show that the HDS formula previously given is actually an approximate version. Then the HDS formula is extended to tailed DAC. We also deduce the average codebook cardinality, which is closely related to decoding complexity, and rate loss of tailed DAC with the help of CCS. The effects of tail length are extensively analyzed. It is revealed that by increasing tail length to a value not close to the bitstream length, closely-spaced codewords within the same codebook can be removed at the cost of a higher decoding complexity and a larger rate loss. Finally, theoretical analyses are verified by experiments.

KW - distributed source coding

KW - Slepian-Wolf coding

KW - distributed arithmetic coding

KW - hamming distance spectrum

KW - codebook cardinality spectrum

KW - tail length

KW - codebooks

UR - http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=26

U2 - 10.1109/TCOMM.2016.2599535

DO - 10.1109/TCOMM.2016.2599535

M3 - Article

VL - 64

SP - 4305

EP - 4319

JO - IEEE Transactions on Communications

T2 - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

SN - 0090-6778

IS - 10

ER -