Untersuchung von Kanalkodierverfahren für den Einsatz in drahtlosen Sensornetzwerken

Fachstudie von Michael Terörde

Einleitung:

Die Professur Elektrische Messtechnik entwickelt im Rahmen des Industrieprojektes ‘Energieautarke Aktor- und Sensorsysteme für die intelligente Vernetzung von Produktionsanlagen’, kurz EnAS, drahtlose Sensornetzwerke für die Fabrikautomatisierung. Es soll eine Fertigungsstrecke aufgebaut werden, welche über Funk gesteuert wird. Dabei muss die Kommunikation echtzeitfähig und zuverlässig sein, um den präzisen Produktionsablauf nicht zu gefährden. Durch Störungen im Funkkanal kann es zu Bitfehlern bei der Datenübertragung kommen.

Es wurden bereits technische Änderungen am System vorgenommen, um es robuster zu gestalten. Dazu gehören z.B. ein zweiter Funk-Transciever auf dem Sensor-/ Aktormodul, der die Daten redundant sendet und empfängt.

Aus einer bereits abgeschlossenen Arbeit sind typische Fehlerbitströme bekannt, die bei unterschiedlichen Störern und Signal-Rausch-Abständen die verfälschten Bits angeben.

Diese Studienarbeit hat als Ziel mittels Kanalkodierung die Stör- und Übertragungssicherheit zu verbessern und somit eine robuste Kommunikation sicherzustellen. Es werden zuerst die Grundlagen der Kanalkodierung erklärt und dann unterschiedliche Verfahren hinsichtlich ihrer Einsetzbarkeit untersucht. Die Wahl fiel auf einen systematischen, zyklischen BCH-Code. Mit der Programmiersprache C wurde ein Programm geschrieben, um die Korrektur- und Fehlererkennungsfähigkeit der Codes zu simulieren und zu testen. Dabei wurden der (15,11) Hamming-Code und der (48,36) BCH-Code untersucht und miteinander verglichen.

Abschließend wurde der BCH-Code mit besonderem Hinblick auf die Verlängerung der Übertragungszeit mittels der Programmierentwicklungssoftware IAR Embedded Workbench für den Mikrocontroller MSP430 getestet.

Inhaltsverzeichnis:

1.	Einführung	7
1.1	Einleitung und Zielsetzung	7
1.2	Aufgabe der Kanalkodierung	8
1.3	Abgrenzung der Kanalcodes von anderen Kodierungsarten	10
2.	Grundlagen	12
2.1	Grundbegriffe	12
2.1.1	Hammingdistanz	12
2.1.2	Hamminggewicht	13
2.1.3	Kanalkapazität	16
2.1.4	Perfekter Code	17
2.1.5	Coderate	17
2.1.6	Systematischer Code	18
2.1.7	Lineare Codes	19
2.1.8	Theorem der Kanalkodierung	19
2.2	Störungen des Funkkanals und Fehlerarten	20
2.3	Übersicht verschiedener Kanalkodierungs-Codes	23
2.4	Wiederholungscode	24
2.5	Paritätbits	27
2.6	Automatic Repeat Request	29
2.7	Interleaving	31
3.	Kanalkodierungsverfahren	34
3.1	Zyklische Redundanzprüfung	34
3.1.1	Algorithmus zur Berechnung des CRC-Prüfwerts	35
3.1.2	Algorithmus zur Dekodierung von CRC-Codes	37
3.2	Blockcodes	40
3.2.1	Hamming-Code	40
3.2.2	Shortened Hamming-Code	44
3.3	Zyklische Codes	46
3.3.1	Kodierung und Dekodierung zyklischer Codes	49
3.3.2	Realisierung der Kodierung mittels Schieberegister	51
3.4	Vergleich RS und BCH-Codes	53
3.5	BCH-Codes	56
3.5.1	Mathematische Grundlagen für BCH-Codes	57
3.5.2	Kodierung von BCH-Codes	59
3.5.3	Dekodierung von BCH-Codes	60
3.6	Faltungscodes	63
3.6.1	Kodierung und Dekodierung von Faltungscodes	63
3.6.2	Unterschied zwischen Blockcodes und Faltungscodes	68
3.7	Kanalkodierverfahren bei Bluetooth	69
3.8	Bewertung der verschiedenen Kodierverfahren	73
4.	Simulation und Bewertung	76
4.1	Mikrocontroller und Bewertung des Rechenaufwands	76
4.1.1	Allgemeines und Aufbau eines Mikrocontrollers	76
4.1.2	Mikrocontroller MSP430 von Texas Instruments	78
4.2	Das (15,11)-Hamming Programm	79
4.3	Das (48,36)-BCH Programm	82
4.4	Simulation und Ergebnis	85
4.5	Implementierung in den MSP430	91
5.	Zusammenfassung und Ausblick	93
	Literaturverzeichnis	95
	Symbolverzeichnis	96
	Abbildungsverzeichnis	97
	Tabellenverzeichnis	98
	Anhang A Tabelle zur Erstellung von Hamming-Codes	100
	Anhang B Simulationsergebnis in Fehlerraten	100
	Anhang C Simulationsergebnis in Absolutfehler	102
	Anhang D Grafische Simulationsergebnisse	104
	Anhang E Quellcode des (15,11)-Hamming-Codes	105
	Anhang F Quellcode des (48,36) – BCH-Code	110
	Anhang G Quellcode des BCH für den MSP430	118

Textprobe:

Kapitel 3.2, Blockcodes:

Diese Art der Kanalkodierung kennzeichnet sich dadurch aus, dass die benutzten Codewörter alle dieselbe Länge haben. Handelt es sich um systematische Blockcodes, können die Symbole in Informationsbits und Prüfbits unterteilt werden. Zusätzlich zur Information werden noch redundante Information eingefügt, die die Fehlererkennung und -korrektur ermöglichen. Beispiele für Blockcodes sind der Hamming-Code, der Wiederholungscode sowie alle zyklischen Codes, die eine wichtige Unterklasse darstellen.

3.2.1, Hamming-Code:

Der Hamming-Code ist nach seinem Erfinder Richard Hamming benannt worden und ist ein linearer Fehler korrigierender Blockcode.

Hamming wollte mit diesem Code die Hammingdistanz und die Coderate so hoch wie möglich halten. Das entscheidend Neue an seinem Code ist die Überlappung der Paritätbits, die somit nicht mehr nur zur Prüfung der Daten dienen, sondern sich auch gegenseitig überprüfen.

Es gilt: Für jede Zahl m>2, wobei m aus den natürlichen Zahlen stammt, existiert ein Einzelfehler korrigierender, binärer (n,k)-Code, mit den Parametern:

Länge: n = 2m-1.

Dimension: k = n-m.

Mindestdistanz: d=3.

Der Code ordnet jedem empfangenen Codewort ein Datenwort zu und ist somit perfekt. Gängige Hamming-Codes sind z.B. (7,4), (15,11), (31,26), (63,57) und (127,120). Der minimale Abstand der einzelnen Codewörter voneinander ist drei. Dadurch kann der Dekoder einen Bitfehler in einem Datenblock immer erkennen und korrigieren. Bei zwei oder mehreren Fehlern wird der Datenblock allerdings falsch dekodiert.

Einer dieser Codes ist der (8,4)-Hamming-Code mit einem Minimalabstand von 3. Er kann also entweder 2 Fehler erkennen oder einen Fehler pro Datenblock korrigieren. Soll der Code Fehler korrigieren, und treten zwei oder mehr Fehler auf, wird falsch dekodiert. Der (8,4)-Code entspricht dem (7,4)-Code, mit der Ausnahme, dass ein weiteres redundantes Bit angefügt wird. Dadurch kommt man auf die Länge von genau einem Byte. Die achte Stelle zeigt einen nur ein an dieser Stelle aufgetretenen Fehler an.

Es ist praktisch über jede Binärdarstellung die Spaltennummer zu schreiben, also 1, 2, …, n. Beim Dekodieren zeigt der Syndromvektor S dann direkt die Fehlerstelle an.