You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

119 lines
3.4 KiB

\documentclass{article}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\title{Homework 3}
\begin{document}
\maketitle
\section*{Q1}
Given the logical formula, we can follow
the following process to convert it into strictly
inverters, NOR, and NAND gates:
\begin{equation*}
\begin{aligned}
& \lnot((AB+C)D+E) \\
\Leftrightarrow & \lnot(\lnot\lnot(AB+C)D+E) & \text{(negation involutive)} \\
\Leftrightarrow & \lnot(\lnot(\lnot(AB+C)+\lnot D)+E) & \text{(DeMorgan's Laws)} \\
\Leftrightarrow & \lnot(\lnot(\lnot(\lnot\lnot AB+C)+\lnot D)+E) & \text{(negation involutive)} \\
\Leftrightarrow & \lnot(\lnot(\lnot(\lnot(\lnot A + \lnot B)+C)+\lnot D)+E) & \text{(DeMorgan's Laws)} \\
\end{aligned}
\end{equation*}
This corresponds to the following circuit:
\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{Q1HW3.png}
\end{figure}
\pagebreak
\section*{Q2}
Making Scott's adjustment (adding a top-level 'not' to the formula in the assignment) yields the following:
\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{Q2.png}
\end{figure}
\pagebreak
\section*{Q3}
The book gives the following equation for determing the ideal number of stages:
\begin{equation*}
\begin{aligned}
N &= \log_{\rho}F \\
0 &= p_\text{inv} + \rho(1-\ln\rho)
\end{aligned}
\end{equation*}
Where $p_\text{inv}$ is the intrinsic delay of an inverter.
For $p_\text{inv} = 5$, we have $\rho = 6.14$. We then compute $F$:
\begin{equation*}
\begin{aligned}
& F &= GBH \\
& G &= 1 \\
& B &= 1 \\
& H &= 1000 \\
\Rightarrow & F &= 1000
\end{aligned}
\end{equation*}
The ideal number of stages is then:
\begin{equation*}
\log_\rho F = 3.8 \approx 4
\end{equation*}
For all inverters, then, we get the following:
\begin{equation*}
\begin{aligned}
\hat{f} &= \sqrt[4]{1000} \\
\text{sz}_4 &= 1000/\hat{f}^1 = 178 \\
\text{sz}_3 &= 1000/\hat{f}^2 = 31.6 \\
\text{sz}_2 &= 1000/\hat{f}^3 = 5.62 \\
\text{sz}_1 &= 1000/\hat{f}^4 = 1 \\
\end{aligned}
\end{equation*}
\pagebreak
\section*{Q4}
First, to compute total effort $F$.
\begin{equation*}
\begin{aligned}
& F &= GBH \\
& G &= \left(\frac{4}{3}\right)\left(\frac{5}{3}\right)\left(\frac{5}{3}\right) \\
& B &= 3 \\
& H &= 1000 \\
\Rightarrow & F &= 11111
\end{aligned}
\end{equation*}
Since we are using the same inverter as the one in Q3, we are
once again using $p_\text{inv}=5$, and thus, have that $\rho=6.138$.
From this, we can determine the ideal number of stages:
\begin{equation*}
\log_\rho F = 5.13 \approx 5
\end{equation*}
Since we currently have 3 stages, we should insert 2 inverters.
I will insert these at the end of the path in question. From
there, we once again compute stage effort $\hat{f}$, and work
backwards to determine the optimal sizes for all of the stages.
\begin{equation*}
\begin{aligned}
\hat{f} &= \sqrt[5]{11111} \\
\text{sz}_\text{inv1} &= 1000/\hat{f}^1 = 155 \\
\text{sz}_\text{inv2} &= 1000/\hat{f}^2 = 24.1 \\
\text{sz}_\text{nand3} &= 1000/\hat{f}^3 * \left(\frac{5}{3}\right) = 6.23 \\
\text{sz}_\text{nor2} &= 1000/\hat{f}^4 * \left(\frac{5}{3}\right)\left(\frac{5}{3}\right) = 1.61 \\
\text{sz}_\text{nand2} &= 1000/\hat{f}^5 * \left(\frac{5}{3}\right)\left(\frac{5}{3}\right)\left(\frac{4}{3}\right)3 = 1
\end{aligned}
\end{equation*}
\end{document}