離散フーリエ変換の式と演算回路について

Question

離散フーリエ変換の式をアセンブリ言語に変換した時に気になったのですが、どのようにして演算回路から離散フーリエ変換を計算した時と同じ結果を導いているのでしょうか？
離散フーリエ変換の式の結果と同じになるように演算回路に流すためのデータを工夫しているのでしょうか？ 離散フーリエ変換の式をデータ化するのではなく、離散フーリエ変換と同じ答えが演算回路から出るようなデータを使っているのでしょうか？

Answer 1

質問意図を外しているような気もしますが・・・

どのようにして演算回路から離散フーリエ変換を計算した時と同じ結果を導いているのでしょうか？

高級言語のコード、プロセッサーのネイティブな機械語でのコード（アセンブリー言語も要するに機械語に相当するものです）、さらにはもっと低水準な論理回路のどういったもので表現しても本質的にはそこにあるのは「入力から出力を得るための論理」であることは同じです。

低水準な層から見た場合「ある瞬間のシステムの状態から、次の瞬間のシステムの状態をどう変化させるか」の一連の規則（論理）がプログラミングや論理回路の設計の本質と思いますので、記述する内容が低水準か高水準かの違い、言い換えれば同じことを表現する手間が多いか少ないかの違いだけであって究極的には何を用いても同様のことが計算できるという点では同じ能力を持っています。多分そういうことを一言でいうと「どれもチューリング完全なもの」という言い方になるのでしょうか・・・

離散フーリエ変換の式の結果と同じになるように演算回路に流すためのデータを工夫しているのでしょうか？ 離散フーリエ変換の式をデータ化するのではなく、離散フーリエ変換と同じ答えが演算回路から出るようなデータを使っているのでしょうか？

そういう理解（あるいは表現）ではなく、「その回路による論理が離散フーリエ変換を計算するようなものになっている」と捉えるのが自然であると思います。ひょっとしたら質問者さんは「回路の結線」などによる回路の論理のことを「データ」と表現されているのかも知れません。そういう意味なら「離散フーリエ変換と同じ答えが演算回路から出るようなデータを使っている」といっても間違いとは言えないでしょうが、多くの人にとってデータという表現は「一番自然な表現」とは感じられず論理と表現した方が自然に聞こえる気がします。

---

例えば1bitの加算をすることは高級言語でなら

r = a + b

とかけ、これはこれで一つの論理ですし、それをハードウェアで実現した

https://ja.wikipedia.org/wiki/加算器

のようなものでは回路の部品や結線の具合はデータというより「論理」と捉えた方がよいように思います。

---

追記：

離散フーリエ変換の計算をするためだけの論理回路ではないのに、どのように演算回路を工夫して使う事で離散フーリエ変換の計算と同じ答えを導いているのか

なるほどそちらの方ですか。
汎用プロセッサの場合、おっしゃるように特定目的の演算（本例では離散フーリエ変換）を直接実装した回路を備えているわけではありません。一定のビット数の符号有り/無しの両方の整数の四則演算や論理演算（和・積・排他的論理和・否定）、浮動小数点数の四則演算（や多分初等関数のいくつかも？）などの演算ができるだけですが、計算機能に加えてとても重要な機能が付いています。それは「メモリーに格納されている命令語を順番に読み込みながらそれに従って任意の演算回路を駆動する能力」、またそれからの必然ですが「どこから命令を読むかを変更したりするメタな命令（分岐など）」、つまりプログラマブルな機構を備えています。このような仕組みの計算機のことを発明した人（？）にちなんでフォン・ノイマン型計算機などと呼ぶと思います。

こういう構成の計算機は「直接実行できる演算は単純なもののみ」なのですがそれを「命令語」による指示によって任意に組み合わせていかなるル論理も達成できるようになっている点がミソです。プログラマーの多くはそういう低水準なレベルでの「命令語（＝機械語）と、個々の演算を実行するハードウェアによる論理回路」を全て合わせて「プログラムの目的を達成するための論理」として考えたり、それよりはむしろハードウェアの演算回路を「汎用計算機に組み込まれている基本機能」と捉え論理の一部であるとはあまり意識せずに、実行を駆動する中心になる命令語の列（＝ソフトウェア）を「計算論理」として捉えることが多いと思います。

こういうやや複雑な構成になっているのは「論理を組み上げたり設定するのがハード結線により回路を組み上げるよりはるかに容易・柔軟」なためです。離散フーリエ変換の計算をする論理回路を組むことはできますが、その回路を離散フーリエ変換意外の目的にも使えるような論理にするのは大変複雑で困難な仕事になると思います。そういうわけで「どんなふうにでも論理を自由に組めるように」フォン・ノイマン型計算機（プロセッサー）を使えるようにしたのが汎用計算機です。

最初の回答で「データというより論理と捉えた方が」とコメントしましたが、フォン・ノイマン型の計算機の低水準な仕組みに着目して話をする場合は「命令語、即ちデータによって論理を駆動する」というような理解の仕方もすると思います。そういうレベルで話をするのなら

離散フーリエ変換と同じ答えが演算回路から出るようなデータを使っている

これは「離散フーリエ変換と同じ答えが演算回路から出るような、命令語（プログラムコード＝データ）を使っている」といって差し支えないと思います。

Comments

[carnage0216]

解答ありがとうございます。
私の知りたいことが、解答者様がおっしゃる「その回路による論理が離散フーリエ変換を計算するようなものになっている」に近いです。
ただ、pcなどのcpuの演算回路には離散フーリエ変換をそのまま論理回路にしたわけではないと思います。
そこで、離散フーリエ変換の計算をするためだけの論理回路ではないのに、どのように演算回路を工夫して使う事で離散フーリエ変換の計算と同じ答えを導いているのかを知りたいと思いました。

[carnage0216]

詳しい解答をどうもありがとうございます。
ちなみに「離散フーリエ変換と同じ答えが演算回路から出るような、命令語（プログラムコード＝データ）を使っている」に関してなのですが、
数式と同じような答えが出るようにプログラム(命令語)を作るアルゴリズムなどはどうやって考えられているのでしょうか？
以上を紹介しているような本はありますでしょうか？
最初の質問と主軸がズレますがよろしくお願いします。

[KSwordOfHaste]

「離散フーリエ変換」あるいは「DFT」あるいはその高速計算アルゴリズム「FFT」といったキーワードで検索すると計算式そのものや高速化のためのFFTの考え方（バタフライ演算）の方式を解説したページがヒットすると思います。数式だらけでやや難解なものから「どういう考え方か」を比較的親切に解説したものなど色々あると思います。工学系の学校で工業数学を学んだ方でまだ工業数学の教科書が捨てずにとってあるなら教科書に数学的な色んな説明が見つかると思いますが自分の印象ではわかりやすいかは少々疑問です。数学的な意味はさておいて具体的な計算式を知るという点ではFFTについての解説ページを当たってみるのがよさそうに思います。

[carnage0216]

本当にどうもありがとうございます。
ベストアンサーにさせて頂きます。

Answer 2

フーリエ変換に限らず、基本的に論理回路で構築できる回路はソフトウェア的にも実現できるはずです。

まず基本ですが、任意の論理回路は突き詰めれば2入力NAND素子と結線だけでも構築できます（2入力NOR素子でも可）。当然ですが、ソフトウェア的にNAND素子をシミュレートすることは容易ですので、ここまで分解すれば任意の回路をシミュレートできると言えます。