GB2216752A - Forward error correction in packet switched communications - Google Patents

Abstract

In a packet switched network, information is encoded in accord with a maximum distance separable code and the redundancy forms r packets of length L symbols additional to the K packets of length L symbols comprising the original information, whereby any K packets suffice to reconstruct the original information. <IMAGE>

Description

FORWARD ERROR CORRECTION IN PACKET-SWITCHED COMMUNICATIONS The invention is generally in the area of digital communications and particularly applies to the application of forward error correction to packet switched networks.

Packet switched networks are a well known type of communication net, intended to spread communications traffic over the available links to obtain the benefit of enhanced efficiency.

Conventionally, packets containing defined information content include a parity checkword to confirm the integrity of the packet content. Upon detection of error at the receiver, the conventional system initiates a request from the receiver for re-transmission of the putative erroneous packet(s). Eventually all packets are received without error. Such a system is known as an ARQ system. Characteristic of such systems is the need for a return path (receiver to transmitter) to close the loop.

Distinct from a strict ARQ approach to error control is the broad class of forward error correction (hereafter FEC). The essence of an FEC technique is that recovery of correct information from erroneous data is functionally executed at the receiver on the basis of the totality of received information. No return path from receiver to transmitter is required. An FEC code operates by encoding original information at the data source by which means redundancy is generated and annexed to the original information for transmission. At the data sink the received data is processed in an FEC decoder to determine whether error is present, the specific location(s) of the error and finally to correct the same using the whole of that received information otherwise correctly received.Within the subject matter of the present invention, it should be noted that error detection is common to both ARQ and FEC systems. FEC coding and apparatus is the subject of a vast literature: as a general reference, see E.R. Berlekamp, Algebraic Coding Theory, Agaean Park Press, 1984.

The time required for transmission of the original information depends strongly upon the number of error-free channels available. In an environment where the channels are subject to noise, fades, jamming and like corrupting influences, the time required for successfully transmitting a given set of packets may become lengthy due to necessity for re-transmission where error is detected at the destination terminal.

In another known arrangement for recovering information from an error prone channel it is proposed to encode each packet with an n,k error correcting code. Each time a packet is determined to be defective, transmission is repeated and after L repetitions, the set of L defective repetitions is regarded as an erroneous nL,k codeword. Weighting of each of the L repetitions is accomplished at the receiver and if the information is still not recoverable, repetition continues, eg. L is increased. This approach is discussed by Chase, IEEE COM-33, no. 5, May 1985.

For packet switched systems it is also known to reduce the amount of transmitted redundant error correction information. In these prior art schemes, a systematic error correcting code is employed in the encoder to generate redundant data and append the same to the original information to yield a codeword. An example of this class of prior art is an approach wherein an information block with error detection parity is initially transmitted. If this is received without detected error, the next information block (with respective error detection parity) is transmitted. In the event that the block is detected to contain error, the receiver signals an alarm back to the transmitter. The transmitter then computes redundancy for the block in error, in accord with some systematic error correction code and transmits same to the receiver.The receiver then operates upon the erroneous information block using the separately received (and possibly corrupted) redundant information. Successful communication based upon such schemes assumes that the noise level does not routinely exceed the error correction capability of the selected error correcting code and that the ARQ mechanism achieves a reasonable throughput. These assumptions are appropriate to a rather benign communications environment, whereas a more severely disruptive environment is the contemplated context of the present invention.

The present invention incorporates forward error correction in combination with packet switched communications techniques. A system of this type greatly increases the level of recovery of information transmitted over error prone channels and, thereby decreases the time required to transmit an entire message. In one embodiment of the present invention, K packets to be transmitted in a packet switched network are first subject to an encoding procedure in accord with a maximum distance separable code, to yield K + r packets, each of length L symbols. That is, r redundant packets comprising the redundancy resulting from the encoding procedure are appended to the original K information packets. At the receiver, packets are accepted if an error detection protocol indicates no error and rejected otherwise.From the maximum distance separable property of the code, error correction decoding will be effective to retrieve the information content whenever any K or more packets of the K + r packets are received and accepted as correct. Thus the loss of a packet due to a missing link can be minimized because it is only necessary to successfully receive K out of K + r packets.

In the context of both random and non-random disturbances it is preferred to operate on each of K packets transmitted in the packet switched network according to an embodiment employing a concatenated code. All packets are first encoded in an appropriate maximum distance separable code (the "outer" code) to yield K + r packets, each of length L symbols as described above. The K + r packets are then subject to a further encoding procedure to produce K + r packets, each of extended length L + c symbols. The receiver processing each packet determines the errata content of each packet and performs correction by an appropriate decoding technique. Upon receipt of sufficient information (at least K packets to recover the original information) outer decoding is initiated.If fewer than K of the K + r packets are received without error, or cannot be corrected by the error correction decoding of the outer decoder, then a re-transmission request is initiated to supply the deficiency in correct packets The communication link may be terminated upon receipt of at least K correct (correctable) packets of the particular original transmission.

The present invention will now be described by way of example with reference to the accompanying drawings, in which: Fig. 1 schematically illustrates apparatus embodying the invention; Fig. 2 compares performance of the invention with a conventional ARQ system for K=16 and N=32; and Fig. 3 compares performance of the invention with a conventional ARQ system for K=32 and N=64.

The invention is concisely explained in reference to Fig. 1. A data stream of information is divided into strings, each a fixed number of symbols in length, by packet former 14 acting on the input data stream. The resulting packets are encoded through maximum distance separable error correction encoder 16 to yield redundancy-forming r further packets in a first embodiment. As indicated by (16), the further r packets are annexed to the original K packets. Alternatively, packets of extended length (a second embodiment) may be realized with redundancy derived from an inner encoder 20 wherein redundancy is annexed to each packet. For example, redundancy characters IRi, i=l....K+r are indicated in format description (20). The selection of the inner code is not a critical aspect of the embodiment. It is simply desired to implement a modicum of forward error protection to individual packets ( in this concatenated embodiment) to gain earlier acceptance of any given packet which may have suffered correctable error without requiring a retransmission. (For convenience, Fig. 1 describes both of these embodiments. The format described at (20) differs from that described at (18) only by the appending of the inner redundancy characters IRi to the ith packet.) After encoding, an error detection check generator 18 computes a parity check symbol and appends same to the corresponding packet as indicated from format description (18). Packets are retained in packet store 22 to provide for a possible re-transmission requirement. The packets are then distributed by transmitter 24 over a network 26, to receive 28.By this is meant that the network 26b may comprise a plurality of w communication links.

Different ones of the k+r packets are transmitted through different ones of the w communication links in the network 26. The w links may be in parallel, as, for example, w individual RF channels, if the network 26 is an RF serial, as, for example, w time windows in the same RF channel. At the receiver, the received packets are processed within conventional network protocols in error detector 32 to ascertain the presence of error in received packets. Operating upon the result of error detector 32, a packet rejectorlacceptor 34 retains packets without error in packet store 36 and indicates to retransmit requestor 38 the condition of the most recently processed packet. It is entirely equivalent to accumulate error detection indications from the output of error detector 32 or to ascertain from the convent of packet store 36 whether enough information has been successfully received.In the event that fewer than K packets have been received without error, retransmit requestor 38 initiates a retransmission request to the sending apparatus. The nature of this request may be preferably directed to specific packets received in error, although a retransmission of all packets is an acceptable alternative. Error correction decoder 40 treats a corrupted packet as an erasure and attempts to recover the information content through the decoding process. When sufficient information has been received to reconstruct the original information, the receiver initiates a termination of message condition at module 42. It is entirely equivalent for the purpose of this invention, whether the termination is effected by failure to assert a request for transmission of further packets or whether a positive message termination code is asserted.It is also a matter of design choice whether encoding precedes division of the original information into packets or follows such packetizing.

The presence of inner packet decoder 30 according to the second embodiment of the invention merely hastens the accumulation of a "sufficient" number of correct packets for the operation of the MDS packet decoder 40 by obviating one or more retransmit requests which might possibly be otherwise required.

Performance of the invention is best illustrated through comparison with a conventional ARQ model. Consider a packet switched network subject to severe jamming. Each packet experiences a probability p for loss or. randomization. A model ARQ system is defined as follows: original information forming K packets is transmitted (in parallel for example) and transmission is re-initiated periodically until the receiver of the model system acknowledges correct receipt. The return path for the model system may be assumed to be free of disturbance: therefore a packet received without error is acknowledged and will not be re-transmitted. The performance of this model system may be parameterized in terms of the time required to deliver the original information under conditions prescribed by the value of p.The performance curves a and b of Fig. 2 and 3 were computed following a model based upon the theory of Markov chains applied to the present problem. These curves show respectively the performance of the model ARQ system (curve a) and that of the invention (curve b). Given a probability p, for the loss of any single packet in the transmission, and given that reception is an independent process, what is the average number of transmissions required before there is sufficient information for decoding to proceed? Consider a process-characterized by K states E0, E1, E2, E3 ... EK2, F. The subscript indicates how many packets have been received at that instant. The state F represents the reception of K or more packets, at which point decoding may commence.At the beginning of the process the state Eg obtains with probability 1.

The first set of transmissions may change the state of Ei (including state F possibly) with the probability of the transition to Ei depending upon i. For a subsequent transmission, starting from a knowledge of i packets (from the preceding set of transmissions), there is a probability p(j,k) of reaching the state with k packets. Because packets cannot be lost, once received, p(j,k) - O if k < j. A transition to state F terminates the process and in the theory of Markov chains, the state F is known as an absorbing barrier.

For k j, the probability of p(j,k) has the significance of receiving exactly the k-j packets of the N-j packets not already received.

Assume that the probability p for missing a packet is given by

p(j,k) = q(k-j) where q = l-p

1"1 al and = This results in an upper triangular matrix M of dimension K x K where each row sums to 1. The probability of being in a given state after starting from an initial vector I is P(n) = IM" The probability of reaching the state F at the nth transmission is taken as q(n), eg. the last entry in P(n). The probability of reaching state F at time n and not before time n is given by r(n) = q(n) q(n-l) and q(O) = O. Then the expected time to transmit the message is

and it is this quantity which is illustrated.

Curve a of Fig. 2 illustrates this performance level. The abscissa p is expressed as the fraction of network links successfully jammed with resulting destruction of information propagated on such link. For the purpose of exposition, the link is regarded as either perfect or destroyed.

Having established a reference system, the performance of the invention may be measured with respect thereto.

The first embodiment of the invention operates to encode the K packets of original information through a maximum distance separable code to yield N > K packets of information for transmission. For the purpose of comparison with the model system the transmission will be assumed to be parallel with the N packets subject to the (same) standard ARQ protocols including a checkword procedure by which the received packets are recognizable as either correct or unreliable (erased). A maximum distance separable code provides the condition that any K (or more) packets correctly received are sufficient to recover the original information.

Performance of the invention in relation to the model ARQ system is shown in curve b of Fig. 2 wherein K=16 as for curve a and N=32. It is noteworthy for this example, that if fewer than 30% of the channels are successfully jammed, no more than negligible delay is introduced in the time required for transmission of the information. The integrity of each link is thus rendered more robust by the FEC coding. Successful jamming of a given information transmission therefore requires a much greater effort.

Fig. 3 shows a comparison similar to Fig. 2 for the case K = 32 and N = 64.

Merely to further illustrate the fundamental advantage of the invention, consider a simple example. A conventional ARQ system transmits a 16 packet message under a standard protocol whereby the receiver is able to ascertain which packets have been received without error. The receiver then requests selective re-transmission of the erroneous packets. The cycle is then repeated until all information has been received without error. A hypothetical example might be as follows: Transmission A transmits B receives Cumulative Packet acket &num;s w/o error w/o error 1 0-15 0,3,10,8,7,6 6 (of 16) 2 1,2,4,5,9, 1,2,11,13 10 3 4,5,9,12,14 4,5,9,12 15 This conventional ARQ system gradually converges, but at a cost of some number of attempts to transmit for a given degree of attack.Assume as an alternative that the invention is employed to encode (with 100% redundancy as a conservative example) the information to create additional packets, for a total of 32 packets. It is apparent that the successful receipt of at least 16 packets of the 32 packets is sufficient to recover the original information. Again assume a selective request for re-transmission of packets in error. A corresponding hypothetical record might show: Transmission A transmits B receives Cumulative Packet acket &num;s w/o error w/o error 1 0-31 0,2,7,8,16, 8 (of 32) 21,24,25 2 1,3,5,6,9-15 3,4,5,17,22, 16 17-20 9,13,31 In the arbitrary example of the system in operation, despite successful receipt of only half of the packets comprising the transmitted information, there is sufficient error-free received data to obtain the recovery of the original information.

The essence of the example is to recognize that the achievement of k of n desired events (non-erroneous transmissions) will be more readily achieved than k of k desired events in the face of a hostile environment.

It is preferred that the maximum distance separable code be selected from the class of Reed-Solomon codes. These are symbol codes defined for b bit symbols forming an alphabet of k symbols encoded to yield N symbols for every K information symbols directed to the encoder. Such RS(n,k) codes are further characterized by the distance d, d = n - k +1 where d > n > k > O. Such a code with redundancy r = n-k is capable of correcting as many as t symbol errors in a codeword subject to the condition that 2 t ç r. The factor 2 is related to the necessity to utilize independent information for the function of locating an error and the separate function of correcting the error. In practical situations, there is often independent indicia of the location of error.Where there is no independent indicia of error, an error location polynomial is determined by the decoder at the expense of utilizing a portion of the redundancy in the received information.

Independent means for location of corrupt or suspect symbols (eg. as with modem apparatus capable of proportional response to incoming datums) permits conservation of redundant information. The redundancy which is thereby saved may be exploited for correction of a further number of s errata (erasure), in which case s+2t r. RS codes are preferred for the maximum distance separable codes of the present invention for practical reasons and a systematic RS code is further preferred as it is desired to attach packets to the original packetized information.Inasmuch as the specificity of the selected FEC code, and consequent structure of encoder and decoder are not critical to the practice of the present invention, the reasons for such preference may be summarized as a lower level of functional complexity required due to relatively fewer number of operations per output bit. This implies a lower level of complexity for implementation as well higher speed. However, a non-systematic code may be used instead, if desired.

As indicated in Fig. 1, an interleaver and de-interleaver may be added to the data source and sink with advantage. Interleavers are often employed to spread the effects of interference over a number of independently encoded blocks of data.

This is accomplished by shuffling the elements of a number of blocks of data in such fashion that such elements or groups of elements associated with different blocks constitute temporally adjacent positions in the stream transmitted. The de-interleaver operates in reverse fashion to restore the original ordering to the received datums. The decoder then operates upon the data in its original form to recover errata. Interleavers are well known in the art. For the present invention it is preferred (but not essential) practice for interleaving of RS codewords of the K packets such that the i th packet contains code symbols of constant ordinal location with respective codewords.

Since many changes could be made in the above construction and many apparently widely differing embodiments could be made without departing from the scope thereof, it is intended that all matter contained in the above description or shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

Claims (24)

1. The method for communicating information over a plurality of channels from a data source to a data sink, said channels subject to non-random interference, comprising the steps of (a) grouping said information into K information packets, each of length L symbols, (b) encoding the symbols comprising said K packets in accord with a selected maximum distance separable code to derive redundancy comprising r additional packets, each said additional packets of length L symbols, (c) initiating transmission of said K + r packets over said plurality of channels, (d) receiving without error at least M of said K + r packets K m m < (K + r), said M packets sufficient to protect a pre-selected number of errors in said K + r transmitted packets, (e) during said step of receiving, decoding at least said M packets, whereby said information is recovered, (f) terminating said transmission.

2. The method of claim 1 wherein said plurality of channels comprise a packet switched network and said step of initiating transmission comprises distribution and propagation of said packets over said packet switched network.

3. The method of claim 2 wherein said step of encoding is in accord with a Reed-Solomon code.

4. The method of claim 3 wherein said step of receiving further comprises retaining each said packet received without error, counting the number of said packets received without error and generating an indicia of receipt of said at least M packets received without error.

5. The method of claim 4 wherein said step of counting further comprises causing said step of transmitting to be repeated for selected ones of said K + r packets.

6. The method of claim 5 wherein said step of grouping includes annexation to each said packet at least one error detection symbol, said L symbols including said at least one error detection symbol.

7. The method of claim 6 wherein said step of encoding further comprises interleaving encoded symbols from said K + r packets and presenting said K + r packets for transmission in interleaved sequence.

8. The method of claim 7 wherein said step of interleaving results in grouping together within an interleaved packet, symbols characterized by the same ordinal position within respective packets prior said step of interleaving.

9. The method of communicating information over a plurality of channels from a data source to a data sink, said channels subject to noise and non-random interference, comprising the steps of (a) grouping said information into K information packets, each said packet comprising L symbols, (b) outer encoding each said K packets in accord with an inner code comprising a selected maximum distance separable code to derive from each said packet a plurality of redundant symbols forming r additional packets, each of length L symbols, (c) inner encoding said K outer encoded packets in accord with a selected forward error correction code to derive redundancy from said K + r packets resulting from said step of outer encoding, the resulting inner redundancy comprising c symbols annexed to respective packets whereby the encoded information comprises K + r packets each of length L + c symbols, (d) transmitting said K + r packets over said plurality of channels, (e) receiving without error at least M of said K + r packets, K 4 M, said M packets sufficient to correct a pre-selected number of errata in said K + r received packets, (f) decoding in accord with said selected maximum distance separable code at least M said packets received without error, whereby said information is recovered, (g) terminating said communication.

10. The method of claim 9 wherein said plurality of channels comprises a packet switched network and said step of transmitting comprises distributing and propagating said packets over said packet switched network.

11. The method of claim 10 wherein said step of receiving without error comprises inner decoding each said packet in accord with said selected inner code, whereby to ascertain whether said packet is free of error and to correct same, retaining packets received without error and retaining packets corrected by said inner decoding step and counting said retained packets whereby said step of decoding is initiated when at least M packets have been retained.

12. The method of claim 11 wherein said step of outer encoding is carried out in accord with a Reed-Solomon code.

13. The method of claim 12 further comprising causing transmission again of selected packets when fewer than M of said K + r packets have been received error free.

14. Apparatus for communicating over a plurality of channels from a data source to a data sink in packets comprising symbols, said channels subject to non-random interference, said apparatus comprising (a) packet forming means for grouping said information into said packets, each said packet comprising L symbols, (b) forward error correction encoder means for encoding said information packets in accord with a selected maximum distance separable code to derive redundancy from said information and for forming r additional packets, each said additional packet comprising L symbols, (c) transmission means for transmitting said K + r packets over said plurality of channels, (d) receiver means for demodulating said channels to recover at least K packets without error from said K + r transmitted packets, (e) forward error correction decoder means for decoding any said K packets received without error, in accord with said selected maximum distance separable code, for recovery of said information and, (f) termination means for terminating said communication.

15. The apparatus of claim 14 wherein said plurality of channels comprise a packet switched network and said transmission means comprises packet switched network means for distributing and propagating said packets over said plurality of channels.

16. The apparatus of claim 15 wherein said packet forming means comprises means for annexing at least one error detection symbol to each said packet, said at least one error correction symbol included in said L symbols.

17. The apparatus of claim 16 wherein said receiver means comprises error detection means for ascertaining presence of error in respective demodulated packets, acceptance means for retaining any packet free of error and counting means for retaining at least K packets without error.

18. The apparatus of claim 17 wherein said counting means further comprises retransmission request means for causing said transmission means to again transmit selected packets in the event that at least K packets of said K + r packets have not been received without error.

19. Apparatus for communicating information over a plurality of channels from a data source to a data sink over a plurality of channels as a first plurality of packets, said channels subject to non-random interference, each said packet comprising a second plurality of symbols, said apparatus comprising (a) packetizing means for grouping said information into K packets, each said packet comprising L symbols, (b) outer forward error correction means comprising encoding means for encoding said K packets in accord with a maximum distance separable code, (c) inner forward error correction encoder apparatus operating on each said packet to derive inner redundancy from same in accord with a selected forward error correction code and memory means for grouping said redundancy to reconstitute said packets-of length L symbols and said inner redundancy symbols to form packets of length L + c symbols, (d) transmission means for transmitting said K + r packets over said plurality of channels, (e) receiver means for demodulating said channels to recover at least a portion of said K packets from said channels and inner error detection means for ascertaining the presence of error in each said packet, (f) inner error correction decoder means for correcting in accord with said selected inner error correcting code correctable error detected by said error detection means, (g) acceptance means for treating packets corrected by said inner error correcting decoder means and packets ascertained by inner error detection means as free of error to form a sufficient set of packets to reconstitute said information, a sufficient number of said packets being at least M said packets, K M < (K + r), (h) maximum distance separable decoder means for operating upon said sufficient set of packets to reconstitute said information.

20. The apparatus of claim 19 comprising re-transmission request means for initiating a request for retransmission of at least selected packets of said K + r packets in the event that fewer than M said packets have been formed by said acceptance means into said sufficient set.

21. The method of claim 1 substantially as hereinbefore described with reference to the accompanying drawings.

22. The method of claim 9 substantially as hereinbefore described with reference to the accompanying drawings.

23. The apparatus of claim 14 substantially as hereinbefore described with reference to the accompanying drawings.

24. The apparatus of claim 19 substantially as hereiflbefore described with reference to the accoRpanging drawings.