\begin{document}

\title{CSD–Zahlendarstellung}
\author{Rafael Deliano}
\maketitle

\begin{multicols}{2}

\begin{abstract}
Die Multiplikation von festen Koeffizienten, wie sie besonders bei
digitalen Filtern benötigt wird, kann im 2er--Komplementformat durch
Shift\&Add erfolgen. Dabei sind offensichtlich Koeffizienten günstig,
bei denen nur eine geringe Zahl von Bits gesetzt ist.  Ein
Zahlenformat, das die Zahl der gesetzten Bits minimiert, indem es
zusätzlich zu Addition auch Subtraktion verwendet, wird also die
Multiplikation beschleunigen.
\end{abstract}

\section{Das allgemeine SD--Format}

("`Signed Digit"') ist ternär und hat als Grundelemente $-1,0,+1$.  In
der Literatur wird für die negative Eins eine Überstreichung bevorzugt
(Abbildung \ref{bild1}). Da das aber viele DTP--Systeme nicht vertragen, ist
ein Kompromiss die Unterstreichung. ASCII--fähig, aber in Zusammenhang
mit negativem Vorzeichen problematisch, ist das Verwenden nur der
Vorzeichen. Hier wird die Variante mit "`T"' bevorzugt.

\begin{figure}
\begin{center}\includegraphics{2007-01/csd-bild1}\caption{\label{bild1} Schreibweisen}
\end{center}
\end{figure}

Es sind im SD--Format unterschiedliche Varianten in der
Zahlendarstellung möglich. Der Spezialfall CSD ("`Canonical Signed
Digit"') \cite{reitwiesner} hat die Eigenschaften: eine minimale
Anzahl von 1 bzw. $-1$ und es sind immer Nullen zwischen diesen Ziffern
(Abbildung \ref{bild2}).

\begin{figure}
\begin{center}\includegraphics[width=\columnwidth]{2007-01/csd-bild2}\caption{\label{bild2} Zahlendarstellung}
\end{center}
\end{figure}

Interesse für derartige Rechenwerke war schon zu Zeiten der
Röhrencomputer vorhanden. Damals wurden ternäre Codes noch als
mögliche Alternative zur heute durchwegs üblichen binären Logik
angesehen. Bald aber aus Mainframes verdrängt. In den 70ern für
Signalverarbeitung wiederentdeckt \cite{peled} und dann auch 1979 im
allerersten DSP, dem Intel 2920 verwendet. Danach speziell in
bitseriellen VLSI--Schaltungen, heute zusätzlich vereinzelt auch in
FPGAs eingesetzt.

\section{Controller}

Für variable Koeffizienten im SD--format gäbe es zwar "`Booth's
modified algorithm"', eine Variante des gängigen Booth--Multiplizierers
\cite{emb}, aber besonders auf Controllern ist nur die Multiplikation
fester Koeffizienten im CSD--Format von Interesse. In VLSI--Schaltungen
werden die Shifts durch geeignete Verdrahtung ausgeführt, nur die
Additionen bzw. Subtraktion benötigen Schaltungen. Auf Controllern
sind die Shifts explizit nötig (Abbildung \ref{bild3}). Man kann aus einer
Shiftkette mehrere Multiplikationen ableiten (Abbildung \ref{bild4}). Die
transponierte Form von kaskadierten Biquads (Abbildung \ref{bild5}) oder
FIRs (Abbildung \ref{bild6}) sind hier günstig.

\begin{figure}
\begin{center}\includegraphics[scale=0.75]{2007-01/csd-bild3}\caption{\label{bild3} Implementierung auf Controller}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\includegraphics[scale=0.75]{2007-01/csd-bild4}\caption{\label{bild4} Mehrere Multiplikationen aus einer Shiftkette}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\includegraphics[scale=0.8]{2007-01/csd-bild5}\caption{\label{bild5} Kaskadierte transportierte Biquads}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\includegraphics[scale=0.8]{2007-01/csd-bild6}\caption{\label{bild6} Transponiertes FIR--Filter}
\end{center}
\end{figure}

\section{Programm}

Der ursprüngliche Reitwiesner--Algorithmus (Abbildung \ref{bild7}) wandelt
eine vorzeichenlose 2er--Komplementzahl $x$ seriell auf CSD--Format $y$
um. Ein Carrybit $c$ wird als Zwischenspeicher verwendet. Die Benutzung
der Tabelle ist anhand eines Rechenbeispiels (Abbildung \ref{bild8}) leicht
nachvollziehbar. Das entsprechende Programm (Listing 1) ist trivial,
druckt dann aber als Schönheitsfehler LSB links aus.

\begin{figure}
\begin{center}\includegraphics{2007-01/csd-bild7}\caption{\label{bild7} Tabelle für Umwandlung}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\includegraphics{2007-01/csd-bild8}\caption{\label{bild8} Beispiel für Verwendung von Tabelle}
\end{center}
\end{figure}

\begin{thebibliography}{9}
\bibitem{emb} emb (2)
\bibitem{reitwiesner} Reitwiesner "`Binary Arithmetic"' 	      in: Advances on Computers Vol 1.
      Academic Press 1960
\bibitem{peled} Peled "`An architecture for digital 	      signal processors"' IEEE
      Electronics and Aerospace 
      Systems Convention IEEE 		      EASCON 1975
\end{thebibliography}

\listinginput[1]{1}{2007-01/csd.fs}

\end{multicols}

\end{document}