Forward error correction (FEC) for packetized data networks

[0002] This application is related to U.S. patent application Ser. No. 09/693,782, entitled “SYSTEM AND METHOD FOR FRAME PACKING”, filed Oct. 19, 2000, assigned to the assignee of the present application, and herein incorporated by reference.

[0003] 1. Field of the Invention

[0004] The present invention relates generally to the field of packetized data transmission, and more particularly, to a system and method for forward error correction (FEC) for packetized data networks, such as a Voice-over-IP (VoIP) network.

[0005] 2. Description of the Related Art

[0006] A typical communications network 10 is shown in FIG. 1. Individual computers 12, 14, 16, 18, 20 are connected via a network interface 30, 32, 34 to a network, such as the Internet 40. The network 10 forwards and routes data sent from a source computer to a destination computer. Increasingly, such networks are also used to transmit voice signals, as well as data. In fact, digital telephones 50 may be connected directly to the network 10, as shown in the Figure. However, since such networks were originally designed to transmit data, and not necessarily in real-time, there are many problems associated with transmitting voice conversations between two parties.

[0007] In packetized voice communication systems (e.g. Voice-over-IP (VoIP), frame relay, or ATM), voice data is digitized and lossily compressed into frames. Each frame represents the voice data for a small unit of time, typically 30 milliseconds. Frames are then transported over the network from a source to a destination, where the frames are then decompressed.

[0008] In a Voice-over-IP (VoIP) network, each frame of voice data is typically encapsulated in one datagram. The Internet Protocol (IP) imposes a minimum of 20 bytes of header, containing such information as the destination EP address. The User Datagram Protocol (UDP), typically used for voice transport applications, adds another six bytes of header information. A voice frame encoded with, for example, the Lucent 9600 codec is 18 bytes long. (FIG. 2).

[0009] It is the responsibility of the underlying network protocols to ensure that the packets are received at the receiving end. Occasionally, however, packets may be lost or corrupted. In a protocol such as TCP running over EP, if a packet is missing, it is the responsibility of the TCP layer to ask for retransmission of the packet, thus ensuring data integrity. However, in a VoIP network, the compressed voice packets are time critical, and if a packet is lost there is not time to request a retransmission of the packet. This may result in the voice sounding “broken-up.”

[0010] One common method to overcome this problem is to use a buffer which stores a certain number of packets in a queue. If a packet is missing, its retransmission can be requested and the packet received before the packets are decompressed. Packets can then be rearranged to ensure that they are in the correct order. However, this produces unacceptably long latencies as a result of the extra retransmission time and buffer delay. For example, in FIG. 3, the total latency for the receive queue is 150 ms. For this method to work, the queue length needs to be sufficiently long to account for the retransmission latency. Assuming a retransmission latency of 120 ms, as shown in FIG. 4, a lost packet can be recovered before the packet is sent to the decompression hardware. In reality, the retransmission latencies are much greater than 120 ms, and this approach thus becomes unacceptable.

[0011] Alternatively, each packet may be transmitted two or three times, but this is an inefficient use of bandwidth. Thus, it would be desirable to have an improved error correction technique that could be used with VoIP systems, without introducing large latencies and without significantly increasing the required bandwidth.

[0012] In general, the present invention is a system and method for using forward error correction (FEC) to improve transmission reliability for data packets transmitted on a packetized data network, such as an Internet Protocol (EP) network. Packets containing error data are transmitted separately from corresponding voice packets. The error packets are transmitted a predetermined number of packets before the voice packets, to increase the probability that either the voice packet or error packet will be received. The error packets are preferably created using a Reed-Solomon algorithm. This approach greatly reduces the amount of error data that needs to be transmitted, without substantially increasing latency.

[0013] Additionally, the present invention may be further enhanced by dynamically adapting the amount of error correction that is sent based upon the “reliability” of a network connection. In another embodiment, voice frames and error frames from different conversations are packed at a same time interval to increase transmission efficiency.

[0014] The present invention will be readily understood by the following detailed description in conjunction with the accompanying drawings, wherein like reference numerals designate like structural elements, and in which:

[0015] FIG. 1 illustrates a typical Voice-over-IP network;

[0016] FIG. 2 illustrates a typical EP voice packet;

[0017] FIG. 3 is a diagram of a prior art receiving queue buffer;

[0018] FIG. 4 illustrates the operation of a prior art receiving queue buffer with packet retransmission;

[0019] FIG. 5 illustrates the operation of forward error correction (FEC);

[0020] FIG. 6 is a diagram of a typical Reed-Solomon codeword;

[0021] FIG. 7 is a diagram of a systematic RS(255,249) encoder;

[0022] FIG. 8 is a diagram of a general Reed-Solomon decoder;

[0023] FIG. 9 is a diagram illustrating the construction of a “queue pair” according to the present invention;

[0024] FIG. 10 is a diagram of transmission “queue pairs” constructed according to the present invention;

[0025] FIG. 11 is a diagram of the operation of the present invention;

[0026] FIG. 12 is a block diagram of a network interface incorporating the present invention; and

[0027] FIG. 13 is a table showing ratios of Ecc window size, latency and bandwidth to compensate for a specific reliability measure.

[0028] The following description is provided to enable any person skilled in the art to make and use the invention and sets forth the best modes contemplated by the inventor for carrying out the invention. Various modifications, however, will remain readily apparent to those skilled in the art, since the basic principles of the present invention have been defined herein specifically to provide a system and method for forward error correction (FEC) for packetized data networks. Any and all such modifications, equivalents and alternatives are intended to fall within the spirit and scope of the present invention.

[0029] In order to overcome transmission errors and packet loss, many systems use forward error correction (FEC). In general, FEC schemes transmit extra data which can be used at the receiving end to re-create any corrupted or lost packets. FEC has been applied to CD-ROMs to compensate for scratches, and used in satellite and deep-space transmissions, since the broadcast is in only one direction (i.e. the receiver is incapable of asking for retransmission). See, for example, Error Coding Cookbook: Practical C/C++ Routines and Recipes for Error Detection and Correction, by C. Britton Rorabaugh, herein incorporated by reference.

[0030] Many of these systems use the Reed-Solomon algorithm, which is primarily designed to take an arbitrary stream of data and restore any corrupted section therein, with the appropriate amount of error correction contained in the stream. In order for the algorithm to recover data that has been corrupted or lost in an arbitrary location, the algorithm must include enough error correction to compensate for the fact that some error correction may not be received at the receiving end as well (i.e. the algorithm needs to be able to account for the fact that both data and error correction may be lost). As a result, applying Reed-Solomon in some cases can actually double the amount of data that is transmitted.

[0031] In packetized data transmission systems, the data loss is not a random length, i.e. a fixed number of packets are either lost or corrupted. In other words, the data stream is not interrupted at some random location for a random interval, but the interruption is much more predictable. Since the actual data transmission is handled at lower layers (routers, etc.), the only time that a transmission will lose data is if the router does not have enough bandwidth or enough processor time to forward an entire packet. So, from a sender's point of view, an error correction technique only needs to be able to correct a packet in its entirety (not a partial packet). It also follows from this reasoning that the error correction data should not be transmitted in the same packet as the voice data.

[0032] Note that while the present invention will be described herein specifically with reference to a Voice-over-IP network, the present invention may be advantageously applied to any network that utilizes packets to transmit frames of data, in order to reduce the amount of error correction data that needs to be transmitted.

[0033] The present invention utilizes the fact that if one knows the type of data loss ahead of time (i.e. discrete packet loss), then the amount of overhead and amount of error correction associated with the Reed-Solomon algorithm can be reduced. According to the present invention, for each packet of voice data that is transmitted, error correction data is generated and transmitted in pieces over a predetermined number of packets prior to the voice packet itself. At the receiving end, what generally arrives is several error packets, and then a voice packet. In the present invention, since an error correction packets are separate from the voice packets, this helps ensure that one or the other will be received. Also, additional error correction data can be generated to account for multiple packets getting lost in a row—limited by the bandwidth of the network. The present invention is designed to be able to adjust the above settings to account for more or less packet loss.

[0034] In further detail, the present invention employs a type of Forward Error Correction (FEC) right at the packet level. This enables the reconstruction of whole packets instead of single bit errors, which may occur at lower levels. Consider the following assumptions:

[0035] 1. All packets received are 100% correct with regard to data integrity.

[0036] 2. It is possible for packets not arrive at all (loss).

[0037] 3. It is possible a packet will arrive late.

[0038] 4. It is possible packets will arrive in an incorrect order (may be viewed as a combination of 2 & 3).

[0039] 5. Duplicate packets are possible.

[0040] The present invention reliably compensates for the above anomalies, resulting in clear and consistent voice signals, with respect to a reasonable amount of packet loss.

[0041] FEC can be viewed as an advanced form of checksums. A set mathematical (polynomials) equations are applied to input data resulting in another set of data. The output data is called Error Correcting Code data (ECC data). Both sets of data are then transmitted. Upon reception, the data is checked for integrity using the ECC data and the known polynomials, resulting in another piece of data indicating exactly where and how the received data is incorrect and how to correct it. Note that the checking algorithm can detect discrepancies in the ECC data itself, even if it was corrupted. This process is illustrated graphically in FIG. 5.

[0042] In general, the set of mathematical algorithms and equations used to calculate the ECC data is called “Reed-Solomon”, and is well known in the art, but for background, will now be described below.

[0043] Reed Solomon codes are a subset of BCH codes and are linear block codes. A Reed-Solomon code is specified as RS(n,k) with s-bit symbols. This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol codeword. There are n−k parity symbols of s bits each. A Reed-Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t=n−k. In reality, a Reed-Solomon decoder can correct up to 2t symbols if the locations of the errors are already known, which is an important feature utilized in the present implementation.

[0044] FIG. 6 illustrates a typical Reed-Solomon codeword (known as a Systematic code because the data is left unchanged and the parity symbols are appended).

[0045] One popular Reed-Solomon code is RS(255,223) having 8-bit symbols. Each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity.

[0046] For this code:

[0047] n=255, k=223, s=8, 2t=32, t=16

[0048] The decoder can correct any 16-symbol errors in the code word: i.e. errors in up to 16 bytes anywhere in the codeword can be automatically corrected.

[0049] Given a symbol size s, the maximum codeword length (n) for a Reed-Solomon code is:

[0050] n=2s−1. For example, the maximum length of a code with 8-bit symbols (s=8) is 255 bytes.

[0051] Reed-Solomon codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder.

[0052] The RS(255,223) code described above can be shortened to (200,168). The encoder takes a block of 168 data bytes, and (conceptually) adds 55 zero bytes, creates a (255,223) codeword and transmits only the 168 data bytes and 32 parity bytes.

[0053] The amount of processing “power” required to encode and decode Reed-Solomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t. The standard implementation of Reed-Solomon has been described but since the goal of the present implementation is to recover whole packets of information, i.e. t=k, which results in making 2t a large number. However, since the error locations are known (i.e. a whole packet) the amount of ECC data actually needed according to the present invention is only k (the size of the packet itself).

[0054] One symbol error occurs when 1 bit in a symbol is wrong or when all the bits in a symbol are wrong.

[0055] RS(255,223) can correct 16 symbol errors. In the worst case, 16 bit errors may occur, each in a separate symbol (byte), so that the decoder corrects 16 bit errors. In the best case, 16 complete byte errors occur so that the decoder corrects 16×8 bit errors. Reed-Solomon codes are particularly well suited to correcting burst errors (where a series of bits in the codeword are received in error).

[0056] Reed-Solomon algebraic decoding procedures can correct errors and erasures. An erasure occurs when the position of an erred symbol is known (in the present implementation erasures are the only occurrence). A decoder can correct up to t errors or up to 2t erasures. The demodulator can often supply erasure information in a digital communication system, i.e. the demodulator “flags” received symbols that are likely to contain errors.

[0057] When a codeword is decoded, there are three possible outcomes:

[0058] 1. If 2s+r<2t (s errors, r erasures), then the original transmitted code word will always be recovered.

[0059] OTHERWISE

[0060] 2. The decoder will detect that it cannot recover the original code word and indicate this fact.

[0061] OR

[0062] 3. The decoder will mis-decode and recover an incorrect code word without any indication. The probability of each of the three possibilities depends on the particular Reed-Solomon code and on the number and distribution of errors.

[0063] Reed-Solomon codes are based on a specialized area of mathematics known as Galois fields, or finite fields. A finite field has the property that arithmetic operations (+,−,x,/ etc.) on field elements always have a result in the field. A Reed-Solomon encoder or decoder needs to carry out these arithmetic operations. These operations generally require special hardware or software functions in order to implement them.

[0064] A Reed-Solomon codeword is generated using a special polynomial. All valid codewords are exactly divisible by the generator polynomial. The general form of the generator polynomial is:

[0065] g(x)=(x−α)(x−α^i+I) . . . (x−α^i−2t)

[0066] and the codeword is constructed using:

[0067] c(x)=g(x)·i(x)

[0068] where g(x) is the generator polynomial, i(x) is the information block, c(x) is a valid codeword and α is referred to as a primitive element of the field.

[0069] Example: Generator for RS(255,249)

[0070] g(x)=(x−α⁰)(x−α¹)(x−α²)(x−α³)(x−α⁴)(x−α⁵)

[0071] g(x)x⁶+g₅x⁵+x⁴+g₃x³+g₂x²+g₁x¹+g₀

[0072] The 2t parity symbols in a systematic Reed-Solomon codeword are given by:

[0073] p(X)=i(x)^n-kmodg(x)

[0074] FIG. 7 shows an architecture for a systematic RS(255,249) encoder. Each of the 6 registers R1-R6 holds a symbol (8 bits). The arithmetic operators carry out finite field addition or multiplication operations on a complete symbol.

[0075] A general architecture for decoding Reed-Solomon codes is shown in FIG. 8.

[0076] Key

[0077] r(x) Received codeword

[0078] Si Syndromes

[0079] L(x) Error locator polynomial

[0080] Xi Error locations

[0081] Yi Error magnitudes

[0082] c(x) Recovered code word

[0083] V Number of errors

[0084] The received codeword r(x) is the original (transmitted) codeword c(x) plus errors:

[0085] r(x)=c(x)+e(x)

[0086] A Reed-Solomon decoder attempts to identify the position and magnitude of up to t errors (or 2t erasures) and to correct the errors or erasures.

[0087] This is a similar calculation to a parity calculation. A Reed-Solomon codeword has 2t syndromes that depend only on errors (not on the transmitted code word). The syndromes can be calculated by substituting the 2t roots of the generator polynomial g(x) into r(x).

[0088] Note that this explanation describes how to find the Symbol Error Locations in a general case. However, in the present implementation, the Symbol Error Locations are already known and thus regenerated. In general, finding the Symbol Error Locations involves solving simultaneous equations with t unknowns. Several fast algorithms are available to do this. These algorithms take advantage of the special matrix structure of Reed-Solomon codes and greatly reduce the computational effort required. In general, two steps are involved:

[0089] 1. Find an Error Locator Polynomial

[0090] In the preferred embodiment, this is done using the Berlekamp-Massey algorithm. Euclid's algorithm could be used and is more widely used in practice because it is easier to implement. However, the Berlekamp-Massey algorithm tends to lead to more efficient hardware and software implementations.

[0091] 2. Find the Roots of this Polynomial

[0092] This is done using the Chien search algorithm.

[0093] Similarly, this operation involves solving simultaneous equations with t unknowns. A widely used fast algorithm is the Forney algorithm.

[0094] As shown in FIG. 9, compressed voice packets are passed up from the voice hardware. ECC (Error Correcting Code) data is then calculated on each packet. The data is appended to the back of “ECC queues”. Packets are then transmitted out the front of the queues.

[0095] In further detail, the compressed voice packets that are transmitted originate from the DSP hardware. These packets are passed on to a transmission queue. As each packet is received from the hardware, ECC information is calculated and the ECC data is spread over the length of an attached ECC queue. As each packed is processed into the queue, packets from the other side are transmitted, either as two packets (ECC and data packets) or sent onto get “frame packed”. Frame packing is described in related U.S. patent application Ser. No. 09/693,782 entitled “SYSTEM AND METHOD FOR FRAME PACKING”, filed Oct. 19, 2000, assigned to the assignee of the present application, and herein incorporated by reference.

[0096] As seen in the transmission “queue pairs” (ECC queue+corresponding Data queue) in FIG. 10, ECC data is ready to be transmitted before some of the actual data. In this case, silence is transmitted for the data packets. Each “queue pair” in FIG. 10 represents a new packet arriving and transmitted. (See FIG. 9.)

[0097] Note:

[0098] Each data packet is transmitted after ALL corresponding ECC data has been transmitted, this is a fundamental in Forward Error Correction.

[0099] Each piece of ECC data that is placed across the queues is appended to any existing ECC data.

[0100] Transmission latency can be calculated by the size of the queue (in this case 5) multiplied by the sample rate, usually 30 ms, i.e. 5×30=150 ms

[0101] FIGS. 9 and 10 represent one call. A List of Call queues may be set up for each call.

[0102] In general, data is received asynchronously and filtered back into ECC queues synchronously (same as in transmission). Packet sequencing is checked and corrections are made (if necessary) to the queue. The ECC queue is then “shunted” along and the packet just received is “copied down” to the voice hardware, i.e. there is no latency involved at the receiving end.

[0103] The receive processing will now be described in greater detail with reference to FIG. 11.

[0104] 1. Call data is received from a transport layer (IP, Frame Relay, ATM etc). This data is then pushed onto the end of a FIFO queue, asynchronously. The queue is used as a type of flow control for the synchronous data reception.

[0105] 2. The queue is then operated every time a clock Interrupt is received for the voice hardware. The Interrupt is taken as an indication that the voice hardware is waiting for another packet.

[0106] 3. The packet at the front of the queue is removed and checked whether it is an ECC or non-ECC packet.

[0107] ECC packets are placed into an ECC queue associated with a particular call. The ECC packet is placed into whichever slot is required to match the corresponding data packet. For example, if the ECC packet sequence is 15, then there probably exists a data packet with a sequence of 15, which then can be matched.

[0108] Non-ECC packets have their packet sequence checked relative to the back of the ECC queue, and if valid it is put into the back of the queue.

[0109] 4. The queue for each call is then checked to see if there is in fact a data packet in slot zero.

[0110] If there is a data packet then the queue is moved or “shunted along” one slot. (Packets in slot 5 would get moved off the queue and deleted)

[0111] If there is no packet in slot 0 then FEC is used to correct the missing data packet. This is done by reversing the process used to assemble the ECC data on the transmission side, followed by a Reed-Solomon algorithm decode/reconstruction. If the queue is successfully reconstructed, then the queue is moved or “shunted along” one slot.

[0112] 5. If there is a data packet in slot 1 then it is “copied down” to the voice hardware for further processing.

[0113] Important points to note:

[0114] ECC packets are placed into an ECC queue for a particular call. An ECC packet is placed into whichever slot is required to match the corresponding data packet. For example, if the ECC packet sequence is 15, then there probably exists a data packet with a sequence of 15, which then can be matched. This operation is performed because if a data packet is late, FEC reconstructs that data packet (NOT the corresponding ECC packet as well). So when or if the data/ECC pair of packets does arrive, the present invention can still use the ECC data.

[0115] Some voice compression CODECs have different sample rates—usually 30 ms, but sometimes 10 ms or 15 ms as well. To maintain a synchronous receiver, the voice hardware needs to support the different clock rate interrupts. Otherwise, a 30 ms clock rate is used and steps 3-5 are operated on 1, 2 or 3 times in one clock interrupt.

[0116] As noted above, the present forward error correction (FEC) scheme may be combined with the frame packing method disclosed in the related application “SYSTEM AND METHOD FOR FRAME PACKING”, herein incorporated by reference. The voice data frames at a same time interval, but from different conversations, can be combined into one packet, and the corresponding error frames combined into a second packet. This greatly reduces the latency associated with sending the error packets, and reduces the overhead associated with prior art Reed-Solomon solutions.

[0117] One of the trade-offs with doing the FEC is that since the error packets are transmitted several packets before the corresponding data packets, an overall latency is induced (from the transmission side) in order to determine if the current voice packets arrive. However, for public IP links, as illustrated by the network of FIG. 1, an additional 100 ms or so of delay is not that noticeable.

[0118] According to prior art Reed-Solomon approaches, the voice data and error correction data would be placed in the same packet and the system would be useless, since if the packet is lost, there is no way to use the lost error data to recreate the voice data. Thus, the present invention places error data in a separate packet, and transmits the error packet within a predefined number of packets of the corresponding data packet. The present invention thus greatly reduces overhead and thereby improves system performance.

[0119] FIG. 12 is a block diagram of a network interface 70 incorporating the present invention. A network I/O module 71 connects the interface 70 to an external network. The interface 70 includes a processor 72, an I/O bus 73, and a memory 74 for processing the call packets. The network interface 70 has an internal operating system 75 to control the internal operation of the interface. An internal system ROM 76 stores the operative control code for the interface. The network interface further includes telephony hardware interface 78 for connecting to telephone equipment, and also includes a DSP voice compression module 79. A Forward Error Correction (FEC) module 77 for provides error correction services according to the present invention.

[0120] The teachings of the present invention may be further enhanced by dynamically adapting the amount of error correction that is sent based upon the “reliability” of a network connection. For example, a link quality management module 80 can monitor various links available by sending “ping” type requests, or “echo requests” to known network nodes. When each foreign node receives an “echo request”, it responds to the sender by sending an “echo reply”. The sending node notes how many responses it gets, and how long each takes to return. These two statistics are maintained as “average loss” and “average round trip delay”.

[0121] The “average loss” statistic is the most important measure for error correction. If a link is determined to be 100% reliable, then there is no need to transmit any error correction. If the link is only somewhat unreliable (i.e. 95%), then a much smaller amount of error correction data can be transmitted. This in turn helps to reduce latency and bandwidth requirements for reliable links. In practice, for any loss less than 10%, it is more efficient to assume a 10% loss in order to reduce latency, as shown by the data table of FIG. 13, where Ecc is “Error Checking and Correction.”

[0122] Those skilled in the art will appreciate that various adaptations and modifications of the just-described preferred embodiments can be configured without departing from the scope and spirit of the invention. Therefore, it is to be understood that, within the scope of the appended claims, the invention may be practiced other than as specifically described herein.