Retransmission technique

Abstract

A technique for transferring data (602) that is representable by N data symbols (606) of a finite field is described. The size of the field is an integer power of a Mersenne prime. As to a method aspect of the technique, a polynomial over the finite field is determined based on the N data symbols (606). More than N code symbols (610) of the finite field are used for transmitting or initiating to transmit the data (602). At least one of the code symbols (610) corresponds to an evaluation of the polynomial at a non-primitive element of the finite field.

Claims

1. A method of transmitting data that is representable by N data symbols of a finite field, the size of which field is an integer power of a Mersenne prime, the method comprising the steps of: determining, based on the N data symbols, a polynomial over the finite field; and transmitting or initiating to transmit the data using more than N code symbols of the finite field, at least one of the code symbols corresponding to an evaluation of the polynomial at a non-primitive element of the finite field.

2. A computer program product comprising a non-transitory computer readable medium storing program code for causing a device executing the program code to perform the method of claim 1.

3. A method of receiving data that is representable by N data symbols of a finite field, the size of which field is an integer power of a Mersenne prime, the method comprising the step of: determining the N data symbols based on at least N received code symbols out of more than N code symbols, wherein the determining includes determining a polynomial over the finite field based on the at least N received code symbols, at least one of the code symbols corresponding to an evaluation of the polynomial at a non-primitive element of the finite field.

4. A computer program product comprising a non-transitory computer readable medium storing program code for causing a device executing the program code to perform the method of claim 3.

5. A device for transmitting data that is representable by N data symbols of a finite field, the size of which field is an integer power of a Mersenne prime, the device comprising at least one processor and a memory, said memory comprising instructions executable by said at least one processor, wherein the device is operative to: determine, based on the N data symbols, a polynomial over the finite field; and transmit or initiate to transmit the data using more than N code symbols of the finite field, at least one of the code symbols corresponding to an evaluation of the polynomial at a non-primitive element of the finite field.

6. The device of claim 5, wherein N of the code symbols correspond to the N data symbols, and the device is operable to transmit the N data symbols prior to the transmission, or the initiation of the transmission, of the at least one of the code symbols.

7. The device of claim 5, wherein the size of the field is a Mersenne prime or the square of a Mersenne prime.

8. The device of claim 5, wherein the device is operable to generate at least one of the code symbols by evaluating the polynomial at different powers of the non-primitive element, and the order of the non-primitive element in the finite field is equal to or greater than the number of the at least one of the code symbols.

9. The device of claim 5, wherein the Mersenne prime is equal to 2p-1 with a prime p>2, and wherein the non-primitive element is equal to 2 or an integer power of 2.

10. The device of claim 5, wherein the order of the non-primitive element in the finite field is equal to or greater than the number of the more than N code symbols.

11. The device of claim 5, wherein the device is operable to determine the polynomial by linearly mapping the N data symbols to coefficients of the polynomial, and the device is operable to determine the polynomial by coefficients of the polynomial that are equal to the N data symbols.

12. The device of claim 5, wherein a degree of the polynomial is less than N.

13. The device of claim 5, wherein to device is operable to transmit each of the more than N code symbols or is operable to initiate for the transmission of each of the more than N code symbols in a separate packet data unit or frame, and/or wherein each code symbol comprises or is associated with a portion for error detection.

14. The device of claim 5, wherein the device is further operable to map or to initiate to map the data to the N data symbols.

15. The device of claim 5, wherein the Mersenne prime is equal to 2p-1, each data symbol comprises p bits or an integer multiple thereof, and the device is further operable to generate or initiate to generate the N data symbols by segmenting the data into groups of p bits or integer multiples thereof.

16. The device of claim 15, wherein the device is operable to generate the data symbols by scrambling or whitening the data so that each of the N data symbols comprises at least one bit being one and at least one bit being zero.

17. The device of claim 5, wherein at least one of the determination and the evaluation includes performing circular bit shifts.

18. A device for receiving data that is representable by N data symbols of a finite field, the size of which field is an integer power of a Mersenne prime, the device comprising at least one processor and a memory, said memory comprising instructions executable by said at least one processor, wherein the device is operative to: determine the N data symbols based on at least N received code symbols out of more than N code symbols, wherein the determining includes determining a polynomial over the finite field based on the at least N received code symbols, at least one of the code symbols corresponding to an evaluation of the polynomial at a non-primitive element of the finite field.

19. The device of claim 18, wherein the device is operable to determine the data symbols by linearly mapping coefficients of the polynomial to the N data symbols.

20. The device of claim 18, wherein the device is further operable to map or initiate to map the N data symbols to the data.

21. The device of claim 18, wherein the Mersenne prime is equal to 2p-1, each data symbol comprises p bits or a multiple thereof, and the device is further operable to generate or initiate to generate the data by concatenating the N data symbols as groups of p bits or multiples thereof.

22. The device of claim 18, wherein the device is operable to generate or to initiate to generate the data by descrambling or unwhitening the data symbols.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further details of embodiments of the technique are described with reference to the enclosed drawings, wherein:

(2) FIG. 1 shows a schematic block diagram of a device embodiment for transmitting data;

(3) FIG. 2 shows a schematic block diagram of a device embodiment for receiving data;

(4) FIG. 3 shows a flowchart of a method embodiment for transmitting data, which is implementable by the device of FIG. 1;

(5) FIG. 4 shows a flowchart of a method embodiment for receiving data, which is implementable by the device of FIG. 2;

(6) FIG. 5 shows a flowchart for an implementation of the method of FIG. 3;

(7) FIG. 6 shows schematic block diagrams for a first embodiment of the transmitting and receiving devices at a transmitting station and a receiving station, respectively, in a radio communication;

(8) FIG. 7 shows schematic block diagrams for a second embodiment of the transmitting and receiving devices at a transmitting station and a receiving station, respectively, in a radio communication;

(9) FIG. 8 shows schematic block diagrams for a third embodiment of the transmitting and receiving devices at a transmitting station and a receiving station, respectively, in a radio communication;

(10) FIG. 9 shows a schematic block diagram of an embodiment of the transmitting device at a transmitting station, which is combinable with any embodiment of FIGS. 1, 3, 5 and 6 to 8;

(11) FIG. 10 shows a schematic block diagram of an embodiment of the transmitting device outside of a transmitting station, which is combinable with any embodiment of FIGS. 1, 3, 5 and 6 to 8;

(12) FIG. 11 shows a schematic block diagram of an embodiment of the receiving device at a receiving station, which is combinable with any embodiment of FIGS. 2, 4 and 6 to 8; and

(13) FIG. 12 shows a schematic block diagram of an embodiment of the receiving device outside of a receiving station, which is combinable with any embodiment of FIGS. 2, 4 and 6 to 8.

DETAILED DESCRIPTION

(14) In the following description, for purposes of explanation and not limitation, specific details are set forth, such as a specific network environment in order to provide a thorough understanding of the technique disclosed herein. It will be apparent to one skilled in the art that the technique may be practiced in other embodiments that depart from these specific details. Moreover, while the following embodiments are primarily described for a 5G New Radio (NR) implementation, it is readily apparent that the technique described herein may also be implemented in any other radio network, including 3GPP LTE or a successor thereof, Wireless Local Area Network (WLAN) according to the standard family IEEE 802.11, Bluetooth according to the Bluetooth Special Interest Group (SIG), particularly Bluetooth Low Energy and Bluetooth broadcasting, and/or ZigBee based on IEEE 802.15.4.

(15) Moreover, those skilled in the art will appreciate that the functions, steps, units and modules explained herein may be implemented using software functioning in conjunction with a programmed microprocessor, an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), a Digital Signal Processor (DSP) or a general purpose computer, e.g., including an Advanced RISC Machine (ARM). It will also be appreciated that, while the following embodiments are primarily described in context with methods and devices, the invention may also be embodied in a computer program product as well as in a system comprising at least one computer processor and memory coupled to the at least one processor, wherein the memory is encoded with one or more programs that may perform the functions and steps or implement the units and modules disclosed herein.

(16) FIG. 1 schematically illustrates a block diagram of an embodiment of a device for transmitting data, which device is generically referred to by reference sign 100.

(17) The device 100 may be connected to and/or part of a radio network. The device 100 may be implemented at a transmitting station of the radio network, at a node of the radio network controlling the transmitting station or by a combination thereof. The transmitting station may transmit (e.g., broadcast) the data to one or more receiving stations of the radio network. A channel or path from the transmitting station to the respective receiving station may include one or more hops in the radio network.

(18) The data is representable by N data symbols of a finite field or a Galois field (GF). The size, s, of the finite field GF(s) is a Mersenne prime,
s=M.sub.p=2.sup.p1,
or an integer power of an Mersenne prime,
s=(M.sub.p).sup.q=(2.sup.p1).sup.q.

(19) The device 100 comprises a polynomial module 104 that determines, based on the N data symbols, a polynomial over the finite field. The device 100 further comprises a transmission module 106 that transmits or initiates to transmit the data using more than N code symbols of the finite field.

(20) The code symbols are computed based on the N data symbols and/or the polynomial. At most N (if any) of the code symbols are equal to the N data symbols or computed directly (e.g., without using the polynomial) from the N data symbols. Each of the at least one further code symbol (e.g., each code symbol) corresponds to an evaluation of the polynomial at a non-primitive element of the finite field, e.g., evaluations of the polynomial at different integer powers of the same non-primitive element of the finite field.

(21) Optionally, the device 100 further comprises a segmentation module 102 that segments the data into N data portions. Each of the N data symbols is equal to, includes or is computed based on a different one of the N data portions. The data portions are preferably equally sized, e.g., each including p bits. Padding bits may be included in one of the N data portions (e.g., the N-th data portion), if a size, l, of the data in bit length is not an integer multiple of p and N.

(22) At least one of p, q and N may be set based on the size 1 of the data to be transmitted. A technical standard for the radio network may specify one or more values for each of p and/or q. The method 300 may compute the number N of the data symbols as the minimum of N.Math.p.Math.q1. For the minimization, the exponent p may be set to any prime that yields a Mersenne prime M.sub.p. Alternatively or in combination, the positive integer q may be equal to 1 or may be set to any even number or any value in a subset thereof (e.g., {1, 2, 4}).

(23) Any of the modules of the device 100 may be implemented by units configured to provide the corresponding functionality.

(24) FIG. 2 schematically illustrates a block diagram of an embodiment of a device for receiving data, which device is generically referred to by reference sign 200. The device 200 may be connected to and/or part of a radio network. The device 200 may be implemented at a receiving station of the radio network, at a node of the radio network controlling the receiving station or by a combination thereof.

(25) The data is representable by N data symbols of a finite field. The size of the field is a Mersenne prime or an integer power thereof. The device 200 optionally comprises a reception module 202 for receiving or initiating to receive the data using more than N code symbols of the finite field, at least one of the code symbols corresponding to an evaluation of a polynomial over the finite field at a non-primitive element of the finite field. The device 200 comprises a polynomial module 204 that determines the N data symbols by determining the polynomial based on received N of the code symbols.

(26) Optionally, the device 200 further comprises a concatenation module 206 that concatenates the N data symbols or N data portions, resulting in the data. Each of the N data portions is equal to, extracted from or is computed based on a different one of the N data symbols. One of the N data portions (e.g., the N-th data portion) may include padding bits, which are not included in the data that is output by the concatenation module 206.

(27) Any of the modules of the device 200 may be implemented by units configured to provide the corresponding functionality.

(28) Each of the transmitting station and the receiving station may include a base station (e.g., a network controller or a Wi-Fi access point) or a radio access node (e.g. a 3G base station, a 4G eNodeB or a 5G gNodeB) of the radio network (e.g., more specifically, of a radio access network providing radio access within the radio network). Alternatively or in addition, each of the transmitting station and the receiving station, may include a mobile or portable station or a radio device connectable to the radio network (e.g., more specifically, connectable to a radio access network providing radio access within the radio network). The radio device may be a user equipment (UE) or a device for machine-type communication (MTC). Alternatively or in addition, each of the transmitting and receiving stations may be configured to provide radio access and/or to wirelessly connect to each other, e.g., in an ad-hoc radio network or via 3GPP sidelinks.

(29) FIG. 3 shows a flowchart for a method 300 of transmitting data that is representable by N data symbols of a finite field. The size of the finite field is an integer power of a Mersenne prime.

(30) The data to be transmitted may be input to the method 300 as the N data symbols or as N data portions for inclusion in or computation of the N data symbols, respectively. Alternatively, the method 300 comprises an optional step 302 of segmenting the data into the N data symbols or the N data portions.

(31) The method 300 comprises a step 304 of determining, based on the N data symbols, a polynomial over the finite field. The method further comprises a step 306 of transmitting or initiating to transmit the data using more than N code symbols of the finite field. At least one of the more than N code symbols corresponds to an evaluation of the polynomial at a non-primitive element of the finite field. The transmission may be a unicast or broadcast transmission.

(32) The method 300 may be performed by the device 100, e.g., at the transmitting station of the radio network. For example, the modules 102, 104 and 106 may perform the steps 302, 304 and 306, respectively.

(33) FIG. 4 shows a flowchart for a method 400 of receiving data that is representable by N data symbols of a finite field. The size of the finite field is an integer power of a Mersenne prime.

(34) The method 400 comprises a step of receiving or initiating to receive the data using more than N code symbols of the finite field, wherein at least one of the more than N code symbols corresponds to an evaluation of a polynomial over the finite field at a non-primitive element of the finite field. It is not necessary that all of the more than N code symbols are successfully received. In a step 404 of the method 400, the N data symbols are determined by determining the polynomial based on at least N of the code symbols, which are successfully received.

(35) The method 400 may output the data as the N determined data symbols. Alternatively or in addition, the N data symbols, or N data portions respectively extracted or computed from the N data symbols, are concatenated in an optional step 406, resulting in the data.

(36) The method 400 may be performed by the device 200, e.g., at the receiving station. For example, the modules 202, 204 and 206 may perform the steps 402, 404 and 406, respectively.

(37) The method may be implemented as a retransmission protocol. Each of the code symbols is transmitted in the step 306 and/or received in the step 402 in a protocol data unit (PDU), e.g., a frame. The first N PDUs represent the data. The transmission and/or the (not necessarily successful) reception of the first N PDUs is referred to as the first transmission cycle or the data transmission. The transmission and/or the reception of the at least one further PDU, which includes the at least one code symbol resulting from evaluating the polynomial, is referred to as the second transmission cycle or the data retransmission. Data transmission and data retransmission are collectively referred to as data transfer.

(38) The data retransmission of the at least one PDU follows the data transmission of the first N PDUs, e.g., preemptively, responsive to a negative acknowledgment (NACK) from at least one of the receiving stations and/or upon expiration of a timer for an outstanding positive acknowledgment (ACK) from at least one of the receiving stations. The number of the at least one retransmitted PDU may depend on channel quality, the number of received NACKs (e.g., the maximum number of NACKs received from the same receiving station) and/or the number of overdue ACKs (e.g., the maximum number of ACKs outstanding for the same receiving station).

(39) The steps 304 and 306 encode the data represented or representable by a data word comprising the N data symbols into a code word comprising the more than N code symbols, i.e., N+K code symbols with K>0. The code rate is R=N/(N+K). The at least one code symbol, i.e., the K code symbols for the K PDUs of the retransmission, is or are based on an algebraic code defined by the polynomial over the finite field. The K PDUs for the retransmission are generated by the algebraic code. The code symbols of the algebraic code, i.e., the symbol alphabet of the algebraic code, are evaluations of the polynomial at non-primitive elements of the finite field.

(40) At least the K code symbols for the retransmission (e.g., all N+K code symbols) are generated by evaluating the polynomial at different integer powers of the non-primitive element. The L code symbols, with KLN+K, are generated by evaluating the polynomial at L different integer powers .sup.i of the non-primitive element . For example, the L code symbols correspond to evaluations of the polynomial at .sup.i for i=0, . . . , L1, respectively.

(41) In a first implementation, all code symbols are generated as evaluations of the polynomial (i.e., L=N+K). In a second implementation, not all code symbols are generated as evaluations of the polynomial (i.e., L<N+K). For example, only the K code symbols for the retransmission are generated as evaluations of the polynomial (i.e., L=K). In the second implementation, up to N code symbols may be directly derived from the N data symbols (i.e., without evaluating the polynomial). For example, N code symbols are equal to the N data symbols (e.g., for implementing a systematic code). The further L=K code symbols are generated by evaluating the polynomial.

(42) The retransmission protocol according to the methods 300 and 400 is advantageous for transferring the data from the transmitting station to one or more remote receiving stations. Implementations of the technique can achieve erasure correction properties similar or equal to Reed-Solomon codes. For example, the data retransmission according to the method 300 provides the receiving stations with a means to compensate for the loss of PDUs in the data transmission, independent of which specific PDUs are lost and independently for each receiving station. An implementation of the method 400 reconstructs or decodes the data in the step 404 based on successfully (i.e., correctly) receiving any N code symbols among the more than N code symbols. That is, any subset including N code symbols out of the set of the N+K code symbols is sufficient to decode the data. Thus, signaling overhead and latency can be reduced.

(43) For example, the step 302 splits a message as the data into 30 data portions, each including p bits. The PDUs may be implemented by frames. The frames are broadcasted to several remote nodes as the receiving stations. Suppose that a first node suffered the erasure of frames number 3 and 5, a second node suffered the erasure of frames number 11, 21 and 30 and a third node lost frame number 15. The retransmission protocol according to the methods 300 and 400 has the property that the initial data transmission of 30 frames, each including p bits for the respective data portion (if using a systematic code) or the respective code symbol (if using a non-systematic code), followed by the retransmission of K=3 frames, each including p bits for the respective code symbol, suffices for the each of the three remote nodes to recover the entire message. The K=3 code symbols transmitted in the data retransmission are generated using the algebraic code. Efficient algorithms for encoding and decoding are available, because the required arithmetic operations are performed in a finite field whose size is a Mersenne prime number.

(44) The polynomial (or polynomial function), F, may be determined by N coefficients c.sub.i,
F(X)=c.sub.1+c.sub.2X+c.sub.3X.sup.2+ . . . +c.sub.N-1X.sup.N-2+c.sub.NX.sup.N-1,
or more than N coefficients c.sub.i. In the step 304, N of the coefficients c.sub.i of the polynomial (e.g., all coefficients of the polynomial) are set to the N data symbols, respectively. Alternatively, the N (or more) coefficients of the polynomial F are determined by an injective linear mapping (i.e., a monomorphism) of the N data symbols. The injective linear mapping for determining the polynomial in the step 304 may be specified by a technical standard for the retransmission protocol in the radio network.

(45) In case the polynomial includes more than N coefficients, the further coefficients of the polynomial may be specified by the technical standard of the radio network or in a negotiation between the transmitting station and the receiving station when establishing radio connectivity. For example, the further coefficients of the polynomial may be computed based on a key for encrypting the data transfer.

(46) The L code symbols that are generated in the step 306 by evaluating the polynomial (i.e., at least the K code symbols for the retransmission, e.g., all N+K code symbols for transmission and retransmission) are determined by means of a generator matrix. The generator matrix maps the coefficients of the polynomial to the code symbols. The generator matrix includes N rows and L columns. The N.Math.L coefficients of the generator matrix include the integer powers of the non-primitive element.

(47) Optionally, if not all code symbols correspond to evaluations of the polynomial (i.e., for KL<N+K), N+KL columns of the identity matrix (of size N) are prepended or appended to the generator matrix, resulting in a generator matrix with N+K columns. In a first example for implementing a systematic code (i.e., L=K), the identity matrix of size N is prepended.

(48) In a second example for implementing a systematic code, all N+K code symbols correspond to evaluations of the polynomial (i.e., L=N+K). The monomorphism in the step 304 for mapping the N data symbols y.sub.i, i=1, . . . , N, to the N (or more) coefficients of the polynomial F is determined by (or fulfills):
y.sub.i=F(.sup.i-1) for i=1, . . . ,N.

(49) The generator matrix has full rank, i.e., the generator matrix is an injective linear mapping of the coefficients of the polynomial. In other words, any N columns of the generator matrix are linearly independent. For this reason, the device 200 is enabled to determine the N data symbols in the step 404 based on successfully receiving any N of the N+K code symbols.

(50) An element 0 of the finite field GF(M.sub.p).sup.q) is a primitive element, if .sup.i1 for all i=1, . . . , (M.sub.p).sup.q2. Otherwise, the element is non-primitive. The order of an element of the finite field GF(M.sub.p).sup.q) is the smallest positive integer r, so that .sup.r=1. The order of any primitive element is equal to (M.sub.p).sup.q1. The order r of any non-primitive element is less than (M.sub.p).sup.q1, i.e., 1r(M.sub.p).sup.q2. Up to r code symbols may be generated by evaluating the polynomial at integer powers of the non-primitive element, i.e., KLr.

(51) For example, a non-primitive element ca is 2 for p>3 (i.e., p7). The order r of =2 is equal to the exponent p (i.e., the bit length p for representing any one of the data symbols and/or code symbols). Hence, KLr=p, which is does not limit the number of K PDUs for the data retransmission, since typically p>>K. The number of K retransmitted PDUs may be specified by the standard of the radio network. For example, K=3.

(52) Alternatively or in addition to the advantageous erasure correction properties, same or further implementations of the technique efficiently generate the code symbols according to the steps 304 and 306 (which may be referred to as encoding) as well as efficiently determine the data symbols according to the step 404 (which may be referred to as decoding). The encoding and/or the decoding may be implemented using an integer arithmetic, e.g., including ones' complement for addition, subtraction, multiplication and/or any integer arithmetic described by the document Implementing Exact Calculations in Hardware by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-36, No. 6, pp. 764-768 and/or the document The Calculation of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-35, No. 5, pp. 478-482.

(53) The primality of the Mersenne prime M.sub.p=2.sup.p1 implies that the exponent p itself is a prime number. Below Table lists the smallest 14 Mersenne primes.

(54) TABLE-US-00001 Prime ex- ponent, p Mersenne prime, M.sub.p = 2.sup.p 1 2 3 3 7 5 31 7 127 13 8191 17 131071 19 524287 31 2147483647 61 2305843009213693951 89 618970019642690137449562111 107 162259276829213363391578010288127 127 170141183460469231731687303715884105727 521 68647976601306097149819007990813932172694353001433 05409394463459185543183397656052122559640661454554 97729631139148085803712198799971664381257402829111 5057151 607 53113799281676709868958820655246862732959311772703 19231994441382004035598608522427391625022652292856 68889329486246501015346579337652707239409519978766 587351943831270835393219031728127

(55) FIG. 5 shows a flowchart for an implementation of the method 300 as a retransmission protocol, which is combinable with any implementation or embodiment disclosed herein.

(56) In a substep 502 or implementation of the step 302, the data to be transmitted, e.g., a message, is split into N data symbols y.sub.n, n=1, . . . , N for N transmission PDUs (e.g., frames). Each of the transmission PDUs may contain code bits (i.e., the output of one or more inner encoders) for representing the corresponding data symbol (e.g., according to above-mentioned second implementation), a PDU check sequence (e.g., a CRC) and possibly padding. The technique is not limited by the exact nature and structure of the data contained in the transmission PDUs for carrying the corresponding data symbol.

(57) Each transmission PDU (e.g., each frame) contains a code symbols of p bits (or an integer multiple q>1) thereof, wherein M.sub.p=2.sup.p1 is a Mersenne prime. Hence, each transmission PDU can be considered as an element in the Galois field GF(M.sub.p) or GF((M.sub.p).sup.q) with q>1. That is, for each n=1, . . . , N: y.sub.n GF((M.sub.p).sup.q) with q1. Preferably, the method is implemented with N<p in order not to lose any erasure correction capabilities.

(58) Optionally, e.g., if a number of N frames resulting from the splitting in the substep 502 for a given p is too large, a subset of N frames is selected as a first group of frames for transmission in a substep 504. The further N-N frames may be transmitted by repeating the method 300. Otherwise, all N PDUs (e.g., frames) resulting from the splitting in the substep 502 define the first group of PDUs.

(59) In a substep 506 of the step 304, a non-primitive element GF(M.sub.p), or GF((M.sub.p).sup.q) for q>1, is chosen. A primitive element is any non-zero element such that .sup.M.sup.p.sup.1=1, but .sup.n1 if 0<n<M.sub.p1. If p3, it is advantageous to set =2, since in this case the number 2 (or its extension 2+2J+ . . . for q>1) is not a primitive element of GF(M.sub.p) (or GF((M.sub.p).sup.q) for q>1). Moreover, with the choice =2, multiplication by a or powers of may be implemented by shifts. It is not necessary that is determined at connection set-up or at runtime. Rather, the value for may be predefined by a standard and/or encoded in hardware.

(60) In a substep 508 or implementation of the step 304, a polynomial F(X)=y.sub.1+y.sub.2X+y.sub.3X.sup.2+ . . . +y.sub.N-1X.sup.N-2+y.sub.NX.sup.N-1 over GF((M.sub.p).sup.q) (for q1) is generated. According to above-mentioned second implementation, the coefficients of the polynomial are the data symbols or frames comprising the message to transmit. Evaluating the polynomial F(X) at any element GF((M.sub.p).sup.q) (for q1) generates another element F()GF((M.sub.p).sup.q) (for q1).

(61) In a substep 510 of the step 306, a set of K code symbols [F(.sup.0), F(.sup.1), F(.sup.2), . . . , F(.sup.K-1)] is generated by evaluating the polynomial F(X) at powers of the non-primitive . Preferably, K<p in order not to lose any erasure correction capabilities. The K code symbols define a second group of retransmission PDUs (e.g., frames).

(62) Each of the retransmission PDUs may contain code bits (i.e., the output of one or more inner encoders) for representing the corresponding code symbol (e.g., according to above-mentioned second implementation), a PDU check sequence (e.g., a CRC) and possibly padding. The technique is not limited by the exact nature and structure of the data contained in the retransmission PDUs for carrying the corresponding code symbol.

(63) A substep 512 of the step 306 includes a first cycle of transmissions for transmitting the frames [y.sub.1, y.sub.2, y.sub.3, . . . , y.sub.N] of the first group. An example for allocating the data symbols to the transmission PDUs (e.g., frames) is illustrated in below Table.

(64) TABLE-US-00002 Transmission Table Transmission # Transmitted PDU 1 y.sub.1 2 y.sub.2 . . . . . . N 1 y.sub.N1 N y.sub.N

(65) A substep 514 of the step 306 includes a second cycle of transmissions, i.e., the data retransmission by transmitting the code symbols [F(.sup.0), F(.sup.1), F(.sup.2), . . . , F(.sup.K-1)]. The data retransmission is either triggered by ACKs and/or NACKs from the remote nodes or is preemptive (i.e., performed in order to decrease the probability of failure in message decoding by the remote nodes).

(66) An example allocation of code symbols to retransmission PDUs is illustrated in below Table.

(67) TABLE-US-00003 Retransmission Table Retransmission # Transmitted PDU 1 F(.sup.0) 2 F(.sup.1) 3 F(.sup.2) . . . . . . K 1 F(.sup.K2) K F(.sup.K1)

(68) Below Table summarizes protocol parameters that may be set in any implementation or embodiment disclosed herein.

(69) TABLE-US-00004 Parameter Parameter description Embodiment s Number of elements in the M.sub.p = 2.sup.p 1 finite field (Mersenne prime) Element used to generate the code Non-primitive element word (order = p < s 1) N Number of transmission PDUs per N < p message K Number of retransmissions K < p

(70) The method 300, particularly the step 304 of determining the polynomial and the substep 510 of generating the code symbols for the step 306, may be referred to as an encoding process. Similarly, the device 100 may be referred to as an encoder.

(71) A systematic implementation of the encoding process 300 is described in more detail. The encoding process 300 is used to generate the code symbols for the second cycle of transmissions, i.e., the retransmission 514 in the step 306. A convenient choice for the non-primitive element is c=2, or a power of 2. This ensures that an efficient arithmetic is available, e.g., according to the document Implementing Exact Calculations in Hardware by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-36, No. 6, pp. 764-768 and/or the document The Calculation of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-35, No. 5, pp. 478-482.

(72) Below Tables illustrate the transmission 512 and the retransmission 514 for a systematic implementation using the non-primitive element =2.

(73) TABLE-US-00005 Transmission Table Transmission # Transmitted frame 1 y.sub.1 2 y.sub.2 . . . . . . N 1 y.sub.N1 N y.sub.N

(74) TABLE-US-00006 Retransmission Table Retransmission # Transmitted frame 1 F(1) 2 F(2) 3 F(2.sup.2) . . . . . . K 1 F(2.sup.K2) K F(2.sup.K1)

(75) The method 400, particularly the step 404, may be referred to as a decoding process. Similarly, the device 200 may be referred to as decoder. The decoding process 400 recovers data symbols (e.g., PDUs or frames in a systematic implementation) that are missing after the first transmission cycle 512 from the received code symbols, i.e. from the N received PDUs among the N+K transmitted PDUs (e.g., frames). Typically, the decoding process 400 is more involved than the encoding process 300.

(76) Suppose that an arbitrary receiving station (or remote node) has suffered K erasures from the first cycle of transmissions 512 (i.e., the data transmission, e.g., according to above Transmission Table). These lost frames are labeled by n.sub.i, wherein 1n.sub.1<n.sub.2< . . . <n.sub.KN. After reception of the second cycle of transmissions 514 (i.e., the data retransmission, e.g., according to above Retransmission Table), the following relations hold for the device 200 (e.g., at the receiving station).

(77) $y_{n_1}+y_{n_2}\mathrm{.Math.}+y_{n_K}=F\left(1\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i$$y_{n_1}.Math.2^{\left(n_1-1\right)}+y_{n_2}.Math.2^{\left(n_2-1\right)}\mathrm{.Math.}+y_{n_K}.Math.2^{\left(n_K-1\right)}=F\left(2\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(i-1\right)}$$y_{n_1}.Math.2^{2\left(n_1-1\right)}+y_{n_2}.Math.2^{2\left(n_2-1\right)}\mathrm{.Math.}+y_{n_K}.Math.2^{2\left(n_K-1\right)}=F\left(2^2\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(i-1\right)}$$\mathrm{.Math.}$$y_{n_1}.Math.2^{\left(K-2\right)\left(n_1-1\right)}+y_{n_2}.Math.2^{\left(K-2\right)\left(n_2-1\right)}\mathrm{.Math.}+y_{n_K}.Math.2^{\left(K-2\right)\left(n_K-1\right)}=F\left(2^{K-2}\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(K-2\right)\left(i-1\right)}$$y_{n_1}.Math.2^{\left(K-1\right)\left(n_1-1\right)}+y_{n_2}.Math.2^{\left(K-1\right)\left(n_2-1\right)}\mathrm{.Math.}+y_{n_K}.Math.2^{\left(K-1\right)\left(n_K-1\right)}=F\left(2^{K-1}\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(K-1\right)\left(i-1\right)}$

(78) That is, a linear system of K equations with K unknowns is obtained. The unknowns, y.sub.n.sub.1, . . . , y.sub.n.sub.K, are exactly the missing data symbols (e.g., PDUs or frames in a systematic implementation). The equation system can be represented in matrix form by defining A, , and as follows.

(79) $A=\left[\begin{array}{ccc}\begin{array}{cc}1& 1\\ 2^{\left(n_1-1\right)}& 2^{\left(n_2-1\right)}\\ 2^{2\left(n_1-1\right)}& 2^{2\left(n_2-1\right)}\end{array}& \mathrm{.Math.}& \begin{array}{c}1\\ 2^{\left(n_K-1\right)}\\ 2^{2\left(n_K-1\right)}\end{array}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ \begin{array}{cc}{2}^{\left(K-2\right).Math.\left(n_1-1\right)}& 2^{\left(K-2\right).Math.\left(n_2-1\right)}\\ 2^{\left(K-1\right).Math.\left(n_1-1\right)}& 2^{\left(K-1\right).Math.\left(n_2-1\right)}\end{array}& \mathrm{.Math.}& \begin{array}{c}{2}^{\left(K-2\right).Math.\left(n_K-1\right)}\\ 2^{\left(K-1\right).Math.\left(n_K-1\right)}\end{array}\end{array}\right]$$=\left[\begin{array}{c}{y}_{n_1}\\ y_{n_2}\\ \mathrm{.Math.}\\ y_{n_K}\end{array}\right]$$=\left[\begin{array}{c}F\left(1\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i\\ F\left(2\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(i-1\right)}\\ F\left(2^2\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(i-1\right)}\\ \mathrm{.Math.}\\ F\left(2^{K-2}\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(K-2\right)\left(i-1\right)}\\ F\left(2^{K-1}\right)-\underset{i{n}_1,n_2,\mathrm{.Math.},n_K}{\overset{N}{.Math.}}{y}_i.Math.2^{\left(K-1\right)\left(i-1\right)}\end{array}\right]$

(80) With this notation, the system of equations can be expressed in the form
A.Math.=.

(81) The system of equations has a unique solution , provided that the determinant of the matrix A is not zero. The solution contains the missing data symbols. The matrix A is a so-called Vandermonde matrix with a determinant given by
det(A)=.sub.a>b(2.sup.(n.sup.a.sup.1)2.sup.(n.sup.b.sup.1)).
Since a>b,
2.sup.(n.sup.a.sup.1)>2.sup.(n.sup.b.sup.1).
Defining
e.sub.a,b:=(2.sup.(n.sup.a.sup.1)2.sup.(n.sup.b.sup.1)),
the determinant of the matrix A is
det(A)=.sub.a>be.sub.a,b
Moreover,
0<e.sub.a,b2.sup.(n.sup.a.sup.1)1<M.sub.p,
which implies
.sub.a>be.sub.a,b0(mod M.sub.p),
since
.sub.a>be.sub.a,b>0.

(82) Since the arithmetic is performed over GF(M.sub.p), to show that the determinant does not vanish, one must also show that M.sub.p is not a factor of .sub.a>b e.sub.a,b. To see this, express the determinant as a product of prime factors. That is,
.sub.a>be.sub.a,b=p.sub.1.Math.p.sub.2 . . . p.sub.,
where 1, and p.sub.1, p.sub.2, . . . , p.sub. are prime. Moreover, either e.sub.a,b is prime, or can be written as the product of those primes. It follows that
e.sub.a,b<M.sub.p.Math.for all i=1, . . . ,:p.sub.i<M.sub.p.
Since M.sub.p is prime, from the fundamental theorem of arithmetic (i.e., existence of unique prime factorization for any positive integer), it follows that
.sub.a>b e.sub.a,b=p.sub.1.Math.p.sub.2 . . . p.sub.=q.Math.M.sub.p
(latter equality assuming the opposite, det(A)=0)
.Math.M.sub.p=p.sub.i for some 1i.

(83) This is a contradiction (reductio ad absurdum), since M.sub.p>p.sub.i. This concludes the proof that det(A)0 and, hence, the system of equations has a unique solution. In other words, whichever PDUs (e.g., frames) of the data transmission are missing, all data symbols (e.g., the missing PDUs or frames in a systematic implementation) can be recovered from just one set of retransmissions 514.

(84) By way of example, suppose that 2 PDUs of the data transmission 512 are erased, which PDUs shall be labeled by n and n+m, wherein 1n<n+mN. Then, any 2 code symbols of the K code symbols F(2.sup.0), F(2.sup.1), F(2.sup.2), . . . , F(2.sup.K-1) of the retransmission 514 are sufficient to recover all data symbols (e.g., the 2 missing data symbols corresponding to the 2 missing PDUs in a systematic implementation). That is, the entire data is recovered using any 2 of the retransmission PDUs.

(85) Indeed, suppose that the retransmission PDUs i and i+j are successfully received, wherein 1i<i+jK. Then, the erased PDUs n and n+m of the data transmission 512 in a systematic implementation can be recovered provided that the matrix

(86) $A=\left[\begin{array}{cc}{2}^{\left(i-1\right)\left(n-1\right)}& 2^{\left(i-1\right)\left(n+m-1\right)}\\ 2^{\left(i+j-1\right)\left(n-1\right)}& 2^{\left(i+j-1\right)\left(n+m-1\right)}\end{array}\right]$
is invertible. Factoring out 2.sup.(i-1)(n-1) in the first row and 2.sup.(i+j-1)(n-1) in the second row, the matrix becomes

(87) $\left[\begin{array}{cc}1& 2^{\left(i-1\right).Math.m}\\ 1& 2^{\left(i+j-1\right).Math.m}\end{array}\right],$
the determinant of which is

(88) $\det \left(\left[\begin{array}{cc}1& 2^{\left(i-1\right)m}\\ 1& 2^{\left(i+j-1\right)m}\end{array}\right]\right)=2^{\left(i+j-1\right).Math.m}-2^{\left(i-1\right).Math.m}=2^{\left(i-1\right).Math.m}\left(2^{j.Math.m}-1\right)$
Thus, the determinant is zero in GF(M.sub.p) if and only if 2.sup.j.Math.m=(1 mod M.sub.p). Since the order of 2 is p, 2.sup.jm=(1 mod M.sub.p) if and only if j.Math.m=(0 mod p). That is, the determinant vanishes if and only if j.Math.m is a multiple of p. Assuming the opposite of what is to be proven, j.Math.m=q.Math.p, for some positive integer q. Writing j.Math.m as a product of prime factors, j.Math.m=p.sub.1.Math.p.sub.2 . . . p.sub., wherein p.sub.1, p.sub.2 . . . , p.sub. are prime, it follows that p.sub.i<p for all 1i, since both j<K<p and m<N<p. But the fundamental theorem of arithmetic implies that p=p.sub.i for some 1i, which gives a contradiction. Hence, j.Math.m(0 mod p) and the determinant is non-zero in GF(M.sub.p). This shows that erasures in the second cycle transmissions can be tolerated without message loss, provided that no more than two erasures occur in the first cycle of transmissions. Numerical evidence suggests that any number of erasures in the second cycle transmissions (i.e., the data retransmission) can be tolerated without loss of the data (e.g., without message loss), provided that at least as many PDUs are successfully received in the data retransmission as lost in the data transmission (e.g., provided that fewer erasures occur in the first cycle of transmissions in case N=K).

(89) The encoding process 300 and the decoding process 400 use an arithmetic (i.e., addition, subtraction, multiplication and, optionally, division) in the Galois field GF(M.sub.p), or GF((M.sub.p).sup.q). In any implementation or embodiment described herein, the arithmetic may be implemented by an integer arithmetic modulo M.sub.p. More specifically, due to the very special form of the Mersenne prime M.sub.p, the arithmetic can be implemented very efficiently in digital circuitry, e.g., according to the document Implementing Exact Calculations in Hardware by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-36, No. 6, pp. 764-768 and/or the document The Calculation of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-35, No. 5, pp. 478-482.

(90) Alternatively or in addition, any embodiment or implementation disclosed herein may use at least one of the following arithmetic aspects.

(91) As to one arithmetic aspect, any element yGF(M.sub.p) can be represented by a binary string of length p, with the convention that the string consisting only of ones represents the same number (e.g., the same code symbol or the same data symbol) as the string consisting only of zeros. That is, any element y of the finite field (e.g., any code symbol, any data symbol and/or the non-primitive element) may be represented by a string of p bits: y=b.sub.1b.sub.2 . . . b.sub.p-1b.sub.p, wherein each b.sub.n{0,1}. The code symbols and/or data symbols may be represented by the so-called ones' complement notation used in Digital Signal Processing (DSP). Preferably, a scrambler or whitener prevents the occurrence of the all-zeros sequence.

(92) As to another arithmetic aspect, addition, subtraction and/or multiplication by powers of 2 are efficiently implemented using the ones' complement arithmetic. The additive inverse of y is obtained by flipping each of the bits in y. That is, y=b.sub.1b.sub.2 . . . b.sub.p-1b.sub.p, wherein b.sub.n:=1b.sub.n. Alternatively or in combination, addition may correspond to the ordinary addition of integers in binary notation, except that any carry bit appearing in the most significant end of the p-bit adder is injected into the least significant bit. Alternatively or in combination, multiplication of y by 2.sup.n is implemented by a circular shift of the bits representing y by n steps. If the least significant bit (LSB) is located at the right of a p-bit register, the shift is to the left if n>0 and to the right if n<0. Alternatively or in combination, multiplication modulo M.sub.p may be implemented by means of two p-bit registers and a 2p-bit multiplier. The multiplication may be performed according to the document Implementing Exact Calculations in Hardware by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-36, No. 6, pp. 764-768. Alternatively or in combination, the calculation of multiplicative inverses may be performed efficiently, e.g., as described in the document The Calculation of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-35, No. 5, pp. 478-482.

(93) Implementing the encoding process 300 and/or the decoding process 400 requires only the above-mentioned arithmetic operations. More specifically, the encoding process 300 may be implemented using only additions and circular shifts.

(94) The encoding process 300 and the decoding process 400, i.e. the retransmission protocol, are illustrated by means of a numerical example. The numerical example uses below parameters.

(95) TABLE-US-00007 p N K M.sub.p 7 2 5 4 127

(96) The data is transferred to one or more receiving stations (i.e., remote nodes).

(97) For the data transmission 512, the 5 data symbols y.sub.i are encoded (e.g., by an internal encoder) into N=5 frames, as shown in below Table.

(98) TABLE-US-00008 Transmission Table Binary representation in GF(127) Data Symbols for transmission frames y.sub.1 0010010 y.sub.2 0000011 y.sub.3 0110101 y.sub.4 0010111 y.sub.5 1011100

(99) The polynomial of the step 508 is of degree N1.
F(X)=y.sub.1+y.sub.2X+y.sub.3X.sup.2+y.sub.4X.sup.3+y.sub.5X.sup.4.

(100) The encoding process 300 for the data retransmission 514 is based on the N=5 data symbols y.sub.i representing the data of the data transmission 512. The polynomial is used in the step 510 to construct the code word.

(101) The K=4 frames for the data retransmission are computed by evaluating the polynomial at integer powers of the non-primitive element =2. Below Table includes the resulting code symbols for the data retransmission 514.

(102) TABLE-US-00009 Retransmission Table Binary representation in GF(127) Code Symbols for transmission frame F(2.sup.0) 0111110 F(2.sup.1) 1110010 F(2.sup.2) 1111001 F(2.sup.3) 1111000

(103) The computation of F(2.sup.3) is shown as an example. By definition,
F(2.sup.3)=.sub.i=1.sup.5y.sub.i.Math.2.sup.3(i-1).

(104) The sum on the right-hand side consists of 5 terms, and each term is displayed in below Table. Multiplication by powers of 2 is implemented by means of circular left shifts.

(105) TABLE-US-00010 i y.sub.i y.sub.i .Math. 2.sup.3(i1) 1 0010010 0010010 2 0000011 0011000 3 0110101 1011010 4 0010111 1011100 5 1011100 0010111

(106) The 4th retransmission frame carrying the code symbol F(2.sup.3) is obtained in the step 510 by the addition of the numbers in the third column of above Table. The sum is computed step by step below:

(107) TABLE-US-00011 0010010 +0011000 =0101010

(108) The next addition shows how a carry bit is injected into the LSB at the adder.

(109) TABLE-US-00012 0101010 +1011010 =0000101 0000101 +1011100 =1100001 1100001 +0010111 =1111000
Hence, F(2.sup.3)=1111000.

(110) As exemplified above, the encoding process 300 requires only additions and circular shifts.

(111) The decoding process 400 is exemplified by continuing above numerical example. Suppose that the third and fifth frames of the data transmission (i.e., the data symbols y.sub.3 and y.sub.5) are erased, and that the first and fourth retransmissions (i.e., the code symbols F(2.sup.0) and F(2.sup.3)) are received. Using the above-defined notation, the inhomogeneity, , of the linear equation system is computed:

(112) $=\left[\begin{array}{c}F\left(1\right)-y_1-y_2-y_4\\ F\left(2^3\right)-y_1-y_2.Math.2^{3\left(2-1\right)}-y_4.Math.2^{3\left(4-1\right)}\end{array}\right]=\left[\begin{array}{c}0010010\\ 1110001\end{array}\right].$

(113) For illustration, the computation of the first term is performed as follows:
(1)=F(1)y.sub.1y.sub.2y.sub.4
=0111110001001000000110010111
According to the implementation of the arithmetic, the negative of a number is obtained by flipping the bit polarizations, i.e.,
(1)=0111110+1101101+1111100+1101000.

(114) The addition, using ones' complement addition with injection of a carry bit at the most significant bit (MSB) side of the adder into the LSB, yields (1)=0010010.

(115) In order to recover the two data symbols y.sub.3 and y.sub.5 erased in the data transmission 512 (i.e., the erased transmission frames), the decoder 200 solves the following system of equations in the finite field GF(127):

(116) $\left[\begin{array}{cc}1& 1\\ 2^{3\left(3-1\right)}& 2^{3\left(5-1\right)}\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=\left[\begin{array}{c}0010010\\ 1110001\end{array}\right].$
Multiplying the second row by 2.sup.5 results in:

(117) $\left[\begin{array}{cc}1& 1\\ 2& 2^7\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=\left[\begin{array}{c}0010010\\ 1000111\end{array}\right],$
wherein 2.sup.7=2.sup.p=1 (mod M.sub.p). Hence, the system of equations

(118) $\left[\begin{array}{cc}1& 1\\ 2& 1\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=\left[\begin{array}{c}0010010\\ 1000111\end{array}\right]$
is to be solved in the step 404. Subtracting the second equation from the first results in the first missing data symbols:
y.sub.3=10001110010010
=1000111+1101101=0110101.
The last missing data symbols is computed according to
y.sub.5=0010010y.sub.3
=0010010+1001010=1011100.

(119) Thus, the two erased frames y.sub.3 and y.sub.5 of the data transmission 512 are correctly decoded in the step 404 from the first cycle of transmissions 512 and the second cycle of transmissions 514 (i.e., the data transfer) by the decoder 200.

(120) More generally, the system of equations in GF(M.sub.p),

(121) 0$\left[\begin{array}{cc}1& 1\\ 1& 2^k\end{array}\right]\left[\begin{array}{c}{y}_a\\ y_b\end{array}\right]=\left[\begin{array}{c}{r}_a\\ r_b\end{array}\right],$
yields y.sub.b.Math.(2.sup.k1)=r.sub.br.sub.a and, hence, the solution requires the computation of the inverse (2.sup.k1).sup.1 in GF(M.sub.p). This computation can be performed efficiently as described in the document The Calculation of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime by J. J. Thomas et al., IEEE Transactions on Computers, Vol. C-35, No. 5, pp. 478-482.

(122) Some distinguishing features of embodiments of the technique are outlined over existing Reed-Solomon codes, e.g., as described in the document An Improved Broadcast Retransmission Protocol by J. J. Metzner, IEEE Transactions on Communications, Vol. COM-32, No. 6, pp. 679-683 (Metzner protocol).

(123) TABLE-US-00013 Parameter Parameter description Protocol of Metzner Embodiment s Number of elements in 2.sup.B M.sub.p = 2.sup.p 1 the Field (power of 2) (Mersenne prime) Element used to Primitive Non-primitive generate the code word element element (order = (order = p < s 1) s 1) N Number of N < s N < p transmission frames for the data K Number of K < s N K < p retransmissions frames

(124) Two synergetic distinguishing features can be of fundamental and/or practical importance. First, the element ca used to generate the code word is non-primitive. Second, the number of elements in the finite field (i.e., its size) is a Mersenne prime.

(125) The Metzner protocol follows the methodology of Reed-Solomon coding and employs a primitive element. Since the number of elements is a power of 2, each element in the field can be interpreted as a tuple of bits. The code-word generation, the arithmetic and the algorithmic properties of encoder and decoder are highly dependent upon these parameters. In general, the arithmetic in Galois fields whose size is a power of 2 is involved and significantly different from ordinary integer arithmetic. In contrast, the technique uses a non-primitive element. Even though the element ca is non-primitive, the decoder 200 can recover erased PDUs. Furthermore, the number 2 is a non-primitive element (except for the case p=2) that is well-suited to generate the code symbols (i.e., the PDUs, e.g., the frames) for the retransmission 514. This together with the fact that the size of the finite field is a Mersenne prime, enables the use of fast integer arithmetic, e.g., including a ones' complement representation of integers, while ensuring that the generated code symbols possess the desirable property that any missing PDU can be recovered from the same group of retransmitted PDUs.

(126) Any embodiment or implementation herein may be extension to composite PDU sizes (e.g., composite frame sizes). In the discussion above, each PDU comprises p bits, wherein M.sub.p=2.sup.p1 is a Mersenne prime number (and, hence, p is also a prime number). It is possible to extend the retransmission protocol to certain composite (i.e., not prime) PDU sizes.

(127) Some mathematical preliminaries are useful to describe such extended embodiments. The Legendre symbol,

(128) $\left(\frac{-1}{c}\right),$
describes whether or not 1 is a quadratic residue modulo c by equating to +1 and 1, respectively. For the Mersenne prime M.sub.p, the Legendre symbol

(129) $\left(\frac{-1}{M_p}\right)=-1,$
since M.sub.p 3 (mod 4) because 2.sup.p 0 (mod 4). That is, 1 is not a quadratic residue modulo the Mersenne prime M.sub.p. In other words, the equation x.sup.2=1 does not have a solution modulo M.sub.p. Hence, the polynomial f(x)=x.sup.2+1 is irreducible in GF(M.sub.p).

(130) Therefore, the Galois field GF((M.sub.p).sup.q) with q=2 is representable by adjoining a root, J, of the polynomial f(x)=x.sup.2+1 to finite field GF(M.sub.p). Any element yGF((M.sub.p).sup.2) can be written in the form y=a+b.Math.J, wherein a, bGF(M.sub.p). The arithmetic in GF((M.sub.p).sup.2) is reminiscent to the arithmetic of complex numbers, except that real-part arithmetic operations are replaced by the arithmetic operations in GF(M.sub.p). For example, for any y.sub.1=a+b.Math.J and y.sub.2=c+d.Math.J, wherein a, b, c, dGF(M.sub.p),

(131) y.sub.1.Math.y.sub.2=(acbd (mod M.sub.p))+(ad+bc (mod M.sub.p)).Math.J. Consequently, the arithmetic in GF((M.sub.p).sup.2) is implemented efficiently using ones' complement arithmetic.

(132) Furthermore, any element yGF((M.sub.p).sup.2) is represented or representable by a string of 2p bits:
y=(b.sub.1b.sub.2 . . . b.sub.p-1b.sub.pc.sub.1c.sub.2 . . . c.sub.p-1c.sub.p),
wherein each b.sub.i, c.sub.i{0,1}.

(133) Any embodiment or implementation of the retransmission protocol may be extended as follows. First, the data (e.g., a message) to be transmitted is split into N transmission PDUs (e.g., frames) carrying the data symbols y.sub.n, n=1, . . . , N in the step 302. Each transmission PDU contains 2p bits, wherein M.sub.p=2.sup.p1 is a Mersenne prime. Hence, each transmission PDU can be considered as an element in the Galois field GF((M.sub.p).sup.2). That is, y.sub.nGF((M.sub.p).sup.2), n=1, . . . , N.

(134) Second, a non-primitive element GF((M.sub.p).sup.2) is chosen. For p3, it is advantageous to set =2+2.Math.J, since in this case the number 2+2.Math.J is not a primitive element of GF((M.sub.p).sup.2), its powers are easily computed and multiplication by powers of can be implemented by circular shifts. Other choices, such as =2+J, are also possible.

(135) Third, a polynomial F(X)=y.sub.1+y.sub.2X+y.sub.3X.sup.2+ . . . +y.sub.N-1X.sup.N-2+y.sub.NX.sup.N-1 over GF((M.sub.p).sup.2) is generated. The coefficients of the polynomial are the data symbols (e.g., the transmission PDUs) representing the data to be transmitted. Evaluating the polynomial at any element GF((M.sub.p).sup.2), generates another element F()GF((M.sub.p).sup.2).

(136) Fourth, a set of K code symbols [F(.sup.0), F(.sup.1), F(.sup.2), . . . , F(.sup.K-1)] is generated by evaluating the polynomial F(X) at powers of the non-primitive . Preferably, the number of retransmissions, K, is less than the order of the non-primitive , order(), in order not to lose any erasure correction capabilities.

(137) Fifth, in a first cycle of transmissions 512, the N transmission PDUs including the data symbols [y.sub.1, y.sub.2, y.sub.3, . . . , y.sub.N], respectively, are transmitted. Sixth, in a second cycle of transmissions 514, the code symbols [F(.sup.0), F(.sup.1), F(.sup.2), . . . , F(.sup.K-1)] are transmitted. These retransmissions are either triggered by ACKs or NACKs from the receiving stations or are preemptive (i.e., performed to decrease the probability of failure in message decoding by the remote nodes).

(138) In an implementation with the number of frames N<order() and the number of retransmissions K<order(), any receiving station including an instance of the device 200 is enabled to recover any set of K transmission PDUs erased in the first transmission cycle 512, provided it has received the K retransmission PDUs transmitted in the second transmission cycle 514. Indeed, above considerations as to the regularity of the Vandermonde matrix may also be applied to the extended embodiments, which demonstrates that the corresponding Vandermonde matrix of the extended embodiment is invertible in GF((M.sub.p).sup.2).

(139) FIG. 6 shows a schematic block diagram of a transmitting station 600 including the device 100 and a receiving station 650 including the device 200 according to a first embodiment. The first embodiment is compatible with any of the above-mentioned implementations or embodiments.

(140) The first embodiment implements the retransmission protocol on the physical (PHY) layer of a protocol stack for the data transfer. The data 602 to be transmitted is provided by a layer that is higher than the PHY layer (e.g., a MAC layer or a RLC layer) in the protocol stack. The segmentation module (or segmenting unit) 102, which may be included in the device 100, splits the data 602 according to the step 302, resulting in the data word 604 comprising N data symbols 606.

(141) The device 100, i.e., the encoder of the retransmission protocol, generates the code word 608 comprising the N+K code symbols 610 for the data transfer. While the N+K code symbols are expressly indicated in the block diagram of FIG. 6, up to N of the code symbols can be identical to the data symbols 606 in a systematic implementation.

(142) In the first embodiment of FIG. 6, the code symbols 610 are input to a conventional channel encoder (e.g., as an inner encoder) and/or modulator, which unit is generically referred to by reference sign 612. That is, the device 100 is arranged upstream of the conventional unit 612, which transmits the N+K PDUs 624 (e.g., frames) carrying the N+K code symbols 610, respectively.

(143) The code word 658, as received at the receiving station 650, may include any subset of successfully received N code symbols 660. The device 200, i.e., the decoder of the retransmission protocol is arranged downstream of a conventional unit 662 for channel decoding and/or demodulation. Based on any received N code symbols 660, the device 200 outputs the data word 654 comprising the N data symbols 656. A concatenation module (or concatenating unit) 206 combines the N data symbols 656 to recover the data 662.

(144) Optionally, the device 200 reports for each successfully received PDU 624 an ACK signal, for each corruptly received PDU 624 a NACK signal 626 and/or a number of successfully and/or corruptly received PDUs 624 to the device 100. While the report may be transmitted and received through the same transceiver chains also used for the data transfer, the report may also be sent using another communication channel. Based on the report received from one or more receiving stations 650, the device 100 control the number K of retransmission PDUs.

(145) FIG. 7 shows a schematic block diagram of a transmitting station 600 including the device 100 and a receiving station 650 including the device 200 according to a second embodiment. The second embodiment is compatible with any of the above-mentioned implementations or embodiments. Equivalent and/or interchangeable features are indicated by like reference signs.

(146) The second embodiment implements the retransmission protocol on the PHY layer of the protocol stack for the data transfer. The data 602 to be transmitted may be provided by the MAC or RLC layer of the protocol stack.

(147) The device 100 functions as both (e.g., outer) encoder for the retransmission protocol and (e.g., inner) channel encoder. Preferably, the evaluations of the polynomial provide code symbols 610 that are significantly longer (e.g., about 3-fold longer) than the data symbols (e.g., the data portions) provided by the segmenting unit 102. For example, the data symbols are complemented by a fixed bit string to match the bit length p that is input to the device 100. Thus, the generated code symbols 610 are in a proper subset of the finite field.

(148) The data 602 to be transmitted may be a transport block (TB). Each data portion for one of the data symbols 606 may be a code block (CB).

(149) A conventional modulator 612 may be arranged downstream of the device 100. Alternatively, the device 100 outputs the code symbols 610 as modulation signals.

(150) At the receiving station 650, the device 200 functions as both (e.g., outer) decoder for the retransmission protocol and (e.g., inner) channel decoder. Received code symbols 660 that are not within the subset of the finite field, are marked as erased (or buffered at the demodulator 662 for soft-combining with further retransmission versions of the same code symbol). As soon as N code symbols 660 are successfully received, the device 200 outputs the N data symbols 656.

(151) FIG. 8 shows a schematic block diagram of a transmitting station 600 including the device 100 and a receiving station 650 including the device 200 according to a third embodiment. The third embodiment is compatible with any of the above-mentioned implementations or embodiments. Equivalent and/or interchangeable features are indicated by like reference signs.

(152) The third embodiment implements the retransmission protocol on a layer higher than the PHY layer, e.g., on the MAC or RLC layer. The device 100 functions as a PDU encoder, e.g., for MAC PDUs or RLC PDUs.

(153) The data 602 to be transmitted is provided by the RLC layer or a packet data convergence protocol (PDCP) layer, e.g., according to 3GPP LTE. For example, the data is an RLC service data unit (SDU). The segmenting unit 102 may be implemented by the RLC layer.

(154) The device 100, e.g., in an implementation on the RLC layer, may be spaced apart from the transmitting station 600. The RLC layer may be implemented by a server, e.g., in a core network coupled to the transmitting station 600. The device 100 initiates the transmission in the step 306.

(155) The code symbols 610 output by the device 100 in the step 306 are processed on a lower layer, e.g., the MAC or PHY layer. At the receiving station 650, the device 200 receives the code symbols 660 from the lower layer. Based on the successfully received code symbols, the device 200 output the data 662 (or the data symbols 656 thereof). While functionality of the lower layer may be collocated with the receiving station 650, the successfully received code symbols may be forwarded to the device 200 that spaced apart from the receiving station 650.

(156) FIG. 9 shows a schematic block diagram for an embodiment of the device 100. The device 100 comprises one or more processor(s) 904 for performing the method 300 and memory 906 coupled to the processor(s) 904. For example, the memory 906 may be encoded with instructions that implement at least one of the modules 102, 104 and 106.

(157) The one or more processor(s) 904 may be a combination of one or more of a microprocessor, controller, microcontroller, central processing unit, digital signal processor, application specific integrated circuit, field programmable gate array, or any other suitable computing device, resource, or combination of hardware, microcode and/or encoded logic operable to provide, either alone or in conjunction with other components of the device 100, such as the memory 906, data transmitter functionality. For example, the one or more processor(s) 904 may execute instructions stored in the memory 906. Such functionality may include providing various features and steps discussed herein, including any of the benefits disclosed herein. The expression the device being operative to perform an action may denote the device 100 being configured to perform the action.

(158) As schematically illustrated in FIG. 9, the device 100 may be embodied by the transmitting station 600. The transmitting station 600 comprises a radio interface 902 coupled to the device 100 for radio communication with one or more receiving stations.

(159) In a variant, e.g., as schematically illustrated in FIG. 10, the functionality of the device 100 is provided by a node of the radio network. That is, the node performs the method 300. The functionality of the device 100 is provided by the node to the transmitting station 600, e.g., via the interface 902 or a dedicated wired or wireless interface.

(160) FIG. 11 shows a schematic block diagram for an embodiment of the device 200. The device 200 comprises one or more processor(s) 1104 for performing the method 400 and memory 1106 coupled to the processor(s) 1104. For example, the memory 1106 may be encoded with instructions that implement at least one of the modules 202, 204 and 206.

(161) The one or more processor(s) 1104 may be a combination of one or more of a microprocessor, controller, microcontroller, central processing unit, digital signal processor, application specific integrated circuit, field programmable gate array, or any other suitable computing device, resource, or combination of hardware, microcode and/or encoded logic operable to provide, either alone or in conjunction with other components of the device 200, such as the memory 1106, data receiver functionality. For example, the one or more processor(s) 1104 may execute instructions stored in the memory 1106. Such functionality may include providing various features and steps discussed herein, including any of the benefits disclosed herein. The expression the device being operative to perform an action may denote the device 200 being configured to perform the action.

(162) As schematically illustrated in FIG. 11, the device 100 may be embodied by the receiving station 650. The receiving station 650 comprises a radio interface 1102 coupled to the device 200 for radio communication with a transmitting station.

(163) In a variant, e.g., as schematically illustrated in FIG. 12, the functionality of the device 200 is provided by a node of the radio network. That is, the node performs the method 400. The functionality of the device 200 is provided by the node to the receiving station 650, e.g., via the interface 1102 or a dedicated wired or wireless interface.

(164) As has become apparent from above description, embodiments of the technique provide a retransmission technique that achieves the same erasure correction effects of existing retransmission protocols with significantly less computational complexity. The technique can significantly reduce the computational complexity compared to existing MDS codes and optimal fountain codes.

(165) Same or further embodiments require only a simple systemization, and the necessary arithmetic operations for encoding and decoding can be performed efficiently, e.g., using an arithmetic well-suited for low-end loT devices.

(166) The technique can be implemented as a retransmission protocol, e.g., for unicasting or broadcasting on erasure channels. The technique is beneficially implemented in a wireless broadcast communication. Even if the transmitting station does not know whether or not a particular receiving station has received a certain PDU, by broadcasting the more than N PDUs, the transmitting station can ensure with high probability that the one or more receiving stations have successfully received sufficient code symbols to decode the data. The number q>N of transmitted PDUs allows controlling the probability.

(167) The technique can be implemented in stand-alone and ad-hoc networks, e.g., meshed Bluetooth networks, or in communication systems according to 3GPP LTE and newly developed radio access network such as 3GPP 5G NR.

(168) Many advantages of the present invention will be fully understood from the foregoing description, and it will be apparent that various changes may be made in the form, construction and arrangement of the units and devices without departing from the scope of the invention and/or without sacrificing all of its advantages. Since the invention can be varied in many ways, it will be recognized that the invention should be limited only by the scope of the following claims.