SIA OpenIR  > 机器人学研究室
一种基二快速Hadamard变换的并行算法
其他题名Parallelized Algorithm for Radix-2 Fast Hadamard Transform
秦书嘉; 缪磊; 崔龙; 席宁
作者部门机器人学研究室
关键词单像素相机 压缩感知 Hadamard变换 并行算法
发表期刊信息与控制
ISSN1002-0411
2016
卷号45期号:6页码:707-712, 721
收录类别CSCD
CSCD记录号CSCD:5911014
产权排序1
资助机构国家自然科学基金资助项目(61102014) ; 国际热核聚变实验堆(ITER)计划资助项目(2012GB102005)
摘要快速Hadamard变换被广泛应用于信号与图像处理、通信系统、数字逻辑等领域中.当问题规模非常大时,快速Hadamard变换有可能不能满足计算时间的要求;这种情况下,算法并行化是一种行之有效的手段.本文以单像素相机的压缩感知图像复原为应用背景,利用基二快速Hadamard变换与快速傅里叶变换的结构相似性,提出一种通用的基二快速Hadamard变换的任务级并行算法,并用构造方式证明了该并行算法与串行算法计算结果之间的等价性.仿真表明对于小于220向量长度的问题规模以及并行子任务数少于210的情况,该并行算法对比串行算法的数值计算结果的欧氏距离平方误差小于10-18,佐证了并行算法的正确性。在PC平台通过多核CPU上POSIX线程实现的实验表明:在该特定平台和特定配置上对于220至225向量长度的问题规模并行计算加速比为1.33~1.42,证明了文中提出方法的可行性和有效性。
其他摘要The fast Hadamard transform (FHT) has extensive application in signal and image processing, communication systems, digital logic, and other fields. Faced with problems at a very large scale, the serial algorithms of the FHT are probably unable to meet the calculation time requirements. In this situation, parallelizing the algorithm is an effective solution. Based on compressed sensing image reconstruction of a single-pixel camera and by using the structural similarity between the FHT and the fast Fourier transform, we propose a task-level parallel algorithm for the general radix-2 FHT. We prove equivalence between the results of the serial and parallel algorithms by construction. The simulation result shows that for a problem scale with an input vector length less than 220 and subtasks fewer than 210, the squared Euclidean distance error between the serial and parallel algorithms is less than 10-18, which substantiates the correctness of the parallel algorithm. An experiment using POSIX threads on a PC with a multicore CPU demonstrates that on a specific platform and under a specific configuration the observed speedup is 1.33~1.42 for problem scales with an input vector length from 220 to 225. This implies the feasibility and effectiveness of the proposed method.
语种中文
引用统计
文献类型期刊论文
条目标识符http://ir.sia.cn/handle/173321/19777
专题机器人学研究室
通讯作者秦书嘉
作者单位1.中国科学院沈阳自动化研究所
2.中国科学院大学
3.密歇根州立大学
推荐引用方式
GB/T 7714
秦书嘉,缪磊,崔龙,等. 一种基二快速Hadamard变换的并行算法[J]. 信息与控制,2016,45(6):707-712, 721.
APA 秦书嘉,缪磊,崔龙,&席宁.(2016).一种基二快速Hadamard变换的并行算法.信息与控制,45(6),707-712, 721.
MLA 秦书嘉,et al."一种基二快速Hadamard变换的并行算法".信息与控制 45.6(2016):707-712, 721.
条目包含的文件 下载所有文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
一种基二快速Hadamard变换的并行算(1721KB)期刊论文作者接受稿开放获取ODC PDDL浏览 下载
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[秦书嘉]的文章
[缪磊]的文章
[崔龙]的文章
百度学术
百度学术中相似的文章
[秦书嘉]的文章
[缪磊]的文章
[崔龙]的文章
必应学术
必应学术中相似的文章
[秦书嘉]的文章
[缪磊]的文章
[崔龙]的文章
相关权益政策
暂无数据
收藏/分享
文件名: 一种基二快速Hadamard变换的并行算法.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。