Inhaltsverzeichnis

Es soll ein Programm zur Unterstützung der Vorlesung „Codierungstheorie und Kryptographie“ bei Herrn Prof. Dr. Peter entwickelt werden. Das Programm soll die Möglichkeit bieten, Codes mit definierten Eigenschaften zu entwerfen und Codeworte anhand dieser Codes zu überprüfen und ggf. zu korrigieren.

Unterstützte Codes

Hamming-Code, Abramson-Code, Fire-Code, BCH-Code

Anforderungen

1. Potenzreste für primitive, irreduzible Generatorpolynome ermitteln.

2. Erzeugen von Codes mit definierten Eigenschaften

2.1. Hamming-Code

2.1.1. Generatorpolynom wird vorgegeben

2.1.2. Ermitteln der Codeeigenschaften (n,m,k)

2.2. Abramson-Code

2.2.1. Konstruktion des Codes bei gegebenem G₁(u)

2.2.2. Ermitteln der Codeeigenschaften

2.3. Fire-Code

2.3.1. Konstruktion des Codes bei gegebenem G₁(u) und wahlweise

2.3.1.1. K₂ oder

2.3.1.2. b

2.3.2. Ermitteln der Codeeigenschaften

2.4. BCH-Code

2.4.1. Konstruktion des Codes bei gegebenem G₁(u) und e

2.4.2. Ermitteln der Codeeigenschaften

2.4.3. Beschränkung: Wurzel a=u

2.4.4. Bildung von G₂(u), ..., G_e(u)

3. Für Hamming-, Abramson- und Fire-Code zusätzlich

3.1.1. Prüfschema erstellen

3.1.2. Prüfen, ob ein Codewort richtig ist

3.1.3. Ein falsches Codewort korrigieren, wahlweise per

3.1.3.1. Schieberegister oder

3.1.3.2. Prüfschema

Technische Details

Implementiert wird dieses Projekt in der Programmiersprache Delphi.

Benutzerhandbuch

Einleitung

Dieses Programm wurde im Rahmen einer Studienarbeit im Studiengang Medizinische Informatik an der Fachhochschule Heilbronn / Universität Heidelberg zur Unterstützung der Vorlesung "Codierungstheorie und Kryptographie" entwickelt.

Das Programm bietet die Möglichkeit, Codes mit definierten Eigenschaften zu entwerfen und Codeworte anhand dieser Codes zu überprüfen und ggf. per Schieberegister oder per Prüfschema zu korrigieren.

Bei den meisten Fenstern erhält man durch Klick auf das rote Fragezeichen

eine Hilfestellung.

Allgemeines zur Eingabe von Polynomen

Polynome (z. B. u⁶+ u⁴+ u³+ u + 1) können im Programm auf verschiedene Arten eingegeben werden:

in Polynomschreibweise mit „^“: u^6+u^4+u^3+u+1
in Polynomschreibweise ohne „^“: u6+u4+u3+u+1
in Binärschreibweise: 1011011

Installation

Dieses Programm muß nicht extra installiert werden. Es reicht aus, die Datei „CT.EXE“ durch Doppelklicken zu starten.

Programmstart

Nach Programmstart erscheint ein Informationsfenster. Dort einfach auf „OK“ klicken.

Das Hauptfenster erscheint:

Ganz oben ist das Menü zu sehen. Hier sind alle Aktionen erreichbar. Rechts sind 2 der vorhandenen à„Tools“ eingeblendet. Zum einen der à„Codewandler“, zum anderen eine à„Liste der irreduziblen Polynome“ bis u⁶.

Menü „Codes“

Hamming – Code

Dieses Fenster berechnet die Codeeigenschaften eines eingegebenen Polynoms als Hamming-Code. Das Polynom muß primitiv sein. Die Eingabe kann sowohl in Polynom- als auch in Binärdarstellung erfolgen.

Berechnet werden: Grad k, Codewortlänge n, Kontrollstellen k und Nachrichtenstellen m.

Danach kann man mit diesen Parametern ein à„Schieberegister“ oder ein à„Prüfschema“ aufrufen, um Codeworte mit diesem Code zu untersuchen.

Abramson – Code

Dieses Fenster berechnet aus einem eingegebenen Polynom G₁(u) das Generatorpolynom G(u) und seine Codeeigenschaften als Abramson - Code. Das Polynom muß primitiv sein. Die Eingabe kann sowohl in Polynom- als auch in Binärdarstellung erfolgen.

Berechnet werden: Generatorpolynom G(u) = G₁(u) * (u+1), Codewortlänge n, Kontrollstellen k und Nachrichtenstellen m.

Danach kann man mit diesen Parametern ein à„Schieberegister“ oder ein à„Prüfschema“ aufrufen, um Codeworte mit diesem Code zu untersuchen.

Fire – Code

Dieses Fenster berechnet die Codeeigenschaften eines eingegebenen Polynoms als Fire-Code (G(u) = G₁(u) * (u^k2 + 1))

Zusätzlich muß noch entweder k₂ oder b (Fehlerbüschellänge, die noch korrigiert werden kann) eingegeben werden. Die jeweils fehlende Größe (k₂ oder b) wird berechnet. G₁(u) muß primitiv sein. Die Eingabe kann sowohl in Polynom- als auch in Binärdarstellung erfolgen.

Berechnet werden: Generatorpolynom G(u), k₂ oder b, Codewortlänge n, Kontrollstellen k und Nachrichtenstellen m.

Danach kann man mit diesen Parametern ein à„Schieberegister“ oder ein à„Prüfschema“ aufrufen, um Codeworte mit diesem Code zu untersuchen.

BCH – Code

Dieses Fenster berechnet die Generatorpolynome für BCH-Codes. Man muß das Generatorpolynom G₁(u) (für e = 1) eingeben und die maximal gewünschte Fehlerzahl e, die noch korrigierbar sein soll. Die Wurzel ist mit a = u fest vorgegeben.

Nach Klick auf „Codeeigenschaften berechnen" werden alle Teilpolynome von G₁(u) bis G_e(u) angezeigt und danach die Generatorpolyome für alle e. Zusätzlich wird jeweils die Anzahl der Kontrollstellen k und Nachrichtenstellen m angezeigt. Bleiben im Codewort keine Nachrichtenstellen mehr über (weil die Kontrollstellen die Codewortlänge übersteigen), so bricht der Berechnungsalgorithmus ab.

Menü „Tools“

Codewandler

Der Codewandler kann Codes von Polynom- in Binärdarstellung und umgekehrt umwandeln. Er erscheint bei Programmstart automatisch rechts oben.

Liste der irreduziblen Polynome

Dies ist eine Liste der irreduziblen Polynome bis u⁶ in Binärdarstellung. Außerdem wird bei den einzelnen Polynomen angegeben, ob sie primitiv sind oder nicht.

Diese Liste ist hilfreich, da man primitive, irreduzible Polynome bei der Eingabe von Generatorpolynomen braucht. Sie erscheint bei Programmstart automatisch am rechten Bildschirmrand.

Potenzreste

In diesem Fenster können Sie Sich die Potenzreste zu einem Generatorpolynom anzeigen lassen.

Die Eingabe kann sowohl in Polynom- als auch in Binärdarstellung erfolgen. Das Programm zeigt Ihnen ebenfalls, ob das eingegebene Polynom primitiv ist.

Schieberegister

Das lineare, rückgekoppelte Schieberegister kann man auf zwei Wegen erreichen:

Man erzeugt einen Hamming-, Abramson- oder Fire-Code und klickt dann auf „Schieberegister >>“. Dann ist das Schieberegister gleich mit den richtigen Einstellungen versehen.
Man ruft es über das „Tools“-Menü auf. Hier müssen Sie noch die erforderlichen Eingaben machen (Generatorpolynom G(u), Nachrichtenstellen m, Kontrollstellen k, max. Büschelfehlerlänge b). Ihre Eingaben werden nicht auf Plausibilität geprüft!

Beim Schieberegister müssen Sie zuerst ein Codewort oben eingeben und dann das Schieberegister mit dem entsprechenden Button initialisieren. Ohne Eingabe liegt am Codeworteingang immer eine 0 an.

Mit den Buttons „ein Schritt vor" und „ein Schritt zurück" können Sie jeweils einen Takt vor bzw. zurück takten. „n-mal takten" taktet das Schieberegister entsprechend der Codewortlänge n. „Endergebnis" schließlich taktet das Schieberegister solange bis eine Analyse vorliegt.

Dabei können folgende Ergebnisse erreicht werden:

- Das Codewort ist korrekt.

- Das Codewort ist fehlerhaft, kann aber nicht korrigiert werden.

- Das Codewort ist fehlerhaft und korrigierbar. Die fehlerhaften Stellen sowie das korrigierte Codewort werden angezeigt.

Prüfschema

Das Prüfschema kann man auf zwei Wegen erreichen:

Man erzeugt einen Hamming-, Abramson- oder Fire-Code und klickt dann auf „Prüfschema >>“. Dann ist das Prüfschema gleich mit den richtigen Einstellungen versehen.
Man ruft es über das „Tools“-Menü auf. Hier müssen Sie noch die erforderlichen Eingaben machen (Generatorpolynom G(u), Nachrichtenstellen m, Kontrollstellen k, maximale Büschelfehlerlänge b). Die maximale Büschelfehlerlänge beträgt b = 3. Ihre Eingaben werden nicht auf Plausibilität geprüft!

Oben sehen Sie das Prüfschema zu Ihrem eingegebenen Generatorpolynom. Geben Sie jetzt bitte ein Codewort ein und klicken dann auf „1. Fehlersyndrom berechnen".

Wenn es sich um ein fehlerhaftes Codewort handelt, erscheint das bei der Division berechnete Fehlersyndrom rechts und Sie können es im Prüfschema suchen lassen (durch Anklicken von „2. in Prüfschema suchen").

Wird es gefunden, so werden die Fundstellen angezeigt und das eingegebene Codewort an den entsprechenden Stellen korrigiert.

Dieses Programm kann im Prüfschema nur mit Büschellängen bis b = 3 arbeiten!

Arbeiten mit mehreren Fenstern

Man kann alle Fenster mehrfach aufrufen (hier z. B. das Fenster zur Berechnung der Potenzreste) und auch mit verschiedenen Fenstern gleichzeitig arbeiten, wie oben zu sehen.

Fenster lassen sich auch außerhalb des Arbeitsbereichs verschieben. Es erscheinen dann horizontale und vertikale Bildlaufleisten.

Literatur

Mitschrieb zur Vorlesung „Codierungstheorie und Kryptographie“ bei Herrn Prof. Dr. Peter
Swoboda, J.: „Codierung zur Fehlerkorrektur und Fehlererkennung“, 1973, Oldenbourg Verlag, München

Download

http://www.kai-lemke.de

Kontakt

Kai Lemke oder Kai Lemke

Lerchenstr. 7 Sollbrüggenstr. 84

74072 Heilbronn 47800 Krefeld

Tel: 07131 / 993489 Tel: 02151 / 593093

kalemke@stud.fh-heilbronn.de kai.lemke@gmx.de