diff options
Diffstat (limited to 'sem6')
-rw-r--r-- | sem6/com/m3/channel_test.py | 90 | ||||
-rw-r--r-- | sem6/dig/m2/Makefile | 2 | ||||
-rw-r--r-- | sem6/dig/m2/ex1.vhdl | 23 | ||||
-rw-r--r-- | sem6/dig/m2/ex3.vhdl | 15 | ||||
-rw-r--r-- | sem6/dig/m2/noter.tex | 35 | ||||
-rw-r--r-- | sem6/dig/m4/Makefile | 2 | ||||
-rw-r--r-- | sem6/dig/m4/ex2.vhdl | 11 | ||||
-rw-r--r-- | sem6/dig/m4/ex3.vhdl | 2 | ||||
-rw-r--r-- | sem6/dig/m4/ex4.vhdl | 32 | ||||
-rw-r--r-- | sem6/dig/m4/noter.tex | 75 | ||||
-rw-r--r-- | sem6/dig/mm1/opgaver.md | 2 | ||||
-rw-r--r-- | sem6/dig/mm1/opgaver.tex | 169 | ||||
-rw-r--r-- | sem6/dig/shell.nix | 7 | ||||
-rw-r--r-- | sem6/prob/eksamnen/notes.tex | 47 |
14 files changed, 417 insertions, 95 deletions
diff --git a/sem6/com/m3/channel_test.py b/sem6/com/m3/channel_test.py deleted file mode 100644 index c8f9e85..0000000 --- a/sem6/com/m3/channel_test.py +++ /dev/null @@ -1,90 +0,0 @@ -import numpy as np - -class MatrixEncoder: - def ident(dim, value=1): - return np.identity(dim) * value - -class Vector: - def __init__(self, arr): - self.arr = arr - self.len = len(arr) - - def add(self, other): - return self.__class__(self.arr + other.arr) - - def __str__(self): - return str(self.arr) - - def print(self, f="{}"): - print(f.format(self)) - return self - - def gaussian(size, mu, sigma): - return Vector(sigma * np.random.randn(size) + mu) - - -class BitVector(Vector): - def gen_uniform(size): - arr = np.random.randint(0, 2, size) - return BitVector(arr) - - def to_int(self): - reverse = np.flip(self.arr) - - res = 0 - for (i, b) in enumerate(reverse): - res += b * 2**i - return res - - def encode(self, matrix): - return SymbolVector(matrix[self.to_int()]) - - def from_int(index, size=None): - bits = [] - while index > 0: - remainder = index % 2 - index = index // 2 - bits.insert(0, remainder) - - # Padding if they want - if size is not None: - missing = max(0, size - len(bits)) - bits = [0] * missing + bits - - return BitVector(bits) - - def check_if_error(self, other): - return np.array_equal(self.arr, other.arr) - -class SymbolVector(Vector): - def with_noise(self, c): - noise = Vector.gaussian(self.len, 0, c) - return self.add(noise) - - def decide_and_decode(self, matrix): - dim = len(matrix) - # Collect all distances in vector - dists = np.arange(dim) - for (i, vec) in enumerate(matrix): - dists[i] = np.dot(self.arr, vec) - - # Find index with smallest - index = np.argmax(dists) - - # Convert integer back to bit vector - return BitVector.from_int(index, size=int(np.log2(dim))) - -encoder = MatrixEncoder.ident(4, np.sqrt(1)) - -faults = 0 -total = 10000 -for i in range(total): - original = BitVector.gen_uniform(2) - after = original.encode(encoder) \ - .with_noise(1) \ - .decide_and_decode(encoder) - if original.check_if_error(after): - faults += 1 - -print(f"Fault percentage {(faults / total) * 100}%") - 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 <nixpkgs> {}}: + +pkgs.mkShell { + buildInputs = with pkgs; [ + ghdl-llvm zlib + ]; +} diff --git a/sem6/prob/eksamnen/notes.tex b/sem6/prob/eksamnen/notes.tex new file mode 100644 index 0000000..4dfee30 --- /dev/null +++ b/sem6/prob/eksamnen/notes.tex @@ -0,0 +1,47 @@ +\title{Eksamnens Noter} + + +The universal set or sample space is the set everything, and is denoted $S$. +Therefore the probability of hitting $S$ is $P(S) = 1$. + +This is the first of 3 axioms repeated below. + +\begin{enumerate} + \item For any event $A$, $P(A) \geq 0$. + \item The probability of hitting sample space is always 1, $P(S) = 1$. + \item If events $A_1, A_2, ...$ are \textbf{disjoint} event, then + \begin{equation} + P(A_1 \cup A_2 ...) = P(A_1) + P(A_2)\,. + \end{equation} +\end{enumerate} + +The last axiom requires that the events $A_n$ are disjoint. +If they aren't one should subtract the part they have in common. +This is called the \emph{Inclusion-Exclusion Principle}. + +\begin{principle} + The \emph{Inclusion-Exclusion Principle} is defined as + \begin{equation} + P(A \cup B) = P(A) + P(B) - P(A \cap B)\,. + \end{equation} + Definition with 3 events can be found in the in the book. +\end{principle} + +\section{Counting} + +The probability of a event $A$ can be found by +\begin{equation} + P(A) = \frac {|A|} {|S|}\,. +\end{equation} +It is therefore required to count how many elements are in $S$ and $A$. +The most simple method is the \emph{multiplication principle}. + +\begin{principle}[Multiplication principle] + Let there be $r$ random experiments, where the $k$'th experiment has $n_k$ outcomes. + Then there are + \begin{equation} + n_1 \cdot n_2 \cdot ... \cdot n_r + \end{equation} + possible outcomes over all $r$ experiments. +\end{principle} + |