Untersuchung von Kanalkodierverfahren für den Einsatz in drahtlosen Sensornetzwerken

Inhaltsverzeichnis

1 Einführung
1.1 Einleitung und Zielsetzung
1.2 Aufgabe der Kanalkodierung
1.3 Abgrenzung der Kanalcodes von anderen Kodierungsarten

2 Grundlagen
2.1 Grundbegriffe
2.1.1 Hammingdistanz
2.1.2 Hamminggewicht
2.1.3 Kanalkapazität
2.1.4 Perfekter Code
2.1.5 Coderate
2.1.6 Systematischer Code
2.1.7 Lineare Codes
2.1.8 Theorem der Kanalkodierung
2.2 Störungen des Funkkanals und Fehlerarten
2.3 Übersicht verschiedener Kanalkodierungs-Codes
2.4 Wiederholungscode
2.5 Paritätbits
2.6 Automatic Repeat Request
2.7 Interleaving

3 Kanalkodierungsverfahren
3.1 Zyklische Redundanzprüfung
3.1.1 Algorithmus zur Berechnung des CRC-Prüfwerts
3.1.2 Algorithmus zur Dekodierung von CRC-Codes
3.2 Blockcodes
3.2.1 Hamming-Code
3.2.2 Shortened Hamming-Code
3.3 Zyklische Codes
3.3.1 Kodierung und Dekodierung zyklischer Codes
3.3.2 Realisierung der Kodierung mittels Schieberegister
3.4 Vergleich RS und BCH-Codes
3.5 BCH-Codes
3.5.1 Mathematische Grundlagen für BCH-Codes
3.5.2 Kodierung von BCH-Codes
3.5.3 Dekodierung von BCH-Codes
3.6 Faltungscodes
3.6.1 Kodierung und Dekodierung von Faltungscodes
3.6.2 Unterschied zwischen Blockcodes und Faltungscodes
3.7 Kanalkodierverfahren bei Bluetooth
3.8 Bewertung der verschiedenen Kodierverfahren

4 Simulation und Bewertung
4.1 Mikrocontroller und Bewertung des Rechenaufwands
4.1.1 Allgemeines und Aufbau eines Mikrocontrollers
4.1.2 Mikrocontroller MSP430 von Texas Instruments
4.2 Das (15,11)-Hamming Programm
4.3 Das (48,36)-BCH Programm
4.4 Simulation und Ergebnis
4.5 Implementierung in den MSP430

5 Zusammenfassung und Ausblick

Literaturverzeichnis

Symbolverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Anhang A Tabelle zur Erstellung von Hamming-Codes

Anhang B Simulationsergebnis in Fehlerraten

Anhang C Simulationsergebnis in Absolutfehler

Anhang D Grafische Simulationsergebnisse

Anhang E Quellcode des (15,11)-Hamming-Codes

Anhang F Quellcode des (48,36) – BCH-Code

Anhang G Quellcode des BCH für den MSP430

Anhang H CD mit erstellten Programmen 120

1 Einführung

1.1 Einleitung und Zielsetzung

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.

Der Aufbau des Sensor-/Aktor‑Moduls und mehr Informationen zum EnAS-Projekt in [KÖR-07].

1.2 Aufgabe der Kanalkodierung

Aufgabe der Kanalkodierung ist es eine fehlerfreie Kommunikation über einen Kanal, der die Nachricht verfälscht, zu gewährleisten. Man könnte dies über eine Kanalverbesserung erreichen, indem man z.B. höherwertige Kabel oder Bauteile verwendet. Das ist meistens mit hohen Kosten verbunden, die in keinem Verhältnis zu den Verbesserungen stehen. Außerdem sind damit Fehler noch nicht vollkommen ausgeschlossen. In dieser Arbeit geht es um den drahtlosen Einsatz und damit, im Gegensatz zum drahtgebundenen Kanal, fehleranfälligeren Funkkanal. Benutzt wird das 2,4 GHz ISM‑Band, welches ein lizenzfreies Senden ermöglicht.

Erst die Kanalkodierung vermag beim Design von Übertragungs- und Speichersystemen die Anforderungen an hohe Zuverlässigkeit zu erfüllen und ist damit ein integraler Bestandteil der modernen Kommunikationstechnik.

Das Prinzip beruht darauf, dass der Kanalkodierer der Nachricht zusätzliche Informationen hinzufügt. Diese Redundanzen werden am anderen Ende des Kanals dazu verwendet bei der Übertragung aufgetretene Fehler zu erkennen und wenn möglich zu korrigieren. Die Abbildung 1.1 verdeutlicht den Aufbau einer typischen Nachrichtenstrecke. Ausgehend von einer Quelle wird der Nachricht Redundanz hinzugefügt und das Signal moduliert. Nun kann es zu Übertragungsfehlern kommen, die nach der Demodulation korrigiert werden können, damit die Senke die ursprüngliche Nachricht erhält. Welche zusätzlichen Daten angehängt werden und wie groß diese Daten sind entscheidet der zur Kodierung verwendete Code.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1 Aufbau einer Nachrichtenstrecke

Wenn der Sender die Daten vor der Übertragung in redundanter Weise kodiert, wird dieses Verfahren als Vorwärtsfehlerkorrektur, auf Englisch Forward Error Correction kurz FEC, genannt.

Die Codes können danach charakterisiert werden, wie viele Informationen sie der eigentlichen Nachricht hinzufügen und wie viele Fehler sie erkennen und korrigieren können.

Bei der Implementierung in der Praxis spielt auch der Aufwand, der beim Kodieren und Dekodieren entsteht, eine wichtige Rolle.

Die Sicherung von Nachrichten durch Kanalkodierung erlangt besondere Bedeutung, wenn stark gestörte Übertragungskanäle vorliegen, wenig Sendeleistung zur Verfügung steht oder extrem niedrige Fehlerraten erreicht werden müssen.

1.3 Abgrenzung der Kanalcodes von anderen Kodierungsarten

Die Tabelle 1.1 zeigt andere Kodierungsarten und nennt beispielhaft einige dazugehörige Vertreter.

Tabelle 1.1 Kodierungsarten

Abbildung in dieser Leseprobe nicht enthalten

Die gelisteten Kodierungsarten besitzen grundverschiedene Aufgaben. Bei der Quellenkodierung werden Quellcodes verwendet, die zur Datenkompression genutzt werden, um die natürliche Redundanz eines Nachrichtensignals zu verkleinern. Ein Beispiel für Redundanz in der deutschen Sprache ist das U hinter einem Q, denn dieses ist dort immer vorhanden. Das Wissen, dass der Buchstabe Q vorhanden ist, reicht also aus, um dahinter ein U zu setzen, auch wenn es nicht mitgesendet wurde.

Es gibt zum einen die verlustfreie Kompression, wenn die Daten nach der Anwendung der Dekodiervorschrift exakt gleich denen des Originals entsprechen. Hier werden häufig zu kodierende Wörter kurze Codewörter zugeordnet und selten vorkommenden Wörtern längere Codewörter. Das wird auch als Redundanzreduktion bezeichnet.

Zum anderen gibt es die verlustbehaftete Kompression, welche sich nicht fehlerfrei rekonstruieren lässt. Zum Beispiel können bei Musikstücken Frequenzanteile weggelassen werden, die für den Menschen nicht hörbar sind.

Codes zur Verschlüsselung stellen in der Regel eine geschickte Verwürfelung, eine Umkodierung, der Nachricht dar, sodass ein Abhören der Nachricht nur möglich ist, wenn der Code zur Entschlüsselung bekannt ist. Eine Erhöhung der Redundanz findet dabei nicht statt. Ziel ist es, die Nachrichten für Unbefugte unlesbar zu machen, um zu verhindern, dass Nachrichten gefälscht, abgehört oder vorgetäuscht werden.

Bei der Kanalkodierung gibt es Fehler korrigierende und Fehler erkennende Codes, die der Nachricht Redundanz hinzufügen, damit der Empfänger in der Lage ist, die Fehler zu korrigieren bzw. zu erkennen, die bei der Übertragung aufgetreten sind. Somit können Nachrichten von einer Quelle zu einer Senke mit einem Minimum an Fehlern übertragen werden und eine extrem hohe Zuverlässigkeit gewähren. Kanalcodes sind das Hauptthema dieser Studienarbeit. Nebenbei sei erwähnt, dass die Internationalen Standardbuchnummern ISBN, die Personalausweisnummer und sogar die Personenkennziffern deutscher Soldaten durch Fehler erkennende Codes erzeugt werden. Bei der Personenkennziffer stellt die letzte Zahl einen Prüfwert dar, den man über einen Schlüssel berechnen kann. Bei einer ISBN-Nummer kann durch die letzte Stelle bestimmt werden, ob eine Zahl vergessen wurde, oder ob zwei benachbarte Zahlen vertauscht wurden.

Die Codes, die zur spektralen Formung verwendet werden, sind die sogenannten Leitungscodes. Sie nehmen in Kombination mit dem Modulationsverfahren Einfluss auf die Form des Spektrums des Signals, um bestimmte Eigenschaften wie z.B. Gleichstromfreiheit oder Taktrückgewinnung zu erreichen.

2 Grundlagen

2.1 Grundbegriffe

Für die Beschreibung der Codes verwendet man verschiedene Begriffe, die nun erläutert werden. Für weitere Begriffe der Kanalkodierung und der Darstellung linearer Codes als Matrizen siehe [KLI-03].

2.1.1 Hammingdistanz

Die Hammingdistanz oder auch Hammingabstand, dargestellt durch das Symbol d, ist ein Maß für die Unterschiedlichkeit zweier Codewörter. Ermittelt wird sie, indem man die Codewörter Bit für Bit vergleicht und die Stellen zählt, an denen sie sich unterscheiden.

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Die unterstrichenen Stellen sind unterschiedlich. Der Hammingabstand von Codewort A und B ist also d=3.

Die Tabelle 2.1 zeigt die Fähigkeiten von Codes bis zum Hammingabstand von fünf und verdeutlicht, dass die Fehlererkennungs- und Fehlerkorrigierfähigkeit vom minimalen Hammingabstand dmin abhängt. Dabei ist dmin der kleinste vorkommende Hammingabstand in einem Code.

Unterscheiden sich Codewörter nur um 1 Bit, so ist keine Fehlererkennung möglich, weil ein verfälschtes Bit bereits ein anderes gültiges Codewort erzeugt. Je größer der Hammingabstand, desto größer sind die Fehlererkennungs- und Korrekturmöglichkeiten. Die Redundanz des Codes steigt jedoch.

Tabelle 2.1 Minimaler Hammingabstand

Abbildung in dieser Leseprobe nicht enthalten

2.1.2 Hamminggewicht

Das Hamminggewicht ist der Hammingabstand zum Nullwort. Er entspricht der Anzahl der gesetzten Bits und ist, sozusagen, einfach die Quersumme des Codewortes.

Die Formel, um das Hamminggewicht Wt zu berechnen, lautet:

Abbildung in dieser Leseprobe nicht enthalten

mit Wt(cj) = 0, falls cj = 0

und Wt(cj) = 1 ,falls cj = 1.

Wobei ein Codewort c = (c0, c1, …, cn-1) aus n Stellen besteht.

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Das Hamminggewicht von A ist somit 4 und von B ist es 5.

Die Hammingdistanz eines ganzen Codes entspricht dem Minimum aller Abstände der Codewörter untereinander. Ist der Code linear, so ist die Hammingdistanz gleich dem Hamminggewicht.

Grundsätzlich gilt, je größer der Hammingabstand eines Codes ist, desto mehr Fehler kann der Code erkennen und korrigieren. Man kann sich die Fehlerkorrekturfähigkeit t zum besseren Verständnis einfach als Radius um ein Codewort vorstellen und alle verfälschten Codewörter, die innerhalb des Kreises mit diesem Radius liegen, können korrigiert werden. Ein Wort außerhalb des Kreises kann man zwar als fehlerhaft erkennen, es jedoch nicht korrigieren.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1 Veranschaulichung der Korrekturfähigkeit, aus [BOS-91]

Erklärung zur Abbildung 2.1:

Massive Punkte stellen gültige Codewörter dar und transparente Punkte repräsentieren korrigierbare Empfangsworte. X beschreibt ein nicht korrigierbares Wort. Es hat den gleichen Abstand zu beiden Codewörter und somit wäre eine Zuordnung rein zufällig.

Beim oberen Teilbild ist dmin = 4 und damit die Fehlerkorrigierbarkeit t = 2 und die Fehlererkennungsanzahl 3.

Im unteren Teil ist dmin = 5 und t ebenfalls 2. Allerdings können hier bis zu 4 Fehler erkannt werden.

Der Zusammenhang zwischen der Hammingdistanz d und der Anzahl korrigierbarer Fehler t ist folgender:

Abbildung in dieser Leseprobe nicht enthalten

Die Gauß-Klammer bedeutet, dass der in der Klammer errechnete Wert auf die nächste ganze Zahl abgerundet wird. Ist z.B. d = 6 folgt t = 2.

Der Zusammenhang zwischen erkennbaren Fehlern t’ und der Hammingdistanz ist:

Abbildung in dieser Leseprobe nicht enthalten

Codes werden häufig mit (n,k,d)-Code bezeichnet. Hierbei ist n die Länge der kodierten Nachricht, k die Länge der ursprünglichen Nachricht und d der Minimalabstand des Codes. Hier wird die etwas kürze Bezeichnung (n,k) gewählt.

2.1.3 Kanalkapazität

Die Kanalkapazität C ist ein Maß für die Menge an Informationen, die fehlerfrei über einen Kanal übertragen werden kann. Die Abbildung 2.2 zeigt einen binären symmetrischen Kanal. Die Annahme für den Kanal ist, dass es sich um einen diskreten, gedächtnislosen Kanal handelt. Das bedeutet, es gibt eine feste Wahrscheinlichkeit p, dass ein bestimmtes Zeichen gesendet und ein anderes empfangen wurde. Die Wahrscheinlichkeit, dass eine 0 gesendet wurde und eine 1 empfangen wird, ist also p und die Wahrscheinlichkeit das richtige Symbol zu empfangen 1-p.

Die Wahrscheinlichkeit p liegt zwischen 0 und 1 und ist unabhängig von den zuvor gesendeten Symbolen. Ein guter Kanal hat somit einen sehr kleinen p-Wert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2 Binärer symmetrischer Kanal

In der Regel ist die Kanalkapazität C schwer zu bestimmen. Für den binären symmetrischen Kanal lässt sich C jedoch explizit angeben:

Abbildung in dieser Leseprobe nicht enthalten

Treten in einem Kanal keine Fehler auf, gilt p = 0 und somit ist C = 1. Es ist also ein ungestörter Kanal und jedes Symbol kommt unverfälscht an. Für p = 1 wird jedes Symbol umgekehrt und C ist ebenfalls 1, da es keinen Zufall in den Vertauschungen gibt.

Für p = 0,5 ist C = 0 und somit ist der Wert am Ausgang des Kanals absolut zufällig. Die Einheit der Kanalkapazität ist: Abbildung in dieser Leseprobe nicht enthalten

2.1.4 Perfekter Code

Ein perfekter Code kann jedem empfangenen Wort eindeutig ein Codewort zuordnen. Wenn die Anzahl der Fehler jedoch die Anzahl der korrigierbaren Fehler überschreitet, kommt es gezwungenermaßen zu einer Fehlzuordnung. Zu den perfekten Codes gehören alle Wiederholungscodes ungerader Länge, die Einzelfehler korrigierenden Hamming-Codes und der Golay-Code. Das Attribut perfekt ist dabei neutral zu werten, denn ein nicht-perfekter Code ist unter Umständen in der Lage zu erkennen, dass seine Fehlerkorrekturfähigkeit überschritten wurde und vermeidet so Fehlzuordnungen von Codewörtern.

Die Abbildung 2.1 zeigt im oberen Teil einen nicht-perfekten Code, weil es ein ungültiges Codewort X gibt, welches keinem gültigen Codewort zugeordnet werden kann. Im unteren Teil ist immer eine Zuordnung möglich, deshalb handelt es sich um einen perfekten Code.

2.1.5 Coderate

Die Coderate R gibt das Verhältnis der Blocklänge vor und nach dem Kodieren an. Hat die Nachricht vor dem Kodieren die Länge k und nach dem Kodieren die Länge n so ist die Coderate:

Abbildung in dieser Leseprobe nicht enthalten

R ist ein Maß für die vom Kodierer zugefügte Redundanz. Je kleiner R ist, desto größer die Redundanz. Es gilt stets k ≤ n und deshalb R ≤ 1.

Statt des Begriffs Coderate wird auch der Begriff Übertragungsrate verwendet, der jedoch oft verstanden wird als Datenmenge pro Zeiteinheit und damit missverständlich ist.

Die Coderate ist ebenfalls ein Maß für die Ausnutzung des Speicherplatzes, weil eine hohe Coderate nur geringe Redundanz aufweist und damit wenig Speicherplatz verbraucht.

2.1.6 Systematischer Code

Bei einem systematischen Code kann das gesendete Codewort direkt abgelesen werden. Nach dem Kodiervorgang sind die n Symbole umfassenden Codewörter aus einem Block von k Symbolen unveränderter Information und einem zusammenhängenden Block von n-k Redundanzsymbolen zusammengesetzt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3 Aufbau systematischer Codes

Ein Beispiel dafür ist die zyklische Redundanzprüfung CRC und die systematischen zyklischen Codes. Alle Codes, die diese Eigenschaft nicht erfüllen, werden unsystematisch genannt.

Systematische Codes werden in der Praxis bevorzugt, weil nach einer fehlerfreien Übertragung ohne weitere Rechnung die Informationen abgelesen werden können. Da bekannt ist, an welchen Stellen die Informationen liegen, können diese nach einer vorzeitig abgebrochenen Übertragung ausgelesen werden. Beispiele für eine solche Situation sind in etwa der vorzeitig abgebrochene Empfang bei einer Übertragung oder ein Lesefehler von der Festplatte. Auf diese Weise lassen sich unter Umständen noch Teile der Daten rekonstruieren, ohne Fehler, die sich schon darin befinden mögen, durch zusätzliche Verarbeitungsschritte zu vermehren.

Unwichtig ist, an welcher Stelle sich die Informationen befinden. Es können natürlich auch anders als in der Abbildung 2.3 dargestellt die Prüfstellen links und die Informationen rechts stehen. Die Informationsstellen müssen aber bekannt sein.

Bei nicht-systematischen Codes ist die Nachricht nicht im Codewort zu erkennen. Es gibt keine festen Positionen für Daten- und Prüfbits. Nach einer Fehlerkorrektur ist ein weiterer Verarbeitungsschritt nötig, um die Informationen zu erhalten.

2.1.7 Lineare Codes

Ein Code heißt linear, wenn jede Linearkombination zweier beliebiger Codewörter A und B eines Codes wieder ein gültiges Codewort ergibt. Anders ausgedrückt: Ein Code ist linear, wenn mit zwei Codewörtern A und B, die Rechenoperation A Abbildung in dieser Leseprobe nicht enthaltenB wieder ein Codewort ergibt. Das Nullwort ist in jedem linearen Code vorhanden, da die Addition eines Codeworts mit sich selbst das Nullwort ergibt.

Die Hamming-, BCH-, RS- und Faltungscodes gehören zu dieser Klasse. Nicht-lineare Codes haben weniger Struktur und ihre Dekodierung ist schwieriger als bei linearen Codes. Vertreter der nicht-linearen Codes sind der Nordstrom-Robinson-Code, der Kerdock-Code und der Preparata-Code. [BOS-91]

2.1.8 Theorem der Kanalkodierung

Das Theorem der Kanalkodierung war ein Ergebnis in Claude Shannons Arbeit über die Informationstheorie. Sie besagt, wenn Informationen über einen Kanal der Kapazität C mit einer Coderate von R übertragen werden und die Rate R kleiner als die Kapazität C ist, so ist es möglich, die Informationen mit beliebiger Zuverlässigkeit zu übertragen. Dabei bedient er sich langer Fehler korrigierender Codes. Wählt man n groß genug, so erreicht man praktisch eine fehlerfreie Übertragung. Ist jedoch die Coderate größer als die Kapazität ist dies nicht mehr möglich und es treten Störungen auf. Die Kanaleigenschaften begrenzen also nicht die Qualität der Übertragung, sondern nur den Durchsatz.

Im Anschluss an seine Arbeit entwickelten sich rasch und in großer Anzahl mathematische Theorien Fehler erkennender und Fehler korrigierender Codes.

2.2 Störungen des Funkkanals und Fehlerarten

Die Kanalkodierung soll bewirken, dass gestörte Nachrichten korrekt wiedergeben werden können. Die Störungen des Kanals können jedoch in unterschiedlicher Weise auftreten und sind für die Wahl des Codes ein sehr wichtiger Faktor. Deshalb ist eine Untersuchung des Störverhaltens der Übertragungskanäle von grundlegender Bedeutung.

Allgemein lässt sich sagen, dass Funkkanäle deutlich anfälliger als drahtgebundene Kanäle sind. Dies liegt auch an den Störeinflüssen anderer Teilnehmer in Funkzellen.

Im Wesentlichen lassen sich die Störungen eines Funkkanals in zwei Bereiche unterteilen. Dies sind zum einen durch den Funkkanal selbst bedingte und zum anderen durch Störer bedingte Fehler. Aufgrund der unterschiedlichen Störarten muss beim Funkkanal eine Unterteilung in schmal- und breitbandige Kanäle vorgenommen werden. Ein Kanal wird als breitbandig bezeichnet, wenn die Sendebandbreite größer als die Kohärenzbandbreite ist. Andernfalls ist er schmalbandig. Die statistische Größe Kohärenzbandbreite gibt die Frequenzspanne an, innerhalb derer die Kanalübertragungsfunktion einen konstanten Amplitudengang aufweist. Bei einem breitbandigen Kanal können als Folge von Reflexionen, bei denen die Signale unterschiedliche Ausbreitungswege zwischen Sender und Empfänger nutzen und mit unterschiedlicher Laufzeit ankommen, Intersymbolinterferenzen erzeugt werden, jedoch nicht bei einem schmalbandigen.

Das verwendete ISM-Band (I ndustrial, S cientific, and M edical Band) liegt bei 2,4GHz und es wird eine Übertragungsbandbreite von ca. 1 MHz genutzt. Somit liegt ein schmalbandiges System vor. Bei schmalbandigen Kanälen werden statische und dynamische Kanäle unterschieden. Statische, zeitinvariante Kanäle werden durch eine Übertragungsfunktion gekennzeichnet. Die Fehlerrate ist abhängig von der gewählten Frequenz, da bei bestimmten Frequenzen der Kanalabschnitt schlecht sein kann. Dies zeigen tiefe Amplitudengänge in der Übertragungsfunktion, die als Schwundeffekt bezeichnet werden. Es sind etwa 80 Kanäle wählbar, die unterschiedliche Amplituden in der Übertragungsfunktion aufweisen. Ist die Amplitude zu gering, wird das Signal zu stark gedämpft und es kann kein Signal mehr empfangen werden. Bei der Grenze von -87 dBm des CC2400-Transveivers ist die Bitfehlerrate 10-3. [DAT-06] Bewegt sich der Empfänger relativ zum Sender, kommt es zu Interferenzen der elektromagnetischen Wellen, die konstruktiv, also verstärkend, oder destruktiv wirken können.

Dynamische Kanäle sind zeitvariant und somit kann man sich nicht auf eine Frequenz bei der Datenübertragung festlegen. Bei einer gewählten Frequenz ist der Kanal zeitabhängig und verschlechtert sich zu bestimmten Zeiten durch äußere Einflüsse. Durch Frequenzwechselverfahren wird erreicht, dass ein guter Kanalabschnitt genutzt wird.

Störer sind andere Systeme, die ebenfalls drahtlos kommunizieren und sich dabei, abhängig vom Signal-zu-Rausch-Abstand und der Frequenzdifferenz, überlagern.

Das hier betrachtete Funknetz ist ein dynamischer Indoor-Funkkanal. Es wird durch unterschiedliche Mechanismen beeinflusst:

- Dämpfung durch Wände
- Reflexionen und Beugung an Wänden und Gegenständen
- Bewegungen von Personen und Gegenständen

Es werden Geschwindigkeiten von maximal 5 m/s durch sich bewegende Fertigungsteile und agierende Fertigungsmaschinen erreicht. Diese relativ langsame Geschwindigkeit führt zu Abschattungen. Die Dämpfung liegt dann unterhalb der Empfindlichkeit des Empfängers und führt zu sehr langen Burstfehlern. Bei einem Burstfehler, auch Bündelfehler genannt, sind mehrere Bits hintereinander fehlerhaft. Es wird also eine Kette gleicher Symbole empfangen.

Eine erste Auswertung von typischen Fehlerbitströmen mit externen Störquellen an einem Modell der Fertigungsstrecke hat gezeigt, dass Burstfehler seltener als Einzelfehler auftreten. Tauchen Burstfehler auf, sind diese oft länger als das gesamte Codewort und damit unkorrigierbar.

Bei statistischen Einzelfehlern ist die Wahrscheinlichkeit für einen Fehler nicht vom Auftreten früherer Fehler abhängig, sondern nur von der Stärke des Rauschens. Daher ist eine gleichmäßige Verteilung der Fehler in gleich langen Zeitintervallen zu erwarten. Diese Fehlerart ließe sich durch eine Erhöhung der Sendeleistung unterdrücken. Dies ist jedoch, aufgrund der begrenzten Verfügbarkeit von Energie, nicht immer möglich.

Die tolerierbare Restbitfehlerwahrscheinlichkeit hängt von den zu übertragenden

Daten ab. Unkomprimierte, digitalisierte Sprache ist auch noch bei einer Bitfehlerrate von 10-3 verständlich, bei einem Computerprogramm dagegen kann schon ein einziges fehlerhaftes Bit zu Fehlfunktionen führen.

Die Festlegung eines Kodierungsverfahren berücksichtigt sowohl die Qualitätsansprüche an das zu übertragende Signal als auch die Eigenschaften des Kanals.

Da auftretende Bündelfehler die Korrekturfähigkeit übersteigen, ist die Kodierungsart für statistische Einzelfehler auszulegen.

2.3 Übersicht verschiedener Kanalkodierungs-Codes

Mittlerweile gibt es eine Vielzahl an unterschiedlichen Kanalkodierverfahren, die man kaum noch alle aufzählen kann. Die folgende Übersicht soll die Hauptkategorien und die Einteilung der unterschiedlichen Codes verdeutlichen. Man erkennt, dass zwei Hauptklassen unterschieden werden: Die Block- und die Faltungscodes. Bei den Blockcodes bilden die zyklischen Codes eine wichtige Unterklasse. In der Literatur werden Blockcodes auch als Gruppencodes und Faltungscodes auch als konvolutionelle Codes bezeichnet.

Produkt-Codes wenden auf einen Informationsblock nicht nur eine Kodierung, sondern mehrere, im einfachsten Fall zwei, an. Verwendet man mehrere Kanalcodes parallel, spricht man auch von einer Codeverkettung. Die dabei verwendeten Verfahren können sowohl Block- als auch Faltungscodes sein.

Werden parallel verkettete Faltungscode genutzt, spricht man von Turbo-Codes.

Weitere Codes, wie den Goppa-Code, sind in [DAN-06] nachzulesen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4 Einteilung von Kanalkodierverfahren

2.4 Wiederholungscode

Anhand des einfach aufgebauten Wiederholungscode, der auch heutzutage noch Anwendung findet, wird das Prinzip der Kanalkodierung erläutert.

Der Aufbau des Codes ist sehr simpel. Jedes Bit, das über den Kanal gesendet werden soll, wird n-mal wiederholt. Als Beispiel wird der n=3 Wiederholungscode verwendet. Das bedeutet, jedes Bit wird 3-mal wiederholt. Es ist ein (3,1)-Code, da die Länge der kodierten Nachricht 3 ist und vor dem kodieren 1 war. Die Coderate ist somit R = k/n = 1/3. Der Hammingabstand beträgt 3. Bluetooth verwendet diesen (3,1)-Wiederholungscode als Kanalkodierung. Die beiden verwendeten Codewörter sind 000, das sogenannte Nullwort, welches die 0 repräsentiert, und die 111, welches die 1 kodiert darstellt und auch Alleinsenwort genannt wird.

Beispiel: Nachricht ist 1 0 0 0 1 1 0

Der Kodierer macht daraus das Codewort v = 111 000 000 000 111 111 000

Der Dekodierer bekommt v zugesendet und kann daraus nun die ursprüngliche Nachricht rekonstruieren. Dazu nimmt er immer drei Bits und macht aus der Folge 111 eine 1 und aus der Folge 000 eine 0. Es entsteht wieder die ursprüngliche Nachricht: 1 0 0 0 1 1 0.

Wenn nun ein Fehler bei der Übertragung aufgetreten ist, kann es passieren, dass einzelne Bits gekippt werden. Dies ist an den unterstrichenen Stellen passiert.

Angekommene Nachricht: 111 0 1 0 000 000 11 0 111 1 00

Der Empfänger weiß, dass drei aufeinander folgende Bits dasselbe Symbol enthalten müssten und kann nun die Fehler korrigieren, indem er das Symbol auswählt, welches am wahrscheinlichsten gesendet wurde. Dies ist immer das Symbol mit dem geringsten Hammingabstand zum empfangenen Symbol. Aus dem zweiten Block 010 macht er nun 000, aus dem fünften Block 111 und aus dem siebten Block 000. Dies lässt sich auch in einer Tabelle darstellen, wobei links die möglichen empfangenen Wörter enthalten sind und rechts die entsprechende Zuordnung ist.

Tabelle 2.2 Dekodierung des Wiederholungscodes

Abbildung in dieser Leseprobe nicht enthalten

Die Nachricht kann also vollständig wiederhergestellt werden. Hier sieht man jedoch auch die Abhängigkeit von Codes von der Fehlerstruktur. Denn es kann nur ein Fehler pro Block korrigiert werden. Treten mehrere Fehler auf, wird falsch dekodiert. Wird 111 gesendet und durch zwei Fehler 1 00 empfangen, wird daraus fälschlicherweise eine 0 interpretiert, da der Hammingabstand zum Nullwort kleiner ist.

Die Tabelle 2.3 zeigt den Ablauf bei einer fehlerhaften Übertragung anhand des bereits eingeführten Beispiels.

Tabelle 2.3 Wiederholungscode

Abbildung in dieser Leseprobe nicht enthalten

Um mehr Fehler zu korrigieren, könnte man die Bits häufiger wiederholen. Bei fünfmaliger Wiederholung kann man pro Block 2 Fehler korrigieren. Der Nachteil dabei ist, dass der Code sehr groß wird bei gleich viel gesendeten Informationen. Andere Codes sind wesentlich effizienter.

Der (2,1)-Wiederholungscode ist ein Fehler erkennender Code und kein Fehler korrigierender Code. Wenn in einem Block ein Bit gekippt wird, kann nicht daraus geschlossen werden, ob er eine 1 oder eine 0 repräsentiert. Dennoch ist die fehlerhafte Übertragung erkannt worden, solange es sich um 1-Bit-Fehler handelt.

2.5 Paritätbits

Ein einfaches Mittel zur Erkennung von Fehlern bei der Übertragung von Wörtern ist das Anhängen eines Paritätbits. Soll z.B. das Codewort immer „gerade“ sein, wird das Paritätbit immer so angehängt, dass die Anzahl der Einsen in einem Codewort gerade ist. Wird ein Wort mit ungerader Parität empfangen, so muss bei der Übertragung ein Fehler aufgetreten sein, also eine Verfälschung eines einzelnen Bits. Der Fehler wird auf diese Weise erkannt. Es ist jedoch keine Fehlerkorrektur möglich, da unbekannt ist, wo der Fehler auftrat.

Wird dagegen ein Wort mit gerader Parität empfangen, so sind zwei Fälle möglich: Entweder es handelt sich um ein fehlerfrei übertragendes Codewort oder es ist ein Fehler aufgetreten, der aber die Parität nicht verändert hat und somit nicht detektiert wird. Dies passiert, wenn eine gerade Anzahl von Bits verfälscht wird.

Unter der Annahme, dass Fehler mit einer geraden bzw. ungeraden Anzahl von verfälschten Bits gleich wahrscheinlich sind, werden im Mittel durch diese Art der Kodierung 50 % aller Fehler erkannt, und zwar die, mit ungerader Anzahl von verfälschten Bits. Das Problem dieses Verfahrens ist die Unfähigkeit mehrere Fehler zu erkennen. Durch Anhängen von mehr als nur einem Prüfbit, lässt sich die Fehlererkennungsrate drastisch steigern. Das Verfahren wird kaum noch eingesetzt, stattdessen wird das leistungsfähigere CRC-Verfahren genutzt.

Beispiel für die Anwendung eines Paritätbits beim Parity-Check-Code

Gegeben sei ein Codewort c = (co,c1,c2,..., cn-1) der Länge n. Man wählt die ersten n-2 Stellen als die n-2 Informationszeichen i0,i1,...,in-2 aus und berechnet die letzte Stelle nach der Formel: cn-1 = Abbildung in dieser Leseprobe nicht enthalten

Was wörtlich gesprochen bedeutet: Die Anzahl der gesetzten Bits ist gerade. Denn ist die Anzahl der Einsen bereits gerade, ergibt die Modulo 2 Operation eine 0, andernfalls eine 1.

Für einen Code der Länge n=3 ergeben sich die Codewörter nach Tabelle 2.4.

Tabelle 2.4 Codewörter des (3,2)-Parity-Check-Codes

Abbildung in dieser Leseprobe nicht enthalten

[...]