From 211d0ff6835017ba4c237fa909837ca84e1e095b Mon Sep 17 00:00:00 2001 From: Julian T Date: Mon, 31 May 2021 11:30:40 +0200 Subject: Add many more solutions and notes --- sem6/dig/m2/Makefile | 2 +- sem6/dig/m2/ex1.vhdl | 23 +++++++ sem6/dig/m2/ex3.vhdl | 15 +++++ sem6/dig/m2/noter.tex | 35 ++++++++++ sem6/dig/m4/Makefile | 2 +- sem6/dig/m4/ex2.vhdl | 11 ++- sem6/dig/m4/ex3.vhdl | 2 +- sem6/dig/m4/ex4.vhdl | 32 +++++++++ sem6/dig/m4/noter.tex | 75 +++++++++++++++++++++ sem6/dig/mm1/opgaver.md | 2 + sem6/dig/mm1/opgaver.tex | 169 +++++++++++++++++++++++++++++++++++++++++++++++ sem6/dig/shell.nix | 7 ++ 12 files changed, 370 insertions(+), 5 deletions(-) create mode 100644 sem6/dig/m2/ex1.vhdl create mode 100644 sem6/dig/m2/ex3.vhdl create mode 100644 sem6/dig/m2/noter.tex create mode 100644 sem6/dig/m4/ex4.vhdl create mode 100644 sem6/dig/m4/noter.tex create mode 100644 sem6/dig/mm1/opgaver.tex create mode 100644 sem6/dig/shell.nix (limited to 'sem6/dig') diff --git a/sem6/dig/m2/Makefile b/sem6/dig/m2/Makefile index 4f83294..2a4d25a 100644 --- a/sem6/dig/m2/Makefile +++ b/sem6/dig/m2/Makefile @@ -1,4 +1,4 @@ -INPUTFILES = nor_gate ex2 ex5 ex6 +INPUTFILES = nor_gate ex1 ex2 ex5 ex6 ex3 include ../common.mk diff --git a/sem6/dig/m2/ex1.vhdl b/sem6/dig/m2/ex1.vhdl new file mode 100644 index 0000000..33b187c --- /dev/null +++ b/sem6/dig/m2/ex1.vhdl @@ -0,0 +1,23 @@ +-- TEST_START{"inputs": ["sw1", "sw2", "sw3", "sw4"], "outputs": ["l1", "l2", "l3", "l4"], "testin": ["0000", "0001", "0101", "1101", "1010"]}TEST_STOP +LIBRARY IEEE; +USE IEEE.STD_LOGIC_1164.all; + +ENTITY ex1 IS + PORT( + sw1: IN STD_LOGIC; + sw2: IN STD_LOGIC; + sw3: IN STD_LOGIC; + sw4: IN STD_LOGIC; + l1: OUT STD_LOGIC; + l2: OUT STD_LOGIC; + l3: OUT STD_LOGIC; + l4: OUT STD_LOGIC); +END ex1; + +ARCHITECTURE impl OF ex1 IS +BEGIN + l1 <= sw1; + l2 <= sw2; + l3 <= sw3; + l4 <= sw4; +END impl; diff --git a/sem6/dig/m2/ex3.vhdl b/sem6/dig/m2/ex3.vhdl new file mode 100644 index 0000000..8b3603a --- /dev/null +++ b/sem6/dig/m2/ex3.vhdl @@ -0,0 +1,15 @@ +-- TEST_START{"inputs": ["a", "b"], "outputs": ["o"], "testin": ["00", "01", "10", "11"]}TEST_STOP +LIBRARY IEEE; +USE IEEE.STD_LOGIC_1164.all; + +ENTITY ex3 IS + PORT( + a: IN STD_LOGIC; + b: IN STD_LOGIC; + o: OUT STD_LOGIC); +END ex3; + +ARCHITECTURE impl OF ex3 IS +BEGIN + o <= a and b; +END impl; diff --git a/sem6/dig/m2/noter.tex b/sem6/dig/m2/noter.tex new file mode 100644 index 0000000..7a5c531 --- /dev/null +++ b/sem6/dig/m2/noter.tex @@ -0,0 +1,35 @@ +\title{Mininoter} + +Der findes har 3 forskellige typer: +\begin{itemize} + \item Island style eller array type som brugt af Xilinx + \item Hierachical brugt af Altera + \item Logarithmic hvilket er mere eksotisk +\end{itemize} + +Island style indeholder CE (Configurable Elements), IM (Interconnection Matrix) og CB (Connection Block). + +Hierachical har mere ting i hierachier i stedet for et grid. + +\section{VHDL} + +Architecture er en implementation af et design. +Et design kan have flere implementation hvilket er grunden til at man skal give den et unikt navn. + +\texttt{inout} er også en mulighed for pin type, og giver en bidirectional port. + +Forskellige værdier til \texttt{STD_LOGIC} og \texttt{STD_LOGIC_VECTOR}. + +\begin{itemize} + \item \texttt{1} -- forced high + \item \texttt{0} -- forced low + \item \texttt{Z} -- high impedance + \item \texttt{U} -- Uninitialized + \item \texttt{X} -- unknown, low impedance + \item \texttt{W} -- unknown (weak), low impedance + \item \texttt{L} -- weak 0 + \item \texttt{H} -- weak 1 + \item \texttt{-} -- wild card, don't care +\end{itemize} + +Port maps are used to compose modules at a higher level. diff --git a/sem6/dig/m4/Makefile b/sem6/dig/m4/Makefile index 1c04cdd..7c53246 100644 --- a/sem6/dig/m4/Makefile +++ b/sem6/dig/m4/Makefile @@ -1,4 +1,4 @@ -INPUTFILES=ex1 ex2 ex3 +INPUTFILES=ex1 ex2 ex3 ex4 include ../common.mk diff --git a/sem6/dig/m4/ex2.vhdl b/sem6/dig/m4/ex2.vhdl index 76883ad..cb7e952 100644 --- a/sem6/dig/m4/ex2.vhdl +++ b/sem6/dig/m4/ex2.vhdl @@ -1,4 +1,4 @@ --- TEST_START{"inputs": ["sw0"], "outputs": ["o,3,0"], "clk": "bt0", "testin": "000111001001"}TEST_STOP +-- TEST_START{"inputs": ["sw0"], "outputs": ["o,3,0"], "clk": "bt0", "testin": "010111110000001100"}TEST_STOP library ieee; use ieee.std_logic_1164.all; @@ -17,12 +17,19 @@ begin -- Implement shifting next_state(3 downto 1) <= state(2 downto 0); next_state(0) <= sw0; - o <= state; process (bt0) + variable bit_count : integer range 0 to 3; begin if (bt0'event and bt0 = '1') then state <= next_state; + + if (bit_count = 3) then + o <= next_state; + bit_count := 0; + else + bit_count := bit_count + 1; + end if; end if; end process; end impl; diff --git a/sem6/dig/m4/ex3.vhdl b/sem6/dig/m4/ex3.vhdl index 650d303..0fc1062 100644 --- a/sem6/dig/m4/ex3.vhdl +++ b/sem6/dig/m4/ex3.vhdl @@ -1,4 +1,4 @@ --- TEST_START{"inputs": ["input,3,0", "write", "read"], "outputs": ["output,3,0"], "testin": [["0000", 0, 0], ["0000", 0, 1], ["1010", 1, 0], ["0000", 0, 1], ["1100", 1, 1], ["0011", 1, 1]]}TEST_STOP +-- TEST_START{"inputs": ["input,3,0", "write", "read"], "outputs": ["output,3,0"], "testin": [["0000", 0, 0], ["0000", 0, 1], ["1010", 1, 0], ["0000", 0, 1], ["0000", 0, 0], ["0000", 0, 1], ["1100", 1, 1], ["0011", 1, 1]]}TEST_STOP library ieee; use ieee.std_logic_1164.all; diff --git a/sem6/dig/m4/ex4.vhdl b/sem6/dig/m4/ex4.vhdl new file mode 100644 index 0000000..57537bd --- /dev/null +++ b/sem6/dig/m4/ex4.vhdl @@ -0,0 +1,32 @@ +-- TEST_START{"inputs": ["input,7,0", "write", "read"], "outputs": ["output,7,0"], "testin": [["00000000", 0, 0], ["00000000", 0, 1], ["10101010", 1, 0], ["00000000", 0, 1], ["00000000", 0, 0], ["00000000", 0, 1], ["11001010", 1, 1], ["00111111", 1, 1]]}TEST_STOP +library ieee; +use ieee.std_logic_1164.all; + +entity ex4 is + port ( + input: in std_logic_vector(7 downto 0); + write: in std_logic; + read: in std_logic; + output: out std_logic_vector(7 downto 0) + ); +end ex4; + +architecture impl of ex4 is +begin + + mem_low : ENTITY work.ex3 + PORT MAP ( + input => input(3 downto 0), + write => write, + read => read, + output => output(3 downto 0) + ); + + mem_high : ENTITY work.ex3 + PORT MAP ( + input => input(7 downto 4), + write => write, + read => read, + output => output(7 downto 4) + ); +end impl; diff --git a/sem6/dig/m4/noter.tex b/sem6/dig/m4/noter.tex new file mode 100644 index 0000000..de217fd --- /dev/null +++ b/sem6/dig/m4/noter.tex @@ -0,0 +1,75 @@ +\title{Noter til Lektion} + +Dette handlede meget om VHDL men vil mest forklare lidt om logic og nogle forskellige ting man kan lave. + +\paragraph{Combinatorial Cirquits} er når man har et kredsløb som er en direkt function af input, som for eksempel en and gate. + +Herfra kan man implementere memory så output fra kreds afhænger af alt tidligere input. +Dette bliver kaldt \textbf{Sequential Cirquits}. +For det meste bliver denne afhængighed implementeret med en slags \emph{state variabel}. + +De forskellige kan ses i slides og der er nok en god ide at finde dem frem til eksamnen. + +\paragraph{SR latch} er en meget simpel hvor man en set og en reset input, og et output. +Den har følgende sandhedstabel. + +\begin{tabular}{ll|ll} \toprule + $S$ & $R$ & $Q$ & $\neg Q$ \\ \midrule + 0 & 0 & Last $Q$ & Last $\neg Q$ \\ + 0 & 1 & 0 & 1 \\ + 1 & 0 & 1 & 0 \\ + 1 & 1 & 0 & 0 \\ \bottomrule +\end{tabular} + +Her er det lidt et problem at have en state hvor både $Q$ og $\neg Q$ er 0. +Dette giver jo ikke så meget mening. + +Det også tit en fordel at have en \emph{clock} så man kan bestemme hvornår værdier skal gemmes. +Dette kan let implementeres med nogle NOR gates. + +\paragraph{D latch} udskifter $R$ og $S$ med en et enkelt input og en clock. +Dette giver mening da man gemmer en værdi på $D$ ved at clock $C$, også er den gemt til man giver den en ny værdi. + +\begin{tabular}{ll|ll} \toprule + $C$ & $D$ & $Q$ & $\neg Q$ \\ \midrule + 0 & x & Last $Q$ & Last $\neg Q$ \\ + 1 & 0 & 0 & 1 \\ + 1 & 1 & 1 & 0 \\ \bottomrule +\end{tabular} + +Her tilføjer man tit en \emph{edge triggering} så den kun gemmer når $C$ går fra høj til lav, eller omvendt. +Dette giver en \textbf{D Flip-Flop} og er implementeret med to D latches. + +\paragraph{JK Flip-Flop} fungere som en SR latch men trigger på clock rise eller fall. +Den har heller ikke problemet med at have en mærkelig state da output bliver flipped når $J=1$ og $K=1$. + +\section{Characteristic Equation} + +Her beskriver man sin Sequential kreds med en formel. +Man kan beskrive en D Flip-Flop med: +\begin{equation*} + \begin{split} + Q = D \\ + Q_{n+1} = D_n + \end{split} +\end{equation*} + +Eller en JK Flip-Flop med: +\[ + Q_{n+1} = J \cdot \neg Q_n + \neg K \cdot Q_n +\] + +\section{State Automaton} + +Her har man en enhed hvor output, $O_n$, kan beskrives som følgende. +\begin{equation*} + \begin{split} + Q_{n+1} = F(Q_n, I_n) \\ + O_{n} = G(Q_n, I_n) + \end{split} +\end{equation*} + +Her har man altså noget kombinatorisk logic før og efter en block memory, hvilket man kan bruge til at implementere ret avancerede ting. +Her er det vigtigt at man tager højde for timing mellem disse blokke. + +Man kan implementere memory med \texttt{process} functionen i VHDL. diff --git a/sem6/dig/mm1/opgaver.md b/sem6/dig/mm1/opgaver.md index 509c1c5..9f80ad4 100644 --- a/sem6/dig/mm1/opgaver.md +++ b/sem6/dig/mm1/opgaver.md @@ -1,3 +1,5 @@ + + # Opgave 1 Nope diff --git a/sem6/dig/mm1/opgaver.tex b/sem6/dig/mm1/opgaver.tex new file mode 100644 index 0000000..4b8dc91 --- /dev/null +++ b/sem6/dig/mm1/opgaver.tex @@ -0,0 +1,169 @@ +\title{Opgaver til Lektion 1} + +\let\inv\overline + +\section{Opgave 1} + +Perfect induction af $(A + B) \cdot (A + C) = A + (B \cdot C)$: + +\begin{tabular}{lll|ll} \toprule + $A$ & $B$ & $C$ & $(A + B) \cdot (A + C)$ & $A + (B \cdot C)$ \\ \midrule + 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 1 & 0 & 0 \\ + 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 & 1 \\ + 1 & 0 & 0 & 1 & 1 \\ + 1 & 0 & 1 & 1 & 1 \\ + 1 & 1 & 0 & 1 & 1 \\ + 1 & 1 & 1 & 1 & 1 \\ \bottomrule +\end{tabular} + +Perfect induction af $A \cdot (A + B) = A$: + +\begin{tabular}{ll|ll} \toprule + $A$ & $B$ & $A + B$ & $A$ \\ \midrule + 0 & 0 & 0 & 0 \\ + 0 & 1 & 0 & 0 \\ + 1 & 0 & 1 & 1 \\ + 1 & 1 & 1 & 1 \\ \bottomrule +\end{tabular} + +Perfect induction of $A + \inv{A} = 1$: + +\begin{tabular}{l|ll} \toprule + $A$ & $A + \inv{A} $ & $1$ \\ \midrule + 0 & 1 & 1 \\ + 1 & 1 & 1 \\ \bottomrule +\end{tabular} + +Perfect induction of $\inv{A + B + C} = \inv{A} \cdot \inv{B} \cdot \inv{C}$: + +\begin{tabular}{lll|ll} \toprule + $A$ & $B$ & $C$ & $\inv{A + B + C}$ & $\inv{A} \cdot \inv{B} \cdot \inv{C}$ \\ \midrule + 0 & 0 & 0 & 1 & 1 \\ + 0 & 0 & 1 & 0 & 0 \\ + 0 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 0 & 0 \\ + 1 & 0 & 0 & 0 & 0 \\ + 1 & 0 & 1 & 0 & 0 \\ + 1 & 1 & 0 & 0 & 0 \\ + 1 & 1 & 1 & 0 & 0 \\ \bottomrule +\end{tabular} + +\section{Opgave 2} + +\begin{opg} + Show that the following + + \begin{equation*} + R = \inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}} + \end{equation*} + + is XOR. +\end{opg} + +Man kan skrive XOR operator som: +\begin{equation*} + A \oplus B = (A + B) \cdot \inv{(A \cdot B)} +\end{equation*} + +\begin{tabular}{ll|ll} \toprule + $A$ & $B$ & $A \oplus B$ & $(A + B) \cdot \inv{(A \cdot B)}$ \\ \midrule + 0 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 \\ + 1 & 0 & 1 & 1 \\ + 1 & 1 & 0 & 0 \\ \bottomrule +\end{tabular} + +Kan herefter vise at dette er $\inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}}$. +\begin{equation*} + \inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}} = (A + B) \cdot \inv{(A \cdot B)}\\ +\end{equation*} +Vi kan starte med at bruge DeMorgans lov. +\begin{equation*} + = (A + B) \cdot (\inv{A} + \inv{B}) \\ +\end{equation*} +Man kan skrive det ud. +\begin{equation*} + = A \cdot \inv{A} + A \cdot \inv{B} + B \cdot \inv{A} + B \cdot \inv{B} +\end{equation*} +Vi kan bruge axiomen $X \cdot \inv{X} = 0$. +\begin{equation*} + = A \cdot \inv{B} + B \cdot \inv{A} +\end{equation*} +Og nu kan vi bruge DeMorgans lov på venstre side. +\begin{equation*} + \inv{ \inv{A \cdot \inv{B}}} + \inv{ \inv{\inv{A} \cdot B}} = A \cdot \inv{B} + B \cdot \inv{A} +\end{equation*} +Og dette passer hvis man lader inverserne gå ud med hinnanden. + +\section{Opgave 3} + +\begin{opg} + Reduce the following expressions: + \begin{align*} + A \cdot \inv{B} \cdot \inv{C} + A \cdot B \cdot \inv{C} + \inv{A} \cdot \inv{C} \\ + M \cdot \inv N \cdot P + \inv L \cdot M \cdot P + \inv L \cdot M \cdot \inv N + \inv L \cdot M \cdot N \cdot \inv P + \inv L \cdot \inv N \cdot \inv P + \end{align*} +\end{opg} + +Vi starter med den første opgave. +Her tager vi og bruger den distributive teorem et par gange. +\begin{equation*} + \begin{split} + \inv{C} \cdot (A \cdot \inv B + A \cdot B + \inv A) \\ + \inv{C} \cdot (A \cdot (\inv B + B) + \inv A) + \end{split} +\end{equation*} +Nu kan vi bruge axiomen \(X + \inv X = 1\) og \(X \cdot 1 = X\). +\[ + \inv C \cdot (A + \inv A) = \inv C +\] + +Lad og tage den anden. +Vi starter med at bruge den distributive teorem et par gange. +\begin{equation*} + \begin{split} + M \cdot (\inv N \cdot P + \inv L \cdot P + \inv L \cdot \inv N + \inv L \cdot N \cdot \inv P) + \inv L \cdot \inv N \cdot \inv P \\ + M \cdot (\inv N \cdot P + \inv L \cdot (P + \inv N + N \cdot \inv P)) + \inv L \cdot \inv N \cdot \inv P + \end{split} +\end{equation*} +Den inerste parantes er på formen $A + B + \inv A \cdot \inv B$. +Dette kan vise altid er lig med $1$, ved at starte med DeMorgans lov. +\[ + A + B + \inv{A + B} +\] +Ud fra axiomen $X + \inv X = 1$ kan vi se at dette altid er 1. +Nu kan vi sætte dette ind og bruge den distributive lov igen omvendt. +\[ + M \cdot (\inv N \cdot P + \inv L) + \inv L \cdot \inv N \cdot \inv P = M \cdot \inv N \cdot P + M \cdot \inv L + \inv L \cdot \inv N \cdot \inv P +\] +Mere kan jeg desværre ikke reducere den. + +\section{Opgave 4} + +\begin{opg} + Find expression +\end{opg} + +\begin{verbatim} +X = ~(A * B) +Y = ~(A * X) +Z = ~(B * X) +C = ~(Y * Z) +D = ~X + +C = ~(~(A * ~(A * B)) * ~(B * ~(A * B))) +D = ~~(A * B) = A * B +\end{verbatim} + + +\section{Gate Input Cost} + +Skriver lige hurtigt formlen op for GIC. +\begin{verbatim} + GIC = LC + number of terms in boolean expr + number of unique inversions +\end{verbatim} +Her er LC litteral cost, hvilket er antallet af ikke unikke variabler. + +GIC kan også findes ved at tælle antal inputs i et logic diagram. diff --git a/sem6/dig/shell.nix b/sem6/dig/shell.nix new file mode 100644 index 0000000..28b6ba9 --- /dev/null +++ b/sem6/dig/shell.nix @@ -0,0 +1,7 @@ +{ pkgs ? import {}}: + +pkgs.mkShell { + buildInputs = with pkgs; [ + ghdl-llvm zlib + ]; +} -- cgit v1.2.3