Informatik: Optimierung der Codierung im TDMA-Protokoll
Released by matroid on Fr. 04. September 2009 18:06:41 [Statistics]
Written by wkleff - 2852 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\)

Ein Beitrag zur Kanalcodierungstheorie

Worum geht es (Langfassung) - Es wird für jede Struktur in einem TDMA-Protokoll, der jeweils kleinste CRC-Code gesucht, der im ARQ-Verfahren eine noch gerade ausreichende Verbesserung der Fehlerrate bringt - Fall (S). Dabei wird auf eine Erhöhung der Coderate abzielt. Diese Codes verbessern die Restfehlerrate bei großen Strukturen aber erst dann ausreichend, wenn die Bitfehlerrate sehr klein ist. Zudem geht der Datendurchsatz bei einem sehr schlechten Kanal schnell gegen 0.

Aus diesem Grund wurde noch die Codierung jedes Timeslots untersucht. Dieser Ansatz verbessert zwar den Durchsatz bei einem schlechten Kanal, dies aber bei einer schlechten Coderate - Fall (T).

Kurzfassung - Es geht um mehr Netto vom Brutto bei vergleichbarer Sicherheit der
Datenübertragung. Genau dies leisten die im Fall(S) für die einzelnen Strukturen gefundenen primitiven Polynome.

Anmerkung und Dank - Dieser Beitrag steigt ohne Vorwarnung in die Theorie ein, denn um die Zulässigkeit der gezogenen Schlüsse zu untermauern, müssen einige Erkenntnisse (Sätze) aus der Kanalcodierungstheorie zitiert werden. In diesem Zusammenhang möchte ich meiner Frau (Dipl.-Math.) danken, die bereits bei der Literaturrecherche half und zuletzt meine Schlussfolgerungen noch einmal überprüft hat.



Das TDMA-Protokoll (vereinfachte Darstellung)

Die Datenübertragung erfolgt in Timeslots von
je j Bit. Mehrere Timeslots werden zu einer Struktur
zusammengefasst.

  • Struktur Si
    mit  i Timeslots

    Wortlänge in Bit bei
    j  Bits pro Timeslot

    S1
    S2
    S3
    ...

    1 * j
    2 * j
    3 * j
    ...

    Eine Struktur wird auch Rahmen genannt.
  • Ein einzelner Timeslot ist dann ein Unterrahmen.
  • Die Gesamtheit der Bits/Bytes eines Rahmens
    stellen eine Nachricht dar, die in der Codierungs-
    theorie oft als Wort bezeichnet wird.

Bild 1

Bild


Einige Begriffe aus der Kanalcodierungstheorie

BCS ist so ein Begriff, der später erklärt wird. Der von mir betrachtete Kanal ist als Binary
Symmetric Channel (BSC) anzusehen, sodass die Sätze aus der Kanalcodierungstheorie
anwendbar sind.

Die Begriffe werden hier nur ganz kurz angerissen, denn es geht allein darum, den zu
betrachtenden Fall einordnen zu können. Weitergehende Erläuterungen zu den einzelnen
Begriffen finden Sie in dem Buch „Kanalcodierung“ von Bernd Friedrichs - siehe [1].

Die Kanalcodierung soll dazu dienen, die übertragenen Nachrichten über Prüfsummen auf
Fehler zu untersuchen. Bei einem erkannten Fehler kann die Nachricht dann noch einmal
geschickt werden, was als ARQ-Verfahren bekannt ist. Die Alternative ist, die Fehler -
wenn möglich - gleich zu korrigieren, was als FEC-Verfahren bekannt ist und in diesem
Beitrag nicht von Bedeutung ist.

  • FEC-Verfahren (Forward Error Correction) - Die bei der Kanalcodierung sendeseitig
    hinzugefügte Redundanz dient empfangsseitig zur Korrektur der Übertragungsfehler.
    Als Fehlerkorrekturcodes (error correction code) werden Blockcodes, Faltungscodes
    und trelliscodierte Modulationen verwendet.
  • ARQ-Verfahren (Automatic Repeat Request) -  Hierbei werden die Übertragungsfehler
    nicht korrigiert, sondern es erfolgt empfangsseitig eine Beschränkung auf die Erkennung
    von Fehlern (error detection code). Dabei muss allerdings vorausgesetzt werden, dass die
    Übertragungszeit nicht extrem knapp vorgegeben wird, und dass der Rückkanal verfügbar
    ist. Bei einem erkannten Fehler wird nämlich eine Wiederholung über diesen Rückkanal
    angefordert. Zur Fehlererkennung werden fast ausschließlich Blockcodes verwendet.

Hier sind einige neue Begriffe aufgetaucht:

  • Kanalcodierung (error control coding) - Den eigentlichen Informationen wird sendeseitig
    Redundanz, also zusätzliche Bits hinzugefügt, sodass die bei der Übertragung entstandenen
    Fehler empfangsseitig erkannt und eventuell korrigiert werden können.
  • Redundanz - Sowohl die Datenquellen wie auch die Übertragungskanäle werden
    mit stochastischen Modellen beschrieben. Mit einem mathematischen Informationsmaß
    (Entropie) wird jeder Nachricht ein Informationsgehalt zugeschrieben. Damit kann die
    minimale Anzahl von Symbolen bestimmt werden, die zur fehlerfreien Darstellung einer
    Nachricht unbedingt erforderlich ist. Eine um Kontrollbits verlängerte Nachricht mit dem
    gleichen Informationsgehalt weist dann eine Redundanz auf.
  • Blockcodes - Es gibt zwei unterschiedliche Codeklassen, nämlich Blockcodes (BC)
    und Faltungscodes (FC). Bei den Blockcodes interessieren uns die leistungsfähigen RS-,
    BCH- und CRC-Codes.

Bild 2Bild 2

  • Coderate (Definition) - Das Verhältnis von Infobits zur Blocklänge wird
    als Coderate R bezeichnet.
    • Coderate   R = k / n , dabei  ist k die Anzahl der Infobits und
      n die Anzahl der Codebits, kurz Blocklänge genannt

  • Durchsatz bei ARQ (Definition) - Es ist das Verhältnis der durchschnittlich erfolgreich
    übertragenen Informationsbits pro Zeiteinheit zur Anzahl der insgesamt übertragenen
    Bits in derselben Zeiteinheit.
    • Damit ist der Durchsatz  η =  R / V ,
      mit V als mittlere Anzahl der Übertragungen (Wiederholungen)

  • Hamming- und Minimaldistanz - Es seien x, y, z jeweils Wörter mit q-stufigen
    Werten (q = 2 bei binärem Code). Die Hammingdistanz dH(x,y) ist definiert als Anzahl der
    Abweichungen zwischen den Komponenten von x und y. Sofern eine 0 definiert ist, wird als
    Hamminggewicht wH(x) die Anzahl der Komponenten von x bezeichnet, die ungleich 0 sind.
  • Für den Zusammenhang zwischen Abstand und Gewicht gilt

      wH(x) = dH(x,O) mit O = (0, …, 0)

    Falls im Wertebereich der Symbole eine Subtraktion definiert ist,
    gilt weiter  dH(x,y) = wH(x – y)

    Die Minimaldistanz dmin eines (n, k, dmin)-Blockcodes Γ ist definiert als die minimale
    Hammingdistanz zwischen allen Codewörtern.

      dmin = min {dH(a,b) | a, b є Γ, a ≠ b}

    Die Minimaldistanz dmin ist der wichtigste Parameter, der die Güte eines Codes bestimmt.
    Die vollständige Charakterisierung eines Codes erhält man mit der Gewichtsverteilung -
    siehe nächster Absatz.

    Gewichtsverteilung - Zwar ist die Minimaldistanz der wichtigste Parameter eines
    Blockcodes, aber zur Berechnung der Fehlerwahrscheinlichkeit muss die gesamte
    sogenannte Gewichtsverteilung bekannt sein.

  • Die Gewichtsverteilung (weight distribution) eines linearen (n, k, dmin)q - Blockcodes
    ist durch einen Satz von Parametern A0, …, An charakterisiert, wobei Ar die Anzahl der
    Codewörter vom Hamminggewicht r bezeichnet.
  • Ar ≈ 2k-n (

    n
    k

    )

    Viele Codes weisen in grober Näherung eine binomiale
    Gewichtsverteilung auf, d.h. im binären Fall (q = 2) gilt

    Diese Verteilung besitzen auch die Fehlermuster eines BSC mit pe = 0,5
    (BSC siehe auch DMC), dabei ist pe die Wahrscheinlichkeit mit der ein Bitfehler auftritt.

  • Bild 3

    DC, DMC, Symmetrischer
    Hard-Decision DMC
    - DC, der diskrete
    Bild 3Kanal (Discrete Channel, coding channel),
    ist die Zusammenfassung von Modulator,
    physikalischem Kanal und Demodulator
    - siehe rechts, Bild 3.
  • Beim diskreten Kanal sind einige wichtige
    Fälle zu unterscheiden:

    Neben der Hard-Decision oder Soft-
    Decision Demodulation unterscheidet
    man zwischen einer zeitinvarianten und
    zeitvarianten Übertragung. In unserem
    Fall wird zeitinvarant angenommen.

    Ferner kann der Kanal ein Gedächtnis
    haben, d.h. der Empfangswert ist von den
    zuvor empfangenen Werten abhängig. Im anderen Fall ist er gedächtnislos,
    was für den zu betrachtenden Kanal angenommen werden soll.

    Mit DMC (Discrete Memoryless Channel) wird ein diskreter Kanal mit endlichen Alphabeten
    Ain und Aout bezeichnet, der zudem gedächtnislos ist.

    Die Gedächtnislosigkeit ist dadurch gekennzeichnet, dass die Übergangswahrscheinlichkeit
    in das Produkt der Übergangswahrscheinlichkeiten der Einzelsymbole übergeht.

    Ein q-närer symmetrischer Kanal ist ein symmetrischer Hard-Decision DMC,

     P(x|y) =

    {

    1- pe mit y = x

    pe/(q-1) mit y ≠ x

    wenn für die Übergangswahrscheinlichkeit
    Folgendes gilt:

    Im binären Fall (q =2) gilt dann
    P(y = x) = 1- pe und P(y ≠ x) = pe, wobei pe die Bitfehlerwahrscheinlichkeit ist.

    Der binäre Fall (unser Fall) mit Ain = Aout wird als binärer symmetrischer Kanal
    (Binary Symmetric Channel) - kurz BCS bezeichnet.

  • CRC-Codes - Ein zyklischer (2r-1, 2r - r – 2, 4)2-Code wird als CRC-Code
    (Cyclic Redundancy Check) bezeichnet, wenn das Generatorpolynom von der
    Form g(x) = (1 + x) p(x) ist, wobei p(x) ein primitives Polynom vom Grad r sein muss.
  • Es gilt dann:

    (1) Alle Fehlermuster bis zum Gewicht 3 werden erkannt.

    (2) Alle Fehlermuster ungeraden Gewichts werden erkannt.

    (3) Alle Bündelfehler bis zur Länge r+1 werden erkannt.

    (4) Von den Bündelfehlern der Länge r+2 wird nur eine Quote von 2-r nicht erkannt.

    (5) Von den Bündelfehlern der Länge ≥ r+3 wird nur eine Quote von 2-(r+1) nicht erkannt.

  • Verkürzung - Die Verkürzung (shortening) ist nur eine mögliche Modifikation eines
    linearen Codes. Ein (n, k, dmin)q-Code soll zu einem (n´,k´, d´min)q-Code verändert werden.
    Beim Verkürzen werden Infobits unterdrückt:
    • n´< n, k´< k, n´- k´ = n – k, R´< R, d´min ≥ dmin

    In der Praxis werden CRC-Codes oft als verkürzte Codes betrieben. Der resultierende
    (k´+r + 1, k´, 4)2-Code ist ist zwar nicht mehr zyklisch, aber dennoch sind (1) bis (5)
    unter dem Absatz CRC-Codes gewährleistet.


Überlegungen zur Optimierung des Codierungsverfahrens 

Beim statischen TDMA wird in der Regel ein fest definierter CRC-Blockcode verwendet.
Er wird auf jede Nachricht angewandt, wobei die Länge der Nachricht keine Rolle spielt.

Folgenden Schwächen dieses Verfahrens sind sofort einsehbar:

  • Ab einer gewissen Länge der Nachricht wird die Fehlererkennung schlecht!
  • Bei sehr kurzen Nachrichten ist die Fehlerkorrektur übertrieben gut - oder
    anders ausgedrückt - es werden unnötig viele Bits für die Prüfung benötigt,
    die dann an Infobits fehlen!

Für isochron TDMA soll untersucht werden, inwieweit eine Anpassung
des verwendeten CRC-Codes an die Länge der Nachricht möglich ist.

Ohne, dass die Untersuchung an Allgemeingültigkeit verliert, kann angenommen werden, dass die
einzelne Nachricht, in den maximal zur Verfügung stehenden Timeslots übertragen werden kann,
und zwar einschließlich der für die Codierung benötigten Bits, die in der graphischen Darstellung
als Kästchen hinter der eigentlichen Nachricht stehen.

Es werden dabei zwei Ansätze verfolgt:

Codierung jedes einzelnen Unterrahmens

Fall (T) - Bild 4

Bild4

Die Nachricht ist auf die einzelnen Unterrahmen (Timeslots) aufgeteilt und jeder einzelnen
Unterrahmen wird für sich kodiert. Eine Nachricht ist dann fehlerhaft ist, wenn ein Teil der
Nachricht fehlerhaft ist. Sei pR die Fehlerwahrscheinlichkeit des gesamten Rahmens und
pUR die des Unterrahmens, so gilt

    pR = 1 - (1- pUR)i, wenn der Rahmen aus i Unterrahmen besteht (ohne Beweis, da klar) .

Codierung der verschiedenen Strukturen
mit ihrem angepassten CRC-Code im jeweils letzten Unterrahmen

Fall (S) - Bild 5

Bild5

Bei der Codierung über die gesamten Struktur mit einem Code sind die Fehler in den einzelnen
Unterrahmen nicht mehr voneinander unabhängig, sodass nach der Wahrscheinlichkeitstheorie
die obige Gleichung für pR nicht mehr gültig ist.
Ist pe die Bitfehlerwahrscheinlichkeit, so gilt in diesem Fall gilt für die Fehlerwahrscheinlichkeit
der i-ten Struktur

    pR (i) = 1 - (1 - pe) i * j, wenn j die Anzahl der Bits pro Unterrahmen ist (klar).

Es wird versucht die verwendeten CRC-Codes so an den einzelnen Fall anzupassen, dass
die erforderliche Fehlerrate mit sowenig Prüfbits wie nur möglich zu erreichen ist, und gleichzeitig
der Datendurchsatz möglichst nahe an 1 kommt.

Dies Anpassung bedeutet im

  • im Fall (S), dass die Größe des Codes mit der Anzahl der Timeslots zunehmen muss.
    Dies kann durchaus in Sprüngen passieren, d.h. nicht bei jeder Erhöhung der Anzahl von
    Timeslots ist auch ein größerer CRC notwendig, da ein CRC-Code, der für die Wortlänge
    von j * i Bits brauchbar ist, auch noch für j * (i+1) Bits eine tolerable Fehlerrate liefern
    kann (j = Bits pro Timeslot).
  • Im Fall (T), wo der CRC-Code immer auf die gleiche Anzahl von Datenbits angewandt wird,
    bleibt der CRC-Code natürlich über die einzelnen Timeslots hinweg fest. Ist die Fehlerrate im
    Unterrahmen brauchbar, so muss noch überprüft werden, ob sie bei einer Nachricht, die alle
    Unterrahmen benötigt, noch tolerabel ist.

   η = R * 

1
V

 =

k
n

*

1
V

Aus der Gleichung für den Durchsatz ergeben sich zwei
Forderungen, wenn das angestrebte Ziel erreicht werden soll:

  • Die Blocklänge n soll die Anzahl der Infobits k nur gering überschreiten,
    d.h. n-k sollte klein sein und damit auch die Größe des CRC-Codes.
  • Die Wiederholungsrate V sollte möglichst klein ausfallen.

Unter der Größe eines CRC-Codes verstehe ich den Grad des Generatorpolynoms (hoch = groß),
denn der CRC-Code ist über das Generatorpolynom g(x) = (1+x) p(x) mit einem primitiven Polynom
p(x) definiert. Aus der Gleichung ist zu entnehmen, dass der Grad des Generatorpolynoms
gleich dem Grad des primitiven Polynoms + 1 ist.

Zum Beispiel ist x16+x12+x5+1=(x+1)(x15+x14+x13+x12+x4+x3+x2+x+1) ein
gebräuchliches Generatorpolynom für CRC-16.

Fall (T) und (S) sollen im nächsten Kapitel eingehender untersucht werden.


Anpassung der CRC-Codes an die Struktur

Im Sinne einer optimalen Anpassung des CRC-Codes, sei daran erinnert, dass die Coderate R als
Quotient von Infobits durch Blocklänge möglichst nahe bei 1 liegen sollte; das heißt, die Blocklänge
sollte möglichst nahe an der maximalen Periode 2r-1 liegen. In der Praxis haben wir Blocklängen,
die durch die möglichen Strukturen bei einer bestimmten Anzahl von Timeslots vorgegeben sind.

Für konstantes r mit r = 7 ergibt sich:

Fall (T) - Tabelle 1

 r = const.

7

n = 2r-1

127

k = 2r-2-r

119

 

CRC

CRC-8

2 * CRC-8

3 * CRC-8

 i * CRC-8

für Struktur

S1

S2

S3

Si

Codelängen in Bits

120 = 15 Bytes

240

360

i * 120

Die Codelänge von 120 in der ersten Struktur ergibt sich in der Praxis zwangsläufig, wenn man
von Datenbytes ausgeht, denn 120 ist die erste Zahl die kleiner als 127 ist und durch 8 teilbar ist.
Betrachtet werden 8 Timeslots.

Für r = 7 bis 10 ergeben sich folgende Blocklängen n mit k Infobits, die zu folgenden Strukturen
Si noch gerade passen, wenn r bezogen auf die Codelängen minimiert sein soll:

Fall (S) - Tabelle 2

 r

7

8

9

10

n = 2r-1

127

255

511

1023

k = 2r-2-r

119

246

501

1012

 

CRC-(r+1)

CRC-8

CRC-9

CRC-10

CRC-11

für Struktur

S1

S2

S3, S4

S5, S6, S7, S8

Codelängen in Bits

120 = 15 Bytes

240

360, 480

600, 720, 840, 960

Bei der Verkürzung (shortening) werden Infostellen gestrichen; sie werden für die Encodierung
auf Null gesetzt und nicht übertragen. In diesem Zusammenhang ist zu beachten, dass für binäre
zyklische Codes, zu denen auch der CRC-Code gehört, folgendes gilt:

  • Codes mit einer Wortlänge > Periode des Generatorpolynoms
    haben grundsätzlich nur eine Minimaldistanz dmin = 2, was sicherlich unerwünscht ist.
  • Codes mit einer Wortlänge = der Periode des Generatorpolynoms
    sind zyklisch und haben eine Minimaldistanz ≥ 3.
  • Codes mit einer Wortlänge < Periode des Generatorpolynoms
    haben zwar eine Minimaldistanz von ≥ 3, sind aber nicht mehr zyklisch.

Die CRC-Codes lassen sich aber auch als spezielle BCH-Codes zur Entwurfsdistanz d = 3
auffassen. Also gilt dmin ≥ 3. Da für CRC-Codes die Minimaldistanz immer gerade ist,
kann sie nur mindestens 4 sein.

Bei der Verkürzung von BCH-Codes kann die Minimaldistanz dmin in nicht allgemein
vorhersehbarer Weise anwachsen. Die Restfehlerwahrscheinlichkeit kann sich dadurch höchstens
noch weiter verbessern, was im weiteren Verlauf der Fehlerabschätzung nicht berücksichtigt wird,
da in der Praxis der Decodierungsalgorithmus diese Verbesserung nicht ausnutzen kann.

Es sollen die Fehlerwahrscheinlichkeiten der verschiedenen Strukturen aus Tabelle 1
untersucht werden. Für deren Berechnung wird aber vom verkürzten Code ausgegangen,
da dies der Praxis entspricht.

    Damit ist n’ in den einzelnen Strukturen ein Vielfaches von 120, und es gilt k’ = n’ - r -1.

Es soll festgestellt werden, ob dieser Ansatz überhaupt die Fehlerrate ausreichend verbessert.
Dabei kann man sich sicherlich auf folgende zwei Festlegungen einigen:

    1. Ein Kanal mit einer Bit-Fehlerwahrscheinlichkeit pe von 10-4 soll als schlecht gelten. 
    2. Eine Wortfehlerwahrscheinlichkeit pWe ≤ 10-6 soll als ausreichend angenommen werden!

Bei der Restfehlerwahrscheinlichkeit der gesamten Struktur, interessiert uns
die Wortfehlerwahrscheinlichkeit, da im Fehlerfall das gesamte Wort nochmals abzusenden ist!

Berechnet werden die folgenden Werte, und zwar unter der Annahme,
dass es sich in unserem Fall um einen binären symmetrischen DMC handelt:

  • Die Fehlerwahrscheinlichkeit pR des Rahmens:
    • Im Fall (S) ist pR (i) = 1- (1 - pe)120*i , und
      im Fall (T) ist pR (i) = 1- (1-pUR) i mit PRU = 1 - (1 - pe)120

  • pue ≤ pue (pe=1/2) = 

    2k-1
    2n

    [1, S. 91]

    Die Wahrscheinlichkeit eines
    nicht entdeckbaren Fehlermusters
  • Die Wahrscheinlichkeit für die Wiederholung einer Nachricht  pWret = 1 - (1 - pe)n - pue.
    Für pue wird der obige Term  eingesetzt und pWret damit nach oben abgeschätzt.
  • Diese letzte Gleichung ist plausibel, denn hier wird von der Wahrscheinlichkeit,
    dass das Codewort falsch ist, die Wahrscheinlichkeit subtrahiert,
    mit der ein falsches Codewort nicht entdeckt wird.

  • Eine obere Schranke pWe für die Fehlerwahrscheinlichkeit bei ausschließlicher Fehlererkennung,
    wobei zunächst einmal angenommen wird, dass der Fehler mit der Erkennung auch behoben ist.
  • Zur Berechnung der Fehlererkennung wird hier nur die Erkennungsfähigkeit von Fehlerereig-
    nissen mit den Gewichten 1 bis 3 berücksichtigt. Da die Fehler mit den ersten drei Gewichten
    bei dmin = 4 sicher erkannt werden, ist das Ergebnis als obere Schranke anzusehen;
    das heißt, der tatsächliche Fehler ist < pWe !

     [1, S. 77]

    Bei einer Mindestdistanz dmin eines Codes kann er t´ = dmin - 1 Fehler erkennen
    und t =  ½ t´ korrigieren, wobei t´+ t + 1 ≤ dmin mit t´ ≥ t gelten muss.

    Da die Fehler nur erkannt werden sollen, ergibt sich nach den obigen Gleichungen
    bei der Korrektur von 0 Fehlern mit dmin= 4, dass maximal 3 Fehler erkannt werden
    können, also t’ = 3.

    t   
    pWe ≤ 1 - ∑  
    s=0

    (

    n
    s

    )

    pes (1 - pe)n-s mit t = 3

     [1, S. 93]

    Die Berechnung von pWe
    erfolgt nach folgender Formel

    Die Formel in [1] ist für die
    Fehlerkorrektur und nicht für die Fehlererkennung angegeben.
    Unter der obigen Annahme, dass ein Fehler mit seiner Erkennung auch behoben ist, ist die
    Abschätzung über die Fehlerkorrektur als identisch anzusehen. Erst im nächsten Punkt wird
    berücksichtigt, dass das ARQ-Verfahren und nicht das FEC-Verfahren angewendet wird.

  • Die Restfehlerwahrscheinlichkeit pWrest des ARQ-Systems unter der Annahme,
    dass der Übertragungskanal gedächtnislos ist.
  • pWrest = pWe

           1      
    (1 - pWret)

    [5, S. 602]

    Dann gilt für die Restfehlerwahrscheinlichkeit

    Daran erkennt man, dass die Decodierungsfehlerwahrscheinlichkeit nicht
    ausreichend ist, um die Zuverlässigkeit des Übertragungssystems beurteilen zu können.
    Es ist zu berücksichtigen, dass ein Block unter Umständen erst nach mehreren
    Reübertragungen an den Empfänger weitergegeben wird.

     V =

           1      
    (1 – pWret)

    Bei Selektivem-Repeat-ARQ gilt für
    die mittlere Anzahl von Übertragungen

    Da sowohl der Zähler als auch der Nenner in
    der pWrest Gleichung nach oben abgeschätzt werden, wir die Ungleichung unbestimmt!

    Im benutzten Wertebereich kann pWrest aber nur um weniger als 1% überschritten werden.
    Zudem wird der Zähler mit < abgeschätzt.

  •  η = 

    k
    n

     *

    1
    V

    =

    k
    n

    (1 – pWret)

    Den Durchsatz, der sich damit wie folgt schreiben lässt

Da nun alle Gleichungen bekannt sind, kann die Berechnung erfolgen.
Auf die Ergebnistabellen 3 und 4 aus dem Originalbeitrag kann ohne großen Informationsverlust
verzichtet werden, da im nächsten Abschnitt die wichtigsten Ergebnisse noch einmal grafisch
dargestellt werden!


Interpretation der Ergebnisse und deren Vergleich

Die Ergebnisse der Berechnung lassen sich nun sehr anschaulich anhand der grafischen
Auswertung interpretieren (Bild 6). Auch wenn die einzelnen Geraden eine obere Schranke
darstellen, die Ergebnisse in der Praxis also besser ausfallen, so zeigt das Verfahren
folgende Schwächen:

  • Mit zunehmender Größe der Struktur und großer Bitfehlerrate wird der Restfehler
    sehr schnell größer.
  • Schon bei einer Bitfehlerrate von etwas über 10-4 beginnt das System bei den
    größeren Strukturen zu kippen - also bringt das Codierungsverfahren keine
    Verbesserung, sondern eine Verschlechterung der Fehlerwahrscheinlichkeit!

Fall (S) - Bild 6

Bild 6

Wir betrachten jetzt den Fall (T), also die Codierung jedes Timeslots einer Struktur mit einem
festen CRC-Code (hier CRC-8). Anhand der Tabelle 4 (siehe Originalbeitrag) und deren graphischer
Umsetzung auf dieser Seite (Bild 7) ist gegenüber dem Fall (S) eine erhebliche Verbesserung der
Restfehlerraten bei großen Strukturen festzustellen.

  • Mit zunehmender Größe der Struktur wird der Restfehler kaum größer
    (Differenz kleiner als eine Zehnerpotenz).
  • Schon bei einer Bitfehlerrate von etwas weniger als 10-3 liegt die Wortfehlerrate
    in der schlechtesten Struktur 8 schon unter 10-6!

Fall (T) - Bild 7

Bild 7

Es sei an dieser Stelle noch einmal an den Hintergrund dieser Ausarbeitung erinnert:

Optimal an die Strukturen angepasste CRC-Codes sollen Vorteile durch die Einsparung von
Prüfbits bringen! Unter diesem Gesichtspunkt ist (T) die schlechtere Lösung des Problems, denn

  • nur in der Struktur 1 sind beide Ansätze gleich gut,
  • in der Struktur 2 ist (T) schon mit  2*8 - 9 = 7 Bits im Nachteil - und so weiter -
  • in der Struktur 8 wächst der Mehrverbrauch an redundanten Bits bei (T) auf 8*8 - 11 = 53 an.

Das simple Zählen von Prüfbits, die man sparen kann, und damit für Nutzdaten zur Verfügung stehen,
führt aber nur dann zu dem gewünschten Erfolg, wenn die Wiederholungsrate nahe bei 1 liegt und
somit den Durchsatz nicht wesentlich reduziert - siehe nachstehendes Diagramm (Bild 8):

Vergleich von Fall (S) und (T) - Bild 8

Bild 8

Setzt man eine Bitfehlerrate von < 10-4 voraus, so ist (S) zu favorisieren, denn

  • es lassen sich keine weiteren redundanten Bits einsparen (ist optimal);
  • der Durchsatz nähert sich dem optimalen Durchsatz im Fall (T) an, und
  • die Restfehlerwahrscheinlichkeit in der Struktur 8 ist gerade noch ausreichend!

Die offensichtliche Schwäche im Fall (S) ist die schon in der Struktur 2 stark ansteigende
Restfehlerwahrscheinlichkeit. Will man diese Schwäche beheben, so muss der CRC-Code bei
einer Wortlänge von 240 Bit mehr als nur 3 Fehler erkennen - das heißt, dmin muss für den
größer zu wählenden CRC-Code von 4 auf 6 steigen (dmin ist gerade).

[2, S. 110]

Es ist bekannt, dass dmin = 6 für den CRC-16 nur bis zu einer Wortlänge von 151 Bit gilt.

Daraus folgt, dass schon in der Struktur 2 ein CRC-Code größer als CRC-16 zum Einsatz
kommen müsste, um eine Reduzierung der Restfehlerwahrscheinlichkeit zu erreichen.

 [1, S. 205]

Schaut man sich die Tabelle der (n, k)2-BCH Codes an, so müsste man für
die Struktur 2 schon den (255, 239)2-BCH-Code wählen, um eine Verbesserung
der Restfehlerwahrscheinlichkeit zu erreichen (d = 2t + 1 = 2*2 + 1 = 5), denn er
kann 4 anstelle von 3 Fehlern sicher erkennen (t´= d - 1= 5 - 1), wobei dies
wieder mit 16 Prüfbits erkauft wird (n-k = 16).

 [1, S. 207]

Die Minimaldistanz ist in diesem Fall nach Satz 7.5 mit der Entwurfsdistanz
identisch, denn n ist eine primitive Blocklänge (n = pm - 1 = 28 - 1),
die von d = 5 geteilt wird.

Abgesehen davon können Decodierungsverfahren für BCH-Codes größere Minimaldistanzen als
die Entwurfsdistanz nicht ausnutzen. Geht man mit der Entwurfsdistanz auf d = t + 1 herunter,
so ist man wieder bei den CRC-Codes als Spezialfall der BCH-Codes.

 [1, Satz 5.10]

Spezialfall -  Die CRC-Codes sind hier über das Generatorpolynom
g(x) = (x + 1)p(x) mit einem primitiven Polynom p(x) definiert worden.

Mit p(x) = f[z](x) erweisen sich die CRC-Codes als spezielle BCH-Codes der Form

    g(x) = KGV (f[z0] (x), f[z1] (x)) = (x + 1) p(x) 

mit der Entwurfsdistanz d = 3, wobei KGV für das kleinstes gemeinsames Vielfache steht.
Also gilt dmin ≥ 3. Da in Satz 5.10 [1] bereits dmin als gerade erkannt wurde, gilt dmin ≥ 4.

Bei dem Versuch das Problem zu lösen, ist man wieder auf den ursprünglichen Ansatz
zurückgeführt worden!

Quintessenz - Will man die im Fall (S) eingesparten Prüfbits als Datenbits behalten,
so muss es bei den für die einzelnen Strukturen festgelegten Größen der CRC-Codes bleiben!


Qualitative Beurteilung der Generatorpolynome

Tabelle 5

Primitive Polynome

Grad
   7
   8
   9
 10

Anzahl
   18
   16
     ?
     ?

Akzeptiert man die möglichen Restfehler im Fall (S), so geht es jetzt noch darum die vier CRC-Codes von CRC-8 bis CRC-11 konkret anzugeben. Die CRC-Codes ergeben sich als Produkt eines primitiven Polynoms mit (x + 1), wobei es zu einem bestimmten Grad nicht nur ein primitives Polynom gibt.

Uns interessieren die primitiven Polynome mit den Graden 7 bis 10. n der nebenstehenden Tabelle ist angegeben, wie viele primitive Polynome es zu den einzelnen Graden gibt (Tabelle 5):
Es gibt also jeweils mehrere primitive Polynome des gleichen Grades, was die Entscheidung für ein bestimmtes schwierig macht. In der Literatur zur Kanalcodierung findet man meist keine vollständige Tabelle der primitiven Polynome.

[3]

Die nachstehend aufgeführten CRC-Codes beruhen auf den primitiven Polynomen von Wayne Stahnke. Beachten Sie beim Gleichheitszeichen, dass modulo 2 zu rechnen ist!

CRC-8

(x7+x+1)(x+1) = x8+x7+x2+1

(PP8) trionomial

CRC-9

(x8+x6+x5+x+1)(x+1) = x9+x8+x7+x5+x2+1

(PP9) pentanomial

CRC-10

(x9+x4+1)(x+1) = x10+x9+x5+x4+x+1

(PP10) trionomial

CRC-11

(x10+x3+1)(x+1) = x11+x10+x4+x3+x+1

(PP11) trionomial

Um zu zeigen, dass sich genau diese primitiven Polynome bestens eignen, müsste man in die Theorie von Codern und Decodern einsteigen. Darauf wird verzichtet, denn im Rahmen dieses Aufsatzes reichen mir einige wenige gesicherte Erkenntnisse aus der Theorie, um zu einer abschließenden Beurteilung zu kommen.

Die zur Codierung notwendige Polynommultiplikation, bzw. die Polynomdivision bei der Decodierung im GF2 (binär) lässt sich auf die Addition bzw. Subtraktion modulo 2 zurückführen, was beides nach den Regeln der Boolschen Algebra einer XOR-Verknüpfung entspricht (XOR = entweder oder).

In der Praxis wird zur Decodierung von CRC-Codes oft ein „Linear Feedback Shift Register“ (LFSR) benutzt. Mit geeigneten XOR-Anzapfungspunkten (Taps) wird eine „Maximum Length Sequence“ (m-Sequenz) erzeugt. Minimal ist für ein Polynom nur ein XOR nötig, und zwar dann, wenn das primitive Polynom nur aus 3 Termen besteht (die sogenannten „trinomials“).
In bestimmten Graden setzen sich die primitiven Polynome aus mindestens 5 Termen zusammen (sogenannte „pentanomials“), die 3 XORs benötigen (siehe CRC-9).

Die von Wayne Stanke in [3] aufgelisteten primitiven Polynome sind Trinomials, bzw. Pentanomials, die folgenden Bedingungen genügen:

Trinomials

f(x) = xn + xk + 1 mit möglichst kleinem k

Pentanomials

f(x) = xn + xb+a + xb + xa + 1 mit 0 < a < b < n - a bei möglichst kleinem a

Diese Form wurde gewählt, da sich dann die Decodierung mit den üblichen Logikbausteinen gestalten lässt.

[3], [4]

Die hier benutzten primitiven Polynome aus [3] erfüllen recht gut die von
Golomb [4] für PN-Sequenzen (PN = Pseudo Noise) geforderten drei Eigenschaften.

  • R-1 „Balance“: Das Verhältnis von Nullen und Einsen sollte 50% zu 50% sein.
  • R-2 „Run Length“: Die Länge gleicher Bitfolgen soll diese Verteilung haben:
    50% = 1 Bit, 25% = 2 Bit, 12,5% = 3 Bit usw., was dem Münzwurf entspricht.
  • R-3 „Autokorrelation“: Eine für Rauschen optimale Autokorrealtionsfunktion (AKF) wird erreicht.

R-1 und R-2 spiegeln die in der mathematischen Theorie gemachten Annahmen wieder - das heißt, je besser diese Punkte erfüllt sind, desto vertrauenswürdiger sind die errechneten Abschätzungen.

R-3 (AKF) betrifft die hardwaretechnische Synchronisation über eine innere Codierung.
Diese Eigenschaft greift nicht, da es in unserem Fall um die äußere Codierung und Decodierung mit den oben angegebenen Generatorpolynomen geht.

Schlussbemerkung - Bei der Wahl der obigen Generatorpolynome (PP8) bis (PP11) für CRC-8 bis CRC-11 sind die Ergebnisse als vertrauenswürdig anzusehen!


Literaturverzeichnis

[1]

Bernd Friedrichs, “Kanalcodierung”,
Springer Verlag  1995

[2]

Torleiv Kløve, Valery I. Korzhik, “Error Detecting Codes”,
Kluwer Academic Publishers 1995

[3]

Stahnke, “Primitive Binary Polynomials”,
Mathematics of Computation, Vol. 27, Nr. 124, Oct. 1973

[4]

Golomb, “Shift Register Sequences”,
Holden Day 1962 Aegean Park Press  1982

[5]

Yu-Ming Wang, Shu Lin,
“A Modified Selective-Repeat Type-II Hybrid ARQ System and Its Performance Analysis”,
IEEE Trans. Commun., Vol. COM-31, S. 593-607 1983


\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Informatik :: automatisch eingefügt und unbearbeitet :
Optimierung der Codierung im TDMA-Protokoll [von wkleff]  
Ein Beitrag zur Kanalcodierungstheorie Worum geht es (Langfassung) - Es wird für jede Struktur in einem TDMA-Protokoll, der jeweils kleinste CRC-Code gesucht, der im ARQ-Verfahren eine noch ge
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 2852
 
Aufrufstatistik des Artikels
Insgesamt 174 externe Seitenaufrufe zwischen 2012.01 und 2021.12 [Anzeigen]
DomainAnzahlProz
http://google.de14281.6%81.6 %
http://google.ee126.9%6.9 %
https://google.com31.7%1.7 %
http://google.it21.1%1.1 %
https://duckduckgo.com21.1%1.1 %
http://google.ch31.7%1.7 %
http://google.at31.7%1.7 %
https://www.bing.com21.1%1.1 %
http://google.com10.6%0.6 %
https://www.ecosia.org10.6%0.6 %
http://www.bing.com10.6%0.6 %
https://google.at10.6%0.6 %
http://search.1und1.de10.6%0.6 %

Häufige Aufrufer in früheren Monaten
Insgesamt 141 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201201-04 (80x)http://google.de/url?sa=t&rct=j&q=tdma protokoll
2012-2016 (44x)http://google.de/url?sa=t&rct=j&q=
201402-02 (12x)http://google.ee/url?sa=t&rct=j&q=
201310-10 (5x)http://google.de/url?sa=t&rct=j&q=beispiel decodierungsfehlerwahrscheinlichke...

[Top of page]

"Informatik: Optimierung der Codierung im TDMA-Protokoll" | 0 Comments
The authors of the comments are responsible for the content.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]