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

BitVector (int len);

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

getter-Methode Length

int Length ();

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

Methode Extended

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.

Operator []

bool& operator[] (int);
const bool& operator[](int) const;

Mit Hilfe des []-Operators ist gezielt der direkte Zugriff auf das n.-te Bit in einem Bitvektor möglich, lesend und schreibend.

Hinweis: An Hand der zwei Überladungen des Operators können Sie eine Spezialität der Programmiersprache C++ beobachten. Um der Operator sowohl auf const- als auch auf non-const-Objekte anwenden zu können, kann dieser in zwei Versionen deklariert werden, die sich nur durch den Zusatz des const-Schlüsselworts unterscheiden. Liegt bei einer Anwendung ein const-Objekt vor, kommt die const-Version zum Zuge. Haben wir es mit einem veränderbaren Objekt zu tun, wird vom C++-Compiler die non-const-Version ausgewählt.

Tabelle 1. Zentrale Elemente der Klasse BitVector.

2. Klasse GrayCodeList

Für die Ablage aller Gray-Codes einer bestimmten Länge verwenden wir ein GrayCodeList-Objekt. Da die Anzahl der Gray-Codes einer bestimmten Länge von vorne herein bekannt ist (bei einer Länge n gibt es 2n BitVector-Objekte), kann eine entsprechend einfache Verwaltung der BitVector-Objekte zu Grunde gelegt werden (Tabelle 2):

Element

Schnittstelle und Beschreibung

Konstruktor

GrayCodeList (int count);

Der Konstruktor dient zum Erzeugen eines Listenobjekts für count BitVector-Objekte.

getter-Methode Length

int Count ();

Liefert die (maximale) Anzahl der BitVector-Objekte zurück, die in dem Listenobjekt Platz finden.

Methode Add

bool Add (const BitVector&);

Fügt ein BitVector-Objekt in das aktuelle Listenobjekt ein. Ist das Listenobjekt bereits voll, liefert Add den Wert false zurück, andernfalls true.

Operator []

BitVector operator[] (int i) const;

Liefert aus dem Listenobjekt eine Kopie des i.-ten BitVector-Objekts zurück. Der Operator unterstützt also nur den lesenden Zugriff auf das Listenobjekt und keinen schreibenden Zugriff.

Tabelle 2. Zentrale Elemente der Klasse GrayCodeList.

3. Klasse GrayCodeCalculator

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

Element

Schnittstelle und Beschreibung

getter-Methoden GetLength und SetLength

int GetLength () const;
void SetLength (int length);

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

Methode Calculate

GrayCodeList Calculate ();

Berechnet alle Gray-Codes einer bestimmten Länge (siehe die getter- und setter-Methoden GetLength bzw. SetLength. Das Ergebnis wird in einem GrayCodeList-Objekt zusammengestellt.

Tabelle 3. Zentrale Elemente der Klasse GrayCodeCalculator.


Die Calculate-Methode des Calculators 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

Quellcode: Siehe auch github.com/peterloos/Cpp_GrayCodes.git.

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

01: class BitVector
02: {
03: private:
04:     int m_len;
05:     bool* m_vec;
06: 
07: public:
08:     // c'tors / d'tor
09:     BitVector();
10:     BitVector(int len);
11:     BitVector(const BitVector&);
12:     ~BitVector();
13: 
14:     // public interface
15:     BitVector Extended();
16: 
17:     // getter
18:     int Length () const { return m_len; }
19: 
20:     // public operators
21:     BitVector& operator= (const BitVector&);
22:     bool& operator[] (int);
23:     const bool& operator[](int) const;	
24: 
25:     // output
26:     friend ostream& operator<< (ostream&, const BitVector&);
27: };

Beispiel 1. Klasse BitVector: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "BitVector.h"
05: 
06: BitVector::BitVector()
07: {
08:     m_len = 0;
09:     m_vec = (bool*) 0;
10: }
11: 
12: BitVector::BitVector(int len)
13: {
14:     m_len = len;
15:     m_vec = new bool [m_len];
16: 
17:     for (int i = 0; i < m_len; i ++)
18:         m_vec[i] = false;
19: }
20: 
21: BitVector::BitVector(const BitVector& v)
22: {
23:     m_len = v.m_len;
24:     m_vec = new bool [m_len];
25: 
26:     for (int i = 0; i < m_len; i ++)
27:         m_vec[i] = v.m_vec[i];
28: }
29: 
30: BitVector::~BitVector()
31: {
32:     delete[] m_vec;
33: }
34: 
35: BitVector BitVector::Extended()
36: {
37:     BitVector v (m_len + 1);
38: 
39:     for (int i = 0; i < m_len; i++)
40:         v.m_vec[i + 1] = m_vec[i];
41: 
42:     // clear most significant bit
43:     v.m_vec[0] = false;
44: 
45:     return v;
46: }
47: 
48: bool& BitVector::operator[] (int i)
49: {
50:     return m_vec [i];
51: }
52: 
53: const bool& BitVector::operator[](int i) const
54: {
55:     return m_vec [i];
56: }
57: 
58: BitVector& BitVector::operator= (const BitVector& v)
59: {
60:     if (this == &v)
61:         return *this;
62: 
63:     delete[] m_vec;
64: 
65:     m_len = v.m_len;
66:     m_vec = new bool [m_len];
67: 
68:     for (int i = 0; i < m_len; i ++)
69:         m_vec[i] = v.m_vec[i];
70: 
71:     return *this;
72: }
73: 
74: ostream& operator<< (ostream& os, const BitVector& v)
75: {
76:     for (int i = 0; i < v.m_len; i ++)
77:         os << (v[i] == true) ? '1' : '0';
78: 
79:     return os;
80: }

Beispiel 2. Klasse BitVector: Implementierung.


01: class GrayCodeList
02: {
03: private:
04:     int m_len;
05:     int m_top;
06:     BitVector* m_list;
07: 
08: public:
09:     // c'tors / d'tor
10:     GrayCodeList();
11:     GrayCodeList(int len);
12:     GrayCodeList(const GrayCodeList&);
13:     ~GrayCodeList();
14: 
15:     // getter
16:     int Length () const { return m_len; }
17: 
18:     // public interface
19:     bool Add (const BitVector&);
20: 
21:     // public operators
22:     BitVector operator[] (int i) const;
23:     GrayCodeList& operator= (const GrayCodeList&);
24: 
25:     // output
26:     friend ostream& operator<< (ostream&, const GrayCodeList&);
27: };

Beispiel 3. Klasse GrayCodeList: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "BitVector.h"
05: #include "GrayCodeList.h"
06: 
07: // c'tors / d'tor
08: GrayCodeList::GrayCodeList()
09: {
10:     m_len = 0;
11:     m_top = 0;
12:     m_list = (BitVector*) 0;
13: }
14: 
15: GrayCodeList::GrayCodeList(int len)
16: {
17:     m_len = len;
18:     m_top = 0;
19:     m_list = new BitVector [m_len];
20: }
21: 
22: GrayCodeList::GrayCodeList(const GrayCodeList& v)
23: {
24:     m_len = v.m_len;
25:     m_top = v.m_top;
26:     m_list = new BitVector [m_len];
27: 
28:     for (int i = 0; i < m_top; i ++)
29:         m_list[i] = v.m_list[i];
30: }
31: 
32: GrayCodeList::~GrayCodeList()
33: {
34:     delete[] m_list;
35: }
36: 
37: // public interface
38: bool GrayCodeList::Add (const BitVector& vec)
39: {
40:     if (m_top == m_len)
41:         return false;
42: 
43:     m_list[m_top] = vec;
44:     m_top ++;
45:     return true;
46: }
47: 
48: // public operators
49: BitVector GrayCodeList::operator[] (int i) const
50: {
51:     return m_list[i];
52: }
53: 
54: GrayCodeList& GrayCodeList::operator= (const GrayCodeList& list)
55: {
56:     if (this == &list)
57:         return *this;
58: 
59:     delete[] m_list;
60: 
61:     m_len = list.m_len;
62:     m_top = list.m_top;
63:     m_list = new BitVector [m_len];
64: 
65:     for (int i = 0; i < m_top; i ++)
66:         m_list[i] = list.m_list[i];
67: 
68:     return *this;
69: }
70: 
71: // output
72: ostream& operator<< (ostream& os, const GrayCodeList& list)
73: {
74:     for (int i = 0; i < list.Length(); i ++)
75:         os << list[i] << endl;
76: 
77:     return os;
78: }

Beispiel 4. Klasse GrayCodeList: Implementierung.


01: class GrayCodeCalculator
02: {
03: private:
04:     int m_length;
05: 
06: public:
07:     // c'tor
08:     GrayCodeCalculator();
09: 
10:     // getter/setter
11:     int GetLength () const { return m_length; }
12:     void SetLength (int length) { m_length = length; }
13: 
14:     // public interface
15:     GrayCodeList Calculate ();
16: 
17: private:
18:     // private helper method
19:     GrayCodeList Calculate (int length);
20:     GrayCodeList CalculateRankOne ();
21: };

Beispiel 5. Klasse GrayCodeCalculator: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "BitVector.h"
05: #include "GrayCodeList.h"
06: #include "GrayCodeCalculator.h"
07: 
08: // c'tor
09: GrayCodeCalculator::GrayCodeCalculator()
10: {
11:     m_length = 0;
12: }
13: 
14: // public interface
15: GrayCodeList GrayCodeCalculator::Calculate ()
16: {
17:     return Calculate (m_length);
18: }
19: 
20: // private helper methods
21: GrayCodeList GrayCodeCalculator::Calculate (int length)
22: {
23:     if (length == 1)
24:     {
25:         return CalculateRankOne ();
26:     }
27:     else
28:     {
29:         GrayCodeList tmp = Calculate (length - 1);
30: 
31:         // allocate a new Gray Code list - twice a large
32:         GrayCodeList result (2 * tmp.Length());
33: 
34:         // copy old entries ...
35:         for (int i = 0; i < tmp.Length(); i ++)
36:         {
37:             // ... and prefix old entry with '0'
38:             BitVector v = tmp[i];
39:             BitVector ex = v.Extended();
40:             ex[0] = false;
41:             result.Add (ex);
42:         }
43: 
44:         // mirror old entries ...
45:         for (int i = tmp.Length() - 1; i >= 0; i --)
46:         {
47:             // ... and prefix old entry with '1'
48:             BitVector v = tmp[i];
49:             BitVector ex = v.Extended();
50:             ex[0] = true;
51:             result.Add (ex);
52:         }
53: 
54:         return result;
55:     }
56: }
57: 
58: GrayCodeList GrayCodeCalculator::CalculateRankOne ()
59: {
60:     // need two entries
61:     GrayCodeList list (2);
62: 
63:     BitVector v0 (1);
64:     v0[0] = false;
65:     list.Add (v0);
66: 
67:     BitVector v1 (1);
68:     v1[0] = true;
69:     list.Add (v1);
70: 
71:     return list;
72: }

Beispiel 6. Klasse GrayCodeCalculator: Implementierung.


Testbeispiel:

#include <iostream>
using namespace std;

#include "BitVector.h"
#include "GrayCodeList.h"
#include "GrayCodeCalculator.h"

void main()
{
    GrayCodeCalculator calc;
    calc.SetLength (3); 
    GrayCodeList codes = calc.Calculate ();
    cout << calc.GetLength() << "-Bit-Gray-Code:" << endl;
    cout << codes << endl;

    calc.SetLength (5); 
    codes = calc.Calculate ();
    cout << calc.GetLength() << "-Bit-Gray-Code:" << endl;
    cout << codes << endl;
}

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