tceic.com
学霸学习网 这下你爽了
相关文章
当前位置:首页 >> 数学 >>

提高一维FFT和大矩阵的二维FFT的速度


1 , 5 2年 6



重 庆 大 学 学 报



2



提高 一 维 P F T 和 大 矩 阵 的二 维 F F T 的 速 度
朱 明 节
( 重 庆 大学 电 气 工 程 系 )


本 文 分 析 了 影 响 一 维 F F T 速 度 的 因素 ;


着重 介 绍 了 作 者 提 出 的 新 的 倒 序 方 法
,

— 式


插 入 倒 序 法 和 按 时 间 抽 取 的 ( D I T ) 倒 序输 入
同时
,

项 序 输 出的 基 4 算 法 的 递 推 公


时 其 它一 些 提 高 速 度 的 简 单 易 行 的 方 法 也 作 了 分 析 和 验 证

文 中 还 分 析 了影 响 大 矩 阵 的 二 维 厂F T 速 度 的 主 要 目 素 ; 的 数 据 在 内 冲 存 之 间 的 读 写 遇数 减 至 最 小 的 方 法
己l
J
.
s e

提 出 了一 种 使大 拒 阵




分 列 随 机 存 取计 算 法

龚犷
「 刁

数字 信 号 处 理 是 近 十几 年 发 展 起 来 的 一 门 新 兴 学 科 离 散 傅 里 叶 变 换 ( D F T ) 及 其 快 速



算法

.

T

—如


快 速 傅 里 叶 变 换 ( F F T ) 是 这 门 新兴 学 科 的 一 个 支 柱 自从 J





.


,

.

C

o

l o

o

y

和 J

.

的 标志着 F F T 诞 生的 文章 ( 文献 〔 根 据 这 些 算 法 制 造 的 专 用硬 件 仍 具 有 重 要 的 实际 意 义
.

1 〕)


,

1 96 5

年 发表 以来
;
.

F F T 的 各种 算

法 不 断 出现 的 软件程 序
的处 理速 度

,

可 以 对 信 号进 行 实 时 处 理


根 据 这 些算 法 设 计
,

,

可 以 借通 用 计 算 机 进 行 信 号 处 理


然而


时至 今 日

研 究 新 的 算 法 提 高 ’I, 厂 T

,

在 一维 F F T 部分

本 文从倒 序






4

算法

减 少 生 成 加 权 因 子 和 蝶 形 运 算的 实 数 乘 法


次 数 和 省 去 无 效 乘 法 等 方面 来 提 高 速 度

在 二维 F F T 部 分

,

详 细 介 绍 了 分 列 随 机 存 取 计算 法

提 高一 维
关 于一维 F F T 和 蝶形 运算


F F T 的 速度
,

,

经 常 用 到 的 算 法 是 即 位 算法
,

其 处 理 过 程 包括 倒 序


,

加 权因子 的生 成

提 高 F F T 的 处理速 度

宜从 这三 方 面进 行研 究


既 有的 倒序 方法
〔 3〕)
。 ,


2 〕 )

包 括 按定 义 实 现 倒 序 的 方 法 ( 文 献 〔


和 R


a

d

e r

倒 序法 ( 文 献

前者 的 缺 点 是 倒 序 速 度很 慢
本文 于1
98 2 年 2

后 者 的 倒 序 速 度 有 了很 大 提 高

1 9 8 0年

尚 有 人 称 尸 a 口’e )

月2 7 日 收 到
,

本 文 在 周 守 昌 副 教 授 的 直 接 指 导 和 帮助 下

由 研 究 生 朱 明 节 同 志执 笔 写 成
.

38








文献 〔








1 9 8 2年
,

倒序法

是 迄 今 为止 最 好 的 倒 序 方 法
,

(

3〕 )

在微 型 计 算 机 上 实 测 结 果 表 明
4

以上

两 种 倒 序 方法 所 占的 时 间 约 为整 个 F F T 处 理 时 间 的
的 倒序方 法

%一1 5 %



因此

,

研究 速 度更 快的 新
,

是有 实 际 意 义 的
.



-

上 面 两 种 倒 序方 法

依 赖于 十 进 制 数 和
。 。

.

r

(

r

是 大于
.

1

的 正 整 数 )进 制 数 之 间 的 转 换
,



而 要 进 行 乘 除 法和 加 减 法 运 算

本 文从 另外的 途径 探求倒 序的方法 倒 序时
9
.

即 在 十进 制 数 的 范 围

内 来寻找 倒序 序列 的排 列规 律



倒 序序 列 是 一 个 整体
`

序列 中 的 各 个 数 的 排 列 挂 有 内 在 联 系
,
. .

例如
〔 0
.

.

按基
4
,

4
.

(


,



等于
.

!
.

)

,

6 点倒序 序 列是 1
2
,

8

12

1

5

13

,

6

,

10

14

3



.

1 1

.

1 5〕

把 它和
〔0

4
,

点 倒序序 列
l
,

2
.

,

3 〕
,

对 比可 以发现 倒 序序 列
.

只 要把 4 点倒 序 序列 中的 每个数 用 以该 数为 首项 的
,

公 差为
’ ,

4



.

共 有
4

`

4

项 的 等 差 数 列 代替 规律


就得 到 1 6 点倒 序序 列




更 进 一步


.

如 果要 由 4 点 倒序序 列得 到






则 插人的等 差数 列 的公 差应是
,

4



对于 其 它 墓数 的 倒 序序 列

也 有 类 似的 排 列

于是

提 出 了任意 基数 设有尸
.
.

的 倒 序序 列 的 排 列 规 律 的 命 题


命题
〔 0
,

个 点的 顺序 序列



1 0
r

2


·

。 1


,



,

(:

5

1)〕

其中
记 它的 基

(



r



的倒 序序列 为
〔b
。 , ,


.

b

` 爪

·



b

,

r



l 〕

(

1

)

只 要 把 序列 (

1

) 中的 各 个 b ’
b允
.

用 等差数 列


r


r

b{



2


2
,

·

`

+

6





.



,

(:



1)









代替 其中

.

就得 到:
r

` 十

`

个 点的 基

; :

的f J 序序 列 P
,



=

2

.

3

.




0

1

,


r



证明

用 数学 归纳 法
,

第 一步
用 等差数 列
0
.










r

.



=

0 r



1

.



点 倒 序 序列 可 由

1

点 倒 序 序 列 叮 。 〕生 成

,

即将



1

,

2

,



,

(
.



1

)
.

代替 显然

,

就 得到 序列
〔 0
1
r
.

2
r



,

(

r



1

)〕 )〕

(

2

)

,

序列(


2

) 就是 基
〔0
,


1
,

点 顺 序 序列
2
,
·


:


(
一 ’

r



1

(

3

)

的 倒 序 序列

第二 步
r


.











.

设已由

点 钊 字 序 列 按 佘题 中 插 入 等 差 数 列 的 方 法 而得 到 的

点基

/

的 倒 序 序列 为


共中


b




澳 、 . 尸


l





簇r

l



1





2



朱明 节
4
·

:

提 高 一 维 F F 犷 和 大 矩 阵 的 二 维 F 尸犷 的 速 度

g

又设 对 应于序 列(


) 的 顺 序序列 为

,









(r





i
r

)〕

o


(
,

5

)


然 后再将 序列 (

5

) 中的 每 个 数表示 成

进制码


为了进 行码位倒 置
n

每个码 应 由
r



组成



不足

n

位的

,

则 应 在 高位 数 的 位置 上 补
。,

以凑足





记 序列 (

5

)的

进 制 码 序 列为
( 6 )

〔b



,

b

门 ,


,

b

r



i 〕

将 序列 (

6

) :卜 的 每 个码 作码 位倒置
b、
1 ,

就 得 到 序列 ( 6 ) 的 倒 序 码 序 列
·



,

“:

1 ,





、六 1






(



)

显然

,

序 列 ( 6 ) 和序 列 (
4
,

7

) 中 的 每个 码 均 有
5



由 于 己 设 序列 ( 根据 倒序 概念

) 是 序列 (
7
+

) 的倒 序序 列
4

,

序列(



) 是序列 (

5

)的



进 制倒序 码序 列
4

,

序列 (
:

) 中的 每 个 码 转 换 成 十 进 制 数 后 得 到 的 序列 就 是 序 列 (
1时
,

)



第 三步
r
” 十

,



二 。

把 序列 (

) 中的 每 个 数 用 命 题中 所 讲 的 等 差 数 列 代 替

,

就得 到



点序列
〔b

:

。 ’

.


,



b
,

。 ` ,

2



r u
。 ,

+

6
Z

。 ’

.


`

,

(r

,



1)
.

x

r

: `

+

b

。` ,



b





厂月 +

b
r



,

K 厂

+

b
2




(:


·

1)

x


,





b



。:

,

b 一1



,



+

“ 一1



,

\

·

+



补;





(卜

`

)

又 r

`

+

b 一1〕



( 下 面 应 证 明 序列 (


8

)

8

)是


l =

+



点的 基
r

r

倒 序序列




: r

十 `

点 顺 序 序 列可 由 r
,

点 顺序 序列 (
,

5

) 扩充 而成



即 将 序列 (
.

5

) 中的 每 个 数 用 以 该 数 的

倍为 首 项 的

公差 为
〔 0
,

1 l
,


,

共有
2
. ·

项的 等 差数 列代 替
(
1
·

就得到 序 列
.




,

`



1)

.


,


,

r

X

0

,

.

x

用 +

1


.

,





切 +
,

2
r

,



r

x

。 1)

+

(r
2
,

.

)
r


x

,

x

(

r

`

一 l
+

)

,

r

K

(r



l

)

+

1

x

(r





+


r

(r





1)

(r
.



1)〕

(

9

)
5

为 了将 序 川 (
歹 U( 6 )
,

9

) 中 的每 个数表 示成

进制 码 ( 注

1

)

利 用 归纳 法假设 中的 序 列 (

)和 序

就 得到 序 列
。 〔6 o
,

。 b 1

,

。 6 2
,
·

,



,

b (



r


,

1

)

,


,

,

6 o

,。

,

b
,



1

,

b



2

,

·



b



(r



1

)



br一1 0

b r一 1 1

b: 一 2 2



b r 一 z (厂一 1) 〕
又1 0 )

为 了 将 序 列 ( 1 0 ) 中的 每 个 码 作 码 位 倒 置

.

利 用 归 纳 法 假 设 中 的 序 列 ( 6 ) 和 ( 飞) (
,

,

得 到序 列



。“

:

`

,

,

“、

1 ,

2“ 、

` ,





` ,“ 、 ’

,



。 “ 采’

,

, “ 蕊’

,

2 “ 不`

:

.
.

















`

·

·



泛 开



,

l b不 4 l



(

,

r一 1 Z b1石 )六

b;

o1b

(卜
注意 (注
2
,

l

) b于 老l 〕



(

11)

序列 ( 1 1 ) 中的 每个 码均 有 ( n



1 4

)位



为 了将 序 列 ( 1 1 ) 中的每 个码 转换 成十进 制数


)

,

这 时利 用 归纳 法假 设中 的序 列 (
〔b
。 ’ ,

)和 (
。` ,

) 之 间的关 系
,

·

就得 到 序列
+
。` ,

r



+



。` ,

2

`

r



+

b


,

(r




1

)
r


x

r



b
` ,



,

b



` ,

r



+

b

。 ’ ,

2

`

r



+

b

。 ` ,



(r
1

1)

X

+

b

,:


r
r`

b 一1



,

r



+

b 一1



,

2

)` 护”

+

b

井l
b



,

·



(r



1

)

x

+

夯1〕
r



( 进制 码 序 列
12 )
,

12)

由于 序 列 (

.

9

)是
,

r

” +



点顺 序 序 列
`

,

序 列 ( 1。 ) 是 它 的
9

序 列(1 1 ) 是 序列
,

( 10 ) 的倒 序码序列 可知序 列 ( )


序列 ( 1 2 ) 是 把 序列 ( 1 1 ) 转换 成十 进 制数 后 得 到 的序列

, 十

根 据倒 序 的 概

12)

就是

点 顺 序 序列 (

) 的倒序序 列

.

而序 列 (

正 是所 要证 明的 序 列

(

8

数学 归纳 法证明 完 毕
恨据 这 种 方 法 实 现 法 称 为 插 人倒 序 法




,



J

心序 列 的 倒 序



.

只 需插 人 等 羞数列

J



:

所以


,

拟将 这种 倒序 方

表一 中 给 出 了 用 两 种 方 法 完 成 N 点 序 列 的 倒 序 所 需 的 运 算次 数
差 数列
,

由 于插入 法插人 的 是等
,

所 以 不 需 要 乘 除法

,

而 只 需 较 少 次数 的 整 数 加 法 即 可 完 成 倒 序

因 而 倒 序速 度更







1

,

把 十进制 数万 表 为
.



进 制数 的 方法如 下
,

:

第 一步

M 除以

/

.

得商 和 余 数

把 余数作 为
r r
,

r

进 制数 的第 一位 ( 低位 )
,



第 二步 第三 步
于是
,

,

将 第一 步 所 得 之 商 除 以 将第 二步 所得 之 商除 以
,

得商和 余数 得 商和 余数


把 余数 作为 把 余数 作为

r
r

进 制数 的 第 二 位 进 制数 的 第 三 位



.

,

,



如此进 行下去 注
2
,

直 到商 数为 进 制数
=
a



0

时停 止


0 ) 的得 来便 不 难理解 序列 ( 1

将 几位

r

a

a

,

_ :




a

:

a

l

.

转换 成十进 制数 刀的 方法 如 下
一 ,

:



x

r



一 ’

+

a

_

:

又 r

n

+



+

a :



r

+

a ,



2



朱明 节

:

提 高一 维 户夕丁 和 大 矩阵 的 二 维 F F 丁 的 速 度


表一

两 种 倒 序 方 法 所 需 的 运 算 次数 的 近 似 值 (序 列 点 数 为 N )

倒 序方 法
根据 定 义实 现基
2

乘法次数
倒序 倒序

}

整数 加 法次 数

根据 定 义 实 现 基

4

表 二 中 给 出 了 用 三 种 不 同 的 倒 序 方 法 在 R D 一 n 微 型 计算 机 上 完 成
倒序所 需要 的时 间


1 0 2选个

点的 序 列 的


从表 中 可 以 看 出 表二


,

插 八 法 倒 序 的 速 度超 过 了 另 外 两 种 方 法 倒 序的 速 度
,

倒 序 时 间 对 比 (时 间 基
2

秒)

倒序方法
按定 义实 现倒 序的方 法
]才a d
e r

倒 序时 间
2 72
一 1 心 J C 任 」 n U



4

倒序时间



倒序 法

ù.

b

O 3 8 0




插 入倒 序 法 由 于插 入倒 序法 插入 的 是等 差数列
,

22

所 以 程 序 编 制 简单

,

并 可 方 便 而 迅 速 地 用手 工 排 列

倒 序序 列




早 已有人 指 出
2
,

4

算法
2




4
4

算法所需 要的 乘法 次数 比基
算 法处理 速度 更快
。 。

算 法 减少 四 分 之 一
,


,

而加 法 次数和基
,

算法 相 同
4



因此

,

目前

,

尚未 见到 D I T 的

倒序输人

川 五 序输
,

出的基

算 法的递推 公 式


所以 作者进 行并 完成 了这方 面的 工作

,

由于 推 导过程 太 长

,

这里

只 给 出结 果
:

设被 变换 的输 入序 列是 f ( 的
`

j 点数 N 序l
:

=

r 4

,



4

算法 要 执 行 的 步 数 是

进行 第

) 的值 由 下 面 四 个 公 式 给 出 步 计算 时 f ( n
。 f (
:

+

n f

·

4

`

)

=

飞 ” f卜 (

+



·

4

`

)
+

+

才女
不梦
4

.

`

·

f (
一 ;

。 +



·

5 4 +

4

,

一 `

)


+

介 卜 厂长

·

`

·

f

:

一 ,

(


,, +

, 7, ·

4



+

2

.

4

’ 一

`

)
+

`

·

f

:

(

,:

+

,,卜

4

`

+

3

.

4

一 “

, 2 +

,矛 卜

4

+

4

`

一 `

)



f

:

一 ,

(陀

`, `·

)



j牙 护

`

·

f



一 ,

( ,:

+

, ,2

·

4

+

4




+

大 不
`


`


·


f
一;、


: 。

牙梦



`

·







·





一 ’



(
:

+

·



4

+

2 一 4
.



)
4 ,
+

+

j
·

f
` ` 4f + 4 :

:

(

+

m

4

+

3

.



·



·

`

一’





,

(

n +

n t

·

4 )

`



f砰(井 +r
r 一`
·

·

`



m5 4

.

f
+

+ :

_ :

2

(

) 。
·

一 `

+

w梦
`

·

r ,

一“

.



,

_

,



+





4

`

+

2



4

` 一



)



附势

·

`

f

;

一 1

(n



·

4

·

+

3 4

`

一 ’

)

” f (
:

+



·

4

+

3

·

4



一 ’

)
+

=

j
2
·

: 一

:

(。

+

; ;卜

4

`

)
·

+


·



·

4

·



f
+

:

_ :

(n
,

+



·

4



+

4



一 `



甲穷
:





·

f(”

+



·

4

`

4

`

一 `

)



j 平梦

`

n f卜 (
:



·

4

+

3 4

.

`



`

其中



r

;



=

0


刀 二

1

;

m

=

o

,

1

,



,

4

r

一`

一 z ;



e

一 J

Z’

l



j







1



这 四 个 公 式 就 是基
公 式 中的 了加 权 因 子 值 之 间的 关 系
,

4

算 法的 递推 公 式






,

是 蝶 形运 算 群 的 序 号
4







步 计 算 中有 4 一 个 群
:



,

每 个群 中 有


4

,

个点

,

从而每个 群 中 有
,

一 ’

个 四 点蝶 形运 算 (

4

一 ’

正 是第


步 计 算中

n

可 取 值 的 个数 )


公 式给 出

并 清 楚地 表 明 它 与 群 序 号 。 无 关

这 组 递 推 公 式 由 于 清 晰 地 显 示 了 各 有关 量

所 以 根 据 它来 绘 制 信 号 流 图和 编 写 程 序 是 很 方 便 的

加 权 因 子 的生 成 和 蝶 彩 运 算
加权 因子万 异 是 复数
.

其 值在 F F T 运 算 过 程 中应 设 法 产 生 之
,



一 种 常 用 的 方 法是 利 用
,

程 序 设 计 语 言 的 内部 函 数 事 先 求 出 所 需 的 诸 邵 鉴的 值 所 需 的 加 权 因子


存 入 一 个数组

作 蝶 形 运 算时 再 调 用

另一 种 常 用 的 方 法 是 用 程 序 设 计 语 言 的 内 部 函 数 生 成 加 权 因 子 的 少 数 几 个




,

其余 的 值靠 递推 生成 曾有 人指 出 (
a
,

按 下 述 方 式 处 理 复数 乘 法 过 程

+

,

可以减 少 实数乘 法 次数
口+
s

,



+
n

jb ) (
一 e o s

e o ;

j

s

`n

g)

=

(

a

+

b)

C o S

O



b(

C o “

i

n

J)

+

少 〔(

a +

6 )

e o s

s

+

a

(



i 口

口) 〕
,

据此
5

,

增 设一 个 工作变量 当(
a

实 数 乘 法 次 数就 可 由
,

4

次减 少到

3



.

加 法次 数则 由 次


2

次 增加到





+

了 ) 表示 加 权 因 子 时 b
1

实 数 乘 法 有 时还 可 以 减 少 到


2

当 加 权 因 子 甜 二为 不 乳 =

和平





]



,

这 种 蝶 形 运 算的 复 数 乘 法 是 可 以 不 用 进 行





由 于 进 行 实数 乘 法 比 进 行 实 数 加 法 所 花 费的 时 间 多 得 多
度 是有 利 的


,

所 以 减少乘 法次数 对于提 高速

,

采 用 上述 方 法后

,

实 数 乘 法 次 数 有 了较 大 幅 度 的 减 少



例如

,

当刃

1 02 4时

实数乘 法

次 数可 减少 4 0 % 以上







朱明节

提高 一 维
表三


2 大 矩阵 的二维 和

:

F度 T 的F速

F F T

改 进前 后 的 乘 法 次 数 的 近 似 值



还异 , 笙

… }基
`
,


序列 点 数 为 _ _算_ _法
}

,

(
.

N

)
4


一 ,


算2
}







_

,



_

! 二二 j u左 又 l l
-

一 }
}


,

~ 一一 。 一 ` ~ 四 」 四 头 妥又采 扭云
-

}蝶 形 运 算 的 实 数 乘 洪
-

— 一
.

{


’ -

`



}



月“



-

-

- -



,

牡盛 产 旦 一
}
_

,



改 ”
.



,

,









_




`



Z

}
l .



,

}
l
1

4挥
-



-

-

-



Z


-

-

浏、

4
-

-


}一




2刃

z。

N

鱼N z
2





,





巧刃
4

l
的 方法 后










“ 2



。 z

刃z



:





,

N



:

N

}





8

表 四 中 给 出 了 F F T 算 法 改 进 前 后 在 R D 一 1 微 型 计算 机 上 的 运 行 时 间 处理 时 间 可减 少3 0 % 0 %一4 表四




采 用 本文给 出



一 维 F F T 运 行时 间 对 比 ( 单 位 为 秒 )
2
-

基 序 列 点数

-



法 改 迸 后
, 了 ū 曰 八 , 曰 月 O U n ` ù

!


-

4
- -



法 改 进 后
7


-

改 进 前
N N
=



-

-

-



-

1024

] 4

.

18



25 6

éō 八 卜 ō U ` 9 U n

N

=

64

:

—…
1



-

-



改 进 前
12
。 。


44







86
一 切 8 5

2 56

大 矩 阵 的 二 维 F F T 的 分 列 随 机 存 取 计算 法
二维 D F T

定 义 如下

:

N _ 1

3了_

X

、 ,

=

艺 艺

x

:

:

万人 平 户

其中





O

,



,

M



N



上 式可 用 矩 阵 写 成

〔 〕 〔
根 据 矩阵 乘 法 规 则
,

二*

:

=

尸:,

]



`

:

, ,

[

x 一



`





〔 〕


牙另

,





这 个 变 换 可 分 解 成 按 列 进 行 的 一 维 F F T 和 按 行 进 行的 一 维 F F T






就是常 说 的行 列算 法 在 二维 F F T 中

,

常常遇 到的 是大 矩阵 的 二 维 F F T


提高 大 矩阵的 二 维 F F T 的 速度
,

会遇 到 一 个 严重 的 问题

当 数据 矩 阵较 大 时

,

由 于 计 算机 内存 容 量 有 限

只 好 把数 据 矩 阵 的

44


,












I , 8 2年

数 据 全 部 放 到 外 存 (如 磁 盘 等 )

l

{ i [ 把 内 存 空 出 来 供 计算 用


计 算 机 不 能 从 外 存 } 随 机 存取 矩
,

`

,

阵 的某一 个元素

,

,

可 以 随 机 存取 的 是 矩 阵 的 行 或 列
N 矩阵的



例如

当 计 算机 只 能 对 矩阵 按 川 存 取


在首 先 按 列 作 一 维 F F T 时 是 不 会 遇 到 什 么 特 殊 问题 的
,

但 下 一 步 按 行 作 一 维 厂厂 T 的

时侯
n

如 果 计算 机 只 能 处 理 N
,

x



行 则只 好把从 外存 调 到内存 的 每列数 据中 留下
这样
,

,

个需 要 的
·

而 把 不 需 要 的 数 据 送 回 外存


矩 阵 中的 全 部 数据 在 内 外 存 之 间 读 写 一 时的 数 据读 写遍 数是

·



只 能 使 内 存得 至 。 矩阵的


行 所 以 按行 作一 维 F F :
.



其 具体数

值 是比 较 大 的
写 应数


对 于 计算 机 来 讲

数 据在 内外存 之 间的读 写 速 度是比 较 慢 的
听以
, 。

较 大的 数据读
·



,

会 大 大 延 长 厂尸 T 的 处 理 时 间
.

如何减 少数据 在 内外存 之 间的 读写 遍数




成 为 了提 高 大 矩 阵 的 二 维 F 厂 T 速 度 的 关 键 的 问 题 为 了减 少 数 居 读 写 遍 数

人 们 提 出 了一 些 处 理 方 法
9 5


这 些方 法有 矩阵 的快 速转 置法和分


级 计算 法 数)
,

,

0 其数 据 读写 遍数 为 1
.
.

刃 ( 刃 是矩阵 的列 数
~


.

是 计 算机 内 存 每 次 所 能 处 理 的 列
,

共具 体值 为

:

3

4

.

,





本 文 提 出 了另 外 一 种 处 理 方 法
列 的 刃 个 数 据 调 到 内存
,

从 上 面 的 分 析 可以 知 道
,

问 题 在 于 按 行 处 理 把 外 存 中每


可 留下



个数 据


而其 余的 N





个 数据 ( 注 意 万 远 大 于
,

) 这时 是
,

不 作处理 的



本 文 提 出 的 解 决 这 一 问题 的 办 法 是 把 外 存 中 的 数 据 矩 阵 的 每 列 均 分 成 若 干 段


每 段 作 为 外 存 中的 一 个随 机 存 取 单 位 随 机 存取 单 位 由于
n

比较小

.

“ 个数 据 作为 一段 即 作为一个 很 容 易想 到 的 是 把 这 样 选 取 会 大 大 浪 费 外 存 例 如 一 丁幼D R 口万 D 月 微 型 计 算

,

4 个 复数 机 的 外 存 ( 磁 盘 ) 上 的 最 小 随 机 仔取 单 位 可 容 6 法 应作 修改
·





乏远 小 于 6 4 的
·



所以

,

段 数的分

即 应 如 此 分 i沈
.

:

选取
.

一个

尽 可 能 小 的 正 整数 入

`

使 尸》

·


’ `、

把输 入的 数据矩阵


的每 j J 均分 成 K 段 l
`

即兀个子 列
,: 2


每 个 子 列 作 为 外 存 中的



个 随机 存取 单 位


每个 子列中 的

J

数 据 个 数 是 比 较接 近 粤 . ~ 久一 ~ ~ K ~
伟 ;


,

r

`

而远大 于 尸 ~
`


~

,

” “



J




所以 这样 处理 ~ ~ ~ ~
z ’




`

般不 至于 浪 费外存 ~ ~ ” 一
’ J

这 个方法的 “ “ ~
’ /

口 `

二 维 厂 厂 T 的 处 理 过 程 分 成 先 按 列 作 一 维 厂 厂 T 和 后 按 行 作 一 维 厂厂 T 两 步 完 成



先 考虑 输 入 矩阵 是 N
装人 R 中
.

x

N 方 阵的 情形
R
,

若 计 算机 内 存 每 次 只 能 处 理
;


n



.

设计 程 序 时

先 在 内 存 中 定 义一 个 数 组 ( 矩 阵 )
,

R

是 N 。 矩 阵 每 次 从 外 存 中调 到 内 存 来 处 理 的 数 据
入 ”

并 且这 些 数 据 个 数 不 得 超 过 N
,





按 列 作 一 维 厂 夕T 时 依 次 从 外 存 中 调 数 据 矩 阵 的 的 一 列填充 刀 的一 列




列( 共 K


:

个 子列 ) 到 内 存 数 据 矩 阵
.





列恰 好填 满 尺



然 后 调 用一 维 F 厂 T 子 程 序
,
奋 为 续农 迈 一元 万丁

分 别对 尸 中的 各列作
,

一维 F F T
二。



处 理 完 毕后把 R 按 行 分 成 均 等 的 尤 。 段





= r

N


X

n

丈、
.



是 子阵
.

每 个 子 阵尔 对 琳
,
_

一叮 ~ ) 即 有 芬数 据 积是 补 ( 一 ~ 药 K ~ 目
~

’ 、



厂 入

,

` 二
.

:

_

,

l一

` J

`

`

-

好 等于 外 存中一 个子 列的体 积 恰 目 叼 r
. ’

一 ,
J




,


4

L
`

,

~ 叭
J

:



,

, : _

~

。 。

J







J

曰 J

`

L t ,

曰 。 一 一 ~ ~ ~ 然后 再 梅 子阵 中的数据送 回 曰 ” 把 护 个 了 ~ ~ 一 “
二.
` .

,

_

,

_

`




,。

r

,

`

,





J

`

`

卜 `

J









外 序 中 仔放 子 列 的 地 址

:

送 回 外 存时

,

应按子阵 的行 的顺 序送 回 又 见 图一 )

此时

.

输入 数 据

矩 阵 的 数 据 在 内外 存 之 间 读 写 了 一 遍







朱明 节

提 高一 维

2 大 矩阵 的 二 维 T 和

T 的 速度




当 又( 故 节
1


2








川 日绷 尸



, 几

又 飞一

{

人 l l

以 J桩
· ·

l

{i
l L



分 分
l



l

,

图。




j宁 浏 廷 理 刘

按 污廷 理 心

分 列 随 机 存 取 计 算法 原 理 图
下 一 步 应 按 行 作一 维 F 万 T 这 时 应 能 得 到 外 存 中 数 据 矩 阵 的 各 行
二 n * ` 曰 二` , 什 刁 1 八 P牛 目U 月夏』 匕 四 目习 习一 P牛
。 ,
,

,



从 图一 可以 看 出 其
,

,

」二

气 夕七

一 N二

T `

*




,

L

!



, 另 丁赴 竺

一 ;, ~ ~ ~ ~ ` 一 N _ 概 三P 牛甘 公月 吐 护 有 戮 探 面; J、
.

,





T`

l T

e s

o

J奸 卜 认

,

.、

,

首 先 应把 外 存 中对

应于 这



个 子 阵的



个 随 机 存 取 单 位中 的 数 据 调 到 内 存


.

并 且 每 个 随 机存 取 单 位 中 的 数 据 按
,

列 的 顺 序 来填 充 刃 中 的 子 阵 按 列 处 理 时 的 子 阵 的 列 数 就 是 按 行 处 理 的 子 阵 的 行 数 按 列 处 理 时 的 子阵 的 行 数 就 是 按 行 处 理 时 的 子 阵 的 列 数


也 就是说

·

按列 处理 时的
。 。
_ _


ù

/



子阵 变 成

了按 行 处 理 时 的
:



x

心 寸、 降
一 N 二
,
_



二~ , , ` ~ 、 ~ 井 即寸 降 作 J 将 直
一 _
_



,



~ 认尸 ` N 入 妆仃灶 理盯 俐 万 !
` .
`
_ _



了 `

/ 一 K刃 油 一

子阵 恰好填

,
f网

n

丁 八 甘习 止v 丁

`



,


.

` 。 。 , 。 . ~ 灭 1旦 力 已 J 样卜 片U 梦 lJ :以 下
, :
_


、 ,



刁 乞万 网 返





n

j 、 八

山 亢

~



,

`

_

卜 习 了 lJ 妥 父

了 名

( 因为

,、 2

)

兴)
j\



从 而按 行处 理时 R
,

中的 第 一 列 对 应 着 数 矩 阵 的 第 一 行
用 一 维 F 万 犷 子程 序
,

R

中 的 第 二 列 对 应 着数 据 矩 阵 的 第 二 行

余 类推



再调

就 可对 数据矩 阵的 前



行 作一 维 F F 丁




然后

,

把 “ 的 各 列 ( 也就

是数 据矩阵 的名 行 , 均分 成 K 段 ( 每段 含 的
卜 “



存 个数 据 ) 送 回夕 卜

由 于 每 次 只 处 理 了数 据 矩 阵


洪 K
n


` J


,

所 以一 共要 处理 K 从~ ~ ~
`





u



,

2 `





` 一

才对 数据 矩阵 的所 有行 作完一 维 * 下 T P 门 厂 ~ 用~ ~ ~ 八 一
`

J



J



/ ’

,

J





`

-



数 据 在 内外 存 ~ ~ 一 “ ”


`

之间 又 读写 了一 遍
至此
,



已 对数 矩阵 作完二 维 F F T
:
’ r

,

数 据 在 内外 存 之 间 的 读 写 遍数 为


2




选择 K 满 足关 系式 。 ) 是必 要的 篷 、 ” 一 ~ 汁 ~ ~ 月 少 K ` ~ 又
一 `

否则

入切


,





-

刁 。

按行 处 理 时 子 阵 的 列 数 列数 澳 会超 出 R 的 ” 入 ~ ~ 一 ~ K n 门~ ~ “ ~
J

, J



J

J

” 砂

/









n

,

而 这 是不 允 许 的



由 于 这 个 方 法 是 把输 人 数 据 矩 阵 的 每 列 分 成 K 个 随 机 存 取 的 子 l j 二 维 万F T 的 分 列 随 机 存 取 计 算 法


,

故 拟称 之 为 大 矩 阵 的

:

.
.

重 当输 人 数 据 矩 阵 是 非 方 阵 时
比如
,
.












19 只二年


分 殉 逾机 存 取 计 算 法
,

般 来 讲 也是 适 用 的

当刀

/

刃 矩阵 的卫户 训讨



刀 可定 义成 口
\

x





,

并 选 择 尽 可能 小 的 正 整 数 人


·

使· 的



l 要 加




处 理 时 * 中有






.



子阵

.

这 些 子 阵 是 恰 好 填满 R 的
.

按行 处理 时
,

脊 二 武 子 阵 只 填 充 了刀 的 厂 行


达不 到 R 的 行数叮

即 R 的下面 部分 会有空 余
所以
,



是 允许 的

并 并 由 于一




·


)

按 行 处 理 时 子阵 的 列 数

寿 真

不 会超 出 “ 的 列数 、
.

按行

处 理 可 以 顺 利 进行

处理 后得 到的 结果 若不 必再保 留 于外 存


便 可 输 给 打 印设 备 打 印 出 结 果
,

或 送给 其 它外 围设 备作所需 要的 处理
当 于数 据 矩 阵 的 每 一 行


如 果 处理 结 果 要 保 留 在 外 存 中 则 应 将 六 的 每 一 列 ( 相 每 段含
`
=


均分成

,

`



·

冲 数据
/




显 然

·

`

; 应 等 于输 人 数 据 知 阵 的 每
,



个 子列中 的数 据个 数
t

,



令万从

:





为整数 时 全 货


容 易选 到 这 样 的 K

,

使

为 整数



当万 < 八 时

,

根据 二维 D 弃 T 的定 义
v

.

这 时 可 以 先 按行 作 变 换


.

后按 列作变换 阵





这时可

设 计算 机 内 存 每 出 只 能 处 理 卫 数K 一
,

矩阵 的

J
`



,

R 应定 义成 N



K

n

,

选择尽 可能 小的正 整

使 K 满足 关 系式。 )
2

~ 一



“ ~

~ ~

少、

`

之 K




其余 的分析过 程 和二 小 一
’ 、

万时相类f J L



J

以 ’



,





`

-

r





r ’





~

~

作者 曾用 分 列随 机存取 计算 法和分 级 计算 法在 咬 灭 D 刀乙 厂 D 兰 微 型 计 算 机 上 用 一 块 磁

盘 完成

128

/

12 8

复数矩 阵的 二 维




了了



设 内 存 每次 处 理 1 6 列和
,
.

8

列时 的 数 据 读写 遍数 和
,

处理时 间 列在 表五中
写遍 数不 变
.

当 计 算 机 内 存 每 次 处理 的 列数 减 少 时
;

分 分随 机 存 取 计 算 法 的 数 据 读 处 理 时 间显 著 增 加


处理时 间 稍有增加 表五

而 分级 计算 法的数据 读 写遍数 增 加



数据 沐写遍 数 和处理 时 间对 比 分 级 计 算法
读 写遍数
2

分 列随机 存取 计算 法

计 算 机每次 处理 列数
读写遍 数
16

处 理时 间
了分48秒 8

处理时 间
9

分 沼秒



18 秒

3

厂分 6 秒


本 文提 出的 插 入 倒 序法速 度很快 编 写程 序和 用 手 工排 列倒 序序列

.


,

适 用于 不 同 的 基 数

原 理 简单


,

方 法 容 易掌 握

,

易于

它还 可 用 于快 速沃 尔 什变换

本 文 给 出的 基

4 F 厂T

算 法 的 递 推 公 式 能 清 晰 地 反 映 出计 算 过 程 中 各 有 关 量 之 间 的 关



,

用 它 来 编 写 程 序 和 绘 制 信 号 流 图 是 很 方 便 的勺





朱明 节

:

提 高 一 维 F F T 和 大 矩阵 的 二 维 F F T 的 速 度

4
,

本 文 提 出 的 大 矩 阵 的 二 维 F F T 的 分 列 随 机 存取 计算 法 使 数 据 读 写 遍 数 减 少 到 最 小 值
因 而 处 理 速 度比 分 级计 算 法 快


这 两 种 方 法一 般 来讲 都 适 用 于 非 方 阵
,



分 列 随 机 存 取 计算 法

在 按 列 和 按 行 作 变换 时 均 可 调 用 速 度更 快 的 一 维 F F T 子 程 序



所 以 有 利 于 进 一 步提 高 速


分 级 计 算 法 则 只 是 在 按 列 作 变 换 时 ( 或 按 行 作 变 换 时 ) 才 调 用 速 度更 快 的 一 维 尸 F T 子


程序 此外 需要

再者

,

按 分 列 随 机 存 取 计算 法 编 写 程 序 很 简 单
,


,

而 按 分 级 计 算 法 编 写 程序 却 很复 杂


,

用 本 文方 法 得 到 的 输 出 矩 阵 是 转 置 的
,

而 分 级 计 算 法 则不 然

因此

.

可 以 根 据不 同 的

选 用 不 同 的 方法


. .


T
ie
u


,


n

二1 〕

J
ti

o W C

o

le y C
o

a n

d
e x

J

.

.

W
F
o u r

key

’,

A
s
,

A lg o

r

i thm

fo
u

r a

入I a
ti

e

h in
.

e

C l
.

a

lc
,

u

la
p p

-

o n

o

f
,

m pl
.

r

Se

r

ie



M

a

th

.

Co m p

t

o n

V

o

19

.

2 97一30 1
.

1 965

〔 2 〕

E

0

.

布赖 姆
“ n



,

柳群
, “




,



快速 富 里叶 变换 ”
A P P
o r o a e



〔 3 当 复旦 大 学
. .

信号 处 理 与 变 换
d
e r s s o n



[ 4 〕

G
o n a
.

L

A
a s

A T

St

e

p w i

s e

h to
a r r a
.

Co m pu tin g M
y
s
,

u

ltid im
r a n s
.

e n s

i

-

l F 5 p

t

F

o u r

ie

r

r a n s

fo
r

r

m

f

L
,

a r

g

e



IE E E
,

T
3

A

e o u

-

5

t

,

e e e

h

,

a n

b S ig

n a

l p

o e e s s

in g

V

o

l A S S P一 28

N

o

.

Ju

n e

198 0

.

T
a n

o

Ra is
o

e

T he Sp e e d

o

f o

n e

一im
o

e n s

io

n a

l F FT
tr ie
e s

.

d T w

一i m
a r

en s

io
o

n a

l FFT

f L

a r

ge
g in

Ma
e e r

(D e p

tm

e n

t

f
Zh
u

E l e e t r ie a l E
M in
g
,

n

in g )

ji e
t

Ab` t r
A bs t
n s
r a e

a e

t



I

n e

t

h is dis

p

a

p

e r

,

t

h A

e

fa
n e
e r s e
n

e

t

o r s

w hie h
e

a

ff

e e

t

t

h

e

s

p
n

e e

d
a

o

f

o n e



dim

e

-

io

n a

l

F FT
in g
s a

a r s e

e u s s e

d
o

.

w

m
o r

t h
r

o

d
15

e a

lle d i
P
a

n s e r
.

ti

g
t

Pp
o

r o a e
r

h

fo
io
i
e

r

r e o r

d
u

e r

q
a

u e n e e x


in t

r e v a

d

de
e

p

r o

o s e

d

A
ith m
.

s e
,

f
i
s a

e e u r s
n

n n
,

fo
r

r

m

la

fo
o r

r

r

di
a n

4
o u

d

e c

im
u
r

t io

in
t
u r

ti
a e

m l
s

( D IT )
de
d
r
,

lg
gi

o r

w ith
t

P
e

u

t

s

e v e r s e e s

d

d

e r e
,

d
o

t p

t

s

i

n

n a

o r

a r e

v e n a

A t
o r

h

e

m

t im

s o

m

i m P le

m
te

t

h

ds

fo

r a

is in 且 th

P

e e

o

f

FF T

lg

it hm

s

a r e

di

s e u

-

S s e

d

a n

d t

e s

d

.

:

.
.

4

8


n


f
a e


o r




a


e e

19
t

82 年

I
o n a
r a n

ist h
o

a

P
a
a

r

,

P et h

e

m
e

a

i
a

n

t

w hie h
a

ff

t

s

h


e

s

p

e e

d
w
a

o

f m

tw
e
,

o



dim
,

e n s

i

-

l

F FT

f

la
p p

r

g

m h by
f

t
s

r

ix

15
n
e

ls
e o

o

dise
n s

u s s e

d

A
la
r

n e
e

t

hod

e a

lle d m i
-

do m
e s

a e e e s s

r o a e

Plit ti
r

g

lu m

o

f

a

g

m
e

t

r

ix
a

w h ie h
o

n

im iz
a

t

h

e

n u e e n

mb
in t

e r

o

r e a e

d /w
m
o r

it

P

a s s e s

t

h
e

r o u

gh

t h
o

de t
c o

f
,

a

la
P

r

g
r o

e
·

m
P

t

r

i
.

x

b

e

tw

e r n a

l m

y

a n

d

f ile

m

m

o r



·

f

a

m Pu t

e r

15

o s e

d

.
.

:

.


推荐相关:

提高一维FFT和大矩阵的二维FFT的速度_朱明节_图文.pdf

提高一维FFT和大矩阵的二维FFT的速度_朱明节_数学_自然科学_专业资料。1

一维FFT二维FFT.doc

摘要本文介绍了一维 FFT 和二维 FFT 的产生背景及其计算方法, 快速傅里叶变换与离散傅里 叶变换相比,计算速度有了数量级上的提升,是信号与图像领域中,不可缺少...

提高FFT和谱分析速度及精度的方法_图文.pdf

提高FFT和谱分析速度及精度的方法 - 第 年月 卷第 期 重 庆 大 学 学 报 , 冲 提高 和 谱分 析速度及精度的方法 , ‘ ! 丁 康...

对二维FFT的详细介绍及实验.doc

图象频谱中心从矩阵的原点移到矩阵的中心, 其语法...当数据长度是 2 的幂次时,计算速度显著增加,因此,...一维FFT二维FFT 12页 1下载券 C语言实现FFT(快速...

离散二维FFT(IFFT)变化.txt

离散二维FFT(IFFT)变化_数学_自然科学_专业资料。k...k=round(m/2); %m,n为源输入矩阵的行数和列数...(2*k))); end end %一维傅里叶反变化 k=...

matlab效率提升独孤九剑(附fft优化的详细例子).doc

matlab效率提升独孤九剑(附fft优化的详细例子)_计算机软件及应用_IT/计算机_专业...尽量用列向量进行操作: 因为 matlab 的矩阵是按列存放的,对其进行存取的速度比...

二维FFT算法在LFMCW雷达信号处理中的应用及其性能分析_....pdf

二维FFT算法在LFMCW雷达信号处理中的应用及其性能分析_信息通信_工程科技_专业资料。这个是二维fft在导引头上的引用,很有价值 二维「 算法在 「 雷达信号 处理中...

超长点数FFT的设计与实现技术_图文.pdf

在这种情况下,二维FFT算法可以将一 维大点数FFT转化...有效地提高了处理速度,实现了 4.090ms内完成256k点...运算过程中数据需 要进行多次矩阵转置和数据跳变,在...

二维FFT在TMS320系列DSP中的实现.pdf

数据以解决数据交换的瓶颈问题 ,提高运 算速度 。 ...312 使用乒乓缓冲技术在完成一维 FFT 的同时并行实现...其转置要按分块矩阵的转置方法来实现 ,首先 ,各 ...

20140425-超长点数FFT的设计与实现技术_郭骁_图文.pdf

在这种情况下, 二维 FFT 算法可以将一 维大点数 ...FFT,有效地提高了处理速度,实现了 4. 090ms 内...运算过程中数据需 要进行多次矩阵转置和数据跳变, ...

FFT专用芯片的应用.pdf

FFT 的硬件结构 研制成 FFT 专用芯片 因而获得广泛应用 FFT 的运算速度 极大...一维数据序列排成二维数据矩阵 然后将 FFT 分解为对矩阵的列和行分别进行 FFT ...

2.1 FFT变换_图文.ppt

函数fft:用于进行一维离散傅立叶变换(DFT) ? 函数fft2 :用于进行二维DFT ? ...因而DCT的计算速度比 DFT快得多 图像的离散余弦变换 DCT矩阵的左上角代表低频...

二维FFT算法在LFMCW雷达信号处理中的应用及其性能分析_....pdf

一维 , FFT 的结 果 故理论 上不 模 糊距 离..., 当 , T 很小如果 M 和 N 都很 大时 T ...。 这里 主要 考虑中 间结果 数 FFT , , 3 o...

快速傅里叶变换(FFT)_图文.ppt

如果x是一个矩阵,那么fft(x,N)计算x中每一列的...由图 4.2.4可以看出, DIT—FFT 的运算过程很有规...

大点数FFT算法的改进及其实现_图文.pdf

""# 算法, 速度与基 W 或基 X ""# 算法相近...)(-) 矩阵的元素为复数 + !! ) 。因’" 行...大点数FFT的多DSPs并行处... 4页 免费 FFT快速...

基于FFT的阵列方向图快速计算.pdf

FFT 算法 和直接用公式计算阵列方向图的运算速度。在本文 分析的基础上可进一步讨论二维 FFT 技术 , 并...图的邻接矩阵以及度的计... 4页 3下载券 阵列...

二维FFT的FPGA实现_图文.pdf

增加 , 能处理大 容量数据的 2D - FFT 处理器...快二维 FFT 的运算速度 [9 ] . 所以, 一维傅里...在具体的实现中我们利用矩阵存储数据 , 处理 完一次...

DFT与FFT计算速度比较分析.doc

DFT FFT 计算速度比较分析 系 别: 工业自动化...FFT 的运算时间比较 设计要求 利用 Matlab 或者 C ...维矩阵 %DFT 矩阵 %DFT 系数的行向量 变换( 对...

基于二维图像的FFT算法实现.doc

基于二维图像的 FFT 算法实现 1 摘要 FFT 算法基本...DFT 的运算次数大大减少,可以使运算效率极大提高。...(第二版)丁玉美 P104 %输入 x 为一维矩阵 ...

GPU-FFT总结.doc

量级, 大大提高了 DFT 的运算速度, 从而使 DFT 在实际应用中得到了广泛的...(data); 二维 FFT 算法的 CUDA 实现二维 FFT 算法实现中,同一维 FFT 不同...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com