2011-04-19

通信の基礎 part2

授業通信

今回のテーマ

フーリエ変換
フーリエ逆変換
たたみこみ積分

フーリエ変換

周期関数はフーリエ級数で対応をとれた。
ではこの考えを非周期関数に適用させたものは？
→フーリエ変換

周期関数の周期Tを∞にもっていけば非周期関数もフーリエ解析できるのでは？？
結論：出来る。

複素フーリエ級数の係数 $C_{n}$
$C_{n} = \frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} f(t) exp{-jn\omega_{0}t}dt$
Tを∞に飛ばすと $C_{n}$ は0に収束しそう。。そこで辺々にTをかけ $C_{n}T$ について考える。
$\lim_{n \to \infty}C_{n}T = \int_{-\infty}^{\infty}f(t) exp{-jn\omega_{0}t}dt$
$\omega = n\omega_{0}$ として、
$\fbox{F(\omega) = \int_{-\infty}^{\infty} f(t) exp{-j\omega t}dt}$
この拡張は、関数を「各周波数成分に分解する」という考えとは異なる「周波数領域への変換」という概念を導入することに。
すなわちフーリエ変換とは時間領域→周波数領域の変換である。
$C_{n}= \frac{2 \sin{n\omega_{0}T_{1}}}{n\omega_{0}T}$
$n\omega_{0} = \omega$
$F(\omega) = \frac{2 \sin{\omega T_{1}}}{\omega T}$
$TC_{n} = \frac{2 \sin{n\omega_{0}T_{1}}}{n\omega_{0}}$

フーリエ逆変換

$F(\omega) \to f(t)$
結論
$\fbox{f(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega) exp{j\omega t}dt}$
$F(\omega)$ :周波数スペクトル

f(t)の区間 $\left( -\frac{2}{\pi} , \frac{2}{\pi} \right) \to f_{T}(t)$
$-\frac{2}{\pi} \le t \lt \frac{2}{\pi} \; \; f_{T}(t) = f(t)$
周期T $f_{T}(t+T)=f_{T}(t)$
$\begin{align}f_{T}(t) & = & \sum_{n=0}^{\infty}C_{n} exp{j\omega nt} \\ & = & \sum_{n= -\infty}^{\infty} \frac{1}{T}F(n\omega_{0}) exp{-jn\omega_{0}t}\end{align}$
$\omega_{0} = \frac{2\pi}{T}$ を代入し、
$f_{T}(t) = \sum_{n=-\infty}^{\infty}\frac{1}{2\pi}F(n\omega_{0}) exp{-jn\omega_{0}t}\omega_{0}$
これは $\omega_{0} \to 0$ で積分の定義に一致。
この $f_{T}(t)$ を $F(\omega)$ の逆フーリエ変換と呼び、 $\mathcal{F}^{-1} [ F \left( \omega \right) ]$ と記す。

単位インパルス関数

$\delta(t) = \left{ \frac{1}{\Delta} \;\;\left( \mathrm{-\frac{\Delta}{2} \le t \le \frac{\Delta}{2} } \right) \\ 0 \;\; \left( \mathrm{else} \right)$
を定義すると、

$t=t_{0}$ の近傍で連続な関数f(t)に関して、
$\int_{-\infty}^{\infty}f(t)\delta(t-t_{0})dt \\ = \lim_{\Delta \to 0} \frac{1}{\Delta} \int_{t_{0} - \frac{\Delta}{2}}^{t_{0} + \frac{\Delta}{2}} \frac{1}{\Delta}dt = f(t_{0})$
単位インパルス関数は他の関数をを標本化する働きがある。
$f(t) = exp{-j\omega t}$
では $\delta(t)$ のフーリエ変換は？
$\mathcal{F} \left[ \delta \left( t \right) \right] = \int_{-\infty}^{\infty}\delta(t) exp{-j\omega t} dt = f(0) = e^{0} = 1$
$\delta(t) - \frac{1}{2\pi} \int_{-\infty}{\infty} exp{j\omega t} d\omega , \;\; 2\pi\delta(t) = \int_{-\infty}^{\infty}exp{j\omega t} d\omega$
$\omega \leftrightarrow t$
$\omega \leftrightarrow -\omega$
$\fbox{{\mathcal{F} \left[ 1 \right] = 2\pi \delta(\omega)}$

フーリエ変換
周波数推移則
$2\pi\delta(\omega) = \mathcal{F}\left[ 1 \right]$
$\mathcal{F} \left[ exp{j\omega t} \right] = 2\pi\delta(\omega-\omega_{0})$

ゲート関数

$\Pi(\frac{t}{T}) = \left{ 1 \;\; \mathrm{(if |t| \lt \frac{T}{2}) } \\ 0 \;\; \mathrm{(if |t| \ge \frac{T}{2} )}$

$\begin{align} \mathcal{F} \left[ \Pi(\frac{t}{T}) \right] & = & \int_{-\infty}^{\infty} \Pi(\frac{t}{T}) exp{-j\omega t}dt \\ & = & \int_{-\frac{T}{2}}^{\frac{T}{2}} exp{-j\omega t}dt = \left[ \frac{ exp{j\omega t} }{-j\omega} \right]^{\frac{T}{2}} _{{-\frac{T}{2}}} \\ & = & \frac{exp{j\omega \frac{T}{2}} - exp{-j\omega \frac{T}{2}} }{j\omega} = \frac{2 \sin{\frac{\omega T}{2} } }{\omega} = T \times \frac{\sin{(\omega \frac{T}{2} )}}{(\omega \frac{T}{2})} \end{align}$

※sinc関数

$\frac{\sin{x}}{x}$
標本化関数とも呼ばれる。

たたみこみ関数

$\fbox{z(t) = f(t)*g(t) \equiv \int_{-\infty}^{\infty} f(x)g(t-x) dx}$

時間	$f(t)g(t)$	$f(t)*g(t)$
	↓	↑
周波数	$F(\omega)*G(\omega)$	$F(\omega)G(\omega)$

$\mathcal{F} \left[ f\left( t \right) * g \left( t \right) \right] \\ =\int_{-\infty}^{\infty} exp{-j\omega t} \left[ \int_{-\infty}^{\infty} f \left( x \right) g \left( t-x \right) dx \right] dt \\ =\int_{-\infty}^{\infty} f \left( x \right) \left[ \int_{-\infty}^{\infty} g \left( t-x \right) exp{-j\omega t} dt \right] dx \\ =\int_{-\infty}^{\infty} f \left( x \right) \left[ \int_{-\infty}^{\infty} g\left( t^{'} \right) exp{-j\omega t^{'}} dt^{'} \right] dx \\ =\int_{-\infty}^{\infty} f \left( x \right) G \left( \omega \right) exp{-j\omega t} dx \\ = F \left( \omega \right)G \left( \omega \right)$

上式で時間領域と周波数領域を入れ替えると同様にして、
$\fbox{\mathcal{F} \left[ f\left( t \right) g\left( t \right) \right] = \frac{1}{2\pi} F \left( \omega \right) * G \left( \omega \right)$

2011-04-14

NP完全とかNP困難とか

基礎知識

友人からNP完全とNP困難について分かりやすく説明してくれと言われたので、頑張ってまとめました。
時間計算量に関しては↓のエントリ参照。
時間計算量に関して-- http://d.hatena.ne.jp/nsasaki/20110426/1303807572

そもそもNPって何？って話から。
Wikipediaより

NPとは、計算複雑性理論における問題の複雑性クラスで、Non-deterministic Polynomial time（非決定性多項式時間）の略である。
定義
NP の定義は次の3つである、ただしこれらはお互い同値であることが証明されている。

非決定性チューリングマシンによって多項式時間で解くことができる問題。

yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。

問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。

端的に説明するときは 2番目の定義（多項式時間で検算可能）が用いられることが多い。
なお NP はクラス P 同様、判定問題のクラスであり yes/no で答えることの出来ない問題は NP には属さない。
誤解されることが多いが、NP は多項式時間で解けない問題のクラスではない（Not P の略ではない)。上記の定義は全てのクラス P の問題にも当てはまるので、クラス P はクラス NP に含まれる。

と書いてあるけど分かりませんよね。。
専門知識がない人(と言っても高校数学レベルは必要ですが)には2.が一番分かりやすいかと。。
有名な例は3-SAT。

3-SAT

3-SATを理解するためにまず、論理演算の話を。

論理演算とは、 $x_{i}$ に関して、

$x_{i}$ のとりうる値は1か0
$\overline{x_{i}}$ は $x_{i}$ の値を反転させたもの。
$x_{i}+x_{j}$ は $x_{i},x_{j}$ のいずれかが1ならば1。それ以外なら0となる。論理和。
$x_{i}x_{j}$ は $x_{i},x_{j}$ の両方が1ならば1。それ以外なら0となる。論理積。

という演算体系のこと。

3-SATとは
$(x_{1}+\overline{x_{3}}+\overline_{x_{2}})(x_{2}+x_{3}+\overline_{x_{1}})$
のように3個の論理和と任意個の論理積で構成され、その値が1になるような組み合わせが存在するか。という問題。
ここでは $(x_{1},x_{2},x_{3})=(1,1,0)$ が答えの一つ。

変数がn個存在するときについて考えると、一般的な解き方が判明していないので総当たりで調べることになる。
この場合、問題を解くのに最悪のケースで $2^{n}$ 回トライすることになる。
また、各トライでは論理積の数がm個のとき3mn回の計算で答えが出る。(各xについて調べるため)
これはwikipediaさんの2.の定義で言うところのyesとなる証拠が与えられればそれが正しいのかどうか多項式時間で判定できる例である。

NPについて

くだけた言い方をすると、

なんか証拠が与えられた時にそれを確かめるのは変数に対して、確かめるのにかかる時間はその変数の多項式で調べられる。

しかし、何も証拠がないとどれくらいかかるかは分からないかもしれないよ。

っていう感じ。

ちなみにクラスPというのは

何も証拠がなくても多項式で解ける問題。

だからPはNPに含まれると。
で、クラスPとクラスNPは等しくないだろうという予想されている。
この予想はP≠NP予想と呼ばれている。
これが正しいのかそれとも間違っているのかという証明はされていない。
また、クレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられている。

このP≠NP予想を証明するのに1971年にスティーブン・クックが定式化した概念がNP完全。

NP完全とは

クラスNPに属し、
クラスNPに属する他の全問題が多項式時間帰着

される問題のことである。

クラスNPであることが証明されていて
かつクラスNPに属する他の全問題,たとえばあるクラスNPと証明されている問題でn個の変数がある。それに対して、nの多項式時間で何らかの操作(例えば式変形)を行い、前者の問題と同等に変換できる。

ということである。
NP完全な問題がP≠NPを満たすならば、他のすべてのクラスNPに関して、P≠NPが証明されたということになる。
これによってすべての研究をNP完全に集中させようということ。
なお例で出した3-SAT問題は有名なNP完全問題！

一方、

NP困難とは

クラスNPに属しているか分からない
クラスNPに属する他の全問題が多項式時間帰着される問題(i.e.NP完全から多項式時間で帰着される)

を満たす問題のことである。

2011-04-14

パタヘネChapter6 part1

パタヘネ授業

パタヘネ下巻の内容をやる授業をとったので、そちらのまとめでも。。

Chapter6 --パイプラインを用いた性能向上

6.1パイプライン処理の概要

プロセッサにおける命令の処理
例　MIPS　R形式

命令のフェッチ
命令の解読　オペランド（レジスタ）の読み出し
演算
結果の書き込み（レジスタ）

マルチサイクル

――――――――――――――――――――――――――――――＞　時間

逐次

―、―、―、―＞｜
｜―、―、―、―＞｜
｜―、―、―、―＞

パイプライン

―、―、―、―＞｜
―、―、―、―＞｜
―、―、―、―＞｜

パイプライン処理

複数の命令を時間を少しずつずらして同時並行的に実行する。

プロセッサの高速化技術の鍵

各ステップのことをステージと呼ぶ

高速化

4ステージ
- 4 命令　16→7　
- 20命令　80→23
Lステージ
- N命令 NL→N+L-1

MIPSの場合　5ステージ

メモリから命令をフェッチする
命令の解読、オペランド（レジスタ）読み出し
命令操作の実行またはアドレスの生成
データメモリ中のオペランドにアクセス
結果をレジスタに書き込む

例題 p.404

微妙に単位が違うのは授業で使っているのが第三版のため。。
単一サイクル方式とパイプライン処理の性能比較
8個の命令 lw,sw,add,sub,and,or,slt,beq
メモリアクセス　200ps
ALU　200ps
レジスタ　100ps
単一サイクル　最長

　フェッチレジスタ ALU メモリレジスタ

lw 200 100 200 200 100

800ps
パイプライン200*5=1000

理想的な場合

パイプライン処理による命令実行間隔　＝　逐次処理における間隔／パイプラインステージ数

低下の要因

ステージ間のバランス
ステージ間レジスタ
パイプライン処理により
- レイテンシ（命令の実行時間）―短くならない
- スループット（単位時間に実行できる命令数）―増大　→　1／間隔

パイプラインハザード

パイプライン処理において、次のクロックサイクルで次の命令を実行できない状態のこと。

構造ハザード
- 並行して実行される命令の組み合わせにハードウェアが対応できないために命令を所定のクロックサイクルで実行できない
- 解決策
  1. 異なるステージで同じハードウェアを使わないように設計する
データハザード
- まだパイプライン中にある先行命令に後ろの命令が依存している（演算結果を使う）
- 解決策
  - レジスタの書き込みと読み出しのタイミング
    1. サイクル内で書き込みが終わってから読み出す
    2. フォワーディング
- 完全に解決できない場合
  - lw $s0 20($t1)
  - sub $t2 $s0 $t3
- パイプラインストール
  - 命令の並べ替えによる解決　コンパイラ側の努力
制御ハザード
- ある命令の実行に関する判断をまだ実行中の先行命令の結果に基づいて下さなければならない。条件分岐
- 解決策
  1. ストール
  2. 予測　外れたら無効にする
  3. 遅延判定、遅延分岐

2011-04-11

通信の基礎 part1

授業通信

授業名でググると上位に出てきたので名前変更。。
この授業をとるかは分からないんだけど、授業の内容も軽くまとめようかと。

使用する教科書は、オーム社の「情報通信工学」
範囲は三章と四章

大学過程情報通信工学 (大学課程)

作者: 寺田浩詔,吉田進,佐藤亨,木村磐根,岡田博美
出版社/メーカー: オーム社
発売日: 1993/03/01
メディア: 単行本
クリック: 1回
この商品を含むブログ (4件) を見る

前半の講義内容は

フーリエ級数
フーリエ変換
スペクトルと信号処理
標本化
AM変調1
AM変調2
SSB変調

通信モデル

送信ーーー＞伝送路ーーー＞受信

↑

雑音

多重波

これに反射を考えたもの。

フーリエ級数を理解するのに必要な項目

周期信号
- f(t+T) = f(t) :周期T
非周期信号
複素数
- $z = x + jy$ *1, （ $sqrt{-1} = j$ ）
共役
- $\overline{z} = x - jy$
絶対値
- $|z| = sqrt{x^{2} + y^{2}} = sqrt{z\overline{z}}$
偏角
- $\arg{(z)} = \tan^{-1}{\frac{y}{x}$
実部
- $Re(z) = x$
虚部
- $Im(z) = y$
オイラーの公式
- $e^{j\theta} = \cos{\theta} + j\sin{\theta}$
偶関数
- $f(x) = f(-x)$
奇関数
- $f(x) = -f(-x)$
デルタ関数
- $\int_{-\infty}^{\infty} \delta (t) dt = 1,\; \Delta \rightarrow 0, \; \left{\delta(t) = \frac{1}{\Delta} \; \left{ -\frac{\Delta}{2} < t < \frac{\Delta}{2} \right} \\ \delta(t) = 0 \; \left{ \mathrm{else} \right}$

フーリエ級数

f(t+T) = f(t)について、正弦波(sin,cos)で表現できる。（証明は略）
以下のようになる。
$f(t) = \frac{a_{0}}{2} + \sum_{n=1}^{\infty} \left( a_{n}\cos{\left(\omega nt \right) } + b_{n}\sin{\left(\omega nt \right) } \right)$
ただし、
　 $\left{ a_{n} = \frac{2}{T} \int_{-\frac{2}{T}}^{\frac{2}{T}} f(t) \cos{\left(\omega nt \right) } \: dt \; \left( n = 0, 1, \cdots \right) \\ b_{n} = \frac{2}{T} \int_{-\frac{2}{T}}^{\frac{2}{T}} f(t) \sin{\left(\omega nt \right) } \: dt \; \left( n = 1, 2, \cdots \right) \\ \omega = \frac{2\pi}{T}$

複素フーリエ級数

sin,cos に関してオイラーの公式より
$\cos{ \left( \omega nt \right) = \frac{exp{j\omega nt} + exp{-j\omega nt} }{2}$
$\sin{ \left( \omega nt \right) = \frac{exp{j\omega nt} - exp{-j\omega nt} }{2j}$
と表記できるので、
$f(t) = \frac{a_{0}}{2}+\sum_{n=1}^{\infty} \left{ \frac{ \left( a_{n} - jb_{n} \right) }{2} exp{j\omega nt} + \frac{ \left( a_{n} + jb_{n} \right) }{2} exp{-j\omega nt} \right}$
ここで、
$c_{n} = \frac{a_{n} - jb_{n}}{2} \: , \: c_{-n} = \overline{c_{n}} = \frac{a_{n} + jb_{n}}{2}$
とすると
$f(t) = \frac{a_{0}}{2} + \sum_{n=1}^{\infty} c_{n} exp{j\omega nt} +\sum_{n=1}^{\infty} c_{-n} exp{-j\omega nt} \\ = \sum_{-\infty}^{\infty}c_{n} exp{j\omega nt}$
となる。

宿題

$f(t) = 1 - \frac{2|t|}{T} \: \left( - \frac{T}{2} < t < \frac{T}{2} \right)$
を満たす周期Tの周期関数f(t)について、 $a_{0,}a_{1,}b_{1}$ を導出せよ。

答えは後ほど。

*1:電気系ではiだと電流と間違うため虚数はj

2011-03-20

人月の神話メモChapter4

人月の神話メモ

第四章

貴族政治、民主政治、そしてシステムデザイン

この偉大な境界は比類のない芸術作品です。そこに示された協議には、無味乾燥なところも混迷したところもありません…
これは様式の極致、先達らの成功のすべてを理解し、吸収した芸術家たちの作品です。彼らは当時の技術を完璧に習得していながら、それをひけらかしたり、必要以上に巧みな技を使うことはありませんでした。
建物の外観を立案したのはまぎれもなくジャン・ド・オルベイズですが、その構想は少なくとも本質的な部分に関して後継者たちから尊重されています。そのためにこの建築物には並外れた一貫性と統一性が見られるのです。
ランス大聖堂ガイドブックより

プログラミングシステムにはコンセプトの統一性が大事である。

コンセプトの統一性は、どのようにして実現するのか。
この議論には、アーキテクトという「エリート」または「貴族階級」と、創造的才能やアイデアが抑制された「平民」の実現者の存在が、ほのめかされてはいないか。

プログラミングシステムの目的＝コンピューターを使いやすくすること

使いやすくなったの定義
- （昨日の指定で節約できた時間）が（マニュアルを勉強したり、記憶したり、調べたりすることにかかる時間）を上回ったとき
使いやすくするためには
- システムの機能数が適切である
- システムの操作が簡潔である
- システムの操作が直感的である
- システムの操作を直感的にするのは難しい
そもそも直感的なシステムとは
- 複雑な処理を行う際の慣用的なコマンドの組み合わせがユーザの頭の中にすぐに思い浮かぶシステム
システムの操作が直感的であるためには？
- 語義(基本コマンド)それぞれが同じ重みを持つようにする
- 構文(基本コマンドの組み合わせ)の構造が同じ文法で表せるようにする
- では、「直感的なシステム」を作るには？
- システムのデザイン(コンセプト)を一人もしくは少数の人間で作ればよい

現実のプロジェクトで使いやすいシステムを作るには
アーキテクチャとインプリメンテーションを慎重に分離する

アーキテクチャとインプリメンテーションの違い
- 「アーキテクチャは何が起こるのかを語るのにたいして、インプリメンテーションはいかにして起こせるかを語る」

時計の場合

アーキテクチャ	ねじを回して針を現在時刻にあわせる。針が文字盤を指したところが現在時刻
インプリメンテーション	振り子を使って針を進める・ゼンマイを使って針を進める・クォーツとステップモーターを使って針を進める・・・

プログラミングシステムのアーキテクチャとは？
- 実装者から見ればUIについての完全かつ詳細な仕様書
- 利用者から見れば一番詳細なマニュアル

アーキテクトだけがアーキテクチャを決めるべきである。

アーキテクトだけが良いアイデアを持っているというつもりはない
実現者や利用者から良いアイデアや新鮮なコンセプトが出てくるのはよくあること
しかし、システムの使いやすさにとって「直感性」＝「統一されたコンセプト」は命
そのためシステムの基本的コンセプトと相容れない優れた機能やアイデアは除外すべきである
そういう機能やアイデアがたくさんあるようならコンセプトの方が間違っているので基本コンセプトからやり直す

民主的にアーキテクチャを決めると……

アーキテクチャとインプリメンテーションを厳密に区別しないプロジェクトでは思考と議論の大部分がアーキテクチャの決定に注がれる
インプリメンテーションには、死刑執行前に与えられる懺悔の時間くらいしか与えられない

貴族政治擁護の立場

少人数のアーキテクトチームでシステムの外部仕様を書こうとする場合に想定される想定問答

そういう仕様書には機能が多すぎて、現実的なコストの検討がされない
- 実際に起こりうる問題
- 第5章で述べる
アーキテクトが創造的楽しみを独占して、実装者の創意工夫が閉め出されてしまう
- 妄想
- インプリメンテーションも同等の創造的活動である
仕様書がアーキテクトという細い管を通ってくる間多くの実装者がただ漫然と待っていなくてはならない
- 妄想
- 一番良いのは仕様書が完成するまで実装者を雇わないこと
- 実装者を雇った場合でもしなければならないことはいろいろある
大人数でシステムのデザインをするよりも時間がかかるのでは？
- 経験からいって、システムのデザインにかかる時間は同じ
- インプリメンテーションやテストの時間は、コンセプトが統一されていた方が遙かに短くてすむ

2011-03-12

人月の神話メモChapter3

メモ人月の神話

第三章

外科手術チーム

以上の研究から、優秀な者とそうでない者との間には、格段に大きな個人差がたいていの場合あるということが分かった。
サックマン、エリソン、およびグラントより

少数精鋭が望ましい。

人によって生産性が10倍近く違うのはザラ。
コミュニケーションのコストが格段に低い。
コンセプトの統制が出来る。

大規模プロジェクは小数精鋭が出来ない。

精鋭を100人集めたら精鋭ではなくなる。
- コミュニケーションのコスト。
- 管理階級が必要。
- 財務や人事、総務や秘書、マシンオペレータと言った担当も必要。
精鋭は少ないから精鋭

では実際の大規模プロジェクトはどうしたらいい？

ミルズの案

実装と設計を分ける。
設計は、人員をいくつかのチームに分けたチームの長(執刀医)が行う。

小数精鋭
コンセプトの統一性
コミュニケーションコストの限定
実装は独立した外科手術チームのように編成されたチームで行う。
チームの機能ごとに担当者を設定する。

役割	説明
執刀医	成果物を作る(デザイン・コーディング・ドキュメント・テスト)
副執刀医	成果物を作る(執刀医の子分・分身・予備)
管理者	人事・法務・機器管理を行う。法的にクリティカルなシステム開発でなければ、複数チームを掛け持ち
編集者	成果物を評価・手直し・整形して参照や参考文献をつける
プログラム事務	成果物の管理をする・配布をする
ツール制作者	成果物を作成するためのツール（治具）を作成する
テスト担当者	成果物のテスト準備とテストを行う
言語エキスパート	実装上の相談を受ける。複数のチームを掛け持ち

コミュニケーションコストの限定

おざなりにされがちな仕事がきちんと行われる。
実際にプログラム製品を製作する執刀医・副執刀医が、プログラム製品製作に集中できる。

2011-03-10

パタヘネChapter3 part2

パタヘネ

Chpter3--命令:マシンの言葉

ハードウェアの設計に関する四つの基本原則

単純性は規則性につながる。
小さければ小さいほど高速になる。
優れた設計には適度な妥協が必要である。
一般的な場合を高速化せよ。

3.4 コンピューター内での命令の表現 p.105

数の表現
- 人→10進数
- コンピューター→2進数
- コンピューター内ではすべての情報を2進数のbitを単位にして構成される。
- MIPSのアセンブリ言語では、レジスタ$s0から$s7はレジスタ16から23に対応し、レジスタ$t0から$t7はレジスタ8から15に対応する。

命令はフィールドと呼ばれる区切られた部分に分けられる。

命令を数値で表現したものを機械語(machine language)と呼び、
それらの命令を連ねたものをマシン・コード(machine code)と呼ぶ。
命令を表記するこのような枠組みを命令形式(instruction format)と呼ぶ。

単純性は規則性につながるという設計原則にのっとり、MIPSの命令はすべて長さが32ビットになっている。
各フィールドには以下のようになっている。

op	rs	rt	rd	shamt	funct
6bit	5bit	5bit	5bit	5bit	6bit

op: 命令の基本操作。従来から命令操作コード(opcode オペコード)と呼ばれている。
rs: 第1のソース・オペランドのレジスタ。
rt: 第2のソース・オペランドのレジスタ。
rd: デスティネーション・オペランドのレジスタ。つまり結果を収める先。
shamt: シフト量。
funct: 機能。命令操作フィールドのバリエーションを表す。機能コード(functional code)と呼ばれることがある。

しかし、ここで上に記したフィールドよりも長いフィールドを必要とする命令があると、問題が発生する。
ロード命令などでは5ビットのフィールドでは小さ過ぎて役に立たない。

相反する要求

すべての命令長を同じにしたい
命令形式を1つにしたい

これらは両立しない。

そこでハードウェア設計に関する3番目の原則

優れた設計には適度な妥協が必要である。

MIPSの設計者が選択した妥協案
すべての命令長を同じに保つこと。ロード命令を以下のようにする。

op	rs	rt	adress
6bit	5bit	5bit	16bit

複数の命令形式を許すとハードウェアが複雑になる。しかし、命令形式にある程度の類似性を持たせれば、複雑性を抑えることが出来る。

今日のコンピューターは2つの基本原理に基づいて設計されている。

命令は数値として表現される。
プログラムをメモリ中に格納して、数値と同様に読み書きすることが出来る。

この根本原理からプログラム内蔵(stored-program)方式の概念が生まれた。
メモリ中に種々の要素が格納される。具体的には

エディタ・プログラムのソース・コード
それをコンパイルした結果のマシン・コード
コンパイルされてプログラムが使用するテキスト
コンパイルを行ったコンパイラ

など。

	フェッチ	レジスタ	ALU	メモリ	レジスタ
lw	200	100	200	200	100