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的二维算法FPGA并行实现_图文.pdf

这样不但解决了FPGA的IP核计算FFT点数少的问题,而且提高FFT计算的速度。仿 ...的二维信号处 理方法,将一维的大点数FFT算法转换成为适用于 矩阵应用的二维FFT...

一维FFT二维FFT.doc

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

基于FFT的大型平面阵列方向图的综合方法.pdf

该方法大大节省了优化时间 , 提高速度 。()AF=...子矩阵1 和子矩阵 F 矩阵从中心分为4 个子矩阵 ...u=-0.07 6时的一维方向图 , 1.4 二维 FFT 的...

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

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

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

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

FPGA与DSP在二维FFT变换应用中的对比研究_图文.pdf

FPGADSP在二维FFT变换应用中的对比研究陈路林,许骏...在计算技术上, 这些控制都表现为大矩阵的高速运算。...次一维FFT(行)变换,然后再进行另外M次 一维FFT(列...

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

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

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

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

2.1 FFT变换_图文.ppt

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

GPU-FFT总结.doc

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

FFT的研究历史及其现状.doc

其运算量显著减少, 用计算机实现 时速度大为提高。...FFT 算法为例, 简要介绍传统 FFT 的思路大致算法...确定的变换矩阵、准最佳变换性能外,二维 DCT 还 是...

基于FPGA的大点数FFT算法研究_论文.pdf

基于FPGA的大点数FFT算法研究_信息与通信_工程科技_专业资料。由于高速实时信号处理对大点数FFT的需要,很多设计都采用将大点数的一维序列转化为矩阵的二维FFT方法来...

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

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

76800点fft算法实现.doc

针对这一问题,借鉴图像处理中的二维信号处理方法,将一维的大点数 FFT 算法转换成为适用于矩阵应用的二维 FFT 算法。在 FPGA 中设计并实现了并行处 理, 在增加...

FFT专用芯片的应用.pdf

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

信号处理 FFT与IFFT的实际应用程序设计与调试.doc

掌握二维 FFT 算法原理,掌握利用二维 FFT 与 IFFT ...从而很容易地了 解到图像各空间频域成分,进行相应...再存入矩阵 A 中*/ /*再逐列进行一维-FFT*/ ...

二维FFT的程序实现及其应用.doc

方法)中,由逼近方法导出的代数方程组中系数矩阵 基本上是满的,求解计算量太大...本文分析了一维 FFT 算法及二维 FFT 算法,并给出了相应的程序和实例。 [关键...

基于CUDA的矩阵乘法和FFT性能测试.pdf

基于CUDA的矩阵乘法和FFT性能测试_工学_高等教育_教育专区。CUDA GPU第...FFTW 能自动适应 CPU 环境,可移植性强,运行速度 快,可 进行 一维和多 维的...

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

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

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