ドパベン！
← 記事一覧へ戻る

シリーズ「コンピュータの記憶のしくみ」 第9回

回路が「手順を覚える」とは？

いま、どの段階か

前回の最後に、こう書いた。

いま自分がどの段階にいるのかを、誰も覚えていない。

今回は、それを覚えさせる。 記憶のしくみの、最終回である。

自動販売機の前に立ったところを思い浮かべてほしい。

通路に並んだ自動販売機

どれも、いまは待機の段階

硬貨を入れる。 金額が足りると、ボタンが光る。 ボタンを押すと、商品が出てくる。 おつりが返ってきて、また次の人を待つ。

自動販売機がしていることを順に書くと、こうなる。 どれも、ある順番でしか起きない。

ここまでのシリーズで、自動販売機はいろいろなものを覚えられるようになった。 入れた金額は、第6回のアキュムレータが足して覚えている。 商品の値段は、第8回のメモリから番地を指して読める。

けれど、ボタンが押されたとき、商品を出していいのだろうか。

お金が足りているなら、出していい。 まだ硬貨を入れている途中なら、出してはいけない。 商品を出している最中に、もう一度押されたなら、無視したい。

同じ「ボタンが押された」でも、どうするかは、いまどの段階にいるかで変わる。 だから、段階そのものを覚えておく必要がある。

段階に、番号を貼る

まず、段階に名前をつけよう。5 つある。

  • 待機 … 次の人を待っている
  • 受付 … 硬貨を受け付けている。まだ足りない
  • 買える … 金額が足りた。ボタンを待っている
  • 出す … 商品を出している
  • 釣銭 … おつりを返している

回路が覚えられるのは、0 と 1 のパターンだけだった。 そこで、段階に番号を貼る。

第8回で、番地に番号を貼ったのと同じことをすればいい。 番号は、ただの 2 進数である。

段階番号
待機000
受付001
買える010
出す011
釣銭100

5 つを区別するには、2 桁では足りない。2 桁で書けるのは 4 通りまでだからだ。 3 桁なら 8 通り書ける。

ということは、3 つ余る。 101、110、111 は、どの段階にも使っていない。 この 3 つは、あとで効いてくる。

次の段階を、表にする

次に、段階がどう移っていくかを決めよう。

いまの段階と、そのとき来ている入力を見て、次の段階を決める。 入力は 3 つ。硬貨が来たか。金額が足りているか。ボタンが押されたか。

いまの段階見る入力1 なら0 なら
待機 000硬貨受付 001待機 000
受付 001足りる買える 010受付 001
買える 010ボタン出す 011買える 010
出す 011なし釣銭 100釣銭 100
釣銭 100なし待機 000待機 000

見てほしいのは、「見る入力」の列だ。 どの段階も、見る入力は 1 つだけである。

待機のときは、ボタンが押されても関係ない。硬貨だけを見ている。 買えるのときは、硬貨ではなくボタンだけを見ている。 段階を覚えているから、「いま、どれを見ればいいか」が決まる。

条件がそろわなければ、同じ段階にとどまる。 出すと釣銭は、何も見ずに、次の拍で必ず先へ進む。

同じことを、丸と矢印で描くこともできる。 丸が段階、矢印が次に行く先、矢印に添えた言葉が進むための条件だ。 こうした図を、状態遷移図という。このあとのシミュレータの上に描いてある。 「状態」は、ここで言う段階のことである。

5 つの段階は、輪になって並ぶ。 待機から始まって、ぐるりと回って、また待機に戻ってくる。

表が書けたら、もう回路になっている

では、この表を回路にしよう。

「計算のしくみ」シリーズの第1回を思い出してほしい。 1 桁の足し算の表を書いたら、「和」の列が XOR の表と、「繰り上がり」の列が AND の表と、まったく同じだった。 表の列を 1 本ずつ、ゲートで作ればよかった。

今回も同じだ。 次の段階は、3 桁の番号である。1 の位、2 の位、4 の位の 3 本を、それぞれ作ればいい。

まず、いまの段階の番号を、第8回のデコーダに通す。 デコーダは、番号と同じ名前の線を 1 本だけ 1 にするのだった。 これで、段階ごとに 1 本ずつ、「いまこの段階だ」という線ができる。

あとは、表の行を読むだけだ。

たとえば、次の 1 の位が 1 になるのは、どの行だろう。 次の番号の一番下の桁が 1、つまり 001 か 011 に進む行を探す。

  • 待機で、硬貨が来たとき（001 へ）
  • 受付で、足りないとき（001 のまま）
  • 買えるで、ボタンが押されたとき（011 へ）

どれか 1 つでも当てはまれば、1 の位は 1。 「待機の線 AND 硬貨」のように行ごとに AND を取り、OR で合流させればいい。

ほかの桁も同じだ。

  • 次の 1 の位 ＝ (000 AND 硬貨) OR (001 AND NOT 足りる) OR (010 AND ボタン)
  • 次の 2 の位 ＝ (001 AND 足りる) OR 010
  • 次の 4 の位 ＝ 011

2 の位の 010 には、AND が付いていない。 買えるからは、ボタンが押されても押されなくても、次の番号の 2 の位は 1 だからだ（011 と 010）。 同じく、出すの次は必ず釣銭 100 なので、4 の位は 011 の線そのものになる。

ここで、書かなかった行があることに気づいただろうか。

釣銭の行だ。釣銭の次は待機、000 である。 どの桁も 0 なので、どの OR にも入れる必要がない。

第8回で見たとおり、0 は OR で合流させても、何も変えない。 何もつながなければ、その桁は 0 になる。 次が 000 になる行は、書かなくていいのだ。

押して、確かめる

作った回路を動かしてみよう。

段階 シミュレータ

左上の箱が、いまの段階を覚えているレジスタ。クロックを入れるたびに、右の OR から戻ってきた番号を受け取ります

硬貨足りるボタン待機000受付001買える010出す011釣銭100

矢印の言葉は、進むための条件。言葉の無い矢印は、次の拍で必ず進む

段階000 = 0デコーダ000001010011100101110111ANDAND×2ANDOR121124100〜111 の線はどこにもつながない硬貨0足りる0ボタン0クロック0

OR の左の数字は、その線がどの桁へ合流するか（1 の位・2 の位・4 の位）

いま 待機（000）

見ている入力 硬貨 = 0

次は 待機（000）

スイッチで入力を決めてから、「クロックを入れる」を押してください

道のり：待機

左上の箱が、いまの段階を覚えている 3 桁のレジスタだ。第5回で作ったものと同じである。 その右がデコーダ。行ごとに、段階の線が右へ走っている。 行ごとのスイッチと AND を通って、右端の OR で桁ごとに合流し、上を回ってレジスタへ戻っていく。

ここでは、「足りる」もスイッチにしておいた。 お金が足りているかどうかを、いまはあなたが決める。

はじめは待機 000 だ。

「硬貨」を 1 にしてから、「クロックを入れる」を押してほしい。 待機から受付へ進んだ。 上の図でも、光っている丸が受付に移ったはずだ。

「硬貨」を 0 に戻して、もう一度クロックを入れる。 受付が見ているのは「足りる」だけだ。0 のままなので、受付にとどまる。

「足りる」を 1 にしてクロックを入れると、買えるへ。 「ボタン」を 1 にしてクロックを入れると、出すへ。 そこからは、スイッチに関係なく、釣銭、待機と進んでいく。

どの段階でも、左下の「クロック」の丸を 1 にしたまま待ってみてほしい。 段階は動かない。0 に落とした瞬間に、1 つだけ進む。 第4回のフリップフロップが、ここでも効いている。段階は、1 拍に 1 つしか進まない。

輪が、もう一度

図を、もう一度見てほしい。

レジスタが、いまの段階を出す。 デコーダと AND と OR が、それを見て次の段階を決める。 次の段階が、上を回ってレジスタに戻ってくる。

回路が、輪になっている。

この形には見覚えがある。 第6回で作ったアキュムレータだ。 レジスタの出力を加算器に通して、答えをレジスタに戻す。クロックが来るたびに 1 周する。

形は、まったく同じである。 あのとき輪を回っていたのは、金額という数だった。 今回、回っているのは段階だ。

じつは、番号の振り方を見ると、もっと似ている。 待機 0、受付 1、買える 2、出す 3、釣銭 4。 段階は、0、1、2、3、4、0……と、数を数えるように進んでいる。

条件がそろえば 1 を足して、次へ。 そろわなければ、とどまる。第6回で言えば、0 を足しているのだ。 段階の輪は、ときどき 0 を足しながら回るカウンタのように見える。

段階を覚えることは、数を覚えることと何も変わらなかった。 番号を貼ってしまえば、段階も、ただの 2 進数である。

こうして、いまの段階を覚えておき、段階と入力から次の段階を決めて進んでいく回路を、状態機械（ステートマシン）という。

では、状態機械に、新しい部品は何か要っただろうか。

1 つも要らなかった。 覚えるのは第5回のレジスタ。段階をほどくのは第8回のデコーダ。あとは AND と OR だけだ。

新しかったのは、つなぎ方だけである。

第1回の SR ラッチを思い出してほしい。 2 つの NOR の出力が、互いの入力に戻っていた。 出力が入力に戻ってくるから、回路は前の状態を覚えていられた。

今回も、出力が入力に戻ってきている。 ただし今度は、ゲート 2 つの輪ではない。レジスタとデコーダと AND と OR を、ぐるりと回る大きな輪だ。

小さな輪は、1 と 0 を覚えた。 大きな輪は、段階を覚えて、決まった順番に進んでいく。 人間が「次はこれ、その次はこれ」とやっていたことを、回路が自分でやるようになった。

第1回で見た「出力が入力に戻ってくる」輪が、回路全体の大きさでもう一度現れた。それだけで、回路は手順を持つ。

一台に、する

いよいよ、自動販売機を一台にしよう。

いまのシミュレータでは、「足りる」をあなたがスイッチで決めていた。 硬貨とボタンも、スイッチだった。 これを、これまでに作ってきた部品につなぐ。

自動販売機 シミュレータ

お茶は 120 円。硬貨を入れて、ボタンが光ったら押してください

硬貨足りるボタン待機000受付001買える010出す011釣銭100
整える：硬貨整える：ボタン引いて比べる足りる値段次の段階金額00000 = 0段階000 = 0120 円クロック0

金額と値段の箱の数字は、1 を 10 円と読む（第6回の名札）。太い線は束

投入金額　0 円

硬貨を入れてください。クロックは流れつづけています

入れた 0 円　出てきたお茶 0 本　釣銭 0 円

「100 円を入れる」を押し、続けて 10 円を 2 回入れてから、光ったボタンを押してほしい。 お茶が出てきて、釣銭が返り、待機に戻る。 次は、100 円と 50 円を入れて買ってみてほしい。釣銭口から 30 円が返ってくる。

自動販売機の「おつり・返却」口

釣銭の段階で、ここに出てくる

図の箱を 1 つずつ見ていこう。

金額は、第6回のアキュムレータだ。1 の位を 10 円と読む名札も、第6回と同じである。 ただし桁を 1 つ増やして 5 桁にした。110 円のあとに 100 円を入れると、4 桁の 150 円には収まらないからだ。

引いて比べるは、金額から値段を引いている。 引き算は、計算シリーズの第3回で、反転して 1 を足す足し算に化けた。 そして第4回で見たとおり、いちばん上の桁からあふれる繰り上がりのランプは、引かれる数が引く数以上のときにだけ点く。 ここでは金額が値段以上、つまり足りているときだ。 このランプの線を、そのまま「足りる」として次の段階へ渡している。

値段は、120 円に固定した。 商品ごとに値段を変えたければ、第8回のメモリを置いて、押されたボタンの番号をアドレスにすればいい。

そして、段階の箱から右へ出ている太い線が、デコーダでほどいた段階の線だ。 この線が、金額の入口で、どの値を通すかを選んでいる。

段階金額の入口に通す値
待機0 ＋ 硬貨（はじめからやり直す）
受付金額 ＋ 硬貨
買える金額（硬貨はもう受け付けず、返却口へ返す）
出す金額 − 値段（比べたときと同じ引き算の答え）
釣銭0（いまの金額を、釣銭として返す）

第6回で、アキュムレータの入口は加算器でふさがっていて、覚えている数を取り替えられない、と書いた。 第8回で、入口の手前で選べばいい、と答えた。 その「選ぶ」を、ここで段階がやっている。

第8回で、語の線が、どの番地を読み書きするかを選んでいた。 今回は、段階の線が、いま、どの計算をするかを選んでいる。 段階は、自分が覚えているだけでなく、ほかの部品に「いまはお前の番だ」と知らせているのだ。

買えるの段階では、ボタンが光る。 第6回で、「光っているボタンは、もう買える」と書いた。 あの光を点けていたのは、この段階の線だったのである。

値段を表示したボタンが光っている自動販売機

光らせているのは、段階の線

なお、このシミュレータでは、硬貨を 10 円・50 円・100 円に絞り、買えるになったあとの硬貨は受け付けないことにした。 金額の桁が足りなくならないようにするためだ。

本物の自動販売機では、硬貨を見分けたり、おつりを払い出したりするのは、コインメックと呼ばれる装置の仕事である。 センサーと電子回路で、入ってきたのが本物の硬貨かどうかを判定している。 このシミュレータの「硬貨」は、それを見分けたあとの信号だと思ってほしい。

人間は、クロックに合わせてくれない

ここで、1 つ白状しておきたいことがある。

さきほどのシミュレータで、硬貨を入れてから金額が増えるまで、少し間があったはずだ。 あれは、わざと待たせている。

第6回で、硬貨のセンサーについて、こう書いた。

硬貨がセンサーを通り抜ける時間は、クロックとは関係なく決まる。 それを「ちょうどクロック 1 回ぶん」に整えるには、もう一工夫いる。

その一工夫を、ここで見ておこう。 困りごとは 2 つある。

1 つ目は、長すぎることだ。 人間にとっては一瞬でも、クロックから見れば、硬貨がセンサーを通るあいだに何拍も過ぎる。 センサーをそのまま金額の加算器につなぐと、クロックが落ちるたびに足してしまう。 100 円玉 1 枚が、300 円にも 400 円にもなる。

2 つ目は、来る瞬間が選べないことだ。 硬貨は、クロックの都合を知らずにやってくる。 センサーが 1 になるのが、ちょうどクロックが落ちる瞬間と重なったら、どうなるだろう。

整える シミュレータ

硬貨は、クロックの都合を知らずにやってきて、何拍ものあいだセンサーを通っていきます

センサー1 段目02 段目03 段目0来た？クロック0

3 つの箱は、第7回のシフトレジスタと同じつなぎ方。「来た？」は、2 段目 AND（NOT 3 段目）

クロックセンサー1 段目2 段目3 段目来た

右へいくほど新しい。黄色の破線はクロックが落ちたところ。黄色の斜線は、1 段目が迷っているところ

「硬貨を通す」を押してください。クロックも流れはじめます

センサーの値を、フリップフロップ 3 段に順に送っている。 第7回のシフトレジスタと、同じつなぎ方だ。

「硬貨を通す」を押してほしい。 センサーは 2 拍ぶん 1 になり、そのあいだにクロックが 2 回落ちる。 そのまま足せば、2 回足されてしまう。

けれど、右の「来た？」が 1 になるのは、ちょうど 1 拍だけだ。

「来た？」は、2 段目が 1 で、3 段目が 0 のときだけ 1 になる。 2 段目は、いまの拍のセンサー。3 段目は、その 1 拍前のセンサーだ。 つまり、「いまは来ていて、1 拍前は来ていなかった」ときだけ。 来はじめた拍でだけ 1 になり、次の拍では 3 段目も 1 になるので、もう 0 に戻る。

1 拍前を覚えておけば、「いま来はじめた」が分かる。 これも、小さな状態機械だ。「来ていない」と「来ている」の 2 つの段階を覚えて、その切り替わり目を見ている。

では、なぜ 1 段目があるのか。 「切り替わり目を狙って通す」を押してほしい。 センサーの値が、ちょうどクロックが落ちる直前に 1 段目へ届くようにしてある。

テープの 1 段目に、黄色の斜線が出たはずだ。 1 段目の中のラッチが、1 を受け取るか 0 のままでいるか、どちらにも倒れきれずにいる。

床の上に立てた鉛筆
また、この鉛筆

第2回で見た、メタステーブルである。 ゲートの速さがばらつく本物の回路では、いずれどちらかに倒れる。 けれど、どちらに倒れるかも、いつ倒れるかも、前もっては分からない。

だから、1 段目の答えは、すぐには使わない。 2 段目は、1 段目を 1 拍遅れて受け取る。 1 拍のあいだに 1 段目が倒れていれば、2 段目はきれいな 0 か 1 を受け取れる。

何度か試してみてほしい。 1 段目が 1 に倒れたときは、そのまま次の拍で「来た」が出る。 0 に倒れたときは、1 拍遅れて、次にクロックが落ちたときに受け取り直す。 どちらに倒れても、「来た」は 1 回だけ出る。

外から来る信号を、こうしてフリップフロップを 2 段通してから使うのは、本物の回路でもよく使われるやり方である。 迷う時間がとても長くなる確率は 0 ではないが、1 拍待つだけで、それをぐっと小さくできる。

自動販売機のシミュレータで、硬貨を入れてから金額が増えるまで少し待たされたのは、この 3 段を通っていたからだ。 次の硬貨をすぐに入れられないのも、同じ理由である。 センサーが 0 に戻ったことを 1 段目が見る前に次の硬貨が来ると、1 がずっと続いているように見え、2 枚が 1 枚になってしまう。

使っていない番号

番号を貼ったとき、3 つ余った。 101、110、111 だ。

表には、この 3 つの行を書いていない。 どの段階にも使っていないのだから、そこに来ることはない——と言いたいところだが、そうはいかない。

1 つは、電源を入れた瞬間だ。 フリップフロップの中の SR ラッチは、電源が入った瞬間、どちらに倒れるか決まっていない。第2回の鉛筆と同じである。 実際、電源を入れた直後のフリップフロップやレジスタの値は不定だとされている。 3 桁の段階が、110 から始まることもありうる。

もう 1 つは、ノイズだ。 電気的な雑音で、どこかの桁が一瞬化けることがある。

そのとき、回路はどうなるだろうか。

使っていない番号 シミュレータ

段階を、表に書かなかった番号に化けさせてから、クロックを入れてみてください

硬貨足りるボタン使っていない101110111待機000受付001買える010出す011釣銭100

矢印の言葉は、進むための条件。言葉の無い矢印は、次の拍で必ず進む。点線は、使っていない番号から待機へ

段階000 = 0デコーダ000001010011100101110111ANDAND×2ANDOR121124100〜111 の線はどこにもつながない硬貨0足りる0ボタン0クロック0

OR の左の数字は、その線がどの桁へ合流するか（1 の位・2 の位・4 の位）

いま 待機（000）

見ている入力 硬貨 = 0

次は 待機（000）

スイッチで入力を決めてから、「クロックを入れる」を押してください

デコーダの作り
段階を化けさせる

道のり：待機

「110 にする」を押してから、クロックを入れてほしい。

待機に戻った。

110 の線は、デコーダから出ているが、どこにもつながっていない。 どの AND にも、どの OR にも入っていない。 だから、次の番号はどの桁も 0、000 になる。

「表に書かなかった行は、どの OR にも入らない」。 さきほど、釣銭の行を書かなくてよかったのと、同じ理由である。 表どおりにデコーダで 3 桁ぜんぶを見て作っておけば、使っていない番号からは、何もしなくても待機に戻ってくる。

では、少し欲を出してみよう。

表をよく見ると、4 の位が 1 なのは、釣銭 100 だけだ。 それなら、ほかの段階は、下 2 桁だけ見れば見分けられるのではないか。 見る桁が減れば、AND の入力も減る。

「デコーダの作り」で「下 2 桁だけ見る」を選んでから、もう一度「110 にする」を押して、クロックを入れてほしい。

お金を入れていないのに、買えるに進んだ。ボタンが光る。

下 2 桁だけ見れば、110 は 010、買えると区別がつかない。 使っていない番号が、ほかの段階のふりをしたのだ。 101 は受付のふりをする。111 は出すのふりをして、入れてもいないお金を釣銭として返そうとする。

第6回で、入れていないのにお金が増えていく自動販売機を作ってしまった。 「ジュースが配り放題」だった。 同じことが、今度は段階で起きる。

使っていない番号にも、行き先を決めておかなければならない。 表に書かなかった行は、書かなかったでは済まない。書かなかった行が、どこへ行くのかまで決めておくのが、状態機械を作るときの約束である。

もちろん、電源を入れた瞬間については、本物の回路はもっと素直な手を使う。 電源が入ったら、しばらくのあいだ「リセット」の線を 1 にして、フリップフロップを決まった値にそろえてしまう。 パワーオンリセットという。自動販売機のシミュレータで電源を入れ直すと、待機・0 円から始まるのは、これを入れてあるからだ。

歩いてきた道

ここで、第1回からの道のりを振り返っておきたい。 自動販売機の中で、それぞれの部品が何をしていたかを並べてみる。

回作ったものこの自動販売機での役目
第1回SR ラッチ出力が入力に戻る輪。すべての記憶の土台
第2回競合とメタステーブル硬貨がクロックの切り替わり目に来ると、迷う
第3回D ラッチ「値」と「書き込んでいいか」を分けた。フリップフロップの中身
第4回D フリップフロップ段階を、1 拍に 1 つだけ進める
第5回レジスタ段階（3 桁）と、金額（5 桁）を覚える
第6回カウンタ・アキュムレータ金額を足しつづける。0 を足せば、とどまる
第7回シフトレジスタセンサーの信号を整える 3 段
第8回メモリ・デコーダ段階を線にほどき、金額の入口を選ぶ
第9回状態機械いまの段階を覚えて、手順どおりに進む

計算のしくみシリーズで作った加算器も、引き算も、ここに入っている。 金額を足しているのは全加算器を並べたものだし、足りるかどうかを比べているのは、反転して 1 を足す引き算と、5 桁目のランプだ。

計算シリーズの第1回で、こう書いた。

回路は足し算を理解していない。理解していないのに、答えは合っている。

この自動販売機も、お金というものを知らない。お茶が何かも知らない。 それでも、硬貨を入れてボタンを押せば、お茶と釣銭が出てくる。

電源を、切ったら

最後に、もう 1 つだけ試してほしい。

さきほどの自動販売機のシミュレータで、硬貨をいくらか入れてから、「電源を切る」を押してみてほしい。

図の線が、すべて灰色になる。 入れていた金額は、どこにも残っていない。 電源を入れ直すと、待機・0 円から始まる。

段階も金額も、覚えていたのはフリップフロップだった。 そしてフリップフロップの中にあるのは、第1回の SR ラッチの輪である。

第1回で、何も押していないときも、信号はずっと回りつづけている、と書いた。 上のゲートが下のゲートを 0 に保ち、下のゲートが上のゲートを 1 に保つ。 2 つのゲートが働きつづけているあいだだけ、値はそこにある。

ゲートを働かせているのは、電気だ。 電源を切れば、どちらのゲートも相手を支えられなくなる。輪はほどけ、何も残らない。

回路は、覚えていたのではない。覚え続けていたのだ。

夕暮れの建物の前に立つ自動販売機
今夜も、覚え続けている

本物のメモリも、多くはそうなっている。

コンピュータの中のメモリには、大きく分けて SRAM と DRAM がある。 SRAM のひと粒は、フリップフロップ、つまり互いに支え合う輪でできている。電源が入っていれば値を保つが、切れば消える。 DRAM のひと粒は、小さなコンデンサに電気をためて覚える。ためた電気は少しずつ漏れていくので、たとえば 64 ミリ秒以内に、ため直さなければならない。これをリフレッシュという。 DRAM は、文字どおり、覚え直しつづけることで覚えている。

電源を切っても忘れては困るものもある。 スマートフォンの写真や、店の売上の記録だ。 そういうものは、別のしくみの記憶に書く。

フラッシュメモリは、電子を絶縁された層の中に閉じ込めて、0 と 1 を覚える。 閉じ込めた電子は、電源を切っても逃げていかない。 だから、電気を流しつづけなくても、覚えたままでいられる。こうした記憶を、不揮発メモリという。

それでも、このシリーズで作ってきた記憶は、すべて輪だった。 出力を入力に戻し、互いに支え合い、クロックのたびに自分を受け取り直す。 その輪が、1 桁を覚え、4 桁の数を覚え、足しつづけ、場所を指し、手順を持った。

第1回で、こう書いた。

互いに相手の根拠になっていて、外から邪魔されない限り永遠に崩れない。

その「外」のうち、いちばん大きなものが、電源だった。

最終回の今、こう書き足しておきたい。

回路は、一度も忘れていない。それでも、電源を切れば何も残らない。

参考文献

シリーズ「コンピュータの記憶のしくみ」