2015 年 6 月 19 日 小野寺秀俊 論理回路 1 1.1 順序回路 順序回路とは 組合せ回路 (combinational circuit) 出力がその時点での入力のみにより決まる。 順序回路 (sequential circuit) 出力がその時点での入力とともに、過去の入力系列にも 依存する。順序回路は、組合せ回路と記憶回路で構成される。(図 1 参照) 同期式順序回路 (synchronous sequential circuit) 入力変数と状態変数の値を、クロッ ク (0 と 1 を一定周期 T で繰り返す信号) に同期して一斉に変化させる回路。クロッ クの周期 T は、組合せ回路の演算時間より長くとる。同期式順序回路では、T が時 間の単位となる。時刻 t における入力変数 (input variable) xi (t), (i = 1, 2, · · · , n) の 値が定まると、時刻 t における出力変数 (output variable) zj (t), (j = 1, 2, · · · , m) と、 時刻 t + 1 における状態変数 (state variable) yk (t + 1), (k = 1, 2, · · · , s) は、 zj (t) = gj (x1 (t), x2 (t), · · · , xn (t), y1 (t), y2 (t), · · · ys (t)) yk (t + 1) = fk (x1 (t), x2 (t), · · · , xn (t), y1 (t), y2 (t), · · · ys (t)) のように論理関数で表現できる。このとき、gj を出力関数、fk を状態遷移関数 (励 起関数) という。 非同期式順序回路 (asynchronous sequential circuit) クロックを持たない順序回路。 1.2 順序回路の表現法 有限状態機械 (FSM: Finite state machine) 順序回路の動作を数学的に表現したもの。 ミーリ型機械 (Mealy machine) は、M = (S, I, O, δ, λ) なる 5 組で定義される。こ こで、S は状態集合、I は入力集合、O は出力集合、 δ : S × I → S は状態遷移関 数 (state transition function)、λ : S × I → O は出力関数 (output function) である。 ムーア型機械 (Moore machine) は、出力関数が λ : S → O となったもの。すなわ ち、ミーリ型機械は出力が現状態と入力の関数になっており、ムーア型機械は出力 が現状態のみの関数となっている。図 2 参照 状態遷移図 (state transition diagram) 順序回路の内部状態とその遷移を表現した有向 グラフ。各節点は内部状態に対応し、各有向枝は状態遷移に対応する。各有向枝に は、その遷移を起こす入力と、そのときの出力が “入力”/“出力” という書式でラベ ル付けされる。 例 150 円のジュースを売る自動販売機。100 円硬貨と 50 円硬貨のみを受け付け、お つりも出す。 入力は「硬貨が投入されなかった」「50 円硬貨が投入された」「100 円硬貨が投入さ れた」の 3 種類 (I1 ,I2 ,I3 ) 。出力は「何も出さない」 「ジュースを出す」 「ジュースと おつりを出す」の 3 種類 (O1 , O2 , O3 ) 。内部状態は「何もお金が入っていない」 「50 円入った状態」「100 円入った状態」の 3 種類 (S1 , S2 , S3 ) 。 図 3 参照 状態遷移表 状態遷移と出力の様子を表で表したもの。各行が現状態に対応し、各列は入 力の値に対応する。現状態と入力により次状態と出力がどうなるかを示したもの (状 態遷移と出力を別けて表現する場合もある—遷移表と出力表—)。表 1 参照 状態割当てと符合化 内部状態を符号化 (論理変数で表現) することを状態割当て (state assignment) という。n 個の状態変数で、最大 2n 個の内部状態を表現できるが、状 態割当ての方法により回路 (組合せ回路部分) の複雑度が異なる。入力や出力も記号 で表現されている場合には符合化するが、この符号化の方法によっても回路の複雑 度が異なってくる。表 2(状態割当てと符号化の例) 表 2 の状態割り当てと符号化を施した後の遷移表および主力表が表 3。 状態割当てにおける符号化の例 最短符号 (minimum length code) n 個の状態を表すための、[log2 n] ビットの符 号。必要な記憶素子 (フリップフロップ) 数が最小である。 例 4 状態を符号化するには、最低 2 ビット必要。最短符号を用いた状態の割当 て方は全体で 4! = 24 通り存在する。 状態割当てのヒント: 状態遷移が頻繁に生ずる状態対の符号のハミング距離を なるべく小さくする。 1 ホット符号 (1-hot code) n 個の状態を表すための、一カ所のみが 1 で他が 0 の n ビット符号。最短符号に比べ記憶素子が多く必要であるが、組合せ回路部分が 簡単になることが期待される。高速性を狙った回路で有効。 1.3 フリップフロップ 順序回路の記憶回路として、ラッチ (latch) やフリップフロップ (flip-flop: FF と略記) と 呼ばれる 1 ビットの記憶素子を用いる。ラッチは、入力の変化に応じて出力が直ちに変化 する素子。FF は、外部から与える信号 (クロック) に同期して、出力が変化する素子。ラッ チの中で、制御信号入力を持つものをレベルセンシティブラッチ (level-sensitive latch)、 持たないものを透過型ラッチ (transparent latch) という。 SR ラッチ NOR や NAND などの否定ゲートをたすき掛けに接続した回路。S=1, R=0 の とき Q=1 となる (セットされる)。S=0, R=1 のとき Q=0 となる (リセットされる)。 S=R=0 のとき、二つの安定状態 (Q=1 または 0) を持つ。すなわち、以前の状態が 保持される。S=1, R=1 は入力禁止。 マスタースレーブ型 SR FF クロックに同期して出力を変化させるため、入力をサンプ ルするラッチと出力を保持するラッチを従属接続し、それぞれが逆位相のクロック で動作するようにしたもの。入力側のラッチをマスター (master) ラッチ、出力側を スレーブ (slave) ラッチという。 特性方程式は、Q(t + 1) = S + RQ(t) 但し S · R = 0。 マスタースレーブ型 D FF マスタースレーブ型 SR FF の R に S を入力するもの。 特性方程式は、Q(t + 1) = D。現在の入力が、次の時刻の出力となる。すなわち、 入力 D の値を遅延 (delay) させる機能がある。 マスタースレーブ型 JK FF SR FF の禁止入力において、出力が反転するようにスレー ブラッチからマスターラッチにフィードバックをかけている。 特性方程式は、Q(t + 1) = JQ(t) + KQ(t)。 マスタースレーブ型 T FF JK FF で J = K としたもの。T = 1 のとき、1 クロックごと に状態が反転する。T = 0 のときには、状態は変化しない。 特性方程式は、Q(t + 1) = T Q(t) + T Q(t) S R 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 Q(t) Q(t+1) 0 1 0 1 0 1 0 1 0 1 0 0 1 1 X X ホールド リセット セット 入力禁止 J K Q(t) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 Q(t+1) 0 1 0 0 1 1 1 0 ホールド リセット セット トグル 各 FF の駆動条件 順序回路の記憶素子として FF を用いる場合、FF の出力が順序回路の 状態変数に対応する。次のクロックで (次の時刻で)、順序回路が所望の状態遷移を 行なうためには、FF に適切な入力を与える (組合せ回路部分で適切な値を作成する) 必要がある。各種の FF において、それぞれの状態遷移を起こすために必要な入力 値を以下に示す (大変重要: 必ず導出できること)。組み合わせ回路部分は、FF を駆 動する関数、すなわち励起関数 (excitation function) を実現するように設計する。 Q(t) → Q(t + 1) 0→0 0→1 1→0 1→1 S 0 1 0 * R * 0 1 0 D 0 1 0 1 J 0 1 * * K * * 1 0 T 0 1 1 0 入力変数 x1 x2 xn I 出力変数 ・ ・ ・ z1 z2 ・ ・ ・ 組合せ回路 λ 出力関数 O δ 状態遷移関数 S zm y1 ys Mealy型 (Mealy machine) 状態変数 I 記憶回路 図1 λ 出力関数 O δ 状態遷移関数 S 順序回路の概念図 Moore型 (Moore machine) 図2 表1 状態遷移表 I 2/ O1 I 1/ O1 I 1/ O1 S1 S2 I 3/ O2 I 2/ O2 I 3/ O1 I 2/ O1 I 3/ O3 次状態、出力 現状態 入力 I2 I1 I3 S1 S 1 , O1 S 2 , O1 S 3 , O1 S2 S 2 , O1 S 3 , O1 S 1 , O2 S3 S 3 , O1 S 1 , O2 S 1 , O3 S3 I 1/ O1 図3 表2 S 1 未投入 S 2 50円投入済 S 3 100円投入済 状態遷移図 状態割当(一例) state assigment 符合化(一例) encoding I 1 無投入 I 2 50円投入 I 3 100円投入 O 1 何も出さない O 2 ジュースを出す O 3 ジュースと50円を出す 状態割当て及び符合化後の遷移表および出力表 y1y2 z1z2 x1 x2 出力 z1 z2 x1x2 y1y2 0 0 0 1 1 1 1 0 00 01 11 10 I1 0 0 O1 0 0 00 00 01 * * 11 00 00 * * 00 0 1 I2 0 1 O2 0 1 01 01 11 * * 00 00 00 * * 01 1 1 I3 1 0 O3 1 1 11 11 00 * * 00 00 01 * * 11 10 * * * * * * * * * * * * * * * * 状態 y1 y2 S1 0 0 S2 S3 入力 x1x2 S R Q S Q (norで) S Q S Q R R Q Q Q CK R Q S Q R Q D Q CK (nandで) level-sensitive SR latch SR latch S Q S Q D S >CK R Q R Q >CK Q R CK >CK Q Q master-slave D FF master-slave SR FF (negative edge-triggered) (negative edge-triggered) J Q J Q T J >CK K Q K Q T >CK Q K Q >CK Q Q CK master-slave JK FF master-slave T FF R Q D Q D ck >CK CK Q S ck ck Q ck \Q ck switch: ck=1でon, ck=0でoff D Negative edge-triggered D FF (bipolar) Negative edge-triggered D FF (CMOS)
© Copyright 2024 ExpyDoc
