はじめに
本記事は、院試に向けた論理回路の基本事項のまとめ記事になります。他の科目でもまとめ記事を作成しており、同じく取り上げます。
論理回路を出題する大学は、大変多いです。出題しない大学を見つける方が難しいレベルです。
電気系の電磁気学と同じく、情報系の定番科目となっています。
論理関数の簡単化から順序回路まで説明していきます。出願大学の頻出事項と合わせてご覧ください。
論理関数
入力変数と出力ともに、0,1の2値で表現する関数を言います。
中学数学から関数を扱ってきましたが、変数の取りうる値は0.5などの小数も含まれていましたが、論理関数にはそれが無いです。
基本演算子は、NOT、AND、ORとなっています。
NOTは、与えた入力の0,1を反転
ANDは、入力変数すべてが1のとき、出力が1
ORは、入力変数のうちいずれかが1のとき、出力が1
以上で計算できます。勿論、院試問題ではAND、ORが単体で出題されることは無く、これらの組み合わせで様々な関数を表現します。
閾値関数を通して、自己双対関数との関係なども問われることがあります。
上記の論理関数群は、一昔前の東北大でよく出題されていました。しかし、最近は後述する論理回路が良く問われます。知識として入れておく程度で良いかもしれません。
論理関数の簡単化
カルノー図、またはクワインマクラスキー法で実現できます。
両者、実現手段に違いがありますが、出力1を取る変数の組み合わせのうち、ハミング距離が1異なる変数同士をマージする作業に終始します。
人間の目では、カルノー図の方が分かりやすいですが、計算機としてはクワインマクラスキー法の簡単化方法の方が実装しやすい特徴があります。
下記の記事で、積和最簡形、和積最簡形とセットで解説しています。
論理回路
論理関数を論理回路素子で表現したものになります。
使用する基本的な論理回路素子は、NOT、AND、ORになります。(排他的論理和(XOR)もありますが、ここでは割愛します。)
論理回路を作成する問題では、与えた論理関数をそのまま実装するだけで解決できるものは少なく、使用する論理回路素子に制約を設けて問われることが多々あります。
ドモルガン律を使用して解決することが多いです。下記の記事で紹介しています。
加算器
頻出分野となっています。
論理回路の世界での足し算は2進数で行われることから、最下位bitから上位bitに向かって演算していきます。
注目した”i bit目”におけるキャリーフラグ$C_i$と和$S_i$を用いて下記の論理式で表されます。
\begin{cases}C_{i}=a_{i}b_{i}+\left( a_{i} \oplus b_{i} \right ) C_{i-1} \\ S_{i}= a_{i} \oplus b_{i} \oplus C_{i-1}\end{cases}
上記は、桁上げ伝搬加算器の計算手法ですが、先見加算器で問われることもあります。下記の記事で紹介しています。
順序回路
クロックに基づいて計算結果が周期ごとに切り替わっていく回路を言います。院試でよく問われるのは、Dフリップフロップ、SRフリップフロップ、JKフリップフロップの3つです。
特にDフリップフロップは、大学問わずに頻出です。カウンタの方式で聞かれることが多いので、下記の記事で練習しましょう。
SRフリップフロップ、JKフリップフロップは下記の記事で紹介しています。Dフリップフロップは、次回のクロック周期において内部に保持した値を出力する構成になっていますが、SRフリップフロップは、セット：S、リセット：Rを用いて入出力を表現します。JKフリップフロップは保持することもできます。
最後に
論理回路は、意外と知識がものを言う問題が多いですが、最悪知らなくても真理値表から解決していく方法もあります。試験本番で、知らない問題が出て来ても、粘り強く実験していきましょう。
