[要約] RFC 5053は、オブジェクトの配信におけるRaptor Forward Error Correction（FEC）スキームについての標準仕様です。このRFCの目的は、効率的で信頼性の高いデータ転送を実現するために、Raptor FECスキームの詳細な仕様を提供することです。
Network Working Group M. Luby
Request for Comments: 5053 Digital Fountain
Category: Standards Track A. Shokrollahi
EPFL
M. Watson
Digital Fountain
T. Stockhammer
Nomor Research
October 2007
Raptor Forward Error Correction Scheme for Object Delivery
オブジェクト配信のためのラプターフォワードエラー補正スキーム
Status of This Memo
本文書の位置付け
This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.
このドキュメントは、インターネットコミュニティのインターネット標準トラックプロトコルを指定し、改善のための議論と提案を要求します。このプロトコルの標準化状態とステータスについては、「インターネット公式プロトコル標準」（STD 1）の現在のエディションを参照してください。このメモの配布は無制限です。
Abstract
概要
This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 1, for the Raptor forward error correction code and its application to reliable delivery of data objects.
このドキュメントでは、Raptor Forwardエラー補正コードと、データオブジェクトの信頼できる配信へのアプリケーションのFECエンコードID 1に対応する、完全に指定されたフォワードエラー補正（FEC）スキームについて説明します。
Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a source block of data. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols.
Raptorは噴水コードです。つまり、データのソースシンボルからエンコーダでエンコーダーを使用してエンコーダで生成できるため、噴水コードです。デコーダーは、ソースシンボルの数よりも数のエンコードシンボルのセットからソースブロックを回復できます。
The Raptor code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated.
ここで説明するRaptorコードは系統的コードです。つまり、すべてのソースシンボルは、生成できるエンコードシンボルの1つです。
Table of Contents
目次
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3
3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 3
3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 3
3.2. FEC Object Transmission Information (OTI) . . . . . . . . 4
3.2.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 4
3.2.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 5
4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Content Delivery Protocol Requirements . . . . . . . . . . 5
4.2. Example Parameter Derivation Algorithm . . . . . . . . . . 6
5. Raptor FEC Code Specification . . . . . . . . . . . . . . . . 8
5.1. Definitions, Symbols, and Abbreviations . . . . . . . . . 8
5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 8
5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 9
5.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 11
5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3. Object Delivery . . . . . . . . . . . . . . . . . . . . . 12
5.3.1. Source Block Construction . . . . . . . . . . . . . . 12
5.3.2. Encoding Packet Construction . . . . . . . . . . . . . 14
5.4. Systematic Raptor Encoder . . . . . . . . . . . . . . . . 15
5.4.1. Encoding Overview . . . . . . . . . . . . . . . . . . 15
5.4.2. First Encoding Step: Intermediate Symbol Generation . 16
5.4.3. Second Encoding Step: LT Encoding . . . . . . . . . . 20
5.4.4. Generators . . . . . . . . . . . . . . . . . . . . . . 21
5.5. Example FEC Decoder . . . . . . . . . . . . . . . . . . . 23
5.5.1. General . . . . . . . . . . . . . . . . . . . . . . . 23
5.5.2. Decoding a Source Block . . . . . . . . . . . . . . . 23
5.6. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 28
5.6.1. The Table V0 . . . . . . . . . . . . . . . . . . . . . 28
5.6.2. The Table V1 . . . . . . . . . . . . . . . . . . . . . 29
5.7. Systematic Indices J(K) . . . . . . . . . . . . . . . . . 30
6. Security Considerations . . . . . . . . . . . . . . . . . . . 43
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 44
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 44
9.1. Normative References . . . . . . . . . . . . . . . . . . . 44
9.2. Informative References . . . . . . . . . . . . . . . . . . 44
This document specifies an FEC Scheme for the Raptor forward error correction code for object delivery applications. The concept of an FEC Scheme is defined in [RFC5052] and this document follows the format prescribed there and uses the terminology of that document. Raptor Codes were introduced in [Raptor]. For an overview, see, for example, [CCNC].
このドキュメントは、オブジェクト配信アプリケーションのRaptor Forwardエラー補正コードのFECスキームを指定します。FECスキームの概念は[RFC5052]で定義されており、このドキュメントはそこで規定されている形式に従い、そのドキュメントの用語を使用します。ラプターコードは[Raptor]で導入されました。概要については、たとえば[CCNC]を参照してください。
The Raptor FEC Scheme is a Fully-Specified FEC Scheme corresponding to FEC Encoding ID 1.
Raptor FECスキームは、FECエンコードID 1に対応する完全に指定されたFECスキームです。
Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a block. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols.
Raptorは噴水コードです。つまり、ブロックのソース記号からエンコーダでエンコーダを使用することで必要なエンコードシンボルを生成できます。デコーダーは、ソースシンボルの数よりも数のエンコードシンボルのセットからソースブロックを回復できます。
The code described in this document is a systematic code, that is, the original source symbols can be sent unmodified from sender to receiver, as well as a number of repair symbols. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC3453].
このドキュメントで説明されているコードは体系的なコードです。つまり、元のソースシンボルは、送信者からレシーバーに変更されずに送信され、多くの修理記号を送信できます。信頼できるマルチキャストでのフォワードエラー補正コードの使用に関する詳細については、[RFC3453]を参照してください。
The code described here is identical to that described in [MBMS].
ここで説明するコードは、[MBMS]で説明されているコードと同じです。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].
「必須」、「そうしない」、「必須」、「shall」、「shall "、" ingle "、" should "、" not "、" becommended "、" bay "、および「optional」は、[RFC2119]に記載されているように解釈される。
The FEC Payload ID MUST be a 4 octet field defined as follows:
FECペイロードIDは、次のように定義される4オクテットフィールドでなければなりません。
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Block Number | Encoding Symbol ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID format
図1：FECペイロードID形式
Source Block Number (SBN), (16 bits): An integer identifier for the source block that the encoding symbols within the packet relate to.
ソースブロック番号（SBN）、（16ビット）：パケット内のエンコーディングシンボルが関連するソースブロックの整数識別子。
Encoding Symbol ID (ESI), (16 bits): An integer identifier for the encoding symbols within the packet.
シンボルID（ESI）、（16ビット）：パケット内のエンコードシンボルの整数識別子。
The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 5.
ソースブロック番号とエンコードシンボル識別子の解釈は、セクション5で定義されています。
The value of the FEC Encoding ID MUST be 1 (one), as assigned by IANA (see Section 7).
FECエンコードIDの値は、IANAによって割り当てられているように、1（1）でなければなりません（セクション7を参照）。
The Common FEC Object Transmission Information elements used by this FEC Scheme are:
このFECスキームで使用される一般的なFECオブジェクト伝送情報要素は次のとおりです。
- Transfer Length (F)
- 転送長（f）
- Encoding Symbol Length (T)
- シンボルの長さのエンコード（t）
The Transfer Length is a non-negative integer less than 2^^45. The Encoding Symbol Length is a non-negative integer less than 2^^16.
転送長は、2 ^^ 45未満の非陰性整数です。エンコードシンボルの長さは、2 ^^ 16未満の非陰性整数です。
The encoded Common FEC Object Transmission Information format is shown in Figure 2.
エンコードされた共通FECオブジェクト伝送情報形式を図2に示します。
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transfer Length |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: Encoded Common FEC OTI for Raptor FEC Scheme
図2：Raptor FECスキームのエンコードされた共通FEC OTI
NOTE 1: The limit of 2^^45 on the transfer length is a consequence of the limitation on the symbol size to 2^^16-1, the limitation on the number of symbols in a source block to 2^^13, and the limitation on the number of source blocks to 2^^16. However, the Transfer Length is encoded as a 48-bit field for simplicity.
注1：転送長の2 ^^ 45の制限は、シンボルサイズの2 ^^ 16-1への制限の結果であり、ソースブロックのシンボルの数の制限は2 ^^ 13、および2 ^^ 13の制限です。2 ^^ 16へのソースブロックの数の制限。ただし、トランスファー長は、簡単にするために48ビットフィールドとしてエンコードされます。
The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC Scheme:
次のパラメーターは、このFECスキームのスキーム固有のFECオブジェクトトランスミッション情報要素に掲載されています。
- The number of source blocks (Z)
- ソースブロックの数（z）
- The number of sub-blocks (N)
- サブブロックの数（n）
- A symbol alignment parameter (Al)
- シンボルアライメントパラメーター（AL）
These parameters are all non-negative integers. The encoded Scheme-specific Object Transmission Information is a 4-octet field consisting of the parameters Z (2 octets), N (1 octet), and Al (1 octet) as shown in Figure 3.
これらのパラメーターはすべて非陰性整数です。エンコードされたスキーム固有のオブジェクトトランスミッション情報は、図3に示すように、パラメーターZ（2オクテット）、N（1オクテット）、およびAL（1オクテット）からなる4-OCTETフィールドです。
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Z | N | Al |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Encoded Scheme-Specific FEC Object Transmission Information
図3：エンコードされたスキーム固有のFECオブジェクト伝送情報
The encoded FEC Object Transmission Information is a 14-octet field consisting of the concatenation of the encoded Common FEC Object Transmission Information and the encoded Scheme-Specific FEC Object Transmission Information.
エンコードされたFECオブジェクトトランスミッション情報は、エンコードされた一般的なFECオブジェクト伝送情報の連結とエンコードされたスキーム固有のFECオブジェクト伝送情報からなる14オクテットフィールドです。
These three parameters define the source block partitioning as described in Section 5.3.1.2.
これらの3つのパラメーターは、セクション5.3.1.2で説明されているように、ソースブロックパーティションを定義します。
This section describes the information exchange between the Raptor FEC Scheme and any Content Delivery Protocol (CDP) that makes use of the Raptor FEC Scheme for object delivery.
このセクションでは、Raptor FECスキームと、オブジェクト配信のためにRaptor FECスキームを使用するコンテンツ配信プロトコル（CDP）との間の情報交換について説明します。
The Raptor encoder and decoder for object delivery require the following information from the CDP:
オブジェクト配信用のRaptorエンコーダーとデコーダーには、CDPからの次の情報が必要です。
- The transfer length of the object, F, in bytes
- オブジェクトの転送長、f、バイト単位
- A symbol alignment parameter, Al
- シンボルアライメントパラメーター、al
- The symbol size, T, in bytes, which MUST be a multiple of Al
- シンボルサイズ、t、バイト、それはalの倍数でなければなりません
- The number of source blocks, Z
- ソースブロックの数、z
- The number of sub-blocks in each source block, N
- 各ソースブロックのサブブロックの数、n
The Raptor encoder for object delivery additionally requires:
オブジェクト配信用のRaptorエンコーダーには、次のことが必要です。
- the object to be encoded, F bytes
- エンコードされるオブジェクト、fバイト
The Raptor encoder supplies the CDP with the following information for each packet to be sent:
Raptorエンコーダーは、各パケットを送信する各パケットの次の情報をCDPに提供します。
- Source Block Number (SBN)
- ソースブロック番号（SBN）
- Encoding Symbol ID (ESI)
- シンボルIDのエンコード（ESI）
- Encoding symbol(s)
- シンボルをエンコードする
The CDP MUST communicate this information to the receiver.
CDPは、この情報を受信機に伝える必要があります。
This section provides recommendations for the derivation of the three transport parameters, T, Z, and N. This recommendation is based on the following input parameters:
このセクションでは、3つの輸送パラメーター、t、z、およびNの導出に関する推奨事項を示します。この推奨事項は、次の入力パラメーターに基づいています。
- F the transfer length of the object, in bytes
- fオブジェクトの転送長、バイト単位
- W a target on the sub-block size, in bytes
- wサブブロックサイズのターゲット、バイト単位
- P the maximum packet payload size, in bytes, which is assumed to be a multiple of Al
- Pバイト単位の最大パケットペイロードサイズ、これはAlの倍数であると想定されています
- Al the symbol alignment parameter, in bytes
- alは、バイト単位のシンボルアライメントパラメーターです
- Kmax the maximum number of source symbols per source block.
- kmaxソースブロックごとのソース記号の最大数。
Note: Section 5.1.2 defines Kmax to be 8192.
注：セクション5.1.2は、KMAXを8192と定義しています。
- Kmin a minimum target on the number of symbols per source block
- Kminソースブロックごとの記号数の最小ターゲット
- Gmax a maximum target number of symbols per packet Based on the above inputs, the transport parameters T, Z, and N are calculated as follows:
- GMAX上記の入力に基づいてパケットごとの最大ターゲット数のシンボル数、トランスポートパラメーターT、Z、およびNは次のように計算されます。
Let
させて
G = min{ceil(P*Kmin/F), P/Al, Gmax}
T = floor(P/(Al*G))*Al
Kt = ceil(F/T)
kt = ceil（f/t）
Z = ceil(Kt/Kmax)
z = ceil（kt/kmax）
N = min{ceil(ceil(Kt/Z)*T/W), T/Al}
The value G represents the maximum number of symbols to be transported in a single packet. The value Kt is the total number of symbols required to represent the source data of the object. The values of G and N derived above should be considered as lower bounds. It may be advantageous to increase these values, for example, to the nearest power of two. In particular, the above algorithm does not guarantee that the symbol size, T, divides the maximum packet size, P, and so it may not be possible to use the packets of size exactly P. If, instead, G is chosen to be a value that divides P/Al, then the symbol size, T, will be a divisor of P and packets of size P can be used.
値gは、単一のパケットで輸送されるシンボルの最大数を表します。値KTは、オブジェクトのソースデータを表すために必要なシンボルの総数です。上記のGおよびNの値は、下限と見なす必要があります。たとえば、これらの値を2つの最も近い電力に増やすことが有利かもしれません。特に、上記のアルゴリズムは、シンボルサイズのtが最大パケットサイズのPを分割することを保証するものではないため、サイズのパケットを正確に使用することはできない場合があります。P/ALを分割する値、次にシンボルサイズTはPの除数になり、サイズPのパケットを使用できます。
The algorithm above and that defined in Section 5.3.1.2 ensure that the sub-symbol sizes are a multiple of the symbol alignment parameter, Al. This is useful because the XOR operations used for encoding and decoding are generally performed several bytes at a time, for example, at least 4 bytes at a time on a 32-bit processor. Thus, the encoding and decoding can be performed faster if the sub-symbol sizes are a multiple of this number of bytes.
上記のアルゴリズムとセクション5.3.1.2で定義されているアルゴリズムは、サブシンボルサイズがシンボルアライメントパラメーターの倍数であることを確認します。これは、エンコードとデコードに使用されるXOR操作は、たとえば32ビットプロセッサで少なくとも4バイトで数バイトで数バイトで実行されるため、これは便利です。したがって、サブシンボルサイズがこのバイト数の倍数である場合、エンコードとデコードはより速く実行できます。
Recommended settings for the input parameters, Al, Kmin, and Gmax are as follows: Al = 4, Kmin = 1024, Gmax = 10.
入力パラメーターの推奨設定、AL、KMIN、およびGMAXは次のとおりです。Al= 4、kmin = 1024、gmax = 10。
The parameter W can be used to generate encoded data that can be decoded efficiently with limited working memory at the decoder. Note that the actual maximum decoder memory requirement for a given value of W depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than W.
パラメーターWを使用して、デコーダーでの制限された作業メモリを使用して効率的にデコードできるエンコードされたデータを生成できます。wの特定の値の実際の最大デコーダーメモリ要件は実装に依存しますが、ワーキングメモリを使用してデコードを実装することはWよりもわずかに大きいだけです。
For the purposes of this specification, the following terms and definitions apply.
この仕様の目的のために、次の用語と定義が適用されます。
Source block: a block of K source symbols that are considered together for Raptor encoding purposes.
ソースブロック：Raptorエンコーディングの目的で一緒に考慮されるKソース記号のブロック。
Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size.
ソースシンボル：エンコードプロセス中に使用されるデータの最小単位。ソースブロック内のすべてのソース記号のサイズは同じです。
Encoding symbol: a symbol that is included in a data packet. The encoding symbols consist of the source symbols and the repair symbols. Repair symbols generated from a source block have the same size as the source symbols of that source block.
エンコードシンボル：データパケットに含まれるシンボル。エンコーディングシンボルは、ソースシンボルと修理シンボルで構成されています。ソースブロックから生成された修復記号は、そのソースブロックのソース記号と同じサイズです。
Systematic code: a code in which all the source symbols may be included as part of the encoding symbols sent for a source block.
系統的コード：ソースブロックに送信されたエンコードシンボルの一部として、すべてのソースシンボルを含めることができるコード。
Repair symbol: the encoding symbols sent for a source block that are not the source symbols. The repair symbols are generated based on the source symbols.
修復シンボル：ソース記号ではないソースブロックに送信されるエンコードシンボル。修復記号は、ソース記号に基づいて生成されます。
Intermediate symbols: symbols generated from the source symbols using an inverse encoding process . The repair symbols are then generated directly from the intermediate symbols. The encoding symbols do not include the intermediate symbols, i.e., intermediate symbols are not included in data packets.
中間記号：逆エンコーディングプロセスを使用して、ソースシンボルから生成されたシンボル。修復記号は、中間記号から直接生成されます。エンコーディングシンボルには中間記号が含まれていません。つまり、中間記号はデータパケットに含まれていません。
Symbol: a unit of data. The size, in bytes, of a symbol is known as the symbol size.
シンボル：データの単位。シンボルのサイズは、シンボルサイズとして知られています。
Encoding symbol group: a group of encoding symbols that are sent together, i.e., within the same packet whose relationship to the source symbols can be derived from a single Encoding Symbol ID.
エンコーディングシンボルグループ：一緒に送信されるエンコードシンボルのグループ、つまり、ソースシンボルとの関係を単一のエンコードシンボルIDから導き出すことができるのと同じパケット内で。
Encoding Symbol ID: information that defines the relationship between the symbols of an encoding symbol group and the source symbols.
エンコーディングシンボルID：エンコードシンボルグループのシンボルとソースシンボルの関係を定義する情報。
Encoding packet: data packets that contain encoding symbols Sub-block: a source block is sometimes broken into sub-blocks, each of which is sufficiently small to be decoded in working memory. For a source block consisting of K source symbols, each sub-block consists of K sub-symbols, each symbol of the source block being composed of one sub-symbol from each sub-block.
エンコーディングパケット：エンコードシンボルを含むデータパケットサブブロック：ソースブロックがサブブロックに分割されることがあり、それぞれがワーキングメモリでデコードするのに十分に小さくなります。Kソースシンボルで構成されるソースブロックの場合、各サブブロックはkサブシンボルで構成され、各サブブロックからの1つのサブシンボルで構成されているソースブロックの各シンボルが構成されています。
Sub-symbol: part of a symbol. Each source symbol is composed of as many sub-symbols as there are sub-blocks in the source block.
サブシンボル：シンボルの一部。各ソースシンボルは、ソースブロックにサブブロックがあるのと同じくらい多くのサブシンボルで構成されています。
Source packet: data packets that contain source symbols.
ソースパケット：ソースシンボルを含むデータパケット。
Repair packet: data packets that contain repair symbols.
修理パケット：修理記号を含むデータパケット。
i, j, x, h, a, b, d, v, m represent positive integers.
I、J、X、H、A、B、D、V、Mは正の整数を表します。
ceil(x) denotes the smallest positive integer that is greater than or equal to x.
CEIL（x）は、x以上の最小の正の整数を示します。
choose(i,j) denotes the number of ways j objects can be chosen from among i objects without repetition.
[i、j）を選択すると、jオブジェクトが繰り返されることなくiオブジェクトの中から選択できる方法の数を示します。
floor(x) denotes the largest positive integer that is less than or equal to x.
フロア（x）は、x以下の最大の正の整数を示します。
i % j denotes i modulo j.
i％jは、i modulo jを示します。
X ^ Y denotes, for equal-length bit strings X and Y, the bitwise exclusive-or of X and Y.
x ^ yは、等しいビット文字列xおよびyの場合、ビットワイズの排他的またはxとyのことを示します。
Al denotes a symbol alignment parameter. Symbol and sub-symbol sizes are restricted to be multiples of Al.
ALは、シンボルアライメントパラメーターを示します。シンボルとサブシンボルのサイズは、Alの倍数に制限されています。
A denotes a matrix over GF(2).
aは、GF（2）上のマトリックスを示します。
Transpose[A] denotes the transposed matrix of matrix A.
転置[a]は、マトリックスAの転置マトリックスを示します。
A^^-1 denotes the inverse matrix of matrix A.
A ^^ -1は、行列Aの逆マトリックスを示します。
K denotes the number of symbols in a single source block.
Kは、単一のソースブロック内のシンボルの数を示します。
Kmax denotes the maximum number of source symbols that can be in a single source block. Set to 8192.
Kmaxは、単一のソースブロックにある可能性のあるソース記号の最大数を示します。8192に設定します。
L denotes the number of pre-coding symbols for a single source block.
Lは、単一のソースブロックの事前コードシンボルの数を示します。
S denotes the number of LDPC symbols for a single source block.
Sは、単一のソースブロックのLDPC記号の数を示します。
H denotes the number of Half symbols for a single source block.
hは、単一のソースブロックの半分のシンボルの数を示します。
C denotes an array of intermediate symbols, C[0], C[1], C[2],..., C[L-1].
Cは、中間記号の配列を示します。C[0]、C [1]、C [2]、...、C [L-1]。
C' denotes an array of source symbols, C'[0], C'[1], C'[2],..., C'[K-1].
C 'は、ソース記号の配列を示します。C' [0]、C '[1]、C' [2]、...、C '[k-1]。
X a non-negative integer value
x非陰性整数値
V0, V1 two arrays of 4-byte integers, V0[0], V0[1],..., V0[255] and V1[0], V1[1],..., V1[255]
V0、V1 4バイト整数の2つの配列、V0 [0]、V0 [1]、...、V0 [255]およびV1 [0]、V1 [1]、...、V1 [255]
Rand[X, i, m] a pseudo-random number generator
rand [x、i、m]擬似ランダム数ジェネレーター
Deg[v] a degree generator
deg [v]学位ジェネレーター
LTEnc[K, C ,(d, a, b)] a LT encoding symbol generator
ltenc [k、c、（d、a、b）] a ltエンコーディングシンボルジェネレーター
Trip[K, X] a triple generator function
トリップ[k、x]トリプルジェネレーター機能
G the number of symbols within an encoding symbol group
gエンコードシンボルグループ内のシンボルの数
GF(n) the Galois field with n elements.
GF（n）n要素を持つガロワフィールド。
N the number of sub-blocks within a source block
nソースブロック内のサブブロックの数
T the symbol size in bytes. If the source block is partitioned into sub-blocks, then T = T'*N.
tバイトのシンボルサイズ。ソースブロックがサブブロックに分割されている場合、t = t '*n。
T' the sub-symbol size, in bytes. If the source block is not partitioned into sub-blocks, then T' is not relevant.
サブシンボルサイズ、バイトで。ソースブロックがサブブロックに分割されていない場合、t 'は関連性がありません。
F the transfer length of an object, in bytes
fバイト単位のオブジェクトの転送長
I the sub-block size in bytes
iバイトのサブブロックサイズ
P for object delivery, the payload size of each packet, in bytes, that is used in the recommended derivation of the object delivery transport parameters.
Pオブジェクト配信用、各パケットのペイロードサイズ、バイト単位で、これはオブジェクト配信輸送パラメーターの推奨される導出に使用されます。
Q Q = 65521, i.e., Q is the largest prime smaller than 2^^16
Z the number of source blocks, for object delivery
zオブジェクト配信用のソースブロックの数
J(K) the systematic index associated with K I_S denotes the SxS identity matrix.
j（k）k i_sに関連付けられた系統的インデックスは、SXSアイデンティティマトリックスを示します。
0_SxH denotes the SxH zero matrix.
0_SXHはSXHゼロマトリックスを示します。
a ^^ b a raised to the power b
a ^^ b a a a power b
For the purposes of the present document, the following abbreviations apply:
現在の文書の目的のために、次の略語が適用されます。
ESI Encoding Symbol ID
ESIエンコードシンボルID
LDPC Low Density Parity Check
LDPC低密度パリティチェック
LT Luby Transform
Lt Luby Transform
SBN Source Block Number
SBNソースブロック番号
SBL Source Block Length (in units of symbols)
SBLソースブロック長（シンボルの単位）
The principal component of the systematic Raptor code is the basic encoder described in Section 5.4. First, it is described how to derive values for a set of intermediate symbols from the original source symbols such that knowledge of the intermediate symbols is sufficient to reconstruct the source symbols. Secondly, the encoder produces repair symbols, which are each the exclusive OR of a number of the intermediate symbols. The encoding symbols are the combination of the source and repair symbols. The repair symbols are produced in such a way that the intermediate symbols, and therefore also the source symbols, can be recovered from any sufficiently large set of encoding symbols.
系統的ラプターコードの主成分は、セクション5.4で説明されている基本エンコーダーです。まず、中間記号の知識がソース記号を再構築するのに十分であるように、元のソース記号から中間記号のセットの値を導出する方法について説明します。第二に、エンコーダは修理シンボルを生成します。修理シンボルは、それぞれ排他的または多くの中間記号のものです。エンコーディングシンボルは、ソースと修理シンボルの組み合わせです。修復記号は、中間記号、したがってソースシンボルも、エンコードシンボルの十分に大きなセットから回復できるように生成されます。
This document specifies the systematic Raptor code encoder. A number of possible decoding algorithms are possible. An efficient decoding algorithm is provided in Section 5.5.
このドキュメントは、系統的なRaptorコードエンコーダーを指定します。多くの可能なデコードアルゴリズムが可能です。セクション5.5に効率的なデコードアルゴリズムが提供されています。
The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section 5.4.4.1. This generator is based on a fixed set of 512 random numbers that MUST be available to both sender and receiver. These are provided in Section 5.6.
中間記号と修復記号の構築は、セクション5.4.4.1で説明されている擬似ランダム数ジェネレーターに一部基づいています。このジェネレーターは、送信者と受信機の両方が利用できる512の乱数の固定セットに基づいています。これらはセクション5.6に記載されています。
Finally, the construction of the intermediate symbols from the source symbols is governed by a 'systematic index', values of which are provided in Section 5.7 for source block sizes from 4 source symbols to Kmax = 8192 source symbols.
最後に、ソースシンボルから中間記号の構築は「系統的インデックス」によって支配され、その値は、4つのソースシンボルからkmax = 8192ソース記号までのソースブロックサイズのセクション5.7に提供されます。
In order to apply the Raptor encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The Raptor encoder is applied independently to each source block. Each source block is identified by a unique integer Source Block Number (SBN), where the first source block has SBN zero, the second has SBN one, etc. Each source block is divided into a number, K, of source symbols of size T bytes each. Each source symbol is identified by a unique integer Encoding Symbol Identifier (ESI), where the first source symbol of a source block has ESI zero, the second has ESI one, etc.
Raptorエンコーダーをソースオブジェクトに適用するために、ソースブロックとして知られるオブジェクトがz> = 1ブロックに分割される場合があります。Raptorエンコーダーは、各ソースブロックに個別に適用されます。各ソースブロックは、最初のソースブロックにはSBNゼロがあり、2番目のソースブロックにはSBN 1などがあります。各ソースブロックは、サイズTのソース記号の数字kに分割されます。それぞれバイト。各ソースシンボルは、ソースブロックの最初のソースシンボルにはESIゼロがあり、2番目にESI ONEなどがあります。
Each source block with K source symbols is divided into N >= 1 sub-blocks, which are small enough to be decoded in the working memory. Each sub-block is divided into K sub-symbols of size T'.
kソースシンボルを持つ各ソースブロックは、n> = 1サブブロックに分割され、作業メモリでデコードされるほど小さくなります。各サブブロックは、サイズt 'のkサブシンボルに分割されます。
Note that the value of K is not necessarily the same for each source block of an object and the value of T' may not necessarily be the same for each sub-block of a source block. However, the symbol size T is the same for all source blocks of an object and the number of symbols, K, is the same for every sub-block of a source block. Exact partitioning of the object into source blocks and sub-blocks is described in Section 5.3.1.2 below.
Kの値は、オブジェクトのソースブロックごとに必ずしも同じではなく、T 'の値はソースブロックの各サブブロックで必ずしも同じではない場合があることに注意してください。ただし、シンボルサイズTはオブジェクトのすべてのソースブロックで同じであり、シンボルの数kの数はソースブロックのサブブロックごとに同じです。ソースブロックとサブブロックへのオブジェクトの正確な分割については、以下のセクション5.3.1.2で説明します。
The construction of source blocks and sub-blocks is determined based on five input parameters, F, Al, T, Z, and N, and a function Partition[]. The five input parameters are defined as follows:
ソースブロックとサブブロックの構築は、5つの入力パラメーター、F、Al、T、Z、およびN、および関数パーティション[]に基づいて決定されます。5つの入力パラメーターは、次のように定義されています。
- F the transfer length of the object, in bytes
- fオブジェクトの転送長、バイト単位
- Al a symbol alignment parameter, in bytes
- バイト単位のシンボルアライメントパラメーター
- T the symbol size, in bytes, which MUST be a multiple of Al
- Tシンボルサイズ、バイトで、それはalの倍数でなければなりません
- Z the number of source blocks
- zソースブロックの数
- N the number of sub-blocks in each source block
- n各ソースブロックのサブブロックの数
These parameters MUST be set so that ceil(ceil(F/T)/Z) <= Kmax. Recommendations for derivation of these parameters are provided in Section 4.2.
これらのパラメーターは、天井（ceil（f/t）/z）<= kmaxになるように設定する必要があります。これらのパラメーターの導出に関する推奨事項は、セクション4.2に記載されています。
The function Partition[] takes a pair of integers (I, J) as input and derives four integers (IL, IS, JL, JS) as output. Specifically, the value of Partition[I, J] is a sequence of four integers (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL. Partition[] derives parameters for partitioning a block of size I into J approximately equal-sized blocks. Specifically, JL blocks of length IL and JS blocks of length IS.
関数パーティション[]は、整数（i、j）のペアを入力として取り、4つの整数（il、jl、js）を出力として導き出します。具体的には、パーティションの値[i、j]は4つの整数（il、jl、js）のシーケンスであり、il = ceil（i/j）は= floor（i/j）、jl = i -IS * J、JS = J -Jl。Partition []は、サイズIのブロックをjに分割するためのパラメーターを導入します。具体的には、長さILおよびJSブロックのJLブロックはです。
The source object MUST be partitioned into source blocks and sub-blocks as follows:
ソースオブジェクトは、次のようにソースブロックとサブブロックに分割する必要があります。
Let
させて
Kt = ceil(F/T)
kt = ceil（f/t）
(KL, KS, ZL, ZS) = Partition[Kt, Z]
（KL、KS、ZL、ZS）=パーティション[KT、Z]
(TL, TS, NL, NS) = Partition[T/Al, N]
（TL、TS、NL、NS）=パーティション[T/AL、N]
Then, the object MUST be partitioned into Z = ZL + ZS contiguous source blocks, the first ZL source blocks each having length KL*T bytes, and the remaining ZS source blocks each having KS*T bytes.
次に、オブジェクトをz = zl zs連続ソースブロックに分割し、最初のzlソースはそれぞれ長さkl*tバイトを持ち、残りのzsソースはそれぞれks*tバイトを持つブロックをブロックする必要があります。
If Kt*T > F, then for encoding purposes, the last symbol MUST be padded at the end with Kt*T - F zero bytes.
kt*t> fの場合、エンコーディングのために、最後のシンボルはkt*t -fゼロバイトで最後にパッドで埋めなければなりません。
Next, each source block MUST be divided into N = NL + NS contiguous sub-blocks, the first NL sub-blocks each consisting of K contiguous sub-symbols of size of TL*Al and the remaining NS sub-blocks each consisting of K contiguous sub-symbols of size of TS*Al. The symbol alignment parameter Al ensures that sub-symbols are always a multiple of Al bytes.
次に、各ソースブロックはn = nl ns連続サブブロックに分割する必要があります。それぞれがtl*alのサイズのk連続サブシンボルで構成される最初のNLサブブロックと、それぞれk連続したnsサブブロックts*alのサイズのサブシンボル。シンボルアライメントパラメーターALは、サブシンボルが常にALバイトの倍数であることを保証します。
Finally, the m-th symbol of a source block consists of the concatenation of the m-th sub-symbol from each of the N sub-blocks. Note that this implies that when N > 1, then a symbol is NOT a contiguous portion of the object.
最後に、ソースブロックのmthシンボルは、各nサブブロックからのmthサブシンボルの連結で構成されています。これは、n> 1の場合、シンボルがオブジェクトの隣接する部分ではないことを意味することに注意してください。
Each encoding packet contains the following information:
各エンコーディングパケットには、次の情報が含まれています。
- Source Block Number (SBN)
- ソースブロック番号（SBN）
- Encoding Symbol ID (ESI)
- シンボルIDのエンコード（ESI）
- encoding symbol(s)
- シンボルをエンコードする
Each source block is encoded independently of the others. Source blocks are numbered consecutively from zero.
各ソースブロックは、他とは独立してエンコードされています。ソースブロックは、ゼロから連続して番号が付けられています。
Encoding Symbol ID values from 0 to K-1 identify the source symbols of a source block in sequential order, where K is the number of symbols in the source block. Encoding Symbol IDs from K onwards identify repair symbols.
0からk-1のシンボルID値をエンコードすると、ソースブロックのソース記号が順次順序で識別されます。ここで、kはソースブロックのシンボルの数です。K以降のシンボルIDをエンコードすることは、修理シンボルを識別します。
Each encoding packet either consists entirely of source symbols (source packet) or entirely of repair symbols (repair packet). A packet may contain any number of symbols from the same source block. In the case that the last source symbol in a source packet includes padding bytes added for FEC encoding purposes, then these bytes need not be included in the packet. Otherwise, only whole symbols MUST be included.
各エンコードパケットは、完全にソース記号（ソースパケット）または完全に修理シンボル（修理パケット）のいずれかのいずれかです。パケットには、同じソースブロックから任意の数の記号が含まれている場合があります。ソースパケットの最後のソースシンボルには、FECエンコーディング目的で追加されたパディングバイトが含まれている場合、これらのバイトをパケットに含める必要はありません。それ以外の場合、シンボル全体のみを含める必要があります。
The Encoding Symbol ID, X, carried in each source packet is the Encoding Symbol ID of the first source symbol carried in that packet. The subsequent source symbols in the packet have Encoding Symbol IDs, X+1 to X+G-1, in sequential order, where G is the number of symbols in the packet.
各ソースパケットに掲載されたエンコードシンボルID x xは、そのパケットに掲載された最初のソースシンボルのエンコードシンボルIDです。パケット内の後続のソースシンボルには、シンボルID x 1からx g-1をエンコードする順序で、gはパケット内のシンボルの数です。
Similarly, the Encoding Symbol ID, X, placed into a repair packet is the Encoding Symbol ID of the first repair symbol in the repair packet and the subsequent repair symbols in the packet have Encoding Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of symbols in the packet.
同様に、修理パケットに配置されたエンコーディングシンボルID x xは、修理パケットの最初の修理記号のエンコードシンボルIDであり、パケットの後続の修理シンボルには、シンボルIDS x 1からx g-1が順次順序でエンコードされています。、ここで、gはパケット内のシンボルの数です。
Note that it is not necessary for the receiver to know the total number of repair packets.
受信者が修理パケットの総数を知る必要はないことに注意してください。
Associated with each symbol is a triple of integers (d, a, b).
各シンボルに関連付けられているのは、整数のトリプルです（D、A、B）。
The G repair symbol triples (d[0], a[0], b[0]),..., (d[G-1], a[G-1], b[G-1]) for the repair symbols placed into a repair packet with ESI X are computed using the Triple generator defined in Section 5.4.4.4 as follows:
g修復記号はトリプル（d [0]、a [0]、b [0]）、...、（d [g-1]、a [g-1]、b [g-1]）ESI Xを使用して修理パケットに配置された修理記号は、次のようにセクション5.4.4.4で定義されたトリプルジェネレーターを使用して計算されます。
For each i = 0, ..., G-1, (d[i], a[i], b[i]) = Trip[K,X+i]
The G repair symbols to be placed in repair packet with ESI X are calculated based on the repair symbol triples, as described in Section 5.4, using the intermediate symbols C and the LT encoder LTEnc[K, C, (d[i], a[i], b[i])].
ESI Xを使用して修理パケットに配置されるG修復記号は、中間記号CおよびLTエンコーダーLTENC [K、C、（D [I]、A Aを使用して、セクション5.4で説明されている修理シンボルトリプルに基づいて計算されます。[i]、b [i]）]。
The systematic Raptor encoder is used to generate repair symbols from a source block that consists of K source symbols.
系統的なRaptorエンコーダーは、Kソースシンボルで構成されるソースブロックから修理シンボルを生成するために使用されます。
Symbols are the fundamental data units of the encoding and decoding process. For each source block (sub-block), all symbols (sub-symbols) are the same size. The atomic operation performed on symbols (sub-symbols) for both encoding and decoding is the exclusive-or operation.
シンボルは、エンコードおよびデコードプロセスの基本的なデータ単位です。各ソースブロック（サブブロック）について、すべてのシンボル（サブシンボル）は同じサイズです。エンコードとデコードの両方に対してシンボル（サブシンボル）で実行される原子動作は、排他的または操作です。
Let C'[0],..., C'[K-1] denote the K source symbols.
c '[0]、...、c' [k-1]がkソースシンボルを示すとします。
Let C[0],..., C[L-1] denote L intermediate symbols.
C [0]、...、C [L-1]がL中間記号を示すとします。
The first step of encoding is to generate a number, L > K, of intermediate symbols from the K source symbols. In this step, K source symbol triples (d[0], a[0], b[0]), ..., (d[K-1], a[K-1], b[K-1]) are generated using the Trip[] generator as described in Section 5.4.2.2. The K source symbol triples are associated with the K source symbols and are then used to determine the L intermediate symbols C[0],..., C[L-1] from the source symbols using an inverse encoding process. This process can be realized by a Raptor decoding process.
エンコードの最初のステップは、Kソース記号から中間記号の数字l> kを生成することです。このステップでは、kソースシンボルトリプル（d [0]、a [0]、b [0]）、...、（d [k-1]、a [k-1]、b [k-1]）セクション5.4.2.2で説明されているように、トリップ[]ジェネレーターを使用して生成されます。KソースシンボルトリプルはKソースシンボルに関連付けられ、逆エンコードプロセスを使用してソース記号からL中間記号C [0]、...、C [L-1]を決定するために使用されます。このプロセスは、ラプターデコードプロセスによって実現できます。
Certain "pre-coding relationships" MUST hold within the L intermediate symbols. Section 5.4.2.3 describes these relationships and how the intermediate symbols are generated from the source symbols.
特定の「事前コード関係」は、L中間記号内に保持する必要があります。セクション5.4.2.3では、これらの関係と、ソース記号から中間記号がどのように生成されるかについて説明します。
Once the intermediate symbols have been generated, repair symbols are produced and one or more repair symbols are placed as a group into a single data packet. Each repair symbol group is associated with an Encoding Symbol ID (ESI) and a number, G, of repair symbols. The ESI is used to generate a triple of three integers, (d, a, b) for each repair symbol, again using the Trip[] generator as described in Section 5.4.4.4. Then, each (d,a,b)-triple is used to generate the corresponding repair symbol from the intermediate symbols using the LTEnc[K, C[0],..., C[L-1], (d,a,b)] generator described in Section 5.4.4.3.
中間記号が生成されると、修復記号が生成され、1つ以上の修復記号がグループとして単一のデータパケットに配置されます。各修理シンボルグループは、エンコードシンボルID（ESI）と修復記号の数字gに関連付けられています。ESIは、各修復記号に対して3つの整数（D、A、B）のトリプルを生成するために使用され、再びセクション5.4.4.4で説明されているトリップ[]ジェネレーターを使用します。次に、各（d、a、b）-tripleは、ltenc [k、c [0]、...、c [l-1]、（d、aを使用して中間記号から対応する修復記号を生成するために使用されます。、b）]セクション5.4.4.3で説明されているジェネレーター。
The first encoding step is a pre-coding step to generate the L intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], ..., C'[K-1]. The intermediate symbols are uniquely defined by two sets of constraints:
最初のエンコーディングステップは、ソース記号C '[0]、...、C' [k-k-からL中間記号C [0]、...、C [L-1]を生成するための事前コードステップです。1]。中間記号は、2つの制約セットによって一意に定義されています。
1. The intermediate symbols are related to the source symbols by a set of source symbol triples. The generation of the source symbol triples is defined in Section 5.4.2.2 using the Trip[] generator described in Section 5.4.4.4.
1. 中間記号は、ソースシンボルトリプルのセットによってソースシンボルに関連しています。ソースシンボルトリプルの生成は、セクション5.4.4.4で説明されているトリップ[]ジェネレーターを使用して、セクション5.4.2.2で定義されています。
2. A set of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section 5.4.2.3.
2. 一連の事前コード関係は、中間記号自体に保持されます。これらはセクション5.4.2.3で定義されています。
The generation of the L intermediate symbols is then defined in Section 5.4.2.4
L中間記号の生成は、セクション5.4.2.4で定義されます
Each of the K source symbols is associated with a triple (d[i], a[i], b[i]) for 0 <= i < K. The source symbol triples are determined using the Triple generator defined in Section 5.4.4.4 as:
各kソースシンボルは、0 <= i <Kのトリプル（d [i]、a [i]、b [i]）に関連付けられています。ソースシンボルトリプルは、セクション5.4で定義されたトリプルジェネレーターを使用して決定されます。4.4 AS：
For each i, 0 <= i < K
(d[i], a[i], b[i]) = Trip[K, i]
（d [i]、a [i]、b [i]）= trip [k、i]
The pre-coding relationships amongst the L intermediate symbols are defined by expressing the last L-K intermediate symbols in terms of the first K intermediate symbols.
L中間記号間の事前コード関係は、最初のK中間記号に関して最後のL-K中間記号を表現することによって定義されます。
The last L-K intermediate symbols C[K],...,C[L-1] consist of S LDPC symbols and H Half symbols The values of S and H are determined from K as described below. Then L = K+S+H.
最後のL-K中間記号c [k]、...、c [l-1]はs ldpcシンボルで構成され、hの半分記号は、sとhの値を以下に説明するようにkから決定します。次に、l = k sH。
Let
させて
X be the smallest positive integer such that X*(X-1) >= 2*K.
x x*（x-1）> = 2*kになるような最小の正の整数になります。
S be the smallest prime integer such that S >= ceil(0.01*K) + X
H be the smallest integer such that choose(H,ceil(H/2)) >= K + S
H' = ceil(H/2)
h '= ceil（h/2）
L = K+S+H
C[0],...,C[K-1] denote the first K intermediate symbols
c [0]、...、c [k-1]は最初のk中間記号を示します
C[K],...,C[K+S-1] denote the S LDPC symbols, initialised to zero
c [k]、...、c [k s-1]は、ゼロに初期化されたs ldpcシンボルを示します
C[K+S],...,C[L-1] denote the H Half symbols, initialised to zero
c [k s]、...、c [l-1]は、ゼロに初期化されたHの半分記号を示します
The S LDPC symbols are defined to be the values of C[K],...,C[K+S-1] at the end of the following process:
S LDPC記号は、次のプロセスの最後にあるC [k]、...、C [k s-1]の値であると定義されています。
For i = 0,...,K-1 do
i = 0、...、k-1の場合
a = 1 + (floor(i/S) % (S-1))
b = i % S
b = i％s
C[K + b] = C[K + b] ^ C[i]
b = (b + a) % S
C[K + b] = C[K + b] ^ C[i]
b = (b + a) % S
C[K + b] = C[K + b] ^ C[i]
The H Half symbols are defined as follows:
Hの半分のシンボルは、次のように定義されています。
Let
させて
g[i] = i ^ (floor(i/2)) for all positive integers i
Note: g[i] is the Gray sequence, in which each element differs from the previous one in a single bit position
注：g [i]は灰色のシーケンスであり、各要素は前の要素と1つのビット位置で異なります
m[k] denote the subsequence of g[.] whose elements have exactly k non-zero bits in their binary representation.
m [k]は、バイナリ表現に要素が正確にK非ゼロビットを持っているg [。]のサブシーケンスを示します。
m[j,k] denote the jth element of the sequence m[k], where j=0, 1, 2, ...
m [j、k]は、シーケンスm [k]のjth要素を示します。ここで、j = 0、1、2、...
Then, the Half symbols are defined as the values of C[K+S],...,C[L-1] after the following process:
次に、半分のシンボルは、次のプロセスの後にc [k s]、...、c [l-1]の値として定義されます。
For h = 0,...,H-1 do
h = 0、...、h-1の場合
For j = 0,...,K+S-1 do
j = 0、...、k s-1の場合
If bit h of m[j,H'] is equal to 1 then C[h+K+S] = C[h+K+S] ^ C[j].
m [j、h ']のビットが1に等しい場合、c [h k s] = c [h k s] ^ c [j]。
Given the K source symbols C'[0], C'[1],..., C'[K-1] the L intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined symbol values that satisfy the following conditions:
kソース記号C '[0]、c' [1]、...、c '[k-1]が与えられると、L中間記号C [0]、C [1]、...、C [L-1]は、次の条件を満たす独自に定義されたシンボル値です。
1. The K source symbols C'[0], C'[1],..., C'[K-1] satisfy the K constraints
1. kソースシンボルc '[0]、c' [1]、...、c '[k-1]はk制約を満たします
C'[i] = LTEnc[K, (C[0],..., C[L-1]), (d[i], a[i], b[i])], for all i, 0 <= i < K.
c '[i] = ltenc [k、（c [0]、...、c [l-1]）、（d [i]、a [i]、b [i]）]、すべてのi、0 <= i <k。
2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the pre-coding relationships defined in Section 5.4.2.3.
2. L中間記号C [0]、C [1]、...、C [L-1]は、セクション5.4.2.3で定義されている事前コード関係を満たします。
This subsection describes a possible method for calculation of the L intermediate symbols C[0], C[1],..., C[L-1] satisfying the constraints in Section 5.4.2.4.1.
このサブセクションは、セクション5.4.2.4.1の制約を満たすL中間記号C [0]、C [1]、...、C [L-1]を計算する可能性のある方法を説明しています。
The 'generator matrix' for a code that generates N output symbols from K input symbols is an NxK matrix over GF(2), where each row corresponds to one of the output symbols and each column to one of the input symbols and where the ith output symbol is equal to the sum of those input symbols whose column contains a non-zero entry in row i.
k入力記号からn出力記号を生成するコードの「ジェネレーターマトリックス」は、GF（2）上のNXKマトリックスであり、各行は出力シンボルの1つに、各列は入力記号のいずれかに対応します。出力シンボルは、行iにゼロ以外のエントリが含まれる入力記号の合計に等しくなります。
Then, the L intermediate symbols can be calculated as follows:
次に、L中間記号を次のように計算できます。
Let
させて
C denote the column vector of the L intermediate symbols, C[0], C[1],..., C[L-1].
Cは、L中間記号の列ベクトル、C [0]、C [1]、...、C [L-1]を示します。
D denote the column vector consisting of S+H zero symbols followed by the K source symbols C'[0], C'[1], ..., C'[K-1]
d s Hゼロ記号で構成される列ベクトルを示し、その後にkソースシンボルC '[0]、c' [1]、...、c '[k-1]が続きます
Then the above constraints define an LxL matrix over GF(2), A, such that:
次に、上記の制約は、GF（2）、AのLXLマトリックスを定義します。
A*C = D
a*c = d
The matrix A can be constructed as follows:
マトリックスAは次のように構築できます。
Let:
させて：
G_LDPC be the S x K generator matrix of the LDPC symbols. So,
g_ldpc LDPCシンボルのS x Kジェネレーターマトリックス。それで、
G_LDPC * Transpose[(C[0],...., C[K-1])] = Transpose[(C[K], ...,
C[K+S-1])]
G_Half be the H x (K+S) generator matrix of the Half symbols, So,
g_halfは、半分のシンボルのh x（k s）ジェネレーターマトリックスです。
G_Half * Transpose[(C[0], ..., C[S+K-1])] = Transpose[(C[K+S],
..., C[K+S+H-1])]
I_S be the S x S identity matrix
i_sはs x s Identityマトリックスです
I_H be the H x H identity matrix
I_HはH X H IDのマトリックスになります
0_SxH be the S x H zero matrix
0_SXHはs x hゼロマトリックスです
G_LT be the KxL generator matrix of the encoding symbols generated by the LT Encoder. So,
G_LT LTエンコーダによって生成されたエンコードシンボルのKXLジェネレーターマトリックス。それで、
G_LT * Transpose[(C[0], ..., C[L-1])] =
Transpose[(C'[0],C'[1],...,C'[K-1])]
i.e., G_LT(i,j) = 1 if and only if C[j] is included in the symbols that are XORed to produce LTEnc[K, (C[0], ..., C[L-1]), (d[i], a[i], b[i])].
すなわち、g_lt（i、j）= 1の場合のみ、c [j]がltenc [k、（c [0]、...、c [l-1]）を生成するためにxされたシンボルに含まれている場合にのみ、（d [i]、a [i]、b [i]）]。
Then:
それから：
The first S rows of A are equal to G_LDPC | I_S | 0_SxH.
aの最初のs行はg_ldpcに等しい|i_s |0_SXH。
The next H rows of A are equal to G_Half | I_H.
Aの次のh行はg_halfに等しい|I_H。
The remaining K rows of A are equal to G_LT.
Aの残りのk行はg_ltに等しくなります。
The matrix A is depicted in Figure 4 below:
マトリックスAを以下の図4に示します。
K S H
+-----------------------+-------+-------+
| | | |
S | G_LDPC | I_S | 0_SxH |
| | | |
+-----------------------+-------+-------+
| | |
H | G_Half | I_H |
| | |
+-------------------------------+-------+
| |
| |
K | G_LT |
| |
| |
+---------------------------------------+
Figure 4: The matrix A
図4：マトリックスa
The intermediate symbols can then be calculated as:
その後、中間記号は次のように計算できます。
C = (A^^-1)*D
The source symbol triples are generated such that for any K matrix, A has full rank and is therefore invertible. This calculation can be realized by applying a Raptor decoding process to the K source symbols C'[0], C'[1],..., C'[K-1] to produce the L intermediate symbols C[0], C[1],..., C[L-1].
ソースシンボルトリプルは、任意のKマトリックスの場合、Aが完全なランクを持ち、したがって反転可能になるように生成されます。この計算は、ラプターデコードプロセスをKソース記号C '[0]、C' [1]、...、C '[k-1]に適用して、L中間記号C [0]を生成することで実現できます。c [1]、...、c [l-1]。
To efficiently generate the intermediate symbols from the source symbols, it is recommended that an efficient decoder implementation such as that described in Section 5.5 be used. The source symbol triples are designed to facilitate efficient decoding of the source symbols using that algorithm.
ソースシンボルから中間記号を効率的に生成するには、セクション5.5で説明したような効率的なデコーダー実装を使用することをお勧めします。ソースシンボルトリプルは、そのアルゴリズムを使用してソース記号の効率的なデコードを容易にするように設計されています。
In the second encoding step, the repair symbol with ESI X is generated by applying the generator LTEnc[K, (C[0], C[1],..., C[L-1]), (d, a, b)] defined in Section 5.4.4.3 to the L intermediate symbols C[0], C[1],..., C[L-1] using the triple (d, a, b)=Trip[K,X] generated according to Section 5.3.2
2番目のエンコーディングステップでは、ESI Xを使用した修復記号は、発電機LTENC [k、（c [0]、c [1]、...、c [l-1]）、（d、a、）を適用することにより生成されます。b）]トリプル（d、a、b）= trip [k、xを使用して、セクション5.4.4.3でL中間記号C [0]、C [1]、...、C [L-1]に定義されています。]セクション5.3.2に従って生成されます
The random number generator Rand[X, i, m] is defined as follows, where X is a non-negative integer, i is a non-negative integer, and m is a positive integer and the value produced is an integer between 0 and m-1. Let V0 and V1 be arrays of 256 entries each, where each entry is a 4-byte unsigned integer. These arrays are provided in Section 5.6.
乱数ジェネレーターrand [x、i、m]は次のように定義されます。ここで、xは非陰性整数であり、iは非陰性整数であり、mは正の整数であり、生成される値は0から0の間の整数です。M-1。V0とV1をそれぞれ256エントリの配列とし、各エントリは4バイトの符号なし整数です。これらの配列は、セクション5.6に記載されています。
Then,
それから、
Rand[X, i, m] = (V0[(X + i) % 256] ^ V1[(floor(X/256)+ i) % 256])
% m
The degree generator Deg[v] is defined as follows, where v is an integer that is at least 0 and less than 2^^20 = 1048576.
学位ジェネレーターのdeg [v]は次のように定義されます。ここで、vは少なくとも0で2 ^^ 20 = 1048576未満の整数です。
In Table 1, find the index j such that f[j-1] <= v < f[j]
Then, Deg[v] = d[j]
次に、deg [v] = d [j]
+---------+---------+------+
| Index j | f[j] | d[j] |
+---------+---------+------+
| 0 | 0 | -- |
| 1 | 10241 | 1 |
| 2 | 491582 | 2 |
| 3 | 712794 | 3 |
| 4 | 831695 | 4 |
| 5 | 948446 | 10 |
| 6 | 1032189 | 11 |
| 7 | 1048576 | 40 |
+---------+---------+------+
Table 1: Defines the degree distribution for encoding symbols
表1：エンコーディングシンボルの程度分布を定義します
The encoding symbol generator LTEnc[K, (C[0], C[1],..., C[L-1]), (d, a, b)] takes the following inputs:
エンコードシンボルジェネレーターLtenc [k、（c [0]、c [1]、...、c [l-1]）、（d、a、b）]は次の入力を取得します。
K is the number of source symbols (or sub-symbols) for the source block (sub-block). Let L be derived from K as described in Section 5.4.2.3, and let L' be the smallest prime integer greater than or equal to L.
Kは、ソースブロックのソース記号（またはサブシンボル）の数（サブブロック）です。セクション5.4.2.3で説明されているように、lをkから導出し、L 'をLよりも大きい最小プライム整数とします。
(C[0], C[1],..., C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section 5.4.2.4.
（C [0]、C [1]、...、C [L-1]）は、セクション5.4.2.4で説明されているように生成されたL中間記号（サブシンボル）の配列です。
(d, a, b) is a source triple determined using the Triple generator defined in Section 5.4.4.4, whereby
（d、a、b）は、セクション5.4.4.4で定義されたトリプルジェネレーターを使用して決定されたソーストリプルで決定されます。
d is an integer denoting an encoding symbol degree
Dは、エンコードシンボルの程度を示す整数です
a is an integer between 1 and L'-1 inclusive
Aは、1とL'-1の包括的整数です
b is an integer between 0 and L'-1 inclusive
Bは、0からL'-1の包括的な整数です
The encoding symbol generator produces a single encoding symbol as output, according to the following algorithm:
エンコードシンボルジェネレーターは、次のアルゴリズムに従って、出力として単一のエンコードシンボルを生成します。
While (b >= L) do b = (b + a) % L'
Let result = C[b].
結果= C [b]とします。
For j = 1,...,min(d-1,L-1) do
j = 1、...、min（d-1、l-1）の場合
b = (b + a) % L'
While (b >= L) do b = (b + a) % L'
result = result ^ C[b]
結果= result ^ c [b]
Return result
返品結果
The triple generator Trip[K,X] takes the following inputs:
トリプルジェネレータートリップ[k、x]は、次の入力を取得します。
K - The number of source symbols
K-ソース記号の数
X - An encoding symbol ID
X-エンコーディングシンボルID
Let
させて
L be determined from K as described in Section 5.4.2.3
lセクション5.4.2.3で説明されているようにKから決定される
L' be the smallest prime that is greater than or equal to L Q = 65521, the largest prime smaller than 2^^16.
L 'は、L Q = 65521以上の最小プライムであり、2 ^^ 16よりも最大の最小プライムです。
J(K) be the systematic index associated with K, as defined in Section 5.7.
j（k）セクション5.7で定義されているように、Kに関連付けられた系統的インデックスになります。
The output of the triple generator is a triple, (d, a, b) determined as follows:
トリプルジェネレーターの出力はトリプル（d、a、b）が次のように決定されます。
A = (53591 + J(K)*997) % Q
B = 10267*(J(K)+1) % Q
Y = (B + X*A) % Q
v = Rand[Y, 0, 2^^20]
d = Deg[v]
d = deg [v]
a = 1 + Rand[Y, 1, L'-1]
a = 1 rand [y、1、l'-1]
b = Rand[Y, 2, L']
b = rand [y、2、l ']
This section describes an efficient decoding algorithm for the Raptor codes described in this specification. Note that each received encoding symbol can be considered as the value of an equation amongst the intermediate symbols. From these simultaneous equations, and the known pre-coding relationships amongst the intermediate symbols, any algorithm for solving simultaneous equations can successfully decode the intermediate symbols and hence the source symbols. However, the algorithm chosen has a major effect on the computational efficiency of the decoding.
このセクションでは、この仕様で説明されているRaptorコードの効率的なデコードアルゴリズムについて説明します。受信した各エンコードシンボルは、中間記号間の方程式の値と見なすことができることに注意してください。これらの同時方程式、および中間記号間の既知の事前コード関係から、同時方程式を解くためのアルゴリズムは、中間記号、したがってソース記号をうまくデコードできます。ただし、選択したアルゴリズムは、デコードの計算効率に大きな影響を及ぼします。
It is assumed that the decoder knows the structure of the source block it is to decode, including the symbol size, T, and the number K of symbols in the source block.
デコーダーは、シンボルサイズ、t、およびソースブロックのシンボルの数を含む、デコードするソースブロックの構造を知っていると想定されています。
From the algorithms described in Section 5.4, the Raptor decoder can calculate the total number L = K+S+H of pre-coding symbols and determine how they were generated from the source block to be decoded. In this description, it is assumed that the received encoding symbols for the source block to be decoded are passed to the decoder. Note that, as described in Section 5.3.2, the last source symbol of a source packet may have included padding bytes added for FEC encoding purposes. These padding bytes may not be actually included in the packet sent and so must be reinserted at the received before passing the symbol to the decoder.
セクション5.4で説明されているアルゴリズムから、Raptorデコーダーは、事前コードシンボルの総数l = k s hを計算し、ソースブロックから生成された方法を決定する方法を決定できます。この説明では、デコードされるソースブロックの受信したエンコード記号がデコーダーに渡されると想定されています。セクション5.3.2で説明したように、ソースパケットの最後のソース記号には、FECエンコーディングの目的で追加されたパディングバイトが含まれている可能性があることに注意してください。これらのパディングバイトは、実際に送信されたパケットに含まれていない可能性があるため、シンボルをデコーダーに渡す前に受信してから再挿入する必要があります。
For each such encoding symbol, it is assumed that the number and set of intermediate symbols whose exclusive-or is equal to the encoding symbol is also passed to the decoder. In the case of source symbols, the source symbol triples described in Section 5.4.2.2 indicate the number and set of intermediate symbols that sum to give each source symbol.
そのようなエンコードシンボルごとに、排他的またはエンコードシンボルに等しい中間記号の数とセットもデコーダーに渡されると想定されています。ソースシンボルの場合、セクション5.4.2.2で説明されているソースシンボルトリプルは、各ソースシンボルを与えるために合計する中間記号の数とセットを示します。
Let N >= K be the number of received encoding symbols for a source block and let M = S+H+N. The following M by L bit matrix A can be derived from the information passed to the decoder for the source block to be decoded. Let C be the column vector of the L intermediate symbols, and let D be the column vector of M symbols with values known to the receiver, where the first S+H of the M symbols are zero-valued symbols that correspond to LDPC and Half symbols (these are check symbols for the LDPC and Half symbols, and not the LDPC and Half symbols themselves), and the remaining N of the M symbols are the received encoding symbols for the source block. Then, A is the bit matrix that satisfies A*C = D, where here * denotes matrix multiplication over GF[2]. In particular, A[i,j] = 1 if the intermediate symbol corresponding to index j is exclusive-ORed into the LDPC, Half, or encoding symbol corresponding to index i in the encoding, or if index i corresponds to a LDPC or Half symbol and index j corresponds to the same LDPC or Half symbol. For all other i and j, A[i,j] = 0.
n> = kをソースブロックの受信したエンコードシンボルの数とし、M = S H Nとします。次のM x lビットマトリックスAは、ソースブロックがデコードされるためにデコーダーに渡された情報から導出できます。cをL中間記号の列ベクトルとし、dを受信機に既知の値を持つmシンボルの列ベクトルとし、mシンボルの最初のs hはLDPCと半分のシンボルに対応するゼロ値シンボルです（これらは、LDPCのチェックシンボルと半分のシンボルであり、LDPCと半分のシンボル自体ではありません）であり、Mシンボルの残りのNは、ソースブロックの受信エンコードシンボルです。次に、AはA * c = Dを満たすビットマトリックスであり、ここで *はGF [2]のマトリックスの乗算を示します。特に、a [i、j] = 1インデックスjに対応する中間記号が、エンコーディングのインデックスIに対応するLDPC、半分、またはエンコード記号に排他的に使用されている場合、またはインデックスIがLDPCまたは半分に対応する場合シンボルとインデックスjは、同じLDPCまたは半分のシンボルに対応します。他のすべてのiとjについて、a [i、j] = 0。
Decoding a source block is equivalent to decoding C from known A and D. It is clear that C can be decoded if and only if the rank of A over GF[2] is L. Once C has been decoded, missing source symbols can be obtained by using the source symbol triples to determine the number and set of intermediate symbols that MUST be exclusive-ORed to obtain each missing source symbol.
ソースブロックのデコードは、既知のAおよびDのCを解読することに相当します。GF[2]のランクがLである場合にのみ、Cをデコードできることは明らかです。ソースシンボルトリプルを使用して取得して、各欠落しているソースシンボルを取得するために排他的である必要がある中間記号の数とセットを決定します。
The first step in decoding C is to form a decoding schedule. In this step A is converted, using Gaussian elimination (using row operations and row and column reorderings) and after discarding M - L rows, into the L by L identity matrix. The decoding schedule consists of the sequence of row operations and row and column reorderings during the Gaussian elimination process, and only depends on A and not on D. The decoding of C from D can take place concurrently with the forming of the decoding schedule, or the decoding can take place afterwards based on the decoding schedule.
Cをデコードする最初のステップは、デコードスケジュールを形成することです。このステップでは、ガウス除去（行操作と行と列の並べ替えを使用して）を使用して、M -l列を捨てた後、LバイLアイデンティティマトリックスに変換されます。デコードスケジュールは、ガウス除去プロセス中の行操作と行と列の並べ替えのシーケンスで構成され、Dからのみ依存します。Dからのcのデコードは、デコードスケジュールの形成と同時に行うことができます。デコードは、デコードスケジュールに基づいてその後行うことができます。
The correspondence between the decoding schedule and the decoding of C is as follows. Let c[0] = 0, c[1] = 1,...,c[L-1] = L-1 and d[0] = 0, d[1] = 1,...,d[M-1] = M-1 initially.
デコードスケジュールとCのデコードの対応は次のとおりです。c [0] = 0、c [1] = 1、...、c [l-1] = l-1およびd [0] = 0、d [1] = 1、...、d [M-1] = M-1最初は。
- Each time row i of A is exclusive-ORed into row i' in the decoding schedule, then in the decoding process, symbol D[d[i]] is exclusive-ORed into symbol D[d[i']].
- a of a of a of aの毎回iは、デコードスケジュールで行I 'に排他的に装飾されており、デコードプロセスでは、シンボルd [d [i]]はシンボルd [d [i']]に排他的に使用されます。
- Each time row i is exchanged with row i' in the decoding schedule, then in the decoding process, the value of d[i] is exchanged with the value of d[i'].
- 毎回行私は、デコードスケジュールで行I 'と交換され、デコードプロセスでは、d [i]の値はd [i']の値と交換されます。
- Each time column j is exchanged with column j' in the decoding schedule, then in the decoding process, the value of c[j] is exchanged with the value of c[j'].
- 列jは、デコードスケジュールで列j 'と交換され、デコードプロセスでは、c [j]の値はc [j']の値と交換されます。
From this correspondence, it is clear that the total number of exclusive-ORs of symbols in the decoding of the source block is the number of row operations (not exchanges) in the Gaussian elimination. Since A is the L by L identity matrix after the Gaussian elimination and after discarding the last M - L rows, it is clear at the end of successful decoding that the L symbols D[d[0]], D[d[1]],..., D[d[L-1]] are the values of the L symbols C[c[0]], C[c[1]],..., C[c[L-1]].
この対応から、ソースブロックのデコードにおけるシンボルの排他的な数の総数が、ガウス排除の行操作（交換ではない）の数であることは明らかです。aはガウスの除去後と最後のm -l行を破棄した後のL by l Identityマトリックスであるため、L syribons d [d [0]]、d [d [1]のデコードが成功したことは明らかです。]、...、d [d [l-1]]は、l記号の値c [c [0]]、c [c [1]]、...、c [c [l-1]の値です]。
The order in which Gaussian elimination is performed to form the decoding schedule has no bearing on whether or not the decoding is successful. However, the speed of the decoding depends heavily on the order in which Gaussian elimination is performed. (Furthermore, maintaining a sparse representation of A is crucial, although this is not described here). The remainder of this section describes an order in which Gaussian elimination could be performed that is relatively efficient.
デコードスケジュールを形成するためにガウスの除去が実行される順序は、デコードが成功するかどうかに関係していません。ただし、デコードの速度は、ガウスの除去が実行される順序に大きく依存します。（さらに、Aのまばらな表現を維持することが重要ですが、これはここでは説明されていません）。このセクションの残りの部分では、比較的効率的なガウス除去を実行できる順序について説明しています。
The first phase of the Gaussian elimination, the matrix A, is conceptually partitioned into submatrices. The submatrix sizes are parameterized by non-negative integers i and u, which are initialized to 0. The submatrices of A are:
ガウス除去の第1フェーズであるマトリックスAは、概念的にサブマトリックに分割されます。サブマトリックスサイズは、非陰性整数IおよびUによってパラメーター化され、0に初期化されます。
(1) The submatrix I defined by the intersection of the first i rows and first i columns. This is the identity matrix at the end of each step in the phase.
(1) 最初のI行と最初のI列の交差によって定義されたサブマトリックスI。これは、フェーズの各ステップの最後にあるアイデンティティマトリックスです。
(2) The submatrix defined by the intersection of the first i rows and all but the first i columns and last u columns. All entries of this submatrix are zero.
(2) サブマトリックスは、最初のI行と最初のI列と最後のu列を除くすべての交差によって定義されます。このサブマトリックスのすべてのエントリはゼロです。
(3) The submatrix defined by the intersection of the first i columns and all but the first i rows. All entries of this submatrix are zero.
(3) サブマトリックスは、最初のI列と最初のI行を除くすべての交差によって定義されます。このサブマトリックスのすべてのエントリはゼロです。
(4) The submatrix U defined by the intersection of all the rows and the last u columns.
(4) すべての行と最後のu列の交差によって定義されるサブマトリックスu。
(5) The submatrix V formed by the intersection of all but the first i columns and the last u columns and all but the first i rows.
(5) サブマトリックスVは、最初のI列を除くすべての交差点によって形成され、最後のU列、および最初のI行を除くすべての列によって形成されます。
Figure 5 illustrates the submatrices of A. At the beginning of the first phase, V = A. In each step, a row of A is chosen.
図5は、Aの下部を示しています。最初のフェーズの先頭にあるv = Aを示しています。各ステップでは、Aの行が選択されます。
+-----------+-----------------+---------+
| | | |
| I | All Zeros | |
| | | |
+-----------+-----------------+ U |
| | | |
| | | |
| All Zeros | V | |
| | | |
| | | |
+-----------+-----------------+---------+
Figure 5: Submatrices of A in the first phase
図5：第一段階のaの副士号
The following graph defined by the structure of V is used in determining which row of A is chosen. The columns that intersect V are the nodes in the graph, and the rows that have exactly 2 ones in V are the edges of the graph that connect the two columns (nodes) in the positions of the two ones. A component in this graph is a maximal set of nodes (columns) and edges (rows) such that there is a path between each pair of nodes/edges in the graph. The size of a component is the number of nodes (columns) in the component.
Vの構造によって定義された次のグラフは、選択されたAの行を決定する際に使用されます。vと交差する列はグラフのノードであり、vに正確に2つの列がある行は、2つの列（ノード）を2つの列（ノード）に接続するグラフのエッジです。このグラフのコンポーネントは、グラフ内の各ノード/エッジの間にパスがあるように、ノード（列）とエッジ（行）の最大セットです。コンポーネントのサイズは、コンポーネントのノード（列）の数です。
There are at most L steps in the first phase. The phase ends successfully when i + u = L, i.e., when V and the all-zeroes submatrix above V have disappeared and A consists of I, the all zeroes submatrix below I, and U. The phase ends unsuccessfully in decoding failure if, at some step before V disappears, there is no non-zero row in V to choose in that step. Whenever there are non-zero rows in V, then the next step starts by choosing a row of A as follows: o Let r be the minimum integer such that at least one row of A has exactly r ones in V.
最初のフェーズにはせいぜいLステップがあります。私がu = l、つまりvとv上記のサブマトリックスが消え、aがiで構成されている場合、vの下のゼロサブマトリックス、U。Vが消える前のステップVには、そのステップで選択するゼロ以外の行はありません。vにゼロ以外の行がある場合は、次のステップは次のようにaの行を選択することから始まります。orを最小整数とし、aの少なくとも1つの行がvに正確にrを持つようにします。
* If r != 2, then choose a row with exactly r ones in V with minimum original degree among all such rows.
* r！= 2の場合、そのようなすべての行の中で最小の元の程度を持つvの正確なrをvの行を選択します。
* If r = 2, then choose any row with exactly 2 ones in V that is part of a maximum size component in the graph defined by V.
* r = 2の場合、Vで定義されたグラフの最大サイズコンポーネントの一部であるVに正確に2つの行を持つ行を選択します。
After the row is chosen in this step the first row of A that intersects V is exchanged with the chosen row so that the chosen row is the first row that intersects V. The columns of A among those that intersect V are reordered so that one of the r ones in the chosen row appears in the first column of V and so that the remaining r-1 ones appear in the last columns of V. Then, the chosen row is exclusive-ORed into all the other rows of A below the chosen row that have a one in the first column of V. Finally, i is incremented by 1 and u is incremented by r-1, which completes the step.
このステップで行が選択された後、aの最初の行は、選択された行と交換されるaの最初の行は、選択された行がVと交差する最初の行になるようにします。選択した行のRはVの最初の列に表示されるため、残りのR-1がVの最後の列に表示されます。その後、選択した行は、選択したAの他のすべての行に排他的に使用されています。Vの最初の列に1つを持つ行。最後に、Iは1で増加し、UはR-1で増加し、ステップが完了します。
The submatrix U is further partitioned into the first i rows, U_upper, and the remaining M - i rows, U_lower. Gaussian elimination is performed in the second phase on U_lower to either determine that its rank is less than u (decoding failure) or to convert it into a matrix where the first u rows is the identity matrix (success of the second phase). Call this u by u identity matrix I_u. The M - L rows of A that intersect U_lower - I_u are discarded. After this phase, A has L rows and L columns.
サブマトリックスuは、最初のi行、u_upper、および残りのm -i列、u_lowerにさらに分割されます。ガウスの除去は、U_Lowerの第2フェーズで実行され、そのランクがUよりも低い（障害を解読する）か、最初のU行がIDマトリックス（第2フェーズの成功）であるマトリックスに変換することを決定します。これをuでuをused matrix i_uに呼びます。u_lower -i_uと交差するaのm -l列は破棄されます。このフェーズの後、aはl行とl列を持っています。
After the second phase, the only portion of A that needs to be zeroed out to finish converting A into the L by L identity matrix is U_upper. The number of rows i of the submatrix U_upper is generally much larger than the number of columns u of U_upper. To zero out U_upper efficiently, the following precomputation matrix U' is computed based on I_u in the third phase and then U' is used in the fourth phase to zero out U_upper. The u rows of Iu are partitioned into ceil(u/8) groups of 8 rows each. Then, for each group of 8 rows, all non-zero combinations of the 8 rows are computed, resulting in 2^^8 - 1 = 255 rows (this can be done with 2^^8-8-1 = 247 exclusive-ors of rows per group, since the combinations of Hamming weight one that appear in I_u do not need to be recomputed). Thus, the resulting precomputation matrix U' has ceil(u/8)*255 rows and u columns. Note that U' is not formally a part of matrix A, but will be used in the fourth phase to zero out U_upper.
2番目のフェーズの後、Aの唯一の部分をゼロアウトする必要があるのは、lバイLバイLのアイデンティティマトリックスへの変換を完了することです。サブマトリックスU_upperの行Iの数は、一般に、u_upperの列uの数よりもはるかに大きいです。u_upperを効率的にゼロにするために、次の事前計算マトリックスu 'は第3フェーズのi_uに基づいて計算され、u'はu 'を使用してU_upperをゼロにします。iuのu列は、それぞれ8行の天井（u/8）グループに分割されます。次に、8行の各グループについて、8行のすべての非ゼロの組み合わせが計算され、2 ^^ 8-1 = 255行になります（これは2 ^^ 8-8-1 = 247限定で実行できます - I_Uに表示される重量をハミングするものの組み合わせは、再計算する必要がないため、グループあたりの行のORS。したがって、結果の事前計算マトリックスu 'には、ceil（u/8）*255行とu列があります。u 'は正式にはマトリックスAの一部ではありませんが、第4フェーズでu_upperをゼロにするために使用されることに注意してください。
For each of the first i rows of A, for each group of 8 columns in the U_upper submatrix of this row, if the set of 8 column entries in U_upper are not all zero, then the row of the precomputation matrix U' that matches the pattern in the 8 columns is exclusive-ORed into the row, thus zeroing out those 8 columns in the row at the cost of exclusive-ORing one row of U' into the row.
Aの最初のI行のそれぞれについて、この行のU_UPPERサブマトリックスの8列のグループごとに、U_UPPERの8列のエントリのセットがすべてゼロではない場合、事前計算マトリックスUの行はそれに一致します。8列のパターンは排他的に行われているため、u 'の1行を列に並べるために、行の8列をゼロにします。
After this phase, A is the L by L identity matrix and a complete decoding schedule has been successfully formed. Then, as explained in Section 5.5.2.1, the corresponding decoding consisting of exclusive-ORing known encoding symbols can be executed to recover the intermediate symbols based on the decoding schedule. The triples associated with all source symbols are computed according to Section 5.4.2.2. The triples for received source symbols are used in the decoding. The triples for missing source symbols are used to determine which intermediate symbols need to be exclusive-ORed to recover the missing source symbols.
このフェーズの後、AはLバイLアイデンティティマトリックスであり、完全なデコードスケジュールが正常に形成されました。次に、セクション5.5.2.1で説明したように、デコードスケジュールに基づいて中間記号を回復するために、排他的な既知のエンコード記号で構成される対応するデコードを実行できます。すべてのソースシンボルに関連付けられたトリプルは、セクション5.4.2.2に従って計算されます。受信したソースシンボルのトリプルは、デコードで使用されます。欠落しているソースシンボルのトリプルは、欠落しているソースシンボルを回復するために排他的である必要がある中間記号を決定するために使用されます。
The two tables V0 and V1 described in Section 5.4.4.1 are given below. Each entry is a 32-bit integer in decimal representation.
セクション5.4.4.1で説明した2つの表V0とV1を以下に示します。各エントリは、10進表現の32ビット整数です。
251291136, 3952231631, 3370958628, 4070167936, 123631495, 3351110283, 3218676425, 2011642291, 774603218, 2402805061, 1004366930, 1843948209, 428891132, 3746331984, 1591258008, 3067016507, 1433388735, 504005498, 2032657933, 3419319784, 2805686246, 3102436986, 3808671154, 2501582075, 3978944421, 246043949, 4016898363, 649743608, 1974987508, 2651273766, 2357956801, 689605112, 715807172, 2722736134, 191939188, 3535520147, 3277019569, 1470435941, 3763101702, 3232409631, 122701163, 3920852693, 782246947, 372121310, 2995604341, 2045698575, 2332962102, 4005368743, 218596347, 3415381967, 4207612806, 861117671, 3676575285, 2581671944, 3312220480, 681232419, 307306866, 4112503940, 1158111502, 709227802, 2724140433, 4201101115, 4215970289, 4048876515, 3031661061, 1909085522, 510985033, 1361682810, 129243379, 3142379587, 2569842483, 3033268270, 1658118006, 932109358, 1982290045, 2983082771, 3007670818, 3448104768, 683749698, 778296777, 1399125101, 1939403708, 1692176003, 3868299200, 1422476658, 593093658, 1878973865, 2526292949, 1591602827, 3986158854, 3964389521, 2695031039, 1942050155, 424618399, 1347204291, 2669179716, 2434425874, 2540801947, 1384069776, 4123580443, 1523670218, 2708475297, 1046771089, 2229796016, 1255426612, 4213663089, 1521339547, 3041843489, 420130494, 10677091, 515623176, 3457502702, 2115821274, 2720124766, 3242576090, 854310108, 425973987, 325832382, 1796851292, 2462744411, 1976681690, 1408671665, 1228817808, 3917210003, 263976645, 2593736473, 2471651269, 4291353919, 650792940, 1191583883, 3046561335, 2466530435, 2545983082, 969168436, 2019348792, 2268075521, 1169345068, 3250240009, 3963499681, 2560755113, 911182396, 760842409, 3569308693, 2687243553, 381854665, 2613828404, 2761078866, 1456668111, 883760091, 3294951678, 1604598575, 1985308198, 1014570543, 2724959607, 3062518035, 3115293053, 138853680, 4160398285, 3322241130, 2068983570, 2247491078, 3669524410, 1575146607, 828029864, 3732001371, 3422026452, 3370954177, 4006626915, 543812220, 1243116171, 3928372514, 2791443445, 4081325272, 2280435605, 885616073, 616452097, 3188863436, 2780382310, 2340014831, 1208439576, 258356309, 3837963200, 2075009450, 3214181212, 3303882142, 880813252, 1355575717, 207231484, 2420803184, 358923368, 1617557768, 3272161958, 1771154147, 2842106362, 1751209208, 1421030790, 658316681, 194065839, 3241510581, 38625260, 301875395, 4176141739, 297312930, 2137802113, 1502984205, 3669376622, 3728477036, 234652930, 2213589897, 2734638932, 1129721478, 3187422815, 2859178611, 3284308411, 3819792700, 3557526733, 451874476, 1740576081, 3592838701, 1709429513, 3702918379, 3533351328, 1641660745, 179350258, 2380520112, 3936163904, 3685256204, 3156252216, 1854258901, 2861641019, 3176611298, 834787554, 331353807, 517858103, 3010168884, 4012642001, 2217188075, 3756943137, 3077882590, 2054995199, 3081443129, 3895398812, 1141097543, 2376261053, 2626898255, 2554703076, 401233789, 1460049922, 678083952, 1064990737, 940909784, 1673396780, 528881783, 1712547446, 3629685652, 1358307511
246043949、4016898363、649743608、1974987508、2651273766、2357956801、689605112、715807172、2722736134、191999188、3535520147、14701956901956901956901956901954701954701956901956901901956901901956901956901956701956701956701701956701701956701チ41、3763101702、3232409631、122701163、3920852693、7822246947、372121310、2995604341、2045698575、2332962102、4005368743、218743、218743、218743、218743、2187474207612806、861117671、3676575285、2581671944、3312220480、681232419、307306866、4112503940、1158111502、70922827802、2724140433、42011515、4201151527802、 4048876515、3031661061、1909085522、510985033、1361682810、129243379、3142379587、2569842483、3033268270、165818006、932109358、2983082771、3007670818、3448104768、683749698、778296777777777770、1399125101、1939403708、1692176003、3868299200、142476658、593097225722522247658、5930972257222476658224765888888888888、593097258258224765882247658882247658882247658822476588822476588224765822247658222476582224765822597225972259722593972 949、1591602827、3986158854、3964389521、2695031039、1942050155、424618399、1347204291、2669179716、2434425874、2540801947、134476、1349476、13494762593736473、2471651269、4291353919、650792940、1191583883、3046561335、2466530435、2545983082、969168436、2019348792、226807552109349252121933492521212121021021021021021021021021021021069521069210695212193チ、3963499681、2560755113、911182396、760842409、3569308693、2687243553、381854665、2613828404、276107888666666666666666666666666656668111、8837778891、8837749519519519491616452097、3188863436、2780382310、2340014831、1208439576、258356309、3837963200、2075009450、3214181212、33038882142、880813252、13307142、13307142、20755552、207555552、13555552、13555555552、135555555552、 2420803184、358923368、1617557768、3272161958、1771154147、2842106362、1751209208、1421030790、658316681、194065839、3241510581、386260、301875395、4176141739、297312930、2137802113、1502984205、3669376622、3728477036、234652930、2213589897、2734638932、1129721478、1129721478、1129721478、 11、3284308411、3819792700、3557526733、451874476、1740576081、3592838701、1709429513、3702918379、3533351328、1641660745、179350551328、1741660745、3936163904、3685256204、3156252216、1854258901、2861641019、3176611298、834787554、331353807、517858103、301688884、4012642001、22175175175175175175175175175175175175175175175175175175175175172172172172172172172175175172172172172172172172172001 37、3077882590、2054995199、3081443129、3895398812、1141097543、2376261053、2626898255、2554703076、401233789、1460049922、679952、67927952、67922、679222、67927952、67927952、1460049922、67927952940909784、1673396780、528881783、1712547446、3629685652、1358307511
807385413, 2043073223, 3336749796, 1302105833, 2278607931, 541015020, 1684564270, 372709334, 3508252125, 1768346005, 1270451292, 2603029534, 2049387273, 3891424859, 2152948345, 4114760273, 915180310, 3754787998, 700503826, 2131559305, 1308908630, 224437350, 4065424007, 3638665944, 1679385496, 3431345226, 1779595665, 3068494238, 1424062773, 1033448464, 4050396853, 3302235057, 420600373, 2868446243, 311689386, 259047959, 4057180909, 1575367248, 4151214153, 110249784, 3006865921, 4293710613, 3501256572, 998007483, 499288295, 1205710710, 2997199489, 640417429, 3044194711, 486690751, 2686640734, 2394526209, 2521660077, 49993987, 3843885867, 4201106668, 415906198, 19296841, 2402488407, 2137119134, 1744097284, 579965637, 2037662632, 852173610, 2681403713, 1047144830, 2982173936, 910285038, 4187576520, 2589870048, 989448887, 3292758024, 506322719, 176010738, 1865471968, 2619324712, 564829442, 1996870325, 339697593, 4071072948, 3618966336, 2111320126, 1093955153, 957978696, 892010560, 1854601078, 1873407527, 2498544695, 2694156259, 1927339682, 1650555729, 183933047, 3061444337, 2067387204, 228962564, 3904109414, 1595995433, 1780701372, 2463145963, 307281463, 3237929991, 3852995239, 2398693510, 3754138664, 522074127, 146352474, 4104915256, 3029415884, 3545667983, 332038910, 976628269, 3123492423, 3041418372, 2258059298, 2139377204, 3243642973, 3226247917, 3674004636, 2698992189, 3453843574, 1963216666, 3509855005, 2358481858, 747331248, 1957348676, 1097574450, 2435697214, 3870972145, 1888833893, 2914085525, 4161315584, 1273113343, 3269644828, 3681293816, 412536684, 1156034077, 3823026442, 1066971017, 3598330293, 1979273937, 2079029895, 1195045909, 1071986421, 2712821515, 3377754595, 2184151095, 750918864, 2585729879, 4249895712, 1832579367, 1192240192, 946734366, 31230688, 3174399083, 3549375728, 1642430184, 1904857554, 861877404, 3277825584, 4267074718, 3122860549, 666423581, 644189126, 226475395, 307789415, 1196105631, 3191691839, 782852669, 1608507813, 1847685900, 4069766876, 3931548641, 2526471011, 766865139, 2115084288, 4259411376, 3323683436, 568512177, 3736601419, 1800276898, 4012458395, 1823982, 27980198, 2023839966, 869505096, 431161506, 1024804023, 1853869307, 3393537983, 1500703614, 3019471560, 1351086955, 3096933631, 3034634988, 2544598006, 1230942551, 3362230798, 159984793, 491590373, 3993872886, 3681855622, 903593547, 3535062472, 1799803217, 772984149, 895863112, 1899036275, 4187322100, 101856048, 234650315, 3183125617, 3190039692, 525584357, 1286834489, 455810374, 1869181575, 922673938, 3877430102, 3422391938, 1414347295, 1971054608, 3061798054, 830555096, 2822905141, 167033190, 1079139428, 4210126723, 3593797804, 429192890, 372093950, 1779187770, 3312189287, 204349348, 452421568, 2800540462, 3733109044, 1235082423, 1765319556, 3174729780, 3762994475, 3171962488, 442160826, 198349622, 45942637, 1324086311, 2901868599, 678860040, 3812229107, 19936821, 1119590141, 3640121682, 3545931032, 2102949142, 2828208598, 3603378023, 4135048896
3431345226、1779595665、3068494238、1424062773、10334484644444、4050396853、3302235057、420600373、2868446243、311689386、259047959,5495924727272727272472472727272727272721689386、259047959,000959 8、4151214153、110249784、3006865921、4293710613、3501256572、998007483、499288295、1205710710、2997199489、640417429、304194711、30417429、3041747112686640734、2394526209、2521660077、49993987、3843885867、420110668、415906198、19296841、2402488407、21371919134、1744097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2097284、2137284、21379134、2137919134、 、852173610、2681403713、1047144830、2982173936、910285038、4187576520、2589870048、989448887、3292758024、50632719、176010738、1097574450、2435697214、3870972145、1888833893、29140855525、4161315584、12731133343、3269644828、3681293816、41253684、11253684、11253684、10444444444444444038444444038444440384403844038440384038403844038403844038440384403844032 66971017、3598330293、1979273937、2079029895、1195045909、1071986421、2712821515、3377754595、2184151095、75091888888884、2585729959595959595959595959595959595959595959595959595959595959595959595995995995995959959959999999999999年67、1192240192、946734366、31230688、3174399083、3549375728、1642430184、1904857554、8618777404、3277825584、4267074718、31228448418、312284848166666666666666666666666666666666666668181818181818181818181818181818181818181818181818181818181818181818181818181818181818181842842 89126、226475395、307789415、1196105631、3191691839、782852669、1608507813、1847685900、4069766876、3931548641、252671011、76688888888888888888888888888888888888881393681855622、903593547、3535062472、1799803217、772984149、895863112、1899036275、4187322100、101856048、234650315、3183125617、5196969696969696969696969696969696969696969696969696969696969696969692 7、1286834489、455810374、1869181575、922673938、3877430102、3422391938、1414347295、1971054608、3061798054、830555555555555555555555555555555555555555555555555555555555555555555555555555555555556 -22905141411411411411411413640121682、3545931032、2102949142、2828208598、3603378023、4135048896
For each value of K, the systematic index J(K) is designed to have the property that the set of source symbol triples (d[0], a[0], b[0]), ..., (d[L-1], a[L-1], b[L-1]) are such that the L intermediate symbols are uniquely defined, i.e., the matrix A in Section 5.4.2.4.2 has full rank and is therefore invertible.
kの各値について、系統的インデックスj（k）は、ソースシンボルのセットがトリプル（d [0]、a [0]、b [0]）、...、（d [）という特性を持つように設計されています。l-1]、a [l-1]、b [l-1]）は、L中間記号が一意に定義されるようなものです。つまり、セクション5.4.2.4.2のマトリックスAはフルランクであるため、反転可能です。
The following is the list of the systematic indices for values of K between 4 and 8192 inclusive.
以下は、4〜8192を含むKの値の系統的指数のリストです。
18, 14, 61, 46, 14, 22, 20, 40, 48, 1, 29, 40, 43, 46, 18, 8, 20, 2, 61, 26, 13, 29, 36, 19, 58, 5, 58, 0, 54, 56, 24, 14, 5, 67, 39, 31, 25, 29, 24, 19, 14, 56, 49, 49, 63, 30, 4, 39, 2, 1, 20, 19, 61, 4, 54, 70, 25, 52, 9, 26, 55, 69, 27, 68, 75, 19, 64, 57, 45, 3, 37, 31, 100, 41, 25, 41, 53, 23, 9, 31, 26, 30, 30, 46, 90, 50, 13, 90, 77, 61, 31, 54, 54, 3, 21, 66, 21, 11, 23, 11, 29, 21, 7, 1, 27, 4, 34, 17, 85, 69, 17, 75, 93, 57, 0, 53, 71, 88, 119, 88, 90, 22, 0, 58, 41, 22, 96, 26, 79, 118, 19, 3, 81, 72, 50, 0, 32, 79, 28, 25, 12, 25, 29, 3, 37, 30, 30, 41, 84, 32, 31, 61, 32, 61, 7, 56, 54, 39, 33, 66, 29, 3, 14, 75, 75, 78, 84, 75, 84, 25, 54, 25, 25, 107, 78, 27, 73, 0, 49, 96, 53, 50, 21, 10, 73, 58, 65, 27, 3, 27, 18, 54, 45, 69, 29, 3, 65, 31, 71, 76, 56, 54, 76, 54, 13, 5, 18, 142, 17, 3, 37, 114, 41, 25, 56, 0, 23, 3, 41, 22, 22, 31, 18, 48, 31, 58, 37, 75, 88, 3, 56, 1, 95, 19, 73, 52, 52, 4, 75, 26, 1, 25, 10, 1, 70, 31, 31, 12, 10, 54, 46, 11, 74, 84, 74, 8, 58, 23, 74, 8, 36, 11, 16, 94, 76, 14, 57, 65, 8, 22, 10, 36, 36, 96, 62, 103, 6, 75, 103, 58, 10, 15, 41, 75, 125, 58, 15, 10, 34, 29, 34, 4, 16, 29, 18, 18, 28, 71, 28, 43, 77, 18, 41, 41, 41, 62, 29, 96, 15, 106, 43, 15, 3, 43, 61, 3, 18, 103, 77, 29, 103, 19, 58, 84, 58, 1, 146, 32, 3, 70, 52, 54, 29, 70, 69, 124, 62, 1, 26, 38, 26, 3, 16, 26, 5, 51, 120, 41, 16, 1, 43, 34, 34, 29, 37, 56, 29, 96, 86, 54, 25, 84, 50, 34, 34, 93, 84, 96, 29, 29, 50, 50, 6, 1, 105, 78, 15, 37, 19, 50, 71, 36, 6, 54, 8, 28, 54, 75, 75, 16, 75, 131, 5, 25, 16, 69, 17, 69, 6, 96, 53, 96, 41, 119, 6, 6, 88, 50, 88, 52, 37, 0, 124, 73, 73, 7, 14, 36, 69, 79, 6, 114, 40, 79, 17, 77, 24, 44, 37, 69, 27, 37, 29, 33, 37, 50, 31, 69, 29, 101, 7, 61, 45, 17, 73, 37, 34, 18, 94, 22, 22, 63, 3, 25, 25, 17, 3, 90, 34, 34, 41, 34, 41, 54, 41, 54, 41, 41, 41, 163, 143, 96, 18, 32, 39, 86, 104, 11, 17, 17, 11, 86, 104, 78, 70, 52, 78, 17, 73, 91, 62, 7, 128, 50, 124, 18, 101, 46, 10, 75, 104, 73, 58, 132, 34, 13, 4, 95, 88, 33, 76, 74, 54, 62, 113, 114, 103, 32, 103, 69, 54, 53, 3, 11, 72, 31, 53, 102, 37, 53, 11, 81, 41, 10, 164, 10, 41, 31, 36, 113, 82, 3, 125, 62, 16, 4, 41, 41, 4, 128, 49, 138, 128, 74, 103, 0, 6, 101, 41, 142, 171, 39, 105, 121, 81, 62, 41, 81, 37, 3, 81, 69, 62, 3, 69, 70, 21, 29, 4, 91, 87, 37, 79, 36, 21, 71, 37, 41, 75, 128, 128, 15, 25, 3, 108, 73, 91, 62, 114, 62, 62, 36, 36, 15, 58, 114, 61, 114, 58, 105, 114, 41, 61, 176, 145, 46, 37, 30, 220, 77, 138, 15, 1, 128, 53, 50, 50, 58, 8, 91, 114, 105, 63, 91, 37, 37, 13, 169, 51, 102, 6, 102, 23, 105, 23, 58, 6, 29, 29, 19, 82, 29, 13, 36, 27, 29, 61, 12, 18, 127, 127, 12, 44, 102, 18, 4, 15, 206, 53, 127, 53, 17, 69, 69, 69, 29, 29, 109, 25, 102, 25, 53, 62, 99, 62, 62, 29, 62, 62, 45, 91, 125, 29, 29, 29, 4, 117, 72, 4, 30, 71, 71, 95, 79, 179, 71, 30, 53, 32, 32, 49, 25, 91, 25, 26, 26, 103, 123, 26, 41, 162, 78, 52, 103, 25, 6, 142, 94, 45, 45, 94, 127, 94, 94, 94, 47, 209, 138, 39, 39, 19, 154, 73, 67, 91, 27, 91, 84, 4, 84, 91, 12, 14, 165, 142, 54, 69, 192, 157, 185, 8, 95, 25, 62, 103, 103, 95, 71, 97, 62, 128, 0, 29, 51, 16, 94, 16, 16, 51, 0, 29, 85, 10, 105, 16, 29, 29, 13, 29, 4, 4, 132, 23, 95, 25, 54, 41, 29, 50, 70, 58, 142, 72, 70, 15, 72, 54, 29, 22, 145, 29, 127, 29, 85, 58, 101, 34, 165, 91, 46, 46, 25, 185, 25, 77, 128, 46, 128, 46, 188, 114, 46, 25, 45, 45, 114, 145, 114, 15, 102, 142, 8, 73, 31, 139, 157, 13, 79, 13, 114, 150, 8, 90, 91, 123, 69, 82, 132, 8, 18, 10, 102, 103, 114, 103, 8, 103, 13, 115, 55, 62, 3, 8, 154, 114, 99, 19, 8, 31, 73, 19, 99, 10, 6, 121, 32, 13, 32, 119, 32, 29, 145, 30, 13, 13, 114, 145, 32, 1, 123, 39, 29, 31, 69, 31, 140, 72, 72, 25, 25, 123, 25, 123, 8, 4, 85, 8, 25, 39, 25, 39, 85, 138, 25, 138, 25, 33, 102, 70, 25, 25, 31, 25, 25, 192, 69, 69, 114, 145, 120, 120, 8, 33, 98, 15, 212, 155, 8, 101, 8, 8, 98, 68, 155, 102, 132, 120, 30, 25, 123, 123, 101, 25, 123, 32, 24, 94, 145, 32, 24, 94, 118, 145, 101, 53, 53, 25, 128, 173, 142, 81, 81, 69, 33, 33, 125, 4, 1, 17, 27, 4, 17, 102, 27, 13, 25, 128, 71, 13, 39, 53, 13, 53, 47, 39, 23, 128, 53, 39, 47, 39, 135, 158, 136, 36, 36, 27, 157, 47, 76, 213, 47, 156, 25, 25, 53, 25, 53, 25, 86, 27, 159, 25, 62, 79, 39, 79, 25, 145, 49, 25, 143, 13, 114, 150, 130, 94, 102, 39, 4, 39, 61, 77, 228, 22, 25, 47, 119, 205, 122, 119, 205, 119, 22, 119, 258, 143, 22, 81, 179, 22, 22, 143, 25, 65, 53, 168, 36, 79, 175, 37, 79, 70, 79, 103, 70, 25, 175, 4, 96, 96, 49, 128, 138, 96, 22, 62, 47, 95, 105, 95, 62, 95, 62, 142, 103, 69, 103, 30, 103, 34, 173, 127, 70, 127, 132, 18, 85, 22, 71, 18, 206, 206, 18, 128, 145, 70, 193, 188, 8, 125, 114, 70, 128, 114, 145, 102, 25, 12, 108, 102, 94, 10, 102, 1, 102, 124, 22, 22, 118, 132, 22, 116, 75, 41, 63, 41, 189, 208, 55, 85, 69, 8, 71, 53, 71, 69, 102, 165, 41, 99, 69, 33, 33, 29, 156, 102, 13, 251, 102, 25, 13, 109, 102, 164, 102, 164, 102, 25, 29, 228, 29, 259, 179, 222, 95, 94, 30, 30, 30, 142, 55, 142, 72, 55, 102, 128, 17, 69, 164, 165, 3, 164, 36, 165, 27, 27, 45, 21, 21, 237, 113, 83, 231, 106, 13, 154, 13, 154, 128, 154, 148, 258, 25, 154, 128, 3, 27, 10, 145, 145, 21, 146, 25, 1, 185, 121, 0, 1, 95, 55, 95, 95, 30, 0, 27, 95, 0, 95, 8, 222, 27, 121, 30, 95, 121, 0, 98, 94, 131, 55, 95, 95, 30, 98, 30, 0, 91, 145, 66, 179, 66, 58, 175, 29, 0, 31, 173, 146, 160, 39, 53, 28, 123, 199, 123, 175, 146, 156, 54, 54, 149, 25, 70, 178, 128, 25, 70, 70, 94, 224, 54, 4, 54, 54, 25, 228, 160, 206, 165, 143, 206, 108, 220, 234, 160, 13, 169, 103, 103, 103, 91, 213, 222, 91, 103, 91, 103, 31, 30, 123, 13, 62, 103, 50, 106, 42, 13, 145, 114, 220, 65, 8, 8, 175, 11, 104, 94, 118, 132, 27, 118, 193, 27, 128, 127, 127, 183, 33, 30, 29, 103, 128, 61, 234, 165, 41, 29, 193, 33, 207, 41, 165, 165, 55, 81, 157, 157, 8, 81, 11, 27, 8, 8, 98, 96, 142, 145, 41, 179, 112, 62, 180, 206, 206, 165, 39, 241, 45, 151, 26, 197, 102, 192, 125, 128, 67, 128, 69, 128, 197, 33, 125, 102, 13, 103, 25, 30, 12, 30, 12, 30, 25, 77, 12, 25, 180, 27, 10, 69, 235, 228, 343, 118, 69, 41, 8, 69, 175, 25, 69, 25, 125, 41, 25, 41, 8, 155, 146, 155, 146, 155, 206, 168, 128, 157, 27, 273, 211, 211, 168, 11, 173, 154, 77, 173, 77, 102, 102, 102, 8, 85, 95, 102, 157, 28, 122, 234, 122, 157, 235, 222, 241, 10, 91, 179, 25, 13, 25, 41, 25, 206, 41, 6, 41, 158, 206, 206, 33, 296, 296, 33, 228, 69, 8, 114, 148, 33, 29, 66, 27, 27, 30, 233, 54, 173, 108, 106, 108, 108, 53, 103, 33, 33, 33, 176, 27, 27, 205, 164, 105, 237, 41, 27, 72, 165, 29, 29, 259, 132, 132, 132, 364, 71, 71, 27, 94, 160, 127, 51, 234, 55, 27, 95, 94, 165, 55, 55, 41, 0, 41, 128, 4, 123, 173, 6, 164, 157, 121, 121, 154, 86, 164, 164, 25, 93, 164, 25, 164, 210, 284, 62, 93, 30, 25, 25, 30, 30, 260, 130, 25, 125, 57, 53, 166, 166, 166, 185, 166, 158, 94, 113, 215, 159, 62, 99, 21, 172, 99, 184, 62, 259, 4, 21, 21, 77, 62, 173, 41, 146, 6, 41, 128, 121, 41, 11, 121, 103, 159, 164, 175, 206, 91, 103, 164, 72, 25, 129, 72, 206, 129, 33, 103, 102, 102, 29, 13, 11, 251, 234, 135, 31, 8, 123, 65, 91, 121, 129, 65, 243, 10, 91, 8, 65, 70, 228, 220, 243, 91, 10, 10, 30, 178, 91, 178, 33, 21, 25, 235, 165, 11, 161, 158, 27, 27, 30, 128, 75, 36, 30, 36, 36, 173, 25, 33, 178, 112, 162, 112, 112, 112, 162, 33, 33, 178, 123, 123, 39, 106, 91, 106, 106, 158, 106, 106, 284, 39, 230, 21, 228, 11, 21, 228, 159, 241, 62, 10, 62, 10, 68, 234, 39, 39, 138, 62, 22, 27, 183, 22, 215, 10, 175, 175, 353, 228, 42, 193, 175, 175, 27, 98, 27, 193, 150, 27, 173, 17, 233, 233, 25, 102, 123, 152, 242, 108, 4, 94, 176, 13, 41, 219, 17, 151, 22, 103, 103, 53, 128, 233, 284, 25, 265, 128, 39, 39, 138, 42, 39, 21, 86, 95, 127, 29, 91, 46, 103, 103, 215, 25, 123, 123, 230, 25, 193, 180, 30, 60, 30, 242, 136, 180, 193, 30, 206, 180, 60, 165, 206, 193, 165, 123, 164, 103, 68, 25, 70, 91, 25, 82, 53, 82, 186, 53, 82, 53, 25, 30, 282, 91, 13, 234, 160, 160, 126, 149, 36, 36, 160, 149, 178, 160, 39, 294, 149, 149, 160, 39, 95, 221, 186, 106, 178, 316, 267, 53, 53, 164, 159, 164, 165, 94, 228, 53, 52, 178, 183, 53, 294, 128, 55, 140, 294, 25, 95, 366, 15, 304, 13, 183, 77, 230, 6, 136, 235, 121, 311, 273, 36, 158, 235, 230, 98, 201, 165, 165, 165, 91, 175, 248, 39, 185, 128, 39, 39, 128, 313, 91, 36, 219, 130, 25, 130, 234, 234, 130, 234, 121, 205, 304, 94, 77, 64, 259, 60, 60, 60, 77, 242, 60, 145, 95, 270, 18, 91, 199, 159, 91, 235, 58, 249, 26, 123, 114, 29, 15, 191, 15, 30, 55, 55, 347, 4, 29, 15, 4, 341, 93, 7, 30, 23, 7, 121, 266, 178, 261, 70, 169, 25, 25, 158, 169, 25, 169, 270, 270, 13, 128, 327, 103, 55, 128, 103, 136, 159, 103, 327, 41, 32, 111, 111, 114, 173, 215, 173, 25, 173, 180, 114, 173, 173, 98, 93, 25, 160, 157, 159, 160, 159, 159, 160, 320, 35, 193, 221, 33, 36, 136, 248, 91, 215, 125, 215, 156, 68, 125, 125, 1, 287, 123, 94, 30, 184, 13, 30, 94, 123, 206, 12, 206, 289, 128, 122, 184, 128, 289, 178, 29, 26, 206, 178, 65, 206, 128, 192, 102, 197, 36, 94, 94, 155, 10, 36, 121, 280, 121, 368, 192, 121, 121, 179, 121, 36, 54, 192, 121, 192, 197, 118, 123, 224, 118, 10, 192, 10, 91, 269, 91, 49, 206, 184, 185, 62, 8, 49, 289, 30, 5, 55, 30, 42, 39, 220, 298, 42, 347, 42, 234, 42, 70, 42, 55, 321, 129, 172, 173, 172, 13, 98, 129, 325, 235, 284, 362, 129, 233, 345, 175, 261, 175, 60, 261, 58, 289, 99, 99, 99, 206, 99, 36, 175, 29, 25, 432, 125, 264, 168, 173, 69, 158, 273, 179, 164, 69, 158, 69, 8, 95, 192, 30, 164, 101, 44, 53, 273, 335, 273, 53, 45, 128, 45, 234, 123, 105, 103, 103, 224, 36, 90, 211, 282, 264, 91, 228, 91, 166, 264, 228, 398, 50, 101, 91, 264, 73, 36, 25, 73, 50, 50, 242, 36, 36, 58, 165, 204, 353, 165, 125, 320, 128, 298, 298, 180, 128, 60, 102, 30, 30, 53, 179, 234, 325, 234, 175, 21, 250, 215, 103, 21, 21, 250, 91, 211, 91, 313, 301, 323, 215, 228, 160, 29, 29, 81, 53, 180, 146, 248, 66, 159, 39, 98, 323, 98, 36, 95, 218, 234, 39, 82, 82, 230, 62, 13, 62, 230, 13, 30, 98, 0, 8, 98, 8, 98, 91, 267, 121, 197, 30, 78, 27, 78, 102, 27, 298, 160, 103, 264, 264, 264, 175, 17, 273, 273, 165, 31, 160, 17, 99, 17, 99, 234, 31, 17, 99, 36, 26, 128, 29, 214, 353, 264, 102, 36, 102, 264, 264, 273, 273, 4, 16, 138, 138, 264, 128, 313, 25, 420, 60, 10, 280, 264, 60, 60, 103, 178, 125, 178, 29, 327, 29, 36, 30, 36, 4, 52, 183, 183, 173, 52, 31, 173, 31, 158, 31, 158, 31, 9, 31, 31, 353, 31, 353, 173, 415, 9, 17, 222, 31, 103, 31, 165, 27, 31, 31, 165, 27, 27, 206, 31, 31, 4, 4, 30, 4, 4, 264, 185, 159, 310, 273, 310, 173, 40, 4, 173, 4, 173, 4, 250, 250, 62, 188, 119, 250, 233, 62, 121, 105, 105, 54, 103, 111, 291, 236, 236, 103, 297, 36, 26, 316, 69, 183, 158, 206, 129, 160, 129, 184, 55, 179, 279, 11, 179, 347, 160, 184, 129, 179, 351, 179, 353, 179, 129, 129, 351, 11, 111, 93, 93, 235, 103, 173, 53, 93, 50, 111, 86, 123, 94, 36, 183, 60, 55, 55, 178, 219, 253, 321, 178, 235, 235, 183, 183, 204, 321, 219, 160, 193, 335, 121, 70, 69, 295, 159, 297, 231, 121, 231, 136, 353, 136, 121, 279, 215, 366, 215, 353, 159, 353, 353, 103, 31, 31, 298, 298, 30, 30, 165, 273, 25, 219, 35, 165, 259, 54, 36, 54, 54, 165, 71, 250, 327, 13, 289, 165, 196, 165, 165, 94, 233, 165, 94, 60, 165, 96, 220, 166, 271, 158, 397, 122, 53, 53, 137, 280, 272, 62, 30, 30, 30, 105, 102, 67, 140, 8, 67, 21, 270, 298, 69, 173, 298, 91, 179, 327, 86, 179, 88, 179, 179, 55, 123, 220, 233, 94, 94, 175, 13, 53, 13, 154, 191, 74, 83, 83, 325, 207, 83, 74, 83, 325, 74, 316, 388, 55, 55, 364, 55, 183, 434, 273, 273, 273, 164, 213, 11, 213, 327, 321, 21, 352, 185, 103, 13, 13, 55, 30, 323, 123, 178, 435, 178, 30, 175, 175, 30, 481, 527, 175, 125, 232, 306, 232, 206, 306, 364, 206, 270, 206, 232, 10, 30, 130, 160, 130, 347, 240, 30, 136, 130, 347, 136, 279, 298, 206, 30, 103, 273, 241, 70, 206, 306, 434, 206, 94, 94, 156, 161, 321, 321, 64, 161, 13, 183, 183, 83, 161, 13, 169, 13, 159, 36, 173, 159, 36, 36, 230, 235, 235, 159, 159, 335, 312, 42, 342, 264, 39, 39, 39, 34, 298, 36, 36, 252, 164, 29, 493, 29, 387, 387, 435, 493, 132, 273, 105, 132, 74, 73, 206, 234, 273, 206, 95, 15, 280, 280, 280, 280, 397, 273, 273, 242, 397, 280, 397, 397, 397, 273, 397, 280, 230, 137, 353, 67, 81, 137, 137, 353, 259, 312, 114, 164, 164, 25, 77, 21, 77, 165, 30, 30, 231, 234, 121, 234, 312, 121, 364, 136, 123, 123, 136, 123, 136, 150, 264, 285, 30, 166, 93, 30, 39, 224, 136, 39, 355, 355, 397, 67, 67, 25, 67, 25, 298, 11, 67, 264, 374, 99, 150, 321, 67, 70, 67, 295, 150, 29, 321, 150, 70, 29, 142, 355, 311, 173, 13, 253, 103, 114, 114, 70, 192, 22, 128, 128, 183, 184, 70, 77, 215, 102, 292, 30, 123, 279, 292, 142, 33, 215, 102, 468, 123, 468, 473, 30, 292, 215, 30, 213, 443, 473, 215, 234, 279, 279, 279, 279, 265, 443, 206, 66, 313, 34, 30, 206, 30, 51, 15, 206, 41, 434, 41, 398, 67, 30, 301, 67, 36, 3, 285, 437, 136, 136, 22, 136, 145, 365, 323, 323, 145, 136, 22, 453, 99, 323, 353, 9, 258, 323, 231, 128, 231, 382, 150, 420, 39, 94, 29, 29, 353, 22, 22, 347, 353, 39, 29, 22, 183, 8, 284, 355, 388, 284, 60, 64, 99, 60, 64, 150, 95, 150, 364, 150, 95, 150, 6, 236, 383, 544, 81, 206, 388, 206, 58, 159, 99, 231, 228, 363, 363, 121, 99, 121, 121, 99, 422, 544, 273, 173, 121, 427, 102, 121, 235, 284, 179, 25, 197, 25, 179, 511, 70, 368, 70, 25, 388, 123, 368, 159, 213, 410, 159, 236, 127, 159, 21, 373, 184, 424, 327, 250, 176, 176, 175, 284, 316, 176, 284, 327, 111, 250, 284, 175, 175, 264, 111, 176, 219, 111, 427, 427, 176, 284, 427, 353, 428, 55, 184, 493, 158, 136, 99, 287, 264, 334, 264, 213, 213, 292, 481, 93, 264, 292, 295, 295, 6, 367, 279, 173, 308, 285, 158, 308, 335, 299, 137, 137, 572, 41, 137, 137, 41, 94, 335, 220, 36, 224, 420, 36, 265, 265, 91, 91, 71, 123, 264, 91, 91, 123, 107, 30, 22, 292, 35, 241, 356, 298, 14, 298, 441, 35, 121, 71, 63, 130, 63, 488, 363, 71, 63, 307, 194, 71, 71, 220, 121, 125, 71, 220, 71, 71, 71, 71, 235, 265, 353, 128, 155, 128, 420, 400, 130, 173, 183, 183, 184, 130, 173, 183, 13, 183, 130, 130, 183, 183, 353, 353, 183, 242, 183, 183, 306, 324, 324, 321, 306, 321, 6, 6, 128, 306, 242, 242, 306, 183, 183, 6, 183, 321, 486, 183, 164, 30, 78, 138, 158, 138, 34, 206, 362, 55, 70, 67, 21, 375, 136, 298, 81, 298, 298, 298, 230, 121, 30, 230, 311, 240, 311, 311, 158, 204, 136, 136, 184, 136, 264, 311, 311, 312, 312, 72, 311, 175, 264, 91, 175, 264, 121, 461, 312, 312, 238, 475, 350, 512, 350, 312, 313, 350, 312, 366, 294, 30, 253, 253, 253, 388, 158, 388, 22, 388, 22, 388, 103, 321, 321, 253, 7, 437, 103, 114, 242, 114, 114, 242, 114, 114, 242, 242, 242, 306, 242, 114, 7, 353, 335, 27, 241, 299, 312, 364, 506, 409, 94, 462, 230, 462, 243, 230, 175, 175, 462, 461, 230, 428, 426, 175, 175, 165, 175, 175, 372, 183, 572, 102, 85, 102, 538, 206, 376, 85, 85, 284, 85, 85, 284, 398, 83, 160, 265, 308, 398, 310, 583, 289, 279, 273, 285, 490, 490, 211, 292, 292, 158, 398, 30, 220, 169, 368, 368, 368, 169, 159, 368, 93, 368, 368, 93, 169, 368, 368, 443, 368, 298, 443, 368, 298, 538, 345, 345, 311, 178, 54, 311, 215, 178, 175, 222, 264, 475, 264, 264, 475, 478, 289, 63, 236, 63, 299, 231, 296, 397, 299, 158, 36, 164, 164, 21, 492, 21, 164, 21, 164, 403, 26, 26, 588, 179, 234, 169, 465, 295, 67, 41, 353, 295, 538, 161, 185, 306, 323, 68, 420, 323, 82, 241, 241, 36, 53, 493, 301, 292, 241, 250, 63, 63, 103, 442, 353, 185, 353, 321, 353, 185, 353, 353, 185, 409, 353, 589, 34, 271, 271, 34, 86, 34, 34, 353, 353, 39, 414, 4, 95, 95, 4, 225, 95, 4, 121, 30, 552, 136, 159, 159, 514, 159, 159, 54, 514, 206, 136, 206, 159, 74, 235, 235, 312, 54, 312, 42, 156, 422, 629, 54, 465, 265, 165, 250, 35, 165, 175, 659, 175, 175, 8, 8, 8, 8, 206, 206, 206, 50, 435, 206, 432, 230, 230, 234, 230, 94, 299, 299, 285, 184, 41, 93, 299, 299, 285, 41, 285, 158, 285, 206, 299, 41, 36, 396, 364, 364, 120, 396, 514, 91, 382, 538, 807, 717, 22, 93, 412, 54, 215, 54, 298, 308, 148, 298, 148, 298, 308, 102, 656, 6, 148, 745, 128, 298, 64, 407, 273, 41, 172, 64, 234, 250, 398, 181, 445, 95, 236, 441, 477, 504, 102, 196, 137, 364, 60, 453, 137, 364, 367, 334, 364, 299, 196, 397, 630, 589, 589, 196, 646, 337, 235, 128, 128, 343, 289, 235, 324, 427, 324, 58, 215, 215, 461, 425, 461, 387, 440, 285, 440, 440, 285, 387, 632, 325, 325, 440, 461, 425, 425, 387, 627, 191, 285, 440, 308, 55, 219, 280, 308, 265, 538, 183, 121, 30, 236, 206, 30, 455, 236, 30, 30, 705, 83, 228, 280, 468, 132, 8, 132, 132, 128, 409, 173, 353, 132, 409, 35, 128, 450, 137, 398, 67, 432, 423, 235, 235, 388, 306, 93, 93, 452, 300, 190, 13, 452, 388, 30, 452, 13, 30, 13, 30, 306, 362, 234, 721, 635, 809, 784, 67, 498, 498, 67, 353, 635, 67, 183, 159, 445, 285, 183, 53, 183, 445, 265, 432, 57, 420, 432, 420, 477, 327, 55, 60, 105, 183, 218, 104, 104, 475, 239, 582, 151, 239, 104, 732, 41, 26, 784, 86, 300, 215, 36, 64, 86, 86, 675, 294, 64, 86, 528, 550, 493, 565, 298, 230, 312, 295, 538, 298, 295, 230, 54, 374, 516, 441, 54, 54, 323, 401, 401, 382, 159, 837, 159, 54, 401, 592, 159, 401, 417, 610, 264, 150, 323, 452, 185, 323, 323, 185, 403, 185, 423, 165, 425, 219, 407, 270, 231, 99, 93, 231, 631, 756, 71, 364, 434, 213, 86, 102, 434, 102, 86, 23, 71, 335, 164, 323, 409, 381, 4, 124, 41, 424, 206, 41, 124, 41, 41, 703, 635, 124, 493, 41, 41, 487, 492, 124, 175, 124, 261, 600, 488, 261, 488, 261, 206, 677, 261, 308, 723, 908, 704, 691, 723, 488, 488, 441, 136, 476, 312, 136, 550, 572, 728, 550, 22, 312, 312, 22, 55, 413, 183, 280, 593, 191, 36, 36, 427, 36, 695, 592, 19, 544, 13, 468, 13, 544, 72, 437, 321, 266, 461, 266, 441, 230, 409, 93, 521, 521, 345, 235, 22, 142, 150, 102, 569, 235, 264, 91, 521, 264, 7, 102, 7, 498, 521, 235, 537, 235, 6, 241, 420, 420, 631, 41, 527, 103, 67, 337, 62, 264, 527, 131, 67, 174, 263, 264, 36, 36, 263, 581, 253, 465, 160, 286, 91, 160, 55, 4, 4, 631, 631, 608, 365, 465, 294, 427, 427, 335, 669, 669, 129, 93, 93, 93, 93, 74, 66, 758, 504, 347, 130, 505, 504, 143, 505, 550, 222, 13, 352, 529, 291, 538, 50, 68, 269, 130, 295, 130, 511, 295, 295, 130, 486, 132, 61, 206, 185, 368, 669, 22, 175, 492, 207, 373, 452, 432, 327, 89, 550, 496, 611, 527, 89, 527, 496, 550, 516, 516, 91, 136, 538, 264, 264, 124, 264, 264, 264, 264, 264, 535, 264, 150, 285, 398, 285, 582, 398, 475, 81, 694, 694, 64, 81, 694, 234, 607, 723, 513, 234, 64, 581, 64, 124, 64, 607, 234, 723, 717, 367, 64, 513, 607, 488, 183, 488, 450, 183, 550, 286, 183, 363, 286, 414, 67, 449, 449, 366, 215, 235, 95, 295, 295, 41, 335, 21, 445, 225, 21, 295, 372, 749, 461, 53, 481, 397, 427, 427, 427, 714, 481, 714, 427, 717, 165, 245, 486, 415, 245, 415, 486, 274, 415, 441, 456, 300, 548, 300, 422, 422, 757, 11, 74, 430, 430, 136, 409, 430, 749, 191, 819, 592, 136, 364, 465, 231, 231, 918, 160, 589, 160, 160, 465, 465, 231, 157, 538, 538, 259, 538, 326, 22, 22, 22, 179, 22, 22, 550, 179, 287, 287, 417, 327, 498, 498, 287, 488, 327, 538, 488, 583, 488, 287, 335, 287, 335, 287, 41, 287, 335, 287, 327, 441, 335, 287, 488, 538, 327, 498, 8, 8, 374, 8, 64, 427, 8, 374, 417, 760, 409, 373, 160, 423, 206, 160, 106, 499, 160, 271, 235, 160, 590, 353, 695, 478, 619, 590, 353, 13, 63, 189, 420, 605, 427, 643, 121, 280, 415, 121, 415, 595, 417, 121, 398, 55, 330, 463, 463, 123, 353, 330, 582, 309, 582, 582, 405, 330, 550, 405, 582, 353, 309, 308, 60, 353, 7, 60, 71, 353, 189, 183, 183, 183, 582, 755, 189, 437, 287, 189, 183, 668, 481, 384, 384, 481, 481, 481, 477, 582, 582, 499, 650, 481, 121, 461, 231, 36, 235, 36, 413, 235, 209, 36, 689, 114, 353, 353, 235, 592, 36, 353, 413, 209, 70, 308, 70, 699, 308, 70, 213, 292, 86, 689, 465, 55, 508, 128, 452, 29, 41, 681, 573, 352, 21, 21, 648, 648, 69, 509, 409, 21, 264, 21, 509, 514, 514, 409, 21, 264, 443, 443, 427, 160, 433, 663, 433, 231, 646, 185, 482, 646, 433, 13, 398, 172, 234, 42, 491, 172, 234, 234, 832, 775, 172, 196, 335, 822, 461, 298, 461, 364, 1120, 537, 169, 169, 364, 694, 219, 612, 231, 740, 42, 235, 321, 279, 960, 279, 353, 492, 159, 572, 321, 159, 287, 353, 287, 287, 206, 206, 321, 287, 159, 321, 492, 159, 55, 572, 600, 270, 492, 784, 173, 91, 91, 443, 443, 582, 261, 497, 572, 91, 555, 352, 206, 261, 555, 285, 91, 555, 497, 83, 91, 619, 353, 488, 112, 4, 592, 295, 295, 488, 235, 231, 769, 568, 581, 671, 451, 451, 483, 299, 1011, 432, 422, 207, 106, 701, 508, 555, 508, 555, 125, 870, 555, 589, 508, 125, 749, 482, 125, 125, 130, 544, 643, 643, 544, 488, 22, 643, 130, 335, 544, 22, 130, 544, 544, 488, 426, 426, 4, 180, 4, 695, 35, 54, 433, 500, 592, 433, 262, 94, 401, 401, 106, 216, 216, 106, 521, 102, 462, 518, 271, 475, 365, 193, 648, 206, 424, 206, 193, 206, 206, 424, 299, 590, 590, 364, 621, 67, 538, 488, 567, 51, 51, 513, 194, 81, 488, 486, 289, 567, 563, 749, 563, 338, 338, 502, 563, 822, 338, 563, 338, 502, 201, 230, 201, 533, 445, 175, 201, 175, 13, 85, 960, 103, 85, 175, 30, 445, 445, 175, 573, 196, 877, 287, 356, 678, 235, 489, 312, 572, 264, 717, 138, 295, 6, 295, 523, 55, 165, 165, 295, 138, 663, 6, 295, 6, 353, 138, 6, 138, 169, 129, 784, 12, 129, 194, 605, 784, 445, 234, 627, 563, 689, 627, 647, 570, 627, 570, 647, 206, 234, 215, 234, 816, 627, 816, 234, 627, 215, 234, 627, 264, 427, 427, 30, 424, 161, 161, 916, 740, 180, 616, 481, 514, 383, 265, 481, 164, 650, 121, 582, 689, 420, 669, 589, 420, 788, 549, 165, 734, 280, 224, 146, 681, 788, 184, 398, 784, 4, 398, 417, 417, 398, 636, 784, 417, 81, 398, 417, 81, 185, 827, 420, 241, 420, 41, 185, 185, 718, 241, 101, 185, 185, 241, 241, 241, 241, 241, 185, 324, 420, 420, 1011, 420, 827, 241, 184, 563, 241, 183, 285, 529, 285, 808, 822, 891, 822, 488, 285, 486, 619, 55, 869, 39, 567, 39, 289, 203, 158, 289, 710, 818, 158, 818, 355, 29, 409, 203, 308, 648, 792, 308, 308, 91, 308, 6, 592, 792, 106, 106, 308, 41, 178, 91, 751, 91, 259, 734, 166, 36, 327, 166, 230, 205, 205, 172, 128, 230, 432, 623, 838, 623, 432, 278, 432, 42, 916, 432, 694, 623, 352, 452, 93, 314, 93, 93, 641, 88, 970, 914, 230, 61, 159, 270, 159, 493, 159, 755, 159, 409, 30, 30, 836, 128, 241, 99, 102, 984, 538, 102, 102, 273, 639, 838, 102, 102, 136, 637, 508, 627, 285, 465, 327, 327, 21, 749, 327, 749, 21, 845, 21, 21, 409, 749, 1367, 806, 616, 714, 253, 616, 714, 714, 112, 375, 21, 112, 375, 375, 51, 51, 51, 51, 393, 206, 870, 713, 193, 802, 21, 1061, 42, 382, 42, 543, 876, 42, 876, 382, 696, 543, 635, 490, 353, 353, 417, 64, 1257, 271, 64, 377, 127, 127, 537, 417, 905, 353, 538, 465, 605, 876, 427, 324, 514, 852, 427, 53, 427, 557, 173, 173, 7, 1274, 563, 31, 31, 31, 745, 392, 289, 230, 230, 230, 91, 218, 327, 420, 420, 128, 901, 552, 420, 230, 608, 552, 476, 347, 476, 231, 159, 137, 716, 648, 716, 627, 740, 718, 679, 679, 6, 718, 740, 6, 189, 679, 125, 159, 757, 1191, 409, 175, 250, 409, 67, 324, 681, 605, 550, 398, 550, 931, 478, 174, 21, 316, 91, 316, 654, 409, 425, 425, 699, 61, 699, 321, 698, 321, 698, 61, 425, 699, 321, 409, 699, 299, 335, 321, 335, 61, 698, 699, 654, 698, 299, 425, 231, 14, 121, 515, 121, 14, 165, 81, 409, 189, 81, 373, 465, 463, 1055, 507, 81, 81, 189, 1246, 321, 409, 886, 104, 842, 689, 300, 740, 380, 656, 656, 832, 656, 380, 300, 300, 206, 187, 175, 142, 465, 206, 271, 468, 215, 560, 83, 215, 83, 215, 215, 83, 175, 215, 83, 83, 111, 206, 756, 559, 756, 1367, 206, 559, 1015, 559, 559, 946, 1015, 548, 559, 756, 1043, 756, 698, 159, 414, 308, 458, 997, 663, 663, 347, 39, 755, 838, 323, 755, 323, 159, 159, 717, 159, 21, 41, 128, 516, 159, 717, 71, 870, 755, 159, 740, 717, 374, 516, 740, 51, 148, 335, 148, 335, 791, 120, 364, 335, 335, 51, 120, 251, 538, 251, 971, 1395, 538, 78, 178, 538, 538, 918, 129, 918, 129, 538, 538, 656, 129, 538, 538, 129, 538, 1051, 538, 128, 838, 931, 998, 823, 1095, 334, 870, 334, 367, 550, 1061, 498, 745, 832, 498, 745, 716, 498, 498, 128, 997, 832, 716, 832, 130, 642, 616, 497, 432, 432, 432, 432, 642, 159, 432, 46, 230, 788, 160, 230, 478, 46, 693, 103, 920, 230, 589, 643, 160, 616, 432, 165, 165, 583, 592, 838, 784, 583, 710, 6, 583, 583, 6, 35, 230, 838, 592, 710, 6, 589, 230, 838, 30, 592, 583, 6, 583, 6, 6, 583, 30, 30, 6, 375, 375, 99, 36, 1158, 425, 662, 417, 681, 364, 375, 1025, 538, 822, 669, 893, 538, 538, 450, 409, 632, 527, 632, 563, 632, 527, 550, 71, 698, 550, 39, 550, 514, 537, 514, 537, 111, 41, 173, 592, 173, 648, 173, 173, 173, 1011, 514, 173, 173, 514, 166, 648, 355, 161, 166, 648, 497, 327, 327, 550, 650, 21, 425, 605, 555, 103, 425, 605, 842, 836, 1011, 636, 138, 756, 836, 756, 756, 353, 1011, 636, 636, 1158, 741, 741, 842, 756, 741, 1011, 677, 1011, 770, 366, 306, 488, 920, 920, 665, 775, 502, 500, 775, 775, 648, 364, 833, 207, 13, 93, 500, 364, 500, 665, 500, 93, 295, 183, 1293, 313, 272, 313, 279, 303, 93, 516, 93, 1013, 381, 6, 93, 93, 303, 259, 643, 168, 673, 230, 1261, 230, 230, 673, 1060, 1079, 1079, 550, 741, 741, 590, 527, 741, 741, 442, 741, 442, 848, 741, 590, 925, 219, 527, 925, 335, 442, 590, 239, 590, 590, 590, 239, 527, 239, 1033, 230, 734, 241, 741, 230, 549, 548, 1015, 1015, 32, 36, 433, 465, 724, 465, 73, 73, 73, 465, 808, 73, 592, 1430, 250, 154, 154, 250, 538, 353, 353, 353, 353, 353, 175, 194, 206, 538, 632, 1163, 960, 175, 175, 538, 452, 632, 1163, 175, 538, 960, 194, 175, 194, 632, 960, 632, 94, 632, 461, 960, 1163, 1163, 461, 632, 960, 755, 707, 105, 382, 625, 382, 382, 784, 707, 871, 559, 387, 387, 871, 784, 559, 784, 88, 36, 570, 314, 1028, 975, 335, 335, 398, 573, 573, 573, 21, 215, 562, 738, 612, 424, 21, 103, 788, 870, 912, 23, 186, 757, 73, 818, 23, 73, 563, 952, 262, 563, 137, 262, 1022, 952, 137, 1273, 442, 952, 604, 137, 308, 384, 913, 235, 325, 695, 398, 95, 668, 776, 713, 309, 691, 22, 10, 364, 682, 682, 578, 481, 1252, 1072, 1252, 825, 578, 825, 1072, 1149, 592, 273, 387, 273, 427, 155, 1204, 50, 452, 50, 1142, 50, 367, 452, 1142, 611, 367, 50, 50, 367, 50, 1675, 99, 367, 50, 1501, 1099, 830, 681, 689, 917, 1089, 453, 425, 235, 918, 538, 550, 335, 161, 387, 859, 324, 21, 838, 859, 1123, 21, 723, 21, 335, 335, 206, 21, 364, 1426, 21, 838, 838, 335, 364, 21, 21, 859, 920, 838, 838, 397, 81, 639, 397, 397, 588, 933, 933, 784, 222, 830, 36, 36, 222, 1251, 266, 36, 146, 266, 366, 581, 605, 366, 22, 966, 681, 681, 433, 730, 1013, 550, 21, 21, 938, 488, 516, 21, 21, 656, 420, 323, 323, 323, 327, 323, 918, 581, 581, 830, 361, 830, 364, 259, 364, 496, 496, 364, 691, 705, 691, 475, 427, 1145, 600, 179, 427, 527, 749, 869, 689, 335, 347, 220, 298, 689, 1426, 183, 554, 55, 832, 550, 550, 165, 770, 957, 67, 1386, 219, 683, 683, 355, 683, 355, 355, 738, 355, 842, 931, 266, 325, 349, 256, 1113, 256, 423, 960, 554, 554, 325, 554, 508, 22, 142, 22, 508, 916, 767, 55, 1529, 767, 55, 1286, 93, 972, 550, 931, 1286, 1286, 972, 93, 1286, 1392, 890, 93, 1286, 93, 1286, 972, 374, 931, 890, 808, 779, 975, 975, 175, 173, 4, 681, 383, 1367, 173, 383, 1367, 383, 173, 175, 69, 238, 146, 238, 36, 148, 888, 238, 173, 238, 148, 238, 888, 185, 925, 925, 797, 925, 815, 925, 469, 784, 289, 784, 925, 797, 925, 925, 1093, 925, 925, 925, 1163, 797, 797, 815, 925, 1093, 784, 636, 663, 925, 187, 922, 316, 1380, 709, 916, 916, 187, 355, 948, 916, 187, 916, 916, 948, 948, 916, 355, 316, 316, 334, 300, 1461, 36, 583, 1179, 699, 235, 858, 583, 699, 858, 699, 1189, 1256, 1189, 699, 797, 699, 699, 699, 699, 427, 488, 427, 488, 175, 815, 656, 656, 150, 322, 465, 322, 870, 465, 1099, 582, 665, 767, 749, 635, 749, 600, 1448, 36, 502, 235, 502, 355, 502, 355, 355, 355, 172, 355, 355, 95, 866, 425, 393, 1165, 42, 42, 42, 393, 939, 909, 909, 836, 552, 424, 1333, 852, 897, 1426, 1333, 1446, 1426, 997, 1011, 852, 1198, 55, 32, 239, 588, 681, 681, 239, 1401, 32, 588, 239, 462, 286, 1260, 984, 1160, 960, 960, 486, 828, 462, 960, 1199, 581, 850, 663, 581, 751, 581, 581, 1571, 252, 252, 1283, 264, 430, 264, 430, 430, 842, 252, 745, 21, 307, 681, 1592, 488, 857, 857, 1161, 857, 857, 857, 138, 374, 374, 1196, 374, 1903, 1782, 1626, 414, 112, 1477, 1040, 356, 775, 414, 414, 112, 356, 775, 435, 338, 1066, 689, 689, 1501, 689, 1249, 205, 689, 765, 220, 308, 917, 308, 308, 220, 327, 387, 838, 917, 917, 917, 220, 662, 308, 220, 387, 387, 220, 220, 308, 308, 308, 387, 1009, 1745, 822, 279, 554, 1129, 543, 383, 870, 1425, 241, 870, 241, 383, 716, 592, 21, 21, 592, 425, 550, 550, 550, 427, 230, 57, 483, 784, 860, 57, 308, 57, 486, 870, 447, 486, 433, 433, 870, 433, 997, 486, 443, 433, 433, 997, 486, 1292, 47, 708, 81, 895, 394, 81, 935, 81, 81, 81, 374, 986, 916, 1103, 1095, 465, 495, 916, 667, 1745, 518, 220, 1338, 220, 734, 1294, 741, 166, 828, 741, 741, 1165, 1371, 1371, 471, 1371, 647, 1142, 1878, 1878, 1371, 1371, 822, 66, 327, 158, 427, 427, 465, 465, 676, 676, 30, 30, 676, 676, 893, 1592, 93, 455, 308, 582, 695, 582, 629, 582, 85, 1179, 85, 85, 1592, 1179, 280, 1027, 681, 398, 1027, 398, 295, 784, 740, 509, 425, 968, 509, 46, 833, 842, 401, 184, 401, 464, 6, 1501, 1501, 550, 538, 883, 538, 883, 883, 883, 1129, 550, 550, 333, 689, 948, 21, 21, 241, 2557, 2094, 273, 308, 58, 863, 893, 1086, 409, 136, 1086, 592, 592, 830, 830, 883, 830, 277, 68, 689, 902, 277, 453, 507, 129, 689, 630, 664, 550, 128, 1626, 1626, 128, 902, 312, 589, 755, 755, 589, 755, 407, 1782, 589, 784, 1516, 1118, 407, 407, 1447, 589, 235, 755, 1191, 235, 235, 407, 128, 589, 1118, 21, 383, 1331, 691, 481, 383, 1129, 1129, 1261, 1104, 1378, 1129, 784, 1129, 1261, 1129, 947, 1129, 784, 784, 1129, 1129, 35, 1104, 35, 866, 1129, 1129, 64, 481, 730, 1260, 481, 970, 481, 481, 481, 481, 863, 481, 681, 699, 863, 486, 681, 481, 481, 55, 55, 235, 1364, 944, 632, 822, 401, 822, 952, 822, 822, 99, 550, 2240, 550, 70, 891, 860, 860, 550, 550, 916, 1176, 1530, 425, 1530, 916, 628, 1583, 916, 628, 916, 916, 628, 628, 425, 916, 1062, 1265, 916, 916, 916, 280, 461, 916, 916, 1583, 628, 1062, 916, 916, 677, 1297, 924, 1260, 83, 1260, 482, 433, 234, 462, 323, 1656, 997, 323, 323, 931, 838, 931, 1933, 1391, 367, 323, 931, 1391, 1391, 103, 1116, 1116, 1116, 769, 1195, 1218, 312, 791, 312, 741, 791, 997, 312, 334, 334, 312, 287, 287, 633, 1397, 1426, 605, 1431, 327, 592, 705, 1194, 592, 1097, 1118, 1503, 1267, 1267, 1267, 618, 1229, 734, 1089, 785, 1089, 1129, 1148, 1148, 1089, 915, 1148, 1129, 1148, 1011, 1011, 1229, 871, 1560, 1560, 1560, 563, 1537, 1009, 1560, 632, 985, 592, 1308, 592, 882, 145, 145, 397, 837, 383, 592, 592, 832, 36, 2714, 2107, 1588, 1347, 36, 36, 1443, 1453, 334, 2230, 1588, 1169, 650, 1169, 2107, 425, 425, 891, 891, 425, 2532, 679, 274, 274, 274, 325, 274, 1297, 194, 1297, 627, 314, 917, 314, 314, 1501, 414, 1490, 1036, 592, 1036, 1025, 901, 1218, 1025, 901, 280, 592, 592, 901, 1461, 159, 159, 159, 2076, 1066, 1176, 1176, 516, 327, 516, 1179, 1176, 899, 1176, 1176, 323, 1187, 1229, 663, 1229, 504, 1229, 916, 1229, 916, 1661, 41, 36, 278, 1027, 648, 648, 648, 1626, 648, 646, 1179, 1580, 1061, 1514, 1008, 1741, 2076, 1514, 1008, 952, 1089, 427, 952, 427, 1083, 425, 427, 1089, 1083, 425, 427, 425, 230, 920, 1678, 920, 1678, 189, 189, 953, 189, 133, 189, 1075, 189, 189, 133, 1264, 725, 189, 1629, 189, 808, 230, 230, 2179, 770, 230, 770, 230, 21, 21, 784, 1118, 230, 230, 230, 770, 1118, 986, 808, 916, 30, 327, 918, 679, 414, 916, 1165, 1355, 916, 755, 733, 433, 1490, 433, 433, 433, 605, 433, 433, 433, 1446, 679, 206, 433, 21, 2452, 206, 206, 433, 1894, 206, 822, 206, 2073, 206, 206, 21, 822, 21, 206, 206, 21, 383, 1513, 375, 1347, 432, 1589, 172, 954, 242, 1256, 1256, 1248, 1256, 1256, 1248, 1248, 1256, 842, 13, 592, 13, 842, 1291, 592, 21, 175, 13, 592, 13, 13, 1426, 13, 1541, 445, 808, 808, 863, 647, 219, 1592, 1029, 1225, 917, 1963, 1129, 555, 1313, 550, 660, 550, 220, 660, 552, 663, 220, 533, 220, 383, 550, 1278, 1495, 636, 842, 1036, 425, 842, 425, 1537, 1278, 842, 554, 1508, 636, 554, 301, 842, 792, 1392, 1021, 284, 1172, 997, 1021, 103, 1316, 308, 1210, 848, 848, 1089, 1089, 848, 848, 67, 1029, 827, 1029, 2078, 827, 1312, 1029, 827, 590, 872, 1312, 427, 67, 67, 67, 67, 872, 827, 872, 2126, 1436, 26, 2126, 67, 1072, 2126, 1610, 872, 1620, 883, 883, 1397, 1189, 555, 555, 563, 1189, 555, 640, 555, 640, 1089, 1089, 610, 610, 1585, 610, 1355, 610, 1015, 616, 925, 1015, 482, 230, 707, 231, 888, 1355, 589, 1379, 151, 931, 1486, 1486, 393, 235, 960, 590, 235, 960, 422, 142, 285, 285, 327, 327, 442, 2009, 822, 445, 822, 567, 888, 2611, 1537, 323, 55, 1537, 323, 888, 2611, 323, 1537, 323, 58, 445, 593, 2045, 593, 58, 47, 770, 842, 47, 47, 842, 842, 648, 2557, 173, 689, 2291, 1446, 2085, 2557, 2557, 2291, 1780, 1535, 2291, 2391, 808, 691, 1295, 1165, 983, 948, 2000, 948, 983, 983, 2225, 2000, 983, 983, 705, 948, 2000, 1795, 1592, 478, 592, 1795, 1795, 663, 478, 1790, 478, 592, 1592, 173, 901, 312, 4, 1606, 173, 838, 754, 754, 128, 550, 1166, 551, 1480, 550, 550, 1875, 1957, 1166, 902, 1875, 550, 550, 551, 2632, 551, 1875, 1875, 551, 2891, 2159, 2632, 3231, 551, 815, 150, 1654, 1059, 1059, 734, 770, 555, 1592, 555, 2059, 770, 770, 1803, 627, 627, 627, 2059, 931, 1272, 427, 1606, 1272, 1606, 1187, 1204, 397, 822, 21, 1645, 263, 263, 822, 263, 1645, 280, 263, 605, 1645, 2014, 21, 21, 1029, 263, 1916, 2291, 397, 397, 496, 270, 270, 1319, 264, 1638, 264, 986, 1278, 1397, 1278, 1191, 409, 1191, 740, 1191, 754, 754, 387, 63, 948, 666, 666, 1198, 548, 63, 1248, 285, 1248, 169, 1248, 1248, 285, 918, 224, 285, 1426, 1671, 514, 514, 717, 514, 51, 1521, 1745, 51, 605, 1191, 51, 128, 1191, 51, 51, 1521, 267, 513, 952, 966, 1671, 897, 51, 71, 592, 986, 986, 1121, 592, 280, 2000, 2000, 1165, 1165, 1165, 1818, 222, 1818, 1165, 1252, 506, 327, 443, 432, 1291, 1291, 2755, 1413, 520, 1318, 227, 1047, 828, 520, 347, 1364, 136, 136, 452, 457, 457, 132, 457, 488, 1087, 1013, 2225, 32, 1571, 2009, 483, 67, 483, 740, 740, 1013, 2854, 866, 32, 2861, 866, 887, 32, 2444, 740, 32, 32, 866, 2225, 866, 32, 1571, 2627, 32, 850, 1675, 569, 1158, 32, 1158, 1797, 2641, 1565, 1158, 569, 1797, 1158, 1797, 55, 1703, 42, 55, 2562, 675, 1703, 42, 55, 749, 488, 488, 347, 1206, 1286, 1286, 488, 488, 1206, 1286, 1206, 1286, 550, 550, 1790, 860, 550, 2452, 550, 550, 2765, 1089, 1633, 797, 2244, 1313, 194, 2129, 194, 194, 194, 818, 32, 194, 450, 1313, 2387, 194, 1227, 2387, 308, 2232, 526, 476, 278, 830, 830, 194, 830, 194, 278, 194, 714, 476, 830, 714, 830, 278, 830, 2532, 1218, 1759, 1446, 960, 1747, 187, 1446, 1759, 960, 105, 1446, 1446, 1271, 1446, 960, 960, 1218, 1446, 1446, 105, 1446, 960, 488, 1446, 427, 534, 842, 1969, 2460, 1969, 842, 842, 1969, 427, 941, 2160, 427, 230, 938, 2075, 1675, 1675, 895, 1675, 34, 129, 1811, 239, 749, 1957, 2271, 749, 1908, 129, 239, 239, 129, 129, 2271, 2426, 1355, 1756, 194, 1583, 194, 194, 1583, 194, 1355, 194, 1628, 2221, 1269, 2425, 1756, 1355, 1355, 1583, 1033, 427, 582, 30, 582, 582, 935, 1444, 1962, 915, 733, 915, 938, 1962, 767, 353, 1630, 1962, 1962, 563, 733, 563, 733, 353, 822, 1630, 740, 2076, 2076, 2076, 589, 589, 2636, 866, 589, 947, 1528, 125, 273, 1058, 1058, 1161, 1635, 1355, 1161, 1161, 1355, 1355, 650, 1206, 1206, 784, 784, 784, 784, 784, 412, 461, 412, 2240, 412, 679, 891, 461, 679, 679, 189, 189, 1933, 1651, 2515, 189, 1386, 538, 1386, 1386, 1187, 1386, 2423, 2601, 2285, 175, 175, 2331, 194, 3079, 384, 538, 2365, 2294, 538, 2166, 1841, 3326, 1256, 3923, 976, 85, 550, 550, 1295, 863, 863, 550, 1249, 550, 1759, 146, 1069, 920, 2633, 885, 885, 1514, 1489, 166, 1514, 2041, 885, 2456, 885, 2041, 1081, 1948, 362, 550, 94, 324, 2308, 94, 2386, 94, 550, 874, 1329, 1759, 2280, 1487, 493, 493, 2099, 2599, 1431, 1086, 1514, 1086, 2099, 1858, 368, 1330, 2599, 1858, 2846, 2846, 2907, 2846, 713, 713, 1854, 1123, 713, 713, 3010, 1123, 3010, 538, 713, 1123, 447, 822, 555, 2011, 493, 508, 2292, 555, 1736, 2135, 2704, 555, 2814, 555, 2000, 555, 555, 822, 914, 327, 679, 327, 648, 537, 2263, 931, 1496, 537, 1296, 1745, 1592, 1658, 1795, 650, 1592, 1745, 1745, 1658, 1592, 1745, 1592, 1745, 1658, 1338, 2124, 1592, 1745, 1745, 1745, 837, 1726, 2897, 1118, 1118, 230, 1118, 1118, 1118, 1388, 1748, 514, 128, 1165, 931, 514, 2974, 2041, 2387, 2041, 979, 185, 36, 1269, 550, 173, 812, 36, 1165, 2676, 2562, 1473, 2885, 1982, 1578, 1578, 383, 383, 2360, 383, 1578, 2360, 1584, 1982, 1578, 1578, 1578, 2019, 1036, 355, 724, 2023, 205, 303, 355, 1036, 1966, 355, 1036, 401, 401, 401, 830, 401, 849, 578, 401, 849, 849, 578, 1776, 1123, 552, 2632, 808, 1446, 1120, 373, 1529, 1483, 1057, 893, 1284, 1430, 1529, 1529, 2632, 1352, 2063, 1606, 1352, 1606, 2291, 3079, 2291, 1529, 506, 838, 1606, 1606, 1352, 1529, 1529, 1483, 1529, 1606, 1529, 259, 902, 259, 902, 612, 612, 284, 398, 2991, 1534, 1118, 1118, 1118, 1118, 1118, 734, 284, 2224, 398, 734, 284, 734, 398, 3031, 398, 734, 1707, 2643, 1344, 1477, 475, 1818, 194, 1894, 691, 1528, 1184, 1207, 1501, 6, 2069, 871, 2069, 3548, 1443, 2069, 2685, 3265, 1350, 3265, 2069, 2069, 128, 1313, 128, 663, 414, 1313, 414, 2000, 128, 2000, 663, 1313, 699, 1797, 550, 327, 550, 1526, 699, 327, 1797, 1526, 550, 550, 327, 550, 1426, 1426, 1426, 2285, 1123, 890, 728, 1707, 728, 728, 327, 253, 1187, 1281, 1364, 1571, 2170, 755, 3232, 925, 1496, 2170, 2170, 1125, 443, 902, 902, 925, 755, 2078, 2457, 902, 2059, 2170, 1643, 1129, 902, 902, 1643, 1129, 606, 36, 103, 338, 338, 1089, 338, 338, 338, 1089, 338, 36, 340, 1206, 1176, 2041, 833, 1854, 1916, 1916, 1501, 2132, 1736, 3065, 367, 1934, 833, 833, 833, 2041, 3017, 2147, 818, 1397, 828, 2147, 398, 828, 818, 1158, 818, 689, 327, 36, 1745, 2132, 582, 1475, 189, 582, 2132, 1191, 582, 2132, 1176, 1176, 516, 2610, 2230, 2230, 64, 1501, 537, 1501, 173, 2230, 2988, 1501, 2694, 2694, 537, 537, 173, 173, 1501, 537, 64, 173, 173, 64, 2230, 537, 2230, 537, 2230, 2230, 2069, 3142, 1645, 689, 1165, 1165, 1963, 514, 488, 1963, 1145, 235, 1145, 1078, 1145, 231, 2405, 552, 21, 57, 57, 57, 1297, 1455, 1988, 2310, 1885, 2854, 2014, 734, 1705, 734, 2854, 734, 677, 1988, 1660, 734, 677, 734, 677, 677, 734, 2854, 1355, 677, 1397, 2947, 2386, 1698, 128, 1698, 3028, 2386, 2437, 2947, 2386, 2643, 2386, 2804, 1188, 335, 746, 1187, 1187, 861, 2519, 1917, 2842, 1917, 675, 1308, 234, 1917, 314, 314, 2339, 2339, 2592, 2576, 902, 916, 2339, 916, 2339, 916, 2339, 916, 1089, 1089, 2644, 1221, 1221, 2446, 308, 308, 2225, 2225, 3192, 2225, 555, 1592, 1592, 555, 893, 555, 550, 770, 3622, 2291, 2291, 3419, 465, 250, 2842, 2291, 2291, 2291, 935, 160, 1271, 308, 325, 935, 1799, 1799, 1891, 2227, 1799, 1598, 112, 1415, 1840, 2014, 1822, 2014, 677, 1822, 1415, 1415, 1822, 2014, 2386, 2159, 1822, 1415, 1822, 179, 1976, 1033, 179, 1840, 2014, 1415, 1970, 1970, 1501, 563, 563, 563, 462, 563, 1970, 1158, 563, 563, 1541, 1238, 383, 235, 1158, 383, 1278, 383, 1898, 2938, 21, 2938, 1313, 2201, 2059, 423, 2059, 1313, 872, 1313, 2044, 89, 173, 3327, 1660, 2044, 1623, 173, 1114, 1114, 1592, 1868, 1651, 1811, 383, 3469, 1811, 1651, 869, 383, 383, 1651, 1651, 3223, 2166, 3469, 767, 383, 1811, 767, 2323, 3355, 1457, 3341, 2640, 2976, 2323, 3341, 2323, 2640, 103, 103, 1161, 1080, 2429, 370, 2018, 2854, 2429, 2166, 2429, 2094, 2207, 871, 1963, 1963, 2023, 2023, 2336, 663, 2893, 1580, 691, 663, 705, 2046, 2599, 409, 2295, 1118, 2494, 1118, 1950, 549, 2494, 2453, 2046, 2494, 2453, 2046, 2453, 2046, 409, 1118, 4952, 2291, 2225, 1894, 1423, 2498, 567, 4129, 1475, 1501, 795, 463, 2084, 828, 828, 232, 828, 232, 232, 1818, 1818, 666, 463, 232, 220, 220, 2162, 2162, 833, 4336, 913, 35, 913, 21, 2927, 886, 3037, 383, 886, 876, 1747, 383, 916, 916, 916, 2927, 916, 1747, 837, 1894, 717, 423, 481, 1894, 1059, 2262, 3206, 4700, 1059, 3304, 2262, 871, 1831, 871, 3304, 1059, 1158, 1934, 1158, 756, 1511, 41, 978, 1934, 2603, 720, 41, 756, 41, 325, 2611, 1158, 173, 1123, 1934, 1934, 1511, 2045, 2045, 2045, 1423, 3206, 3691, 2512, 3206, 2512, 2000, 1811, 2504, 2504, 2611, 2437, 2437, 2437, 1455, 893, 150, 2665, 1966, 605, 398, 2331, 1177, 516, 1962, 4241, 94, 1252, 760, 1292, 1962, 1373, 2000, 1990, 3684, 42, 1868, 3779, 1811, 1811, 2041, 3010, 5436, 1780, 2041, 1868, 1811, 1780, 1811, 1868, 1811, 2041, 1868, 1811, 5627, 4274, 1811, 1868, 4602, 1811, 1811, 1474, 2665, 235, 1474, 2665
18、14、61、46、14、22、20、40、48、1、29、40、43、46、18、8、20、2、61、26、13、29、36、19、58、5、58、0、54、56、24、14、5、67、39、31、25、29、24、19、14、56、49、49、63、30、4、39、2、1、20、19、61、4、54、70、25、52、9、26、55、69、27、68、75、19、64、57、45、3、37、31、100、41、25、41、53、23、9、31、26、30、30、46、90、50、13、90、77、61、31、54、54、3、21、21、66、21、11、23、11、29、21、7、1、27、4、34、17、85、69、17、75、93、57、0、53、71、88、119、88、90、22、0、58、41、22、96、26、79、118、19、3、81、72、50、0、32、79、28、25、12、25、29、3、37、30、30、41、84、32、31、61、32、61、7、56、54、39、33、66、29、3、14、75、75、78、84、75、84、25、54、25、25、107、78、27、73、0、49、96、53、50、21、10、73、58、65、27、3、27、18、54、45、69、29、3、65、31、71、76、56、54、76、54、13、5、18、142、17、3、37、114、41、25、56、0、23、3、41、22、22、31、18、48、31、58、37、75、88、3、56、1、95、19、73、52、52、4、75、26、1、25、10、1、70、31、12、10、54、46、11、74、84、74、8、58、23、74、8、36、11、16、94、76、14、57、65、8、22、10、36、96、62、103、6、75、103、58、10、15、41、75、125、58、15、10、34、29、34、4、16、29、18、18、28、71、28、43、77、18、41、41、41、62、29、96、15、106、43、15、3、43、61、3、18、103、77、29、103、19、58、84、58、1、146、32、3、70、52、54、29、70、69、124、62、1、26、38、26、3、16、26、5、51、120、41、16、1 1、43、34、34、29、37、56、29、96、86、54、25、84、50、34、34、93、84、96、29、29、50、50、6、1、105、78、15、37、19、50、71、36、6、54、8、28、54、75、75、16、75、131、5、25、16、69、17、69、6、96、53、96、41、119、6、6、88、50、88、52、37、0、124、73、73、7、14、36、69、79、6、114、40、79、17、77、24、44、37、69、27、37、29、33、37、50、31、69、29、101、7、61、45、17、73、37、34、18、94、22、22、63、3、25、25、17、3、90、34、34、41、34、41、54、41、54、41、41、41、163、143、96、18、32、39、86、104、11、17、17、11、86、104、78、70、52、78、17、73、91、62、7、128、50、124、18、101、46、10、75、104、73、58、132、34、13、4、95、88、33、76、74、54、62、113、114、103、32、103、69、54、53、3、11、72、72、31、53、102、37、53、11、81、41、164、10、41、31、36、113、82、3、125、62、16、4、41、41、4、128、49、138、128、74、103、0、6、101、41、142、171、39、105、121、81、62、41、81、37、3、81、69、62、3、69、69、70、21、29、4、91、87、37、79、36、21、71、37、41、75、128、128、15、25、3、108、73、91、62、114、62、62、36、36、15、58、114、61、114、58、105、114、41、61、176、145、46、37、30、220、77、138、15、1、128、53、50、50、58、8、91、114、105、63、91、37、37、13、169、51、102、6、102、23、105、23、58、6、29、29、19、82、29、13、36、27、29、61、12、18、127、127、12、44、102、18、4、15、206、53、127、53、17、69、69、69、69、29、29、109、25、102、25、53、62、99、62、62、29、62、62、45、91、125、29、29、29、4、117、72、4、30、71、71、95、79、179、71、30、53、32、32、49、25、91、25、26、26、103、123、26、41、162、78、52、103、25、6、142、94、45、45、94、127、94、94、94、47、209、138、39、39、19、154、73、67、91、27、91、84、4、84、84、91、12、14、165、142、54、69、192、157、185、8、95、25、62、103、103、95、71、97、62、128、0、29、51、16、94、16、16、51、0、29、85、10、105、16、29、29、13、29、4、4、132、23、95、25、54、41、29、50、70、58、142、72、70、15、72、54、29、22、145、29、127、29、85、58、101、34、165、91、46、46、25、185、25、25、77、128、46、128、46、188、114、46、25、45、45、114、145、114、15、102、142、8、73、31、139、157、13、79、13、114、150、8、90、91、123、69、82、132、8、18、10、102、103、114、103、8、103、13、115、55、62、3、8、154、114、99、19、8、31、73、19、99、10、6、121、32、13、32、119、32、29、145、30、13、13、114、145、32、1、123、39、29、31、69、31、140、72、72、25、25、25、123、25、123、8、4、85、8、25、39、25、39、85、138、25、138、25、33、102、70、25、25、31、25、25、192、69、69、114、145、120、120、8、33、98、15、212、155、8、101、8、8、98、68、155、102、132、120、30、25、123、123、101、25、123、32、24、94、145、32、24、94、118、145、101、53、53、25、128、173、142、81、81、69、33、33、125、4、1、17、27、4、17、102、27、13、25、128、71、13、39、53、13、53、47、39、23、128、53、39、47、39、135、158、136、36、36、27、157、47、76、213、47、156、25、25、25、53、25、53、25、86、27、159、25、62、79、39、79、25、145、49、25、143、13、114、150、130、94、102、39、4、39、61、77、228、22、25、47、119、205、122、119、205、119、22、119、258、143、22、81、179、22、22、143、25、65、53、168、36、79、175、37、79、70、79、103、70、25、175、4、96、96、49、128、138、96、22、62、47、95、105、105、95、62、95、62、142、103、69、103、30、103、34、173、127、70、127、132、18、85、22、71、18、206、206、18、128、145、70、193、188、8、125、114、70、128、114、145、102、25、12、108、102、94、10、102、1、102、124、22、22、118、132、22、116、75、41、63、41、189、208、55、85、69、8、71、53、71、69、102、165、41、99、69、33、33、33、29、29、156、102、13、251、102、25、13、109、102、164、102、164、102、25、29、228、29、259、179、222、95、94、30、30、30、30、142、55、142、72、55、102、128、17、69、164、165、3、164、36、165、27、2
Data delivery can be subject to denial-of-service attacks by attackers that send corrupted packets that are accepted as legitimate by receivers. This is particularly a concern for multicast delivery because a corrupted packet may be injected into the session close to the root of the multicast tree, in which case, the corrupted packet will arrive at many receivers. This is particularly a concern when the code described in this document is used because the use of even one corrupted packet containing encoding data may result in the decoding of an object that is completely corrupted and unusable. It is thus RECOMMENDED that source authentication and integrity checking are applied to decoded objects before delivering objects to an application. For example, a SHA-1 hash [SHA1] of an object may be appended before transmission, and the SHA-1 hash is computed and checked after the object is decoded but before it is delivered to an application. Source authentication SHOULD be provided, for example, by including a digital signature verifiable by the receiver computed on top of the hash value. It is also RECOMMENDED that a packet authentication protocol, such as TESLA [RFC4082], be used to detect and discard corrupted packets upon arrival. This method may also be used to provide source authentication. Furthermore, it is RECOMMENDED that Reverse Path Forwarding checks be enabled in all network routers and switches along the path from the sender to receivers to limit the possibility of a bad agent successfully injecting a corrupted packet into the multicast tree data path.
データ配信は、受信者によって合法として受け入れられている破損したパケットを送信する攻撃者によるサービス拒否攻撃の対象となります。これは、マルチキャストツリーのルートに近いセッションに破損したパケットが注入される可能性があるため、マルチキャスト配信の懸念事項です。その場合、破損したパケットは多くのレシーバーに到着します。これは、このドキュメントで説明されているコードが使用される場合に特に懸念事項です。これは、エンコードデータを含む1つの破損したパケットを使用すると、完全に破損して使用できないオブジェクトがデコードされる可能性があるためです。したがって、アプリケーションにオブジェクトを配信する前に、ソース認証と整合性チェックをデコードされたオブジェクトに適用することをお勧めします。たとえば、オブジェクトのSHA-1ハッシュ[SHA1]は、送信前に追加される場合があり、SHA-1ハッシュは、オブジェクトがデコードされた後にアプリケーションに配信される前に計算およびチェックされます。ソース認証は、たとえば、ハッシュ値の上に計算された受信機が検証可能なデジタル署名を含めることにより、提供する必要があります。また、Tesla [RFC4082]などのパケット認証プロトコルを使用して、到着時に破損したパケットを検出および破棄することもお勧めします。この方法は、ソース認証を提供するためにも使用できます。さらに、すべてのネットワークルーターと送信者から受信機にパスに沿ってスイッチを入れて、不良エージェントが破損したパケットをマルチキャストツリーデータパスに正常に注入する可能性を制限することをお勧めします。
Another security concern is that some FEC information may be obtained by receivers out-of-band in a session description, and if the session description is forged or corrupted, then the receivers will not use the correct protocol for decoding content from received packets. To avoid these problems, it is RECOMMENDED that measures be taken to prevent receivers from accepting incorrect session descriptions, e.g., by using source authentication to ensure that receivers only accept legitimate session descriptions from authorized senders.
別のセキュリティ上の懸念は、セッションの説明で一部のFEC情報が帯域外の受信機によって取得される可能性があり、セッションの説明が偽造または破損している場合、受信者は受信パケットからコンテンツをデコードするために正しいプロトコルを使用しないことです。これらの問題を回避するために、レシーバーが誤ったセッションの説明を受け入れるのを防ぐための措置を講じることをお勧めします。
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA registration. For general guidelines on IANA considerations as they apply to this document, see [RFC5052]. This document assigns the Fully-Specified FEC Encoding ID 1 under the ietf:rmt:fec:encoding name-space to "Raptor Code".
FECエンコードIDとFECインスタンスIDの値は、IANA登録の対象となります。IANAの考慮事項に関する一般的なガイドラインについては、この文書に適用されます。[RFC5052]を参照してください。このドキュメントは、IETF：RMT：FEC：名前空間を「Raptorコード」にエンコードする完全に指定されたFECエンコードID 1を割り当てます。
Numerous editorial improvements and clarifications were made to this specification during the review process within 3GPP. Thanks are due to the members of 3GPP Technical Specification Group SA, Working Group 4, for these.
3GPP内のレビュープロセス中に、この仕様に多数の編集上の改善と説明がなされました。これらについては、3GPPテクニカル仕様グループSA、ワーキンググループ4のメンバーに感謝します。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するためのキーワード」、BCP 14、RFC 2119、1997年3月。
[RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction", RFC 4082, June 2005.
[RFC4082] Perrig、A.、Song、D.、Canetti、R.、Tygar、J。、およびB. Briscoe、「タイミング効率の高いストリーム損失耐性認証（TESLA）：マルチキャストソース認証変換導入」、RFC 4082、2005年6月。
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction (FEC) Building Block", RFC 5052, August 2007.
[RFC5052] Watson、M.、Luby、M。、およびL. Vicisano、「フォワードエラー補正（FEC）ビルディングブロック」、RFC 5052、2007年8月。
[CCNC] Luby, M., Watson, M., Gasiba, T., Stockhammer, T., and W. Xu, "Raptor Codes for Reliable Download Delivery in Wireless Broadcast Systems", CCNC 2006, Las Vegas, NV , Jan 2006.
[CCNC] Luby、M.、Watson、M.、Gasiba、T.、Stockhammer、T.、およびW. Xu、「ワイヤレス放送システムでの信頼できるダウンロード配信のためのRaptorコード」、CCNC 2006、ラスベガス、NV、Jan、Jan、Jan2006年。
[MBMS] 3GPP, "Multimedia Broadcast/Multicast Service (MBMS); Protocols and codecs", 3GPP TS 26.346 6.1.0, June 2005.
[MBMS] 3GPP、「マルチメディアブロードキャスト/マルチキャストサービス（MBMS）、プロトコルとコーデック」、3GPP TS 26.346 6.1.0、2005年6月。
[RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002.
[RFC3453] Luby、M.、Vicisano、L.、Gemmell、J.、Rizzo、L.、Handley、M。、およびJ. Crowcroft、「信頼できるマルチキャストでのフォワードエラー補正（FEC）の使用」、RFC 3453、2002年12月。
[Raptor] Shokrollahi, A., "Raptor Codes", IEEE Transactions on Information Theory no. 6, June 2006.
[Raptor] Shokrollahi、A。、「Raptor Codes」、IEEE Transactions on Information Theory no。6、2006年6月。
[SHA1] "Secure Hash Standard", Federal Information Processing Standards Publication (FIPS PUB) 180-1, April 2005.
[SHA1]「Secure Hash Standard」、連邦情報処理標準出版（FIPS Pub）180-1、2005年4月。
Authors' Addresses
著者のアドレス
Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538 U.S.A.
Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont、CA 94538 U.S.A.
EMail: luby@digitalfountain.com
Amin Shokrollahi EPFL Laboratory of Algorithmic Mathematics IC-IIF-ALGO PSE-A Lausanne 1015 Switzerland
アルゴリズム数学のAmin Shokrollahi EPFL研究所IC-IIF-ALGO PSE-A LAUSANNE 1015 SWITZERLAND
EMail: amin.shokrollahi@epfl.ch
Mark Watson Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538 U.S.A.
マークワトソンデジタルファウンテン39141シビックセンタードライブスイート300フリーモント、カリフォルニア94538 U.S.A.
EMail: mark@digitalfountain.com
Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541 Germany
Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541ドイツ
EMail: stockhammer@nomor.de
Full Copyright Statement
完全な著作権声明
Copyright (C) The IETF Trust (2007).
著作権（c）The IETF Trust（2007）。
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
この文書は、BCP 78に含まれる権利、ライセンス、および制限の対象となり、そこに記載されている場合を除き、著者はすべての権利を保持しています。
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
このドキュメントとここに含まれる情報は、「現状のまま」に基づいて提供され、貢献者、彼/彼女が代表する組織（もしあれば）、インターネット協会、IETFトラスト、インターネットエンジニアリングタスクフォースがすべてを否認します。明示的または黙示的な保証。ここでの情報の使用は、特定の目的に対する商品性または適合性の権利または暗黙の保証を侵害しないという保証を含むがこれらに限定されない。
Intellectual Property
知的財産
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
IETFは、知的財産権またはその他の権利の有効性または範囲に関して、この文書に記載されている技術の実装または使用、またはそのような権利に基づくライセンスがどの程度であるかについての使用に関連すると主張する可能性があるという立場はありません。利用可能になります。また、そのような権利を特定するために独立した努力をしたことも表明していません。RFCドキュメントの権利に関する手順に関する情報は、BCP 78およびBCP 79に記載されています。
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
IETF事務局に行われたIPR開示のコピーと、利用可能にするライセンスの保証、またはこの仕様の実装者またはユーザーによるそのような独自の権利の使用のための一般的なライセンスまたは許可を取得するための試みの結果を取得できます。http://www.ietf.org/iprのIETFオンラインIPRリポジトリから。
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.
IETFは、関心のある当事者に、著作権、特許、または特許出願、またはこの基準を実装するために必要なテクノロジーをカバーする可能性のあるその他の独自の権利を注意深く招待します。ietf-ipr@ietf.orgのIETFへの情報をお問い合わせください。