-
Die Erfindung betrifft ein Verfahren zur Kanalcodierung von digitalen Daten.
-
Zur Übertragung von digitalen Daten über gestörte Kanäle, bei denen Datenverluste auftreten können, sind aus dem Stand der Technik Verfahren zur Kanalcodierung bekannt, welche den zu übertragenden Daten Redundanz hinzufügen, um hierdurch eine Rekonstruktion der Daten auch bei Datenverlusten sicherzustellen.
-
Eine Variante der Kanalcodierung betrifft die sog. Blockcodierung, bei der aus einer Anzahl von k Quellsymbolen eines Quellsymbolblocks eine Anzahl von n Codesymbolen generiert wird, wobei n größer als k ist. Auf diese Weise wird jedem Quellsymbolblock Redundanz in der Form von (n – k) Codesymbolen hinzugefügt. Im Stand der Technik gibt es viele unterschiedliche Verfahren zur Blockcodierung. Eines der geläufigsten dieser Verfahren ist die sog. Reed-Solomon-Codierung.
-
Neben der Blockcodierung ist aus dem Stand der Technik ferner die sog. Fountain-Codierung bekannt, bei der ein digitaler Fountain-Code aus einer Anzahl von Quellsymbolen generiert wird. Im Unterschied zur Blockcodierung kann mittels der Fountain-Codierung eine beliebige Anzahl von Codesymbolen aus einem vorgegebenen Quellsymbolblock erzeugt werden. Im Idealfall eines optimalen Fountain-Codes kann aus jeder Teilmenge von Codesymbolen, welche der Anzahl an Quellsymbolen entspricht, der ursprüngliche Quellsymbolblock rekonstruiert werden. Bei der Fountain-Codierung handelt es sich um eine sog. ratenlose Codierung, da kein festes Verhältnis zwischen der Anzahl an Codesymbolen zur Anzahl an Quellsymbolen vorgegeben ist. Fountain-Codes weisen gegenüber Blockcodes den Vorteil auf, dass eine Übertragung von codierten Daten unbegrenzte Zeit fortgesetzt werden kann, bis ein entsprechender Empfänger die Daten decodieren kann. Im Unterschied hierzu muss bei der Blockcodierung ein Empfänger, der wegen zu hoher Datenverluste einen Blockcode nicht decodieren kann, die verloren gegangenen Daten nochmals beim Sender anfordern.
-
Im Stand der Technik werden verschiedene Varianten der Fountain-Codierung beschrieben. Die Druckschrift [1] betrifft Fountain-Codes in der Form sog. LT-Codes (LT = Luby Transform). Bei diesen Codes wird mit Hilfe einer Wahrscheinlichkeitsverteilung und einer XOR-Verknüpfung die Sequenz an Codesymbolen generiert. In dem Dokument [2] werden sog. Raptor-Codes beschrieben, bei denen die Quellsymbole zunächst vorcodiert werden und anschließend die vorcodierten Symbole einer LT-Codierung unterzogen werden. In dem Dokument [3] wird eine Fountain-Codierung beschrieben, bei der die Codesymbole eine zufällige, durch eine Gleichverteilung realisierte Kombination von Quellsymbolen darstellen.
-
In der Druckschrift [4] wird ein Verfahren zur Kanalkodierung von digitalen Daten offenbart, bei dem ein erster Code und ein zweiter Code generiert werden. Der erste Code ist vorzugsweise ein Blockcode, wohingegen als zweiter Code z. B. ein LT-Code erzeugt werden kann.
-
In der Druckschrift [5] wird die Generierung von binären linearen zufälligen Fountain-Codes sowie von LT-Codes beschrieben.
-
Aufgabe der Erfindung ist es, eine auf Fountain-Codes basierende Kanalcodierung dahingehend zu verbessern, dass die Codiereffizienz erhöht wird, d. h. dass im Mittel weniger Codesymbole zur Rekonstruktion der ursprünglichen Quellsymbole benötigt werden.
-
Diese Aufgabe wird gelöst durch das Verfahren gemäß Patentanspruch 1 bzw. das Verfahren gemäß Patentanspruch 8 bzw. dem Sender gemäß Patentanspruch 10 bzw. das Übertragungssystem gemäß Patentanspruch 11 bzw. das Computerprogrammprodukt gemäß Patentanspruch 12. Weiterbildungen der Erfindung sind in den abhängigen Ansprüchen definiert.
-
Das erfindungsgemäße Verfahren dient zur Kanalcodierung von digitalen Daten und wandelt einen Quellsymbolblock umfassend eine Anzahl von Quellsymbolen aus den digitalen Daten in einen Ausgangscode, der Codesymbole umfasst, die den Quellsymbolblock mit Redundanz codieren. Das Verfahren wird anhand der Codierung eines Quellsymbolblocks beschrieben, wobei mit dem Verfahren auch mehrere Quellsymbolblöcke hintereinander mit den nachfolgend dargelegten Schritten codiert werden können.
-
In dem erfindungsgemäßen Verfahren wird der Quellsymbolblock in einen ersten Code und einen zweiten Code gewandelt, wobei der erste Code ein Blockcode umfassend erste Codesymbole ist und der zweite Block ein linearer zufälliger Fountain-Code umfassend zweite Codesymbole ist, wobei ein jeweiliges zweites Codesymbol eine zufällige lineare Kombination aus den Quellsymbolen des Quellsymbolblocks ist und die zufällige lineare Kombination mit einer vorgegebenen Wahrscheinlichkeitsverteilung bzw. Wahrscheinlichkeitsdichtefunktion bestimmt wird. Die Codesymbole des Ausgangscodes werden dabei aus den ersten Codesymbolen des ersten Codes und den zweiten Codesymbolen des zweiten Codes gebildet. Erfindungsgemäß werden die Quellsymbole sowie die ersten und zweiten Codesymbole jeweils aus einer Anzahl von Symbolelementen und insbesondere aus einem Symbolelement eines Galois-Felds GF(q) mit q > 2 gebildet. Ein Galois-Feld stellt dabei einen endlichen Körper aus einer endlichen Menge von Symbolelementen mit darauf definierten Grundoperationen dar, wobei die Verwendung von Galois-Feldern im Rahmen einer Datencodierung dem Fachmann geläufig ist. Eine besonders recheneffiziente Codierung wird erfindungsgemäß dadurch erreicht, dass die Symbolelemente der Quellsymbole und die Symbolelemente der ersten und zweiten Codesymbole zum gleichen Galois-Feld (d. h. zum Galois-Feld mit der gleichen Ordnung q) gehören.
-
Unter einem Blockcode ist erfindungsgemäß ein beliebiger Blockcode zu verstehen, der auf einem Galois-Feld GF(q) mit q > 2 erzeugt wird und insbesondere mit aus dem Stand der Technik bekannten Verfahren gebildet werden kann. Demgegenüber wird für die Generierung des zweiten Codes ein spezieller Fountain-Code verwendet, der auf einer zufälligen linearen Kombination von Quellsymbolen beruht. Wie jeder Fountain-Code zeichnet sich auch dieser spezielle Fountain-Code dadurch aus, dass der Code eine beliebige und potentiell unendliche Anzahl von zweiten Codesymbolen umfassen kann. In einer bevorzugten Ausführungsform wird das in der Druckschrift [3] beschriebene Verfahren zur Erzeugung des Fountain-Codes verwendet. Im Unterschied zu dem Fountain-Code der Druckschrift [3] kann erfindungsgemäß anstatt der dort beschriebenen Gleichverteilung gegebenenfalls auch eine andere Wahrscheinlichkeitsverteilung zur Generierung des Codes verwendet werden. Die Erfindung beruht auf der Erkenntnis, dass durch die Kombination eines Blockcodes mit einem linearen zufälligen Fountain-Code, welche beide zum gleichen Galois-Feld GF(q) mit q > 2 gehören, eine deutlich verbesserte Codiereffizienz erreicht wird, wie auch in der detaillierten Beschreibung näher dargelegt wird.
-
In einer besonders bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens werden die Codesymbole des Ausgangscodes als eine Sequenz von Codesymbolen gebildet, welche zunächst die ersten Codesymbole des ersten Codes und anschließend die zweiten Codesymbole des zweiten Codes umfasst. Durch die Reihenfolge der Codesymbole in der Sequenz wird insbesondere die zeitliche Reihenfolge einer späteren, sich an die Kanalcodierung anschließenden Übertragung von Codesymbolen festgelegt.
-
Zur Realisierung des linearen zufälligen Foutain-Codes werden in einer besonders bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens die Koeffizienten der linearen Kombination der Quellsymbole des Quellsymbolblocks aus dem Galois-Feld der Symbolelemente der Quellsymbole basierend auf der vorgegebenen Wahrscheinlichkeitsverteilung zufällig ausgewählt. Die Koeffizienten werden somit durch Stichprobenentnahme basierend auf der Wahrscheinlichkeitsverteilung bzw. Wahrscheinlichkeitsdichtefunktion über die Elemente des Galois-Felds bestimmt. Wie bereits oben erwähnt, kann dabei die Wahrscheinlichkeitsverteilung eine Gleichverteilung über die Symbolelemente des Galois-Felds der Quellsymbole sein. In diesem Fall ist das Auftreten von jedem Symbolelement aus dem Galois-Feld gleich wahrscheinlich. Gegebenenfalls ist es jedoch auch möglich, dass die Wahrscheinlichkeitsverteilung eine andere Verteilung über die Symbolelemente des Galois-Felds der Quellsymbole ist. Insbesondere kann die Verteilung auch derart ausgestaltet sein, dass das Symbolelement Null aus dem Galois-Feld eine höhere Wahrscheinlichkeit als andere Symbolelemente aufweist. Eine solche Verteilung hat den Vorteil, dass der Rechenaufwand bei der Decodierung des Codes geringer ist als bei einer Gleichverteilung.
-
Wie bereits oben erwähnt, können in dem erfindungsgemäßen Verfahren bei der Generierung des ersten Codes beliebige Blockcodes zum Einsatz kommen. Insbesondere kann der generierte Blockcode ein linearer Blockcode, vorzugsweise ein sog. MDS-Code (MDS = Maximum Distance Separable), sein. Entsprechende Codierverfahren zur Erzeugung solcher Blockcodes sowie die soeben genannte Klassifizierung von Blockcodes sind dem Fachmann hinlänglich bekannt und werden deshalb nicht näher erläutert. Beispiele von in dem erfindungsgemäßen Verfahren verwendbaren Blockcodes sind ein Reed-Solomon-Code sowie ein Parity-Check-Code, insbesondere ein Low-Density-Parity-Check-Code.
-
Das erfindungsgemäße Verfahren eignet sich für eine Übertragung von digitalen Daten von einem Sender zu einer Anzahl von Empfängern über einen Übertragungskanal, wobei die Übertragung eine terrestrische Kommunikation und/oder eine Satellitenkommunikation umfassen kann. Im Rahmen einer Satellitenkommunikation weist das Verfahren besondere Vorteile auf, da es auf Satellitenkanälen häufiger zu Störungen kommt und die digitalen Daten meist an eine große Anzahl von Empfängern übermittelt werden müssen.
-
Im Rahmen der Verwendung der erfindungsgemäßen Kanalcodierung bei einer Datenübertragung von einem Sender zu einer Anzahl von Empfängern werden die digitalen Daten mit dem oben beschriebenen Verfahren im Sender kanalcodiert, und der hierdurch erhaltene Ausgangscode wird durch den Sender über einen Übertragungskanal ausgesendet. Anschließend wird der ausgesendete Ausgangscode von dem oder den Empfängern empfangen, welche den Ausgangscode decodieren. Die Realisierung einer Decodierung des erfindungsgemäß codierten Ausgangscodes ist dabei dem Fachmann geläufig und kann mit an sich bekannten Verfahren erfolgen. Insbesondere kann ein Gaußsches Eliminationsverfahren zum Rückrechnen der ursprünglichen Quellsymbole verwendet werden. Mit diesem Verfahren können aus dem in der speziellen Beschreibung über die Matrix G gegebenen Zusammenhang zwischen Ausgangscode c und Quellsymbolblock u – gegebenenfalls auch bei fehlenden Codesymbolen – die ursprünglichen Quellsymbole rückgerechnet werden. Dem Empfänger sind dabei die entsprechenden Einträge der Matrix G bekannt. Zum Beispiel können diese Einträge vom Sender zum Empfänger übertragen werden oder auf andere Weise dem Empfänger bekannt gemacht werden bzw. durch diesen abgeleitet werden. Für die Einträge der Matrix zur Generierung der Fountain-Codes kann auf Seiten des Senders und auf Seiten der jeweiligen Empfänger der gleiche Pseudo-Zufallsgenerator zur Generierung der Koeffizienten verwendet werden.
-
In einer besonders bevorzugten Ausführungsform überträgt ein jeweiliger Empfänger der Anzahl von Empfänger bei erfolgreicher Decodierung des Ausgangscodes eine Bestätigung an den Sender, wobei der Sender das Aussenden des Ausgangscodes beendet, wenn er von allen Empfängern eine Bestätigung erhalten hat. Auf diese Weise wird sichergestellt, dass eine kontinuierliche Codierung des Quellsymbolblocks solange fortgesetzt wird, bis eine Decodierung bei jedem Empfänger sichergestellt ist.
-
Neben den oben beschriebenen Verfahren umfasst die Erfindung ferner einen Sender zum Aussenden von digitalen Daten, wobei der Sender ein Kanalcodierungs-Mittel zur Erzeugung eines Ausgangscodes gemäß dem erfindungsgemäßen Kanalcodierungs-Verfahren sowie ein Sendemittel zum Aussenden des Ausgangscodes über einen Übertragungskanal enthält.
-
Die Erfindung betrifft darüber hinaus ein System zur Übertragung von digitalen Daten umfassend den soeben beschriebenen Sender sowie eine Anzahl von Empfängern, wobei ein jeweiliger Empfänger der Anzahl von Empfängern ein Decodierungs-Mittel zur Decodierung des durch den Sender ausgesendeten Ausgangscodes beinhaltet. Wie oben bereits dargelegt, liegt eine entsprechende Decodierung des erfindungsgemäß codierten Signals im Rahmen von Fachwissen.
-
Die Erfindung betrifft darüber hinaus ein Computerprogrammprodukt, das direkt in den internen Speicher eines digitalen Computers geladen werden kann und Softwarecodeabschnitte umfasst, mit denen das erfindungsgemäße Verfahren und insbesondere eine oder mehrere Varianten des erfindungsgemäßen Verfahrens ausgeführt werden, wenn das Produkt auf einem Computer läuft.
-
Ausführungsbeispiele der Erfindung werden nachfolgend anhand der beigefügten Figuren detailliert beschrieben.
-
Es zeigen:
-
1 eine schematische Darstellung der gemäß einer Ausführungsform der Erfindung durchgeführten Kanalcodierung;
-
2 eine schematische Darstellung einer satellitenbasierten Datenübertragung, in der eine Ausführungsform der erfindungsgemäßen Kanalcodierung verwendet wird;
-
3 und 4 Diagramme, welche die Ergebnisse einer Kanalcodierung basierend auf verschiedenen Ausführungsformen wiedergeben.
-
Die nachfolgend beschriebene Ausführungsform der Erfindung wird basierend auf der Codierung eines Quellsymbolblocks u = (u1, u2, ..., uk) erläutert, der eine Sequenz von Quellsymbolen ui (i = 1, ..., k) umfasst, die zu einem Galois-Feld GF(q) der Ordnung q gehören, d. h. es gilt: u ∊ F k / q mit q > 2. Die Ordnung q des Galois-Felds kann beliebig gewählt werden, muss jedoch größer zwei sein. In der hier beschriebenen Variante der Erfindung stellt somit jedes einzelne Quellsymbol ui ein entsprechendes Symbolelement des Galois-Felds dar. Gegebenenfalls ist es jedoch auch möglich, dass ein Quellsymbol durch eine Mehrzahl von Symbolelementen des entsprechenden Galois-Felds gebildet wird. In diesem Fall wird ein Quellsymbol durch einen entsprechenden Vektor aus Symbolelementen repräsentiert und die nachfolgend beschriebene Generierung von Codesymbolen wird auf die einander entsprechenden Einträge der Vektoren der Quellsymbole angewandt. Das heißt, die nachfolgend beschriebenen Schritte werden in diesem Fall jeweils separat auf die Einträge mit dem gleichen Index der Vektoren der Quellsymbole angewandt.
-
In der hier beschriebenen Ausführungsform wird aus dem Quellsymbolblock zunächst ein (n, k) systematischer linearer Blockcode C' über dem Galois-Feld Fq mit Hilfe der Generatormatrix G' = (I|P') generiert. Die Matrix I ist dabei die k×k-Identitätsmatrix, wohingegen die Matrix P' eine k×(n – k)-Matrix mit Elementen aus Fq ist. Durch die Notation (n, k) wird zum Ausdruck gebracht, dass der Blockcode insgesamt n Codesymbole aus Fq enthält, wobei die ursprüngliche Anzahl von Quellsymbolen k beträgt. Es kann zur Generierung des Blockcodes C' ein beliebiges, aus dem Stand der Technik bekanntes lineares Blockcodierungs-Verfahren eingesetzt werden. Blockcodierungs-Verfahren zeichnen sich dadurch aus, dass sie eine Codierung mit fester Coderate Rc = k/n durchführen.
-
Der generierte Blockcode C' enthält zunächst die ursprünglichen k Quellsymbole und anschließend weitere (n – k) Codesymbole, über welche dem Code Redundanz hinzugefügt wird, so dass auch bei einem Verlust von Codesymbolen bei deren Übertragung der ursprüngliche Quellsymbolblock wiederhergestellt werden kann. Der codierte Blockcode C' ist somit gegeben durch c' = uG' = (c ' / 1, c ' / 2, ..., c ' / n), wobei c ' / 1 = u1, c ' / 2 = u2, ..., c ' / k = uk und die verbleibenden (n – k)-Symbole von c' die Redundanzsymbole des Blockcodes sind, die gegeben sind durch (c ' / k+1, c ' / k+2, ..., c ' / n) = uP'.
-
Zu dem Blockcode C' wird in einem nächsten Schritt ein digitaler Foutain-Code hinzugefügt. Wie bereits oben beschrieben, zeichnet sich ein Fountain-Code dadurch aus, dass er aus einem Quellsymbolblock eine beliebig lange und gegebenenfalls auch unendlich lange Sequenz an Codesymbolen generieren kann. Es wird dabei eine spezielle Variante eines Fountain-Codes verwendet, welche in der Druckschrift [3] beschrieben ist. Dieser Fountain-Code wird im Folgenden auch als LRFC-Code bezeichnet (LRFC = Linear Random Foutain Code) und erzeugt entsprechende Codesymbole basierend auf einer zufälligen linearen Kombination der Quellsymbole des Quellsymbolblocks. Die zusätzlichen Redundanzsymbole des Fountain-Codes werden somit durch die Berechnung von zufälligen linearen Kombinationen aus den obigen k Quellsymbolen wie folgt erhalten:
-
Dabei werden die Koeffizienten gj,i durch Stichprobenentnahme aus dem Galois-Feld Fq mit einer vorgegebenen Wahrscheinlichkeitsdichtefunktion entnommen, wobei in der hier beschriebenen Ausführungsform eine Gleichverteilung (1/q) verwendet wird, bei der das Auftreten jedes Symbolelements aus dem Galois-Feld gleich wahrscheinlich ist.
-
Die codierte Sequenz an Codesymbolen umfasst den Blockcode und den Fountain-Code und wird durch den Ausgangscode c = (c'|c'') repräsentiert. Die Codierung kann somit durch die nachfolgend wiedergegebene Generatormatrix beschrieben werden:
wobei der Ausgangscode gegeben ist durch
c = (uG')G'' = u(G'G'') = uG. -
Dabei wird über die Matrix G' der Blockcode generiert und über die Matrix G'' der LRFC-Code. Der Fountain-Code ist dabei im Gegensatz zum Blockcode ratenlos, d. h. die Anzahl 1 an Spalten der obigen Matrix G kann im Prinzip beliebig groß werden.
-
Die soeben beschriebene Codierung gemäß einer Ausführungsform der Erfindung wird nochmals anhand von 1 verdeutlicht. Wie sich aus dieser Figur ergibt, wird als Eingangssignal I ein Quellsymbolblock SB = u1, u2, ..., uk verarbeitet, aus dem zum einen ein Blockcode generiert wird, was durch die Box BC in 1 angedeutet ist. Der Blockcode ist in 1 als CO1 = c1, c2, ..., cn bezeichnet. Neben der Generierung des Blockcodes wird ferner der obige LRFC-Code generiert, wie durch die Box LRFC in 1 angedeutet ist. Der LRFC-Code ist in 1 mit CO2 = cn+1, cn+2, ... bezeichnet. Die beiden Codes CO1 und CO2 werden dann miteinander zu dem Ausgangscode CO kombiniert, was in 1 durch einen Schalter SW veranschaulicht ist. Der Schalter befindet sich zu Beginn der Codierung in der in 1 dargestellten Position, in welcher die Box BC mit dem Ausgang O verbunden ist, so dass der generierte Code zunächst die Codesymbole des Blockcodes CO1 enthält. An diese Symbole schließt sich dann der LRFC-Code CO2 an, was durch ein Umschalten des Schalters SW erreicht wird, so dass dieser Schalter die Box LRFC mit dem Ausgang O verbindet. Auf diese Weise ergibt sich somit der insgesamt generierte Ausgangscode CO = c1, c2, ..., cn, cn+1, cn+2, .... Dieser Ausgangscode kann anschließend über einen beliebigen Übertragungskanal, beispielsweise im Rahmen einer satellitenbasierten Kommunikation, an eine Vielzahl von Empfängern ausgesendet werden, wie nachfolgend anhand von 2 beschrieben wird.
-
2 zeigt ein typisches Szenario, in dem die erfindungsgemäße Kanalcodierung verwendet werden kann. Es ist dabei eine satellitenbasierte Kommunikation wiedergegeben, bei der ein auf der Erde befindlicher Sender TR (auch als Gateway bezeichnet) Informationen über einen Satelliten SA an eine Vielzahl von ebenfalls auf der Erde befindlichen Empfängern in der Form entsprechender Terminals T1, T2, ..., TN übermitteln möchte. Bei den zu übermittelnden Informationen kann es sich um beliebige digitale Daten handeln, beispielsweise um ein digitales Bild oder ein Softwareupdate. Der Sender TR teilt dabei die zu übertragende Information, welche dem oben beschriebenen Quellsymbolblock entspricht, in k Symbole auf, welche anschließend basierend auf dem oben beschriebenen Verfahren codiert werden. Die codierte Sequenz an Codesymbolen c1, c2, ..., cn+1 usw. wird dann über einen Übertragungskanal ausgesendet, der eine erste Übertragungsstrecke S1 zum Satelliten SA und eine zweite Übetrtragungsstrecke S2 von dem Satelliten SA zu den einzelnen Terminals T1 bis TN umfasst. Jeder einzelne Empfänger versucht dann basierend auf an sich bekannten Verfahren, insbesondere über ein Gaußsches Eliminationsverfahren, die übermittelten Codesymbole zu decodieren, um die Quellsymbole rückzurechnen.
-
Da bei der Datenübertragung Datenverluste auftreten können, ist es für die jeweiligen Terminals oftmals nicht möglich, bereits aus den ersten k empfangenen Codesymbolen, welche den ursprünglichen Quellsymbolen entsprechen, die Quellsymbole wiederherzustellen. Durch die Hinzufügung von Redundanz über den Blockcode bzw. den Fountain-Code wird jedoch eine Rückrechnung der Quellsymbole nach dem Empfang von weiteren Codesymbolen möglich, wobei die Anzahl an weiteren, für die Decodierung benötigten Codesymbolen davon abhängt, wie viele Daten auf dem Übertragungskanal verloren gegangen sind. Das Übertragungsverfahren ist dabei derart ausgestaltet, dass jeder der Terminals T1 bis TN den Sender TR benachrichtigt, sobald er die Quellsymbole erfolgreich codiert hat. Das heißt, jeder Terminal sendet eine Bestätigung an den Sender TR zurück, über welche er dem Sender die erfolgreiche Decodierung mitteilt. Die Bestätigung kann dabei wiederum über den Satelliten SA und entsprechende Übertragungsstrecken an den Sender TR übermittelt werden. Sobald der Sender von allen Terminals eine entsprechende Bestätigung erhalten hat, beendet er die kontinuierliche Übertragung der Codesymbole.
-
Die erfindungsgemäße Kombination aus einem Blockcode mit einem Fountain-Code weist den Vorteil auf, dass ein Terminal bei nicht erfolgreicher Decodierung die auf dem Übertragungskanal verloren gegangenen Daten nicht nochmals beim Sender anfordern muss. Stattdessen wird die Übertragung der Codesymbole solange fortgesetzt, bis jeder Terminal die Quellsymbole wiederherstellen kann. Darüber hinaus ist das Verfahren effizienter als das aus der Druckschrift [3] bekannte Verfahren, d. h. es werden weniger codierte Symbole von den jeweiligen Terminals benötigt, um die Quellsymbole wiederherzustellen.
-
3 und 4 zeigen Diagramme, welche auf von den Erfindern durchgeführte Abschätzungen bzw. Simulationen beruhen. Diese Diagramme vergleichen das Verfahren gemäß der Druckschrift [3] mit verschiedenen Ausführungsformen von Verfahren, welche einen LRFC-Code mit einem Blockcode kombinieren. Die Figuren betreffen dabei eine Übertragung der kanalcodierten Daten von einem Sender zu Empfängern über einen Übertragungskanal mit vorgegebener Datenverlustrate. In 3 wird dabei ein Übertragungskanal mit einer Datenverlustrate von 10% betrachtet, wohingegen die Datenverlustrate für den Übertragungskanal der 4 1% beträgt. In 3 ist die Fehlerrate PF bei einem Empfänger in Abhängigkeit von der Anzahl δ an empfangenen Codesymbolen wiedergegeben, welche über die ursprüngliche Anzahl an Quellsymbolen hinausgeht. Die Fehlerrate PF gibt dabei die Wahrscheinlichkeit an, mit der ein Empfänger bei einer entsprechenden empfangenen Anzahl δ von Zusatzsymbolen die ursprünglichen Quellsymbole nicht decodieren kann. In 3 sind über die mit der Ellipse E1 überlagerten Linien L1 und L2 eine obere und untere Grenze der Fehlerrate für den Fountain-Code der Druckschrift [3] über dem Galois-Feld GF(2) wiedergegeben. Demgegenüber sind durch die mit der Ellipse E2 überlagerten Linien L3 und L4 eine obere und untere Grenze der Fehlerrate für einen Code wiedergegeben, der aus einer Kombination eines (11, 10) Single-Partiy-Check-Codes mit dem LRFC-Code der Druckschrift [3] über dem Galois-Feld GF(2) generiert wurde. Ferner sind in 3 durch entsprechende Punkte, welche aus Übersichtlichkeitsgründen nur teilweise mit dem Bezugszeichen P bezeichnet sind, tatsächlich über Simulationen berechnete Fehlerraten für den erfindungsgemäß generierten Code wiedergegeben. Man erkennt aus 3, dass die Fehlerrate in einem Empfänger für das Verfahren, bei dem der Code aus der Kombination des Single-Parity-Check-Codes und des LRFC-Codes generiert wurde, das immer unterhalb der Fehlerrate gemäß dem Verfahren der Druckschrift [3] liegt.
-
4 zeigt ein Diagramm, in dem die Fehlerrate PE bei einem Empfänger (d. h. die Wahrscheinlichkeit, dass der Empfänger die Codesymbole nicht decodieren kann) in Abhängigkeit von einer vorgegebenen Anzahl von durch den Sender ausgesendeten Codesymbolen wiedergegeben ist. Insbesondere ist dabei die Fehlerrate in Abhängigkeit von der Anzahl ? an Zusatzsymbolen wiedergegeben, die von dem Sender zusätzlich zu den Quellsymbolen ausgesendet werden. Die Linien L5 und L6, welche durch die Ellipse E3 überlagert werden, zeigen die abgeschätzte obere und untere Grenze der Fehlerrate für einen LRFC-Code gemäß der Druckschrift [3] über dem Galois-Feld GF(2), wohingegen die übereinander liegenden Linien L7, die durch die Ellipse E4 überlagert sind, die abgeschätzte obere und untere Grenze für die Fehlerrate des LRFC-Codes der Druckschrift [3] für das Galois-Feld GF(16) wiedergeben. Demgegenüber verdeutlichen die Linien L8 und L9, welche durch die Ellipse E5 überlagert werden, die abgeschätzte obere und untere Grenze für die Fehlerrate basierend auf einem Code, der sich aus einem (11, 10) Single-Parity-Check-Code und dem LRFC-Code gemäß der Druckschrift [3] über dem Galois-Feld GF(2) zusammensetzt. Ferner zeigt die Linie L10, welche durch die Ellipse E6 überlagert ist, die Fehlerrate für einen erfindungsgemäß generierten Code, der sich aus einem (15, 6) Reed-Solomon-Code und dem LRFC-Code gemäß der Druckschrift [3] über dem Galois-Feld GF(16) zusammensetzt. Aus 5 ergibt sich deutlich, dass sowohl für das Galois-Feld GF(2) als auch das Galois-Feld GF(16) die Fehlerrate der Verfahren, bei dem ein Blockcode mit einem LRFC-Code kombiniert wird (angedeutet durch Ellipse E5 bzw. Ellipse E6), unterhalb der Fehlerrate des aus der Druckschrift [3] bekannten Verfahrens (angedeutet durch die Ellipse E3 bzw. E4) liegt.
-
Literaturverzeichnis
-
- [1] M. Luby: „LT Codes”, Proc. IEEE Symposium on the Foundations of Computer Science (FOCS): 271–280.
- [2] A. Shokrollahi: „Raptor Codes”, IEEE Transactions on Information Theory, Vol. 52, NO 6. Juni 2006.
- [3] G. Liva, E. Paolini, E. Chiani: „Performance versus overhead for fountain codes over Fq”, IEEE Communication Letters, Februar 2010.
- [4] US 2007/0300127 A1
- [5] MACKAY, D. J. C.: Fountain codes. In: IEE Proceedings Communications, Vol. 152, 2005, No. 6, S. 1062–1068. – ISSN 1350–2425