Codierungstheorie

Gray-Code

 aufwärts

Ein Gray-Code ist eine Codierung der Zahlen 0, ..., 2n-1 durch einen n-Bit-Blockcode in der Weise, dass Codewörter, die aufeinander folgenden Zahlen entsprechen, den Hamming-Abstand 1 haben, d.h. sich in genau einem Bit unter­scheiden.

Es gibt verschiedene solche Codierungen, also verschiedene n-Bit-Gray-Codes.

Grundlagen

Definition:  Sei A ein Alphabet. Dann ist A* die Menge aller Wörter über A; ferner ist An die Menge aller Wörter der Länge n über A. Das leere Wort wird mit ε bezeichnet, d.h. es gilt A0 = {ε}.

Definition:  Zwei Wörter u, v Element A* werden verkettet, indem sie zu einem Wort uv hinter­einandergeschrieben werden. Für alle Wörter u Element A* gilt uε = εu = u.

Definition:  Sei u ein Wort über A und X = x0, ..., xk-1 eine endliche Folge von Wörtern über A. Das Produkt uX ist die endliche Folge

uX  =  ux0, ..., uxk-1,

d.h. die Folge uX entsteht, indem u mit jedem Wort xi der Folge X verkettet wird.

Definition:  Sind X = x0, ..., xk-1 und Y = y0, ..., ym-1 zwei endliche Folgen, so ist X, Y die endliche Folge, die entsteht, wenn X und Y hinter­einandergeschrieben werden:

X, Y  =  x0, ..., xk-1, y0, ..., ym-1

Definition:  Ist X = x0, ..., xk-1 eine endliche Folge, so ist XR die endliche Folge, die entsteht, wenn X rückwärts durchlaufen wird:

XR  =  xk-1, ..., x0

Im Folgenden sei A = boolesche Werte = {0, 1}.

Konstruktion

Wir bezeichnen den zu konstruierenden n-Bit-Gray-Code mit Gn. Da es beim Gray-Code auf die Reihenfolge der Codewörter ankommt, ist Gn eine endliche Folge.

 

Der Gray-Code Gn für n Element natürliche Zahlen0 ergibt sich rekursiv in folgender Weise:

Gn  =   geschweifte Klammer
ε    falls  n = 0
0Gn-1, 1Gn-1R    falls  n > 0

 

Die nach dieser Vorschrift konstruierten Gray-Codes ergeben sich also folgender­maßen (Codewörter unter­einander geschrieben):

G0 = ε
 
G1 = 0
  1
 
G2 = 00
  01
  11
  10
 
G3 = 000
  001
  011
  010
  110
  111
  101
  100

Literatur

[Ham 87]R.W. Hamming: Information und Codierung. VCH (1987)

 

 

Weiter mit:  [Lineare Codes]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 06.12.2006   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik