問題一： https://blog.yexca.net/archives/198
問題二： https://blog.yexca.net/archives/201
問題三： https://blog.yexca.net/archives/200
問題四： https://blog.yexca.net/archives/202
問題五：この記事

はじめに

もう2週間近く経ったかな、やっとこの問題用紙全部見終わったよ。効率悪すぎだよね。全体的に見てどうかな。中国の408試験よりは全体的な難易度は少し低いけど、試験のスタイルや重点が違うから、具体的に比較するのはちょっと難しいね。次こそはもう少し効率良くできるといいな。

雑談

そういえば最近、雑談あんまり書いてないな。これって、記事を投稿しようって思うときにはもうヘトヘトで、書く気力がないからなんだよね。そういえば、昔は何かを学ぶかどうかだけを考えてたけど、今は時間とか体力とかも計算に入れなきゃいけないんだって思うようになったよ。最近見たネタなんだけど、

公務員試験も、選抜採用も、国家試験も、地方公務員試験も、教員免許も、留学も、インターンも、面接も、正社員登用も、就職活動も、卒業制作も、恋愛も、全部やればいいじゃん。でもまだ切り札は隠しておかないとね、中国人は何事も一手残すのが美学だから。

これ、すごく心に響いたよ。人間のエネルギーって限りがあるから、何かを得るためには必ず何かを失うんだよね。時間とか、体力とか、情熱とかさ。これらって実は全部数値化できる変数なんだけど、昔はそういう変数の上限が自分の活動よりもずっと大きくて、気づいてなかっただけなんだ（もちろん、消耗とか他の変換って可能性もあるから、念のため補足しとくね）。年齢を重ねるにつれて、経験とか見るものが増えていくと、だんだん考慮すべき変数が多くなってきて、そのせいで毎日すごく疲れて効率も悪くなってるんだろうな。

時々、生きるってすごく疲れるよね。もしかしたら僕が唯物論的すぎるのかもしれないな。もっと唯心論的に考えれば、世界はもっと素敵なはずだ（もう何事に対しても断定的な表現はできないな、不確実性が怖いんだ。でも人生って往々にして不確実なもので、それは変数を把握できてないからなんだけど、これ以上は広げないでおこう、また長くなっちゃうからね）。

背景

図５.１のように構成された、$ck$ を入力とし $z_2,z_1,z_0$ を出力とする論理回路Xを考える。ここで $R_0,R_1,R_2$ はポジティブエッジトリガ型（前縁トリガ型）Dフリップフロップであり、初期化時の出力は０とする。またF は $x_2,x_1,x_0$ を入力とし $y_2,y_1,y_0$ を出力とする論理回路であり、図５.２のように構成されている。AおよびBは図5.3に示されている2入力ゲートのいずれかとする。回路Xの入力 $ck$ に1単位時間を周期とするクロックパルスを与える。以下 $n$ を正整数、$t$ を時刻とする。時刻 $t=0$ において $R_0,R_1,R_2$ は初期化されており、時刻0以降 $n$ 個目のクロックパルスの立ち上がりによる出力が時刻 $t=n$ において $z_2,z_1,z_0$ に安定して得られるとする。この様子を図5.4に示す。以降、回路の構成要素（ゲート、フリップフロップおよび配線）による遅延はクロックパルスの周期と比較して十分小さく無視できるとする。

• 図5.1：論理回路X

• 図5.2：論理回路F

• 図5.3：2入力ゲート

• 図5.4：回路Xの動作

1

以下の問い a~f に答えよ。

a）回路Fの出力 $y_2,y_1,y_0$ は入力 $x_2,x_1,x_0$ の値のみで決まる。このような動作を行う回路の名称として最も適切なものを以下の選択肢から一つ選べ。

ア　非同期回路

イ　組み合わせ回路

ウ　順序回路

エ　非線形回路

b）時刻 $t=n$ における回路Xの出力 $z_2,z_1,z_0$ は、時刻 $t=$ アにおける $y_2,y_1,y_0$ の値それぞれと等しい。アを $n$ の式として表せ。

c）回路Xが図5.4に示すような動作をするための、回路Fの動作を表す真理値表を図5.5に示す表形式で完成させよ。

• 図5.5：回路Fの動作

d）図5.4のような動作を行う回路の名称として最も適切なものを以下の選択肢から一つ選び記号①～④で答えよ。

①デコーダ ②マルチプレクサ ③カウンタ ④シフトレジスタ

e）回路Ｘを図5.4のように動作させるためには図5.2のＡおよびＢにはそれぞれ何が入るか。図5.3から選び記号①～⑥で答えよ。同一のゲートを複数回用いてもよい。

f）論理変数 $x$ と $y$ の論理積（AND）を $xy$、論理和（OR）を $x+y$、$x$ の否定（NOT）を $\bar{x}$ と表記する。回路Fの出力 $y_2$ を

1-解答

1-a

• 非同期回路はクロック信号を使わず、各部分が独立して動作する回路を指します。
• 組み合わせ回路は、出力が入力の現在の値だけで決まる回路です。
• 順序回路は、出力が現在の入力だけでなく、内部の状態（フリップフロップの出力など）にも依存します。
• 非線形回路は、入力と出力の関係が線形でない特性を持つ回路を指します。

この問題は明らかに「組み合わせ回路」だね。

1-b

Dフリップフロップはまず入力を受け取って、クロックの立ち上がりエッジでのみ出力するから、状態更新の同期性によって、Dフリップフロップは1周期分の遅延をもたらすんだ。だからアは $n-1$ になるね。

1-c

1-d

• デコーダ（Decoder）：デコーダは、少ない入力信号を多数の出力信号にデコードする組み合わせ論理回路だよ。入力のバイナリコードに基づいて、対応する出力線をアクティブにするんだ。
• マルチプレクサ（Multiplexer）：マルチプレクサは、複数の入力信号から一つを選んで出力する組み合わせ論理回路だよ。選択信号（Select Lines）を使って、どの入力信号を出力に通すか決めるんだ。
• カウンタ（Counter）：カウンタは、パルス信号を数えるための順序論理回路だよ。パルス信号の数に応じて、カウンタの出力値が特定の方法で変わるんだ。
• シフトレジスタ（Shift Register）：シフトレジスタは、データを保存して、一定の方向にデータを移動させることができる順序論理回路だよ。一連のフリップフロップで構成されているんだ。

この問題は明らかに「シフトレジスタ」だね。

1-e

A: ② (OR) B: ① (AND)

真理値表と回路を使って分析するね。出力が複数あるから、一つずつ見ていけばいいよ。$y_0$ の回路はもう決まってるから、まず $y_1$ の出力が1になるときの入力を見てみよう。

回路を分析すると、入力 $x_2$ は一時的に無視できるよ（回路や次の問題から、簡略化後に $x_2$ がなくなるのがわかる）。

それから、1になる入力を代入して試してみたら、AがORゲートで、BがANDゲートだとわかったよ。

$y_2$ の出力が1になる入力で検証したら、結果は正しかったよ。

1-f

2

図5.6に示すGは $x_2,x_1,x_0$ を入力とし $y_2,y_1,y_0$ を出力とする論理回路である。Gを用いて、$ck$ を入力とし $z_2,z_1,z_0$ を出力とする論理回路Yを図5.7のように構成する。さらにYを用いて図5.8に示す論理回路 $X'$ を構成する。図5.8のCおよびDは図5.3に示されている2入力ゲートのいずれかである。以下の問い a~e に答えよ。

図5.6：論理回路G

図5.7：論理回路Y

図5.8：論理回路 $X'$

図5.9：回路Yの動作

a）回路Gでは出力 $y_0$ を得るためにゲートを5個用いている。図5.3に挙げたゲート2個以下を用いてGにおける $y_0$ と同じ出力を得ることができる回路を一つ記せ。

b）回路Yの入力 $ck$ に1単位時間を周期とするクロックパルスを与える。時刻 $t=0$ において $R_0,R_1,R_2$ は初期化されているとし、時刻0以降のｎ個目のクロックパルスの立ち上がりによる出力が時刻 $t=n$ において $z_2,z_1,z_0$ に安定して得られるとする。時刻 $t=1,4,7,12$ における回路Ｙの出力 $z_2,z_1,z_0$ を図5.9に示す表形式で完成させよ。

c）ｍを非負整数とする。上記ｂ）で示した条件下での時刻 $t=m$ における回路Ｙの出力の組 $(z_2,z_1,z_0)$ をベクトルとみなし $z(m)$ と表記する。$z(m)$ と $z(m+1)$ のハミング距離の最大値を答えよ。

d）図5.8の回路X’と図5.1の回路Xは同等のふるまいを示す。このとき図5.8のCおよびDに入るゲートを図5.3から選び、記号①～⑥で答えよ。同一のゲートを複数回用いてもよい。ここで同等のふるまいとは以下のことという。X’とXそれぞれの入力 $ck$ に図5.10のように同一のパルス発生源Ｐから1単位時間を周期とするクロックパルスを与える。時刻 $t=0$ においてX’およびX内のDクロックパルスの立ち上がりによる出力が時刻 $t=n$ において $w_2,w_1,w_0$ および $z_2,z_1,z_0$ それぞれに安定して得られているとき、 $w_2=z_2$ かつ $w_1=z_1$ かつ $w_0=z_0$ である。

• 図5.10

e）図5.11のような論理回路を考える。時刻 $t=t_0$ において入力ｘとｙが0から1に同時に変化したとする。このとき出力ｚは0のまま変化しないことが期待されるが、NOT ゲートにおける遅延が原因で図5.12に示すようなパルスが生じることがある。この現象はグリッチ（あるいはハザード）と呼ばれ、接続される回路によっては誤動作の原因となり得る。図5.8の回路Ｘ’において、ゲートＣ、Ｄにおける遅延が無視できない場合に出力 $w_0$ においてグリッチが発生し得るか否かを述べ、発生し得るなら対策方法を、発生しないならその理由を100文字以内で記せ。ただし回路Ｙの構成要素（ゲート、フリップフロップおよび配線）による遅延は無視できるものとし、$R_0,R_1,R_2$ それぞれの出力は同時に変化するものとする。

図5.11：グリッチを生じ得る論理回路の例

図5.12：グリッチの例

2-解答

2-a

回路を分析すると $y_0=x_1x_2+\bar{x_1}\bar{x_2}$ だから、これは $x_1\ \text{XNOR}\ x_2$ と等価だね。だからXNORゲートを一つ使うだけで回路を簡略化できるよ。

⑥だけ使用することができる。

2-b

$t=7$ からループしてるのがわかるね。

2-c

ハミング距離は、同じ長さの二つのバイナリベクトルで、異なるビットの数を示すものだよ。

上の真理値表から見ると、最大値は1だね。

2-d

C: ③ (XOR) D: ③ (XOR)

二つの回路のタイミングチャートを分析すると、真理値表が得られるよ。

回路を分析するんだけど、まず $w_1$ を見て、$w_1$ が1になる入力を探してみよう。

回路から $z_0$ は無視できることがわかるよ。残りの $z_1$ と $z_2$ は異なる入力で1を出力する形、つまりXORゲートの形をしてるから、DはXORゲートだね。

$w_0$ が1になる入力を分析しよう。

回路から、$z_0$ と $z_1 \oplus z_2$ を直接見ると、異なる入力で1を出力する形、つまりXORゲートの形をしてるから、CはXORゲートだね。

2-e

$w_0$ にグリッチが発生する可能性があるね。対策としては、出力にバッファを追加するか、同期フリップフロップを追加するか、それか回路設計を見直すのがいいと思うよ。

参考記事

論理代数の簡略化（公式法とカルノー図法）