教育资源为主的文档平台

当前位置: 查字典文档网> 所有文档分类> 农林牧渔> 林学> SymmetricRVLC

SymmetricRVLC

上传者:林密
|
上传时间:2015-04-26
|
次下载

SymmetricRVLC

Construction of Symmetrical Reversible Variable Length

Codes Using Backtracking

Hsien-Wen Tseng and Chin-Chen Chang

Department of Computer Science and Information Engineering National Chung Cheng University, Chiayi 621, Taiwan, R.O.C.

E-mail: {hwtseng,ccc}@http://wendang.chazidian.comu.edu.tw

Correspondence address:

Chin-Chen Chang

Professor

Department of Computer Science and Information Engineering National Chung Cheng University

Chiayi 621, Taiwan, R.O.C.

E-mail: ccc@http://wendang.chazidian.comu.edu.tw

TEL: 886-5-2720411 ext. 33100

FAX: 886-5-2720859

Construction of Symmetrical Reversible Variable Length

Codes Using Backtracking

Hsien-Wen Tseng and Chin-Chen Chang

Department of Computer Science and Information Engineering, National Chung Cheng University, Chaiyi, Taiwan 621, R.O.C.

E-mail: {hwtseng,ccc}@http://wendang.chazidian.comu.edu.tw

Abstract

Many coding standards, such as JPEG, H.261, H.263, MPEG-1, MPEG-2, use variable length codes (VLC) as their entropy coding strategy. However, VLC have a big drawback when transmitting over a noisy channel. This drawback is an error propagation problem. For this reason, reversible variable length codes (RVLC) have been used to enhance the error resilient capabilities of VLC. This paper presents a new algorithm using backtracking that can construct symmetrical RVLC. Depth first node generation is applied to this algorithm and bounding function is used to replace nodes with their symmetrical children. The experimental results show that our algorithm can generate better codes than those of previous methods. In addition, our proposed algorithm provides a shorter maximum code length. The shorter maximum code length can usually achieve more efficient decoding.

Keywords: reversible variable length codes (RLVC), Huffman Code, H.263, MPEG-4,

JPEG-2000, error resilience

1

1. Introduction

Traditionally, variable length codes (VLC) have been used as entropy coding in many image coding standards (JPEG [1]) and video coding standards (H.261 [2], H.263 [3], MPEG-1 [4], MPEG-2 [5]). An example of VLC is the Huffman Code, which is well known to give the optimal code with minimum redundancy. But in recent years, more and more new standards such as JPEG-2000 [6], H.263+ [7], H.263++ [8], MPEG-4 [9] have adopted reversible variable length codes (RVLC), because VLC have the problem of error propagation. Even one single bit error will cause many following codewords to be misinterpreted. This is a big problem in an error-prone environment. In order to enhance the error resilient capabilities of VLC, Fraenkel and Klein [10] presented the bidirectional Huffman coding in 1990, Takishima et al. [11] proposed the RVLC for avoiding continuous errors in 1995. RVLC are not only a prefix code but also a suffix code. A code is called a prefix code namely if no codeword is a prefix of any other codewords. Conversely, a code is called a suffix code namely if no codeword is a suffix of any other codewords. Therefore, RVLC can be decoded both in the forward and backward directions so as to provide error resilient transmission over a noisy channel.

RVLC are very useful because they provide the capability of error resiliency and because they can be decoded in two directions. Except for the adoption in many 2

standards as we mentioned above, RVLC can also be applied to speed up searching of encoded data. For example, we can begin by searching the encoded data in the forward and backward directions at the same time. This can significantly reduce the search time and this kind of search is impossible when using VLC.

There are two types of RVLC, one is symmetrical and the other is asymmetrical. Symmetrical RVLC share the same code table when decoding both in the forward and backward directions, because the code is symmetrical. But two types of code tables are necessary for asymmetrical RVLC. For this reason, symmetrical RVLC is simpler than asymmetrical RVLC; meanwhile, the memory requirement of symmetrical RVLC is less than that of asymmetrical RVLC. However, asymmetrical RVLC always provides better efficiency than symmetrical RVLC because a more flexible code selection is allowed.

In this paper, we will concentrate on symmetrical RVLC and devise a new method of constructing symmetrical RVLC. The remainder of this paper is organized as follows. Section 2 introduces the related works. Section 3 explains the details of our proposed algorithm. Experimental results are presented in Section 4. The conclusions are drawn in Section 5.

3

2. Previous Works

In 1995, Takishima et al. [11] proposed a coding scheme to generate RVLC. It starts from a non-reversible VLC, such as Huffman Code, and converts the code by a top-down scheme into a symmetrical RVLC. Recently, Tsai and Wu [12, 13] proposed a more efficient symmetrical RVLC construction algorithm that is based on Takishima et al.’s algorithm. This algorithm also starts from a list of given Huffman Code, but uses a new codeword selection mechanism to select candidate codewords in each level. We first explain some terms in relation to their construction algorithms, and then briefly summarize their algorithms.

The number of symmetrical codewords on a full binary tree of level L is given as follows:

mo(L) = 2└(L+1)/2┘,

where └x┘ is the largest integer less than or equal to x. Let p(L) denote the total number of symmetrical codewords at level L unavailable due to the violation of the prefix condition. The calculation of p(L) can be found in [11]. Hence, the number of available symmetrical codewords, m(L), at level L is calculated as follows:

m(L) = mo(L) - p(L).

If we ignore the codeword selection mechanism in both Takishima et al.’s algorithm and Tsai and Wu’s algorithms, then their algorithms can be summarized as 4

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注

全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考英语 2014词汇考情分析及对策
考研英语_常用词组大全
2012年考研 英语必备——考研英语全部下载地址 (5)
2016考研 新闻传播学院校推荐上海大学
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 写作范文100篇节选
2016考研经济学 国际金融学问答题十
全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考英语 2013年英语(二)大纲增减词汇
2016考研经济学 国际金融学问答题九
2016考研经济学 国际金融学问答题六
2013年暨南大学生物化学和普通生物学考研真题回忆
2016考研经济学 国际金融学问答题十二
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 数学轻松通关
2016考研经济学 国际金融学问答题五
2016考研经济学 国际金融学问答题二
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 数学365题节选
2014年吉林财经大学mba招生简章
2015年广东财经大学mba招生简章-中公管理人
美国留学MPA项目申请研究
中国MPA教育_十年总结与未来展望
2016考研经济学 国际金融学问答题四
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 英语语法宝典
2014年辽宁石油化工大学MBA招生简章
人大外国语学院050201-英语语言文学报录比录取名单专业解析
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 英译汉资料
(OK)2009年考研英语真题
2016考研 新闻传播学院校推荐武汉大学
重庆大学mba招生简章
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 英语知识运用高分必备
2016全国硕士研究生入学统一考试MBA、MPA、MPAcc管理类专业学位联考 阅读理解高分必备
2016考研经济学 国际金融学计算题一

网友关注视频

19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
外研版英语七年级下册module1unit3名词性物主代词讲解
二年级下册数学第二课
冀教版小学英语五年级下册lesson2教学视频(2)
沪教版牛津小学英语(深圳用)五年级下册 Unit 1
冀教版小学数学二年级下册1
3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
沪教版牛津小学英语(深圳用) 五年级下册 Unit 7
化学九年级下册全册同步 人教版 第25集 生活中常见的盐(二)
沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
化学九年级下册全册同步 人教版 第18集 常见的酸和碱(二)
每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
《小学数学二年级下册》第二单元测试题讲解
沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
沪教版八年级下册数学练习册21.4(1)无理方程P18
沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594
冀教版英语五年级下册第二课课程解读
第8课 对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
外研版英语七年级下册module3 unit2第一课时
七年级英语下册 上海牛津版 Unit3
北师大版数学 四年级下册 第三单元 第二节 小数点搬家
苏科版数学七年级下册7.2《探索平行线的性质》
沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
沪教版八年级下册数学练习册21.3(3)分式方程P17
北师大版小学数学四年级下册第15课小数乘小数一
冀教版英语三年级下册第二课
30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市