DE102012004273A1 - Method for restoring lost or damaged data transmitted from transmitting device to receiving device, involves using generator matrix for coding and decoding, where data are coded by concatenating maximum distance separable and fountain codes - Google Patents

Abstract

The method involves coding the data by an encoder which is connected with the transmitting device. The data are transmitted from the transmitting device to the receiving device by a transmission channel. The data are decoded by a decoder which is connected with the receiving device. The lost or damaged data are restored during decoding. A generator matrix is used for coding and decoding. The data are coded by concatenation of maximum distance separable codes and fountain codes. The generator matrix of the maximum distance separable codes has a Vandermonde or Cauchy structure. The inverse matrix of the Vandermonde or Cauchy matrix is calculated during decoding.

Description

Translated fromGerman

Die Erfindung betrifft ein Verfahren zum Wiederherstellen verlorengegangener und/oder beschädigter Daten.The invention relates to a method for restoring lost and / or damaged data.

Es ist bekannt, dass Daten während der Übertragung, z. B. über einen rauschbehafteten Kanal durch verschiedene Fehlerkorrekturschemata geschützt werden können. Zu diesem Zweck werden m Paritätspakete durch einen Encoder erzeugt, die k Informationspaketen hinzugefügt werden, sodass n = k + m Codewortpakete über den Kanal übertragen werden. Unter Verwendung der übertragenen Paritätsinformationen können verlorengegangene und/oder beschädigte Daten wiederhergestellt werden. Ein Codierschema, das aus dem Stand der Technik bekannt ist, ist Fountain Coding. Fountain Coding kann z. B. auf Packet Level angewandt werden und ist eine einfache und effiziente Technik, um eine zuverlässige Übertragung in einem Kommunikationssystem zu gewährleisten (1).It is known that data is transmitted during transmission, e.g. B. can be protected via a noisy channel by various error correction schemes. For this purpose, m parity packets are generated by an encoder added to k information packets so that n = k + m codeword packets are transmitted over the channel. Using the transmitted parity information, lost and / or corrupted data can be recovered. An encoding scheme known in the art is fountain coding. Fountain coding can, for. At packet level and is a simple and efficient technique for ensuring reliable transmission in a communication system ( 1 ).

Es ist ferner aus dem Stand der Technik bekannt, Daten durch eine Konkatenation eines MDS-Codes und eines Fountain Codes zu schützen. Dies ist z. B. beschrieben in der Veröffentlichung –F. Lazaro Blasco, G. Liva, ”On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes,” in proceedings of International Conference on Communications, 5–9 Juni 2011, Japan.It is also known in the art to protect data by concatenation of an MDS code and a fountain code. This is z. As described in the publication - F. Lazaro Blasco, G. Liva, "On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes," in proceedings of International Conference on Communications, 5-9 June 2011, Japan ,

Eine Klasse einfacher und effektiver Fountain Codes ist bspw. gegeben durch Linear Random Fountain Codes (LRFC) über Galois Felder höherer Ordnung, die beschrieben sind in –G. Liva, E. Paolini, and M. Chiani, ”Performance versus Overhead for Fountain Codes over Fq”, IEEE Communications Letters, vol. 14, no. 2, Seiten 178–180, Februar 2010.For example, a class of simple and effective fountain codes is given by Linear Random Fountain Codes (LRFC) over Galois fields of higher order, which are described in US Pat. G. Liva, E. Paolini, and M. Chiani, "Performance versus Overhead for Fountain Codes over Fq," IEEE Communications Letters, vol. 14, no. 2, pages 178-180, February 2010 ,

Software-Implementierungen von Packet Level Encodern und Decodern sind besonders attraktiv, da sie keine großen Anstrengungen für das Design/die Implementierung erfordern und sie mehr Flexibilität im Vergleich zu Hardware-Implementierungen erlauben. Software Module können einfach in einer Hardware-Architektur implementiert werden, die nicht speziell designt wurde, um Packet Level Coding zu unterstützen. Da Software Packet Level Encoder und Decoder auch dazu bestimmt sind, auf energiebeschränkten Plattformen zu laufen (z. B. on-board Units von Raumschiffen, Landungsschiffen, Rovern, Orbitern in erdnahen und Deep-space Missionen, Satelitten) sind effiziente Verfahren notwendig.Software implementations of packet level encoders and decoders are particularly attractive because they do not require much design / implementation effort and allow more flexibility compared to hardware implementations. Software modules can be easily implemented in a hardware architecture that was not specifically designed to support packet level coding. Since software packet level encoders and decoders are also designed to run on energy-constrained platforms (eg on-board units of spaceships, dropships, rovers, orbiters in near-earth and deep-space missions, satellites) efficient procedures are necessary.

Die Generatormatrix einer Konkatenation eines MDS Codes und eines Linear Random Fountain Codes, wie sie aus dem Stand der Technik bekannt ist, ist unten dargestellt, als eine Konkatenation zweier Matrizen G' und G''.The generator matrix of a concatenation of an MDS code and a Linear Random Fountain Code, as known in the art, is shown below, as a concatenation of two matrices G 'and G ".

G' ist eine k × n MDS Matrix und G'' ist eine k × l Generator Matrix eines Fountain Codes. Da der Linear Random Fountain Code ein ratenloser Code ist, kann die Anzahl l der Spalten von G'' prinzipiell unendlich ansteigen.G 'is a k × n MDS matrix and G "is a k × 1 generator matrix of a fountain code. Since the Linear Random Fountain Code is a non-random code, the number 1 of the columns of G "can in principle increase infinitely.

Das Kodieren wird somit durchgeführt als c = u·G wobei u in Reihenvektor ist, der die k Eingangssymbole enthält und c ein Reihenvektor ist, der die n + l Ausgangssymbole enthält.The coding is thus performed as c = u * G where u is in row vector containing the k input symbols and c is a row vector containing the n + 1 output symbols.

Auf der Empfängerseite wird ein Unterset von m Symbolen empfangen. Wir bezeichnen durch J = {j₁, j₂, ..., j_m} das Set der Indizes an den Symbolen von c, die empfangen wurden. Der empfangene Vektor y ist daher gegeben durch y = (y₁, y₂, ..., y_m) = (c_j1, c_j2, ..., c_jm) und er kann in Bezug gesetzt werden zu dem Quellblock u als y = u·G ~. Hier bezeichnet G ~ die k m Matrix zusammengesetzt durch die Spalten von G mit den Indizes in J, d. h.On the receiver side, a subset of m symbols is received. We denote by J = {j₁ , j₂ , ..., j_m } the set of indices on the symbols of c that have been received. The received vector y is therefore given by y = (y₁ , y₂ , ..., y_m ) = (c_j1 , c_j2 , ..., c_jm ) and it can be related to the source block u as y = u · G ~. Here G ~ denotes the km matrix composed of the columns of G with the indices in J, ie

Die Wiederherstellung von u wird reduziert auf das Lösen des Systems von m = k + δ linearer Gleichungen in k Unbekannten G ~^T·u^T = Y^T mit der Matrix des Systems in (2), die umgeschrieben werden kann, wie es in (3) dargestellt ist, wobei m' die gesammelten Ausgangssymbole, die zu dem MDS Code gehören, sind. Somit kann man G ~^T, wie unten dargestellt partitionieren.The restoration of u is reduced to solving the system of m = k + δ linear equations in k unknown G ~^T · u^T = Y^T with the matrix of the system in (2), which can be rewritten as described in ( 3), where m 'is the collected output symbols associated with the MDS code. Thus one can partition G ~^T as shown below.

Das Decodieren gemäß dem Stand der Technik besteht aus dem Lösen des Gleichungssystems G ~^T·u^T = Y^T, dessen Matrix in (3) dargestellt ist, mit Gauss'scher Elimination. Somit ist u ein Reihenvektor, der die k Eingangssymbole enthält, y ist der empfangene Vektor und G ~^T ist die Matrix des Systems. Insbesondere gehören m' Gleichungen zu dem MDS Code und die verbleibenden Gleichungen gehören zum Fountain Code. Weitere Hintergrundinformationen, die die vorliegende Erfindung betreffen, sind in den folgenden Veröffentlichungen beschrieben:
Byers, M. Luby, M. Mitzenmacher, and A. Rege, ”A digital fountain approach to reliable distribution of bulk data,” SIGCOMM Comput. Commun. Rev., vol. 28, no. 4, Seiten 56–67, Okt. 1998,
L. Richard Turner, ”Inverse of Vandermonde matrix with applications,” NASA Technical Note, August 1966,
Irving S. Reed, Gustave Solomon, ”Polynomial codes over certain finite fields,” Journal of the Society for Industrial and Applied Mathematics. [SIAM J.], 8, 1960,
M. K. R. M. L. J. Bloemer, M. Kalfane and D. Zuckerman, ”An xor-based erasure-resilient coding scheme,” ICSI, Tech. Rep., Aug. 1995, TR-95-048.The decoding according to the prior art consists of solving the equation system G ~^T · u^T = Y^T , the matrix of which is shown in (3), with Gaussian elimination. Thus, u is a row vector containing the k input symbols, y is the received vector, and G ~^T is the matrix of the system. In particular, m 'equations belong to the MDS code and the remaining equations belong to the Fountain Code. Further background information concerning the present invention is described in the following publications:
Byers, M. Luby, M. Mitzenmacher, and A. Rege, "A digital fountain approach to reliable distribution of bulk data," SIGCOMM Comput. Commun. Rev., vol. 28, no. 4, pages 56-67, Oct. 1998 .
L. Richard Turner, "Inverse of Vandermonde matrix with applications," NASA Technical Note, August 1966 .
Irving S. Reed, Gustave Solomon, "Polynomial codes over certain finite fields," Journal of the Society for Industrial and Applied Mathematics. [SIAM J.], 8, 1960 .
MKRMLJ Bloemer, M. Kalfane and D. Zuckerman, "An xor-based erasure-resilient coding scheme," ICSI, Tech. Rep., Aug. 1995, TR-95-048 ,

Es ist Aufgabe der vorliegenden Erfindung, ein Verfahren zum Wiederherstellen von verlorengegangenen und/oder beschädigten Daten bereitzustellen, wobei Daten mit einer verringerten Berechnungskomplexität wiederhergestellt werden können.It is an object of the present invention to provide a method for recovering lost and / or corrupted data whereby data can be restored with reduced computational complexity.

Diese Aufgabe wird erfindungsgemäß gelöst durch die Merkmale des Anspruchs 1.This object is achieved by the features of claim 1.

Gemäß der erfindungsgemäßen Methode werden Daten von einer Sendevorrichtung zu einer Empfangsvorrichtung übermittelt, wobei Daten kodiert werden durch einen Encoder, der mit der Sendevorrichtung verbunden ist. Daten werden übertragen über einen Übertragungskanal, der z. B. ein Broadcasting Netzwerk in einem Satellitenszenario ist. Jeder passende Übertragungskanal kann verwendet werden. Die übertragenen Daten werden dekodiert durch einen Decoder, der mit der Empfangsvorrichtung verbunden ist, wobei verlorengegangene und/oder beschädigte Daten während des Dekodierens wiederhergestellt werden.According to the inventive method, data is transmitted from a transmitting device to a receiving device, data being encoded by an encoder connected to the transmitting device. Data is transmitted via a transmission channel, the z. B. is a broadcasting network in a satellite scenario. Any suitable transmission channel can be used. The transmitted data is decoded by a decoder connected to the receiving device, recovering lost and / or damaged data during decoding.

Eine Generatormatrix wird für das Codieren und Decodieren verwendet, wobei Daten kodiert werden durch eine Konkatenation eines MDS Codes und eines Fountain Codes. Gemäß der Erfindung hat die Generator Matrix des MDS Codes eine Vandermonde oder Cauchy Struktur. Während des Decodierens ist ein wichtiger Schritt das Berechnen der inversen Matrix der Vandermonde oder Cauchy Matrix. In diesem Schritt kann die spezielle Struktur einer Vandermonde oder Cauchy Matrix ausgenutzt werden, um die Berechnungskomplexität für das Berechnen der inversen Matrix zu verringern. Die Vorteile des erfindungsgemäßen Verfahrens verglichen zum Stand der Technik werden im Folgenden gezeigt:
Gemäß dem Stand der Technik ist die Decodierkomplexität kubisch mit der Anzahl der Eingangssymbole des Codingschemas k, d. h. ~O(k³). Tatsächlich ist die Anzahl der Operationen, die während der Gauss'schen Elimination (GE) bei einer Matrix der Größe (k + δ) × k benötigt werden, im Packet Level bezeichnet alsN (GE) / a undN (GE) / m und wird im Folgenden dargestellt,

wobei L die Paketgröße in Bits ist, q die Ordnung des Galois Felds, über dem der Code erzeugt wurde. A generator matrix is used for encoding and decoding, data being encoded by a concatenation of an MDS code and a fountain code. According to the invention, the generator matrix of the MDS code has a Vandermonde or Cauchy structure. During decoding, an important step is calculating the inverse matrix of the Vandermonde or Cauchy matrix. In this step, the special structure of a Vandermonde or Cauchy matrix can be exploited to reduce the computational complexity for calculating the inverse matrix. The advantages of the method according to the invention compared to the prior art are shown below:
According to the prior art, the decoding complexity is cubic with the number of input symbols of the coding scheme k, ie ~ O (k³ ). In fact, the number of operations needed during Gaussian elimination (GE) for a matrix of size (k + δ) × k is denoted in the Packet Level as N (GE) / a and N (GE) / m and is shown below,

where L is the packet size in bits, q is the order of the Galois field over which the code was generated.

Der vorgeschlagene Decodieralgorithmus nutzt die Struktur der Decodiermatrix in (3) und die Struktur einer Vandermonde oder Cauchy Matrix. Um die Erfindung darzustellen, muss zuerst ein Überblick über Reed-Solomon Matrizen und Vandermonde Matrizen und ihre Inversen gegeben werden. Obwohl keine detaillierte Erklärung in Bezug auf Cauchy Matrizen gegeben wird, ist es ebenfalls möglich, eine Cauchy Matrix mit quadratischer Komplexität zu invertieren, wie gezeigt ist in –.K. R. M. L. J. Bloemer, M. Kalfane and D. Zuckerman, ”An xor-based erasure-resilient coding scheme,” ICSI, Tech. Rep., Aug. 1995, TR-95-048.The proposed decoding algorithm uses the structure of the decoding matrix in (3) and the structure of a Vandermonde or Cauchy matrix. To illustrate the invention, first review the Reed-Solomon matrices and Vandermonde matrices and their inverses. Although no detailed explanation is given with respect to Cauchy matrices, it is also possible to invert a quadratic complexity Cauchy matrix as shown in FIG. KRMLJ Bloemer, M. Kalfane and D. Zuckerman, "An xor-based erasure-resilient coding scheme," ICSI, Tech. Rep., Aug. 1995, TR-95-048 ,

Im Folgenden wird ein Überblick einer Reed-Solomon Generator Matrix und Vandermonde Matrizen gegeben:
Die Generator Matrix eines Reed-Solomon Codes der Länge n = q – 1 und der Distanz d = n – k + 1 ist im Folgenden dargestellt und wird bezeichnet als G',

wobei q die Ordnung des Galois Felds ist, über dem der Code erzeugt wurde, und α das primitive Element des Felds ist.The following is an overview of a Reed-Solomon generator matrix and Vandermonde matrices:
The generator matrix of a Reed-Solomon code of length n = q-1 and the distance d = n-k + 1 is shown below and is referred to as G ',

where q is the order of the Galois field over which the code was generated, and α is the primitive element of the field.

Die transponierte Matrix von G' wird bezeichnet als G^'T und ist wie folgt definiert,

The transposed matrix of G 'is referred to as G^{' T} and is defined as follows,

Eine quadratische Vandermonde Matrix der Ordnung y wird bezeichnet als V^γ und ist wie folgt definiert,

wobei x_i mit i = 1, ..., γ, γ unterschiedliche Elemente sind. Es ist zu beachten, dass das j-te Element in der i-ten Reihe von V^γ geschrieben werden kann als (x_i)^j–1, für j = 1, ..., γ. Eine wichtige Eigenschaft einer Vandermonde Matrix der Ordnung γ ist, dass sie eine Matrix mit vollem Rang ist, d. h. Rang (V^γ) = γ.A quadratic Vandermonde matrix of order y is designated V^γ and is defined as follows,

where x_i with i = 1, ..., γ, γ are different elements. It should be noted that the j-th element in the i-th row of V^γ can be written as (x_i)^j-1, for j = 1, ..., γ. An important property of a Vandermonde matrix of order γ is that it is a full rank matrix, ie rank (V^γ ) = γ.

Es wird bezeichnet mit J = {j₁, j₂, ..., j_m'} ein zufälliges Set von m' <= k Indizes von Reihen von G^'T. Jede der( n / m') Matrizen bestehend aus den m' Reihen, deren Indizes definiert sind in Y, ist eine Vandermonde Matrix der Ordnung m', für jedes m' <= k. Insbesondere ist

für i = 1, ..., m', und j = 1, ..., m'. Als ein Beispiel wird angenommen, dass J = {j₁ = 1, j₂ = 2, ..., j_m' = k}, d. h. m' = k und wir betrachten die Matrix, die sich zusammensetzt aus den ersten k Reihen von G^'T. Es gibt eine Vandermonde Matrix mit Rang k, wobei die k unterschiedlichen Elemente x_i = α^i–1, für i = 1, ..., k sind und die anderen Elemente (x_i)^j–1 = (α^i–1)^j–1, für j = 1, ..., k.With J = {j₁ , j₂ , ..., j_{m '} } we denote a random set of m'<= k indices of series of G^'T. Each of the (n / m ') Matrices consisting of the m 'series whose indices are defined in Y, is a vandermonde matrix of order m', for each m '<= k. In particular

for i = 1, ..., m ', and j = 1, ..., m'. As an example, it is assumed that J = {j₁ = 1, j₂ = 2, ..., j_{m '} = k}, ie m' = k, and we consider the matrix composed of the first k rows G^'T. There is a Vandermonde matrix of rank k, where the k different elements are x_i = α^i-1 , for i = 1, ..., k and the other elements (x_i )^j-1 = (α^i-1 )^j-1 , for j = 1, ..., k.

Die besondere Struktur einer Vandermonde Matrix der Ordnung y kann ausgenutzt werden, um ihre Inverse (V^(γ))^–1 mit quadratischer Komplexität in γ, d. h. ~O(γ²) anstelle einer kubischen Komplexität in γ ~ O(γ³) zu berechnen, z. B. mit einem Gauss'schen Eliminations Algorithmus.The particular structure of a vandermonde matrix of order y can be exploited to give its inverse (V^(γ) )^-1 with quadratic complexity in γ, ie ~ O (γ² ) instead of a cubic complexity in γ ~ O (γ³ ) calculate, for. With a Gaussian elimination algorithm.

Es ist bevorzugt, dass die Berechnung der inversen Vandermonde oder Cauchy Matrix stattfindet mit einer reduzierten Berechnungskomplexität, verglichen zu einer Matrix, die keine Vandermonde oder Cauchy Struktur hat, insbesondere mit quadratischer Komplexität, verglichen zu einer kubischen Komplexität für eine Matrix ohne die Vandermonde oder Cauchy Struktur.It is preferred that the computation of the inverse vowel probe or Cauchy matrix takes place with a reduced computational complexity compared to a matrix that does not have a vandermonde or cauchy structure, especially with quadratic complexity, compared to a cubic complexity for a matrix without the vandermonde or Cauchy Structure.

Es ist ferner bevorzugt, dass k Ausgangssymbole generiert werden durch den MDS Code und l Ausgangssymbole generiert werden durch den Fountain Code.It is further preferred that k output symbols are generated by the MDS code and l output symbols are generated by the fountain code.

Ferner ist es bevorzugt, dass die Konkatenation des MDS Codes und des Fountain Codes zu einem ratenlosen Code führt. Es ist bevorzugt, dass ein Reed-Solomon Code als ein MDS Code verwendet wird. Die inverse Matrix einer Vandermonde Matrix kann erlangt werden durch ein Produkt der beiden Matrizen U^–1 und L^–1, wobei U eine obere Dreiecksmatrix ist und L eine untere Dreiecksmatrix ist. Die Berechnung der Matrix L^–1 umfasst die folgenden Verfahrensschritte:
Definieren von Koeffizienten der Matrix L^–1, d. h. l_i,j mit i = 1, ..., γ und j = 1, ..., γ durch die folgenden Gleichungen:

• a. l_1,1 = 1,
• b. l_i,j = 0 für j > i, d. h. untere Dreiecksmatrix

Fixieren von j, Fokusieren auf die Koeffizienten der j-ten Spalte von L^–1, wobei die folgende rekursive Gleichung für i = j + 1, ..., γ gilt,

Starten von dem Element auf der Diagonalen l_i=j,j gegeben bei c. (außer l_1,1) als,

Verwenden rekursiver Gleichungen, um die Elemente von L^–1 zu berechnen: für jede Spalte j, j = 1, ..., γ,
Beginnen mit dem Berechnen des Elements auf der Diagonalen, d. h. i = j,
Berechnender anderen Elemente für jede Reihe i = j + 1, ..., γ.Further, it is preferable that the concatenation of the MDS code and the fountain code results in a guessless code. It is preferred that a Reed-Solomon code be used as an MDS code. The inverse matrix of a Vandermonde matrix can be obtained by a product of the two matrices U^-1 and L^-1 , where U is an upper triangular matrix and L is a lower triangular matrix. The calculation of the matrix L^-1 comprises the following method steps:
Defining coefficients of the matrix L^-1 , ie l_{i, j} with i = 1, ..., γ and j = 1, ..., γ by the following equations:

• a._1,1 = 1,
• b. l_{i, j} = 0 for j> i, ie lower triangular matrix

Fixing j, focusing on the coefficients of the jth column of L^-1 , where the following recursive equation holds for i = j + 1, ..., γ,

Starting from the element on the diagonal l_{i = j, j} given at c. (except_1.1 ) as,

Using recursive equations to calculate the elements of L^-1 : for each column, j, j = 1, ..., γ,
Starting with calculating the element on the diagonal, ie i = j,
Calculating other elements for each row i = j + 1, ..., γ.

Die Berechnung der Matrix U^–1 umfasst die folgenden Verfahrensschritte:
Definieren der Koeffizienten der Matrix U^–1, d. h. u_i,j mit i = 1, ..., γ und j = 1, ..., γ durch die folgenden Gleichungen:

• a. u_i,i = 1, wobei die Hauptdiagonale nur Elemente gleich 1 hat,
• b. u_i,j = 0 für j < i, d. h. obere Dreiecksmatrix
• c. u_i,j = u_i-1,j-1 – u_i,j-1x_j-1 mit u_0,j = 0, für j > i,

Verwenden der rekursiven Gleichung in c, um die Elemente von U^–1 zu berechnen durch Fixieren der Reihe i für jedes i = 1, ..., γ, und Berechnen der Elemente von U^–1 für jede Spalte j mit j = i + 1, ..., γ.The calculation of the matrix U^-1 comprises the following method steps:
Defining the coefficients of the matrix U^-1 , ie u_{i, j} with i = 1, ..., γ and j = 1, ..., γ by the following equations:

• a. u_{i, i} = 1, where the main diagonal has only elements equal to 1,
• b. u_{i, j} = 0 for j <i, ie upper triangular matrix
• c. u_{i, j} = u_{i -1, j -1} - u_{i, j -1} x_{j -1} with u_{0, j} = 0, for j> i,

Using the recursive equation in c to calculate the elements of U^-1 by fixing the row i for each i = 1, ..., γ, and calculating the elements of U^-1 for each column j with j = i + 1, ..., γ.

Im Folgenden wird die Anzahl der Operationen, die notwendig ist, um V^(δ) zu invertieren, berechnet gemäß den vorgestellten rekursiven Formeln. Insbesondere berücksichtigt die Berechnung Vandermonde Matrizen mit Elementen in einem Galois Feld der Ordnung q und einem primitiven Element a, wie oben für Reed-Solomon Codes dargestellt. Somit sind die elementaren Operationen Additionen und Multiplikationen über GF(q).In the following, the number of operations necessary to invert V^{(δ) is} calculated according to the recursive formulas presented. In particular, the calculation takes into account Vandermonde matrices with elements in a Galois field of order q and a primitive element a, as shown above for Reed-Solomon codes. Thus, the elementary operations are additions and multiplications over GF (q).

Die Komplexität der Berechnung von L^–1 wird bezeichnet als

für die Additionen und als

für Multiplikationen und kann ausgedrückt werden, als

wobei die erste Serie für die Operationen steht, um die Elemente auf der Hauptdiagonalen von L^–1 zu berechnen, und die zweite Serie für die Operationen steht, um die anderen Terme zu berechnen. Somit ist die asymptotische Komplexität der Berechnung von L^–1 quadratisch in γ, d. h. O(γ²).The complexity of calculating L^-1 is referred to as

for the additions and as

for multiplications and can be expressed as

where the first series represents the operations to compute the elements on the main diagonal of L^-1 and the second series represents the operations to compute the other terms. Thus, the asymptotic complexity of calculating L^{-1 is} quadratic in γ, ie O (γ² ).

Die Komplexität der Berechnung von U^–1 wird bezeichnet als

für die Additionen und als

für die Multiplikationen und kann ausgedrückt werden als

und basiert auf dem rekursiven Term. Somit ist die asymptotische Komplexität der Berechnung von U^–1 ebenfalls quadratisch in γ, d. h. ~O(γ²).The complexity of calculating U^-1 is referred to as

for the additions and as

for the multiplications and can be expressed as

and is based on the recursive term. Thus, the asymptotic complexity of the computation of U^{-1 is} also quadratic in γ, ie ~ O (γ² ).

Es ist ferner bevorzugt, dass während des Decodierens das Lösen des Gleichungssystems, das definiert ist durch eine Matrix G ~^T, die eine Konkatenation der Matrix G ~'^T des MDS Codes und der Matrix G''^T des Fountain Codes ist, die folgenden Verfahrensschritte umfasst:
Umschreiben der Matrix G ~^T als eine Konkatenation von vier Matrizen in der folgenden Form:

wobei die Reihen von V_m'×m' ein Set von m' < k Reihen einer Vandermonde Matrix der Ordnung m' und A, B and C zwei Matrizen ohne Vandermonde Struktur sind,
wobei das System, das auf der Empfängerseite gelöst werden muss, istG ~^T·u^T = y^Twobei G ~^T, die m × k Matrix des Systems ist, u^T die k × L/log₂(q) Matrix ist, die sich zusammensetzt aus den k Informationspaketen von L Bits und y^T eine m × L/log₂(q) Matrix ist, die die bekannten Terme des Systems darstellt.It is further preferred that during decoding, the solving of the system of equations defined by a matrix G ~^T , which is a concatenation of the matrix G ~ '^{T of} the MDS code and the matrix G "^{T of} the fountain code, is the following Process steps include:
Rewriting the matrix G ~^T as a concatenation of four matrices in the following form:

where the rows of V_{m '× m' are} a set of m '<k rows of a vandermonde matrix of order m' and A, B and C are two matrices without a vandermonde structure,
the system that needs to be solved on the receiver side is G ~^T · u^T = y^T where G ~^T , the m × k matrix of the system, u^{T is} the k × L / log₂ (q) matrix, which is composed of the k information packets of L bits and y^{T is} an m × L / log₂ ( q) is the matrix representing the known terms of the system.

Die Berechnung der Inversen von V unter Ausnutzung der Struktur einer Vandermonde Matrix kann durchgeführt werden, mit der folgenden Obergrenze hinsichtlich der Anzahl an Operationen, die bezeichnet werden alsN (1) / a undN (1) / m (siehe den vorherigen Abschnitt).The calculation of the inverse of V using the structure of a Vandermonde matrix can be performed with the following upper limit on the number of operations referred to as N (1) / a and N (1) / m (see the previous section).

Ferner ist es bevorzugt, dass der Decodieralgorithmus, die folgenden zusätzlichen Verfahrensschritte umfasst:
Multiplizieren der Gleichungen G ~^T·u^T = γ^T mit der Matrix M, die hiernach angegeben ist,

sodass die Matrix des Systems wird zu

sodass der neue bekannte Term bezeichnet wird als y ≈^T und das Gleichungssystem nun geschrieben werden kann, als G ≈^T·u^T = y ≈^T.Furthermore, it is preferred that the decoding algorithm comprises the following additional method steps:
Multiplying the equations G ~^T · u^T = γ^T by the matrix M given below

so that the matrix of the system becomes too

so that the new known term is called y ≈^T and the system of equations can now be written as G ≈^T · u^T = y ≈^T.

Die Anzahl der Operationen, die in diesem Schritt involviert sind, ist die Anzahl der Operationen, die notwendig sind, um V^–1 mit A zu multiplizieren, sodass man A' erhält

plus die Anzahl an Operationen, die notwendig sind um V^–1 mit y^T zu multiplizieren, sodass man y ≈^T

erhält. Durch Verwendung der zerlegten Struktur von V^–1 = U^–1L^–1 kann man zuerst die Anzahl der Operationen, die notwendig ist, um L^–1 mit A zu multiplizieren und L^–1 mit y^T erhalten, wobei zu berücksichtigen ist, dass die Multiplikation mit U^–1 die gleiche Anzahl an Operationen beinhaltet. Es ist insbesondere

The number of operations involved in this step is the number of operations necessary to multiply V^-1 by A, thus obtaining A '

plus the number of operations necessary to multiply V^-1 by y^T , so that y ≈^T

receives. By using the decomposed structure of V^-1 = U^-1 L^-1 one can first of^all obtain the number of operations necessary to multiply L^-1 by A and L^-1 by y^T , bearing in mind that multiplication by U^-1 involves the same number of operations. It is special

Die Anzahl an Operationen, die den o. g. Schritt (bezeichnet alsN (2) / a undN (2) / m) beinhaltet, ist somit

The number of operations involving the above step (referred to as N (2) / a and N (2) / m) includes, is thus

Der erfindungsgemäße Decodieralgorithmus kann ferner den folgenden zusätzlichen Verfahrensschritt umfassen:
Ausnullen der Matrix B in G ≈^T durch Multiplikationen und Reihenadditionen, wobei die Matrix des Systems, die sich nach diesem Schritt ergibt, bezeichnet wird als G =^T und hiernach angegeben ist

The decoding algorithm according to the invention may further comprise the following additional method step:
Nulling the matrix B in G ≈^T by multiplication and row additions, where the matrix of the system resulting from this step is denoted as G =^T and given below

Die Anzahl der Operationen an G =^T, die während dieses Schritts notwendig sind, wird bezeichnet alsN (B) / a und alsN (B) / m,N (B) / a = m'(m – m')(k – m')N (B) / m = m'(m – m')(1 + k – m')The number of operations on G =^T necessary during this step is referred to as N (B) / a and as N (B) / m, N (B) / a = m '(m - m') (k - m ') N (B) / m = m '(m - m') (1 + k - m ')

Die Anzahl der Operationen, die an dem bekannten Term y ≈^T notwendig sind, die zu dem neuen bekannten Term y =^T führen und somit zu dem System G =^T·u^T = y =^T, wird bezeichnet als,

The number of operations necessary on the known term y ≈^T leading to the new known term y =^T and thus to the system G =^T * u^T = y =^T is referred to as

Die Anzahl an Operationen, die in Schritt (3) involviert sind (bezeichnet alsN (3) / aundN (3) / m) ist, somit

The number of operations involved in step (3) (referred to as N (3) / a and N (3) / m ) therefore

Es ist ferner bevorzugt, dass das Lösen des Gleichungssystems der Matrix C' die Gauss'sche Elimination umfasst, wobei somit k – m' Informationssymbole, nämlich Pakete von L Bits wiederhergestellt werden.It is further preferred that the solving of the system of equations of the matrix C 'comprises the Gaussian elimination, thus restoring k - m' information symbols, namely packets of L bits.

Die Anzahl der Operationen, die während der Gauss'schen Elimination (GE) an einer Matrix der Größe (k + δ) × k im Packet Level benötigt werden, werden bezeichnet alsN (GE) / a undN (GE) / m,

The number of operations required during Gaussian elimination (GE) on a matrix of size (k + δ) x k in the packet level are designated as N (GE) / a and N (GE) / m,

Die Anzahl der Operationen, die in diesem Schritt involviert sind, wird bezeichnet alsN (4) / a undN (4) / m und wird erhalten durch Evaluieren der obigen Gleichungen über k = k – m'.The number of operations involved in this step is referred to as N (4) / a and N (4) / m and is obtained by evaluating the above equations about k = k - m '.

Es ist bevorzugt, dass die verbleibenden m' Eingangssymbole wiederhergestellt werden durch Rücksubstitution.It is preferred that the remaining m 'input symbols be restored by back substitution.

Die Anzahl der Operationen, die durch diesen Schritt notwendig sind, wird bezeichnet alsN (5) / a undN (5) / m und ist

The number of operations required by this step is referred to as N (5) / a and N (5) / m and is

Somit wird die Gesamtkomplexität der Erfindung bezeichnet alsN (Erfindung) / a undN (Erfindung) / m und istN (Erfindung) / a = N (1) / a + N (2) / a + N (3) / a + N (4) / a + N (5) / aN (Erfindung) / m = N (1) / m + N (2) / m + N (3) / m + N (4) / m + N (5) / m.Thus, the overall complexity of the invention is referred to as N (Invention) / a and N (invention) / m and is N (invention) / a = N (1) / a + N (2) / a + N (3) / a + N (4) / a + N (5) / a N (invention) / m = N (1) / m + N (2) / m + N (3) / m + N (4) / m + N (5) / m.

Der Schlüsselpunkt des vorgeschlagenen Decodieralgorithmus ist der Schritt bgzl der Berechnung der Inversen einer Vandermonde oder einer Cauchy Matrix der Ordnung m' mit quadratischer Komplexität, d. h. O((m')²), wobei z. B. der vorgeschlagene Algorithmus verwendet werden kann.The key point of the proposed decoding algorithm is the step bgzl of calculating the inverse of a quadratic complexity vowel probe or Cauchy matrix m ', ie, O ((m')² ), where z. B. the proposed algorithm can be used.

Die Erfindung erlaubt das Einsparen einer bedeutenden Anzahl an Operationen für das Decodieren von Codes basierend auf konkatenierten MDS Codes und Fountain Codes. Die Komplexitätsverringerung wird erreicht durch Ausnutzen der Struktur der Matrizen des MDS Codes.The invention allows to save a significant number of operations for decoding codes based on concatenated MDS codes and fountain codes. The complexity reduction is achieved by exploiting the structure of the matrices of the MDS code.

Im Folgenden werden bevorzugte Ausführungsformen der Erfindung im Kontext der Figuren erläutert:In the following, preferred embodiments of the invention are explained in the context of the figures:

1 zeigt ein Packet Level Coding Szenario, in dem das erfindungsgemäße Verfahren angewandt werden kann, 1 shows a packet level coding scenario in which the method according to the invention can be used,

2–4 zeigen Matrizen, die in unterschiedlichen Schritten des erfindungsgemäßen Verfahrens verwendet werden. 2 - 4 show matrices that are used in different steps of the method according to the invention.

Das Szenario des vorliegenden Patents, d. h. Packet Level Coding mit konkatenierten MDS Codes (Vandermonde/Cauchy-Matrix-basierten Codes) und Fountain Codes, ist in1 dargestellt. Zunächst wird die zu übertragende Nachricht, z. B. eine DATEI, aufgeteilt in k Informationspaketen von L Bits (Eingangssymbole) und kodiert in n + l Code Symbole, die Pakete von L Bits sind (Ausgangssymbole). Somit werden die n + l Ausgangssymbole generiert durch den Packet Level Encoder. Insbesondere ist n die Anzahl der Ausgangssymbole, die gemäß einem MDS Code generiert werden und l ist die Anzahl der Ausgangssymbole, die gemäß einem Fountain Coding Schema generiert werden. Zweitens werden die n + l Ausgangssymbole im Physical Layer geschützt (innerhalb des PHY Layer Frames) durch Fehlerkorrekturcodes (z. B. Turbo, LDPC ...), Fehlererkennungscodes (z. B. Cyclic Redundancy Check (CRC)) und sie werden übertragen. Drittens, wird auf jedes Paket auf der Empfängerseite Physical Layer Fehlerkorrektur angewandt und verbleibende Fehler werden detektiert durch den Fehlererkennungscode. Wenn Fehler detektiert werden, wird das Paket als verlorengegangen angesehen und als Auslöschung markiert. Somit sehen die Schichten über der Bitübertragungsschicht das Kommunikationsmedium als ein Packet Erasure Channel (PEC) an, wo Pakete entweder korrekt empfangen werden oder verloren gehen. Zuletzt stellt der Packet Level Decoder die Originalnachricht wieder her, wenn eine ausreichende Anzahl an Paketen empfangen wurde.The scenario of the present patent, ie Packet Level Coding with Concatenated MDS Codes (Vandermonde / Cauchy Matrix Based Codes) and Fountain Codes, is described in U.S.P. 1 shown. First, the message to be transmitted, z. A FILE divided into k information packets of L bits (input symbols) and encoded in n + 1 code symbols which are packets of L bits (output symbols). Thus, the n + 1 output symbols are generated by the packet level encoder. In particular, n is the number of output symbols generated according to an MDS code, and l is the number of output symbols generated according to a fountain coding scheme. Second, the n + l output symbols in the physical layer are protected (within the PHY layer frame) by error correction codes (eg Turbo, LDPC ...), error detection codes (eg Cyclic Redundancy Check (CRC)) and they are transmitted , Third, physical layer error correction is applied to each packet on the receiver side and remaining errors are detected by the error detection code. If errors are detected, the packet is considered lost and marked as extinction. Thus, the layers above the physical layer look at the communication medium as a Packet Erasure Channel (PEC), where packets are either received correctly or lost. Finally, the Packet Level Decoder recovers the original message when a sufficient number of packets have been received.

Im Folgenden wird ein konkretes Beispiel für die Berechnung der inversen einer Vandermonde Matrix beschrieben:
Es wird die folgende Vandermonde Matrix V⁽³⁾ über GF(4) betrachtet, die mit dem primitiven Polynom p(x) = x² + x + 1 generiert wurde. Die Inverse von V⁽³⁾, V^–1 = U^–1L^–1 muss gefunden werden,

In the following a concrete example for the calculation of the inverse of a Vandermonde matrix is described:
Consider the following Vandermonde matrix V⁽³⁾ over GF (4) generated with the primitive polynomial p (x) = x² + x + 1. The inverse of V⁽³⁾ , V^-1 = U^-1 L^-1 must be found

Somit, x₁ = α⁰ = 1, x₂ = α¹ = α, x₃ = α².Thus, x₁ = α⁰ = 1, x₂ = α¹ = α, x₃ = α² .

Zuerst muss L^–1 gefunden werden, gemäß dem vorgestellten Verfahren, ergibt dies:

First, L^-1 must be found, according to the presented procedure, this yields:

Nun soll U^–1 berechnet werden. Gemäß dem vorgestellten Verfahren ergibt dies:

Now let U^-1 be calculated. According to the presented method this results in:

Dies ergibt

This results

Es jetzt einfach festzustellen, dass V^–1·V = I, wobei I eine 3 × 3 Identitätsmatrix ist. Die Inverse von V wurde gefunden.It is now easy to see that V^-1 · V = I, where I is a 3 × 3 identity matrix. The inverse of V was found.

Die Form, in die die Matrix G ~^T des Systems umgeschrieben werden kann, ist auf der linken Seite der2 gezeigt, als eine Konkatenation von vier Matrizen (wie bereits im Kontext der Gleichung (3) beschrieben). Der bekannte Term des zu lösenden Gleichungssystems auf der Empfängerseite ist auf der rechten Seite der2 gezeigt.The form into which the matrix G ~^{T of} the system can be rewritten is on the left side of the 2 shown as a concatenation of four matrices (as already described in the context of equation (3)). The known term of the system of equations to be solved on the receiver side is on the right side of FIG 2 shown.

3 zeigt die Matrix des Systems auf der linken Seite und den bekannten Term des Systems auf der rechten Seite nach Multiplizieren von y^T mit der Matrix M. 3 shows the matrix of the system on the left and the known term of the system on the right after multiplying y^T by the matrix M.

4 zeigt die gleichen zwei Matrizen nach dem nächsten Schritt, nämlich nach Ausnullen der Matrix B. 4 shows the same two matrices after the next step, namely after nulling out the matrix B.

Eine detaillierte Beschreibung der Erfindung wurde bereits gegeben. Die abgeleiteten Gleichungen für die Anzahl der benötigten Operationen für den vorgeschlagenen Decodieralgorithmus wurden in SW implementiert. Ein Vergleich des Standes der Technik mit der Erfindung wurde durchgeführt. Nun wird das folgende Beispiel für das Prüfen der Komplexität betrachtet.A detailed description of the invention has already been given. The derived equations for the number of operations required for the proposed decoding algorithm have been implemented in SW. A comparison of the prior art with the invention was made. Now consider the following example for checking the complexity.

Wir betrachten einen konkatenierten RS(255, 191) erzeugt in GF(256) mit einem Linear Random Fountain Code über GF(256), sodass die Ordnung des Galois Felds, in dem gearbeitet wird q = 256 ist. Somit ist k = 191, n = 255, q = 256. Es wird ausgegangen von L = 40 Bits, was eine Blockgröße von 3GPP/UMTS Turbo Codes ist. Es wird angenommen, dass m' = 187 ist und somit m = 191. Es wird die Komplexität des vorgeschlagenen Decodierverfahrens mit dem Stand der Technik, z. B. einem Gauss'schen Elimination Algorithmus verglichen.Consider a concatenated RS (255, 191) generated in GF (256) with a Linear Random Fountain Code over GF (256), so that the order of the Galois field in which q is worked is 256. Thus, k = 191, n = 255, q = 256. It is assumed that L = 40 bits, which is a block size of 3GPP / UMTS turbo codes. It is assumed that m '= 187, and thus m = 191. The complexity of the proposed prior art decoding method, e.g. B. compared to a Gaussian elimination algorithm.

Die Ergebnisse wurden berechnet gemäß den präsentierten Gleichungen und sind wiedergegeben in Tabelle I.The results were calculated according to the presented equations and are given in Table I.

Tabelle I. Komplexitätsvergleich für das präsentierte Beispiel im Hinblick auf die Gesamtanzahl der Operationen N = N_a + N_m. RS(255, 191) + LRFC über GF(256), q = 256, L = 40 bits, m' = 187. Stand der Technik vs. Erfindung.

Table I. Complexity comparison for the presented example with respect to the total number of operations N = N_a + N_m . RS (255, 191) + LRFC over GF (256), q = 256, L = 40 bits, m '= 187. Invention.

Es ist zu beachten, dass für dieses Beispiel die Erfindung die Anzahl der im Stand der Technik benötigten Operationen um 84% reduziert.It should be noted that for this example, the invention reduces the number of operations required in the prior art by 84%.

Der vorgeschlagene Decodieralgorithmus kann verwendet in allen Arten von kommerziellen kabellosen und kabelgebundenen Übertragungssystemen, wie in der Satelittenkommunikation, der Kommunikation via Internet etc.The proposed decoding algorithm can be used in all types of commercial wireless and wired transmission systems, such as satellite communication, internet communication, etc.

Wie gezeigt wurde, erlaubt das vorgeschlagene Decodierverfahren, eine wesentliche Reduzierung der Komplexität des Decodieralgorithmus aus dem Stand der Technik, sodass konkatenierte Schemata basierend auf MDS Codes (z. B. Reed-Solomon Codes) und Fountain Codes (z. B. LRFC, LT Codes, Raptor Codes) auch auf Plattformen mit niedriger Rechenleistung ausgeführt werden können.As has been shown, the proposed decoding method allows a substantial reduction in the complexity of the prior art decoding algorithm, so that concatenated schemes are based MDS codes (eg Reed-Solomon codes) and fountain codes (eg LRFC, LT codes, Raptor codes) can also be executed on platforms with low computing power.

ZITATE ENTHALTEN IN DER BESCHREIBUNG QUOTES INCLUDE IN THE DESCRIPTION

Diese Liste der vom Anmelder aufgeführten Dokumente wurde automatisiert erzeugt und ist ausschließlich zur besseren Information des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt keinerlei Haftung für etwaige Fehler oder Auslassungen.This list of the documents listed by the applicant has been generated automatically and is included solely for the better information of the reader. The list is not part of the German patent or utility model application. The DPMA assumes no liability for any errors or omissions.

Zitierte Nicht-PatentliteraturCited non-patent literature

• F. Lazaro Blasco, G. Liva, ”On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes,” in proceedings of International Conference on Communications, 5–9 Juni 2011, Japan[0003]Lazaro Blasco, G. Liva, "On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes," in proceedings of International Conference on Communications, 5-9 June 2011, Japan.[0003]
• G. Liva, E. Paolini, and M. Chiani, ”Performance versus Overhead for Fountain Codes over Fq”, IEEE Communications Letters, vol. 14, no. 2, Seiten 178–180, Februar 2010[0004]G. Liva, E. Paolini, and M. Chiani, "Performance versus Overhead for Fountain Codes over Fq," IEEE Communications Letters, vol. 14, no. 2, pages 178-180, February 2010[0004]
• Byers, M. Luby, M. Mitzenmacher, and A. Rege, ”A digital fountain approach to reliable distribution of bulk data,” SIGCOMM Comput. Commun. Rev., vol. 28, no. 4, Seiten 56–67, Okt. 1998[0011]Byers, M. Luby, M. Mitzenmacher, and A. Rege, "A digital fountain approach to reliable distribution of bulk data," SIGCOMM Comput. Commun. Rev., vol. 28, no. 4, pages 56-67, Oct. 1998[0011]
• L. Richard Turner, ”Inverse of Vandermonde matrix with applications,” NASA Technical Note, August 1966[0011]L. Richard Turner, "Inverse of Vandermonde matrix with applications," NASA Technical Note, August 1966[0011]
• Irving S. Reed, Gustave Solomon, ”Polynomial codes over certain finite fields,” Journal of the Society for Industrial and Applied Mathematics. [SIAM J.], 8, 1960[0011]Irving S. Reed, Gustave Solomon, "Polynomial codes over certain finite fields," Journal of the Society for Industrial and Applied Mathematics. [SIAM J.], 8, 1960[0011]
• M. K. R. M. L. J. Bloemer, M. Kalfane and D. Zuckerman, ”An xor-based erasure-resilient coding scheme,” ICSI, Tech. Rep., Aug. 1995, TR-95-048[0011]MKRMLJ Bloemer, M. Kalfane and D. Zuckerman, "An xor-based erasure-resilient coding scheme," ICSI, Tech. Rep., Aug. 1995, TR-95-048[0011]
• K. R. M. L. J. Bloemer, M. Kalfane and D. Zuckerman, ”An xor-based erasure-resilient coding scheme,” ICSI, Tech. Rep., Aug. 1995, TR-95-048[0016]KRMLJ Bloemer, M. Kalfane and D. Zuckerman, "An xor-based erasure-resilient coding scheme," ICSI, Tech. Rep., Aug. 1995, TR-95-048[0016]

Claims (9)

Translated fromGerman

Verfahren zum Wiederherstellen verlorengegangener und/oder beschädigter Daten, die übertragen wurden von einer Sendevorrichtung zu einer Empfangsvorrichtung, wobei dieses Verfahren die Schritte umfasst: Codieren dieser Daten durch einen Encoder, der mit der Sendevorrichtung verbunden ist, Übertragen dieser Daten von der Sendevorrichtung zu der Empfangsvorrichtung über einen Übertragungskanal und Decodieren dieser Daten durch einen Decoder, der mit der Empfangsvorrichtung verbunden ist, wobei verlorengegangene und/oder beschädigte Daten während des Decodierens wiederhergestellt werden, wobei eine Generatormatrix für das Codieren und Decodieren verwendet wird, wobei die Daten codiert werden durch eine Konkatenation eines MDS Codes und eines Fountain Codes, die Generatormatrix des MDS Codes eine Vandermonde oder Cauchy Struktur hat, wobei während des Decodierens die inverse Matrix der Vandermonde oder Cauchy Matrix berechnet wird.A method of restoring lost and / or corrupted data transmitted from a sending device to a receiving device, the method comprising the steps of:Encoding this data by an encoder connected to the transmitting device,Transmitting this data from the transmitting device to the receiving device via a transmission channel andDecoding this data by a decoder connected to the receiving device, recovering lost and / or corrupted data during decoding,wherein a generator matrix is used for coding and decoding,the data being encoded by a concatenation of an MDS code and a fountain code,the generator matrix of the MDS code has a Vandermonde or Cauchy structure,wherein during decoding the inverse matrix of the Vandermonde or Cauchy matrix is calculated.Verfahren gemäß nach Anspruch 1, dadurch gekennzeichnet, dass die Berechnung der inversen Vandermonde oder Cauchy Matrix stattfindet mit einer verringerten Berechnungskomplexität verglichen zu einer Matrix ohne eine Vandermonde oder Cauchy Struktur, insbesondere mit quadratischer Komplexität verglichen zu einer kubischen Komplexität für eine Matrix ohne die Vandermonde oder Cauchy Struktur.A method according to claim 1, characterized in that the calculation of the inverse vowel probe or Cauchy matrix takes place with a reduced computational complexity compared to a matrix without a vandermonde or cauchy structure, in particular of quadratic complexity compared to a cubic complexity for a matrix without the vandermonde or Cauchy structure.Verfahren gemäß Anspruch 1 oder 2, dadurch gekennzeichnet, dass n Ausgangssymbole generiert werden durch den MDS Code und l Ausgangssymbole generiert werden durch den Fountain Code.A method according to claim 1 or 2, characterized in that n output symbols are generated by the MDS code and l output symbols are generated by the fountain code.Verfahren gemäß nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die Konkatenation des MDS Codes und des Fountain Codes zu einem ratenlosen Code führt.Method according to one of Claims 1 to 3, characterized in that the concatenation of the MDS code and the fountain code leads to a non-random code.Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass ein Reed-Solomon Code als ein MDS Code verwendet wird.Method according to one of claims 1 to 4, characterized in that a Reed-Solomon code is used as an MDS code.Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass die inverse Matrix einer Vandermonde oder einer Cauchy Matrix erlangt wird durch das Produkt zweier Matrizen U^–1 und L^–1, wobei U eine obere Dreiecksmatrix und L eine untere Dreiecksmatrix ist, wobei die Berechnung der Matrix L^–1 die folgenden Verfahrensschritte beinhaltet: Definieren von Koeffizienten der Matrix L^–1, d. h. l_i,j mit i = 1, ..., γ und j = 1, ..., γ durch die folgenden Gleichungen: a. l_1,1 = 1, b. l_i,j = 0 für j > i, d. h. untere Dreiecksmatrix

Fixieren von j, Fokussieren auf die Koeffizienten der j-ten Spalte von L^–1, wobei die folgende rekursive Gleichung für i = j + 1, ..., γ gilt,

Starten von dem Element auf der Diagonalen l_i=j,j gegeben bei c. (außer l_1.1) als,

Verwenden rekursiver Gleichungen, um die Elemente von L^–1 zu berechnen: für jede Spalte j, j = 1, ..., γ, Beginnen mit dem Berechnen des Elements auf der Diagonalen, d. h. i = j, Berechnen der anderen Elemente für jede Reihe i = j + 1, ..., γ und die Berechnung der Matrix U^–1 umfasst die folgenden Verfahrensschritte: Definieren der Koeffizienten der Matrix U^–1, d. h. u_i,j mit i = 1, ..., γ und j = 1, ..., γ durch die folgenden Gleichungen: a. u_i,i = 1, wobei die Hauptdiagonale nur Elemente gleich 1 hat, b. u_i,j = 0 für j < i, d. h. obere Dreiecksmatrix c. u_i,j = u_i-1,j-1 – u_i,j-1x_j-1 mit u_0,j = 0, für j > i, Verwenden der rekursiven Gleichung in c, um die Elemente von U^–1 zu berechnen durch Fixieren der Reihe i für jedes i = 1, ..., γ, und Berechnen der Elemente von U^–1 für jede Spalte j mit j = i + 1, ..., γ.Method according to one of claims 1 to 5, characterized in that the inverse matrix of a Vandermonde or a Cauchy matrix is obtained by the product of two matrices U^-1 and L^-1 , where U is an upper triangular matrix and L is a lower triangular matrix, the calculation of the matrix L^-1 comprises the following method steps: defining coefficients of the matrix L^-1 , ie l_{i, j} with i = 1, ..., γ and j = 1, ..., γ by the following equations : a._1.1 = 1, b. l_{i, j} = 0 for j> i, ie lower triangular matrix

Fixing j, focusing on the coefficients of the jth column of L^-1 , the following recursive equation for i = j + 1, ..., γ,

Starting from the element on the diagonal l_{i = j, j} given at c. (except_1.1 ) as,

Using recursive equations to calculate the elements of L^-1 : For each column, j, j = 1, ..., γ, begin by calculating the element on the diagonal, ie i = j, computing the other elements for each Row i = j + 1, ..., γ and the calculation of the matrix U^-1 comprises the following method steps: Defining the coefficients of the matrix U^-1 , ie u_{i, j} with i = 1, ..., γ and j = 1, ..., γ by the following equations: a. u_{i, i} = 1, where the main diagonal has only elements equal to 1, b. u_{i, j} = 0 for j <i, ie upper triangular matrix c. u_{i, j} = u_{i-1, j-1} - u_{i, j-1} x_j-1 with u_{0, j} = 0, for j> i, using the recursive equation in c to obtain the elements of U^{- 1} by fixing the row i for each i = 1, ..., γ, and calculating the elements of U^-1 for each column j with j = i + 1, ..., γ.Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, das während des Decodierens das Lösen des Gleichungssystems, dass durch die Matrix G ~^T definiert ist, die eine Konkatenation der Matrix G ~'^T des MDS Codes und Matrix G ~''^T des Fountain Codes ist, die folgenden Verfahrensschritte umfasst: Umschreiben der Matrix G ~^T als eine Konkatenation von vier Matrizen in der folgenden Form:

2 Matrix des Gleichungssystems (linke Seite) und bekannte Term des zu lösenden Gleichungssystems (rechte Seite) auf der RX Seite, wobei die Reihen von V_m'×m' ein Set von m' < k Reihen einer Vandermonde Matrix der Ordnung m' und A, B und C zwei Matrizen ohne Vandermonde Struktur sind, wobei das System, das auf der Empfängerseite gelöst werden muss, ist:G ~^T·u^T = y^Twobei G ~^T, die m × k Matrix des Systems ist, u^T, die k × L/log₂(q) Matrix ist, die sich zusammensetzt aus den k Informationspaketen von L Bits und y^T eine m × L/log₂(q) Matrix ist, die die bekannten Terme des Systems darstellt.Method according to one of Claims 1 to 6, characterized in that, during the decoding, the solving of the system of equations defined by the matrix G ~^T is a concatenation of the matrix G ~ '^{T of} the MDS code and matrix G ~''^T of the fountain code, comprises the following steps: rewriting the matrix G ~^T as a concatenation of four matrices in the following form:

2 Matrix of the system of equations (left side) and known term of the system of equations (right side) to be solved on the RX side, where the series of V_{m '× m' is} a set of m '<k rows of a vandermonde matrix of order m' and A , B and C are two matrices without Vandermonde structure, where the system that needs to be solved on the receiver side is: G ~^T · u^T = y^T where G ~^T , the m × k matrix of the system, is u^T , the k × L / log₂ (q) matrix, which is composed of the k information packets of L bits and y^{T is} an m × L / log₂ (q) is matrix representing the known terms of the system.Verfahren gemäß Anspruch 7, dadurch gekennzeichnet, dass der Decodieralgorithmus ferner die folgenden Verfahrensschritte aufweist: Multiplizieren der Gleichungen G ~^T·u^T = γ^T durch die Matrix M, die hiernach angegeben ist,

sodass die Matrix des Systems wird zu

sodass der neue bekannte Term bezeichnet wird als y ≈^T und das Gleichungssystem nun geschrieben werden kann als G ≈^T·u^T = y ≈^T. Ausnullen der Matrix B in G ≈^T durch Multiplikationen und Reihenadditionen, wobei die Matrix des nach diesem Schritt resultierenden Systems bezeichnet wird als G =^T und hiernach gegeben ist,

A method according to claim 7, characterized in that the decoding algorithm further comprises the following method steps: multiplying the equations G ~^T · u^T = γ^T by the matrix M indicated hereinafter

so that the matrix of the system becomes too

so that the new known term is called y ≈^T and the system of equations can now be written as G ≈^T · u^T = y ≈^T. Nulling the matrix B in G ≈^T by multiplication and row additions, where the matrix of the system resulting from this step is called G =^T and given hereafter,

Verfahren gemäß Anspruch 8, dadurch gekennzeichnet, dass das Lösen des Gleichungssystems der Matrix C' Gauss'sche Elimination umfasst, sodass k – m' Information Symbole, nämlich Pakete von L Bits wiederhergestellt werden, wobei die verbleibenden m' Eingangssymbole durch Rücksubstitution wiederhergestellt werden.Method according to claim 8, characterized in that the solving of the system of equations of the matrix C 'comprises Gaussian elimination such that k - m' information symbols, namely packets of L bits with the remaining m 'input symbols being restored by back substitution.

Images