\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{subfigure}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{float}

\newcommand{\vect}[1]{\mathbf{#1}}

\usepackage[top = 2.55cm, bottom=2.55cm, left = 2.55cm , right = 2.55cm]{geometry}

\makeatletter

\makeatother

\usepackage{color, graphics, times, mathptm}

\definecolor{light}{gray}{0.75}

\usepackage{fancyhdr}
 
\pagestyle{fancy}
\fancyhf{}
\rhead{ \textbf{CSE140 Exam 2, Week 7, Spring 2021} \hspace{1cm}
Name\hspace{4cm}}
\rfoot{Page \thepage}

\begin{document}
This is a take-home exam. You are allowed to check books, notes, and conduct an internet search.
However, you are expected to work on the solution by yourself. 
No discussion with anyone else is allowed.

There are two parts to the exam. Part A weighs 90 points.
Part B weighs 10 points. However, in Part B, the total weight of the problems
is higher than 10 points. You are encouraged to earn up to 
10 points. In other words, there is no penalty on
wrong solutions in Part B, but the maximum points to earn are limited to 10 points.

Please read the following instructions carefully.
If you are unclear about any of the questions on the exam,
make the most plausible assumption to answer the question.
Instructors and proctors will not answer questions on the exam material.
{\textbf{All the Best!}} \\

\noindent
{\LARGE Part A: (90 pts)}

\section{Timing Diagram of Latch and Flip-Flop}

\noindent
Given the input waveforms shown below, sketch the output D-Latch of the latch and
the output D-FF of the flip-flop. Label your drawing at the time points of the rising edges of the clock as
shown in the figure. (20 pts)

\begin{figure}[ht!]
\label{fig: fig1}
\centering
\includegraphics[width=1\textwidth]{midterm2-3.pdf}
\end{figure}

\section{Finite State Machine} A pattern recognizer inputs a string of binary
bits $x(t)$ and outputs $y(t)=1$ whenever $x(t-3,t)=1011$ or $1010$; $y(t)=0$ otherwise. (30 pts)

\noindent
1. Draw the state diagram for the state machine using a minimal number of states.
%\vspace{6cm}

\noindent
2. Write the state table for a state machine using 2 D Flip Flops. 
%\vspace{8cm}

\noindent
3. Describe $y(t), D_1 (t), D_0 (t)$ as functions of variables
$(x, Q_1 (t), Q_0 (t))$
in minimal sum-of-products expressions. No need to draw the logic diagram.

\section{Mealy and Moore Machine Conversion} Given a state table as below,
each entry of the table is the next state and output. (20 pts)

\begin{table}[!h]
    \centering
    \begin{tabular}{|c|c|c|c|}
        \hline
$id$ & $Q_1(t)~Q_0(t)$ & $x(t)=0$ & $x(t)=1$ \\ \hline
       0 & S0 &  S0,0 & S1,1 \\ \hline
       1 & S1 &  S0,1 & S3,0 \\ \hline
       2 & S2 &  S1,0 & S3,1 \\ \hline
       3 & S3 &  S2,0 & S4,1 \\ \hline
       4 & S4 &  S2,1 & S3,0 \\ \hline
    \end{tabular}
\end{table}

\noindent
1. Fill the following table as the machine starts at state $S0$ and process through
the given input $x$ from CLK (Clock) sequence =1 to 10.

\begin{table}[!h]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
        \hline
        CLK &   1   & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
        $x$   &   0   & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ \hline
        state & $S0$ &   &   &   &   &   &   &  &  &   \\ \hline
        $y$   &       &   &   &   &   &   &   & & &  \\ \hline
    \end{tabular}
\end{table}

\noindent
2. Convert the above machine into a Moore machine. Write the state table.
%\vspace{8cm}

\noindent
3. Use the Moore machine to fill the table starting at state $S0$ and process through
the given input $x$ from CLK (Clock) sequence 1 to 10.

\begin{table}[!h]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
        \hline
        CLK &   1   & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
        $x$   &   0   & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ \hline
        state & $S0$ &   &   &   &   &   &   &  &  &   \\ \hline
        $y$   &       &   &   &   &   &   &   & & &  \\ \hline
    \end{tabular}
\end{table}

\section{Timing and Retiming} For the following circuit (figure \ref{fig: fig2}, the timing
characteristics of the components are summarized below.(20 pts)
\begin{itemize}
    \item Flip-flop: clock-to-Q maximum delay (propagation delay) $t_{pcq}$ = 20ps,
 clock-to-Q minimum delay (contamination delay) $t_{ccq}$ = 15ps,
 setup time $t_{setup}$ = 10ps,
hold time $t_{hold}$ = 20ps
    \item Logic gate (e.g. Buffer, AND, OR, XOR, etc%Inverter
    ): propagation delay $t_{pd}(gate)$ = 15ps,
contamination delay $t_{cd}(gate)$ = 10ps.
\end{itemize}

\begin{figure}[H]
\label{fig: fig2}
\centering
\includegraphics[width=1\textwidth]{circuit_2.pdf}
\caption{A4. sequential circuit for retiming.}
\end{figure}

%\begin{figure}[ht!]
%\label{fig: fig1}
%\centering
%\includegraphics[width=0.6\textwidth]{Mid2_Timing_v1.pdf}
%\end{figure}

\noindent
1. Derive the minimal clock cycle time $T$, suppose that there is no clock skew.\\
%\vspace{2.5in}

\noindent
2. Derive the minimal clock cycle time $T$ using a designated skew.\\
%\vspace{1in}

%\vspace{4mm}
\noindent
{\LARGE Part B: (10 pts)}
8
In Part B, the total weight of the problems
is higher than 10 points. You are encouraged to earn up to 
10 points. In other words, there is no penalty on
wrong solutions, but the maximum points to earn are limited to 10 points.
Note that some problems are open, i.e. exact (perfect) solutions may be challenging to derive.
Nonetheless, the principles taught in the class can be used to start the exploration.\\

\noindent
{\textbf B.1. Latch:}
With reference to the SR latch of slide 14 of lecture 7, replace the NOR gate at the bottom
with a NAND gate.
Complete the state table \ref{TableB1}.
(5 pts)\\

\begin{table}[H]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
        \hline
$id$ & $S$ & $R$ & $Q_t$ & $y_t$ & $Q_{t+1}$ & $y_{t+1}$ & $Q_{t+2}$ & $y_{t+2}$ & $Q_{t+3}$ & $y_{t+3}$   \\ \hline
0 & 0 & 0 & 0 & 0 & & & & & &  \\ \hline
1 & 0 & 0 & 0 & 1 & & & & & & \\ \hline
2 & 0 & 0 & 1 & 0 & & & & & & \\ \hline
3 & 0 & 0 & 1 & 1 & & & & & & \\ \hline
4 & 0 & 1 & 0 & 0 & & & & & & \\ \hline
5 & 0 & 1 & 0 & 1 & & & & & & \\ \hline
6 & 0 & 1 & 1 & 0 & & & & & & \\ \hline
7 & 0 & 1 & 1 & 1 & & & & & & \\ \hline
8 & 1 & 0 & 0 & 0 & & & & & & \\ \hline
9 & 1 & 0 & 0 & 1 & & & & & & \\ \hline
10 & 1 & 0 & 1 & 0 & & & & & & \\ \hline
11 & 1 & 0 & 1 & 1 & & & & & & \\ \hline
12 & 1 & 1 & 0 & 0 & & & & & & \\ \hline
13 & 1 & 1 & 0 & 1 & & & & & & \\ \hline
14 & 1 & 1 & 1 & 0 & & & & & & \\ \hline
15 & 1 & 1 & 1 & 1 & & & & & & \\ \hline
    \end{tabular}
    \caption{B.1 State Table}
    \label{TableB1}
\end{table}

\noindent
{\textbf B.2. Finite State Machine:}
With reference to page 4 of lecture 8 slides, we have a pattern-matching game with a fair coin (50\% chance on either tail or head for each toss). The coin
is tossed in sequence. Each person chooses a pattern
of 4 consecutive tosses. The pattern that appears the first
wins.
Design a pattern so that you have the best chance to win.
Explain your solution.
(5 pts) \\

\noindent
{\textbf B.3. Timing and Retiming:}
For the following circuit (figure \ref{fig: fig3}), the timing
characteristics of the components are the same as
problem A.4. (5 pts)

\noindent
1. Derive the minimal clock cycle time $T$, suppose that there is no clock skew.
%\vspace{2.5in}

\noindent
2. Derive the minimal clock cycle time $T$ using a designated skew. Use $CLK1$ as the reference, write the amounts of skew of the rest of the clock signals, i.e. $CLK2$, $CLKS3$ and
$CLK4$ with respect to $CLK1$.\\

\begin{figure}[H]
\label{fig: fig3}
\centering
\includegraphics[width=1.0\textwidth]{circuit_1.pdf}
\caption{B3 sequential circuit for retiming.}
\end{figure}


\end{document}