% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}


\begin{document}

\title{Logarithmische Zahlensysteme}
\author{Rafael Deliano}
\maketitle
\label{LNS}

Multiplikation und Division sind bei Festkommazahlen aufwändig. Vom Rechenschieber ist bekannt, dass bei logarithmischer Zahlendarstellung diese Funktionen einfach sind, sie reduzieren sich auf Addition und Subtraktion.

\begin{multicols}{2}

	Für Potenzen und Wurzeln sind nur noch Multiplikation und Division nötig, für Quadrat und Quadratwurzel genügen Shiftbefehle (Bild 1). Andererseits sind Addition und Subtraktion logarithmierter Zahlen schwierig.
	
\begin{center}
\includegraphics[width=0.4\columnwidth]{2008-01/LNS-Bild1}\\
\label{LNS:Bild1}Bild 1: Operationen
\end{center}
	
Die primitive Lösung für z.B. Multiplikation war somit über eine log--Tabelle das Zahlensystem zu wechseln, die Addition auszuführen und dann über eine invlog--Tabelle zurück auf Festkomma zu wandeln (Bild 2). Mit ersten Verfeinerungen wurde das bereits in den 60er Jahren propagiert [1].
	
\begin{center}
\includegraphics[width=0.4\columnwidth]{2008-01/LNS-Bild2}\\
\label{LNS:Bild2}Bild 2: Multiplikation
\end{center}
	
	Verwendet wird heute durchwegs der binäre Logarithmus (Bild 3). Man ist, wie man am Funktionsverlauf sieht, auf positive Zahlen beschränkt.
\begin{center}
\includegraphics[width=0.9\columnwidth]{2008-01/LNS-Bild3}\\
\label{LNS:Bild3}Bild 3: $y=ld(x)$
\end{center}
Für bipolare Signale wird also ein zusätzliches Vorzeichenbit nötig. Zudem muss das Signal größer 1,0 sein. Dagegen hilft Umformulierung der Gleichungen, um günstige Koeffizienten zu erhalten (Bild 4).

\begin{center}
\includegraphics[width=0.3\columnwidth]{2008-01/LNS-Bild4}\\
\label{LNS:Bild4}Bild 4: Umwandlung für günstige Koeffizienten
\end{center}
		
\begin{center}
\includegraphics[width=0.5\columnwidth]{2008-01/LNS-Bild5}\\
\label{LNS:Bild5}Bild 5: Exponentialfunktion
\end{center}
			 
Besonders bei Exponentialfunktionen  ergeben sich oft überraschend einfache Lösungen (Bild 5). Durch die weite Dynamik ist auch das Überlaufverhalten günstig. Jedoch sind in den meisten Gleichungen Additionen nötig (Bild 6), was Formatwandlung bedeutet. Abgesehen von der Rechenzeit besonders wegen der Quantisierungsfehler kritisch. Dem kann man natürlich durch erhöhte Auflösung begegnen. Aber wenn die Umwandlung durch Tabellen erfolgen soll, stößt man schnell an praktische Grenzen.


\begin{center}
\includegraphics[width=0.9\columnwidth]{2008-01/LNS-Bild6}\\
\label{LNS:Bild6}Bild 6: gemischte Rechnung
\end{center}



\section{Signalverarbeitung}

	Der Speicherbedarf der ROMs war und ist einer der Pferdefüße, die den praktischen Einsatz von LNS 
(„Logarithmic Number Systems“) bisher aufgehalten haben. Obwohl heute manchmal als Ersatz für Float propagiert, wurde das Format ursprünglich speziell für Signalverarbeitung als geeignet angesehen [2]. Denn A/D-- und D/A--Wandler waren auf  
8--12 Bit beschränkt und damit blieb der Speicherbedarf der Tabellen erträglich. Anders als Festkommazahlen, die konstante Schrittweite haben, werden  nichtlinear kleine Werte mit größerer Auflösung dargestellt. Damit erhält man bei DC--freien Signalen über einen weiten Dynamikbereich einen günstigen Signal/Rausch--Abstand, selbst wenn man nur mit kurzen Wortlängen arbeitet. Im Telefonsystem macht man bei PCM--Codecs seit langem von dieser Eigenschaft gebrauch (Bild 7). 


\begin{center}
\includegraphics[width=0.5\columnwidth]{2008-01/LNS-Bild7}\\
\label{LNS:Bild7}Bild 7: Telefonie
\end{center}
Ein PID--Regler kann als Filter angesehen werden. Abhängig von der Implementierungsform wird der Filterkern im eingeregelten Zustand zumindest am Eingang 
\end{multicols}
\pagebreak
\vspace*{-1.3cm}
\begin{multicols}{2}
fast DC--frei sein, das Fehlersignal $e$ ist auf null ausgeglichen. LNS kann damit zweckmäßig sein (Bild 8). 

\begin{center}
\includegraphics[width=0.5\columnwidth]{2008-01/LNS-Bild8}\\
\label{LNS:Bild8}Bild 8: Regler
\end{center}
		
	Außer weiter Dynamik kann
vereinfachte Arithmetik durch
 günstige Stromaufnahme von Vorteil sein.  Mit Ausrichtung auf Anwendung in Hörgerät wurde in [50] ein experimenteller Filterbankprozessor vorgestellt, der durch logarithmische A/D-- und D/A--Wandler ergänzt werden sollte [51], so dass die Tabellen für die Formatwandlung prinzipiell entfallen. 
	Manche Sensorsignale wie Licht oder Lautstärke benötigen viele Dekaden Dynamik und damit einen 14--16--Bit--A/D--Wandler. Wenn man solche Signale aber mit einem analogen Logarithmierer behandelt, genügt in manchen Anwendungen ein 
	8--Bit--Wandler (Bild 9).  Die Kennlinie der Analogschaltung ersetzt hier auch die digitale Tabelle, allerdings muss das LNS--System auf sie abgestimmt werden.
\medskip

\begin{center}
\includegraphics[width=0.5\columnwidth]{2008-01/LNS-Bild9}\\
\label{LNS:Bild9}Bild 9: Analoge \glqq Tabellen\grqq
\end{center}
\vspace{-1mm}

\section{Additionstabellen}

	Die Umwandlung mit Tabellen führt zu Rundungsfehlern. Man kann verhindern, dass sich diese akkumulieren, indem man nur für Ein-- und Ausgabe auf Festkomma wandelt. Und ansonsten im LNS--Format rechnet. Damit benötigt man aber je eine weitere Tabelle für Addition und Subtraktion. Die Vorteile überwiegen jedoch, im Verlauf der 70er Jahre hat sich das bald als die bevorzugte Variante eingebürgert.
	
	Einen nicht zu unterschätzenden Beitrag zur Popularisierung hat dabei die Publizierung des FOCUS--Zahlensystems [4] von Lee und Edgar 1977 bzw. 1979
geleistet, da dieses die konkrete Implementierung auf einem \columnbreak 8080--Mikroprozessor beschrieb und dafür auch die Listings veröffentlicht wurden.
	
	Obwohl die praktischen Anwendungen bisher spärlich geblieben sind, hat die Zeit seither für LNS gearbeitet. Einerseits weil immer mehr Speicher billig verfügbar wurde. Andererseits hat eine Handvoll Wissenschaftler dafür gesorgt, dass über Interpolation und Eliminierung vorhandener Redundanzen die Tabellen verkleinert wurden, ohne dass Zugriffszeit und Genauigkeit zu sehr litten.
	
	In den 90er Jahren wurde versucht, LNS in Form von Softwaresystemen kommerziell und patentiert auf den Markt zu bringen. Marktführer dürfte die 1993 von Les Pickett gegründete Firma gewesen sein [10]--[12]. Anwendung z.B. die Luftdrucksteuerung im Passagierraum der Boeing 767 und ähnlicher Flugzeuge seit 1977. Wobei der Hersteller das System nicht als LNS, sondern als EFP („Exponential Floating Point“) bezeichnete. Etwa anno 2000 ist die Firma über Turbulenzen an der Börse gestolpert.
	
	Nicht viel besser ging es dem Unternehmen von Mark Winkel [20], der basierend auf von Mark Arnold entwickelter Technik [21] das gleiche Geschäftsmodell verfolgte, aber auch noch Picketts Patent umgehen musste. Diese Gruppe scheint aber mit Zielrichtung auf FPGA--Cores und ICs weiterhin aktiv zu sein.
	
	Auch große Halbleiterhersteller wie Motorola und VLSI Technology waren aktiv und haben zumindest Patente angemeldet. Motorola stellte 1999 einen experimentellen 32--Bit--Coprozessor vor [30] [31], der 64  Arithmetikeinheiten enthält und damit 10 (US) Billionen Flops pro Sekunde erreicht. Anwendung war Video.
	
	Der Esprit--finanzierte „European Logarithmic Microprocessor“ hat es bisher zu Patent, einer FPGA--Implementierung [40] und einem teilweisen ASIC--Prototypen [41] gebracht. Die Ziele sind mit 32 Bit Wortbreite und damit Annäherung an IEEE--Float hoch gesteckt [42]. Finanziell unterstützt von der englischen Regierung entstand dann unter Coleman 2005 die Firma Northern Digital als spin--off der Newcastle University. Samples in 0,18--micron CMOS mit 125 MHz Takt sind wohl verfügbar. Da die Firma aber auf Vermarktung von IP ausgelegt ist, kann man das IC einstweilen noch nicht kaufen. Angepeilte Anwendung auch hier Video. 
\end{multicols}
\vspace*{-2mm}
% \section{Literatur}
\newlength{\refskip}\setlength{\refskip}{-0.3mm}
\begin{small}
{[1]} Mitchell „Computer Multiplication and Division using Binary Logarithms“ 
IEEE Trans. Comput. August 1962\\[\refskip]
{[2]} Kingsbury, Rayner „Digital filtering using logarithmic arithmetic“ Electronic Letters vol. 7 1971\\[\refskip]
{[4]} Lee, Edgar „The FOCUS number system“ IEEE Trans. Comp. Nov 1977\\[\refskip]
{[10]} \url{www.logpoint.com}\\[\refskip]
{[11]} L. Pickett „Method and Apparatus for Exponential/Logarithmic Computation“
U.S. Patent 5.197.024.23 March 1993\\[\refskip]
{[12]} „Software Math Coprozessor Rivals Hardware Speeds“ Electronic Design August 1997\\[\refskip]
{[20]} \url{www.xlnresearch.com}\\[\refskip]
{[21]} Arnold „Method and Apparatus for Fast Logarithmic Addition and Subtraction“ U.S. Patent 5.337.266.9 August 1994\\[\refskip]
{[22]} „Fast Math: Software Faster Then a Coprozessor“ C User's Journal Juli 1991\\[\refskip]
{[30]} Pan „A 32b 64--matrix parallel CMOS processor“ 1999 IEEE Intl. 	       Solid--State Circuits Conf.\\[\refskip]
{[31]} „10bn Flops using logs“ Electronics Weekly Feb. 1999\\[\refskip]
{[40]} Kadlec et Al. „32--bit Logarithmic ALU for Handel C2.1 and Celoxica DK1“\\[\refskip]
{[41]} Chester, Coleman „Development of a High--Speed 32b Real Arithmetic Core for DSP and Graphics Applications using Logarithmic Number System Techniques“\\[\refskip]
{[42]} Coleman, Chester „A 32--Bit Logarithmic Arithmetic Unit and Its Performance Compared to Floating Point“\\[\refskip]
{[50]} Morley, Sullivan, Engel „A VLSI FIR Digital Signal Prozessor Using Logarithmic Arithmetic“ in: Broderson „VLSI Signal Processing III“ IEEE 1988\\[\refskip]
{[51]} Engel, Morley, Kwa, Fretz „Integrated Circuit Logartihmic Digital Quantizers with Applications to low--power data interfaces for speech processing“ in: Moscovitz „VLSI Signal Processing IV“ IEEE 1991
\end{small}
\end{document}
