Aufgabe - Data Matrix

Aufgabenkontext

Zur Kennzeichnung ihrer Produkte führt eine Firma ein neues Beschriftungssystem ein, das für jedes Produkt die graphische Darstellung einer Produkt-ID ermöglicht. Dazu werden alle Produkte mit einem zweidimensionalen Code versehen, der Data Matrix genannt wird. Diese besteht aus einem inneren (8 mal 8 Kästchen großen) Datenblock und einer äußeren Begrenzung (vgl. Abbildung 1). Zur Verdeutlichung ist in der Abbildung der Datenblock von der Begrenzung durch einen roten Rahmen abgehoben. Mithilfe einer Data Matrix wird die ID eines Produktes binär codiert. Die zugehörigen Daten werden dabei innerhalb des Datenblocks dargestellt. Ein schwarzes Kästchen entspricht dem Binärwert 1, und ein weißes dem Binärwert 0.

Zur effizienten Speicherung des Datenblocks einer Data Matrix innerhalb einer Produktverwaltungssoftware wird zunächst der Ansatz einer zeilenweisen Lauflängencodierung vorgeschlagen.

In der Tabelle in Abbildung 5 ist eine Lauflängencodierung der ersten und letzten Zeile eines Datenblocks angegeben.

Frage

Ergänzen Sie die fehlenden Zeilen der Tabelle.

3 2 3 5 1 2 1 1 6 3 1 1 1 2 0 1 7 1 2 3 1 1 8 0 2 5 1

Frage

Für die Übertragung der Lauflängencodierung sollen die Zahlen binär mit einem Code fester Länge dargestellt werden.

Untersuchen Sie, wie viele Bits dafür pro Zahl mindestens nötig sind.

Es werden 4 Bit gebraucht, da 9 verschiedene Werte gebraucht werden.

Frage

Untersuchen Sie, wie viele Bits zur binären Darstellung der Lauflängencodierung einer Zeile eines Datenblocks im besten und im schlechtesten Fall jeweils benötigt werden.

Wort Case:

• 36 Bit (Checkerboard)
  • 0000 wenn es mit Schwarz beginnt
  • 0001,0001,0001,0001,0001,0001,0001,0001