heron_sqrt/bericht/bericht.tex

%*******************************************************************************
% * Copyright (c) 2006-2013
% * Institute of Automation, Dresden University of Technology
% *
% * All rights reserved. This program and the accompanying materials
% * are made available under the terms of the Eclipse Public License v1.0
% * which accompanies this distribution, and is available at
% * http://www.eclipse.org/legal/epl-v10.html
% *
% * Contributors:
% *   Institute of Automation - TU Dresden, Germany
% *      - initial API and implementation
% ******************************************************************************/

\documentclass[
  print,          % print optimized version of the thesis, standard option
                  % alternative:
%  screen,        % makes the thesis better readable on screens (onesided, coloured links)
                  % use only 'print' OR 'screen'
                  % ATTENTION: 'screen' changes size of text area slightly. Always optimize document WITH
                  % 'print' option first for printing (size of graphics etc.) and convert afterwards
                  % in screen optimized version!
  listoffigures,  % includes list of figures
  listoftables,   % includes list of tables
  listoflistings, % includes list of listings
  abbrevations,   % includes index of symbols and abbrevations
  bibNumeric,     % citation style (IfA standard), alternatives: bibNumeric, bibHarvard
  langDE          % define the language (default: langDE)
]{ifathesis}
\ifaThesis{Belegarbeit}
\ifaAuthor{Jörg Thalheim}
\ifaAuthorBirthday{03.01.1992}
\ifaAuthorBirthplace{Großröhrsdorf}
\ifaAuthorCourse{Informationssystemtechnik}
\ifaAuthorYearOfMatriculation{2011}
\ifaKeywords{Praktikum, Schaltungsentwurf, Verilog} % Keywords included in pdf-file. Could be found e.g. by Windows file search.
\ifaTitleDE{Schaltkreis- und Systementwurf}
\ifaTitleEN{}
\bibliography{bibliography}

\ifaSupervisorA{Jens-Uwe Schlüßler}
\ifaProfessor{Prof. Dr.-Ing. habil. René Schüffny}
\ifaDayOfSubmission{\today}
\ifaTopicDescriptionPDF{parts/00_Aufgabenstellung.pdf}
\ifaAppendix{example_files/appendix}
\ifaAbstractDE{example_files/00_abstract_de__invalid}
\ifaAbstractEN{example_files/00_abstract_en__invalid}
\usepackage{tabularx}
\usepackage{graphicx}

% Keine Kapitelnummerierung
\makeatletter
\renewcommand{\thesection}{
  \ifnum\c@chapter<1 \@arabic\c@section
  \else \thechapter.\@arabic\c@section
  \fi
}
\makeatother

\begin{document}

\section{Einleitung}
Aufgabe des Praktikums \emph{Schaltkreis- und Systementwurf} ist es einen integrierten Schaltkreis (ASIC) für
einen numerischen Algorithmus zu entwickeln. Der Schaltkreis ist mit der
Enwicklungsumgebung \emph{Cadence} zu erstellen. Dabei ist den Arbeitsschritten der Aufgabenstellung
\cite{aufgabenstellung} zu folgen. Die Schaltung ist durch Simulation zu verifizieren.
Der folgende Bericht enthält die geforderte Dokumentation nach Kapitel 5.1
\cite{dokumentation} der Aufgabenstellung.

\section{Beschreibung des Algorithmus}
Der hier selbst gewählte Algorithmus ist Ziehen der Quadratwurzel mithilfe des
Heron’sche Näherungsverfahren (auch Babylonverfahren genannt). Es ist benannt
nach dem Altgriechen Heron von Alexandria, der es zum 1. Mal beschrieb. Es ist
vermutlich das älteste Nährungsverfahren für die Quadratwurzel. Wegen seines
einfachen Aufbaus, war es ein beliebter Algorithmus für die Implementierung in
Software bevor Hardwareimplementierung sich verbreitet haben.

Die Iterationsvorschrift des Verfahren lautet:

\begin{align}
  x_{n+1} & =\frac{x_n + \frac{a}{x_n}}{2} \\
  lim_{n \rightarrow \infty} x_n & = \sqrt{a}
\end{align}

wobei $a$ der Ausgangswert ist, aus welchem die Wurzel berechnet werden soll und
$x_n$ der sich von Iterations zu Iterations an die Quadratwurzel annähernde
Wert.

Herleiten lässt sich die Folge aus dem Newton-Verfahren zur Bestimmung der
Nullstellen ($x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$):

\begin{align}
  x^2         &= a \\
  f(x)        &= x^2 - a \\
  f'(x)       &= 2x \\
  x_{n + 1}   &= x_n - \frac{f(x_n)}{f'(x_n)} \\
              &= x_n - \frac{x_n^2 - a}{2x_n} \\
              &= x_n - \frac{x_n - a/x_n}{2} \\
              &= \frac{x_n + a/x_n}{2}
\end{align}

Wobei in diesem Praktikum die Quadratwurzel von mehreren hintereinander im
Speicher abgelegten Zahlen berechnet wird.

\section{Implementierung in C}
Der Prototyp des Algorithmus erfolgte in der Programmiersprache C nach dem
C99-Standard.

\ifalisting{Implementierung in C}{lst:implementierung}{c}{code/sqrt.c}{true}

Wie auch in der zu realisierenden Schaltung erwartet die Funktion im
Speicherfeld die Operanden für die Quadratwurzel-Berechnung. Wobei das 1. Feld
die Anzahl der Operanden angibt (siehe Speicherbelegung \ref{tbl:speicherbelegung}).

\subsection{Speicherbelegung und Zahlenformat}

Es wird angenommen, das jeder Speicherplatz 32 Bit breit ist.
Jedes Datenfeld wird als vorzeichenlose Festkommazahl interpretiert.
Die Anzahl der Nachkommastellen lässt sich sowohl in der Schaltung
(heron\_comma\_fix) als auch in
der C-Implementierung (siehe Zeile \ref{comma}) leicht anpassen, wobei
vorrausgesetzt wird, dass die Anzahl durch 2 teilbar sein muss. Für die
Verifikation wurden 8. Kommastellen festgesetzt.

\begin{table}
\begin{tabularx}{\textwidth}{X|X}
  Speicherplatz & Beschreibung \\\hline
  MEM[0]        & Anzahl der Operanden (N) \\
  MEM[1]        & 1. Operand \\
  MEM[2]        & 2. Operand \\
  $\ldots$      & $\dots$ \\
  MEM[N]        & N. Operand
\end{tabularx}
\caption{Speicherbelegung}
\label{tbl:speicherbelegung}
\end{table}

\subsection{Datenflussgraph}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.6\textwidth]{graph.pdf}
  \label{fig1}
\end{figure}

\subsection{Datenpfad}

\end{document}

% vim:spelllang=de