情報

閾値関数は、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}が成立するとき、線形関数と呼ぶ。

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

(1)下記の言語が正規言語ではないことを反復補題を利用して証明せよ。\begin{eqnarray}L=({a^{n},b^{n} | n≧0})\end{eqnarray}(2)自由文脈文法\(G_{1}=(N_{1},\Sigma_{1...

2進表現について、以下の問に答えよ。 (1) (i)+78 (ii)-66 を8bitの2進数表記でそれぞれ表せ (2)下記の2の補数表現の8bitの情報を絶対値表記に変換せよ。 (i)00001111 (ii)11110000 (3)下記...

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

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