PoStInG - Praxisorientiertes Studium Informatik und Gesellschaft

Sommersemester 2001: Technologie & Transparenz / Geistiges Eigentum

  Beispiel eines Softwarepatents: Der LZW-Algorithmus 

Der LZW-Algorithmus ist ein relativ einfaches Kompressionsverfahren. Es ist außerdem relativ schnell, da linear über die Eingabe gegangen wird. Zur Funktionsweise siehe [1]. Er entstand aus der Weiterentwicklung des LZ-Algorithmus durch Terry Welch, und ist nach seinen Erfindern Lempel, Ziv und Welch benannt. Dieses Kompressionsverfahren wird unter anderem im populären GIF-Bildformat benutzt, das neben JPG das Standardformat für Bilder im Internet ist. Auch TIFF-LZW, ein weiteres Bildformat und PDF-LZW benutzen diesen Algorithmus. Ebenso das UNIX-Tool compress, ein Packprogramm für Dateien und die Druckersprache PostScript-2.

LZW wurde 1983 in den USA von der Sperry Corporation unter der Patentnummer 4558302 [3] patentiert. 1984 folgte ein europäisches Patent (Patentnummer 304111) [2], welches in England, Frankreich, Italien und auch in Deutschland gilt. Die entsprechende deutsche Patentnummer ist 3476617. Weitere Patente existieren Kanada und Japan. 1986 übernahm Unisys Sperry und damit auch die Patentrechte an LZW.
1989 wurde ein dem LZW-Algorithmus entsprechender Algorithmus von IBM patentiert (US-Patentnummer 4814746). Dieses ist eine Fortführung eines älteren Patentantrags von 1983, welche damals sogar noch vor der Anmeldung von Sperry eingereicht wurde (Sperry: 20.06.1983, IBM: 01.06.1983). Das IBM-Patent ist etwas allgemeiner gehalten, der Anspruch 7 des IBM-Patents entspricht jedoch genau der Funktionsweise von LZW:
"...adding a new string S' to said set, where S' comprises a concatenation of said current string match and an immediately succeeding symbol in said data stream; and assigning an identifier I' to said string S'." [4].
Somit unterlief dem amerikanischen Patentamt vermutlich ein Fehler und der gleiche Algorithmus wurde doppelt patentiert.

In den USA können im Gegensatz zu Europa unter dem Begriff ‘Method and apparatus’ regulär auch Problemlösungen patentiert werden, die aus Software-Implementationen bestehen. In Europa sind Patente auf Software, d. h. „Programme für Datenverarbeitungsanlagen“ aber nach Artikel 52 Absatz 2c des Europäischen Patentübereinkommens (EPÜ) von den patentfähigen Erfindungen ausgeschlossen [6]. Trotzdem konnte Sperry auch in Europa ein Patent auf LZW erwerben. Ein Grund, wie das gelang, könnte die Darstellung des Verfahrens, als Teil einer Maschine sein. Im Patenttext wird in Blockdiagrammen auch Hardwareteile (u.a. RAM) in die Beschreibung des Verfahren miteinbezogen [2 Skizzen 2/9. ff]. Desweiteren wurde auch die Anwendung des Verfahrens innerhalb von Hardware als Anwendungsbeispiel angeführt:
Ein elektronischer Speicher könnte ein Kompressor in der Eingangselektronik und dementsprechend ein Dekompressor am Ausgang beinhalten [2 S. 7]. Trotzdem wurde der Patentschrift, FORTRAN-Programmcode beigelegt, die das Verfahren in Software implementiert, ohne das auf spezielle Hardware Bezug genommen wird. („..implementing in software a data decompressor...“ [2 S. 7; Skizzen 6/9 ff]). Es ist somit schwer einzusehen, das dieses Patent anscheinend nicht als "Programm für eine Datenverarbeitungsanlage" angesehen wurde.

Seit Mitte der Neunziger Jahre verlangt Unisys Lizenzgebühren. Softwareentwicklern müssen von Unisys eine Lizenz erwerben, falls ihre Programme den LZW-Algorithmus einsetzen um z.B.: GIF-Bilder zu erzeugen oder zu dekodieren. Nachdem Anfangs Freewareprogramme nicht lizenzpflichtig waren [8], muss für sie mittlerweile eine (kostenlose) Lizenz erworben werden. Unisys verlangt ebenfalls von Websitebetreibern Lizenzgebühren, falls diese GIF-Bilder benutzen, die evtl. nicht von einem Programm mit gültiger Lizenz erstellt wurden. Um Rechtssicherheit zu erhalten, müssten diese z.B.: 5000 US $ für eine Lizenz für zwei Server entrichten [7]. Mittlerweile haben fast 2000 Firmen eine LZW-Lizenz, unter ihnen z.B.: Microsoft, Adobe, Corel [8]. LZW ist damit ein ziemlich erfolgreiches Patent.

Als Folge der Lizenzforderung für das GIF-Format ist dieses mittlerweile ziemlich unter Druck und es wird nach Alternativen für das Internet gesucht, etwa das Bildformat PNG, welches den LZW-Algorithmus nicht benutzt [9,0].
Trotzdem denke ich, dass das GIF-Format zu weit verbreitet ist, als das es so schnell ersetzt werden könnte.
2003 wird das amerikanische Patent der Firma Unisys auf LZW auslaufen.

 Quellen:

[1]: LZW-Algorithmus: http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
[2]: Europäisches Patent: http://www.depatisnet.de: Dokument EP0000129439A1
[3]: US-Patent (Unisys): PN/4558302
[4]: US-Patent (IBM): PN/4814746
[5]: Patente auf Kompressionsalgorithmen: http://www.cd.sc.ehu.es/DOCS/mice/compression-faq/part1/faq-doc-7.html
[6]: Artikel 52 EPÜ: „Patentfähige Erfindungen“ http://www.european-patent-office.org/legal/epc/d/ar52.html
[7]: Lizenzinformationen: http://www.unisys.com/unisys/lzw/lzw-license.asp
[8]: Unternehmen mit Lizenz: http://www.unisys.com/unisys/lzw/lzw-companies.asp
[9]: Burn All Gifs: http://burnallgifs.org/
[0]: GNU Philosophie: http://www.gnu.org/philosophy/gif.html

 Weiterführende Links:

Deutsches Patent- und Markenamt: http://www.dpma.de/
US-Patentamt: http://www.uspto.gov/
GIF-Format: http://goethe.ira.uka.de/seminare/redundanz/vortrag10/
GIF-FAQ: http://www.cpe.surrey.ac.uk/support/faq/gif_lzw.htm
FFII: Softwarepatente: http://swpat.ffii.org/vreji/pikta/xrani/gif-lzw/index.de.html
c't-Artikel Softwarepatentierung: http://www.heise.de/ct/99/16/072/


Florian Zug

Home            aktuelles Seminar        TüSIG        Kontakt  

Diese Seite wurde zuletzt aktualisiert von Detlev Krause am 30.6.2001
Layout und Realisierung: © 1999 Sylvia Rizvi, © 2000 Ursula Wörz