A New Recursive Algorithm for Universal Coding of Integers
Journal Title: Journal of Information Systems and Telecommunication - Year 2015, Vol 3, Issue 1
Abstract
In this paper, we aim to encode the set of all positive integers so that the codewords not only be uniquely decodable but also be an instantaneous set of binary sequences. Elias introduces three recursive algorithms for universal coding of positive integers where each codeword contains binary representation of the integer plus an attachment portion that gives some information about the first part [1]. On the other hand, Fibonacci coding which is based on Fibonacci numbers is also introduced by Apostolico and Fraenkel for coding of integers [2]. In this paper, we propose a new lossless recursive algorithm for universal coding of positive integers based on both recursive algorithms and Fibonacci coding scheme without using any knowledge about the source statistics [3].The coding schemes which don’t use the source statistics is called universal coding, in these universal coding schemes we should use a universal decoding scheme in the receiver side of communication system. All of these encoding and decoding schemes assign binary streams to positive integers and conversely, without any need of use to probability masses over positive integers. We show that if we use Fibonacci coding in the first part of each codeword we can achieve shorter expected codeword length than Elias Omega code. In addition, our proposed algorithm has low complexity of encoding and decoding procedures.
Authors and Affiliations
Mehdi Nangir, Hamid Behroozi, Mohammad Reza Aref
Keywords
Related Articles
- EP ID EP184733
- DOI 10.7508/jist.2015.01.001
- Views 87
- Downloads 0
The Surfer Model with a Hybrid Approach to Ranking the Web Pages
Users who seek results pertaining to their queries are at the first place. To meet users’ needs, thousands of webpages must be ranked. This requires an efficient algorithm to place the relevant webpages at first ranks. R...
A new Sparse Coding Approach for Human Face and Action Recognition
Sparse coding is an unsupervised method which learns a set of over-complete bases to represent data such as image, video and etc. In the cases where we have some similar images from the different classes, using the spars...
Automatic Construction of Domain Ontology Using Wikipedia and Enhancing it by Google Search Engine
The foundation of the Semantic Web are ontologies. Ontologies play the main role in the exchange of information and development of the Lexical Web to the Semantic Web. Manual construction of ontologies is time-consuming,...
A New Approach to Overcome the Count to Infinity Problem in DVR Protocol Based on HMM Modelling
Due to low complexity, power and bandwidth saving Distance Vector Routing has been introduced as one of the most popular dynamic routing protocol. However, this protocol has a serious drawback in practice called Count To...
Crisis management using spatial query processing in wireless sensor networks
Natural disasters are an inevitable part of the world that we inhabit. Human casualties and financial losses are concomitants of these natural disasters. However, by an efficient crisis management program, we can minimiz...