Gray-Codes

1. Aufgabe

Unter dem Gray-Code versteht man eine Folge binärer Zahlenketten, die nach dem Ingenieur Frank Gray, einem Forscher in den Bell Laboratories, benannt wurde. Er erhielt im Jahre 1953 für die Nutzung des nach ihm benannten Codes das U.S. Patent No. 2 632 058 Pulse Code Communication. Durch die Anzahl der Bits wird die Länge n eines Gray-Codes festgelegt. Man kann sich leicht überlegen, dass es zu einem bestimmten n 2n unterschiedliche Gray-Codes gibt. Die Besonderheit des Gray-Codes liegt darin, dass sich benachbarte Zahlenketten nur in genau einem Bit unterscheiden. Dies gilt auch für den Übergang vom 2n-1.-ten Code zum 0.-ten Code:

Definition: Eine Folge aller 2n Bitketten der Länge n (n ≥ 1) heißt ein Gray-Code der Länge n, falls sich jeweils 2 benachbarte Bitketten nur in einer Bitposition unterscheiden.

Diese Eigenschaft kommt vielen Anwendungen zu Gute, wie wir beispielsweise an einem Inkrementalgeber erörtern können. Würde ein Inkrementalgeber eine herkömmliche Binärzahl (im Zweier-Komplement) als Position liefern, also etwa 0101 für 5 und 0110 für 6, dann gäbe es ein Problem, wenn nicht alle Bits absolut gleichzeitig ihre Wertigkeit ändern. In diesem Fall könnten Phantomwerte wie 0100 (4) oder 0111 (7) auftreten. Der Gray-Code hat dieses Problem nicht, da sich benachbarte Werte nur in einem Bit unterscheiden. In Abbildung 1 wird diese Eigenschaft am Beispiel des 4-Bit-Gray-Codes demonstriert:

4-Bit-Gray-Code.

Abbildung 1. 4-Bit-Gray-Code.


Um Gray-Codes einer bestimmten Länge zu erzeugen, ist eine Darstellung wie in Abbildung 2 gezeigt intuitiver. Ausgehend von einer Kombination der beiden Bits 0 und 1 wird durch wiederholtes Spiegeln der Ausgangsinformation und Hinzufügen von 0- und 1-Werten an der höchstwertigen Stelle der vollständige Gray-Code aufgebaut. In Abbildung 2 finden Sie die sukzessive Erzeugung des 1-, 2- und 3-Bit-Gray-Codes bis hin zum 4-Bit-Gray-Code vor:

Bildung des Gray-Codes durch Spiegelung und Bitergänzung.

Abbildung 2. Bildung des Gray-Codes durch Spiegelung und Bitergänzung.


Wir benutzen die Gray-Code-Darstellung, um an Hand einer Reihe von C#-Klassen das Zusammenspiel unterschiedlicher C#-Sprachkonstrukte zu üben und zu vertiefen. Das Endergebnis dieser Aufgabe ließe sich sicherlich auch kürzer und direkter erzielen, nur würden wir dabei keinen Lerneffekt erreichen.

1.1 Klasse BitVector

Einen einzelnen Gray-Code (einer bestimmten Länge) stellen wir in einem Objekt der Klasse BitVector dar. Dazu benötigen wir die Länge des Codes und zum anderen die Bits (Tabelle 1):

Element

Schnittstelle und Beschreibung

Konstruktor

public BitVector (int length);

Der Konstruktor dient zum Erzeugen eines Bitvektors für length Bits.

Eigenschaft Length

public int Length { get; }

Liefert die Anzahl der Bits des Gray-Codes zurück.

Methode Extended

public BitVector Extended();

Für das Anwenden der Bitergänzung liefert diese Methode einen um 1 Bit erweiterten Gray-Code zurück. Das erste Bit besitzt den Wert 0.

Indexer

public bool this[int index];

Mit Hilfe des Indexers ist der direkte lesende und schreibende Zugriff auf das n.-te Bit (Parameter index) eines Bitvektors möglich.

Tabelle 1. Zentrale Elemente der Klasse BitVector.

1.2. Klasse GrayCodeCalculator

Ein Objekt der Klasse GrayCodeCalculator berechnet die Gray-Codes einer bestimmten Länge. Das Resultat wird in Gestalt eines List<BitVector>-Objekts zurückgegeben.

Element

Schnittstelle und Beschreibung

Konstruktor

public BitVector (int length);

Der Konstruktor legt ein Gray-Code-Kalkulator-Objekt zum Erzeugen von Graycodes der Länge length an.

Eigenschaft Length

public int Length { get; set; }

Dient zum Lesen oder Schreiben der Gray-Code-Länge, die der Calculator berechnet.

Methode Calculate

public List<BitVector> Calculate();

Berechnet alle Gray-Codes einer bestimmten Länge (siehe die Eigenschaft Length). Das Ergebnis wird in einem GrayCodeList-Objekt zusammengestellt.

Tabelle 2. Zentrale Elemente der Klasse GrayCodeCalculator.


Die Calculate-Methode des Kalkulators arbeitet auf einem rekursiven Prinzip. Liegen für eine bestimmte Länge n alle Gray-Codes vor, so erhält man die Gray-Codes der Länge n+1 wie in Abbildung 2 skizziert wird. Es werden alle vorliegenden Gray-Codes der Länge n an einer fiktiven Spiegelachse gespiegelt. Um Gray-Codes der Länge n+1 zu erhalten, werden diese zunächst mit der Extended-Methode aus Tabelle 1 um ein Bit vorne verlängert. In einem zweiten Schritt wird dann bei den gespiegelten Gray-Codes an der höchstwertigen Stelle das Bit auf den Wert 1 gesetzt. Auf diese Weise lassen sich rekursiv alle Gray-Codes einer bestimmten Länge berechnen.

2. Lösung

Wir stellen unmittelbar aufeinanderfolgend Lösungsvorschläge für die Klassen BitVector und GrayCodeCalculator vor:

01: class BitVector
02: {
03:     private int length;
04:     private bool[] vector;
05: 
06:     // c'tors
07:     public BitVector()
08:     {
09:         this.length = 0;
10:         this.vector = null;
11:     }
12: 
13:     public BitVector(int length)
14:     {
15:         this.length = length;
16:         this.vector = new bool[length];
17:     }
18: 
19:     // properties
20:     public int Length
21:     {
22:         get
23:         {
24:             return this.length;
25:         }
26:     }
27: 
28:     // public interface
29:     public BitVector Extended()
30:     {
31:         BitVector v = new BitVector(this.length + 1);
32: 
33:         for (int i = 0; i < this.length; i ++)
34:             v.vector[i + 1] = this.vector[i];
35: 
36:         // clear most significant bit
37:         v.vector[0] = false;
38: 
39:         return v;
40:     }
41: 
42:     // operators / indexer
43:     public bool this[int index]
44:     {
45:         get
46:         {
47:             return this.vector[index];
48:         }
49: 
50:         set
51:         {
52:             this.vector[index] = value;
53:         }
54:     }
55: 
56:     // overrides
57:     public override String ToString()
58:     {
59:         String s = "";
60: 
61:         for (int i = 0; i < this.length; i ++)
62:             s += (this.vector[i]) ? '1' : '0';
63: 
64:         return s;
65:     }
66: }

Beispiel 1. Klasse BitVector.


01: using System;
02: using System.Collections.Generic;
03: 
04: class GrayCodeCalculator
05: {
06:     private int length;
07: 
08:     // c'tors
09:     public GrayCodeCalculator()
10:     {
11:         this.length = 0;
12:     }
13: 
14:     public GrayCodeCalculator(int length)
15:     {
16:         this.length = length;
17:     }
18: 
19:     // properties
20:     public int Length
21:     {
22:         get
23:         {
24:             return this.length;
25:         }
26: 
27:         set
28:         {
29:             this.length = value;
30:         }
31:     }
32: 
33:     // public interface
34:     public List<BitVector> Calculate()
35:     {
36:         return Calculate(this.length);
37:     }
38: 
39:     // private helper methods
40:     private List<BitVector> Calculate (int length)
41:     {
42:         if (length == 1)
43:         {
44:             return CalculateRankOne ();
45:         }
46:         else
47:         {
48:             List<BitVector> tmp = this.Calculate (length - 1);
49: 
50:             // allocate a new Gray Code list
51:             List<BitVector> result = new List<BitVector>();
52: 
53:             // copy old entries ...
54:             for (int i = 0; i < tmp.Count; i ++)
55:             {
56:                 // ... and prefix old entry with '0'
57:                 BitVector v = tmp[i];
58:                 BitVector ex = v.Extended();
59:                 ex[0] = false;
60:                 result.Add (ex);
61:             }
62: 
63:             // mirror old entries ...
64:             for (int i = tmp.Count - 1; i >= 0; i--)
65:             {
66:                 // ... and prefix old entry with '1'
67:                 BitVector v = tmp[i];
68:                 BitVector ex = v.Extended();
69:                 ex[0] = true;
70:                 result.Add (ex);
71:             }
72: 
73:             return result;
74:         }
75:     }
76: 
77:     List<BitVector> CalculateRankOne ()
78:     {
79:         // need two entries
80:         List<BitVector> list = new List<BitVector>();
81: 
82:         BitVector vec0 = new BitVector (1);
83:         vec0[0] = false;
84:         list.Add (vec0);
85: 
86:         BitVector vec1 = new BitVector(1);
87:         vec1[0] = true;
88:         list.Add (vec1);
89: 
90:         return list;
91:     }
92: }

Beispiel 2. Klasse GrayCodeCalculator.


Testbeispiel:

public static void Main()
{
    GrayCodeCalculator calc = new GrayCodeCalculator(3);
    List<BitVector> codes = calc.Calculate();

    Console.WriteLine("{0}-Bit-Gray-Code:", calc.Length);
    for (int i = 0; i < codes.Count; i++)
        Console.WriteLine (codes[i]);
    Console.WriteLine();

    calc.Length = 5;
    codes = calc.Calculate();

    Console.WriteLine("{0}-Bit-Gray-Code:", calc.Length);
    for (int i = 0; i < codes.Count; i++)
        Console.WriteLine(codes[i]);
}

Ausgabe:

3-Bit-Gray-Code:
000
001
011
010
110
111
101
100

5-Bit-Gray-Code:
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000