Bessere Flachbildschirme dank diskreter Optimierung

Andreas Karrenbauer

Bessere Flachbildschirme dank diskreter Optimierung

Unser Ziel ist, den Stand der Bildschirmtechnik mit Hilfe diskreter Optimierung voranzubringen. Wir streben einen niedrigeren Energieverbrauch für Flachbildschirme der nächsten Generation durch die Reduzierung ihrer Adressierzeit an. Zu diesem Zweck nutzen wir eine Eigenschaft moderner Displays: die Pixel sind in einer Matrix angeordnet und werden durch jeweils einen Kontakt pro Zeile und einen pro Spalte angesteuert. Der Einfachheit halber stellen wir uns diese Kontakte als Schalter vor, so dass ein Pixel (i, j) genau dann leuchtet, wenn die Schalter für Zeile i und Spalte j geschlossen sind. Daraus folgt, dass nicht jedes beliebige Muster in einem Schritt dargestellt werden kann. Daher ist es notwendig, das Bild in mehrere Teilbilder zu zerlegen. Traditionell wird ein Bild Zeile für Zeile bei ausreichend hoher Bildrate angezeigt, so dass das Auge nur den Mittelwert wahrnimmt. Diese Methode wird als Einzeilenadressierung bezeichnet, da jedes Teilbild aus einer einzelnen Zeile besteht. Dies ist eine Hauptursache für übermäßigen Stromverbrauch, weil jeder Pixel nur für eine sehr kurze Zeit leuchtet und somit sehr hell sein muss, um eine ausreichende durchschnittliche Helligkeit zu erreichen. Es ist jedoch möglich, mehrere Zeilen auf einmal zu adressieren. Allerdings muss dazu ein diskretes Optimierungsproblem auf einem Treiberchip in Echtzeit gelöst werden. Durch den harten Wettbewerb auf dem Displaymarkt bedingen die Fertigungskosten sehr strenge Anforderungen an die verfügbare Chipfl äche und somit auch an Rechenoperationen und Speicherbedarf. Deshalb haben wir einen voll-kombinatorischen Aproximationsalgorithmus für den praktisch relevanten Fall entwickelt, in dem die Pixel in aufeinanderfolgenden Zeilen gleichzeitig adressiert werden. Dies bedeutet, dass der Algorithmus nur Addition, Subtraktion und Vergleiche verwendet und sich somit kostengünstig in Hardware implementieren lässt. Trotzdem werden in Echtzeit Zerlegungen berechnet, deren Zielfunktionswert in der Praxis meistens weniger als ein Prozent vom Optimum entfernt ist.

Diese Erfi ndung wurde von uns erfolgreich patentiert. Sie wird zur Zeit von Dialog Semiconductor unter dem Namen SmartXtend vermarktet und ist in OLEDDisplays von Futaba (früher TDK) verbaut. Dadurch wurden z. B. auch transparente und fl exible Displays Realität. Mit dem Lenovo S800 [ Abbildung 1 ] , dem Explay Crystal und dem Nexian Glaze M9090 gibt es drei Mobiltelefone auf dem internationalen Markt, die unsere Technologie enthalten.

Abbildung 1: Lenovo S800

In einem Folgeprojekt, das von der Deutschen Forschungsgemeinschaft gefördert wird, dehnen wir unsere Forschung auf weitere Displaytechnologien aus. Unsere Arbeit wird in Geräten wie OLED-Displays, Plasma-Bildschirmen und E-Paper Anwendung fi nden.

Abbildung 2: Repräsentierung einer Bildschirmmatrix durch einen bipartiten Graphen

Dazu entwickeln wir neue ausgeklügelte Steuerungsalgorithmen. Wir leisten damit einen Beitrag zur Theorie der Adressierung von Bildschirmen mit passiver Matrix, die zur Zeit ein profundes Verständnis der zugrunde liegenden algorithmischen Probleme vermissen lässt. Wir schließen eine Forschungslücke im Themengebiet der Approximationsalgorithmen für Bicliquenzerlegungsprobleme, die auch in anderen Anwendungen (wie z. B. Graphenzeichnen, EDV-Sicherheit und Genetik) vorkommen, die somit ebenfalls von der Grundlagenforschung in diesem Projekt profi tieren. In der Tat sind wir vor Kurzem bereits einen großen Schritt weiter gekommen, in dem wir sehr scharfe untere und obere Schranken für Aproximationsfaktoren von Polynomialzeitalgorithmen für Bicliquenüberdeckung und Bicliquenpartitionierung gezeigt haben.