Sequentially-Constructible Reversible Variable Length Codes

Sayed Jalal Zahabi

doi:10.1109/TCOMM.2014.2329478

Return

Sequentially-Constructible Reversible Variable Length Codes

2014-08-01

PRE

Sayed Jalal Zahabi *

Adel Aghajan

Mohammadali Khosravifard

DOI：10.1109/TCOMM.2014.2329478

Original

Original request for help

Save

Abstract

En 中文

Dominant codelength sequences for reversible variable length codes (RVLCs) have been recently introduced and studied as a means to looking into optimal RVLCs. However, obtaining the dominant sequences for RVLCs is computationally challenging. In this paper, we consider a special subset of all RVLCs, namely, the sequentially-constructible (SC) RVLCs, for which the dominant sequences can be obtained with less computational complexity. Of course, this time saving is achieved at the cost of losing the optimality. However, it is shown that the dominant sequences for SC RVLCs provide acceptable performance in terms of the redundancy. Specifically, it is seen that the worst case penalty in using the optimal SC RVLCs with respect to the optimal RVLCs is at most 2/9 bit per symbol for alphabet size of up to 16. While obtaining the dominant sequences of SC RVLCs is relatively faster, it will still become challenging as the search space of the relevant branch-and-bound algorithm gets larger, when the source alphabet size increases. In order to further reduce the time complexity, we propose an alternative approach to a table of SC RVL codelength sequences, which avoids the branch-and-bound algorithm. It is shown that the codes obtained by this approach perform almost as well as the SC dominant sequences. Specifically, for an alphabet size of up to 21, the redundancy of this approach is, at most, 2/19 bit more than the optimal SC RVLCs.

Keywords:

RVLC

dominant sequences

redundancy

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.