情報

閾値関数は、1を取る変数の数が一定個数(T)以上のとき、必ず1を取る。逆に、1を取る変数の数が一定個数未満のとき、必ず0を取る。自己双対(関数の否定)を取ると、n-T個以下のとき、必ず0を取るようになる。

はじめに論理回路を使用した算術問題は、院試頻出分野になっています。先日の記事では、加算器の設計についてお話してきました。本記事では、比較器(コンパレータ)の設計方法について紹介していきます。

加算器の回路設計は、院試頻出分野です。全加算器を使用し、桁上げ伝搬加算器を作成することが多いですが、計算時間が長い課題があります。そこで、伝搬加算器を改良した先見加算器、保存加算器が出題されることがあります。少し難しいですが、是非マスターして得点源になれば幸いです。

論理関数\(f_{1}\left( x_{1},x_{2},\ldots ,x_{i},\ldots ,x_{j},\ldots x_{n}\right)\)の\(x_{i},x_{j}\)を入れ替えた関数\(f_{2}\left( x_{1},x_{2},\ldots ,x_{j},\ldots ,x_{i},\ldots x_{n}\right)\)の\(x_{i},x_{j}\)を考える。任意の\(i,j\)について\(f_{1},f_{2}\)の出力が等しいとき、n変数対称関数と言う。

あるn変数論理関数について、\begin{eqnarray}f\left( x_{1},x_{2},\ldots ,x_{n}\right)=c_{0}\oplus c_{1}x_{1}\oplus c_{2}x_{2}\oplus \ldots \oplus c_{n}x_{n}\end{eqnarray}が成立するとき、線形関数と呼ぶ。

論理関数の性質に関する問題は、東北大を初め、京大などで出題されます。閾値関数、対称関数、正関数など、様々な関数が存在しますが、本問ではまず自己双対関数の性質について例題を用いて説明していきます。

オートマトンを試験範囲とする大学で、たまに出題される証明問題です。 ※頻出問題としては、ある言語Lが与えられ、それに対応するオートマトンを作成する問題があります。こちらに関しては別サイトでの解説が豊富なので、今回は省略します。

10進数➡2の補数表記 似たような解き方はいくつかありますが、本サイトでは下記のやり方をオススメしています。 変換元の10進数(絶対値)から、2の累乗で表せる数の最大値を0になるまで引いていく。 0になったとき、今まで引いてきた2の累乗に対応するbitに1を立てる。 変換元の10進数が負の場合、bit反転し、最下位bitに1を足す。

再帰関数を分解し、計算時間の見積もりをする行為は、ソフト作成において非常に重要な作業になります。本記事では、再帰式からの計算時間量の見積もり方法について紹介します。

電気回路の過渡解析を、オイラー法を用いて行います。非線形素子の無い一般的なLR直列回路は、回路方程式をラプラス変換を使用して解くことが出来ます。今回は、発展形として非線形素子が付いている場合について紹介します。