Network Working Group M. Luby
Request for Comments: 3453 Digital Fountain
Category: Informational L. Vicisano
Cisco
J. Gemmell
Microsoft
L. Rizzo
Univ. Pisa
M. Handley
ICIR
J. Crowcroft
Cambridge Univ.
December 2002
Network Working Group M. Luby
Request for Comments: 3453 Digital Fountain
Category: Informational L. Vicisano
Cisco
J. Gemmell
Microsoft
L. Rizzo
Univ. Pisa
M. Handley
ICIR
J. Crowcroft
Cambridge Univ.
December 2002
The Use of Forward Error Correction (FEC) in Reliable Multicast
前向纠错（FEC）在可靠组播中的应用
Status of this Memo
本备忘录的状况
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
本备忘录为互联网社区提供信息。它没有规定任何类型的互联网标准。本备忘录的分发不受限制。
Copyright Notice
版权公告
Copyright (C) The Internet Society (2002). All Rights Reserved.
版权所有（C）互联网协会（2002年）。版权所有。
Abstract
摘要
This memo describes the use of Forward Error Correction (FEC) codes to efficiently provide and/or augment reliability for one-to-many reliable data transport using IP multicast. One of the key properties of FEC codes in this context is the ability to use the same packets containing FEC data to simultaneously repair different packet loss patterns at multiple receivers. Different classes of FEC codes and some of their basic properties are described and terminology relevant to implementing FEC in a reliable multicast protocol is introduced. Examples are provided of possible abstract formats for packets carrying FEC.
本备忘录描述了前向纠错（FEC）代码的使用，以有效地提供和/或增强使用IP多播的一对多可靠数据传输的可靠性。在这种情况下，FEC码的关键特性之一是能够使用包含FEC数据的相同分组来同时修复多个接收机处的不同分组丢失模式。描述了不同类别的FEC码及其一些基本特性，并介绍了在可靠多播协议中实现FEC的相关术语。提供了用于承载FEC的包的可能抽象格式的示例。
Table of Contents
目录
1. Rationale and Overview . . . . . . . . . . . . . . . . . . . . 2
1.1. Application of FEC codes . . . . . . . . . . . . . . . . . 5
2. FEC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . . 8
2.3. Large block FEC codes. . . . . . . . . . . . . . . . . . . 10
2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . . 11
2.5. Source blocks with variable length source symbols. . . . . 13
3. Security Considerations. . . . . . . . . . . . . . . . . . . . 14
4. Intellectual Property Disclosure . . . . . . . . . . . . . . . 14
5. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 15
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 17
8. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 18
1. Rationale and Overview . . . . . . . . . . . . . . . . . . . . 2
1.1. Application of FEC codes . . . . . . . . . . . . . . . . . 5
2. FEC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . . 8
2.3. Large block FEC codes. . . . . . . . . . . . . . . . . . . 10
2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . . 11
2.5. Source blocks with variable length source symbols. . . . . 13
3. Security Considerations. . . . . . . . . . . . . . . . . . . . 14
4. Intellectual Property Disclosure . . . . . . . . . . . . . . . 14
5. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 15
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 17
8. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 18
There are many ways to provide reliability for transmission protocols. A common method is to use ARQ, automatic request for retransmission. With ARQ, receivers use a back channel to the sender to send requests for retransmission of lost packets. ARQ works well for one-to-one reliable protocols, as evidenced by the pervasive success of TCP/IP. ARQ has also been an effective reliability tool for one-to-many reliability protocols, and in particular for some reliable IP multicast protocols. However, for one-to-very-many reliability protocols, ARQ has limitations, including the feedback implosion problem because many receivers are transmitting back to the sender, and the need for a back channel to send these requests from the receiver. Another limitation is that receivers may experience different loss patterns of packets, and thus receivers may be delayed by retransmission of packets that other receivers have lost that but they have already received. This may also cause wasteful use of bandwidth used to retransmit packets that have already been received by many of the receivers.
有许多方法可以为传输协议提供可靠性。一种常用的方法是使用ARQ（自动请求重传）。在ARQ中，接收方使用一个到发送方的反向通道来发送丢失数据包的重传请求。ARQ适用于一对一可靠协议，TCP/IP的普遍成功证明了这一点。ARQ也是一对多可靠性协议，特别是一些可靠IP多播协议的有效可靠性工具。然而，对于一对多可靠性协议，ARQ具有局限性，包括反馈内爆问题，因为许多接收器正在向发送器发回传输，以及需要一个反向通道从接收器发送这些请求。另一个限制是，接收机可能会经历不同的分组丢失模式，因此，接收机可能会因重新传输其他接收机已经丢失但已经接收到的分组而延迟。这还可能导致浪费用于重新传输已经由许多接收机接收的分组的带宽。
In environments where ARQ is either costly or impossible because there is either a very limited capacity back channel or no back channel at all, such as satellite transmission, a Data Carousel approach to reliability is sometimes used [1]. With a Data Carousel, the sender partitions the object into equal length pieces of data, which we hereafter call source symbols, places them into packets, and then continually cycles through and sends these packets. Receivers continually receive packets until they have received a copy of each packet. Data Carousel has the advantage that it requires no back channel because there is no data that flows from receivers to the sender. However, Data Carousel also has limitations. For example,
在ARQ成本高昂或不可能实现的环境中，因为存在容量非常有限的反向信道或根本没有反向信道，例如卫星传输，有时会使用数据传送带方法来提高可靠性[1]。通过数据传送带，发送方将对象划分为等长的数据段，我们将其称为源符号，将其放入数据包中，然后连续循环发送这些数据包。接收器持续接收数据包，直到收到每个数据包的副本。数据转盘的优点是它不需要反向通道，因为没有数据从接收者流向发送者。然而，数据转盘也有局限性。例如
if a receiver loses a packet in one round of transmission it must wait an entire round before it has a chance to receive that packet again. This may also cause wasteful use of bandwidth, as the sender continually cycles through and transmits the packets until no receiver is missing a packet.
如果一个接收器在一轮传输中丢失了一个数据包，它必须等待一整轮，然后才有机会再次接收该数据包。这也可能导致带宽的浪费，因为发送方不断循环发送数据包，直到没有接收方丢失数据包。
Forward Error Correction (FEC) codes provide a reliability method that can be used to augment or replace other reliability methods, especially for one-to-many reliability protocols such as reliable IP multicast. We first briefly review some of the basic properties and types of FEC codes before reviewing their uses in the context of reliable IP multicast. Later, we provide a more detailed description of some of FEC codes.
前向纠错（FEC）码提供了一种可靠性方法，可用于增强或替代其他可靠性方法，特别是对于一对多可靠性协议，如可靠IP多播。我们首先简要回顾FEC码的一些基本属性和类型，然后再回顾它们在可靠IP多播环境中的使用。稍后，我们将提供一些FEC代码的更详细描述。
In the general literature, FEC refers to the ability to overcome both erasures (losses) and bit-level corruption. However, in the case of an IP multicast protocol, the network layers will detect corrupted packets and discard them or the transport layers can use packet authentication to discard corrupted packets. Therefore the primary application of FEC codes to IP multicast protocols is as an erasure code. The payloads are generated and processed using an FEC erasure encoder and objects are reassembled from reception of packets containing the generated encoding using the corresponding FEC erasure decoder.
在一般文献中，FEC指的是克服擦除（丢失）和位级损坏的能力。然而，在IP多播协议的情况下，网络层将检测损坏的分组并丢弃它们，或者传输层可以使用分组认证来丢弃损坏的分组。因此，FEC码在IP多播协议中的主要应用是作为擦除码。使用FEC擦除编码器生成和处理有效载荷，并且使用相应的FEC擦除解码器从包含生成的编码的分组的接收重新组装对象。
The input to an FEC encoder is some number k of equal length source symbols. The FEC encoder generates some number of encoding symbols that are of the same length as the source symbols. The chosen length of the symbols can vary upon each application of the FEC encoder, or it can be fixed. These encoding symbols are placed into packets for transmission. The number of encoding symbols placed into each packet can vary on a per packet basis, or a fixed number of symbols (often one) can be placed into each packet. Also, in each packet is placed enough information to identify the particular encoding symbols carried in that packet. Upon receipt of packets containing encoding symbols, the receiver feeds these encoding symbols into the corresponding FEC decoder to recreate an exact copy of the k source symbols. Ideally, the FEC decoder can recreate an exact copy from any k of the encoding symbols.
FEC编码器的输入是若干k个等长源符号。FEC编码器生成与源符号长度相同的一些编码符号。所选择的符号长度可以根据FEC编码器的每个应用而变化，也可以是固定的。这些编码符号被放入数据包中进行传输。放入每个分组的编码符号的数量可以在每个分组的基础上变化，或者可以将固定数量的符号（通常为一个）放入每个分组。此外，在每个分组中放置足够的信息以识别该分组中携带的特定编码符号。在接收到包含编码符号的分组时，接收机将这些编码符号馈送到相应的FEC解码器中，以重新创建k个源符号的精确副本。理想情况下，FEC解码器可以从任意k个编码符号重新创建精确副本。
In a later section, we describe a technique for using FEC codes as described above to handle blocks with variable length source symbols.
在后面的部分中，我们将描述一种使用如上所述的FEC码来处理具有可变长度源符号的块的技术。
Block FEC codes work as follows. The input to a block FEC encoder is k source symbols and a number n. The encoder generates a total of n encoding symbols. The encoder is systematic if it generates n-k redundant symbols yielding an encoding block of n encoding symbols in total composed of the k source symbols and the n-k redundant symbols.
块FEC代码的工作原理如下。块FEC编码器的输入是k个源符号和一个数字n。编码器总共生成n个编码符号。如果编码器生成n-k个冗余符号，产生总共由k个源符号和n-k个冗余符号组成的n个编码符号的编码块，则编码器是系统的。
A block FEC decoder has the property that any k of the n encoding symbols in the encoding block is sufficient to reconstruct the original k source symbols.
块FEC解码器具有编码块中的n个编码符号中的任意k个足以重构原始k个源符号的特性。
Expandable FEC codes work as follows. An expandable FEC encoder takes as input k source symbols and generates as many unique encoding symbols as requested on demand, where the amount of time for generating each encoding symbol is the same independent of how many encoding symbols are generated. An expandable FEC decoder has the property that any k of the unique encoding symbols is sufficient to reconstruct the original k source symbols.
可扩展FEC代码的工作原理如下。可扩展FEC编码器将k个源符号作为输入，并根据需要生成尽可能多的唯一编码符号，其中生成每个编码符号的时间量与生成的编码符号数量无关。可扩展FEC解码器具有任意k个唯一编码符号足以重构原始k个源符号的特性。
The above definitions explain the ideal situation when the reception of any k encoding symbols is sufficient to recover the k source symbols, in which case the reception overhead is 0%. For some practical FEC codes, slightly more than k encoding symbols are needed to recover the k source symbols. If k*(1+ep) encoding symbols are needed, we say the reception overhead is ep*100%, e.g., if k*1.05 encoding symbols are needed then the reception overhead is 5%.
上述定义解释了当任何k个编码符号的接收足以恢复k个源符号时的理想情况，在这种情况下，接收开销为0%。对于一些实际的FEC码，需要略多于k个编码符号来恢复k个源符号。如果需要k*（1+ep）编码符号，我们说接收开销是ep*100%，例如，如果需要k*1.05编码符号，则接收开销是5%。
Along a different dimension, we classify FEC codes loosely as being either small or large. A small FEC code is efficient in terms of processing time requirements for encoding and decoding for small values of k, and a large FEC code is efficient for encoding and decoding for much large values of k. There are implementations of block FEC codes that have encoding times proportional to n-k times the length of the k source symbols, and decoding times proportional to l times the length of the k source symbols, where l is the number of missing source symbols among the k received encoding symbols and l can be as large as k. Because of the growth rate of the encoding and decoding times as a product of k and n-k, these are typically considered to be small block FEC codes. There are block FEC codes with a small reception overhead that can generate n encoding symbols and can decode the k source symbols in time proportional to the length of the n encoding symbols. These codes are considered to be large block FEC codes. There are expandable FEC codes with a small reception overhead that can generate each encoding symbol in time roughly proportional to its length, and can decode all k source symbols in time roughly proportional to their length. These are considered to be large expandable FEC codes. We describe examples of all of these types of codes later.
沿着不同的维度，我们将FEC码松散地分类为小码或大码。就编码和解码小k值的处理时间要求而言，小FEC码是有效的，而大FEC码对于编码和解码大k值是有效的。存在具有与k个源符号的长度的n-k倍成比例的编码时间和与k个源符号的长度的l倍成比例的解码时间的块FEC码的实现，其中l是k个接收到的编码符号中丢失的源符号的数目，并且l可以大到k。由于编码和解码时间作为k和n-k的乘积的增长率，这些通常被认为是小块FEC码。存在具有小接收开销的块FEC码，其可以生成n个编码符号并且可以在与n个编码符号的长度成比例的时间内解码k个源符号。这些码被认为是大分组FEC码。存在具有小接收开销的可扩展FEC码，其可以在时间上大致与每个编码符号的长度成比例地生成每个编码符号，并且可以在时间上大致与其长度成比例地解码所有k个源符号。这些被认为是大型可扩展FEC代码。我们稍后将描述所有这些类型代码的示例。
Ideally, FEC codes in the context of IP multicast can be used to generate encoding symbols that are transmitted in packets in such a way that each received packet is fully useful to a receiver to reassemble the object regardless of previous packet reception patterns. Thus, if some packets are lost in transit between the sender and the receiver, instead of asking for specific
理想情况下，IP多播上下文中的FEC码可用于生成以分组的方式发送的编码符号，该方式使得每个接收到的分组对于接收器完全有用，以重新组装对象，而不管先前的分组接收模式如何。因此，如果某些数据包在发送方和接收方之间的传输过程中丢失，而不是请求特定的
retransmission of the lost packets or waiting till the packets are resent using Data Carousel, the receiver can use any other subsequent equal number of packets that arrive to reassemble the object. These packets can either be proactively transmitted or they can be explicitly requested by receivers. This implies that the same packet is fully useful to all receivers to reassemble the object, even though the receivers may have previously experienced different packet loss patterns. This property can reduce or even eliminate the problems mentioned above associated with ARQ and Data Carousel and thereby dramatically increase the scalability of the protocol to orders of magnitude more receivers.
重新传输丢失的数据包或等待使用数据传送带重新发送数据包，接收器可以使用任何其他随后到达的相同数量的数据包来重新组装对象。这些数据包可以主动发送，也可以由接收方显式请求。这意味着相同的数据包对于所有接收器重新组装对象都是完全有用的，即使接收器之前可能经历过不同的数据包丢失模式。该属性可以减少甚至消除上述与ARQ和数据转盘相关的问题，从而显著提高协议对多个数量级接收机的可伸缩性。
For some reliable IP multicast protocols, FEC codes are used in conjunction with ARQ to provide reliability. For example, a large object could be partitioned into a number of source blocks consisting of a small number of source symbols each, and in a first round of transmission all of the source symbols for all the source blocks could be transmitted. Then, receivers could report back to the sender the number of source symbols they are missing from each source block. The sender could then compute the maximum number of missing source symbols from each source block among all receivers. Based on this, a small block FEC encoder could be used to generate for each source block a number of redundant symbols equal to the computed maximum number of missing source symbols from the block among all receivers, as long as this maximum maximum for each block does not exceed the number of redundant symbols that can be generated efficiently. In a second round of transmission, the server would then send all of these redundant symbols for all blocks. In this example, if there are no losses in the second round of transmission then all receivers will be able to recreate an exact copy of each original block. In this case, even if different receivers are missing different symbols in different blocks, transmitted redundant symbols for a given block are useful to all receivers missing symbols from that block in the second round.
对于一些可靠的IP多播协议，FEC码与ARQ结合使用以提供可靠性。例如，可以将大对象划分为多个源块，每个源块由少量的源符号组成，并且在第一轮传输中，可以传输所有源块的所有源符号。然后，接收者可以向发送者报告他们从每个源块中丢失的源符号的数量。然后，发送方可以计算所有接收方中每个源块丢失的源符号的最大数量。基于此，可以使用小块FEC编码器为每个源块生成多个冗余符号，这些冗余符号等于从所有接收机中的块计算出的最大缺失源符号数，只要每个块的最大缺失源符号数不超过可以有效生成的冗余符号数。在第二轮传输中，服务器将为所有块发送所有这些冗余符号。在此示例中，如果在第二轮传输中没有丢失，则所有接收器将能够重新创建每个原始块的精确副本。在这种情况下，即使不同的接收机在不同的块中丢失不同的符号，对于在第二轮中丢失来自该块的符号的所有接收机，给定块的发送的冗余符号也是有用的。
For other reliable IP multicast protocols, FEC codes are used in a Data Carousel fashion to provide reliability, which we call an FEC Data Carousel. For example, an FEC Data Carousel using a large block FEC code could work as follows. The large block FEC encoder produces n encoding symbols considering all the k source symbols of an object as one block. The sender cycles through and transmits the n encoding symbols in packets in the same order in each round. An FEC Data Carousel can have much better protection against packet loss than a Data Carousel. For example, a receiver can join the transmission at any point in time, and, as long as the receiver receives at least k encoding symbols during the transmission of the next n encoding
对于其他可靠的IP多播协议，FEC代码以数据旋转方式使用以提供可靠性，我们称之为FEC数据旋转。例如，使用大块FEC代码的FEC数据转盘可以如下工作。大块FEC编码器产生n个编码符号，将对象的所有k个源符号视为一个块。发送方循环并在每一轮中以相同的顺序发送分组中的n个编码符号。FEC数据传送带可以比数据传送带更好地防止数据包丢失。例如，接收机可以在任何时间点加入传输，并且只要接收机在下一个n个编码的传输期间接收到至少k个编码符号
symbols, the receiver can completely recover the object. This is true even if the receiver starts receiving packets in the middle of a pass through the encoding symbols. This method can also be used when the object is partitioned into blocks and a short block FEC code is applied to each block separately. In this case, as we explain in more detail below, it is useful to interleave the symbols from the different blocks when they are transmitted.
符号，接收器可以完全恢复对象。即使接收机在通过编码符号的中间开始接收分组，这也是正确的。当对象被划分为块并且对每个块分别应用短块FEC代码时，也可以使用该方法。在这种情况下，正如我们在下面更详细地解释的，在传输不同块的符号时，对它们进行交织是有用的。
Since any number of encoding symbols can be generated using an expandable FEC encoder, reliable IP multicast protocols that use expandable FEC codes generally rely solely on these codes for reliability. For example, when an expandable FEC code is used in a FEC Data Carousel application, the encoding packets never repeat, and thus any k of the encoding symbols in the potentially unbounded number of encoding symbols are sufficient to recover the original k source symbols.
由于可以使用可扩展FEC编码器生成任意数量的编码符号，因此使用可扩展FEC代码的可靠IP多播协议通常仅依赖这些代码来确保可靠性。例如，当在FEC数据转盘应用中使用可扩展FEC代码时，编码分组从不重复，因此编码符号的潜在无限数量中的任意k个编码符号足以恢复原始k个源符号。
For additional reliable IP multicast protocols, the method to obtain reliability is to generate enough encoding symbols so that each encoding symbol is transmitted only once (at most). For example, the sender can decide a priori how many encoding symbols it will transmit, use an FEC code to generate that number of encoding symbols from the object, and then transmit the encoding symbols to all receivers. This method is applicable to streaming protocols, for example, where the stream is partitioned into objects, the source symbols for each object are encoded into encoding symbols using an FEC code, and then the sets of encoding symbols for each object are transmitted one after the other using IP multicast.
对于额外的可靠IP多播协议，获得可靠性的方法是生成足够的编码符号，以便每个编码符号只传输一次（最多）。例如，发送方可以事先决定它将发送多少编码符号，使用FEC代码从对象生成该数量的编码符号，然后将编码符号发送给所有接收方。该方法适用于流协议，例如，其中流被划分为对象，每个对象的源符号使用FEC码被编码为编码符号，然后每个对象的编码符号集使用IP多播被逐个发送。
There are some very simple codes that are effective for repairing packet loss under very low loss conditions. For example, to provide protection from a single loss is to partition the object into fixed size source symbols and then add a redundant symbol that is the parity (XOR) of all the source symbols. The size of a source symbol is chosen so that it fits perfectly into the payload of a packet, i.e. if the packet payload is 512 bytes then each source symbol is 512 bytes. The header of each packet contains enough information to identify the payload. This is an example of encoding symbol ID. The encoding symbol IDs can consist of two parts in this example. The first part is an encoding flag that is equal to 1 if the encoding symbol is a source symbol and is equal to 0 if the encoding symbol is a redundant symbol. The second part of the encoding symbol ID is a source symbol ID if the encoding flag is 1 and a redundant symbol ID if the encoding flag is 0. The source symbol IDs can be numbered
有一些非常简单的代码可以在非常低的丢失情况下有效地修复数据包丢失。例如，为防止单个丢失提供保护就是将对象划分为固定大小的源符号，然后添加一个冗余符号，即所有源符号的奇偶校验（XOR）。选择源符号的大小以使其完全适合分组的有效载荷，即，如果分组有效载荷为512字节，则每个源符号为512字节。每个数据包的报头包含足够的信息来识别有效负载。这是编码符号ID的示例。在本示例中，编码符号ID可以由两部分组成。第一部分是编码标志，如果编码符号是源符号，则等于1；如果编码符号是冗余符号，则等于0。如果编码标志为1，则编码符号标识的第二部分为源符号标识；如果编码标志为0，则编码符号标识的第二部分为冗余符号标识。可以对源符号ID进行编号
from 0 to k-1 and the redundant symbol ID can be 0. For example, if the object consists of four source symbols that have values a, b, c and d, then the value of the redundant symbol is e = a XOR b XOR c XOR d. Then, the packets carrying these symbols look like:
从0到k-1，冗余符号ID可以为0。例如，如果对象由四个具有值a、b、c和d的源符号组成，则冗余符号的值为e=a XOR b XOR c XOR d。然后，携带这些符号的包看起来像：
(1, 0: a), (1, 1: b), (1, 2: c), (1, 3: d), (0, 0: e).
（1,0:a），（1,1:b），（1,2:c），（1,3:d），（0,0:e）。
In this example, the encoding symbol ID consists of the first two values, where the first value is the encoding flag and the second value is either a source symbol ID or the redundant symbol ID. The portion of the packet after the colon is the value of the encoding symbol. Any single source symbol of the object can be recovered as the parity of all the other symbols. For example, if packets
在此示例中，编码符号ID由前两个值组成，其中第一个值是编码标志，第二个值是源符号ID或冗余符号ID。冒号后的数据包部分是编码符号的值。对象的任何单个源符号都可以恢复为所有其他符号的奇偶校验。例如，如果数据包
(1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e)
(1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e)
are received then the missing source symbol value with source symbol ID = 2 can be recovered by computing a XOR b XOR d XOR e = c.
然后，可以通过计算XOR b XOR d XOR e=c来恢复源符号ID=2的缺失源符号值。
Another way of forming the encoding symbol ID is to let values 0,...,k-1 correspond to the k source symbols and value k correspond to the redundant symbol that is the XOR of the k source symbols.
形成编码符号ID的另一种方式是使值0、…、k-1对应于k个源符号，并且值k对应于作为k个源符号的异或的冗余符号。
When the number of source symbols in the object is large, a simple block code variant of the above can be used. In this case, the source symbols are grouped together into source blocks of some number k of consecutive symbols each, where k may be different for different blocks. If a block consists of k source symbols then a redundant symbol is added to form an encoding block consisting of k+1 encoding symbols. Then, a source block consisting of k source symbols can be recovered from any k of the k+1 encoding symbols from the associated encoding block.
当对象中的源符号数量较大时，可以使用上述的简单块代码变体。在这种情况下，源符号被分组在一起，每个源块具有一定数量的k个连续符号，其中k对于不同的块可能不同。如果一个块由k个源符号组成，则添加一个冗余符号以形成由k+1个编码符号组成的编码块。然后，可以从来自相关编码块的k+1编码符号中的任意k个恢复由k个源符号组成的源块。
Slightly more sophisticated ways of adding redundant symbols using parity can also be used. For example, one can group a block consisting of k source symbols in an object into a p x p square matrix, where p = sqrt(k). Then, for each row a redundant symbol is added that is the parity of all the source symbols in the row. Similarly, for each column a redundant symbol is added that is the parity of all the source symbols in the column. Then, any row of the matrix can be recovered from any p of the p+1 symbols in the row, and similarly for any column. Higher dimensional product codes using this technique can also be used. However, one must be wary of using these constructions without some thought towards the possible loss patterns of symbols. Ideally, the property that one would like to obtain is that if k source symbols are encoded into n encoding symbols (the encoding symbols consist of the source symbols and the redundant symbols) then the k source symbols can be recovered from
还可以使用稍微复杂一些的使用奇偶校验添加冗余符号的方法。例如，可以将对象中由k个源符号组成的块分组为p x p平方矩阵，其中p=sqrt（k）。然后，为每行添加一个冗余符号，即该行中所有源符号的奇偶校验。类似地，为每列添加一个冗余符号，即该列中所有源符号的奇偶校验。然后，可以从行中的p+1符号中的任何p恢复矩阵的任何行，并且对于任何列也是如此。也可以使用使用这种技术的高维产品代码。然而，在没有考虑符号可能丢失的模式的情况下，使用这些结构必须谨慎。理想情况下，人们希望获得的特性是，如果将k个源符号编码为n个编码符号（编码符号由源符号和冗余符号组成），则可以从中恢复k个源符号
any k of the n encoding symbols. Using the simple constructions described above does not yield codes that come close to obtaining this ideal behavior.
n个编码符号中的任意k个。使用上面描述的简单构造不会产生接近于获得这种理想行为的代码。
Reliable IP multicast protocols may use a block (n, k) FEC code [2]. For such codes, k source symbols are encoded into n > k encoding symbols, such that any k of the encoding symbols can be used to reassemble the original k source symbols. Thus, these codes have no reception overhead when used to encode the entire object directly. Block codes are usually systematic, which means that the n encoding symbols consist of the k source symbols and n-k redundant symbols generated from these k source symbols, where the size of a redundant symbol is the same as that for a source symbol. For example, the first simple code (XOR) described in the previous subsection is a (k+1, k) code. In general, the freedom to choose n larger than k+1 is desirable, as this can provide much better protection against losses. A popular example of these types of codes is a class of Reed-Solomon codes, which are based on algebraic methods using finite fields. Implementations of (n, k) FEC erasure codes are efficient enough to be used by personal computers [16]. For example, [15] describes an implementation where the encoding and decoding speeds decay as C/j, where the constant C is on the order of 10 to 80 Mbytes/second for Pentium class machines of various vintages and j is upper bounded by min(k, n-k).
可靠的IP多播协议可以使用块（n，k）FEC码[2]。对于这样的代码，k个源符号被编码成n>k个编码符号，使得任意k个编码符号可用于重新组合原始k个源符号。因此，这些代码在用于直接编码整个对象时没有接收开销。块码通常是系统的，这意味着n个编码符号由k个源符号和从这些k个源符号生成的n-k个冗余符号组成，其中冗余符号的大小与源符号的大小相同。例如，前面小节中描述的第一个简单代码（XOR）是（k+1，k）代码。一般来说，选择大于k+1的n的自由度是可取的，因为这可以提供更好的损失保护。这类码的一个常见例子是一类基于有限域代数方法的Reed-Solomon码。（n，k）FEC擦除码的实现效率足以供个人计算机使用[16]。例如，[15]描述了一种实现，其中编码和解码速度衰减为C/j，其中对于不同年份的奔腾级机器，常数C约为10到80 Mbytes/s，j的上界为min（k，n-k）。
In practice, the values of k and n must be small (for example below 256) for such FEC codes as large values make encoding and decoding prohibitively expensive. As many objects are longer than k symbols for reasonable values of k and the symbol length (e.g. larger than 16 kilobyte for k = 16 using 1 kilobyte symbols), they can be divided into a number of source blocks. Each source block consists of some number k of source symbols, where k may vary between different source blocks. The FEC encoder is used to encode a k source symbol source block into a n encoding symbol encoding block, where the number n of encoding symbols in the encoding block may vary for each source block. For a receiver to completely recover the object, for each source block consisting of k source symbols, k distinct encoding symbols (i.e., with different encoding symbol IDs) must be received from the corresponding encoding block. For some encoding blocks, more encoding symbols may be received than there are source symbols in the corresponding source block, in which case the excess encoding symbols are discarded. An example encoding structure is shown in Figure 1.
实际上，对于这样的FEC码，k和n的值必须小（例如低于256），因为大的值使得编码和解码昂贵得令人望而却步。由于对于合理的k值和符号长度，许多对象比k个符号长（例如，对于k=16，使用1KB符号，大于16KB），因此可以将它们划分为多个源块。每个源块由一些k个源符号组成，其中k可能在不同的源块之间变化。FEC编码器用于将k个源符号源块编码为n个编码符号编码块，其中编码块中的编码符号的数目n可针对每个源块而变化。为了使接收器完全恢复对象，对于由k个源符号组成的每个源块，必须从相应的编码块接收k个不同的编码符号（即，具有不同的编码符号ID）。对于一些编码块，接收的编码符号可能比相应源块中的源符号多，在这种情况下，多余的编码符号被丢弃。图1显示了一个示例编码结构。
| source symbol IDs | source symbols IDs |
| of source block 0 | of source block 1 |
| |
v v
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|
FEC encoder
|
v
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
^ ^
| |
| encoding symbol IDs | encoding symbol IDs |
| of encoding block 0 | of encoding block 1 |
| source symbol IDs | source symbols IDs |
| of source block 0 | of source block 1 |
| |
v v
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|
FEC encoder
|
v
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
^ ^
| |
| encoding symbol IDs | encoding symbol IDs |
| of encoding block 0 | of encoding block 1 |
Figure 1. The encoding structure for an object divided into two source blocks consisting of 8 source symbols each, and the FEC encoder is used to generate 2 additional redundant symbols (10 encoding symbols in total) for each of the two source blocks.
图1。对象的编码结构分为两个源块，每个源块由8个源符号组成，FEC编码器用于为两个源块中的每个生成2个额外的冗余符号（总共10个编码符号）。
In many cases, an object is partitioned into equal length source blocks each consisting of k contiguous source symbols of the object, i.e., block c consists of the range of source symbols [ck, (c+1)k-1]. This ensures that the FEC encoder can be optimized to handle a particular number k of source symbols. This also ensures that memory references are local when the sender reads source symbols to encode, and when the receiver reads encoding symbols to decode. Locality of reference is particularly important when the object is stored on disk, as it reduces the disk seeks required. The block number and the source symbol ID within that block can be used to uniquely specify a source symbol within the object. If the size of the object is not a multiple of k source symbols, then the last source block will contain less than k symbols.
在许多情况下，对象被划分为等长的源块，每个源块由对象的k个相邻源符号组成，即块c由源符号的范围[ck，（c+1）k-1]组成。这确保可以优化FEC编码器以处理特定数量的k个源符号。这还确保了当发送方读取源符号进行编码时，以及当接收方读取编码符号进行解码时，内存引用是本地的。当对象存储在磁盘上时，引用的局部性尤其重要，因为它减少了所需的磁盘空间。该块中的块编号和源符号ID可用于唯一指定对象中的源符号。如果对象的大小不是k个源符号的倍数，则最后一个源块将包含少于k个符号。
The block numbers can be numbered consecutively starting from zero. Encoding symbols within a block can be uniquely identified by an encoding symbol ID. One way of identifying encoding symbols within a block is to use the combination of an encoding flag that identifies the symbol as either a source symbol or a redundant symbol together with either a source symbol ID or a redundant symbol ID. For example, an encoding flag value of 1 can indicate that the encoding symbol is a source symbol and 0 can indicate that it is a redundant symbol. The source symbol IDs can be numbered from 0 to k-1 and the redundant symbol IDs can be numbered from 0 to n-k-1.
块编号可以从零开始连续编号。块内的编码符号可通过编码符号ID进行唯一标识。标识块内编码符号的一种方法是使用将符号标识为源符号或冗余符号的编码标志与源符号ID或冗余符号ID的组合。例如，编码标志值1可以表示编码符号是源符号，0可以表示它是冗余符号。源符号ID可以从0到k-1进行编号，冗余符号ID可以从0到n-k-1进行编号。
For example, if the object consists 10 source symbols with values a, b, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are two source blocks consisting of 5 symbols each, and there are two encoding blocks consisting of 8 symbols each. Let p, q and r be the values of the redundant symbols for the first encoding block, and let x, y and z be the values of the redundant symbols for the second encoding block. Then the encoding symbols together with their identifiers are
例如，如果对象包含10个值为a、b、c、d、e、f、g、h、i和j的源符号，且k=5和n=8，则存在两个源块，每个源块包含5个符号，并且存在两个编码块，每个编码块包含8个符号。设p、q和r为第一编码块的冗余符号的值，且设x、y和z为第二编码块的冗余符号的值。然后，编码符号及其标识符被删除
(0, 1, 0: a), (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 1, 4: e), (0, 0, 0: p), (0, 0, 1: q), (0, 0, 2: r), (1, 1, 0: f), (1, 1, 1: g), (1, 1, 2: h), (1, 1, 3: i), (1, 1, 4: j), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z).
（0,1,0:a）、（0,1,1:b）、（0,1,2:c）、（0,1,3:d）、（0,1,4:e）、（0,0,0:p）、（0,0,1:q）、（0,0,2:r）、（1,1,0:f）、（1,1,1,1:g）、（1,1,2:h）、（1,1,3:i）、（1,1,4:j）、（1,0,0:x）、（1,0,1:y）、（1,0,2:z）。
In this example, the first value identifies the block number and the second two values together identify the encoding symbol within the block, i.e, the encoding symbol ID consists of the encoding flag together with either the source symbol ID or the redundant symbol ID depending on the value of the encoding flag. The value of the encoding symbol is written after the colon. Each block can be recovered from any 5 of the 8 encoding symbols associated with that block. For example, reception of
在该示例中，第一个值标识块编号，第二个值一起标识块内的编码符号，即，编码符号ID包括编码标志以及源符号ID或冗余符号ID，具体取决于编码标志的值。编码符号的值写在冒号之后。每个块可以从与该块关联的8个编码符号中的任意5个恢复。例如，接收
(0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q)
(0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q)
is sufficient to recover the first source block, and reception of
足以恢复第一个源块，并接收
(1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z)
(1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z)
is sufficient to recover the second source block.
足以恢复第二个源块。
Another way of uniquely identifying encoding symbols within a block is to let the encoding symbol IDs for source symbols be 0,...,k-1 and to let the encoding symbol IDs for redundant symbols be k,...,n-1.
唯一标识块内编码符号的另一种方法是使源符号的编码符号id为0，…，k-1，并使冗余符号的编码符号id为k，…，n-1。
Tornado codes [12], [13], [10], [11], [9] are large block FEC codes that provide an alternative to small block FEC codes. An (n, k) Tornado code requires slightly more than k out of n encoding symbols to recover k source symbols, i.e., there is a small reception overhead. The benefit of the small cost of non-zero reception overhead is that the value of k may be on the order of tens of thousands and still the encoding and decoding are efficient. Because of memory considerations, in practice the value of n is restricted to be a small multiple of k, e.g., n = 2k. For example, [4] describes an implementation of Tornado codes where the encoding and decoding speeds are tens of megabytes per second for Pentium class machines of
Tornado码[12]、[13]、[10]、[11]、[9]是大分组FEC码，可替代小分组FEC码。（n，k）Tornado代码需要n个编码符号中略多于k个的编码符号来恢复k个源符号，即存在较小的接收开销。非零接收开销的小成本的好处是k的值可能在数万的数量级上，并且编码和解码仍然是有效的。由于内存方面的考虑，在实践中，n的值被限制为k的小倍数，例如，n=2k。例如，[4]描述了Tornado代码的一种实现，其中奔腾级机器的编码和解码速度为每秒数十兆字节
various vintages when k is in the tens of thousands and n = 2k. The reception overhead for such values of k and n is in the 5-10% range. Tornado codes require a large amount of out of band information to be communicated to all senders and receivers for each different object length, and require an amount of memory on the encoder and decoder which is proportional to the object length times 2n/k.
当k值为数万且n=2k时，会出现不同的年份。k和n的这种值的接收开销在5-10%的范围内。Tornado代码需要将大量带外信息传输到每个不同对象长度的所有发送器和接收器，并且需要编码器和解码器上的内存量，该内存量与对象长度乘以2n/k成比例。
Tornado codes are designed to have low reception overhead on average with respect to reception of a random portion of the encoding packets. Thus, to ensure that a receiver can reassemble the object with low reception overhead, the packets are permuted into a random order before transmission.
Tornado码被设计为相对于编码分组的随机部分的接收平均具有较低的接收开销。因此，为了确保接收机能够以较低的接收开销重新组装对象，分组在传输之前被排列成随机顺序。
All of the FEC codes described up to this point are block codes. There is a different type of FEC codes that we call expandable FEC codes. Like block codes, an expandable FEC encoder operates on an object of known size that is partitioned into equal length source symbols. Unlike block codes, there is no predetermined number of encoding symbols that can be generated for expandable FEC codes. Instead, an expandable FEC encoder can generate as few or as many unique encoding symbols as required on demand.
到目前为止描述的所有FEC码都是分组码。有一种不同类型的FEC码，我们称之为可扩展FEC码。与块码一样，可扩展FEC编码器对被划分为等长源符号的已知大小的对象进行操作。与分组码不同，对于可扩展的FEC码，不存在可以生成的预定数量的编码符号。相反，可扩展FEC编码器可以根据需要生成尽可能少或尽可能多的唯一编码符号。
LT codes [6], [7], [8], [5] are an example of large expandable FEC codes with a small reception overhead. An LT encoder uses randomization to generate each encoding symbol randomly and independently of all other encoding symbols. Like Tornado codes, the number of source symbols k may be very large for LT codes, i.e., on the order of tens to hundreds of thousands, and the encoder and decoder run efficiently in software. For example the encoding and decoding speeds for LT codes are in the range 3-20 megabytes per second for Pentium class machines of various vintages when k is in the high tens of thousands. An LT encoder can generate as few or as many encoding symbols as required on demand. When a new encoding symbol is to be generated by an LT encoder, it is based on a randomly chosen encoding symbol ID that uniquely describes how the encoding symbol is to be generated from the source symbols. In general, each encoding symbol ID value corresponds to a unique encoding symbol, and thus the space of possible encoding symbols is approximately four billion if for example the encoding symbol ID is 4 bytes. Thus, the chance that a particular encoding symbol is the same as any other particular encoding symbol is inversely proportional to the number of possible encoding symbol IDs. An LT decoder has the property that with very high probability the receipt of any set of slightly more than k randomly and independently generated encoding symbols is sufficient to reassemble the k source symbols. For example, when k
LT代码[6]、[7]、[8]、[5]是具有较小接收开销的大型可扩展FEC代码的示例。LT编码器使用随机化来随机且独立于所有其他编码符号生成每个编码符号。与Tornado码一样，对于LT码，源符号k的数量可能非常大，即，在数十到几十万的数量级上，并且编码器和解码器在软件中高效地运行。例如，当k值高达数万时，对于不同年份的奔腾级机器，LT码的编码和解码速度在每秒3-20兆字节的范围内。LT编码器可以根据需要生成尽可能少或尽可能多的编码符号。当新编码符号将由LT编码器生成时，它基于随机选择的编码符号ID，该编码符号ID唯一地描述如何从源符号生成编码符号。通常，每个编码符号ID值对应于唯一的编码符号，因此，如果例如编码符号ID为4字节，则可能的编码符号的空间约为40亿。因此，特定编码符号与任何其他特定编码符号相同的概率与可能的编码符号id的数量成反比。LT解码器具有这样的特性，即以非常高的概率接收到任意一组略多于k个随机和独立生成的编码符号就足以重新组合k个源符号。例如，当k
is on the order of tens to hundreds of thousands the reception overhead is less than 5% with no failures in hundreds of millions of trials under any loss conditions.
在几十万到几十万的范围内，接收开销小于5%，在任何损失条件下，在数亿次试验中都没有失败。
Because encoding symbols are randomly and independently generated by choosing random encoding symbol IDs, LT codes have the property that encoding symbols for the same k source symbols can be generated and transmitted from multiple senders and received by a receiver and the reception overhead and the decoding time is the same as if though all the encoding symbols were generated by a single sender. The only requirement is that the senders choose their encoding symbol IDs randomly and independently of one another.
因为编码符号是通过选择随机编码符号ID随机独立生成的，LT码具有这样的特性，即相同k源符号的编码符号可以从多个发送方生成和发送，并由接收机接收，并且接收开销和解码时间与所有编码符号由单个发送方生成的情况相同。唯一的要求是发送方随机且独立地选择其编码符号ID。
There is a weak tradeoff between the number of source symbols and the reception overhead for LT codes, and the larger the number of source symbols the smaller the reception overhead. Thus, for shorter objects, it is sometimes advantageous to partition the object into many short source symbols and include multiple encoding symbols in each packet. In this case, a single encoding symbol ID is used to identify the multiple encoding symbols contained in a single packet.
源符号的数量和LT代码的接收开销之间存在微弱的折衷，并且源符号的数量越大，接收开销越小。因此，对于较短的对象，有时将对象划分为许多短源符号并在每个分组中包括多个编码符号是有利的。在这种情况下，单个编码符号ID用于标识单个分组中包含的多个编码符号。
There are a couple of factors for choosing the appropriate symbol length/ number of source symbols tradeoff. The primary consideration is that there is a fixed overhead per symbol in the overall processing requirements of the encoding and decoding, independent of the number of source symbols. Thus, using shorter symbols means that this fixed overhead processing per symbol will be a larger component of the overall processing requirements, leading to larger overall processing requirements. A second much less important consideration is that there is a component of the processing per symbol that depends logarithmically on the number of source symbols, and thus for this reason there is a slight preference towards fewer source symbols.
选择适当的符号长度/源符号数量有几个因素。主要考虑的是，在编码和解码的总体处理需求中，每个符号都有固定的开销，与源符号的数量无关。因此，使用较短的符号意味着每个符号的固定开销处理将是总体处理需求的较大组成部分，从而导致更大的总体处理需求。第二个不太重要的考虑因素是，每个符号的处理有一个组件，该组件以对数方式取决于源符号的数量，因此，出于这个原因，稍微倾向于更少的源符号。
Like small block codes, there is a point when the object is large enough that it makes sense to partition it into blocks when using LT codes. Generally the object is partitioned into blocks whenever the number of source symbols times the packet payload length is less than the size of the object. Thus, if the packet payload is 1024 bytes and the maximum number of source symbols is 128,000 then any object over 128 megabytes will be partitioned into more than one block. One can choose the maximum number of source symbols to use, depending on the desired encoding and decoding speed versus reception overhead tradeoff desired. Encoding symbols can be uniquely identified by a block number (when the object is large enough to be partitioned into more than one block) and an encoding symbol ID. The block numbers, if they are used, are generally numbered consecutively starting from zero within the object. The block number and the encoding symbol ID
与小的块代码一样，当对象足够大时，在使用LT代码时将其划分为块是有意义的。通常，只要源符号的数量乘以数据包有效负载长度小于对象的大小，就将对象划分为块。因此，如果数据包有效负载为1024字节，且源符号的最大数量为128000，则超过128兆字节的任何对象将被划分为多个块。根据所需的编码和解码速度与所需的接收开销的权衡，可以选择要使用的最大源符号数。编码符号可以通过块编号（当对象足够大，可以划分为多个块时）和编码符号ID进行唯一标识。如果使用块编号，则通常在对象内从零开始连续编号。块编号和编码符号ID
are both chosen uniformly and randomly from their range when an encoding symbol is to be transmitted. For example, suppose the number of source symbols is 128,000 and the number of blocks is 2. Then, each packet generated by the LT encoder could be of the form (b, x: y). In this example, the first value identifies the block number and the second value identifies the encoding symbol within the block. In this example, the block number b is either 0 or 1, and the encoding symbol ID x might be a 32-bit value. The value y after the colon is the value of the encoding symbol.
在传输编码符号时，从其范围内均匀随机地选择。例如，假设源符号的数量为128000，块的数量为2。然后，LT编码器生成的每个分组可以是（b，x:y）形式。在此示例中，第一个值标识块编号，第二个值标识块内的编码符号。在该示例中，块号b是0或1，并且编码符号ID x可以是32位值。冒号后面的值y是编码符号的值。
For all the FEC codes described above, all the source symbols in the same source block are all of the same length. In this section, we describe a general technique to handle the case when it is desirable to use source symbols of varying lengths in a single source block. This technique is applicable to block FEC codes.
对于上述所有FEC码，相同源块中的所有源符号都具有相同的长度。在本节中，我们描述了一种处理在单个源块中使用不同长度的源符号的情况的通用技术。该技术适用于分组FEC码。
Let l_1, l_2, ... , l_k be the lengths in bytes of k varying length source symbols to be considered part of the same source block. Let lmax be the maximum over i = 1, ... , k of l_i. To prepare the source block for the FEC encoder, pad each source symbol i out to length lmax with a suffix of lmax-l_i zeroes, and then prepend to the beginning of this the value l_i. Thus, each padded source symbol is of length x+lmax, assuming that it takes x bytes to store an integer with possible values 0,...,lmax, where x is a protocol constant known to both the encoder and the decoder. These padded source symbols, each of length x+lmax, are the input to the encoder, together with the value n. The encoder then generates n-k redundant symbols, each of length x+lmax.
让l_1，l_2，l_k是k个可变长度源符号的字节长度，被视为同一源块的一部分。设lmax为i=1，….上的最大值，洛伊的k。为了准备FEC编码器的源块，将每个源符号i以lmax-l_i零的后缀填充到长度lmax，然后将值l_i前置到该值的开头。因此，每个填充源符号的长度为x+lmax，假设需要x字节来存储可能值为0、…、lmax的整数，其中x是编码器和解码器都知道的协议常数。这些加垫的源符号，每个长度为x+lmax，与值n一起作为编码器的输入。编码器然后生成n-k个冗余符号，每个符号的长度为x+lmax。
The encoding symbols that are placed into packets consist of the original k varying length source symbols and n-k redundant symbols, each of length x+lmax. From any k of the received encoding symbols, the FEC decoder recreates the k original source symbols as follows. If all k original source symbols are received, then no decoding is necessary. Otherwise, at least one redundant symbol is received, from which the receiver can easily determine if the block is composed of variable- length source symbols: if the redundant symbol(s) is longer than the source symbols then the source symbols are variable-length. Note that in a variable-length block the redundant symbols are always longer than the longest source symbol, due to the presence of the prepended symbol- length. The receiver can determine the value of lmax by subtracting x from the length of a received redundant symbol. For each of the received original source symbols, the receiver can generate the corresponding padded source symbol as described above. Then, the input to the FEC decoder is the set of received redundant symbols, together with the set of padded source
放入分组中的编码符号包括原始k个可变长度源符号和n-k个冗余符号，每个符号的长度为x+lmax。从接收到的编码符号中的任意k个，FEC解码器如下重新创建k个原始源符号。如果接收到所有k个原始源符号，则无需解码。否则，至少接收一个冗余符号，接收器可以从中容易地确定块是否由可变长度源符号组成：如果冗余符号比源符号长，则源符号是可变长度的。注意，在可变长度块中，由于存在前置符号长度，冗余符号总是比最长的源符号长。接收机可以通过从接收到的冗余符号的长度中减去x来确定lmax的值。对于接收到的每个原始源符号，接收机可以如上所述生成相应的填充源符号。然后，FEC解码器的输入是接收到的冗余符号集以及填充源集
symbols constructed from the received original symbols. The FEC decoder then produces the set of k padded source symbols. Once the k padded source symbols have been recovered, the length l_i of original source symbol i can be recovered from the first x bytes of the ith padded source symbol, and then original source symbol i is obtained by taking the next l_i bytes following the x bytes of the length field.
从接收到的原始符号构造的符号。然后，FEC解码器产生k个填充源符号的集合。一旦k个填充源符号已经恢复，原始源符号i的长度l_i可以从第i个填充源符号的第一个x字节恢复，然后通过获取长度字段的x字节之后的下一个l_i字节来获得原始源符号i。
The use of FEC, in and of itself, imposes no additional security considerations versus sending the same information without FEC. However, just like for any transmission system, a malicious sender may try to inject packets carrying corrupted encoding symbols. If a receiver accepts one or more corrupted encoding symbol, in place of authentic ones, then such a receiver may reconstruct a corrupted object.
与在没有FEC的情况下发送相同的信息相比，FEC的使用本身并没有带来额外的安全考虑。然而，就像任何传输系统一样，恶意发送方可能会尝试注入携带损坏编码符号的数据包。如果接收器接受一个或多个损坏的编码符号来代替真实的编码符号，那么这样的接收器可以重建损坏的对象。
Application-level transmission object authentication can detect the corrupted transfer, but the receiver must discard the transferred object. By injecting corrupted encoding symbols, they are accepted as valid encoding symbols by a receiver, which at the very least, is an effective denial of service attack.
应用程序级传输对象身份验证可以检测损坏的传输，但接收方必须丢弃传输的对象。通过注入损坏的编码符号，接收器将其作为有效的编码符号接受，这至少是一种有效的拒绝服务攻击。
In light of this possibility, FEC receivers may screen the source address of a received symbol against a list of authentic transmitter addresses. Since source addresses may be spoofed, transport protocols using FEC may provide mechanisms for robust source authentication of each encoding symbol. Multicast routers along the path of a FEC transfer may provide the capability of discarding multicast packets that originated on that subnet, and whose source IP address does not correspond with that subnet.
鉴于这种可能性，FEC接收机可以对照真实发射机地址列表来屏蔽接收符号的源地址。由于源地址可能是伪造的，所以使用FEC的传输协议可以提供用于每个编码符号的健壮源认证的机制。沿FEC传输路径的多播路由器可提供丢弃源自该子网且其源IP地址与该子网不对应的多播分组的能力。
It is recommended that a packet authentication scheme such as TESLA [14] be used in conjunction with FEC codes. Then, packets that cannot be authenticated can be discarded and the object can be reliably recovered from the received authenticated packets.
建议将数据包认证方案（如TESLA[14]）与FEC码结合使用。然后，可以丢弃不能被认证的包，并且可以从接收到的认证包可靠地恢复对象。
The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights.
IETF已收到关于本文件所含部分或全部规范的知识产权声明。有关更多信息，请查阅在线权利主张列表。
Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document.
感谢Vincent Roca和Hayder Radha对本文件的详细评论。
[1] Acharya, S., Franklin, M. and S. Zdonik, "Dissemination - Based Data Delivery Using Broadcast Disks", IEEE Personal Communications, pp.50-60, Dec 1995.
[1] Acharya，S.，Franklin，M.和S.Zdonik，“使用广播磁盘进行基于传播的数据传输”，IEEE个人通信，第50-60页，1995年12月。
[2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984.
[2] Blahut，R.E.，“差错控制码的理论与实践”，马萨诸塞州艾迪生·韦斯利，1984年。
[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
[3] Bradner，S.，“互联网标准过程——第3版”，BCP 9，RFC 2026，1996年10月。
[4] Byers, J.W., Luby, M., Mitzenmacher, M. and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998.
[4] Byers，J.W.，Luby，M.，Mitzenmacher，M.和A.Rege，“批量数据可靠分发的数字喷泉方法”，ACM SIGCOMM'98论文集，加拿大温哥华，1998年9月。
[5] Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J. and M. Mitzenmacher, "Generating high weight encoding symbols using a basis", U.S. Patent No. 6,411,223, June 25, 2002.
[5] Haken，A.，Luby，M.，Horn，G.，Hernek，D.，Byers，J.和M.Mitzenmacher，“使用基生成高权重编码符号”，美国专利号6411223，2002年6月25日。
[6] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001.
[6] Luby，M.，“通信系统的信息加法代码生成器和解码器”，美国专利号630487，2001年10月23日。
[7] Luby, M., "Information Additive Group Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,320,520, November 20, 2001.
[7] Luby，M.，“通信系统的信息加法组码发生器和解码器”，美国专利号6320520，2001年11月20日。
[8] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,373,406, April 16, 2002.
[8] Luby，M.，“通信系统的信息加法代码生成器和解码器”，美国专利号6373406，2002年4月16日。
[9] Luby, M. and M. Mitzenmacher, "Loss resilient code with double heavy tailed series of redundant layers", U.S. Patent No. 6,195,777, February 27, 2001.
[9] Luby，M.和M.Mitzenmacher，“具有双重尾冗余层系列的抗丢失代码”，美国专利号6195777，2001年2月27日。
[10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D. and V. Stemann, "Message encoding with irregular graphing", U.S. Patent No. 6,163,870, December 19, 2000.
[10] Luby，M.，Mitzenmacher，M.，Shokrollahi，A.，Spielman，D.和V.Stemann，“带有不规则图形的消息编码”，美国专利号6163870，2000年12月19日。
[11] Luby, M., Mitzenmacher, M., Shokrollahi, A. and D. Spielman, "Efficient Erasure Correcting Codes", IEEE Transactions on Information Theory, Special Issue: Codes on Graphs and Iterative Algorithms, pp. 569-584, Vol. 47, No. 2, February 2001.
[11] Luby，M.，Mitzenmacher，M.，Shokrollahi，A.和D.Spielman，“高效纠错码”，IEEE信息论交易，特刊：图上的码和迭代算法，第569-584页，第47卷，第2期，2001年2月。
[12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Loss resilient decoding technique", U.S. Patent No. 6,073,250, June 6, 2000.
[12] Luby，M.，Shokrollahi，A.，Stemann，V.，Mitzenmacher，M.和D.Spielman，“抗丢失解码技术”，美国专利号6073250，2000年6月6日。
[13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Irregularly graphed encoding technique", U.S. Patent No. 6,081,909, June 27, 2000.
[13] Luby，M.，Shokrollahi，A.，Stemann，V.，Mitzenmacher，M.和D.Spielman，“不规则图形编码技术”，美国专利号6081909，2000年6月27日。
[14] Perrig, A., Canetti, R., Song, D. and J.D. Tygar, "Efficient and Secure Source Authentication for Multicast", Network and Distributed System Security Symposium, NDSS 2001, pp. 35-46, February 2001.
[14] Perrig，A.，Canetti，R.，Song，D.和J.D.Tygar，“多播的高效和安全源认证”，网络和分布式系统安全研讨会，NDSS 2001，第35-46页，2001年2月。
[15] Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997.
[15] Rizzo，L.“可靠计算机通信协议的有效擦除码”，《ACM SIGCOMM计算机通信评论》，第27卷，第2期，第24-36页，1997年4月。
[16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997.
[16] Rizzo，L.，“关于软件FEC的可行性”，DEIT技术报告，http://www.iet.unipi.it/~luigi/softfec.ps，1997年1月。
Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538
迈克尔·鲁比数字喷泉39141加利福尼亚州弗里蒙特市中心大道300号套房94538
EMail: luby@digitalfountain.com
EMail: luby@digitalfountain.com
Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134
Lorenzo Vicisano Cisco Systems，Inc.170 West Tasman Dr.，美国加利福尼亚州圣何塞，邮编：95134
EMail: lorenzo@cisco.com
EMail: lorenzo@cisco.com
Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105
吉姆GMMELL微软研究455市场S.Syz 1690旧金山，CA，94105
EMail: jgemmell@microsoft.com
EMail: jgemmell@microsoft.com
Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy
路易吉·里佐·迪普。迪宁。意大利比萨信息大学经迪奥蒂萨尔维256126
EMail:luigi@iet.unipi.it
电邮：luigi@iet.unipi.it
Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704
马克·汉德利ICSI互联网研究中心1947年加利福尼亚州圣伯克利中心，美国，94704
EMail: mjh@icir.org
EMail: mjh@icir.org
Jon Crowcroft Marconi Professor of Communications Systems University of Cambridge Computer Laboratory William Gates Building J J Thomson Avenue Cambridge CB3 0FD
Jon Crowcroft Marconi通信系统教授剑桥大学计算机实验室威廉盖茨大厦J J汤姆逊大道剑桥CB3 0FD
EMail: Jon.Crowcroft@cl.cam.ac.uk
EMail: Jon.Crowcroft@cl.cam.ac.uk
Copyright (C) The Internet Society (2002). All Rights Reserved.
版权所有（C）互联网协会（2002年）。版权所有。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
本文件及其译本可复制并提供给他人，对其进行评论或解释或协助其实施的衍生作品可全部或部分编制、复制、出版和分发，不受任何限制，前提是上述版权声明和本段包含在所有此类副本和衍生作品中。但是，不得以任何方式修改本文件本身，例如删除版权通知或对互联网协会或其他互联网组织的引用，除非出于制定互联网标准的需要，在这种情况下，必须遵循互联网标准过程中定义的版权程序，或根据需要将其翻译成英语以外的其他语言。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上述授予的有限许可是永久性的，互联网协会或其继承人或受让人不会撤销。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
本文件和其中包含的信息是按“原样”提供的，互联网协会和互联网工程任务组否认所有明示或暗示的保证，包括但不限于任何保证，即使用本文中的信息不会侵犯任何权利，或对适销性或特定用途适用性的任何默示保证。
Acknowledgement
确认
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC编辑功能的资金目前由互联网协会提供。