检索结果-内蒙古大学图书馆

Energy-Efficient prefix-free codes for Wireless Nano-Sensor Networks Using OOK Modulation

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2014年第5期13卷 2670-2682页

作者： Chi, Kaikai Zhu, Yi-hua Jiang, Xiaohong Leung, Victor C. M. Zhejiang Univ Technol Sch Comp Sci & Technol Hangzhou 310023 Zhejiang Peoples R China Future Univ Hakodate Sch Syst Informat Sci Hakodate Hokkaido 0418655 Japan Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

Wireless nano-sensor networks (WNSNs), which consist of nano-sensors a few hundred nanometers in size with the capability to detect and sense new types of events in nano-scale, are promising for many unique applications such as air pollution surveillance. The nano-sensors of WNSNs are highly energy-constrained, which makes it essential to develop energy-efficient communication techniques in such networks. In this paper, we focus on WNSNs employing on-off keying (OOK) modulation, whereby transmission energy minimization corresponds to the minimization of average codeword weight (ACW). We formulate an integer nonlinear programming problem to construct prefix-free codes with minimum ACW under the constraint of average codeword length (ACL) so as to minimize the transmission energy consumption while guaranteeing the throughput larger than a preset desired value. In addition, two efficient algorithms, called binary tree based weight decreasing (BT-WD) algorithm and binary tree based length decreasing (BT-LD) algorithm, are presented for constructing low-ACW prefix-free codes. The effectiveness of the proposed algorithms is verified through simulations and comparisons with the exhaustive search method. Compared with the available fixed-length low-weight codes, the designed prefix-free variable-length codes allow us to not only control the throughput more flexibly but also achieve lower transmission energy consumption in the scenarios with low or medium bit error rates.

关键词： Wireless nano-sensor network OOK modulation prefix-free code transmission energy saving

来源：评论

学校读者我要写书评

暂无评论

Optimal codes With Limited Kraft Sum

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第11期61卷 6385-6394页

作者： Aghajan, Adel Khosravifard, Mohammadali Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran

The well-known Huffman algorithm is an elegant approach to solve the basic problem of finding the optimal code among those with Kraft sums smaller than or equal to 1. In this paper, an extended problem is investigated, where the Kraft sum of the usable codes is limited to a given real number gamma, 0 < gamma < 1. Unlike the case gamma = 1 (i.e., Huffman coding), for gamma < 1, the Kraft sum of the optimal code is not necessarily equal to gamma. However, we show that the Kraft sum of the optimal code lies in a finite set of rational numbers which depend on the value of gamma. This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to gamma', where gamma' has a finite binary representation and 0 < gamma' < 1. To do so, the set of N-tuple codelength vectors with a specific Kraft sum gamma' is characterized. The binary representation of. plays a fundamental role in all problems that arise for gamma < 1.

关键词： prefix-free code Kraft sum optimal codelength vector Huffman code fix-free code

来源：评论

学校读者我要写书评

暂无评论

Efficient construction of minimum-redundancy codes for large alphabets

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1998年第4期44卷 1650-1657页

作者： Moffat, A Turpin, A Univ Melbourne Dept Comp Sci Parkville Vic 3052 Australia

We consider the problem of calculating minimum-redundancy codes for alphabets in which there is significant repetition of symbol weights. On a sorted-by-weight alphabet of n symbols and r distinct symbol weights we show that a minimum-redundancy prefix code can be constructed in O (r + rlog(n/r)) time, and that a minimum-redundancy L-bit length-limited prefix code can be constructed in O(Lr + Lrlog(n/r)) time. When I is small relative to n-which is necessarily the case for most practical coding problems on large alphabets-these bounds represent a substantial improvement upon the best previous algorithms for these two problems, which consumed O(n) time and O(nL) time, respectively. The improved algorithms are also space-efficient.

关键词： adaptive algorithm Huffman code length-limited code minimum-redundancy code package-merge algorithm prefix-free code text compression

来源：评论

学校读者我要写书评

暂无评论

On the construction of prefix-free and fix-free codes with specified codeword compositions

引用

DISCRETE APPLIED MATHEMATICS 2011年第18期159卷 2269-2275页

作者： Kakhbod, Ali Zadimoghaddam, Morteza Univ Michigan Dept Elect Engn & Comp Sci EECS Ann Arbor MI 48109 USA MIT Comp Sci & Artificial Intelligence Lab CSIL Cambridge MA 02139 USA

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Information theory Algorithm Approximation algorithm prefix-free code Fix-free code

来源：评论

学校读者我要写书评

暂无评论

A Simple Recursive Shannon code

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2012年第2期60卷 295-299页

作者： Khosravifard, M. Narimani, H. Gulliver, T. A. Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Univ Victoria Dept Elect & Comp Engn STN CSC Victoria BC V8W 3P6 Canada

The Shannon code is a very simple suboptimal scheme for computing prefix-free codelengths for a given memoryless source. A recursive version of the well-known Shannon code (RSh) is investigated in this paper. It has a redundancy which never exceeds that of the Shannon code. Unlike the Huffman code, the RSh code and its variations can be directly applied to sources with an infinitely countable alphabet. The average redundancy, taken over the set of all n-tuple distributions, is considered as a criterion for code comparisons. For n > 40, the average redundancy is approximately 0.14 bits for the RSh code, compared to approximately 0.5 and 0.03 bits for the Shannon and Huffman codes, respectively. For large n, a constrained version of the RSh code, called CRSh, has an average redundancy of only 0.07 bits for unsorted symbol probabilities. If the symbol probabilities are sorted in descending order, then a very simple modification of the RSh algorithm results in a code which is near-optimal from the average redundancy point of view.

关键词： Average redundancy Huffman code infinitely countable alphabet prefix-free code Shannon code Kraft sum

来源：评论

学校读者我要写书评

暂无评论

In-place calculation of minimum-redundancy codes 4th

In-place calculation of minimum-redundancy codes

引用

4th International Workshop on Algorithms and Data Structures (WADS 95)

作者： Moffat, A Katajainen, J UNIV COPENHAGEN DEPT COMP SCI DK-2100 COPENHAGEN DENMARK

ISBN: (纸本)3540602208

The optimal prefix-free code problem is to determine, for a given array p = [p(i) \i is an element of {1...n}] of n weights, an integer array I = [l(i) \i is an element of (1...n)] of n codeword lengths such that Sigma(i=1)(n) 2(-li) less than or equal to 1 and Sigma(i=1)(n) p(i)l(i) is minimized. Huffman's famous greedy algorithm solves this problem in O(n log n) time, if p is unsorted;and can be implemented to. execute in O(n) time, if the input array p is sorted. Here we consider the space requirements of the greedy method. We show that if p is sorted then it is possible to calculate the array 1 in-place, with l(i) overwriting pi, in O(n) time and using O(1) additional space. The new implementation leads directly to an O(n log n)-time and n + O(1) words of extra space implementation for the case when p is not sorted. The proposed method is simple to implement and executes quickly.

关键词： prefix-free code Huffman code in-place algorithm data compression

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Calculating Minimum Redundancy prefix codes with Unsorted Alphabet 9

A Fast Algorithm for Calculating Minimum Redundancy Prefix C...

引用

9th International Conference on Communications and Networking in China (CHINACOM 2014)

作者： Tai, Yupeng Wang, Haibin Chinese Acad Sci Inst Acoust State Key Lab Acoust Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

ISBN: (纸本)9781479959709

Minimum redundancy coding (also known as Huffman code) is one of the most well-known algorithm of data compression. Many efforts have been made to improve the efficiency of it. Most of them are based on the assumption that the input alphabet has been already sorted. In this paper, we propose an algorithm of calculating the minimum-redundancy codes directly with unsorted alphabet. It consumes only O(nlog(n/k)) time in the worst cases, where n is the alphabet size and k is the longest codeword length. It is fast because only a part of the symbols requires to be sorted before the final minimum redundancy code is generated. The theoretical analysis and numerical simulation results show that this algorithm achieves a substantial improvement upon the best previous O(nlogn) algorithms for this problem.

关键词： Huffman coding Lossless data compression Minimum redundancy code prefix-free code

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：