027
DSP快速相关算法研究样本
(样本只提供该系统的基本情况介绍,若需要完整的设计和论文,建议您购买本系统,凡是购买本站系统的,本站均根据您的要求,把系统上的开发信息,题目等修改成符合您的要求)
本系统开发工具：单片机/汇编
本设计包含内容：源代码+毕业论文+开题报告+答辩稿
论文大概：
无损测漏DSP快速相关算法设计
摘要：为了能够找到户外管道泄漏的位置以减少资源浪费和减小环境污染,本文介绍了一种用于管道检漏的设计方法。利用互相关原理,将两个传感器中测到的声音信号进行互相关运算,就可以得到漏点的位置。由于在时域进行互相关运算非常费时,我们在这里就采用了一种新的算法--快速相关算法,这种算法能大大地提高运算速度。快速相关算法是根据两函数相乘时时域中的卷积相当于频域中的乘积这一原理来设计的。具体的实现过程为先将两组实域信号分别用傅立叶变换变换到频域,然后在频域中将他们相乘,再把结果用傅立叶反变换变换到时域中。
本实验利用MATLAB强大的信号模拟能力,模拟出两传感器中测得的声音信号,即管道泄漏信号和环境嘈声的叠加信号,再用汇编语言编制相关算法程序,用实验验证了相关检漏原理。
本文的重点是第二和第三章,分别介绍了管道检漏、快速相关算法、DSP芯片的特点和本实验的具体实现方法即相关算法程序的编写。
关键词：泄漏检测,快速相关运算,FFT算法
APPLICATION OF FAST CORRELATION METHOD FOR
PIPELINE LEAK
DETECTION
To find out the position of the leak in outdoor pipe to
reduce the waste of resources and the pollution of the
environment,in this article we introduced a kind of design method
that used for leak detection in pipes.Make use of cross-correlation
theory,
make two signals measure from sensors pass
cross-correlated operation,we can get the position of the
leak.Because at the real area it is waste of time to perform the
cross-correlated operation,we adopted a new kind of operation--fast
correlated operation, can raise the speed of the operation
consumedly.The principle of the fast correlated operation is that
the book accumulate of two functions in real area is equality to
multiply of two functions in frequency area.First use the fourior
transformation make the two signals from real area to frequency
area,and then multiply each other,and at last use the fourior
anti-transformation make the result from frequency area to
real area.
The principle make use of the MATLAB’s
comprehensive signal simulate capacity, imitate the signal of
leaking and environment noise examinate from two sensors. A
cross-correlation algorithm was also programmed and the correlation
principle for pipeline leak detection is proved to be effective by
experiments.
This article place emphasis from the second
chapter to the third. It also introduce leak detection in pipe ,fast
cross-correlation algorithm ,DSP and system software design
separately.
Key Words: leak detection; fast correlation analysis;
FFT
目
录
中文摘要 3
英文摘要 4
目录 5
图列 7
第一章
绪论 8
第二章
背景知识简介 10
2.1
管道检漏 12
2.1.1
一些主要的检漏方法 12
2.1.2
我国管道检漏发展的现状和未来 14
2.2
相关算法 16
2.2.1
相关函数的概念 16
2.2.2
相关检漏原理 17
2.2.3
快速相关原理.......................................
17
2.2.4
漏点定位算法 21
2.3
相关硬件基础知识 22
2.3.1
DSP芯片的特点和基本结构 22
2.3.2
DSP芯片的现状和发展方向 25
第三章
相关算法的实现 30
3.1
声音信号的时频域变换.....................................
31
3.2
两组频域信号相乘.........................................
32
3.3
反FFT变换................................................
33
3.4
求时间间隔...............................................
34
第四章
系统联调 35
第五章
结果分析 38
第六章
总结......................................................39
附录
算法程序 40
参考文献 57
致谢 58
图
列
图2-1 蝶形运算.......................................22
图2-2 N=8的按时间抽取FFT信号流图.....................24
图2-3 相关检漏技术的工作原理图........................25
图4-1
第一个模拟信号.................................36
图4-2
第二个模拟信号.................................37
图4-3
两组信号的相关结果.............................37
1 第一章
绪论
一、研究目的
随着现代社会的发展,管道运输在现代化建设和人们的生活中起着越来越重要的作用。但是由于自然和人为因素造成的管道泄漏不仅污染了环境,还严重浪费了资源,因此,管道泄漏检测技术也相应地得到更多的关注。而研究的目的是为了能够找到泄漏的位置以减少资源浪费和减小环境污染。
二、研究历史及现状
水是宝贵的自然资源。由于淡水资源的贫乏和高昂的制水成本,世界各国尤其是发达国家都非常重视供水节水的管理工作。很早就开展了漏损控制技术及设备的研究、开发工作。80年代初,英、美、法、日相继开发成功了相关检漏仪,90年代初又研究了利用水传声的相关检漏仪,提高了检漏的正确性。美国、日本在80年代中期还开发了探地雷达,利用电磁波对漏水情况进行检漏,并以图象显示漏水孔周围的情况,实现对漏水点的精确定位。由于西方国家的经济实力,重视程度和技术水平等方面的优势,根据有关资料统计,英国的管网漏失率为18.69%,美国为8%以下,日本10%以下,法国9.5%,德国4.9%,其漏失率远低于亚洲国家。
我国自1897年旅顺建成第一个供水设施,已有100多年的历史,各地供水企业在技术管理上积累了丰富的经验。改革开放以来,各地水司重视运用先进管理手段,加大对管网管理投入,在提高供水效率上取得显著的成效。但由于城市基础设施欠账太多,供水设备的更新,技术水平提高缓慢,加之管理体制落后于不断发展的形势,使管网漏损率均未达到《城市供水2000年技术进步发展规划》所规定的目标,大多数城市供水漏失率多在25--30%。与发达国家比较还有很大的差距。多年来,各地水司以管线事故抢修为主,漏水调查为辅,多数单位管线处于被动检漏状况,效果不好。随着国内市场环境的改善,国家有关用水节水政策措施的颁布,漏损控制逐步受到各水司的重视,相继引进了不少先进的漏水检测设备,如美国、日本、英国、德国等国家的听漏仪、相关检漏仪、探地雷达等。各大中型水司根据实际情况也成立了相应的检漏队伍,取得了一定的效果。但从总体看与发达国家比较还有相当大的差距,普遍存在着检漏技术人员较少、专业技术素质差、对先进设备的使用方法理解不深,更有甚者,有的水司将先进设备闲置,无人使用,造成很大浪费。由此可见,我国供水漏损控制工作是任重道远,要达到10%以内漏控目标还有相当长的一段路要走。
对于管道泄漏检测技术的研究近年来不断有新的发展,检漏方法也由最初的听漏发展到各式各样的基于现代信号处理和自动化装置的检漏,主要有音听检漏法、相关检漏法、漏水声自动记录监测法、分区检漏法、区域泄漏普查系统法,其中相关检漏法是当前比较先进、有效的一种检漏方法。本实验就是利用相关检漏原理来实现实现泄漏的检测和定位的。
三、研究方法与系统描述
本次实验的研究内容是对于管道传输中两相邻传感器所得到的声音信号,利用相关原理来确定泄漏的位置,用MATLAB进行水管漏水信号及其他嘈声的图象重建。这次实验是利用MATLAB强大的信号模拟能力,模拟出管道泄漏信号和环境嘈声,然后用DSP编制相关算法程序确定漏点的位置,来验证相关检漏原理。
四、论文内容概述
论文大概可分为三部分：
第一部分偏重于各种检漏方法的介绍,以及国内外检漏技术的现状和发展
第二部分偏重于课题中应用的软件和硬件基础,论文简单介绍了DSP芯片的特点、现状和发展方向。
第三部分着重于对用MATLAB真实模拟出的漏点信号和环境嘈声,通过利用DSP相关算法编制程序,来实现漏点的定位,验证
的正确性。
2 第二章
背景知识简介
２.1 管道检漏
随着现代社会的发展,管道运输在现代化建设和人们的生活中起着越来越重要的作用。但是由于自然和人为因素造成的管道泄漏不仅污染了环境,还严重浪费了资源,因此,管道泄漏检测技术也相应地得到更多的关注。
对于管道泄漏检测技术的研究近年来不断有新的发展,检漏方法也由最初的听漏发展到各式各样的基于现代信号处理和自动化装置的检漏,其中相关检漏法是当前比较先进、有效的一种检漏方法。
1960年英国水研究中心最先开发了相关检漏仪,随后法国、日本等国也相继研制了相关检漏仪,自20世纪80年代,国外开始研究用互相关法检测水管泄漏,并取得良好的效果。如德国,其最长的试验距离是3.5km,漏孔检测的可靠度高于90％。对于80％以上检测到的漏孔,其定位的精确度达±l
m。近年来,国外在这方面进行了进一步的研究,如加拿大研究人员对塑料水管漏孔检测的研究,该方法主要利用流体通过漏孔时的流动噪声,通过两个传感器接收该信号,漏孔位置的信息是根据信号到达两个接收器的传播时间之差进行判断的,所采用的传感器是水听器或加速度计。近来,我们研发了相关检漏仪,依据相关检测原理它不仅可以用于自来水检漏,也可以用于煤气、石油、天然气等管道的泄漏检测。
2.1.1
一些主要的检漏方法
音听检漏法
音听检漏法分为阀栓听音和地面听音两种,前者用于查找漏水的线索和范围,简称漏点预定位；后者用于确定漏水点位置,简称漏点精确定位。
漏点预定位是指听漏棒、电子听漏仪或噪声自动记录仪来探测供水管道漏水范围的方法,根据使用仪器的不同,操作的方法也不尽相同,到目前止,实用的,有效诉,成本低的预定位技术主要有阀栓听音法,当然类同于GPL99、GPL95,包括PARMALOGA等方法,虽然也能用当其综合效果不好,而且成本高。
（1）阀栓听音法
阀栓跌间法是用听漏棒或电子放大听漏仪直接在管道暴露点（如消火检、阀门及暴露的管道等）听测由漏水点产生的漏水声,从而确定漏水管道,缩小漏水检测范围。金属管道漏水声频率一般在300～2500Hz之间,而非金属管道漏水声频率在100～700Hz之间。听测点距漏水点位置越近,听测到漏水声越大；反之,越小。
（2）地面听音法
当通过预定位方法确定漏水管段后,用电子放大听漏仪在地面听测地下管道的漏水点,并进行精确定位。听测方式为沿着漏水管道走向以一定间距逐点听测比较,当地面拾音器靠近漏水点时,听测到的漏水声越强,在漏水点在上方达到最大。
拾音器放置间距与管道材质有关,一般说来,金属管道间距为1～2米,而非金属管道为0.5～1米,水泥路面间距为1～2米,土路面为0.5米。
相关检漏法
相关检漏法是第三代技术,是世界上包括中国用的最多的先进、有效的一种精确确定漏点的检漏方法,特别适用于环境干扰噪声大、管道埋设深或不适宜用地面听漏法的区域。用相关仪可快速准确地测出地下管道漏水点的准确位置。
一套完整的相关仪主要是由一台相关仪主机（无线电接收机和微处理器等组成）、二台无线电发射机（带前置放大器）和二个高灵敏度振动传感器组成。其工作原理为：当管道漏水时,在漏口处会产生漏水声波,并沿管道向远方传播,当把传感器放在管道或连接件的不同位置时,相关仪主机可测出由漏口产生的漏水声波传播到不同传感器的时间差Td,只要给定两个传感器之间管道的实际长度L和声波在该管道的传播速度V,漏水点的位置Lx就可按下式计算出来。
Lx=（L-V×Td）K2
式中的V取决于管材、管径和管道中的介质,单位为mKms,并全部存入相关仪主机中。
相关仪也经历了从低到高性能的发展过程,现代高性能的相关仪具有时间域和频率域（FFT）时实相关处理功能,同是具有高分辨率（0.1ms）、频谱分析及陷波、自动滤波、测管道声速和距离等功能,如德国SEBA的相关仪SEBADYNACORR,新型相关仪CORRELUXPL都具备这些功能。
漏水声自动记录监测法
以德国SEBA泄漏噪声自动记录仪为例,德国SEBA的GPL99是由多台数据记录仪和一台控制器组成的整体化声波接收系统。当装有专用软件的计算机对数据记录仪进行编程后,只要将记录仪放在管网的不同位置,如消火检、阀门及其他管道暴露点等,按预设时间（如深义2∶00～4∶00）同时自动开K关记录仪,可记录管道各处的漏水声信号,该信号经数字化后自动存入记录仪中,并通过专用软件在计算机上进行处理,从而快速探测装有记录仪的管网区域内是否存在漏水。人耳通常能听到30dB以上的漏水声,而泄漏噪声自动记录仪可探测到10dB以上的漏水声。
数据记录仪放置距离视管材、管径等情况而定,一般说来,金属管道可选200～400米的间距,非金属管道应在100之内的间距。
判别漏水的依据是：每个漏水点会产生一个持续的漏水声,根据记录仪记录的噪声强度和频繁度来判断在记录仪附近是否有漏水的存在,计算机软件自动识别并作二维或三维图。
分区检漏法
在管道听测漏水声时,一般说来,漏点大产生的漏水声比漏点小产生的漏水声要大一声,但漏点大到一定程度漏水声反而小了,因此,我们不能认为听到的漏水声大,其漏水量就大,有时实际情况正姨相反。分区检漏法使漏水点按漏水量大小分烦恼成为可能,并因此能做到：控制大的漏水点并首先被排除掉。
每个管网中都存在着多处小的漏水点和几处大的漏水点,经验表明,漏水总量的80%%是由20%%大漏水点造成的。因此,尽快排除大的漏水点才能更好地控制漏耗,降低漏失率,同时,分区检漏可大大提高检漏速度。
所谓分区检漏法是：是主要应用流量计测漏。首先关闭与该区相连的阀门,使该区与其他区分离,然后用一条消防水带一端接在被隔离区的消火栓上,另一端接到流量计的测试装置上；再将第二条消防水带一端接在其他区的消火栓上,另一端接流量计的测试装置上,最后开启消火栓,向被隔离区管网供水。借助于流量计,测量该区的流量,可得到某一压力下的漏水量。如果有漏水,可通过依此关K开该区的阀门,可发现哪一段管道漏水。德国SEBA的流量计TDM10-60正是为分区检漏而设计的。
采用分区检漏法检漏的优点：
（1）能迅速排除大的漏水点；
（2）系统地测试,可进行管网状况分析；
（3）用所测流量与正常流量比较,可以发现漏水的早期迹象。
其不足之处就是可能会影响部分居民用水。另它装载在车上操作起来方便。
区域泄漏普查系统法
区域泄漏普查系统法是一种目前最新型的,经过实践证明实用有效的一种方法。它在方法和技术上主要是集了上述2,3,4三种方法的优点,并应用了目前声学,电子,软件,通讯,信号处理,数字化处理等综合技术。
区域泄漏普查系统（以下简称多探头相关仪）,由英国BADCOM公司研究生产,埃德尔集团自主开发中文操作界面,是目前世界上独一无二的：集漏水预定位和精定位于一体,仅一次检测即可完成一定区域内的漏点预定位和漏点精定位的仪器,而且对管道属性要求不高,可以在不清楚管材管径的情况下进行漏水定位。从而实现了从发现漏水点到漏水点精确定位,从一段管线到大面积的检漏普查,仅用一套仪器就可完成。
多探头相关仪,顾名思义多探头,从2个探头开始,最多可配置到192个探头；以实现区域漏水声音的记录。普通相关仪则是我们已熟知的,其原理是根据漏水声沿管道传播到传感器的时间差来确定漏点位置的,而多探头相关仪有强大的软件支持,可反复利用在测试中收集到的大量相关测漏数据来验证检测结果,因此大大提高了检测的效率和准确度。
多探头相关仪的记录仪（简称探头）具有防水功能,不用无线发射,可排除无线干扰和盲区,区域泄漏普查系统可对PVC管和水泥管进行检漏。
测试时间不受限制（从10秒～3小时）,可在白天或夜间测试,避免了其它产品只能在夜间测试的局限性。
多探头相关仪既应用了世界的领先技术,也充分反映了实用性：可自动生成模拟管网图。
2.1.2 我国管道检漏发展的现状和未来
我国自1897年旅顺建成第一个供水设施,已有100多年的历史,各地供水企业在技术管理上积累了丰富的经验。改革开放以来,各地水司重视运用先进管理手段,加大对管网管理投入,在提高供水效率上取得显著的成效。但由于城市基础设施欠账太多,供水设备的更新,技术水平提高缓慢,加之管理体制落后于不断发展的形势,使管网漏损率均未达到《城市供水2000年技术进步发展规划》所规定的目标,大多数城市供水漏失率多在25--30%。与发达国家比较还有很大的差距。多年来,各地水司以管线事故抢修为主,漏水调查为辅,多数单位管线处于被动检漏状况,效果不好。随着国内市场环境的改善,国家有关用水节水政策措施的颁布,漏损控制逐步受到各水司的重视,相继引进了不少先进的漏水检测设备,如美国、日本、英国、德国等国家的听漏仪、相关检漏仪、探地雷达等。各大中型水司根据实际情况也成立了相应的检漏队伍,取得了一定的效果。但从总体看与发达国家比较还有相当大的差距,普遍存在着检漏技术人员较少、专业技术素质差、对先进设备的使用方法理解不深,更有甚者,有的水司将先进设备闲置,无人使用,造成很大浪费。由此可见,我国供水漏损控制工作是任重道远,要达到10%以内漏控目标还有相当长的一段路要走。
随着自动化仪表、计算机技术的深入发展,各种动态检测技术也相继出现,如：压力点分析法、特性阻抗检测法、互相关分析法、压力波法、流量差监测法、管道瞬变模型法等等。
压力点分析法。压力点分析法可用于气体、液体的多相流管道的检测。当管线处于稳定工况时,流体的压力、速度和密度的分布是不随时间变化的。当泵或压缩机供给的能量变化时,上述参数是连续变化的。当管道发生泄漏后,液体将过渡至新的稳态。过渡时间从几分钟到十几分钟不等,由动量和冲量定理确定。压力点分析法检测流体从某一稳态过渡到另一稳态时管道内流体压力、速度和密度的变化情况,来判断是否包含有泄漏信号。
特性阻抗检测法。由传感器构成的检漏系统可随时检测到管道微量原油的泄漏情况。传感器采用多孔聚四氟乙烯树脂作为绝缘材料。这种材料导电率、绝缘阻抗热稳定性好、不易燃烧、化学稳定性好。当漏油渗入后,其阻抗降低,从而达到检漏目的。
互相关分析法。设上、下两站的传感器接收到的信号分别为x(t)、y(t)。两个随机信号x(t)和y(t)有互相关函数Ｒｘｙ（ｔ）。如果x(t)和y(t)两信号是同频率的周期信号或包含有同频率的周期成分,那么,即使ｔ趋近于无穷大,互相关函数也不收敛并会出现该频率的周期成分。如果两信号含有频率不等的周期成分,则两者不相关。
压力波法。压力波法是国内应用比较普遍的检漏方法。当管线某点发生泄漏时,该点可视为向上、下游传递压力的压力源,同时向上、下游传递一个减压波,表现为上站的出站压力和下站的进站压力分别下降。
现代科学技术的飞速进步,使管道泄漏检测技术的新方法、新成果层出不穷。特别是传感器技术、计算机技术、探测技术、仪表自动化的融合,使检漏技术向智能化、多样化的发展提供了广阔的发展空间。
2.2
相关算法
相关函数和协方差函数用于描述不同随机过程之间或同一随机过程内不同时刻屈指的相互关系。相关技术在信号和系统的分析和综合中占有重要位置,能够用相关技术解决的工业问题范围很广,基于相关技术的检测系统也有很多种。从本质上来说,相关检测技术基于信号和嘈声的统计特性进行检测的,相关函数是两个时域信号（有时是空间域信号）相似性的一种度量。人们认识到相关技术的重要性已经有很多年了,近二十多年来,随着大规模集成电路技术和计算机技术的发展,硬件电路和软件程序的成本越来越低,在检测数据处理和微弱信号检测领域,更多地使用相关技术可使解决一些难于解决的问题成为可能,一些基于相关技术的实用系统也不断问世。
2.2.1
相关函数的概念
相关函数是一个数学概念,对于两个不同的函数f1(t)和f2(t),积分
就称为f1(t)和f2(t)的互相关函数,用记号 表示,而用 表示 。
当f1(t)＝f2(t)=f(t)时,则积分
称为函数f(t)的自相关函数（简称相关函数）,用
表示。即
（2.2.1.1)
对于X(t)和Y(t)两个常见的平稳遍历性随机信号,经典的互相关函数可以用足够长的统计时间T内的时间历程样本x(t)和y(t)乘积的时间平均来计算,即
(2.2.1.2)
式中τ为延时时间（或位移）。
相关系数（归一化相关函数）则为
,
(2.2.1.3)
式中 与
分别为信号X(t)与Y(t)在零点的自相关函数。
相关性分析能从噪声和其他无关信号中找出信号两部分之间或两个信号之间的函数关系,并根据相关性进行检测和提取。利用相关函数（或相关系数）的统计计算,找出相关函数出现极值所对应的延时量τ0,是相关分析的基本内容,可以在许多重要的领域中得到实际应用。
2.2.2
相关检漏原理
管道发生泄漏时,泄漏发出的声音信号就会沿着管壁向管道两端传播,管道的相关检漏法是指利用两个传感器拾取漏点发出的声波,对这两路声波信号进行互相关分析,没有泄漏时,相关函数的值在零附近；发生泄漏后,相关函数的值将发生显著变化；另外,当管道泄漏点的位置不同时,两个信号的延迟时间
就有区别,信号的相关函数的值就会改变。因此,根据信号的相关函数信息,就可以对管道的泄漏状况进行检测。
2.2.3
快速相关原理
由式 可看出,求一维DFT时,对 u的 N个值中的每一个,需要做N次复数乘法和 （N-1）次复数加法。那么对N个
u值,全部DFT运算则需进行N*N=N2次复数乘法与N（N-1）≈N2（当N很大时）次复数加法。很显然,当N很大时,计算是很费时的。
1965年由库里（Cooley）和图基（Tukey）首先提出一种FFT算法,其复数乘法和加法的次数正比于Nlog2N,这在N大时,计算量的节省很显著,见表2-1。
表2-1 FFT与DFT算法的比较
例如N=1024,用DFT直接运算,对于一般小型计算机需要几十分钟,而用FFT算法,其速度可快100倍以上。秩序几十秒。如采用FFT硬件专用机只需要几十毫秒即可完成。
FFT算法基本上可分为二大类：按时间抽取算法和按频率抽取算法。“库利－图基”算法属于前者,而后者是前者的改进形式,称“桑德（Sande）-图基”算法。FFT算法包括了以下三种情况：
（１）N为2的整数幂的算法；
（２）N为高复合数时的算法；
（３）N为素数时的算法。
这里用的是最基本的N为2的整数幂的算法,而且是按时间抽取的算法。
一维离散付立叶变换对为
(2.2.3.1)
（2.2.3.2）
式中x,u=0,1,2,…,N-1
(2.2.3.3)
FFT是利用WuxN的二个特点来提高计算效率的
（1）WuxN的对称性
Wu(N-x)N=W-uxN=(WuxN)*( 2.2.3.4)
（2）WuxN的周期性
WuxN=Wu(x+N)N=W(u+N)xN
(2.2.3.5)
因为N为2的整数幂,即N=2M,故可以将f(x)分解成二部分；一是偶数部分f(2x),一是奇数部分f(2x+1),此处x=0,1,2,…,(N/2-1)。那么,离散函数f(x)的DFT可以用二个N/2采样点的DFT计算,即由偶数部分f(2x)的DFT和奇数部分f(2x+1)的DFT求出。因此,式（2.2.3.1）可以写成：
（2.2.3.6）
从式（3.3）可得W2uxN=WuxN/2,那么式（3.6）可改写为
（2.2.3.7）
如定义：
（2.2.3.8）
（2.2.3.9）
其中u=0,1,2,…,(N/2-1).
由此,式（2.2.3.7）变为：
（2.2.3.10）
因为
所以Wu+N/2N=Wu *WN/2
=-WuN
那由（2.2.3.8）至（2.2.3.10）可得
（2.2.3.11）
由式（2.2.3.10）和(2.2.3.11)可见,一个
点的DFT可以从二个N/2点的DFT求出。F(u)的前一半的计算由式（2.2.3.8）和（2.2.3.9）求出分别为N/2点的DFT,即求出F偶(u)和F奇(u),然后带入式（2.2.3.10）可得u=0,1,2,…,(N/2-1)的F(u).另一半可直接从式（2.2.3.10）。如依次类推,每次将N/2用2除,就可以分成越来越小的子序列上执行DFT,直到执行2点的DFT为止,最后再合成N点的DFT。
（二）信号流图
FFT运算可用信号流图表示。式（2.2.3.10）和式（2.2.3.11）运算一般称为蝶形运算,因子Wun称为旋转因素。蝶行信号流图如图3-4所示,图3-4中（a）和（b）是等效的二种蝶行运算表示形式。很显然,计算一个蝶形需1次乘法和2次加（减）法。
图
2-1 蝶形运算
下面以N=2为说明式（2.2.3.10）和式（2.2.3.11）的FFT算法,其蝶形信号流图如图3-5所示。
图
2-2 N=8的按时间抽取FFT信号流图
上述方法的每一步分解都是按输入序列在时域上的次序是偶数还是奇数来抽取,故称为为按时间抽取法,同样也可按F(u)在频域上的顺序是偶数还是奇数抽取,这时按频率抽取法。按频率取样法FFT可参阅『3.14』。
从图2-2还可以看出：
（1）对于N=2M点DFT的整个运算全由蝶形运算组成,需要M轮递推,每轮由N/2个蝶形,总共有N*M/2=
Nlog2N/2个蝶形。考虑倒每个蝶形包括1次乘法和2次加法,因此,总的计算量为Nlog2N/2次乘法及Nlog2N次加法。采用这种形式的FFT算法,最少可以节省计算时间的倍数为：
（2）从图3-5中可以看出FFT变换的结果是
F(0),F(1),…,F(7)是自然顺序排列,而输入f(0),f(1),…,f(7)才可以进行FFT运算。此“码位倒置”是因为在时间抽取算法过程中,把偶数点放在上面,把奇数点放在下面。奇数点与偶数点可以从二进制数码的最后一位码
n0先着手区分开来。如果n0为0,则n是偶数,应放在上面。反之,如果n0为1,则n是奇数,应放在下面。然后再依此由左到右逐位检验下去。最后合起来就是倒置了码位的二进制反序数。由表2-2表示了N=8=23共有三个码位
n2n1n0的倒置过程和结果。
自然顺序 二进制码表示 码位倒置 码位倒置顺序
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
表
2-2 码位倒置顺序
（三）逆FFT
FFT的逆变换都可用正变换FFT作适当的修改即可求得。为说明此点,将式（2.2.3.1）和（2.2.3.2）重写如下：
（2.2.3.12）
（2.2.3.13）
求式（2.2.3.13）的共扼并用N除二边可得到。
（2.2.3.14）
将式（2.2.3.14）和式（2.2.3.12）比较,可看出式（2.2.3.14）的右端在形式上就是付立叶正变换。因此,只要将F*(u)输入到计算正变换算法,结果将式
f*(x)/N,取它的复共扼的运算没有必要,因为对实函数有f(x)=f*(x)。
2.2.4 漏点定位算法
图2-3
相关检漏技术的工作原理图
管道检漏技术的工作原理如图2-1所示,假设管道在Q点发生泄漏,泄漏发生后,在泄漏处将引起压力突降,产生一个以Q点为泄漏源的声波信号,该声波信号将以一定的波速V
向管道两端传播,安装在管道A、B两端的传感器分别在t和(
)时刻检测到这个信号（这里假设泄漏点距离两个传感器的距离La>Lb）,由于同时也有外部噪声的影响,设A、B两端的传感器测得的信号样本函数分别为A(t)、B(t),因而它们可以表示为以下形式：
(2.2.4.1)
(2.2.4.2)
其中 和 分别为A、B两点的背景噪声。
对A(t)、B(t)进行相关运算：
(2.2.4.3)
为了处理数据方便,一般认为泄漏信号与噪声信号相互独立不相关,噪声信号 和
完全不相关,那么,
(2.2.4.4)
当相关函数 达到峰值时,所对应的 值正好与两个传感器检测到的信号的时间差相一致。由数学知识可知,相关函数 在
处取得极大值的必要条件是 在 处的导数 ,由此求出
,再测出两个传感器之间的实际长度L和声波在该管道的传播速度V,泄漏点Q的位置就可以用下面的公式计算出来：
(2.2.4.5)
或者
（2.2.4.6）
2.3
第四章
系统联调
本实验是利用快速相关原理来处理户外水管中存在的泄漏问题,该实验要用到两个相邻传感器中所接收到的声音信号,这在本实验中是模拟出的数据。
由于本实验是用于户外水管的,而相关算法的点数是根据公式Lb=(L-τ0*v)/2,漏点信号的频率为20-2000Hz,则最小周期为0.00025s,而两传感器的距离一般为40m,声速为334m/s,则最小的点数为479,所以本实验采用的点数为512点。
用Matlab模拟的两个相邻传感器的声音信号是用漏点信号和白噪声的混合信号,两个信号如下所示：
图4-1
第一个模拟声音信号
图4-2
第二个模拟声音信号
本实验调入的是.dat文件,以上是在DSP环境中观察到的信号,将这两组信号经过程序的运算后得到的时域信号为：
图4-3 两组信号的相关结果