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
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.
このメモは効率的に提供及び/又はIPマルチキャストを用いて一対多信頼できるデータ転送のための信頼性を増強するための前方誤り訂正（FEC）符号の使用を記載しています。この文脈において、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
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では、受信機は、失われたパケットの再送信のための要求を送信する送信者に戻ってチャンネルを使用しています。 TCP / IPの普及の成功によって証明されるようにARQは、一対一の信頼性の高いプロトコルに適しています。 ARQはまた、1対多の信頼性プロトコルのための効果的な信頼性のツールとなって、そしていくつかの信頼性の高いIPマルチキャストプロトコルのために特にました。多くの受信機は、送信者に戻って送信し、受信機からのこれらの要求を送信するバックチャネルを必要としているのでしかし、1対非常に-多くの信頼性のプロトコルのために、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, 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.
このような衛星伝送のように、すべての非常に限られた容量のバックチャネル又は全くバックチャネルのいずれかがあるためARQは高価または不可能のいずれかである環境では、信頼性データカルーセルアプローチが時々使用される[1]。データカルーセルでは、我々は以下のソースシンボルを呼び出して、データの同じ長さの部分、送信者へのパーティションオブジェクトは、パケットにそれらを配置して、継続的サイクルを通じて、これらのパケットを送信します。彼らは、各パケットのコピーを受信するまで、受信機は、継続的にパケットを受信します。データカルーセルは、受信機から送信側に流れるデータがないので、それは何のバックチャネルを必要としないという利点があります。しかし、データカルーセルにも制限があります。受信機は、送信の1ラウンドでパケットが失われた場合、それは再びそのパケットを受信する機会を持つ前に、例えば、それは全体のラウンドを待たなければなりません。また、これは送信者として、を通じて継続的サイクルを、帯域幅の無駄な使用を引き起こし、何の受信機は、パケットが欠落しなくなるまでパケットを送信します。
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マルチキャストのような一対多信頼性プロトコルのため、他の信頼性の方法を増強または置換するために使用することができ、信頼性の方法を提供します。私たちは、最初に簡単に信頼性の高いIPマルチキャストのコンテキストでその使用を検討する前に、FECコードの基本的な性質と種類のいくつかを確認します。その後、我々は、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マルチキャストプロトコルの場合、ネットワーク層は、破損したパケットを検出し、それらを廃棄またはトランスポート層は、破損したパケットを破棄し、パケットの認証を使用することができるであろう。したがって、IPマルチキャストプロトコルにFECコードの主な用途は、消失訂正の通りです。ペイロードが生成され、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符号器の各用途に変えることができ、またはそれを固定することができます。これらの符号化シンボルを送信するためのパケットに配置されます。各パケットに入れ符号化シンボルの数パケット毎に変化することができる、またはシンボルの固定数（多くの場合、1つ）が、各パケットに入れることができます。また、各パケットに、そのパケットで運ば特定の符号化シンボルを識別するために十分な情報が配置されています。符号化シンボルを含むパケットを受信すると、受信機は、K個のソースシンボルの正確なコピーを再作成するために、対応するFECデコーダにこれらの符号化シンボルを供給する。理想的には、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個の符号化シンボルの合計を生成します。それはK個のソースシンボルとn-k個の冗長シンボルで構成される合計でN個の符号化シンボルの符号化ブロックを得たN-k個の冗長シンボルを生成した場合エンコーダが系統的です。
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個の符号化シンボルの受信が、その場合、受信オーバヘッドが0％、K個のソースシンボルを回復するのに十分である場合、上記の定義は、理想的な状況を説明します。いくつかの実用的なFEC符号は、k個の符号化シンボルが必要とされるわずかに超えるK個のソースシンボルを回復します。 K×（1枚の+ EP）符号化シンボルが必要な場合はK * 1.05符号化シンボルが必要な場合、我々は受信オーバヘッドがEP * 100％であると言う、例えば、次に受信オーバヘッドは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コードを分類します。小さいFECコードは、kの小さな値の符号化および復号化の処理時間の要件の点で効率的であり、そして大FECコードは、kのはるかに大きな値のための符号化及び復号化のために効率的です。 L倍に比例したNK倍に比例したk個のソースシンボルの長さを倍をコードしているブロックFECコードの実装、および復号時間は、Lは、Kのうち、欠落したソースシンボルの数であるk個のソースシンボルの長さがあります受信された符号化シンボル、LはKと同じ大きさであることができます。なぜならkおよびN-Kの積として符号化及び復号化時間の成長速度で、これらは、典型的には、小ブロックFECコードであると考えられます。 n個の符号化シンボルを生成することができ、n個の符号化シンボルの長さに比例した時間でk個のソースシンボルを復号することができる小型の受信オーバーヘッドでブロックFECコードがあります。これらのコードは、大きなブロックのFEC符号であると考えられています。その長さにほぼ比例した時間内に各符号化シンボルを生成することができ、そしてそれらの長さにほぼ比例した時間内にすべてのK個のソースシンボルを復号することができる小型の受信オーバーヘッドで拡張可能なFEC符号があります。これらは、大規模な拡張可能な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 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.
理想的には、IPマルチキャストの文脈におけるFEC符号は、各パケットに関係なく、以前のパケット受信パターンのオブジェクトを再構成するために受信機に完全に有用で受信するように、パケットで送信される符号化シンボルを生成するために使用することができます。いくつかのパケットではなく、失われたパケットの特定の再送を要求またはパケットがデータカルーセルを用いて再送信されるまで待ってから、送信者と受信者との間の輸送中に失われた場合したがって、受信機は、到着したパケットの任意の他の後続の同じ番号を使用することができオブジェクトを再構築します。これらのパケットは積極的に送信することができるいずれか、またはそれらを明示的に受信機を要求することができます。これは、同じパケットを受信機が以前に別のパケット損失パターンを経験している場合でも、オブジェクトを再構成するために、すべての受信機に完全に有用であることを意味します。このプロパティは、低減あるいは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 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.
他の信頼できるIPマルチキャストプロトコルのために、FECコードは、私たちがFECデータカルーセルを呼び出して、信頼性を提供するために、データカルーセル方式で使用されています。たとえば、次のように大ブロックFECコードを使用してFECデータカルーセルは、仕事ができます。大ブロックFECエンコーダは、1つのブロックとしてオブジェクトのすべてのK個のソースシンボルを考慮して、n個の符号化シンボルを生成します。センダサイクルを介して、各ラウンドにおいて同じ順序でパケット内のN個の符号化シンボルを送信します。 FECデータカルーセルは、データカルーセルよりもパケット損失に対するより良い保護を持つことができます。例えば、受信機は、任意の時点での伝送に参加することができ、そして、限り、受信機が次のn個の符号化シンボルの送信中に少なくともk個の符号化シンボルを受信するように、受信機は、完全にオブジェクトを回復することができます。これは、受信機は、符号化シンボルを通るパスの途中でパケットの受信を開始する場合も同様です。オブジェクトがブロックに分割され、ショートブロック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 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:
非常に低損失の条件の下でパケット損失を修復するのに有効であるいくつかの非常に単純なコードがあります。例えば、単一の損失からの保護を提供するために固定サイズのソースシンボルにオブジェクトを分割し、すべてのソースシンボルのパリティ（XOR）である冗長シンボルを追加することです。パケットペイロードが512バイトである場合、それは、パケットのペイロードの中に完全に収まるようにソースシンボルのサイズが選択され、すなわち各ソースシンボルは512バイトです。各パケットのヘッダは、ペイロードを識別するのに十分な情報を含んでいます。これは、シンボルIDを符号化する例です。符号化シンボルIDは、この例では2つの部分で構成することができます。最初の部分は、符号化シンボルは、ソースシンボルであり、符号化シンボルは、冗長シンボルである場合は0に等しい場合1に等しく、符号化フラグです。符号化フラグはソースシンボルIDはK-1を0から番号付けすることができ、冗長シンボルIDができ0である場合、符号化フラグが1と冗長シンボルIDである場合、符号化シンボルIDの第2の部分は、ソースシンボルIDでありますオブジェクトが値、B、CおよびDを有する4つのソースシンボルで構成されている場合、その後、冗長シンボルの値がEであり、例えば0で= 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は、最初の値は、符号化フラグである第2の値は、ソースシンボルIDまたは冗長シンボルIDのいずれかである最初の2つの値からなります。コロンの後のパケットの部分は、符号化シンボルの値です。オブジェクトの任意の単一のソースシンボルは、他のすべてのシンボルのパリティとして回収することができます。例えば、パケットの場合
(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電子= 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を形成する別の方法は、K個のソースシンボルと値kに値0、...、K-1対応は、k個のソースシンボルのXORである冗長シンボルに対応させることです。
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個のソースシンボルからなるソースブロックは、関連する符号化ブロックからK + 1符号化シンボルのいずれ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 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.
パリティを使用して冗長シンボルを追加するもう少し洗練された方法を用いることも可能です。例えば、一つの缶群のP X Pの正方行列、にオブジェクトのKのソースシンボルからなるブロックここで、p = SQRT（K）。次いで、行ごとに冗長シンボルは、行のすべてのソースシンボルのパリティである添加されます。同様に、各列の冗長シンボルは、列内のすべてのソースシンボルのパリティであることが追加されます。次いで、行列の任意の行は、行のp + 1つのシンボルの任意Pから回収することができ、同様に任意の列のため。この技術を用いて、より高い次元の製品コードを使用することもできます。しかし、1シンボルの損失の可能性パターンに向けたいくつかの考えなしにこれらの構造を使用しての警戒する必要があります。理想的には、一方が取得したいプロパティは、K個のソースシンボルは、N個の符号化シンボルに符号化されるならば、K個のソースシンボルは、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マルチキャストプロトコル[2]ブロック（n、k）はFECコードを使用してもよいです。このようなコードのために、K個のソースシンボルは、符号化シンボルのいずれkは元のk個のソースシンボルを再構築するために使用することができるように、N> K個の符号化シンボルに符号化されます。直接オブジェクト全体を符号化するために使用される場合したがって、これらのコードには、受信オーバーヘッドを有していません。ブロック符号は、n個の符号化シンボルは、K個のソースシンボルおよび冗長シンボルのサイズは、ソースシンボルと同じであり、これらのk個のソースシンボルから生成されたN-k個の冗長シンボル、からなることを意味し、通常は系統的です。例えば、前節で説明した第1の単純なコード（XOR）が（K + 1、K）符号です。これは損失に対するより良い保護を提供することが可能と一般的には、K + 1 nより大きな選択する自由は、望ましいです。コードのこれらのタイプの一般的な例は、有限フィールドを使用して、代数的方法に基づいているリードソロモン符号のクラスです。 （n、k）はFEC消去符号の実装は、パーソナルコンピュータ、[16]で使用されるのに十分に効率的です。例えば、[15]の符号化及び復号化は定数Cは分によって上部に制限される10〜80バイト/さまざまなヴィンテージとjのPentiumクラスのマシンのための第二のオーダーであるC / J、として減衰速度実装について説明します（K、NK）。
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.
大きな値は、符号化及び復号化は法外に高価なものとして、実際には、kの値は、nは小さいようなFECコードについて（256以下など）でなければなりません。多くのオブジェクトをkとシンボル長（1キロバイトのシンボルを使用して、K = 16のために16キロバイトよりも例えば大きい）の妥当な値のk個のシンボルよりも長い、それらは、ソースブロックの数に分割することができます。各ソースブロックは、kは、異なるソースブロックの間で変化し得るソースシンボル、いくつかの数kから成ります。 FECエンコーダは、符号化ブロック内の符号化シンボルの数nは、各ソースブロックに対して変化してもよいn個の符号化シンボルを符号化ブロックにk個のソースシンボルのソースブロックを符号化するために使用されます。完全にオブジェクトを回復する受信機のために、K個のソースシンボルからなる各ソースブロックについて、（すなわち、異なる符号化シンボルIDを持つ）異なる符号化シンボルをk個の対応する符号化ブロックから受信されなければなりません。いくつかの符号化ブロックのために、より多くの符号化シンボルは、過剰な符号化シンボルが破棄される場合に対応するソースブロック内のソースシンボルが、そこよりも受信することができます。例えば、符号化構造は、図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によって識別することができます。ブロック内の符号化シンボルを同定する1つの方法は、ソースシンボルまたはソースシンボルIDまたは冗長シンボルIDのいずれかと一緒に冗長シンボルのいずれかとして記号を識別する符号化フラグの組み合わせを使用することです。例えば、1の符号化フラグの値は、符号化シンボルは、ソースシンボルであることを示すことができ、0は、冗長シンボルであることを示すことができます。ソースシンボルIDはK-1を0から番号付けすることができ、冗長シンボル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
オブジェクトは、値A、B、C、D、E、F、G、H、I、およびJ、及びK = 5、N = 8と10個のソースシンボルからなる場合、例えば、次にからなる二つのソースブロックが存在します5つのシンボル毎、8つのシンボル毎からなる二符号化ブロックが存在します。 P、QおよびRは、第1の符号化ブロックのための冗長シンボルの値とすると、X、YおよびZは、第2の符号化ブロックのための冗長シンボルの値とします。そして、符号化シンボルは、一緒にその識別子であります
(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：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のいずれかと一緒に符号化フラグから構成され符号化フラグの値。符号化シンボルの値は、コロンの後に書かれています。各ブロックは、任意の5そのブロックに関連付けられた8つの符号化シンボルのから回収することができます。の、例えば、受信
(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.
第2のソースブロックを回復するのに十分です。
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 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.
トルネード符号[12]、[13]、[10]、[11]、[9]小ブロックFECコードに代わるものを提供する大規模なブロックFECコードです。 （N、K）トルネード符号、すなわち、小受信オーバヘッドがある、k個のソースシンボルを回復するために、n個の符号化シンボルのうちKよりわずかに多くを必要とします。非ゼロの受信オーバヘッドの小さなコストの利点は、kの値は、数万のオーダーであってもよく、依然として符号化および復号化が効率的であるということです。なぜなら、メモリの考慮事項のため、実際にはnの値がN = 2Kを、例えばk個の小さな倍数に制限されます。例えば、[4]、kは数万であり、n = 2kのとき符号化及び復号化速度は、様々なヴィンテージのPentiumクラスのマシンの毎秒メガバイト数十あるトルネード符号の実装を記述する。 K、Nのような値の受信オーバヘッドは5~10％の範囲です。トルネード符号はそれぞれ、異なる物体長のためのすべての送信者と受信者に通信される帯域情報のうちの大量を必要とし、物体の長さの時間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.
トルネード符号は、符号化パケットのランダム部分の受信に対して平均で低い受信オーバーヘッドを有するように設計されています。したがって、受信機は、低い受信オーバーヘッドでオブジェクトを再構築することができることを確実にするために、パケットは、送信前にランダムな順序に並べ替えされています。
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 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.
LT符号は、[6]、[7]、[8]、[5]小受信オーバーヘッドで大きな拡張可能なFECコードの一例です。 LT符号は、ランダムかつ独立に、他のすべての符号化シンボルの各符号化シンボルを生成するためにランダム化を使用します。トルネード符号のような、ソースシンボルkの数は数千から数百数十、ソフトウェアにおいて効率的に実行するエンコーダおよびデコーダで、LTコード、即ちため非常に大きくてもよいです。 kは、数千の高い数十であるとき、例えばLT符号の符号化および復号化の速度は、様々なヴィンテージのPentiumクラスのマシンの毎秒3〜20メガバイトの範囲です。オンデマンドで必要に応じて、LTエンコーダは、わずかかなど、多くの符号化シンボルを生成することができます。新たな符号化シンボルは、LT符号化器によって生成される場合には、一意の符号化シンボルは、ソースシンボルから生成する方法について説明し、ランダムに選択された符号化シンボルIDに基づいています。一般的に、各符号化シンボルID値が一意の符号化シンボルに相当し、例えば符号化シンボルIDは4バイトである場合ことができる符号化シンボルのスペースは、約4億です。したがって、特定の符号化シンボルは、任意の他の特定の符号化シンボルと同じである可能性が可能な符号化シンボルIDの数に反比例します。 LTデコーダは、非常に高い確率でKよりもわずかにランダムかつ独立に生成された符号化シンボルのセットの受信がk個のソースシンボルを再構築するのに十分であるという特性を有しています。 kは、数千の数十〜数百のオーダーである場合、例えば、受信オーバーヘッドが損失条件下での試験の数百万でない障害が発生して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 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.
小さなブロック符号のように、オブジェクトは、それがLT符号を用いた場合にブロックにそれを分割することは理にかなっていることを十分な大きさである点があります。パケットペイロード長倍ソースシンボルの数は、オブジェクトのサイズ以下であるときはいつでも一般の目的は、ブロックに分割されます。したがって、場合には、パケットのペイロードは1024バイトであり、ソースシンボルの最大数は128,000次いで、128メガバイトを超える任意のオブジェクトは、複数のブロックに分割されています。一つは、所望の受信オーバーヘッドのトレードオフに対する所望の符号化及び復号化の速度に応じて、使用するソースシンボルの最大数を選択することができます。符号化シンボルは、一意ブロック番号（オブジェクトが複数のブロックに分割することが十分に大きい場合）、符号化シンボルIDによって識別することができます。ブロック番号は、それらが使用される場合、一般的に連続的オブジェクト内のゼロから始まる番号が付けられています。符号化シンボルが送信される場合にブロック番号および符号化シンボルIDは、両方の彼らの範囲から一様にランダムに選択されます。例えば、ソースシンボルの数は128,000であり、ブロック数が次に2であると仮定し、LT符号化器によって生成された各パケットの形式（：Y B、X）のものであってもよいです。この例では、最初の値は、ブロック番号を識別し、第2の値は、ブロック内の符号化シンボルを識別する。この例では、ブロック番号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を聞かせ、...、同じソースブロックの一部とみなされるべき長さのソースシンボルを変えるkのバイトの長さであるL_K。最大ことLMAXましょう超えるI = 1、...、L_iをのK。 FECエンコーダ、パッドLMAX-L_iをゼロの接尾辞長LMAX各ソースシンボルI OUTのためのソースブロックを準備し、この値L_iをの先頭の前に付加します。このように、各パディングソースシンボルは、それが可能な値0の整数を格納するためにxバイトを取ると仮定すると、長さX + LMAXであり、...、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 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.
パケット内に配置される符号化シンボルは、長さ、ソースシンボルとn-k個の冗長シンボル、長さx + LMAXの各々を変える元Kから成ります。次のように受信された符号化シンボルのいずれkから、FECデコーダは、k個のオリジナルソースシンボルを再作成します。全てのkオリジナルソースシンボルが受信される場合、いかなる復号化は不要です。ブロックは可変長ソースシンボルから構成されている場合はそうでなければ、少なくとも一つの冗長シンボルが受信され、受信機は容易に決定することができ、そこから：冗長シンボル（s）は、より長いソースシンボルを超える場合、ソースシンボルが可変長であります。冗長シンボルが原因付加シンボル - 長さが存在するために、最長のソースシンボルよりも常に長い可変長ブロック内ことに留意されたいです。受信機は、受信された冗長シンボルの長さからXを減算することによりLMAXの値を決定することができます。上記のように受信したオリジナルソースシンボルのそれぞれについて、受信機は、対応するパッド入りのソースシンボルを生成することができます。次に、FECデコーダへの入力は、一緒に受信し、元のシンボルから構成されたパディングソースシンボルのセットと、受信された冗長シンボルのセットです。 FECデコーダは、次に、Kパディングソースシンボルのセットを生成します。 Kパディングソースシンボルが回復された後、元のソースシンボルの長さL_iをiは、i番目のパディングソースシンボルの最初のxバイトから回収することができ、その後、元のソースシンボルiはXの次L_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.
このようなテスラ[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.
この文書ではその詳細なコメントヴィンセントロカとHayderラダに感謝します。
[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.、フランクリン、M.およびS. Zdonik、 - 、IEEEパーソナル・コミュニケーションズ、pp.50-60、1995年12月 "普及ブロードキャストディスクの使用基づいてデータ配信"。
[2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984.
[2]、アディソンウェズリー、MA、1984 Blahut、R.E.、 "誤り制御符号の理論と実践"。
[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
[3]ブラドナーの、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]バイヤーズ、J.W.、ルビー、M.、Mitzenmacher、M.とA.レゲ、 "バルクデータの信頼性の高い配信にデジタル泉アプローチ"、議事録の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]派遣、A.、ルビー、M.、ホーン、G.、Hernek、D.、バイヤーズ、J.とM. Mitzenmacher、 "基準を用いて高い重量符号化シンボルを生成"、米国特許第6411223 6月25、2002。
[6] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001.
[6]ルビー、M.、「情報添加通信システムのためのコードジェネレータおよびデコーダ」、米国特許第6307487、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]ルビー、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]ルビー、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]ルビー、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]ルビー、M.、Mitzenmacher、M.、ショクロラヒ、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]ルビー、M.、Mitzenmacher、M.、ショクロラヒ、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]ルビー、M.、ショクロラヒ、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]ルビー、M.、ショクロラヒ、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.、カネッティ、R.、歌、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コンピュータコミュニケーションレビュー、Vol.27、第2号、pp.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.
"ソフトウェアFECの可能性について" [16] Rizzo氏、L.、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フリーモント、CA 94538
EMail: luby@digitalfountain.com
メールアドレス：luby@digitalfountain.com
Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134
ロレンツォVicisanoシスコシステムズ、株式会社170西タスマン博士は、サンノゼ、CA、USA、95134
EMail: lorenzo@cisco.com
メールアドレス：lorenzo@cisco.com
Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105
ジム・Gemmellマイクロソフトリサーチ455市場セント＃1690サンフランシスコ、CA、94105
EMail: jgemmell@microsoft.com
メールアドレス：jgemmell@microsoft.com
Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy
ルイジ・リゾディップ。のIng。ディオーティソルビ2、56126ピサ、イタリア経由ピサの情報大学
EMail:luigi@iet.unipi.it
メールアドレス：luigi@iet.unipi.it
Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704
インターネットリサーチ1947センターセントバークレー、CA、USA、94704のためのマーク・ハンドリーICSIセンター
EMail: mjh@icir.org
メールアドレス：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
ケンブリッジの通信システム大学のコンピュータ研究所のウィリアム・ゲイツビルJ JトムソンアベニューケンブリッジCB3 0FDのジョン・クロークロフトマルコーニ教授
EMail: Jon.Crowcroft@cl.cam.ac.uk
メールアドレス：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 Editor機能のための基金は現在、インターネット協会によって提供されます。