Year: 2012
CAM-Net Digest, Vol. 9 (2012), Iss. 13 : p. 8
Abstract
今年1月，4名麻省理工学院研究人员向人们展示了一种计算机科学中最重要算法的替代品。迪娜·凯塔比、海赛姆·哈桑尼、彼得·因迪克、 埃里克·普赖斯创建出一种进行傅里叶变换的更快方法。傅里叶变换是一种处理数据流的数学技术，其已成为Wi-Fi路由器、数字医疗影像和4G蜂窝网络的运行基础。
傅里叶变换的历史可追溯到19世纪，其原理是，任何信号，如录音信号，可表示为不同频率和振幅的正弦和余弦波的集合总和。对波的集合处理起来相对容易，例如，可对录音信号进行压缩或对噪音进行抑制。在20世纪60年代中期，又发展出了一种被称为快速傅里叶变换（FFT）的对计算机友好的算法。快速傅里叶变换的威力到底有多大， 你只需比较一下MP3文件及其未压缩格式的大小即可。
麻省创建的新算法，称为稀疏傅里叶变换（SFT），其对数据流的处理要比快速傅里叶变换快上10倍至100倍。这种加速的达成，是基于我们最为关注的是信息的有意义部分：音乐不是随机噪声。这些有意义的信号通常只是一个信号可采值的一小部分，用技术术语来说，这个信息是“稀疏”的。因为稀疏傅里叶变换算法无意处理所有可能的数据流，它采集的是某些“捷径”（最有意义）部分，而非其他可用部分。从理论上讲，一个仅处理稀疏信号的算法，要比快速傅里叶变换更具局限性。但是，新算法的共同发明人、电气工程和计算机科学教授凯塔比指出，“稀疏无处不在，它存在于自然中，存在于视频信号中， 也存在于音频信号中”。
更快的变换意味着处理一定量的信息只需更少的电力，这对于对电力要求苛刻的智能手机等移动多媒体设备来说，不啻为一种福音。或者说，使用相同的电量，工程师们可考虑做更多快速傅里叶变换算法不可能达成的计算需求。例如，今天的互联网骨干网和路由器实际上只能读取或处理穿越其间的数字河流中的涓涓细流，而稀疏傅里叶变换可使研究人员以每秒数十亿次的速度更为详细地研究数据洪流。
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: Chinese
DOI: https://doi.org/2012-CAM-15980
CAM-Net Digest, Vol. 9 (2012), Iss. 13 : p. 8
Published online: 2012-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 1