JPS5925253B2 - 余弦・正弦演算方式 - Google Patents

余弦・正弦演算方式

Info

Publication number
JPS5925253B2
JPS5925253B2 JP53114346A JP11434678A JPS5925253B2 JP S5925253 B2 JPS5925253 B2 JP S5925253B2 JP 53114346 A JP53114346 A JP 53114346A JP 11434678 A JP11434678 A JP 11434678A JP S5925253 B2 JPS5925253 B2 JP S5925253B2
Authority
JP
Japan
Prior art keywords
storage area
cos2
sin2
storing
cosine
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired
Application number
JP53114346A
Other languages
English (en)
Other versions
JPS5541525A (en
Inventor
健三 平岩
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP53114346A priority Critical patent/JPS5925253B2/ja
Publication of JPS5541525A publication Critical patent/JPS5541525A/ja
Publication of JPS5925253B2 publication Critical patent/JPS5925253B2/ja
Expired legal-status Critical Current

Links

Landscapes

  • Complex Calculations (AREA)

Description

【発明の詳細な説明】 本発明は、フーリエ変換処理に際して使用する所定角の
余弦及び正弦値を求める方式に係り、特にパイプライン
処理により高速で該余弦、正弦植木める方式に関する。
フ 離散型フーリエ変換において、データが複素数であ
る場合には(1)式の変換又は(2)式の逆変換の演算
処理が必要となる。
ln二1 αに−一ー2−Xjexp(−2 nj=0 Xj=−2△αkexp(2πi− レ■n 、jk l−)、に゛0、゜゜゜、n−1゜゜゜゜゜゜(l))
、j−0、…、n−1……(2)尚、(1)式のフーリ
エ変換において、Xjは複素データ、αkはフーリエ係
数であり、以後(1)式の変換に従つて説明する。
今、データ数を8個(XO..Xl、・・・X7)とす
ればn−8となり、(1)式のフーリエ変換には8種類
の角度0、θ、2θ、3θ、・・・7θ(但しθ−2π
/8)に対する各余弦正弦値が必要となる。ところで、
θ、2θ、・・・7θの余弦、正弦を求めるには以下の
(3)、(4)式に示す漸化式を用いる方法が考えられ
る。
但し、K−011、2、・・・7 すなわち、θに対する余弦及び正弦値COsθ、Sin
θを予め求めておき、これらCOsθ、Sinθを用い
てCOs(K+1)θ、Sin(K+1)θ(K−1、
2、・・・7)を次々と求める方法である。
しかし、この方法では非常に長い演算処理時間を要し、
高速フーリエ変換ができない。というのは、COsθ、
Sinθから、まずCOs2θ、Sin2θを演算し、
ついでこれらの値を使つてCOs3θ、Sin3θを演
算し、以後同様にCOs(K+1)θ、Sin(K+1
)θを求めてゆかなければならないからであり、換言す
れば上記(3)、(4)式に基いて00sKθ、Sin
Kθを求めるには、いわゆる高速演算処理の公知の手法
であるパイプライン処理が適用できない。それ故、本発
明はパイプライン処理に基いて高速にCOsθ、Sin
θから、COs(K+1)θ、Sin(K+1)θ(K
−1、2、・・・7)を求めることができる新規な方式
を提供することを目的とするものであり、この目的は本
発明において、COsθ、SinθよりCOsKθ、S
inKθ(K−2、3、・・・n)を演算する演算方式
において演算された各角度θ、2θ、3θ、・・・nθ
に対応する余弦、正弦値を記憶する記憶手段、COsθ
とSinθ及び倍角の公式に基いてCOS2mθ、Si
n2mθ(m1、2c・・)を順次演算し、これを前記
記憶手段に記憶せしめる演算手段、前記記憶手段の所定
アドレスから順次入力された余弦、正弦データを該記憶
手段の別のアドレスにシフトせしめる第1のパイプライ
ン処理手段、前記シフト処理後記憶手段から人力された
余弦、正弦データを用いて加法演算処理を実行し、その
演算結果を前記記憶手段に格納する第2のパイプライン
処理手段を備え、前記記憶手段の記憶領域を{COS2
mθ、Sin2mθ}を記憶する記憶領域T1;{CO
S2nl−1θ、Sin2nl−1θ}、{COS2n
lθ、Sin2mθ}を記憶する記憶領域T2;{CO
s2m−2θ、Sin2m−2θ}、{COs2m−1
θ、Sin2m−1θ}、{COs(2m−2+2m−
1)θ、{COS2mθ、Sin2mθ}を記憶する記
憶領域T3;{COs2m−3θ、Sin2m−3θ}
、{COS2rrl−2θ、Sin2nl−2θ}、{
COs(2m−3+2m−2)θ、Sin(2m−3+
2m−2)θ}、{COs2m−1θ、Sin2m−1
θ}、{COs(2m−3+2n1−1)θ、Sin(
2n1−3+2m−りθ}、{COS2mθ、Sin2
mθ}を記憶する記憶域T4;・・・;{COsθ、S
inθ}、{COs2θ、Sin2θ}、{COs3θ
、Sin3θ}・・・{COsnθ、Sinnθ}を記
憶する記憶領域T1に分け前記第1のパイプライン処理
手段は記憶領域Tiの各アドレスの内容を記憶領域Ti
+1の偶数領域に順次シフトし、前記第2のパイプライ
ン処理手段は記憶Tiの第1アドレスと偶数番目のアド
レスの内容を用いて順次加法演算処理を実行し、その演
算結果を逐次、Tiの奇数番目のアドレスに書込む処理
を実行し、前記演算手段によりCOS2mθ、Sin2
nlθ(m−1、2、゜゜゜)を演算後、TiからTi
+1への前記シフト処理と加法演算処理を交互に繰返え
し実行しCOsKθ、SinKθ(K−2、3、・・・
n)を求める余弦、正弦演算方式により達成される。
以下、本発明を図面に従つて詳細に説明する。
さて、(3)、(4)式をマトリクスとベクトルで記述
すると、但し、 こ\で、 θの回転因子という)とおけば(5)式は更に次の如く
表現できる。
従つて、W1、W2・・・Wkが求まればX1と乗算し
て簡単にXk+1を求めることができる。
次に、K−8として、W−W8までの回転因子を求める
アルゴリズムを第1図に従つて説明する。
尚、このアルゴリズムは後述するようにパイプライン処
理に適している。図中、wは回転因子、W2、・・・W
8は回転因子wの巾、T1〜T4は記憶領域である。
ステツプ1・・・まず、初めに記憶領域T1に8個のw
を用意する。
ステツプ2・・・次に、上記8個のwのうち各隣接する
2つのwを乗算することによりW2を4個作成し、記憶
領域T2に格納する。
ステツプ3・・・この4個のW2のうち、各隣接する2
つのW2を乗算することによりW4を2個作成し記憶領
域T3に格納する。
ステツプ4・・・次にこの2個のW4を乗算することに
よりW8を作成し、記憶領域T4に格納する。
以上、ステツプ1〜4においては、すべて、記憶領域T
lの隣接する2つの回転因子又はこれらの巾に乗算を施
し、記憶領域Ti+1に格納する処理である。このため
高速演算処理として公知の手法であるパイプライン処理
が適用できる。ステツプ5・・・記憶領域T3の第2領
域に記憶領域T4の第1領域の内容即ちW8をシフトす
る。これにより記憶領域T3にはW4とW8とが記憶さ
れる。ステツプ6・・・記憶領域T2の第2領域と第4
領域にそれぞれ記憶領域T3の第1、第2領域の内容W
4、W8をシフトした後、第1領域と第2領域の内容即
ち席とW4とを乗算して1を作成し、T2の第3領域に
格納する。
尚、W8出ψとからこれらに除算を施して1を作成する
こともできる。
これにより、記憶領域T2の第1、2、3、4領域には
それぞれW2、W4、W6,.W8が格納されたことに
なる。ステツプ7・・・最後に、記憶領域T1の第2、
4、6、8領域に記憶領域T2の第1、2、3、4領域
の内容W2、W4、W6.W8をシフトした後、第1領
域と第2領域の内容wとW2に乗算を施し、又、第1領
域と第4領域の内容wとW4に乗算を施し、更に第1領
域と第6領域の内容w昌ψに乗算を施し、それぞれの乗
算結果をT1の第3、5、7領域に格納する。これによ
り、記憶領域T1の第1、第2、・・・第8領域にW.
W2、・・・W8が得られることになる。以上、ステツ
プ5〜7においては記憶領域Tiの各領域の内容を夫々
順次記憶領域Ti−1の偶数領域に格納した後(シフト
処理)、Ti−1の第1領域の内容とTi−1の各偶数
領域の内容との乗算を順次実行し、その乗算結果をT1
−1の奇数領域に順次記憶格納する処理であり(演算処
理)、高速演算処理としての公知の手法であるパイプラ
イン処理に好適である。
しかし、上記処理はパイプライン処理が可能であるとし
ても各乗算はマトリクス乗算であり、従つてマトリクス
要素同士の8回の乗算と4回の加算が必要となり、高速
処理ができない。
ところで、W2、W3の乗算結果は夫々、次式の如くな
る。
即ち、W2、W3はそれぞれ、COs2θ、Sin2θ
:COs3θ、Sin3θで表わすことができ、一般に
WkはCOsKθ、SinKθが計算できれば簡単に求
まる。
本発明はCOsKθ、SinKθ(K=2、3、・・・
n)を、前述のWkを求めるアルゴリズムとほぼ同一の
手法により求めるものであり、以下第2図、第3図に従
つて説明する。
第2図においてMEMは余弦、正弦値を記憶する主記憶
装置、PLUlは後述の三角関数の倍角演算を実行する
倍角演算装置、PLU2は後述のシフト処理を実行する
第1のパイプライン処理装置、PLU3は三角関数の加
法演算処理を実行する第2のパイプライン処理装置、G
Mはゲート手段、COTは1主記憶装置からの余弦、正
弦データの読出及び書込順序、2PLU1,PLU2,
PLU3を制御していずれを処理可能にするか、3ゲー
ト手段GMを制御してPLUl,PLU2,PLU3の
うちどの出力データを主記憶装置に書込むかをコントロ
ールする制御回路である。
第3図は本発明による処理をより理解し易くするための
説明図であり、図中、MEMは主記憶装置、MCぱCO
sKθを記憶する記憶領域、MSはSinKθを記憶す
る記憶領域、T1〜T4は第1図における符号と同一の
領域を示す記憶領域、PLUlは、倍角演算装置、PL
U2はシフト処理のパイプライン処理装置、PLU3は
加法演算処理のパイプライン処理装置である。尚、第1
図においては、ステツプ1で記憶領域T1の第1、・・
・、第8領域にwを8個用意して以後、ステツプ2、3
、4においてW2、W4、W8を次々と求め各記憶領域
に格納するものとして説明したが、このような処理にパ
イプライン処理を施しても高速処理としての効果は上ら
ないため、第2図では、ステツプ1〜ステツプ4までの
処理をパイプライン処理によらず倍角演算装置PLUl
により個別にCOs2x,.sin2x;COs4xl
sin4x;COs8xl8ln8xを求めている。
しかし、第1図のアルゴリズムに従つて、求めてもよい
ことは当然である。ステツプ1・・・主記憶装置MEM
の余弦記憶領域及び正弦記憶領域MC,MSのアドレス
T1(1)にCOsθ、Sinθを用意する。
尚、図中斜線部は処理に関係したデータを表示している
。ステツプ2・・・MC,MSのアドレスT1(1)の
内容を倍角演算装置PLUlに読出す。
該倍角演算装置PLUlはMC,MSより読出された内
容を(MC)、(MS)とすれば次式の演算を実行し、
その演算結果を別に指示されたMC,MSの所定アドレ
スに記憶する処理を実行する。即ち、(代)式よりCO
s2θ、(自)式よりSin2θが演算されそれぞれ余
弦、正弦記憶領域MC,MSのアドレスT2(1)に記
憶される。
ステツプ3・・・MC,MSのアドレスT2(1)の内
容を倍角演算装置PLUlに読出し、(代)、σDの演
算を実行させ、その演算結果、COs4θ、Sin4θ
をMC,MSのアドレスT3(1)に格納する。
ステツプ4・・・MC,MSのアドレスT3(1)の内
容を倍角演算処理装置PLUlに読出し、(代)、(自
)の演算を実行させ、その演算結果COs8θ、Sin
8θをMC,MSのアドレスT4(1)に格納する。以
上、ステツプ1〜4により、余弦、正弦記憶領域の内容
は第2図イのようになる。ステツプ5・・・ シフト処理・・・MC,MSの記憶領域T4のアドレス
T4(1)の内容をシフト処理のパイプライン処理装置
PLU2に読出す。
該パイプライン処理装置PLU2は余弦、正弦記憶領域
MC,MSに対しそれぞれ記憶領域Tiの各領域Ti(
1)、Ti(2)、Ti(3)・・・の内容を記憶領域
Ti−1の偶数領域Ti−1(2)、Ti−1(4)、
Ti−1(6)・・・にシフトするようにパイプライン
処理を実行する。従つて、MCのアドレスT4(1)の
内容COs8θはMCのアドレスT3(2)に、MSの
アドレスT4(1)の内容Sin8θはMSのアドレス
T3(2)にシフトされる。
(第3図口参照)ステツプ6・・・ シフト処理・・・ステツプ5と同様にMC,MSの記憶
領域T3の内容T3(1)、T3(2)即ちCOs4x
.lsin4x;COx8x.sin8xを順次、パイ
プライン処理装置PLU2に入力し、これをそれぞれM
C,MSf)T2(2)、T2(4)にシフトする。
この結果、余弦正弦領域の内容は第3図ハのようになる
。ステツプ7 加法演算処理・・・上記シフト処理が終了すればMC,
MSに対して、記憶領域T2(1)、T2(2)がそれ
ぞれ対になつて加法演算のパイプライン処理装置PLU
3に読出される。
MCの記憶領域Tiの第1領域Ti(1)より読出した
内容を{MCTi(1)}、MCの記憶域Tiの偶数領
域Ti(2n)より読出した内容を{MCTi(2n)
}、MSの記憶域Tiの第1領域Ti(1)より読出し
た内容を{MSTi(1)}、MSの記憶Tiの偶数領
域Ti(2n)より読出した内容を{MSTi(2n)
}とすれば、パイプライン処理装置PLU3は次式の演
算を実行し、その演算結果をそれぞれMC,MSの記憶
領域Tiの奇数領域Ti(2n+1)に格納する。即ち
、(自)式によりCOs6θ、(自)式によりSin6
θがそれぞれ演算されMC,MSの記憶領域T2の第3
領域T2(3)にそれぞれ記憶される(第3図二参照)
ステツプ8・・・ シフト処理・・・ステツプ6と同様にMC,MSの記憶
域T2(1)、T2(2)、T3(2)、T3(1)、
即ち、COs2x,.sin2x;COs4x,.si
n4x;COs6x,.sin6x;COs8x,.s
in8xを順次パイプライン処理装置PLU2に入力し
、該パイプライン処理装置により、これらを順次MC,
MSの記憶領域T1の偶数領域、即ち第2、第4、第6
、第8領域Ti(2)、T1(4)、T1(6)、T1
(8)にシフト格納する(第3図ホ参照)。
ステツプ9・・・ 加法演算処理・・・ステツプ7の処理と同様にMC,M
Sの記憶領域T1の第1領域T1(1)、第2領域T1
(2);第1領域T1(1)、第4領域T1(4);第
1領域T1(1)、第6領域T1(6)が順次パイプラ
イン処理装置PLU3に読出され、それぞれA2).0
3)式の演算が施されてその演算結果が逐次記憶領域T
1の第3、第5、第7領域T1(3)、T1(5)、T
1(7)に格納され第2図へに示す如くCOsθ、Si
nθ;COs2θ、Sin2θ・・・;COs7θ、S
in7θ,COs8θ、Sin8θがMC,MSの記憶
領域T1に得られることになる。
(第3図へ)以上、本発明ではCOsKθ、SinKθ
(K−1、2、・・・n)をシフトのパイプライン処理
と加法演算のパイプライン処理を実行することにより、
次次と求めることができ、極めて高速度でCOsKθ、
SinKθを得ることができる。
そして、COsKθ、SinKθから回転因子w及びそ
の巾を簡単に得ることができその効果は大きい。尚、上
記説明ではCOs8θ、Sin8θまで求めたが全く同
じ手法でCOsKθ、SinKθ(Kは8より大なる整
数)を得ることができる。
【図面の簡単な説明】
第1図は回転因子wを求めるアルゴリズムを説明する図
、第2図は本発明によりCOsKθ、SinKθを得る
説明図である。 MEM・・・・・・主記憶装置、MC・・・・・・余弦
記憶領域、MS・・・・・・正弦記憶領域、Tl,T2
,T3,T4・・・・・・記憶領域、PLUl・・・・
・・倍角演算装置、PLU2・・・・・・シフトのパイ
プライン処理装置、PLU3・・・・・・加法演算のパ
イプライン処理装置。

Claims (1)

    【特許請求の範囲】
  1. 1 coSθ、sinθよりcosKθ、sinKθ(
    K=2、3、…n)を演算する演算方式において演算さ
    れた各角度θ、2θ、3θ…nθに対応する余弦、正弦
    値を記憶する記憶手段、cosθとsinθ及び倍角の
    公式に基いてcos2^m′θ、sinn2^m′θ(
    m′=1、2、…m但しn=2^m)を順次演算し、こ
    れを前記記憶手段に記憶せしめる演算手段、前記記憶手
    段の所定アドレスから順次入力された余弦、正弦データ
    を該記憶手段の別のアドレスにシフトせしめる第1のパ
    イプライン処理手段、前記シフト処理後記憶手段から入
    力された余弦、正弦データを用いて加法演算処理を実行
    し、その演算結果を前記記憶手段に格納する第2のパイ
    プライン処理手段を備え、前記記憶手段の記憶領域を{
    cos2^mθ、sin2^mθ}を記憶する記憶領域
    T_m_+_1;{cos2^m^−^1θ、sin2
    ^m^−^1θ}、{cos2mθ、sin2^mθ}
    を記憶する記憶領域Tm;{cos^m^−^2θ、s
    in2^m^−^2θ}、{cos2^m^−^1θ・
    sin2^m^−^1θ}、{cos(2^m^−^2
    +2^m^−^1)θ、sin(2^m^−^2+2^
    m^−^1)θ}、{cos2^m^θ、sin2^m
    θ}を記憶する記憶領域T_m_−_1;{cos2^
    m^−^3θ、sin2^m^−^3θ}、{cos2
    ^m^−^2θ、sin2^m^−^2θ}、{cos
    (2^m^−^3+2^m^−^2)θ、sin(2^
    m^−^3+2^m^−^2)θ}、{cos2^m^
    −^1θ、sin2^m^−^1θ}、{cos(2^
    m^−^3+2^m^−^1)θ、sin(2^m^−
    ^3+2^m^−^1)θ}、{cos2^mθ、si
    n2^mθ}を記憶する記憶域T_m_−_2:…;{
    cosθ、sinθ}、{cos2θ、sin2θ}、
    {cos3θ、cos4θ}…{cosnθ、sinn
    θ}を記憶する記憶領域T_1に分け、前記第1のパイ
    プライン処理手段は記憶領域Tiの各アドレスの内容を
    記憶領域Ti+1の偶数領域に順次シフトし、前記第2
    のパイプライン処理手段は記憶Tiの第1アドレスと偶
    数番目のアドレスの内容を用いて順次加法演算処理を実
    行し、その演算結果を逐次、Tiの奇数番目のアドレス
    に書込む処理を実行し、前記演算手段によりcos2^
    mθ、sin2^mθ(m=1、2、…)を演算後、T
    iからT_i_+_1への前記シフト処理と加法演算処
    理を交互に繰返えし実行しcosKθ、sinKθ(K
    =2、3、…n )を求めることを特徴とする余弦、正
    弦演算方式。
JP53114346A 1978-09-18 1978-09-18 余弦・正弦演算方式 Expired JPS5925253B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP53114346A JPS5925253B2 (ja) 1978-09-18 1978-09-18 余弦・正弦演算方式

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP53114346A JPS5925253B2 (ja) 1978-09-18 1978-09-18 余弦・正弦演算方式

Publications (2)

Publication Number Publication Date
JPS5541525A JPS5541525A (en) 1980-03-24
JPS5925253B2 true JPS5925253B2 (ja) 1984-06-15

Family

ID=14635453

Family Applications (1)

Application Number Title Priority Date Filing Date
JP53114346A Expired JPS5925253B2 (ja) 1978-09-18 1978-09-18 余弦・正弦演算方式

Country Status (1)

Country Link
JP (1) JPS5925253B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS60137839U (ja) * 1984-02-24 1985-09-12 プルトンチエン株式会社 スライドレ−ルにおけるロツク機構

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS58213411A (ja) * 1982-06-07 1983-12-12 Ikari Kosan Kk 自動半田付装置
WO2004068365A1 (ja) * 2003-01-29 2004-08-12 Fujitsu Limited フーリェ変換装置

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS60137839U (ja) * 1984-02-24 1985-09-12 プルトンチエン株式会社 スライドレ−ルにおけるロツク機構

Also Published As

Publication number Publication date
JPS5541525A (en) 1980-03-24

Similar Documents

Publication Publication Date Title
Mori et al. The double-exponential transformation in numerical analysis
Watson Numerical linear algebra aspects of globally convergent homotopy methods
US7337205B2 (en) Matrix multiplication in a vector processing system
Dellnitz et al. Locating all the zeros of an analytic function in one complex variable
Fournais et al. Accurate eigenvalue asymptotics for the magnetic Neumann Laplacian
CN101836202B (zh) 快速傅立叶变换/反快速傅立叶变换运算核
Stoer Curve fitting with clothoidal splines
JPS5925253B2 (ja) 余弦・正弦演算方式
Wyman Explicit bounds on integrals of eigenfunctions over curves in surfaces of nonpositive curvature
Lee et al. L p-L q estimates for the circular maximal operator on Heisenberg radial functions
Koh et al. A sharp exponent on sum of distance sets over finite fields
US20230299751A1 (en) Interpolation filter device, system and method
Venkataramanan et al. Estimation of frequency offset using warped discrete-Fourier transform
CN115801145A (zh) 一种混合信号的时延估计方法、装置和电子设备
JP3709291B2 (ja) 高速複素フーリエ変換方法及び装置
US6460062B1 (en) Discrete cosine transformation circuit
Bucy et al. Determination of steady state behavior for periodic discrete filtering problems
Burnham Nonfactorization in subsets of the measure algebra
Liu Modified Gram–Schmidt-based methods for block downdating the Cholesky factorization
Simmons Root projection of one-sided time series
Titus A general card-program for the evaluation of the inverse Laplace transform
Sauer Multivariate B-splines with (almost) arbitrary knots
SU796844A1 (ru) Арифметическое устройство
JPS6029409B2 (ja) 三角関数計算装置
Manni A general parametric framework for functional tension schemes