110年 - 110 國立臺灣大學_碩士班招生考試_電子工程研究所丁組:邏輯設計#101259

科目：研究所、轉學考(插大)◆邏輯設計 | 年份：110年 | 選擇題數：0 | 申論題數：18

試卷資訊

所屬科目：研究所、轉學考(插大)◆邏輯設計

選擇題 (0)

申論題 (18)

(a) (4%) Show that the set ( AND, OR, NOT) of logic operations is functionally complete, that is, any Boolean function can be represented with this set of logic operations.

(b) (4%) Is the set consisting of only majority gate MAJ functionally complete? Justify your answer. (Note that the majority gate MAJ(a,b,c) with three inputs a, b, c equals 1 if and only if at least two of the inputs are 1.)

(c) (4%) Is the set consisting of only minority gate MIN functionally complete? Justify your answer. (Note that the minority gate MIN(a,b,c) with three inputs a, b, c equals 1 if and only if at most one of the inputs is 1.)

(d) (4%) Can any Boolean function be represented in the exclusive-sun-of products (ESOP) expression, which is the AND-XOR two-level expression (with first level AND and second level XOR)? Justify your answer.

(e)(4%) Can any Boolean function be represented in the exclusive-product-of-suns (EPOS) expression, which is the XOR-AND two-level expression (with first level XOR and second level AND)? Justify your answer.

(a) (10%) Prove by induction that it represents an odd-parity function, that is, it evaluates to 1 if and only if the assignment to variables X₁,...,X_n contains an odd number of 1's. (For example, the assignment (X₁, X₂, X₃, X₄)= (1,0,0,0) contains one 1.)

(b) (5%) How many product terms are there for its minimum sum-of-products (SOP) expression?

(c) (5%) How many sum terms are there for its minimum product-of-sums (POS) expression?

(a) (5%) Determine the minimum clock cycle that the circuit can operate.

(b) (5%) Determine the constraint on the flip-flop hold time for the circuit to operate correctly.

(c) (5%) Assume the combinational part of the circuit is to be re-implemented by a single read-only memory (ROM). Determine the size of the ROM in terms of 1) the number of words and 2) the bit-width of each word.

(d) (5%) Assume the circuit is initially in state (A,B,C,D) = (0,0,0,0). Determine the corresponding state-transition sequence and output sequence with respect to the input sequence 0, 1, 1.

(a) (10%) Draw the corresponding state graph and identify all equivalent states, if there is any, for state minimization.

(b) (10%) Implement the circuit with three D flip-lops and one majority gate MAJ.

(a)(5%) Find all possible initial state pairs between M₁and M₂ that make the two circuits behave the same.

(b) (5%) Let M₁ starts from state C and M₂ starts from state T. What is the minimum length of an input sequence that makes M₁ and M₂ produce different outputs? Justify your answer.

(c) (5%) Are there equivalent states in M₁? If yes, which states are equivalent?

(d) (5%) Assume S is the initial state of M₂. Identify all the states in M₂ that can be reached from S. (We say that state A can reach state B if there exists a sequence of state transitions from A to B.)