Internet Engineering Task Force (IETF) M. Luby
Request for Comments: 6330 Qualcomm Incorporated
Category: Standards Track A. Shokrollahi
ISSN: 2070-1721 EPFL
M. Watson
Netflix Inc.
T. Stockhammer
Nomor Research
L. Minder
Qualcomm Incorporated
August 2011
RaptorQ Forward Error Correction Scheme for Object Delivery
Abstract
抽象
This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 6, for the RaptorQ FEC code and its application to reliable delivery of data objects.
この文書では、RaptorQ FECコードおよびデータオブジェクトの信頼できる配信への応用のために、FEC符号化ID 6に対応する、完全指定前方誤り訂正（FEC）スキームを記載しています。
RaptorQ codes are a new family of codes that provide superior flexibility, support for larger source block sizes, and better coding efficiency than Raptor codes in RFC 5053. RaptorQ is also a fountain code, i.e., as many encoding symbols as needed can be generated on the fly by the encoder from the source symbols of a source block of data. The decoder is able to recover the source block from almost any set of encoding symbols of sufficient cardinality -- in most cases, a set of cardinality equal to the number of source symbols is sufficient; in rare cases, a set of cardinality slightly more than the number of source symbols is required.
RaptorQコードはRaptorQもファウンテンコードであるRFC 5053に優れた柔軟性、より大きなソースブロックサイズのサポート、およびラプターコードよりも優れた符号化効率を提供するコードの新しいファミリーである、すなわち、のような多くの符号化シンボル必要に応じて上に生成することができますデータのソースブロックのソースシンボルから、エンコーダによって飛びます。デコーダは十分カーディナリティの符号化シンボルのほぼすべてのセットからソースブロックを回復することができる - ほとんどの場合、ソースシンボルの数に等しい基数のセットで十分です。まれに、ソースシンボルの数よりもわずかにカーディナリティのセットが必要です。
The RaptorQ code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated.
ここで説明するRaptorQコードは、すべてのソースシンボルを発生させることができる符号化シンボルの一つであることを意味し、体系的なコードです。
Status of This Memo
このメモのステータス
This is an Internet Standards Track document.
これは、インターネット標準化過程文書です。
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741.
このドキュメントはインターネットエンジニアリングタスクフォース（IETF）の製品です。これは、IETFコミュニティの総意を表しています。これは、公開レビューを受けており、インターネットエンジニアリング運営グループ（IESG）によって公表のために承認されています。インターネット標準の詳細については、RFC 5741のセクション2で利用可能です。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6330.
このドキュメントの現在の状態、任意の正誤表、そしてどのようにフィードバックを提供するための情報がhttp://www.rfc-editor.org/info/rfc6330で取得することができます。
Copyright Notice
著作権表示
Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.
著作権（C）2011 IETF信託とドキュメントの作成者として特定の人物。全著作権所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
この文書では、BCP 78と、この文書の発行日に有効なIETFドキュメント（http://trustee.ietf.org/license-info）に関連IETFトラストの法律の規定に従うものとします。彼らは、この文書に関してあなたの権利と制限を説明するように、慎重にこれらの文書を確認してください。コードコンポーネントは、トラスト法規定のセクションで説明4.eおよび簡体BSDライセンスで説明したように、保証なしで提供されているよう簡体BSDライセンスのテキストを含める必要があり、この文書から抽出されました。
Table of Contents
目次
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4
3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 5
3.2. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 5
3.3. FEC Object Transmission Information . . . . . . . . . . . 5
3.3.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 5
3.3.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 6
4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 7
4.2. Content Delivery Protocol Requirements . . . . . . . . . . 7
4.3. Example Parameter Derivation Algorithm . . . . . . . . . . 7
4.4. Object Delivery . . . . . . . . . . . . . . . . . . . . . 9
4.4.1. Source Block Construction . . . . . . . . . . . . . . 9
4.4.2. Encoding Packet Construction . . . . . . . . . . . . . 11
4.4.3. Example Receiver Recovery Strategies . . . . . . . . . 12
5. RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . 12
5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 13
5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 14
5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.3. Systematic RaptorQ Encoder . . . . . . . . . . . . . . . . 18
5.3.1. Introduction . . . . . . . . . . . . . . . . . . . . . 18
5.3.2. Encoding Overview . . . . . . . . . . . . . . . . . . 19
5.3.3. First Encoding Step: Intermediate Symbol Generation . 21
5.3.4. Second Encoding Step: Encoding . . . . . . . . . . . . 27
5.3.5. Generators . . . . . . . . . . . . . . . . . . . . . . 27
5.4. Example FEC Decoder . . . . . . . . . . . . . . . . . . . 30
5.4.1. General . . . . . . . . . . . . . . . . . . . . . . . 30
5.4.2. Decoding an Extended Source Block . . . . . . . . . . 31
5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 36
5.5.1. The Table V0 . . . . . . . . . . . . . . . . . . . . . 36
5.5.2. The Table V1 . . . . . . . . . . . . . . . . . . . . . 37
5.5.3. The Table V2 . . . . . . . . . . . . . . . . . . . . . 38
5.5.4. The Table V3 . . . . . . . . . . . . . . . . . . . . . 40
5.6. Systematic Indices and Other Parameters . . . . . . . . . 41
5.7. Operating with Octets, Symbols, and Matrices . . . . . . . 62
5.7.1. General . . . . . . . . . . . . . . . . . . . . . . . 62
5.7.2. Arithmetic Operations on Octets . . . . . . . . . . . 62
5.7.3. The Table OCT_EXP . . . . . . . . . . . . . . . . . . 63
5.7.4. The Table OCT_LOG . . . . . . . . . . . . . . . . . . 64
5.7.5. Operations on Symbols . . . . . . . . . . . . . . . . 65
5.7.6. Operations on Matrices . . . . . . . . . . . . . . . . 65
5.8. Requirements for a Compliant Decoder . . . . . . . . . . . 65
6. Security Considerations . . . . . . . . . . . . . . . . . . . 66
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 67
9.1. Normative References . . . . . . . . . . . . . . . . . . . 67
9.2. Informative References . . . . . . . . . . . . . . . . . . 68
This document specifies an FEC scheme for the RaptorQ forward error correction code for object delivery applications. The concept of an FEC scheme is defined in RFC 5052 [RFC5052], and this document follows the format prescribed there and uses the terminology of that document. The RaptorQ code described herein is a next generation of the Raptor code described in RFC 5053 [RFC5053]. The RaptorQ code provides superior reliability, better coding efficiency, and support for larger source block sizes than the Raptor code of RFC 5053 [RFC5053]. These improvements simplify the usage of the RaptorQ code in an object delivery Content Delivery Protocol compared to RFC 5053 RFC 5053 [RFC5053]. A detailed mathematical design and analysis of the RaptorQ code together with extensive simulation results are provided in [RaptorCodes].
この文書では、オブジェクト・デリバリーアプリケーションのためのRaptorQ前方誤り訂正符号のためのFECスキームを指定します。 FECスキームの概念は、RFC 5052 [RFC5052]で定義されており、この文書が所定のフォーマットに従っており、その文書の用語を使用します。本明細書に記載のRaptorQコードは、RFC 5053 [RFC5053]に記載ラプターコードの次の世代です。 RaptorQコードは、RFC 5053 [RFC5053]のラプターコードよりも大きいソースブロックサイズのために優れた信頼性、より良好な符号化効率、およびサポートを提供します。これらの改善は、RFC 5053、RFC 5053 [RFC5053]に比べオブジェクト配信コンテンツ配信プロトコルでRaptorQコードの使用を簡素化します。広範なシミュレーション結果と詳細な数学的なデザインと一緒にRaptorQコードの解析は、[RaptorCodes]で提供されます。
The RaptorQ FEC scheme is a Fully-Specified FEC scheme corresponding to FEC Encoding ID 6.
RaptorQ FEC方式は、FEC符号化ID 6に対応する完全指定FEC方式です。
RaptorQ is a fountain code, i.e., as many encoding symbols as needed can be generated on the fly by the encoder from the source symbols of a block. The decoder is able to recover the source block from almost any set of encoding symbols of cardinality only slightly larger than the number of source symbols.
RaptorQはファウンテンコードである、すなわち、のような多くの符号化シンボル必要に応じて、ブロックのソースシンボルから、エンコーダによってその場で生成することができます。デコーダは、ソースシンボルの数よりもわずかに大きいだけカーディナリティのシンボルを符号化するほぼすべてのセットからソースブロックを回復することができます。
The code described in this document is a systematic code; that is, the original unmodified source symbols, as well as a number of repair symbols, can be sent from sender to receiver. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC3453].
この文書に記述されたコードは、システマティックコードです。つまり、元の未修飾のソースシンボル、ならびに修復シンボルの数は、送信側から受信側へ送信することができます。信頼性マルチキャストにおける前方誤り訂正コードの使用に関する詳細な背景については、[RFC3453]を参照してください。
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].
この文書のキーワード "MUST"、 "MUST NOT"、 "REQUIRED"、、、、 "べきではない" "べきである" "ないもの" "ものとし"、 "推奨"、 "MAY"、および "OPTIONAL" はあります[RFC2119]に記載されているように解釈されます。
The octet order of all fields is network byte order, i.e., big-endian.
すべてのフィールドのオクテット順序は、ネットワークバイト順、つまり、ビッグエンディアンです。
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SBN | Encoding Symbol ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID Format
図1：FECペイロードIDフォーマット
o Source Block Number (SBN): 8-bit unsigned integer. A non-negative integer identifier for the source block that the encoding symbols within the packet relate to.
Oソースブロック番号（SBN）：8ビット符号なし整数。パケット内の符号化シンボルは、に関連するソースブロックの非負整数識別子。
o Encoding Symbol ID (ESI): 24-bit unsigned integer. A non-negative integer identifier for the encoding symbols within the packet.
O符号化シンボルID（ESI）：24ビットの符号なし整数。パケット内の符号化シンボルの非負整数識別子。
The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 4.
ソースブロック番号および符号化シンボル識別子の解釈は、セクション4で定義されています。
The value of the FEC Encoding ID MUST be 6, as assigned by IANA (see Section 7).
IANA（セクション7参照）によって割り当てられたFEC符号化IDの値は、6でなければなりません。
The Common FEC Object Transmission Information elements used by this FEC scheme are:
このFECスキームによって使用される共通FECオブジェクト伝送情報要素は以下のとおりです。
o Transfer Length (F): 40-bit unsigned integer. A non-negative integer that is at most 946270874880. This is the transfer length of the object in units of octets.
O転送長さ（F）：40ビット符号なし整数。 946270874880.これ以下である非負整数オクテット単位でオブジェクトの転送長です。
o Symbol Size (T): 16-bit unsigned integer. A positive integer that is less than 2^^16. This is the size of a symbol in units of octets.
Oシンボルサイズ（T）：16ビット符号なし整数。 2 ^^ 16未満の正の整数。これは、オクテット単位でのシンボルのサイズです。
The encoded Common FEC Object Transmission Information (OTI) format is shown in Figure 2.
符号化された共通FECオブジェクト伝送情報（OTI）フォーマットは、図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 (F) |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Reserved | Symbol Size (T) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: Encoded Common FEC OTI for RaptorQ FEC Scheme
図2：RaptorQ FECスキームのためにエンコードされた一般的なFEC OTI
NOTE: The limit of 946270874880 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 56403, and the limitation on the number of source blocks to 2^^8.
注：転送長に946270874880の限界は2 ^^ 16-1〜シンボル・サイズの制限の結果、56403のソースブロック内のシンボルの数の制限、及びソースの数に制限され2 ^^〜8ブロック。
The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC scheme:
以下のパラメータは、このFECスキームのスキーム固有のFECオブジェクト伝送情報要素で運ばれています。
o The number of source blocks (Z): 8-bit unsigned integer.
8ビット符号なし整数：ソースブロック（Z）の数、O。
o The number of sub-blocks (N): 16-bit unsigned integer.
16ビット符号なし整数：サブブロック（N）の数、O。
o A symbol alignment parameter (Al): 8-bit unsigned integer.
8ビット符号なし整数：シンボル配列パラメータアルミニウム（Al）O。
These parameters are all positive integers. The encoded Scheme-specific Object Transmission Information is a 4-octet field consisting of the parameters Z, N, and Al as shown in Figure 3.
これらのパラメータは、すべての正の整数です。符号化されたスキーマ固有オブジェクト伝送情報は、図3に示すように、パラメータZ、N、及びAlからなる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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Z | N | Al |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Encoded Scheme-Specific FEC Object Transmission Information
図3：符号化されたスキーマ固有FECオブジェクト伝送情報
The encoded FEC Object Transmission Information is a 12-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オブジェクト伝送情報の連結からなる12オクテットフィールドです。
These three parameters define the source block partitioning as described in Section 4.4.1.2.
セクション4.4.1.2に記載されるように、これらの3つのパラメータは、ソースブロックの区分を規定します。
For any undefined symbols or functions used in this section, in particular the functions "ceil" and "floor", refer to Section 5.1.
このセクションで使用される任意の未定義のシンボルまたは機能のため、特に、関数「切り上げ」及び「床」は、セクション5.1を参照してください。
This section describes the information exchange between the RaptorQ FEC scheme and any Content Delivery Protocol (CDP) that makes use of the RaptorQ FEC scheme for object delivery.
このセクションでは、オブジェクトの配信のためのRaptorQ FECスキームを使用するRaptorQ FECスキームと任意のコンテンツ配信プロトコル（CDP）の間での情報交換を説明します。
The RaptorQ encoder scheme and RaptorQ decoder scheme for object delivery require the following information from the CDP:
RaptorQエンコーダ方式とオブジェクト送達のためRaptorQ復号方式はCDPから次の情報を必要とします。
o F: the transfer length of the object, in octets
O F：オクテット内のオブジェクトの転送長、
o Al: the symbol alignment parameter
アル：シンボル配列パラメータ
o T: the symbol size in octets, which MUST be a multiple of Al
O T：アルの倍数でなければならないオクテットでシンボルサイズ、
o Z: the number of source blocks
OのZ：ソースブロックの数
o N: the number of sub-blocks in each source block
O N：各ソースブロック内のサブブロックの数
The RaptorQ encoder scheme for object delivery additionally requires:
オブジェクト送達のためRaptorQエンコーダ方式がさらに必要となります。
- the object to be encoded, which is F octets long
- オブジェクトは、符号化されるFオクテット長であります
The RaptorQ encoder scheme supplies the CDP with the following information for each packet to be sent:
RaptorQエンコーダ方式は、送信される各パケットのための次の情報をCDPを供給する。
o Source Block Number (SBN)
Oソースブロック番号（SBN）
o Encoding Symbol ID (ESI)
または符号化シンボルID（ESI）
o Encoding symbol(s)
Oエンコーディングシンボル（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の導出のための推奨事項を提供します。
o F: the transfer length of the object, in octets o WS: the maximum size block that is decodable in working memory, in octets
O F：WS Oオクテット内のオブジェクトの転送長、：オクテットで、ワーキングメモリに復号可能な最大サイズのブロック
o P': the maximum payload size in octets, which is assumed to be a multiple of Al
O P '：アルの倍数であると仮定されるオクテットの最大ペイロードサイズ、
o Al: the symbol alignment parameter, in octets
OのAl：シンボル配列パラメータ、オクテット単位
o SS: a parameter where the desired lower bound on the sub-symbol size is SS*Al
O SS：サブシンボルサイズに下限所望のパラメータは、*アルSSであります
o K'_max: the maximum number of source symbols per source block.
O K'_max：ソースブロック当たりのソースシンボルの最大数。
Note: Section 5.1.2 defines K'_max to be 56403.
注意：5.1.2項は56403であることをK'_maxを定義します。
Based on the above inputs, the transport parameters T, Z, and N are calculated as follows:
次のように上記入力に基づいて、転送パラメータT、Z、及びNが算出されます。
Let
してみましょう
o T = P'
O T = P」
o Kt = ceil(F/T)
O Ktを= CEIL（F / T）
o N_max = floor(T/(SS*Al))
O N_max =フロア（T /（SS * Al）から）
o for all n=1, ..., N_max
、全てのn = 1のためのO ...、N_max
* KL(n) is the maximum K' value in Table 2 in Section 5.6 such that
* KL（N）セクションの表2における最大K」値は5.6よう
K' <= WS/(Al*(ceil(T/(Al*n))))
嘔吐<= / O（*すべて（トレント（I /（AL×n個））））
o Z = ceil(Kt/KL(N_max))
O Z = CEIL（（Ktを/ KL N_max））
o N is the minimum n=1, ..., N_max such that ceil(Kt/Z) <= KL(n)
O Nが最小となるN = 1、...、N_maxようCEIL（Ktを/ Z）<= KL（N）
It is RECOMMENDED that each packet contains exactly one symbol. However, receivers SHALL support the reception of packets that contain multiple symbols.
各パケットが正確に1つのシンボルを含んでいることが推奨されます。しかし、受信機は、複数のシンボルを含むパケットの受信をサポートします。
The value Kt is the total number of symbols required to represent the source data of the object.
値Ktを、オブジェクトのソースデータを表すのに必要なシンボルの総数です。
The algorithm above and that defined in Section 4.4.1.2 ensure that the sub-symbol sizes are a multiple of the symbol alignment parameter, Al. This is useful because the sum operations used for encoding and decoding are generally performed several octets at a time, for example, at least 4 octets 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 octets.
アルゴリズム上記サブシンボルサイズがシンボル配列パラメータ、アルミニウムの倍数であることを確認し、セクション4.4.1.2で定義されています。符号化および復号化に使用和演算は、一般に、少なくとも4つのオクテットは、32ビットプロセッサ上で時、例えば、一度にいくつかのオクテットを実行しているので、これは有用です。サブシンボルサイズはオクテットのこの数の倍数である場合にこのように、符号化及び復号化を高速に行うことができます。
The recommended setting for the input parameter Al is 4.
入力パラメータアルのための推奨設定は4です。
The parameter WS 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 WS depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than WS.
パラメータWSは、デコーダに限定ワーキングメモリを効率的に復号することができる符号化データを生成するために使用することができます。 WSの所与の値に対する実際の最大デコーダメモリ要件は、実装に依存するが、わずかに大きいだけWSよりワーキングメモリを用いて復号化を実現することができることに留意されたいです。
In order to apply the RaptorQ encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The RaptorQ encoder is applied independently to each source block. Each source block is identified by a unique 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 octets each. Each source symbol is identified by a unique Encoding Symbol Identifier (ESI), where the first source symbol of a source block has ESI zero, the second has ESI one, etc.
ソースオブジェクトにRaptorQエンコーダを適用するために、オブジェクトは、ソースブロックとして知られているZ> = 1つのブロックに分割されてもよいです。 RaptorQエンコーダは、各ソースブロックに独立に適用されます。各ソースブロックは最初のソースブロックがSBNゼロを持っている固有のソースブロック番号（SBN）によって識別され、第二には、各ソースブロックはサイズTオクテットのソースシンボルの数、Kに分割されるSBNのいずれか等を有しています各。各ソースシンボルは、ソースブロックの最初のソースシンボルがESIゼロで、第二等、ESIいずれかを有している固有の符号化シンボル識別子（ESI）によって識別されます
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 4.4.1.2 below.
Kの値は、必ずしも物体の各ソースブロックに対して同じではなく、「Tの値は、必ずしもソースブロックの各サブブロックに対して同じではないかもしれないことに留意されたいです。しかし、シンボルサイズTは、オブジェクトのすべてのソースブロックに対して同じであり、シンボルの数は、Kは、ソースブロックのすべてのサブブロックについても同様です。ソースブロックおよびサブブロックにオブジェクトの正確な分割は、以下のセクション4.4.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:
FはAl、T、Z、及びN - - と機能パーティション[]ソースブロックおよびサブブロックの構造は、5つの入力パラメータに基づいて決定されます。次のように5つの入力パラメータが定義されています。
o F: the transfer length of the object, in octets o Al: a symbol alignment parameter, in octets
O F：アルOオクテット内のオブジェクトの転送長、：シンボル配列パラメータ、オクテット単位
o T: the symbol size, in octets, which MUST be a multiple of Al
O T：アルの倍数でなければならないオクテットでシンボルサイズ、
o Z: the number of source blocks
OのZ：ソースブロックの数
o N: the number of sub-blocks in each source block
O N：各ソースブロック内のサブブロックの数
These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. Recommendations for derivation of these parameters are provided in Section 4.3.
これらのパラメータは、CEIL（CEIL（F / T）/ Z）<= K'_maxように設定されなければなりません。これらのパラメータの導出のための推奨事項は、セクション4.3で提供されています。
The function Partition[I,J] derives parameters for partitioning a block of size I into J approximately equal-sized blocks. More specifically, it partitions I into JL blocks of length IL and JS blocks of length IS. The output of Partition[I, J] is the sequence (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL.
関数パーティション[I、J]は、私はJほぼ等しいサイズのブロックにサイズのブロックを分割するためのパラメータを導出します。具体的には、長さの長さILとJSブロックのJLブロックにI ISを分割します。 *はJ、および - パーティション[I、J]の出力シーケンス（IL、IS、JL、JS）、IL = CEIL（I / J）であり、=フロア（I / J）、JL = iはJS = J - JL。
The source object MUST be partitioned into source blocks and sub-blocks as follows:
次のようにソース・オブジェクトは、ソースブロックおよびサブブロックに分割されなければなりません。
Let
してみましょう
o Kt = ceil(F/T),
O Ktを= CEIL（F / T）
o (KL, KS, ZL, ZS) = Partition[Kt, Z],
O（KL、KS、ZL、ZS）=パーティション[Ktを、Z]
o (TL, TS, NL, NS) = Partition[T/Al, N].
O（TL、TS、NL、NS）=パーティション[T /ら、N]。
Then, the object MUST be partitioned into Z = ZL + ZS contiguous source blocks, the first ZL source blocks each having KL*T octets, i.e., KL source symbols of T octets each, and the remaining ZS source blocks each having KS*T octets, i.e., KS source symbols of T octets each.
その後、オブジェクトはZ = ZL + ZS隣接ソースブロックに分割されなければならない、最初のZLのソースブロックは各々、それぞれがKS * Tを有するKL * Tオクテット、Tオクテットの、すなわち、KLのソースシンボルそれぞれ、残りZSソースブロックを有しますTオクテットのオクテット、すなわち、KSのソースシンボルそれぞれ。
If Kt*T > F, then, for encoding purposes, the last symbol of the last source block MUST be padded at the end with Kt*T-F zero octets.
Ktを* T> F場合、次に、符号化のために、最後のソースブロックの最後のシンボルは、Ktを* T-Fゼロオクテットと終わりにパディングされなければなりません。
Next, each source block with K source symbols 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 octets and the remaining NS sub-blocks each consisting of K contiguous sub-symbols of size of TS*Al octets. The symbol alignment parameter Al ensures that sub-symbols are always a multiple of Al octets.
次に、K個のソースシンボルと各ソースブロックはN = NL + NS隣接サブブロックに分割されなければならない、各* TLのサイズのK個の連続サブシンボルのAlオクテットからなる第NLサブブロックと残りNSのサブブロックの各々は、TS *アルオクテットのサイズのK個の連続サブシンボルからなります。シンボル配列パラメータAlがサブシンボルは常にアルオクテットの倍数であることを保証します。
Finally, the mth symbol of a source block consists of the concatenation of the mth sub-symbol from each of the N sub-blocks. Note that this implies that when N > 1, a symbol is NOT a contiguous portion of the object.
最後に、ソースブロックの第m番目のシンボルは、N個のサブブロックの各々からm番目のサブシンボルの連結から成ります。これは、N> 1は、シンボルは、オブジェクトの連続した部分ではありませんときことを意味することに留意されたいです。
Each encoding packet contains the following information:
各符号化パケットは、以下の情報が含まれています。
o Source Block Number (SBN)
Oソースブロック番号（SBN）
o Encoding Symbol ID (ESI)
または符号化シンボルID（ESI）
o encoding symbol(s)
O符号化シンボル（S）
Each source block is encoded independently of the others. Each encoding packet contains encoding symbols generated from the one source block identified by the SBN carried in the encoding packet. Source blocks are numbered consecutively from zero.
各ソースブロックは、他とは独立に符号化されます。各符号化パケットは、符号化パケットで運ばSBNによって識別された1つのソースブロックから生成された符号化シンボルを含みます。ソースブロックは、ゼロから連続して番号が付けられています。
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 source symbols in the source block. Encoding Symbol IDs K onwards identify repair symbols generated from the source symbols using the RaptorQ encoder.
0からK-1までシンボルID値をコードするKは、ソースブロック内のソースシンボルの数である順、ソースブロックのソースシンボルを識別する。符号化シンボルIDはK以降RaptorQエンコーダを使用してソースシンボルから生成されたリペアシンボルを識別する。
Each encoding packet either contains only source symbols (source packet) or contains only 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 octets added for FEC encoding purposes, then these octets need not be included in the packet. Otherwise, each packet MUST contain only whole symbols.
各符号化パケットは、いずれかのみソースシンボル（ソースパケット）を含むかのみリペアシンボル（修復パケット）を含みます。パケットは、同じソースブロックからのシンボルの任意の数を含んでいてもよいです。ソースパケット内の最後のソースシンボルが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は、そのパケットで運ばれる最初のソースシンボルの符号化シンボルIDです。パケット内の後続のソースシンボルは、Gはパケット内のシンボルの数で順番にX + G-1に符号化シンボルIDがX + 1を有します。
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は、修復パケットの最初の修復シンボルの符号化シンボルIDであり、パケットの後続の修復シンボルはX + G-1に符号化シンボルIDがX + 1を有します順番に、Gはパケット内のシンボルの数です。
Note that it is not necessary for the receiver to know the total number of repair packets.
受信機が修復パケットの総数を知ることは必要ではないことに留意されたいです。
A receiver can use the received encoding symbols for each source block of an object to recover the source symbols for that source block independently of all other source blocks.
受信機は、独立して、他の全てのソースブロックのソースブロックのソースシンボルを回復するために、オブジェクトの各ソースブロックの受信符号化シンボルを使用することができます。
If there is one sub-block per source block, i.e., N = 1, then the portion of the data in the original object in its original order associated with a source block consists of the concatenation of the source symbols of a source block in consecutive ESI order.
ソースブロック、すなわち当たり一つのサブブロック、N = 1である場合、ソースブロックに関連付けられた元の順序で元のオブジェクト内のデータの部分は、連続で、ソースブロックのソースシンボルの連結から成りESI順。
If there are multiple sub-blocks per source block, i.e., if N > 1, then the portion of the data in the original object in its original order associated with a source block consists of the concatenation of the sub-blocks associated with the source block, where sub-symbols within each sub-block are in consecutive ESI order. In this case, there are different receiver source block recovery strategies worth considering depending on the available amount of Random Access Memory (RAM) at the receiver, as outlined below.
ソースブロックごとに複数のサブブロックがある場合はN> 1の場合、すなわち、ソース・ブロックに関連付けられた元の順序で元のオブジェクト内のデータの一部は、ソースに関連付けられたサブブロックの連結から成り各サブブロック内のサブシンボルが連続ESI順序であるブロック、。下記のとおり、この場合には、異なる受信機のソース・ブロック・リカバリー・ストラテジーは、受信機でのランダムアクセスメモリ（RAM）の利用可能量に応じて検討する価値があります。
One strategy is to recover the source symbols of a source block using the decoding procedures applied to the received symbols for the source block to recover the source symbols as described in Section 5, and then to reorder the sub-symbols of the source symbols so that all consecutive sub-symbols of the first sub-block are first, followed by all consecutive sub-symbols of the second sub-block, etc., followed by all consecutive sub-symbols of the Nth sub-block. This strategy is especially applicable if the receiver has enough RAM to decode an entire source block.
1つの戦略は、セクション5で説明したように、ソースシンボルを回復するためにソースブロックの受信シンボルに適用される復号化手順を使用してソースブロックのソースシンボルを回復するために、そしてそのようにソースシンボルのサブシンボルの順序を変更することです最初のサブブロックの全ての連続するサブシンボルは、N番目のサブブロックの全ての連続するサブシンボルに続く第2のサブブロックなど、すべての連続するサブシンボルに続く、最初のものです。受信機は、全体ソースブロックを復号化するのに十分なRAMを持っている場合、この戦略は、特に適用可能です。
Another strategy is to separately recover the sub-blocks of a source block. For example, a receiver may demultiplex and store sub-symbols associated with each sub-block separately as packets containing encoding symbols arrive, and then use the stored sub-symbols received for a sub-block to recover that sub-block using the decoding procedures described in Section 5. This strategy is especially applicable if the receiver has enough RAM to decode only one sub-block at a time.
別の戦略は、別々のソースブロックのサブブロックを回復することです。例えば、受信機は、逆多重化してもよいし、サブブロックが復号化手順を使用して、そのサブブロックを回復するための符号化シンボルを含むパケットが到着し、その後、格納されたサブシンボルを使用するように別々に、各サブブロックに関連付けられた格納サブシンボルは、受信されました第5節で説明この戦略は、受信機が一度に一つのサブブロックを復号化するのに十分なRAMを持っている場合に特に適用可能です。
For the purpose of the RaptorQ FEC code specification in this section, the following definitions, symbols, and abbreviations apply. A basic understanding of linear algebra, matrix operations, and finite fields is assumed in this section. In particular, matrix multiplication and matrix inversion operations over a mixture of the finite fields GF[2] and GF[256] are used. A basic familiarity with sparse linear equations, and efficient implementations of algorithms that take advantage of sparse linear equations, is also quite beneficial to an implementer of this specification.
このセクションでRaptorQ FECコード明細書の目的のために、以下の定義、記号、及び略語が適用されます。線形代数、行列演算、有限フィールドの基本的な理解は、このセクションで想定されています。具体的には、有限フィールドGFの混合物上に行列乗算および行列反転操作は、[2]及びGF [256]は使用されています。スパース線形方程式、及びスパース線形方程式を利用するアルゴリズムの効率的な実装との基本的な知識は、また、本明細書の実装に非常に有益です。
o Source block: a block of K source symbols that are considered together for RaptorQ encoding and decoding purposes.
Oソースブロック：RaptorQ符号化および復号化のために一緒に考慮されるK個のソースシンボルのブロック。
o Extended Source Block: a block of K' source symbols, where K' >= K, constructed from a source block and zero or more padding symbols.
Kのブロック「ソースシンボル、K」> = Kは、ソースブロックと、ゼロ以上のパディングシンボルから構成されます。oソースブロックを拡張しました。
o Symbol: a unit of data. The size, in octets, of a symbol is known as the symbol size. The symbol size is always a positive integer.
Oシンボル：データの単位。シンボルのオクテットでのサイズは、シンボルサイズとして知られています。シンボルサイズは常に正の整数です。
o Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size.
Oソースシンボル：符号化プロセス中に使用されるデータの最小単位。ソースブロック内のすべてのソースシンボルは、同じサイズを持っています。
o Padding symbol: a symbol with all zero bits that is added to the source block to form the extended source block.
Oパディングシンボル：拡張されたソースブロックを形成するために、ソースブロックに追加されるすべてのゼロ・ビットのシンボル。
o Encoding symbol: a symbol that can be sent as part of the encoding of a source block. The encoding symbols of a source block consist of the source symbols of the source block and the repair symbols generated from the source block. Repair symbols generated from a source block have the same size as the source symbols of that source block.
Oエンコーディングシンボル：ソースブロックの符号化の一部として送信することができるシンボル。ソースブロックの符号化シンボルは、ソースブロックのソースシンボルとソースブロックから生成されたリペアシンボルから成ります。ソースブロックから生成されたリペアシンボルは、ソースブロックのソースシンボルと同じサイズを有します。
o Repair symbol: the encoding symbols of a source block that are not source symbols. The repair symbols are generated based on the source symbols of a source block.
O修復シンボル：ソースシンボルないソースブロックの符号化シンボル。リペアシンボルは、ソースブロックのソースシンボルに基づいて生成されます。
o Intermediate symbols: symbols generated from the source symbols using an inverse encoding process based on pre-coding relationships. 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 sent as part of the encoding of a source block. The intermediate symbols are partitioned into LT symbols and PI symbols for the purposes of the encoding process.
O中間シンボル：プリコーディング関係に基づいて、逆符号化処理を使用してソースシンボルから生成されたシンボル。リペアシンボルは、中間シンボルから直接生成されます。符号化シンボルは中間シンボル、即ち、中間シンボルは、ソースブロックの符号化の一部として送信されていないが含まれていません。中間シンボルは、符号化プロセスの目的のためにLT符号とPIシンボルに分割されます。
o LT symbols: a process similar to that described in [LTCodes] is used to generate part of the contribution to each generated encoding symbol from the portion of the intermediate symbols designated as LT symbols.
O LT記号：[LTCodes]に記載のものと同様のプロセスは、LTシンボルとして指定中間シンボルの部分からそれぞれ生成された符号化シンボルへの寄与の一部を生成するために使用されます。
o PI symbols: a process even simpler than that described in [LTCodes] is used to generate the other part of the contribution to each generated encoding symbol from the portion of the intermediate symbols designated as PI symbols. In the decoding algorithm suggested in Section 5.4, the PI symbols are inactivated at the start, i.e., are placed into the matrix U at the beginning of the first phase of the decoding algorithm. Because the symbols corresponding to the columns of U are sometimes called the "inactivated" symbols, and since the PI symbols are inactivated at the beginning, they are considered "permanently inactivated".
OのPIシンボル：[LTCodes]に記載されたものよりもさらに簡単な方法は、PIシンボルとして指定された中間シンボルの部分からそれぞれ生成された符号化シンボルへの寄与の他の部分を生成するために使用されます。セクション5.4で提案復号アルゴリズムでは、PIシンボルが開始時に不活性化される、即ち、復号アルゴリズムの第1フェーズの開始時に行列U内に配置されています。シンボルは、Uの列に対応しているので、時々「不活性化」のシンボルと呼ばれ、PIシンボルが最初に不活性化されているので、彼らは「永久に不活性化された」と考えられています。
o HDPC symbols: there is a small subset of the intermediate symbols that are HDPC symbols. Each HDPC symbol has a pre-coding relationship with a large fraction of the other intermediate symbols. HDPC means "High Density Parity Check".
O HDPCシンボル：HDPCシンボルである中間シンボルの小さなサブセットがあります。各HDPCシンボルは、他の中間シンボルの大部分を有するプリコーディング関係を有します。 HDPCは「高密度パリティチェック」を意味します。
o LDPC symbols: there is a moderate-sized subset of the intermediate symbols that are LDPC symbols. Each LDPC symbol has a pre-coding relationship with a small fraction of the other intermediate symbols. LDPC means "Low Density Parity Check".
O LDPCシンボル：LDPCシンボルである中間シンボルの中程度のサイズのサブセットが存在します。各LDPCシンボルは、他の中間シンボルの小部分を持つプリコーディング関係を有します。 LDPCは、「低密度パリティチェック」を意味します。
o Systematic code: a code in which all source symbols are included as part of the encoding symbols of a source block. The RaptorQ code as described herein is a systematic code.
O系統的コード：すべてのソースシンボルは、ソースブロックの符号化シンボルの一部として含まれているコード。本明細書に記載されるようRaptorQコードは組織符号です。
o Encoding Symbol ID (ESI): information that uniquely identifies each encoding symbol associated with a source block for sending and receiving purposes.
O符号化シンボルID（ESI）：一意目的を送受信するためのソースブロックに関連付けられた各符号化シンボルを識別する情報。
o Internal Symbol ID (ISI): information that uniquely identifies each symbol associated with an extended source block for encoding and decoding purposes.
O内部シンボルID（ISI）：一意に符号化及び復号化の目的のために拡張されたソースブロックに関連付けられた各シンボルを識別する情報。
o Arithmetic operations on octets and symbols and matrices: the operations that are used to produce encoding symbols from source symbols and vice versa. See Section 5.7.
その逆ソースシンボルから符号化シンボルを生成するために使用される操作：オクテットとシンボルとマトリクスに演算O。 5.7節を参照してください。
i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y represent values or variables of one type or another, depending on the context.
I、J、U、V、H、D、A、B、D1、A1、B1、V、M、X、Yは、文脈に応じて、一種類または別の値または変数を表します。
X denotes a non-negative integer value that is either an ISI value or an ESI value, depending on the context.
Xは、文脈に応じて、ISI値またはESI値のいずれかである非負の整数値を表します。
ceil(x) denotes the smallest integer that is greater than or equal to x, where x is a real value.
CEIL（X）は、より大きい又はxが実数値であり、X、に等しい最小の整数を表します。
floor(x) denotes the largest integer that is less than or equal to x, where x is a real value.
フロア（x）は、以下、xは実数値であり、Xに等しい最大の整数を表します。
min(x,y) denotes the minimum value of the values x and y, and in general the minimum value of all the argument values.
分（x、y）は値xとyの最小値、およびすべての引数の値の一般的な最小値を示しています。
max(x,y) denotes the maximum value of the values x and y, and in general the maximum value of all the argument values.
MAX（x、y）は、すべての引数の値の最大値を値xとyの最大値であり、一般的です。
i % j denotes i modulo j.
私は、％jはiのJを法表します。
i + j denotes the sum of i and j. If i and j are octets or symbols, this designates the arithmetic on octets or symbols, respectively, as defined in Section 5.7. If i and j are integers, then it denotes the usual integer addition.
私はjはiとjの合計を示して+。 i、jはオクテットまたは記号である場合、セクション5.7で定義されるように、これは、それぞれ、オクテットまたはシンボルに対する演算を指定します。 i、jは整数である場合、それは通常の整数の加算を表します。
i * j denotes the product of i and j. If i and j are octets, this designates the arithmetic on octets, as defined in Section 5.7. If i is an octet and j is a symbol, this denotes the multiplication of a symbol by an octet, as also defined in Section 5.7. Finally, if i and j are integers, i * j denotes the usual product of integers.
私はjはiとjの積を表します*。 i、jはオクテットがある場合は、セクション5.7で定義されているように、これは、オクテットの算術演算を指定します。私はオクテットであり、jはシンボルである場合も、セクション5.7で定義されているように、これは、オクテットでシンボルの乗算を表します。 i、jは整数である場合は最後に、私は、jは整数の通常の製品を意味します*。
a ^^ b denotes the operation a raised to the power b. If a is an octet and b is a non-negative integer, this is understood to mean a*a*...*a (b terms), with '*' being the octet product as defined in Section 5.7.
^^ bは、電力Bに上げ操作を示しています。オクテットであり、bは負でない整数である場合、これはセクション5.7で定義されるように「*」がオクテット生成された状態で、*はA * ... *（B条件）を意味すると理解されます。
u ^ v denotes, for equal-length bit strings u and v, the bitwise exclusive-or of u and v.
U ^ vが等しい長ビット列U及びV、排他的論理和uとvのビット単位のため、です。
Transpose[A] denotes the transposed matrix of matrix A. In this specification, all matrices have entries that are octets.
[A]本明細書では行列Aの転置行列を表す転置、すべての行列はオクテットであるエントリを有しています。
A^^-1 denotes the inverse matrix of matrix A. In this specification, all the matrices have octets as entries, so it is understood that the operations of the matrix entries are to be done as stated in Section 5.7 and A^^-1 is the matrix inverse of A with respect to octet arithmetic.
^^ - 1は、本明細書中の行列Aの逆行列を示し、すべての行列がエントリとしてオクテットを有し、マトリックスエントリの操作はセクション5.7と^^に述べたように行われるべきであることが理解されます - 図1は、オクテット演算に対するAの逆行列です。
K denotes the number of symbols in a single source block.
Kは、単一のソースブロック内のシンボルの数を表します。
K' denotes the number of source plus padding symbols in an extended source block. For the majority of this specification, the padding symbols are considered to be additional source symbols.
K」は、拡張されたソースブロック内のソースプラスパディングシンボルの数を表します。本明細書の大部分を、パディングシンボルは、追加のソースシンボルであると考えられます。
K'_max denotes the maximum number of source symbols that can be in a single source block. Set to 56403.
K'_maxは、単一のソースブロックとすることができるソースシンボルの最大数を示します。 56403に設定します。
L denotes the number of intermediate symbols for a single extended source block.
Lは、単一の拡張ソースブロックの中間シンボルの数を示します。
S denotes the number of LDPC symbols for a single extended source block. These are LT symbols. For each value of K' shown in Table 2 in Section 5.6, the corresponding value of S is a prime number.
Sは、単一の拡張ソースブロックのLDPCシンボルの数を表します。これらは、LTのシンボルです。第5.6節の表2に示すKの各値」のため、Sの対応する値は素数です。
H denotes the number of HDPC symbols for a single extended source block. These are PI symbols.
Hは、単一の拡張ソースブロックのHDPCシンボルの数を表します。これらは、PIのシンボルです。
B denotes the number of intermediate symbols that are LT symbols excluding the LDPC symbols.
Bは、LDPC符号を除いLTシンボルである中間シンボルの数を示します。
W denotes the number of intermediate symbols that are LT symbols. For each value of K' in Table 2 shown in Section 5.6, the corresponding value of W is a prime number.
WはLTシンボルである中間シンボルの数を示します。セクション5.6に示す。表2中のK」の各値に対して、Wの対応する値が素数です。
P denotes the number of intermediate symbols that are PI symbols. These contain all HDPC symbols.
PはPIシンボルである中間シンボルの数を示します。これらはすべて、HDPCシンボルが含まれています。
P1 denotes the smallest prime number greater than or equal to P.
P1は、P以上の最小の素数を表します
U denotes the number of non-HDPC intermediate symbols that are PI symbols.
UはPIシンボルである非HDPC中間シンボルの数を示します。
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 the symbols of the extended source block, where C'[0], C'[1], C'[2], ..., C'[K-1] are the source symbols of the source block and C'[K], C'[K+1], ..., C'[K'-1] are padding symbols.
C [0]、C '[1]、C '[2]、...、C'[K-1]のソースシンボルである」Cは、拡張ソースブロックのシンボルの配列を示し、'ソースブロックとC '[K]、C' [K + 1]、...、C '[K'-1]パディングシンボルです。
V0, V1, V2, V3 denote four arrays of 32-bit unsigned integers, V0[0], V0[1], ..., V0[255]; V1[0], V1[1], ..., V1[255]; V2[0], V2[1], ..., V2[255]; and V3[0], V3[1], ..., V3[255] as shown in Section 5.5.
V0、V1、V2、V3は、32ビット符号なし整数の4つの配列を表し、V0 [0]、V0 [1]、...、V0 [255]。 V1 [0]、V1 [1]、...、V1 [255]。 V2 [0]、V2 [1]、...、V2 [255]。そしてV3 [0]、V3 [1]、...、V3 [255]セクション5.5に示すように。
Rand[y, i, m] denotes a pseudo-random number generator.
ランド[Y、I、m]は、擬似乱数生成器を表します。
Deg[v] denotes a degree generator.
DEGは、[V]程度発生器を表します。
Enc[K', C ,(d, a, b, d1, a1, b1)] denotes an encoding symbol generator.
ENC [K」は、Cは、（D、A、B、D1、A1、B1）]は、符号化シンボル生成器を表します。
Tuple[K', X] denotes a tuple generator function.
タプル[K」、X]はタプルジェネレータ関数を示します。
T denotes the symbol size in octets.
Tは、オクテット内のシンボルの大きさを示しています。
J(K') denotes the systematic index associated with K'.
J（K「）がKに関連付けられた系統的インデックスを示します」。
G denotes any generator matrix.
Gは、任意の生成行列を表します。
I_S denotes the S x S identity matrix.
I_SはS X S単位行列を表します。
This section defines the systematic RaptorQ FEC code.
このセクションでは、体系的RaptorQ FECコードを定義します。
Symbols are the fundamental data units of the encoding and decoding process. For each source block, all symbols are the same size, referred to as the symbol size T. The atomic operations performed on symbols for both encoding and decoding are the arithmetic operations defined in Section 5.7.
シンボルは、符号化および復号化プロセスの基本的なデータ単位です。各ソースブロックについて、すべての記号は同じサイズであり、シンボルサイズTと呼ばれる符号化および復号化の両方のためのシンボルに実行アトミック操作は、セクション5.7で定義された算術演算です。
The basic encoder is described in Section 5.3. The encoder first derives a block of intermediate symbols from the source symbols of a source block. This intermediate block has the property that both source and repair symbols can be generated from it using the same process. The encoder produces repair symbols from the intermediate block using an efficient process, where each such repair symbol is the exclusive-or of a small number of intermediate symbols from the block. Source symbols can also be reproduced from the intermediate block using the same process. The encoding symbols are the combination of the source and repair symbols.
基本的なエンコーダは、セクション5.3に記載されています。エンコーダは、最初のソースブロックのソースシンボルから中間シンボルのブロックを導出します。この中間ブロックは、ソースおよびリペアシンボルの両方が、同じプロセスを使用して、それから生成することができる特性を有しています。エンコーダは、このような各リペアシンボルは、排他的論理和ブロックから中間シンボルの数が少ないのである効率的な方法を用いて中間ブロックからリペアシンボルを生成します。ソースシンボルは、同じプロセスを使用して、中間ブロックから再生することができます。符号化シンボルは、ソースおよびリペアシンボルの組合せです。
An example of a decoder is described in Section 5.4. The process for producing source and repair symbols from the intermediate block is designed so that the intermediate block can be recovered from any sufficiently large set of encoding symbols, independent of the mix of source and repair symbols in the set. Once the intermediate block is recovered, missing source symbols of the source block can be recovered using the encoding process.
デコーダの例は、セクション5.4に記載されています。中間ブロックは、セット内のソースおよびリペアシンボルの組み合わせから独立して符号化シンボルのいずれか十分に大きな組から回収することができるように、中間ブロックからソースおよびリペアシンボルを生成するためのプロセスが設計されています。中間ブロックが回収されると、ソースブロックの欠落したソースシンボルは、符号化プロセスを使用して回収することができます。
Requirements for a RaptorQ-compliant decoder are provided in Section 5.8. A number of decoding algorithms are possible to achieve these requirements. An efficient decoding algorithm to achieve these requirements is provided in Section 5.4.
RaptorQ準拠のデコーダのための要件は、セクション5.8で提供されています。デコードアルゴリズムの数は、これらの要件を達成することが可能です。これらの要件を達成するための効率的な復号化アルゴリズムは、セクション5.4で提供されています。
The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section 5.3. This generator is based on a fixed set of 1024 random numbers that must be available to both sender and receiver. These numbers are provided in Section 5.5. Encoding and decoding operations for RaptorQ use operations on octets. Section 5.7 describes how to perform these operations.
中間体および修復シンボルの構築はセクション5.3に記載の擬似乱数発生器に基づいています。この発電機は、送信者と受信者の両方に利用可能でなければならない1024個の乱数の固定セットに基づいています。これらの数値は、5.5節で提供されています。 RaptorQのエンコードとデコードの操作はオクテットの操作を使用します。 5.7節では、これらの操作を実行する方法について説明します。
Finally, the construction of the intermediate symbols from the source symbols is governed by "systematic indices", values of which are provided in Section 5.6 for specific extended source block sizes between 6 and K'_max = 56403 source symbols. Thus, the RaptorQ code supports source blocks with between 1 and 56403 source symbols.
最後に、ソースシンボルから中間シンボルの構成は、「体系的指標」、6及びK'_max = 56403ソースシンボルとの間の特定の拡張ソースブロックサイズについては、セクション5.6に提供された値によって支配されます。したがって、RaptorQコードは、1〜56403のソースシンボルとソースブロックをサポートします。
For a given source block of K source symbols, for encoding and decoding purposes, the source block is augmented with K'-K additional padding symbols, where K' is the smallest value that is at least K in the systematic index Table 2 of Section 5.6. The reason for padding out a source block to a multiple of K' is to enable faster encoding and decoding and to minimize the amount of table information that needs to be stored in the encoder and decoder.
K個のソースシンボルの所与のソースブロックに対して、符号化及び復号化の目的のために、ソースブロックは、K「は、セクションの系統的インデックステーブル2の少なくともKの最小値であるK'-K追加のパディングシンボルで増強され5.6。 「Kの倍数にソースブロックをパディングする理由は、高速符号化及び復号化を可能にするために、エンコーダとデコーダに記憶される必要がテーブル情報の量を最小にすることです。
For purposes of transmitting and receiving data, the value of K is used to determine the number of source symbols in a source block, and thus K needs to be known at the sender and the receiver. In this case, the sender and receiver can compute K' from K and the K'-K padding symbols can be automatically added to the source block without any additional communication. The encoding symbol ID (ESI) is used by a sender and receiver to identify the encoding symbols of a source block, where the encoding symbols of a source block consist of the source symbols and the repair symbols associated with the source block. For a source block with K source symbols, the ESIs for the source symbols are 0, 1, 2, ..., K-1, and the ESIs for the repair symbols are K, K+1, K+2, .... Using the ESI for identifying encoding symbols in transport ensures that the ESI values continue consecutively between the source and repair symbols.
データの送受信の目的のために、Kの値は、ソースブロック内のソースシンボルの数を決定するために使用され、したがって、Kは、送信側と受信側で知られている必要があります。この場合には、送信者と受信者がKからK「を計算することができ、K'-Kパディングシンボルは、自動的に追加の通信なしでソースブロックに追加することができます。符号化シンボルID（ESI）は、ソースブロックの符号化シンボルは、ソースシンボル、ソースブロックに関連付けられたリペアシンボルから成るソースブロックの符号化シンボルを識別するために、送信側と受信側で使用されます。 K個のソースシンボルとソースブロックのソースシンボルについてのESIは、0、1、2、...、K-1、およびリペアシンボルのためのESIは、K、K + 1、K + 2であります.. ..輸送に符号化シンボルを識別するためのESIを使用するESIの値がソースおよび修復シンボルの間に連続し続けることを保証します。
For purposes of encoding and decoding data, the value of K' derived from K is used as the number of source symbols of the extended source block upon which encoding and decoding operations are performed, where the K' source symbols consist of the original K source symbols and an additional K'-K padding symbols. The Internal Symbol ID (ISI) is used by the encoder and decoder to identify the symbols associated with the extended source block, i.e., for generating encoding symbols and for decoding. For a source block with K original source symbols, the ISIs for the original source symbols are 0, 1, 2, ..., K-1, the ISIs for the K'-K padding symbols are K, K+1, K+2, ..., K'-1, and the ISIs for the repair symbols are K', K'+1, K'+2, .... Using the ISI for encoding and decoding allows the padding symbols of the extended source block to be treated the same way as other source symbols of the extended source block. Also, it ensures that a given prefix of repair symbols are generated in a consistent way for a given number K' of source symbols in the extended source block, independent of K.
符号化および復号化データの目的のために、Kの値ソースシンボル元のKのソースから成る「K由来のK符号化および復号化動作が実行される際に、拡張ソースブロックのソースシンボルの数として使用される」がシンボルと追加のK'-Kのパディングシンボル。内部シンボルID（ISI）は、すなわち、符号化シンボルを生成するためおよび復号するために、拡張されたソースブロックに関連付けられたシンボルを識別するために、エンコーダおよびデコーダによって使用されます。 K元のソースシンボルとソースブロックについて、ISISオリジナルソースシンボルは、0、1、2、...、K-1は、K'-KパディングシンボルのISISはK、K + 1、Kであります+2、...、K'-1、およびISISはリペアシンボルについてK」、K 『+ 1、K』 + 2、...は、符号化および復号化のためのISIを使用することのパディングシンボルを可能にしています拡張されたソースブロックは、拡張されたソースブロックの他のソースシンボルと同じように処理されます。また、Kの独立した、リペアシンボルの所定の接頭辞は、拡張ソースブロック内のソースシンボルの所定の数K」の一貫した方法で生成されることを確実にします
The relationship between the ESIs and the ISIs is simple: the ESIs and the ISIs for the original K source symbols are the same, the K'-K padding symbols have an ISI but do not have a corresponding ESI (since they are symbols that are neither sent nor received), and a repair symbol ISI is simply the repair symbol ESI plus K'-K. The translation between ESIs (used to identify encoding symbols sent and received) and the corresponding ISIs (used for encoding and decoding), as well as determining the proper padding of the extended source block with padding symbols (used for encoding and decoding), is the internal responsibility of the RaptorQ encoder/decoder.
ESIおよびISISとの関係は単純である：元のKのソースシンボルのためのESIおよびISISが同じで、K'-Kパディングシンボルは、ISIを有するが、それらはシンボルであるので、対応するESIを（持っていません送信されたことも、受信した）、および修復シンボルISIは単にリペアシンボルESIプラスK'-Kでもありません。 （送信および受信符号化シンボルを識別するために使用される）のESI及び対応イシス（符号化および復号化に使用される）との間の変換、ならびに（符号化および復号化に使用される）パディングシンボルを有する拡張ソースブロックの適切なパディングを決定することは、ありますRaptorQエンコーダ/デコーダの内部責任。
The systematic RaptorQ encoder is used to generate any number of repair symbols from a source block that consists of K source symbols placed into an extended source block C'. Figure 4 shows the encoding overview.
系統的RaptorQエンコーダは、拡張されたソースブロックC」に入れK個のソースシンボルから成るソースブロックからリペアシンボルの任意の数を生成するために使用されます。図4は、符号化の概要を示しています。
The first step of encoding is to construct an extended source block by adding zero or more padding symbols such that the total number of symbols, K', is one of the values listed in Section 5.6. Each padding symbol consists of T octets where the value of each octet is zero. K' MUST be selected as the smallest value of K' from the table of Section 5.6 that is greater than or equal to K.
符号化の最初のステップは、シンボルの総数は、K」は、セクション5.6に列挙された値のいずれかであるように、ゼロ以上のパディングシンボルを追加することによって拡張ソースブロックを構築することです。各パディングシンボルは、各オクテットの値がゼロであるTオクテットで構成されています。 Kは、K以上である第5.6節の表からK「の最小値として選択されなければなりません」
-----------------------------------------------------------+
| |
| +-----------+ +--------------+ +-------------+ |
C' | | | C' | Intermediate | C | | |
----+--->| Padding |--->| Symbol |--->| Encoding |--+-->
K | | | K' | Generation | L | | |
| +-----------+ +--------------+ +-------------+ |
| | (d,a,b, ^ |
| | d1,a1,b1)| |
| | +------------+ |
| | K' | Tuple | |
| +----------------------------->| | |
| | Generation | |
| +------------+ |
| ^ |
+-------------------------------------------------+--------+
|
ISI X
Figure 4: Encoding Overview
図4：エンコードの概要
Let C'[0], ..., C'[K-1] denote the K source symbols.
C '[0]、...、C' [K-1]がK個のソースシンボルを示すものとします。
Let C'[K], ..., C'[K'-1] denote the K'-K padding symbols, which are all set to zero bits. Then, C'[0], ..., C'[K'-1] are the symbols of the extended source block upon which encoding and decoding are performed.
C '[K]、...、C' [K'-1]が全てゼロのビットに設定されているK'-Kパディングシンボルを表すものとします。次いで、C「[0]、...、C」符号化および復号化が実行される際に、拡張ソースブロックのシンボルがある[K'-1]。
In the remainder of this description, these padding symbols will be considered as additional source symbols and referred to as such. However, these padding symbols are not part of the encoding symbols, i.e., they are not sent as part of the encoding. At a receiver, the value of K' can be computed based on K, then the receiver can insert K'-K padding symbols at the end of a source block of K' source symbols and recover the remaining K source symbols of the source block from received encoding symbols.
この説明の残りの部分では、これらのパディングシンボルは、追加のソースシンボルとしてみなされ、そのように呼ばれます。しかしながら、これらのパディングシンボルは符号化シンボルの一部ではない、すなわち、それらは、符号化の一部として送信されていません。受信機において、Kの値はK「に基づいて計算することができ、その後、受信機は、K個のソースブロックの終わりにK'-Kパディングシンボルを挿入することができ」ソースシンボル、ソースブロックの残りのK個のソースシンボルを回復受信符号化シンボルから。
The second step of encoding is to generate a number, L > K', of intermediate symbols from the K' source symbols. In this step, K' source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated using the Tuple[] generator as described in Section 5.3.5.4. The K' source tuples and the ISIs associated with the K' source symbols are used to determine L intermediate symbols C[0], ..., C[L-1] from the source symbols using an inverse encoding process. This process can be realized by a RaptorQ decoding process.
符号化の第二段階は、ソースシンボル「Kから中間シンボルの、」数、L> Kを生成することです。このステップにおいて、K」ソースタプル（D [0]、[0]、[0]、D1 [0]、A [0]、B1 [0] B）、...、（D [K'- 1]、[K'-1]、B [K'-1]、D1 [K'-1]、A [K'-1]、B1 [K'-1]）タプルを用いて生成されます[]セクション5.3.5.4で説明したように発電機。 K「ソースタプルとKに関連付けISIS」ソースシンボルを逆符号化処理を使用してソースシンボルからL個の中間シンボルC [0]、...、C [L-1]を決定するために使用されます。このプロセスは、RaptorQ復号処理により実現することができます。
Certain "pre-coding relationships" must hold within the L intermediate symbols. Section 5.3.3.3 describes these relationships. Section 5.3.3.4 describes how the intermediate symbols are generated from the source symbols.
特定の「プリコーディング関係」L中間シンボルの中に保持する必要があります。セクション5.3.3.3は、これらの関係を説明しています。セクション5.3.3.4は、中間シンボルは、ソースシンボルから生成されている方法を説明します。
Once the intermediate symbols have been generated, repair symbols can be produced. For a repair symbol with ISI X > K', the tuple of non-negative integers (d, a, b, d1, a1, b1) can be generated, using the Tuple[] generator as described in Section 5.3.5.4. Then, the (d, a, b, d1, a1, b1) tuple and the ISI X are used to generate the corresponding repair symbol from the intermediate symbols using the Enc[] generator described in Section 5.3.5.3. The corresponding ESI for this repair symbol is then X-(K'-K). Note that source symbols of the extended source block can also be generated using the same process, i.e., for any X < K', the symbol generated using this process has the same value as C'[X].
中間シンボルが生成されたら、リペアシンボルを製造することができます。セクション5.3.5.4に記載されるようにISI X> K」とリペアシンボルに対して、非負整数（D、A、B、D1、A1、B1）のタプルはタプル[]ジェネレータを使用して、生成することができます。次いで、（D、A、B、D1、A1、B1）タプルとISI Xはセクション5.3.5.3に記載なお、Enc []ジェネレータを使用して中間シンボルから対応するリペアシンボルを生成するために使用されます。このリペアシンボルに対応するESIは、次にX-（K'-K）です。拡張されたソースブロックのソースシンボルは、任意のX <Kのために[X]「このプロセスを使用して生成されたシンボルCと同じ値を有する」、すなわち、同じプロセスを使用して生成することができます。
This 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], where L > K' is defined in Section 5.3.3.3. The intermediate symbols are uniquely defined by two sets of constraints:
この符号化ステップは、L中間シンボルC [0]、...、C [L-1]のソースシンボルC '[0]、...、C' [からK'-を生成するプリコーディングステップであります1]、L> K」は、セクション5.3.3.3で定義されます。中間シンボルは、一意制約の二組によって定義されます。
1. The intermediate symbols are related to the source symbols by a set of source symbol tuples and by the ISIs of the source symbols. The generation of the source symbol tuples is defined in Section 5.3.3.2 using the Tuple[] generator as described in Section 5.3.5.4.
1.中間シンボルは、ソースシンボルタプルのセットによって、ソースシンボルのISISによりソースシンボルに関連しています。セクション5.3.5.4に記載されるようにソースシンボルタプルの生成は、タプル[]ジェネレータを使用して、セクション5.3.3.2で定義されています。
2. A number of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section 5.3.3.3.
2.関係は中間シンボル自体内に保持するプリコーディングの数。これらは、セクション5.3.3.3で定義されています。
The generation of the L intermediate symbols is then defined in Section 5.3.3.4.
L中間シンボルの生成は、その後、セクション5.3.3.4で定義されています。
Each of the K' source symbols is associated with a source symbol tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K'. The source symbol tuples are determined using the Tuple[] generator defined in Section 5.3.5.4 as:
K」のソースシンボルの各々は、0 <= Xのソースシンボルタプル（D [X]、[X]、B [X]、D1 [X]、A [X]、B1 [X]）に関連付けられています<K」。ソースシンボルの組は、以下のように、セクション5.3.5.4で定義されたタプル[]ジェネレータを使用して決定されます。
For each X, 0 <= X < K'
各Xは、0 <= X <K」
(d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X]
（D [X]、[X]、B [X]、D1 [X]、A [X]、B1 [X]）=タプル[K、X]
The pre-coding relationships amongst the L intermediate symbols are defined by requiring that a set of S+H linear combinations of the intermediate symbols evaluate to zero. There are S LDPC and H HDPC symbols, and thus L = K'+S+H. Another partition of the L intermediate symbols is into two sets, one set of W LT symbols and another set of P PI symbols, and thus it is also the case that L = W+P. The P PI symbols are treated differently than the W LT symbols in the encoding process. The P PI symbols consist of the H HDPC symbols together with a set of U = P-H of the other K' intermediate symbols. The W LT symbols consist of the S LDPC symbols together with W-S of the other K' intermediate symbols. The values of these parameters are determined from K' as described below, where H(K'), S(K'), and W(K') are derived from Table 2 in Section 5.6.
Lの間でプリコーディング関係中間シンボルは中間シンボルのS + H線形結合の集合がゼロに評価することを要求することによって定義されます。 S LDPC及びH HDPCシンボル、従ってL = K '+ S + Hが存在します。 L個の中間シンボルの別のパーティションは、二組の一W LTシンボルのセットとPのPIシンボルの別のセットにあり、したがって、それはまた、場合L = W + Pです。 PのPIシンボルは、符号化処理におけるW LTシンボルとは異なる処理されます。 PのPIシンボルは、他のK」中間シンボルのU = P-Hの組と一緒にH HDPCシンボルから成ります。 W LTシンボルは、他のK」中間シンボルのW-Sと共にS LDPCシンボルから成ります。これらのパラメータの値が「（S（K 『）、及びW（K』）5.6項の表2に由来するH K）は、以下に記載のように、」Kから決定されます。
Let
してみましょう
o S = S(K')
O S = Sで（K '）
o H = H(K')
O H = H（K '）
o W = W(K')
O W = W（K '）
o L = K' + S + H
O L = K」+ S + H
o P = L - W
O P = L - W
o P1 denote the smallest prime number greater than or equal to P.
O P1はP.以上の最小の素数を表します
o U = P - H
O U = P - H
o B = W - S
O B = W - S
o C[0], ..., C[B-1] denote the intermediate symbols that are LT symbols but not LDPC symbols.
O C [0]、...、C [B-1] LTシンボルなくLDPCシンボルである中間シンボルを示します。
o C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT symbols.
O C [B]、...、C [B + S-1]もLTシンボルであるS LDPCシンボルを表します。
o C[W], ..., C[W+U-1] denote the intermediate symbols that are PI symbols but not HDPC symbols.
O C [W]、...、C [W + U-1]はPIシンボルなくHDPCシンボルで中間シンボルを示します。
o C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI symbols.
O C [L-H]、...、C [L-1]はPIシンボルであるH HDPCシンボルを表します。
The first set of pre-coding relations, called LDPC relations, is described below and requires that at the end of this process the set of symbols D[0] , ..., D[S-1] are all zero:
LDPC関係と呼ばれるプリコーディング関係の第1のセットは、以下に記載し、このプロセスの終了シンボルDの組で[0]、...、D [S-1]が全てゼロであることを必要とされています。
o Initialize the symbols D[0] = C[B], ..., D[S-1] = C[B+S-1].
OシンボルD [0] = C [B]、...、D [S-1] = C [B + S-1]を初期化します。
o For i = 0, ..., B-1 do
私は= 0、...、B-1が行うため、O
* a = 1 + floor(i/S)
* A = 1つの+床（I / S）
* b = i % S
* B = I％S
* D[b] = D[b] + C[i]
* D [B] = D [B] + C [I]
* b = (b + a) % S
* B =（B + A）％S
* D[b] = D[b] + C[i]
* D [B] = D [B] + C [I]
* b = (b + a) % S
* B =（B + A）％S
* D[b] = D[b] + C[i]
* D [B] = D [B] + C [I]
o For i = 0, ..., S-1 do
私は= 0、...、S-1が行うため、O
* a = i % P
* A = I％のP
* b = (i+1) % P
* B =（I + 1）％P
* D[i] = D[i] + C[W+a] + C[W+b]
* D [I] = D [I] + C [W + A] + C [W + B]
Recall that the addition of symbols is to be carried out as specified in Section 5.7.
シンボルの追加は、セクション5.7で指定されるように行われるべきであることを思い出してください。
Note that the LDPC relations as defined in the algorithm above are linear, so there exists an S x B matrix G_LDPC,1 and an S x P matrix G_LDPC,2 such that
上記のアルゴリズムで定義されているLDPC関係は線形であるので、そのような2 SのX BマトリックスG_LDPC、1およびS X P行列G_LDPCを、そこに存在することに注意してください
G_LDPC,1 * Transpose[(C[0], ..., C[B-1])] + G_LDPC,2 * Transpose(C[W], ..., C[W+P-1]) + Transpose[(C[B], ..., C[B+S-1])] = 0
G_LDPC、1 *トランスポーズ[（C [0]、...、C [B-1]）] + G_LDPC、2 *トランスポーズ（C [W]、...、C [W + P-1]）+ [（C [B]、...、C [B + S-1]）] = 0を転置
(The matrix G_LDPC,1 is defined by the first loop in the above algorithm, and G_LDPC,2 can be deduced from the second loop.)
（マトリックスG_LDPCは、1は最初、上記のアルゴリズムのループ、及びG_LDPCによって定義され、2は、第2のループから推定することができます。）
The second set of relations among the intermediate symbols C[0], ..., C[L-1] are the HDPC relations and they are defined as follows:
中間シンボル間の関係の第二のセットC [0]、...、C [L-1] HDPC関係があり、次のように、それらが定義されます。
Let
してみましょう
o alpha denote the octet represented by integer 2 as defined in Section 5.7.
Oアルファセクション5.7で定義されるように整数2で表されるオクテットを表します。
o MT denote an H x (K' + S) matrix of octets, where for j=0, ..., K'+S-2, the entry MT[i,j] is the octet represented by the integer 1 if i= Rand[j+1,6,H] or i = (Rand[j+1,6,H] + Rand[j+1,7,H-1] + 1) % H, and MT[i,j] is the zero element for all other values of i, and for j=K'+S-1, MT[i,j] = alpha^^i for i=0, ..., H-1.
MTは、+ S-2、エントリーMT [I、J]が場合整数1で表されるオクテットであるH×（K 'J = 0、...、Kオクテット+ S）行列を、' 意味O I =ランド[J + 1,6、H]またはI =（RAND [J + 1,6、H] +ランド[J + 1,7、H-1] + 1）％H、およびMT [I、 j]は、iの他のすべての値に対してゼロ要素であり、jに対する= K '+ S-1、MT [I、J] =アルファ^^ iについてi = 0、...、H-1。
o GAMMA denote a (K'+S) x (K'+S) matrix of octets, where
O GAMMAは場合、オクテット（K '+ S）×（K' + S）行列を表します
GAMMA[i,j] =
GAMMA [I、J] =
alpha ^^ (i-j) for i >= j,
アルファ^^（I-J）は、i> = jについて、
0 otherwise.
それ以外の場合は0。
Then, the relationship between the first K'+S intermediate symbols C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1] is given by:
第K '+ S中間シンボルC [0]、...、C [K' + S-1]とH HDPCシンボルC [K '+ S]の間、次に、関係、...、C [ K '+ S + H-1]によって与えられます。
Transpose[C[K'+S], ..., C[K'+S+H-1]] + MT * GAMMA * Transpose[C[0], ..., C[K'+S-1]] = 0,
[C [K '+ S]、...、C [K' + S + H-1]]転置+ MT * GAMMA *トランスポーズ[C [0]、...、C [K '+ S-1 ]] = 0、
where '*' represents standard matrix multiplication utilizing the octet multiplication to define the multiplication between a matrix of octets and a matrix of symbols (in particular, the column vector of symbols), and '+' denotes addition over octet vectors.
ここで、「*」（シンボル特に、列ベクトル）オクテットのマトリックスシンボルの行列間の乗算を定義するオクテット乗算を利用する標準的な行列の乗算を表し、「+」オクテットベクター上加算を表します。
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'[X] = Enc[K', (C[0], ..., C[L-1]), (d[X], a[X], b[X], d1[X],
a1[X], b1[X])], for all X, 0 <= X < K',
where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X], Tuple[] is defined in Section 5.3.5.4, and Enc[] is described in Section 5.3.5.3.
（D [X]、[X]、B [X]、D1 [X]、A [X]、B1 [X]））=タプル[K」、X]は、タプル[]は、セクション5.3で定義されます.5.4、そしてなお、Enc []は、セクション5.3.5.3に記載されています。
2. The L intermediate symbols C[0], C[1], ..., C[L-1] satisfy the pre-coding relationships defined in Section 5.3.3.3.
2. L中間シンボルC [0]、C [1]、...、C [L-1]は、セクション5.3.3.3で定義されたプリコーディングの関係を満たします。
This section describes a possible method for calculation of the L intermediate symbols C[0], C[1], ..., C[L-1] satisfying the constraints in Section 5.3.3.4.1.
このセクションは、セクション5.3.3.4.1に制約を満たすL個の中間シンボルC [0]、C [1]、...、C [L-1]を計算するための可能な方法を記載しています。
The L intermediate symbols can be calculated as follows:
次のようにL個の中間シンボルを計算することができます。
Let
してみましょう
o C denote the column vector of the L intermediate symbols, C[0], C[1], ..., C[L-1].
O Cは、L個の中間シンボル、C [0]、C [1]、...、C [L-1]の列ベクトルを表します。
o D denote the column vector consisting of S+H zero symbols followed by the K' source symbols C'[0], C'[1], ..., C'[K'-1].
O D S + HからK 'のソースシンボルC '[0]、C'[1]、...、C' [K'-1]続いてゼロシンボルからなる列ベクトルを表します。
Then, the above constraints define an L x L matrix A of octets such that:
次に、上記の制約は、そのオクテットのL X L行列Aを定義します。
A*C = D
*はC = D
The matrix A can be constructed as follows:
次のように行列Aを構築することができます。
Let
してみましょう
o G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices as defined in Section 5.3.3.3.
セクション5.3.3.3で定義されるように、O G_LDPC、1及びG_LDPC、2がS、X B及びSのX P行列です。
o G_HDPC be the H x (K'+S) matrix such that
O G_HDPCようにH×（K '+ S）行列であります
G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S],
..., C[L-1]),
i.e., G_HDPC = MT*GAMMA
すなわち、G_HDPC = MT * GAMMA
o I_S be the S x S identity matrix
O I_S S X S恒等行列であります
o I_H be the H x H identity matrix
O I_H H X H恒等行列であります
o G_ENC be the K' x L matrix such that
O G_ENCそのようなK」のx L行列であります
G_ENC * Transpose[(C[0], ..., C[L-1])] =
Transpose[(C'[0],C'[1], ...,C'[K'-1])], i.e., G_ENC[i,j] = 1 if and only if C[j] is included in the
symbols that are summed to produce Enc[K', (C[0], ..., C[L-1]),
(d[i], a[i], b[i], d1[i], a1[i], b1[i])] and G_ENC[i,j] = 0
otherwise.
Then
それから
o The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2.
Aの第S行がG_LDPC、1に等しく、oを| I_S | G_LDPC、2。
o The next H rows of A are equal to G_HDPC | I_H.
| O Aの次のH行はG_HDPCに等しいですI_H。
o The remaining K' rows of A are equal to G_ENC.
Aの残りのK」行oをG_ENCに等しいです。
The matrix A is depicted in Figure 5 below:
行列Aは、以下の図5に示されています。
B S U H
+-----------------------+-------+------------------+
| | | |
S | G_LDPC,1 | I_S | G_LDPC,2 |
| | | |
+-----------------------+-------+----------+-------+
| | |
H | G_HDPC | I_H |
| | |
+------------------------------------------+-------+
| |
| |
K' | G_ENC |
| |
| |
+--------------------------------------------------+
Figure 5: The Matrix A
図5：マトリックスA
The intermediate symbols can then be calculated as:
中間シンボルは次のように計算することができます。
C = (A^^-1)*D
C =（^^ - 1）* D
The source tuples are generated such that for any K' matrix A has full rank and is therefore invertible. This calculation can be realized by applying a RaptorQ 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の完全なランクを有し、したがって、可逆であるように生成されます。この計算は、L個の中間シンボルC [0を生成するK 'のソースシンボルC '[0]、C'[1]、...、C' [K'-1]にRaptorQ復号化プロセスを適用することによって実現することができます]、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.4 be used.
効率的にソースシンボルから中間シンボルを生成するために、そのような第5.4節に記載されているような効率的なデコーダの実装を使用することが推奨されます。
In the second encoding step, the repair symbol with ISI X (X >= K') is generated by applying the generator Enc[K', (C[0], C[1], ..., C[L-1]), (d, a, b, d1, a1, b1)] defined in Section 5.3.5.3 to the L intermediate symbols C[0], C[1], ..., C[L-1] using the tuple (d, a, b, d1, a1, b1)=Tuple[K',X].
第2の符号化ステップでは、ISI X（X> = K '）との修復シンボルは、（C [0]、C [1]、...、C [L-1、ジェネレータなお、Enc [Kを適用することによって生成されます'使用]）、（D、A、B、D1、A1、B1）] Lにセクション5.3.5.3で定義された中間シンボルC [0]、C [1]、...、C [L-1]タプル（D、A、B、D1、A1、B1）=タプル[K」、X]。
The random number generator Rand[y, i, m] is defined as follows, where y is a non-negative integer, i is a non-negative integer less than 256, and m is a positive integer, and the value produced is an integer between 0 and m-1. Let V0, V1, V2, and V3 be the arrays provided in Section 5.5.
乱数発生器yは非負の整数であるランド[Y、I、m]は次のように定義されているが、私は256未満の非負整数であり、mは正の整数であり、生成される値であります0からM-1までの整数。 V0、V1、V2、V3とは、セクション5.5で提供さの配列とします。
Let
してみましょう
o x0 = (y + i) mod 2^^8
X0 = O（Y + I）MOD 2 ^^ 8
o x1 = (floor(y / 2^^8) + i) mod 2^^8
O×1 =（床（Y / 2 ^^ 8）+ I）MOD 2 ^^ 8
o x2 = (floor(y / 2^^16) + i) mod 2^^8
O×2 =（床（Y / 2 ^^ 16）+ I）MOD 2 ^^ 8
o x3 = (floor(y / 2^^24) + i) mod 2^^8
O×3 =（床（Y / 2 ^^ 24）+ I）MOD 2 ^^ 8
Then
それから
Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m
ランド[Y、I、M] =（V0 [X0] ^ V1 [X1] ^ V2 [X2] ^ V3 [X3]）％mを
The degree generator Deg[v] is defined as follows, where v is a non-negative integer that is less than 2^^20 = 1048576. Given v, find index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] = min(d, W-2). Recall that W is derived from K' as described in Section 5.3.3.3.
度生成゜以下のようにVがVが与えられる2未満^^ 20 = 1048576である非負の整数である、[V]は、定義され、1例えば[D-1] F <=ことをテーブルのインデックスdを見つけます。 V <F [D]、およびDEG [V] =分（D、W-2）を設定します。セクション5.3.3.3に記載されるように、W「はK由来であることを想起されたいです。
+---------+---------+---------+---------+
| Index d | f[d] | Index d | f[d] |
+---------+---------+---------+---------+
| 0 | 0 | 1 | 5243 |
+---------+---------+---------+---------+
| 2 | 529531 | 3 | 704294 |
+---------+---------+---------+---------+
| 4 | 791675 | 5 | 844104 |
+---------+---------+---------+---------+
| 6 | 879057 | 7 | 904023 |
+---------+---------+---------+---------+
| 8 | 922747 | 9 | 937311 |
+---------+---------+---------+---------+
| 10 | 948962 | 11 | 958494 |
+---------+---------+---------+---------+
| 12 | 966438 | 13 | 973160 |
+---------+---------+---------+---------+
| 14 | 978921 | 15 | 983914 |
+---------+---------+---------+---------+
| 16 | 988283 | 17 | 992138 |
+---------+---------+---------+---------+
| 18 | 995565 | 19 | 998631 |
+---------+---------+---------+---------+
| 20 | 1001391 | 21 | 1003887 |
+---------+---------+---------+---------+
| 22 | 1006157 | 23 | 1008229 |
+---------+---------+---------+---------+
| 24 | 1010129 | 25 | 1011876 |
+---------+---------+---------+---------+
| 26 | 1013490 | 27 | 1014983 |
+---------+---------+---------+---------+
| 28 | 1016370 | 29 | 1017662 |
+---------+---------+---------+---------+
| 30 | 1048576 | | |
+---------+---------+---------+---------+
Table 1: Defines the Degree Distribution for Encoding Symbols
表1：符号化シンボルのための次数分布を定義します
The encoding symbol generator Enc[K', (C[0], C[1], ..., C[L-1]), (d, a, b, d1, a1, b1)] takes the following inputs:
符号化シンボル生成なお、Enc [K」、（C [0]、C [1]、...、C [L-1]）、（D、A、B、D1、A1、B1）は、以下の入力を受け取り：
o K' is the number of source symbols for the extended source block. Let L, W, B, S, P, and P1 be derived from K' as described in Section 5.3.3.3.
O K」は、拡張されたソースブロックのソースシンボルの数です。セクション5.3.3.3に記載されているように、Lは、W、B、S、P、及びP1「はKに由来することができます。
o (C[0], C[1], ..., C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section 5.3.3.4.
O（C [0]、C [1]、...、C [L-1]）はセクション5.3.3.4に記載されるように生成されたL個の中間シンボル（サブシンボル）のアレイです。
o (d, a, b, d1, a1, b1) is a source tuple determined from ISI X using the Tuple[] generator defined in Section 5.3.5.4, whereby
O（D、A、B、D1、A1、B1）はそれによって、セクション5.3.5.4で定義されたタプル[]ジェネレータを使用して、ISI Xから決定ソースタプルであります
* d is a positive integer denoting an encoding symbol LT degree
* DエンコーディングシンボルLT度を表す正の整数であります
* a is a positive integer between 1 and W-1 inclusive
* Aが1と包括W-1との間の正の整数であります
* b is a non-negative integer between 0 and W-1 inclusive
* bが0で包括的なW-1との間の負でない整数であります
* d1 is a positive integer that has value either 2 or 3 denoting an encoding symbol PI degree
* D1は符号シンボルPI度を示す値のいずれか2または3を有する正の整数であります
* a1 is a positive integer between 1 and P1-1 inclusive
* A1は1とP1-1の正の整数であります
* b1 is a non-negative integer between 0 and P1-1 inclusive
* B1は0とP1-1までの間の負でない整数であります
The encoding symbol generator produces a single encoding symbol as output (referred to as result), according to the following algorithm:
符号化シンボル生成器は、次のアルゴリズムに従って、（結果と呼ぶ）出力として単一の符号化シンボルを生成します。
o result = C[b]
O結果= C [B]
o For j = 1, ..., d-1 do
J = 1の場合、O、...、D-1を行います
* b = (b + a) % W
* B =（B + A）％のW
* result = result + C[b]
*結果=結果C + [B]
o While (b1 >= P) do b1 = (b1+a1) % P1
（B1> = P）は、B1 =（B1 + A1）％のP1を行う一方で、O
o result = result + C[W+b1]
O結果=結果C + [W + B1]
o For j = 1, ..., d1-1 do
Oについては、J = 1、...、D1-1 DO
* b1 = (b1 + a1) % P1
* B1 =（B1 + A1）％のP1
* While (b1 >= P) do b1 = (b1+a1) % P1
*（B1> = P）は、B1 =（B1 + A1）％のP1を実行している間
* result = result + C[W+b1]
*結果=結果C + [W + B1]
o Return result
O戻り結果
The tuple generator Tuple[K',X] takes the following inputs:
タプル生成タプル[K」、Xは、以下の入力を受け取り：
o K': the number of source symbols in the extended source block
O K '：拡張されたソースブロック内のソースシンボルの数
o X: an ISI
X：等しい場合
Let
してみましょう
o L be determined from K' as described in Section 5.3.3.3
セクション5.3.3.3に記載されるように、O L「はKから決定すること
o J = J(K') be the systematic index associated with K', as defined in Table 2 in Section 5.6
第5.6節の表2で定義されるように、O J = J（K「）は、Kに関連付けられた系統的指標です」
The output of the tuple generator is a tuple, (d, a, b, d1, a1, b1), determined as follows:
タプル生成器の出力は以下のように決定タプル、（D、A、B、D1、A1、B1）、です。
o A = 53591 + J*997
O A = 53591 + 997 * J
o if (A % 2 == 0) { A = A + 1 }
O IF（％2 == 0）{A = A + 1}
o B = 10267*(J+1)
O B = 10267 *（J + 1）
o y = (B + X*A) % 2^^32
O Y =（B + X * A）％2 ^^ 32
o v = Rand[y, 0, 2^^20]
V =縁O [Y、0、2 ^^ 20]
o d = Deg[v]
及びd =゜[V]
o a = 1 + Rand[y, 1, W-1]
A = A + 1ランド[j、1、-1]
o b = Rand[y, 2, W]
入出力B =ランド[Y 2、W]
o If (d < 4) { d1 = 2 + Rand[X, 3, 2] } else { d1 = 2 }
O IF（D <4）{D1 = 2 +ランド[X、3、2]}他{D1 = 2}
o a1 = 1 + Rand[X, 4, P1-1]
O = 1つの+ A1エッジ[X、4、P1-1]
o b1 = Rand[X, 5, P1]
OエッジB1 = [X、5、P1]
This section describes an efficient decoding algorithm for the RaptorQ code introduced in this specification. Note that each received encoding symbol is a known linear combination of the intermediate symbols. So, each received encoding symbol provides a linear equation among the intermediate symbols, which, together with the known linear pre-coding relationships amongst the intermediate symbols, gives a system of linear equations. Thus, any algorithm for solving systems of linear 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.
このセクションでは、本明細書に導入RaptorQコードのための効率的な復号アルゴリズムを記述する。それぞれが符号化シンボルは中間シンボルの既知の線形結合で受信することに注意してください。だから、各符号化シンボルが一緒に中間シンボルの間で既知の線形プリコーディングの関係を用いて、線形方程式のシステムを提供し、中間シンボル、のうち線形方程式を提供しました。従って、線型方程式系を解くためのいかなるアルゴリズムが正常に中間シンボルひいてはソースシンボルを復号することができます。しかし、選択されたアルゴリズムは、復号化の計算効率に大きな影響を有します。
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 and the number K' of source symbols in the extended source block.
デコーダは、それがシンボルサイズ、T、およびソースブロック内のシンボルの数Kと拡張ソースブロック内のソースシンボルの数K」を含む、復号化することにあるソースブロックの構造を知っているものとします。
From the algorithms described in Section 5.3, the RaptorQ decoder can calculate the total number L = K'+S+H of intermediate symbols and determine how they were generated from the extended source block to be decoded. In this description, it is assumed that the received encoding symbols for the extended source block to be decoded are passed to the decoder. Furthermore, for each such encoding symbol, it is assumed that the number and set of intermediate symbols whose sum is equal to the encoding symbol are passed to the decoder. In the case of source symbols, including padding symbols, the source symbol tuples described in Section 5.3.3.2 indicate the number and set of intermediate symbols that sum to give each source symbol.
セクション5.3で説明したアルゴリズムから、RaptorQデコーダは総数L =中間シンボルのK '+ S + Hを計算し、それらが復号される拡張ソースブロックから生成されたかを決定することができます。この説明では、拡張されたソースブロックに関する受信符号化シンボルはデコーダに渡され復号化されることが想定されます。さらに、このような各符号化シンボルに対して、それが想定される和の符号化シンボルに等しい中間シンボルの数およびセットがデコーダに渡されること。パディングシンボルを含むソースシンボルの場合には、セクション5.3.3.2に記述されたソースシンボルタプルは番号を示し、合計が各ソースシンボルを与えるために、中間シンボルのセット。
Let N >= K' be the number of received encoding symbols to be used for decoding, including padding symbols for an extended source block, and let M = S+H+N. Then, with the notation of Section 5.3.3.4.2, we have A*C = D.
Nは> = K」は、拡張ソースブロックのパディングシンボルを含む復号化のために使用される受信符号化シンボルの数であり、及びM = S + H + Nをさせましょう。その後、セクション5.3.3.4.2の表記で、我々は*のC = Dを持っています
Decoding an extended 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 is L. Once C has been decoded, missing source symbols can be obtained by using the source symbol tuples to determine the number and set of intermediate symbols that must be summed to obtain each missing source symbol.
拡張されたソースブロックを復号化することは、使用して、CはCが復号された後及びAのランクがLである場合にのみ、不足しているソースシンボルを得ることができれば復号化することができることは明らかである既知AおよびDから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 x L identity matrix. The decoding schedule consists of the sequence of row operations and row and column reorderings during the Gaussian elimination process, and it only depends on A and not on D.
Cを復号化するための最初のステップは、復号化のスケジュールを形成することです。このステップでは、Aは、（行操作と行と列reorderingsを使用して）ガウスの消去法を使用して変換され、M廃棄後 - LのX L恒等行列に、L行を。復号化スケジュールは、ガウス消去処理中の行の操作と行と列reorderingsの配列から成り、それだけDにAに依存しません
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.
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当初。
o Each time a multiple, beta, of row i of A is added to row i' in the decoding schedule, then in the decoding process the symbol beta*D[d[i]] is added to symbol D[d[i']].
OたびAのiが追加される行の倍数、ベータは、iが「シンボルベータ* D [D [i]を〕シンボルD [Dに追加される[iが復号処理において、次に、復号スケジュールの」行に]]。
o Each time a row i of A is multiplied by an octet beta, then in the decoding process the symbol D[d[i]] is also multiplied by beta.
O行I Aの各時間は復号処理において、次に、オクテットベータによってシンボルDを乗算する[D [i]はまた、βが乗算されます。
o 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'].
O iが行と交換されるたび行iが「[復号処理において、次に、復号スケジュールにdの値を[I] I]のDの値と交換されます」。
o 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と交換されているO「[復号化スケジュールで、その後、復号処理におけるcの値[j]は、CのJ]の値と交換されます」。
From this correspondence, it is clear that the total number of operations on symbols in the decoding of the extended source block is the number of row operations (not exchanges) in the Gaussian elimination. Since A is the L x 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、X Lの単位行列であるため、 - L行は、それが成功した復号化の終了時に明らかであるL個のシンボルD [D [0]、D [D [1] ]、...、D [D [L-1]]は、L個のシンボルC] [0℃]、C [C [1]、...、C [L-1 C]の値であります]。
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の疎表現を維持することは、重要である。）このセクションの残りの部分は、ガウスの消去法は、比較的効率的であることを行うことができた順序を記載します。
In the first phase of the Gaussian elimination, the matrix A is conceptually partitioned into submatrices and, additionally, a matrix X is created. This matrix has as many rows and columns as A, and it will be a lower triangular matrix throughout the first phase. At the beginning of this phase, the matrix A is copied into the matrix X.
ガウスの消去法の第一段階で、行列Aは、概念的部分行列に分割され、さらに、行列Xが作成されます。この行列は、Aと同じ数の行と列を有し、それは第一相全体に下三角行列であろう。このフェーズの開始時に、行列Aは行列Xにコピーされます
The submatrix sizes are parameterized by non-negative integers i and u, which are initialized to 0 and P, the number of PI symbols, respectively. The submatrices of A are:
部分行列のサイズは0とP、それぞれPIシンボルの数に初期化される非負整数iおよびU、によってパラメータ化されます。 Aの部分行列は、次のとおりです。
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カラム。これは、位相の各ステップの終了時の単位行列です。
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.
前記部分行列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 6 illustrates the submatrices of A. At the beginning of the first phase, V consists of the first L-P columns of A, and U consists of the last P columns corresponding to the PI symbols. In each step, a row of A is chosen.
図6は、第一段階の開始時にAの部分行列を示し、Vは、Aの最初のL-Pの列で構成され、UはPIシンボルに対応する最後のPの列で構成されています。各ステップにおいて、Aの行が選択されます。
+-----------+-----------------+---------+
| | | |
| I | All Zeros | |
| | | |
+-----------+-----------------+ U |
| | | |
| | | |
| All Zeros | V | |
| | | |
| | | |
+-----------+-----------------+---------+
Figure 6: Submatrices of A in the First Phase
図6：第一相における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 nonzero entries in V and are not HDPC rows 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非ゼロのエントリを有し、HDPC行でない行は、二つのものの位置に二つの列（ノード）を接続するグラフのエッジです。このグラフ内のコンポーネントは、ノード（カラム）とグラフ内のノード/エッジの各対の間の経路が存在するようにエッジ（行）の最大のセットです。コンポーネントのサイズは、成分内のノード（列）の数です。
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 zeros submatrix above V have disappeared, and A consists of I, the all zeros submatrix below I, and U. The phase ends unsuccessfully in decoding failure if at some step before V disappears there is no nonzero row in V to choose in that step. In each step, a row of A is chosen as follows:
最初の段階で最もLの段階であります。私はuがであれば、位相は復号失敗に失敗終了VとV上全てゼロの部分行列が消えており、AはI、I以下全てゼロの部分行列、およびUから構成さL、すなわち、= +ときに位相が正常に終了しますV前にいくつかのステップは、そのステップで選択するVにはゼロ以外の行が存在しない消えます。次のように各ステップにおいて、Aの行が選択されます。
o If all entries of V are zero, then no row is chosen and decoding fails.
Vのすべてのエントリがゼロである場合、O、次に何行が選択されていないと復号が失敗しています。
o Let r be the minimum integer such that at least one row of A has exactly r nonzeros in V.
O rはAの少なくとも一つの行がVの正確r個の非ゼロ要素を有するような最小の整数とします
* If r != 2, then choose a row with exactly r nonzeros in V with minimum original degree among all such rows, except that HDPC rows should not be chosen until all non-HDPC rows have been processed.
*！R = 2の場合、すべての非HDPC行が処理されるまで行が選択されるべきではないことHDPCを除き、全てのそのような行のうち、最小のオリジナル度を有するVで正確にr個の非ゼロ要素を持つ行を選択します。
* If r = 2 and there is a row with exactly 2 ones in V, then choose any row with exactly 2 ones in V that is part of a maximum size component in the graph described above that is defined by V.
* R = 2及びVにおける正確2のものと行があるが、その後V.によって定義される上述のグラフにおける最大サイズの構成要素の一部であるVに正確2のものとの任意の行を選択した場合
* If r = 2 and there is no row with exactly 2 ones in V, then choose any row with exactly 2 nonzeros in V.
* R = 2及びVにおける正確2のものとは行が存在しないが、その後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 nonzeros in the chosen row appears in the first column of V and so that the remaining r-1 nonzeros appear in the last columns of V. The same row and column operations are also performed on the matrix X. Then, an appropriate multiple of the chosen row is added to all the other rows of A below the chosen row that have a nonzero entry in the first column of V. Specifically, if a row below the chosen row has entry beta in the first column of V, and the chosen row has entry alpha in the first column of V, then beta/alpha multiplied by the chosen row is added to this row to leave a zero value in the first column of V. Finally, i is incremented by 1 and u is incremented by r-1, which completes the step.
行がこのステップで選択された後、選択された行は、Vと交差うちAの列は、1つのように並べ替えられるV.と交差する最初の行になるように、Vと交差の最初の行は、選択された行と交換されます選択された行のR非ゼロのVの最初の列に表示され、残りのR-1非ゼロのVの最後の列に表示されるように、同一の行および列の動作は、適切な、そして行列Xに対して実行されます選択された行の複数の選択された行の下の行は、Vの第一列のエントリベータを有する場合、すなわちVの最初の列の非ゼロのエントリが選択された行の下にAの全ての他の行に追加され、そして選択された行は、Vの最初の列のエントリのアルファを有する、選択された行を乗じ、次いでベータ/アルファ最後に、iを1だけインクリメントされるVの最初の列のゼロ値を残すように、この行に追加され、uはインクリメントされR-1、ステップを完了することによって。
Note that efficiency can be improved if the row operations identified above are not actually performed until the affected row is itself chosen during the decoding process. This avoids processing of row operations for rows that are not eventually used in the decoding process, and in particular this avoids those rows for which beta!=1 until they are actually required. Furthermore, the row operations required for the HDPC rows may be performed for all such rows in one process, by using the algorithm described in Section 5.3.3.3.
影響を受けた行自体が復号化プロセス中に選択されるまで、上記識別される行操作が実際に行われていない場合、その効率を向上させることができます。それらが実際に必要とされるまで、これが最終的に復号化プロセスで使用されていない行の行演算の処理を回避し、特に、これはベータのためにそれらの行を回避！= 1。また、HDPC行に必要な行操作は、セクション5.3.3.3に記載されたアルゴリズムを使用することにより、一つのプロセスでこのようなすべての行に対して実行されてもよいです。
At this point, all the entries of X outside the first i rows and i columns are discarded, so that X has lower triangular form. The last i rows and columns of X are discarded, so that X now has i rows and i columns. 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 either to 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 x 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.
Xが下三角形態を有するように、この時点で、すべての最初のi行外XのエントリとI列は、破棄されます。 Xは現在、i行I列を持っているように、Xの最後のI行と列は、破棄されます。部分行列Uは、さらに、最初のi行にU_upperを分配し、残りのMは - I行U_lower。ガウスの消去法のいずれか、そのランクがU（復号失敗）または最初のu行が単位行列（第二相の成功）である行列に変換する未満であることを決定するためにU_lower上の第二段階で行われます。このU、X U単位行列I_uを呼び出します。 M - のL行はU_lowerを交差 - I_uが破棄されます。この段階の後、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 x 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. Moreover, at this time, the matrix U_upper is typically dense, i.e., the number of nonzero entries of this matrix is large. To reduce this matrix to a sparse form, the sequence of operations performed to obtain the matrix U_lower needs to be inverted. To this end, the matrix X is multiplied with the submatrix of A consisting of the first i rows of A. After this operation, the submatrix of A consisting of the intersection of the first i rows and columns equals to X, whereas the matrix U_upper is transformed to a sparse form.
第二段階の後、LのX L恒等行列に変換完了してゼロにする必要があるの一部のみがU_upperあります。部分行列U_upperのI行の数は、一般的にU U_upperの列の数よりもはるかに大きいです。また、この時、行列U_upper、すなわち、この行列の非ゼロエントリの数が多い、典型的に密です。疎フォームにこのマトリックスを低減するために、一連の動作が反転される必要があるU_lower行列を得るために行わ。この目的のために、行列Xは、この操作の後A.の最初のi行から成るの部分行列と乗算され、最初のi行と列の交差点からなるの部分行列は、行列U_upper一方、Xに等しいです。スパース形式に変換されます。
For each of the first i rows of U_upper, do the following: if the row has a nonzero entry at position j, and if the value of that nonzero entry is b, then add to this row b times row j of I_u. After this step, the submatrix of A consisting of the intersection of the first i rows and columns is equal to X, the submatrix U_upper consists of zeros, the submatrix consisting of the intersection of the last u rows and the first i columns consists of zeros, and the submatrix consisting of the last u rows and columns is the matrix I_u.
U_upperの最初のi行ごとに、次の操作を行います。行は位置jにおける非ゼロエントリを有する場合、その非ゼロエントリの値がBである場合、I_uの回行j Bこの行に追加します。このステップの後、最初のi行と列の交差点からなるの部分行列はXに等しく、U_upperがゼロから成る部分行列は、最後のu行および最初のi列の交点から成る部分行列は、ゼロから成り、および最後のu行および列からなる部分行列が行列I_uあります。
For j from 1 to i, perform the following operations:
iを1からJの場合は、次の操作を実行します。
2. For l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l] multiplied with row l of A to row j of A.
1からJ-1、A [J、L]がゼロ以外の場合は、追加[J、L]のLについて2. A.のj行のAの列Lと乗算しました
After this phase, A is the L x L identity matrix and a complete decoding schedule has been successfully formed. Then, the corresponding decoding consisting of summing known encoding symbols can be executed to recover the intermediate symbols based on the decoding schedule. The tuples associated with all source symbols are computed according to Section 5.3.3.2. The tuples for received source symbols are used in the decoding. The tuples for missing source symbols are used to determine which intermediate symbols need to be summed to recover the missing source symbols.
この段階の後、AはL、X Lの単位行列であり、完全な復号スケジュールが正常に形成されています。次いで、既知の符号化シンボルを合計することからなる対応する復号は、復号スケジュールに基づいて中間シンボルを回復するために実行することができます。すべてのソースシンボルに関連付けられたタプルは、セクション5.3.3.2に従って計算されます。受信したソースシンボルの組は、復号に使用されます。欠落したソースシンボルの組は、中間シンボルが欠落したソースシンボルを回復するために加算される必要があるかを決定するために使用されます。
The four arrays V0, V1, V2, and V3 used in Section 5.3.5.1 are provided below. There are 256 entries in each of the four arrays. The indexing into each array starts at 0, and the entries are 32-bit unsigned integers.
セクション5.3.5.1で使用される4つのアレイV0、V1、V2、およびV3は、以下に提供されます。 4つのアレイのそれぞれに256件のエントリがあります。各アレイへのインデックス付けは0から始まり、そしてエントリは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
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
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
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
1629829892, 282540176, 2794583710, 496504798, 2990494426,
3070701851, 2575963183, 4094823972, 2775723650, 4079480416,
176028725, 2246241423, 3732217647, 2196843075, 1306949278,
4170992780, 4039345809, 3209664269, 3387499533, 293063229,
3660290503, 2648440860, 2531406539, 3537879412, 773374739,
4184691853, 1804207821, 3347126643, 3479377103, 3970515774,
1891731298, 2368003842, 3537588307, 2969158410, 4230745262, 831906319, 2935838131, 264029468, 120852739, 3200326460, 355445271, 2296305141, 1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957, 2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977, 2253762642, 3274144518, 598024568, 3299672435, 556579346, 4121041856, 2896948975, 3620123492, 918453629, 3249461198, 2231414958, 3803272287, 3657597946, 2588911389, 242262274, 1725007475, 2026427718, 46776484, 2873281403, 2919275846, 3177933051, 1918859160, 2517854537, 1857818511, 3234262050, 479353687, 200201308, 2801945841, 1621715769, 483977159, 423502325, 3689396064, 1850168397, 3359959416, 3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797, 593824107, 1116572080, 819179184, 3139123629, 1414339336, 1076360795, 512403845, 177759256, 1701060666, 2239736419, 515179302, 2935012727, 3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553, 171592961, 1607044257, 1227236688, 3647136358, 1417559141, 4087067551, 2241705880, 4194136288, 1439041934, 20464430, 119668151, 2021257232, 2551262694, 1381539058, 4082839035, 498179069, 311508499, 3580908637, 2889149671, 142719814, 1232184754, 3356662582, 2973775623, 1469897084, 1728205304, 1415793613, 50111003, 3133413359, 4074115275, 2710540611, 2700083070, 2457757663, 2612845330, 3775943755, 2469309260, 2560142753, 3020996369, 1691667711, 4219602776, 1687672168, 1017921622, 2307642321, 368711460, 3282925988, 213208029, 4150757489, 3443211944, 2846101972, 4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276, 765042313, 916220877, 3402623607, 2768784621, 1722849097, 3386397442, 487920061, 3569027007, 3424544196, 217781973, 2356938519, 3252429414, 145109750, 2692588106, 2454747135, 1299493354, 4120241887, 2088917094, 932304329, 1442609203, 952586974, 3509186750, 753369054, 854421006, 1954046388, 2708927882, 4047539230, 3048925996, 1667505809, 805166441, 1182069088, 4265546268, 4215029527, 3374748959, 373532666, 2454243090, 2371530493, 3651087521, 2619878153, 1651809518, 1553646893, 1227452842, 703887512, 3696674163, 2552507603, 2635912901, 895130484, 3287782244, 3098973502, 990078774, 3780326506, 2290845203, 41729428, 1949580860, 2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283, 3318686998, 1266458025, 3919578154, 3545413527, 2627009988, 3744680394, 1696890173, 3250684705, 4142417708, 915739411, 3308488877, 1289361460, 2942552331, 1169105979, 3342228712, 698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723, 3646581385, 844950914, 1944371367, 3863894844, 2946773319, 1972431613, 1706989237, 29917467, 3497665928
1891731298, 2368003842, 3537588307, 2969158410, 4230745262, 831906319, 2935838131, 264029468, 120852739, 3200326460, 355445271, 2296305141, 1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957, 2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977, 2253762642, 3274144518, 598024568, 3299672435, 556579346, 4121041856, 2896948975, 3620123492, 918453629, 3249461198, 2231414958, 3803272287, 3657597946, 2588911389, 242262274, 1725007475, 2026427718, 46776484, 2873281403, 2919275846, 3177933051, 1918859160, 2517854537, 1857818511, 3234262050, 479353687, 200201308, 2801945841, 1621715769, 483977159, 423502325, 3689396064, 1850168397, 3359959416, 3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797, 593824107, 1116572080, 819179184, 3139123629, 1414339336, 1076360795, 512403845, 177759256, 1701060666, 2239736419, 515179302, 2935012727, 3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553, 171592961, 1607044257, 1227236688, 3647136358, 1417559141, 4087067551, 2241705880, 4194136288, 1439041934, 20464430, 119668151, 2021257232, 2551262694, 1381539058, 4082839035, 498179069, 311508499, 3580908637, 2889149671, 142719814, 1232184754, 3356662582, 2973775623, 1469897084, 1728205304, 1415793613, 50111003, 3133413359, 4074115275, 2710540611, 2700083070, 2457757663, 2612845330, 3775943755, 2469309260, 2560142753, 3020996369, 1691667711, 4219602776, 1687672168, 1017921622, 2307642321, 368711460, 3282925988, 213208029, 4150757489, 3443211944, 2846101972, 4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276, 765042313, 916220877, 3402623607, 2768784621, 1722849097, 3386397442, 487920061, 3569027007, 3424544196, 217781973, 2356938519, 3252429414, 145109750, 2692588106, 2454747135, 1299493354, 4120241887, 2088917094, 932304329, 1442609203, 952586974, 3509186750, 753369054, 854421006, 1954046388, 2708927882, 4047539230, 3048925996, 1667505809, 805166441, 1182069088, 4265546268, 4215029527, 3374748959, 373532666, 2454243090, 2371530493, 3651087521, 2619878153, 1651809518, 1553646893, 1227452842, 703887512, 3696674163, 2552507603, 2635912901, 895130484, 3287782244, 3098973502, 990078774, 3780326506, 2290845203, 41729428, 1949580860, 2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283, 3318686998, 1266458025, 3919578154, 3545413527, 2627009988, 3744680394, 1696890173, 3250684705, 4142417708, 915739411, 3308488877, 1289361460, 2942552331, 1169105979, 3342228712, 698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723, 3646581385, 844950914, 1944371367, 3863894844, 2946773319, 1972431613, 1706989237, 29917467, 3497665928
1191369816, 744902811, 2539772235, 3213192037, 3286061266,
1200571165, 2463281260, 754888894, 714651270, 1968220972,
3628497775, 1277626456, 1493398934, 364289757, 2055487592,
3913468088, 2930259465, 902504567, 3967050355, 2056499403,
692132390, 186386657, 832834706, 859795816, 1283120926,
2253183716, 3003475205, 1755803552, 2239315142, 4271056352,
2184848469, 769228092, 1249230754, 1193269205, 2660094102,
642979613, 1687087994, 2726106182, 446402913, 4122186606,
3771347282, 37667136, 192775425, 3578702187, 1952659096,
3989584400, 3069013882, 2900516158, 4045316336, 3057163251,
1702104819, 4116613420, 3575472384, 2674023117, 1409126723,
3215095429, 1430726429, 2544497368, 1029565676, 1855801827,
4262184627, 1854326881, 2906728593, 3277836557, 2787697002,
2787333385, 3105430738, 2477073192, 748038573, 1088396515,
1611204853, 201964005, 3745818380, 3654683549, 3816120877,
3915783622, 2563198722, 1181149055, 33158084, 3723047845,
3790270906, 3832415204, 2959617497, 372900708, 1286738499,
1932439099, 3677748309, 2454711182, 2757856469, 2134027055,
2780052465, 3190347618, 3758510138, 3626329451, 1120743107,
1623585693, 1389834102, 2719230375, 3038609003, 462617590,
260254189, 3706349764, 2556762744, 2874272296, 2502399286,
4216263978, 2683431180, 2168560535, 3561507175, 668095726,
680412330, 3726693946, 4180630637, 3335170953, 942140968,
2711851085, 2059233412, 4265696278, 3204373534, 232855056,
881788313, 2258252172, 2043595984, 3758795150, 3615341325,
2138837681, 1351208537, 2923692473, 3402482785, 2105383425,
2346772751, 499245323, 3417846006, 2366116814, 2543090583,
1828551634, 3148696244, 3853884867, 1364737681, 2200687771,
2689775688, 232720625, 4071657318, 2671968983, 3531415031,
1212852141, 867923311, 3740109711, 1923146533, 3237071777,
3100729255, 3247856816, 906742566, 4047640575, 4007211572,
3495700105, 1171285262, 2835682655, 1634301229, 3115169925,
2289874706, 2252450179, 944880097, 371933491, 1649074501,
2208617414, 2524305981, 2496569844, 2667037160, 1257550794,
3399219045, 3194894295, 1643249887, 342911473, 891025733,
3146861835, 3789181526, 938847812, 1854580183, 2112653794,
2960702988, 1238603378, 2205280635, 1666784014, 2520274614,
3355493726, 2310872278, 3153920489, 2745882591, 1200203158,
3033612415, 2311650167, 1048129133, 4206710184, 4209176741,
2640950279, 2096382177, 4116899089, 3631017851, 4104488173,
1857650503, 3801102932, 445806934, 3055654640, 897898279,
3234007399, 1325494930, 2982247189, 1619020475, 2720040856,
885096170, 3485255499, 2983202469, 3891011124, 546522756,
1524439205, 2644317889, 2170076800, 2969618716, 961183518,
1081831074, 1037015347, 3289016286, 2331748669, 620887395,
303042654, 3990027945, 1562756376, 3413341792, 2059647769,
2823844432, 674595301, 2457639984, 4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990, 1684954145, 879227329, 3436182180, 1522273219, 3802543817, 1456017040, 1897819847, 2970081129, 1382576028, 3820044861, 1044428167, 612252599, 3340478395, 2150613904, 3397625662, 3573635640, 3432275192
2823844432, 674595301, 2457639984, 4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990, 1684954145, 879227329, 3436182180, 1522273219, 3802543817, 1456017040, 1897819847, 2970081129, 1382576028, 3820044861, 1044428167, 612252599, 3340478395, 2150613904, 3397625662, 3573635640, 3432275192
Table 2 below specifies the supported values of K'. The table also specifies for each supported value of K' the systematic index J(K'), the number H(K') of HDPC symbols, the number S(K') of LDPC symbols, and the number W(K') of LT symbols. For each value of K', the corresponding values of S(K') and W(K') are prime numbers.
以下の表2は、「Kのサポートされる値を指定します。表には、Kのサポートされている各値に対して 『HDPCシンボルの数S（K」系統的インデックスJ（K』）、数H（K） 『LDPCシンボル）、および数W（K』）を指定しますLTシンボルの。 Kの各値に対して」、S（Kの対応する値 『）とW（K』）が素数です。
The systematic index J(K') is designed to have the property that the set of source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are such that the L intermediate symbols are uniquely defined, i.e., the matrix A in Figure 6 has full rank and is therefore invertible.
体系的インデックスJ（K '）は、D1 [0]、[0] A1、B1 [0、そのソースシンボルタプルの集合（D [0]、[0]、[0]、B特性を有するように設計されています]）、...、（D [K'-1]、[K'-1]、B [K'-1]、D1 [K'-1]、A [K'-1]、[B1 K'-1]）L中間シンボルが一意に定義されるようなものである、すなわち、図6の行列Aはフルランクを有し、したがって可逆です。
+-------+-------+-------+-------+-------+
| K' | J(K') | S(K') | H(K') | W(K') |
+-------+-------+-------+-------+-------+
| 10 | 254 | 7 | 10 | 17 |
+-------+-------+-------+-------+-------+
| 12 | 630 | 7 | 10 | 19 |
+-------+-------+-------+-------+-------+
| 18 | 682 | 11 | 10 | 29 |
+-------+-------+-------+-------+-------+
| 20 | 293 | 11 | 10 | 31 |
+-------+-------+-------+-------+-------+
| 26 | 80 | 11 | 10 | 37 |
+-------+-------+-------+-------+-------+
| 30 | 566 | 11 | 10 | 41 |
+-------+-------+-------+-------+-------+
| 32 | 860 | 11 | 10 | 43 |
+-------+-------+-------+-------+-------+
| 36 | 267 | 11 | 10 | 47 |
+-------+-------+-------+-------+-------+
| 42 | 822 | 11 | 10 | 53 |
+-------+-------+-------+-------+-------+
| 46 | 506 | 13 | 10 | 59 |
+-------+-------+-------+-------+-------+
| 48 | 589 | 13 | 10 | 61 |
+-------+-------+-------+-------+-------+
| 49 | 87 | 13 | 10 | 61 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 55 | 520 | 13 | 10 | 67 |
+-------+-------+-------+-------+-------+
| 60 | 159 | 13 | 10 | 71 |
+-------+-------+-------+-------+-------+
| 62 | 235 | 13 | 10 | 73 |
+-------+-------+-------+-------+-------+
| 69 | 157 | 13 | 10 | 79 |
+-------+-------+-------+-------+-------+
| 75 | 502 | 17 | 10 | 89 |
+-------+-------+-------+-------+-------+
| 84 | 334 | 17 | 10 | 97 |
+-------+-------+-------+-------+-------+
| 88 | 583 | 17 | 10 | 101 |
+-------+-------+-------+-------+-------+
| 91 | 66 | 17 | 10 | 103 |
+-------+-------+-------+-------+-------+
| 95 | 352 | 17 | 10 | 107 |
+-------+-------+-------+-------+-------+
| 97 | 365 | 17 | 10 | 109 |
+-------+-------+-------+-------+-------+
| 101 | 562 | 17 | 10 | 113 |
+-------+-------+-------+-------+-------+
| 114 | 5 | 19 | 10 | 127 |
+-------+-------+-------+-------+-------+
| 119 | 603 | 19 | 10 | 131 |
+-------+-------+-------+-------+-------+
| 125 | 721 | 19 | 10 | 137 |
+-------+-------+-------+-------+-------+
| 127 | 28 | 19 | 10 | 139 |
+-------+-------+-------+-------+-------+
| 138 | 660 | 19 | 10 | 149 |
+-------+-------+-------+-------+-------+
| 140 | 829 | 19 | 10 | 151 |
+-------+-------+-------+-------+-------+
| 149 | 900 | 23 | 10 | 163 |
+-------+-------+-------+-------+-------+
| 153 | 930 | 23 | 10 | 167 |
+-------+-------+-------+-------+-------+
| 160 | 814 | 23 | 10 | 173 |
+-------+-------+-------+-------+-------+
| 166 | 661 | 23 | 10 | 179 |
+-------+-------+-------+-------+-------+
| 168 | 693 | 23 | 10 | 181 |
+-------+-------+-------+-------+-------+
| 179 | 780 | 23 | 10 | 191 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 181 | 605 | 23 | 10 | 193 |
+-------+-------+-------+-------+-------+
| 185 | 551 | 23 | 10 | 197 |
+-------+-------+-------+-------+-------+
| 187 | 777 | 23 | 10 | 199 |
+-------+-------+-------+-------+-------+
| 200 | 491 | 23 | 10 | 211 |
+-------+-------+-------+-------+-------+
| 213 | 396 | 23 | 10 | 223 |
+-------+-------+-------+-------+-------+
| 217 | 764 | 29 | 10 | 233 |
+-------+-------+-------+-------+-------+
| 225 | 843 | 29 | 10 | 241 |
+-------+-------+-------+-------+-------+
| 236 | 646 | 29 | 10 | 251 |
+-------+-------+-------+-------+-------+
| 242 | 557 | 29 | 10 | 257 |
+-------+-------+-------+-------+-------+
| 248 | 608 | 29 | 10 | 263 |
+-------+-------+-------+-------+-------+
| 257 | 265 | 29 | 10 | 271 |
+-------+-------+-------+-------+-------+
| 263 | 505 | 29 | 10 | 277 |
+-------+-------+-------+-------+-------+
| 269 | 722 | 29 | 10 | 283 |
+-------+-------+-------+-------+-------+
| 280 | 263 | 29 | 10 | 293 |
+-------+-------+-------+-------+-------+
| 295 | 999 | 29 | 10 | 307 |
+-------+-------+-------+-------+-------+
| 301 | 874 | 29 | 10 | 313 |
+-------+-------+-------+-------+-------+
| 305 | 160 | 29 | 10 | 317 |
+-------+-------+-------+-------+-------+
| 324 | 575 | 31 | 10 | 337 |
+-------+-------+-------+-------+-------+
| 337 | 210 | 31 | 10 | 349 |
+-------+-------+-------+-------+-------+
| 341 | 513 | 31 | 10 | 353 |
+-------+-------+-------+-------+-------+
| 347 | 503 | 31 | 10 | 359 |
+-------+-------+-------+-------+-------+
| 355 | 558 | 31 | 10 | 367 |
+-------+-------+-------+-------+-------+
| 362 | 932 | 31 | 10 | 373 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 368 | 404 | 31 | 10 | 379 |
+-------+-------+-------+-------+-------+
| 372 | 520 | 37 | 10 | 389 |
+-------+-------+-------+-------+-------+
| 380 | 846 | 37 | 10 | 397 |
+-------+-------+-------+-------+-------+
| 385 | 485 | 37 | 10 | 401 |
+-------+-------+-------+-------+-------+
| 393 | 728 | 37 | 10 | 409 |
+-------+-------+-------+-------+-------+
| 405 | 554 | 37 | 10 | 421 |
+-------+-------+-------+-------+-------+
| 418 | 471 | 37 | 10 | 433 |
+-------+-------+-------+-------+-------+
| 428 | 641 | 37 | 10 | 443 |
+-------+-------+-------+-------+-------+
| 434 | 732 | 37 | 10 | 449 |
+-------+-------+-------+-------+-------+
| 447 | 193 | 37 | 10 | 461 |
+-------+-------+-------+-------+-------+
| 453 | 934 | 37 | 10 | 467 |
+-------+-------+-------+-------+-------+
| 466 | 864 | 37 | 10 | 479 |
+-------+-------+-------+-------+-------+
| 478 | 790 | 37 | 10 | 491 |
+-------+-------+-------+-------+-------+
| 486 | 912 | 37 | 10 | 499 |
+-------+-------+-------+-------+-------+
| 491 | 617 | 37 | 10 | 503 |
+-------+-------+-------+-------+-------+
| 497 | 587 | 37 | 10 | 509 |
+-------+-------+-------+-------+-------+
| 511 | 800 | 37 | 10 | 523 |
+-------+-------+-------+-------+-------+
| 526 | 923 | 41 | 10 | 541 |
+-------+-------+-------+-------+-------+
| 532 | 998 | 41 | 10 | 547 |
+-------+-------+-------+-------+-------+
| 542 | 92 | 41 | 10 | 557 |
+-------+-------+-------+-------+-------+
| 549 | 497 | 41 | 10 | 563 |
+-------+-------+-------+-------+-------+
| 557 | 559 | 41 | 10 | 571 |
+-------+-------+-------+-------+-------+
| 563 | 667 | 41 | 10 | 577 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 573 | 912 | 41 | 10 | 587 |
+-------+-------+-------+-------+-------+
| 580 | 262 | 41 | 10 | 593 |
+-------+-------+-------+-------+-------+
| 588 | 152 | 41 | 10 | 601 |
+-------+-------+-------+-------+-------+
| 594 | 526 | 41 | 10 | 607 |
+-------+-------+-------+-------+-------+
| 600 | 268 | 41 | 10 | 613 |
+-------+-------+-------+-------+-------+
| 606 | 212 | 41 | 10 | 619 |
+-------+-------+-------+-------+-------+
| 619 | 45 | 41 | 10 | 631 |
+-------+-------+-------+-------+-------+
| 633 | 898 | 43 | 10 | 647 |
+-------+-------+-------+-------+-------+
| 640 | 527 | 43 | 10 | 653 |
+-------+-------+-------+-------+-------+
| 648 | 558 | 43 | 10 | 661 |
+-------+-------+-------+-------+-------+
| 666 | 460 | 47 | 10 | 683 |
+-------+-------+-------+-------+-------+
| 675 | 5 | 47 | 10 | 691 |
+-------+-------+-------+-------+-------+
| 685 | 895 | 47 | 10 | 701 |
+-------+-------+-------+-------+-------+
| 693 | 996 | 47 | 10 | 709 |
+-------+-------+-------+-------+-------+
| 703 | 282 | 47 | 10 | 719 |
+-------+-------+-------+-------+-------+
| 718 | 513 | 47 | 10 | 733 |
+-------+-------+-------+-------+-------+
| 728 | 865 | 47 | 10 | 743 |
+-------+-------+-------+-------+-------+
| 736 | 870 | 47 | 10 | 751 |
+-------+-------+-------+-------+-------+
| 747 | 239 | 47 | 10 | 761 |
+-------+-------+-------+-------+-------+
| 759 | 452 | 47 | 10 | 773 |
+-------+-------+-------+-------+-------+
| 778 | 862 | 53 | 10 | 797 |
+-------+-------+-------+-------+-------+
| 792 | 852 | 53 | 10 | 811 |
+-------+-------+-------+-------+-------+
| 802 | 643 | 53 | 10 | 821 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 811 | 543 | 53 | 10 | 829 |
+-------+-------+-------+-------+-------+
| 821 | 447 | 53 | 10 | 839 |
+-------+-------+-------+-------+-------+
| 835 | 321 | 53 | 10 | 853 |
+-------+-------+-------+-------+-------+
| 845 | 287 | 53 | 10 | 863 |
+-------+-------+-------+-------+-------+
| 860 | 12 | 53 | 10 | 877 |
+-------+-------+-------+-------+-------+
| 870 | 251 | 53 | 10 | 887 |
+-------+-------+-------+-------+-------+
| 891 | 30 | 53 | 10 | 907 |
+-------+-------+-------+-------+-------+
| 903 | 621 | 53 | 10 | 919 |
+-------+-------+-------+-------+-------+
| 913 | 555 | 53 | 10 | 929 |
+-------+-------+-------+-------+-------+
| 926 | 127 | 53 | 10 | 941 |
+-------+-------+-------+-------+-------+
| 938 | 400 | 53 | 10 | 953 |
+-------+-------+-------+-------+-------+
| 950 | 91 | 59 | 10 | 971 |
+-------+-------+-------+-------+-------+
| 963 | 916 | 59 | 10 | 983 |
+-------+-------+-------+-------+-------+
| 977 | 935 | 59 | 10 | 997 |
+-------+-------+-------+-------+-------+
| 989 | 691 | 59 | 10 | 1009 |
+-------+-------+-------+-------+-------+
| 1002 | 299 | 59 | 10 | 1021 |
+-------+-------+-------+-------+-------+
| 1020 | 282 | 59 | 10 | 1039 |
+-------+-------+-------+-------+-------+
| 1032 | 824 | 59 | 10 | 1051 |
+-------+-------+-------+-------+-------+
| 1050 | 536 | 59 | 11 | 1069 |
+-------+-------+-------+-------+-------+
| 1074 | 596 | 59 | 11 | 1093 |
+-------+-------+-------+-------+-------+
| 1085 | 28 | 59 | 11 | 1103 |
+-------+-------+-------+-------+-------+
| 1099 | 947 | 59 | 11 | 1117 |
+-------+-------+-------+-------+-------+
| 1111 | 162 | 59 | 11 | 1129 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 1136 | 536 | 59 | 11 | 1153 |
+-------+-------+-------+-------+-------+
| 1152 | 1000 | 61 | 11 | 1171 |
+-------+-------+-------+-------+-------+
| 1169 | 251 | 61 | 11 | 1187 |
+-------+-------+-------+-------+-------+
| 1183 | 673 | 61 | 11 | 1201 |
+-------+-------+-------+-------+-------+
| 1205 | 559 | 61 | 11 | 1223 |
+-------+-------+-------+-------+-------+
| 1220 | 923 | 61 | 11 | 1237 |
+-------+-------+-------+-------+-------+
| 1236 | 81 | 67 | 11 | 1259 |
+-------+-------+-------+-------+-------+
| 1255 | 478 | 67 | 11 | 1277 |
+-------+-------+-------+-------+-------+
| 1269 | 198 | 67 | 11 | 1291 |
+-------+-------+-------+-------+-------+
| 1285 | 137 | 67 | 11 | 1307 |
+-------+-------+-------+-------+-------+
| 1306 | 75 | 67 | 11 | 1327 |
+-------+-------+-------+-------+-------+
| 1347 | 29 | 67 | 11 | 1367 |
+-------+-------+-------+-------+-------+
| 1361 | 231 | 67 | 11 | 1381 |
+-------+-------+-------+-------+-------+
| 1389 | 532 | 67 | 11 | 1409 |
+-------+-------+-------+-------+-------+
| 1404 | 58 | 67 | 11 | 1423 |
+-------+-------+-------+-------+-------+
| 1420 | 60 | 67 | 11 | 1439 |
+-------+-------+-------+-------+-------+
| 1436 | 964 | 71 | 11 | 1459 |
+-------+-------+-------+-------+-------+
| 1461 | 624 | 71 | 11 | 1483 |
+-------+-------+-------+-------+-------+
| 1477 | 502 | 71 | 11 | 1499 |
+-------+-------+-------+-------+-------+
| 1502 | 636 | 71 | 11 | 1523 |
+-------+-------+-------+-------+-------+
| 1522 | 986 | 71 | 11 | 1543 |
+-------+-------+-------+-------+-------+
| 1539 | 950 | 71 | 11 | 1559 |
+-------+-------+-------+-------+-------+
| 1561 | 735 | 73 | 11 | 1583 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 1579 | 866 | 73 | 11 | 1601 |
+-------+-------+-------+-------+-------+
| 1600 | 203 | 73 | 11 | 1621 |
+-------+-------+-------+-------+-------+
| 1616 | 83 | 73 | 11 | 1637 |
+-------+-------+-------+-------+-------+
| 1649 | 14 | 73 | 11 | 1669 |
+-------+-------+-------+-------+-------+
| 1673 | 522 | 79 | 11 | 1699 |
+-------+-------+-------+-------+-------+
| 1698 | 226 | 79 | 11 | 1723 |
+-------+-------+-------+-------+-------+
| 1716 | 282 | 79 | 11 | 1741 |
+-------+-------+-------+-------+-------+
| 1734 | 88 | 79 | 11 | 1759 |
+-------+-------+-------+-------+-------+
| 1759 | 636 | 79 | 11 | 1783 |
+-------+-------+-------+-------+-------+
| 1777 | 860 | 79 | 11 | 1801 |
+-------+-------+-------+-------+-------+
| 1800 | 324 | 79 | 11 | 1823 |
+-------+-------+-------+-------+-------+
| 1824 | 424 | 79 | 11 | 1847 |
+-------+-------+-------+-------+-------+
| 1844 | 999 | 79 | 11 | 1867 |
+-------+-------+-------+-------+-------+
| 1863 | 682 | 83 | 11 | 1889 |
+-------+-------+-------+-------+-------+
| 1887 | 814 | 83 | 11 | 1913 |
+-------+-------+-------+-------+-------+
| 1906 | 979 | 83 | 11 | 1931 |
+-------+-------+-------+-------+-------+
| 1926 | 538 | 83 | 11 | 1951 |
+-------+-------+-------+-------+-------+
| 1954 | 278 | 83 | 11 | 1979 |
+-------+-------+-------+-------+-------+
| 1979 | 580 | 83 | 11 | 2003 |
+-------+-------+-------+-------+-------+
| 2005 | 773 | 83 | 11 | 2029 |
+-------+-------+-------+-------+-------+
| 2040 | 911 | 89 | 11 | 2069 |
+-------+-------+-------+-------+-------+
| 2070 | 506 | 89 | 11 | 2099 |
+-------+-------+-------+-------+-------+
| 2103 | 628 | 89 | 11 | 2131 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 2125 | 282 | 89 | 11 | 2153 |
+-------+-------+-------+-------+-------+
| 2152 | 309 | 89 | 11 | 2179 |
+-------+-------+-------+-------+-------+
| 2195 | 858 | 89 | 11 | 2221 |
+-------+-------+-------+-------+-------+
| 2217 | 442 | 89 | 11 | 2243 |
+-------+-------+-------+-------+-------+
| 2247 | 654 | 89 | 11 | 2273 |
+-------+-------+-------+-------+-------+
| 2278 | 82 | 97 | 11 | 2311 |
+-------+-------+-------+-------+-------+
| 2315 | 428 | 97 | 11 | 2347 |
+-------+-------+-------+-------+-------+
| 2339 | 442 | 97 | 11 | 2371 |
+-------+-------+-------+-------+-------+
| 2367 | 283 | 97 | 11 | 2399 |
+-------+-------+-------+-------+-------+
| 2392 | 538 | 97 | 11 | 2423 |
+-------+-------+-------+-------+-------+
| 2416 | 189 | 97 | 11 | 2447 |
+-------+-------+-------+-------+-------+
| 2447 | 438 | 97 | 11 | 2477 |
+-------+-------+-------+-------+-------+
| 2473 | 912 | 97 | 11 | 2503 |
+-------+-------+-------+-------+-------+
| 2502 | 1 | 97 | 11 | 2531 |
+-------+-------+-------+-------+-------+
| 2528 | 167 | 97 | 11 | 2557 |
+-------+-------+-------+-------+-------+
| 2565 | 272 | 97 | 11 | 2593 |
+-------+-------+-------+-------+-------+
| 2601 | 209 | 101 | 11 | 2633 |
+-------+-------+-------+-------+-------+
| 2640 | 927 | 101 | 11 | 2671 |
+-------+-------+-------+-------+-------+
| 2668 | 386 | 101 | 11 | 2699 |
+-------+-------+-------+-------+-------+
| 2701 | 653 | 101 | 11 | 2731 |
+-------+-------+-------+-------+-------+
| 2737 | 669 | 101 | 11 | 2767 |
+-------+-------+-------+-------+-------+
| 2772 | 431 | 101 | 11 | 2801 |
+-------+-------+-------+-------+-------+
| 2802 | 793 | 103 | 11 | 2833 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 2831 | 588 | 103 | 11 | 2861 |
+-------+-------+-------+-------+-------+
| 2875 | 777 | 107 | 11 | 2909 |
+-------+-------+-------+-------+-------+
| 2906 | 939 | 107 | 11 | 2939 |
+-------+-------+-------+-------+-------+
| 2938 | 864 | 107 | 11 | 2971 |
+-------+-------+-------+-------+-------+
| 2979 | 627 | 107 | 11 | 3011 |
+-------+-------+-------+-------+-------+
| 3015 | 265 | 109 | 11 | 3049 |
+-------+-------+-------+-------+-------+
| 3056 | 976 | 109 | 11 | 3089 |
+-------+-------+-------+-------+-------+
| 3101 | 988 | 113 | 11 | 3137 |
+-------+-------+-------+-------+-------+
| 3151 | 507 | 113 | 11 | 3187 |
+-------+-------+-------+-------+-------+
| 3186 | 640 | 113 | 11 | 3221 |
+-------+-------+-------+-------+-------+
| 3224 | 15 | 113 | 11 | 3259 |
+-------+-------+-------+-------+-------+
| 3265 | 667 | 113 | 11 | 3299 |
+-------+-------+-------+-------+-------+
| 3299 | 24 | 127 | 11 | 3347 |
+-------+-------+-------+-------+-------+
| 3344 | 877 | 127 | 11 | 3391 |
+-------+-------+-------+-------+-------+
| 3387 | 240 | 127 | 11 | 3433 |
+-------+-------+-------+-------+-------+
| 3423 | 720 | 127 | 11 | 3469 |
+-------+-------+-------+-------+-------+
| 3466 | 93 | 127 | 11 | 3511 |
+-------+-------+-------+-------+-------+
| 3502 | 919 | 127 | 11 | 3547 |
+-------+-------+-------+-------+-------+
| 3539 | 635 | 127 | 11 | 3583 |
+-------+-------+-------+-------+-------+
| 3579 | 174 | 127 | 11 | 3623 |
+-------+-------+-------+-------+-------+
| 3616 | 647 | 127 | 11 | 3659 |
+-------+-------+-------+-------+-------+
| 3658 | 820 | 127 | 11 | 3701 |
+-------+-------+-------+-------+-------+
| 3697 | 56 | 127 | 11 | 3739 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 3751 | 485 | 127 | 11 | 3793 |
+-------+-------+-------+-------+-------+
| 3792 | 210 | 127 | 11 | 3833 |
+-------+-------+-------+-------+-------+
| 3840 | 124 | 127 | 11 | 3881 |
+-------+-------+-------+-------+-------+
| 3883 | 546 | 127 | 11 | 3923 |
+-------+-------+-------+-------+-------+
| 3924 | 954 | 131 | 11 | 3967 |
+-------+-------+-------+-------+-------+
| 3970 | 262 | 131 | 11 | 4013 |
+-------+-------+-------+-------+-------+
| 4015 | 927 | 131 | 11 | 4057 |
+-------+-------+-------+-------+-------+
| 4069 | 957 | 131 | 11 | 4111 |
+-------+-------+-------+-------+-------+
| 4112 | 726 | 137 | 11 | 4159 |
+-------+-------+-------+-------+-------+
| 4165 | 583 | 137 | 11 | 4211 |
+-------+-------+-------+-------+-------+
| 4207 | 782 | 137 | 11 | 4253 |
+-------+-------+-------+-------+-------+
| 4252 | 37 | 137 | 11 | 4297 |
+-------+-------+-------+-------+-------+
| 4318 | 758 | 137 | 11 | 4363 |
+-------+-------+-------+-------+-------+
| 4365 | 777 | 137 | 11 | 4409 |
+-------+-------+-------+-------+-------+
| 4418 | 104 | 139 | 11 | 4463 |
+-------+-------+-------+-------+-------+
| 4468 | 476 | 139 | 11 | 4513 |
+-------+-------+-------+-------+-------+
| 4513 | 113 | 149 | 11 | 4567 |
+-------+-------+-------+-------+-------+
| 4567 | 313 | 149 | 11 | 4621 |
+-------+-------+-------+-------+-------+
| 4626 | 102 | 149 | 11 | 4679 |
+-------+-------+-------+-------+-------+
| 4681 | 501 | 149 | 11 | 4733 |
+-------+-------+-------+-------+-------+
| 4731 | 332 | 149 | 11 | 4783 |
+-------+-------+-------+-------+-------+
| 4780 | 786 | 149 | 11 | 4831 |
+-------+-------+-------+-------+-------+
| 4838 | 99 | 149 | 11 | 4889 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 4901 | 658 | 149 | 11 | 4951 |
+-------+-------+-------+-------+-------+
| 4954 | 794 | 149 | 11 | 5003 |
+-------+-------+-------+-------+-------+
| 5008 | 37 | 151 | 11 | 5059 |
+-------+-------+-------+-------+-------+
| 5063 | 471 | 151 | 11 | 5113 |
+-------+-------+-------+-------+-------+
| 5116 | 94 | 157 | 11 | 5171 |
+-------+-------+-------+-------+-------+
| 5172 | 873 | 157 | 11 | 5227 |
+-------+-------+-------+-------+-------+
| 5225 | 918 | 157 | 11 | 5279 |
+-------+-------+-------+-------+-------+
| 5279 | 945 | 157 | 11 | 5333 |
+-------+-------+-------+-------+-------+
| 5334 | 211 | 157 | 11 | 5387 |
+-------+-------+-------+-------+-------+
| 5391 | 341 | 157 | 11 | 5443 |
+-------+-------+-------+-------+-------+
| 5449 | 11 | 163 | 11 | 5507 |
+-------+-------+-------+-------+-------+
| 5506 | 578 | 163 | 11 | 5563 |
+-------+-------+-------+-------+-------+
| 5566 | 494 | 163 | 11 | 5623 |
+-------+-------+-------+-------+-------+
| 5637 | 694 | 163 | 11 | 5693 |
+-------+-------+-------+-------+-------+
| 5694 | 252 | 163 | 11 | 5749 |
+-------+-------+-------+-------+-------+
| 5763 | 451 | 167 | 11 | 5821 |
+-------+-------+-------+-------+-------+
| 5823 | 83 | 167 | 11 | 5881 |
+-------+-------+-------+-------+-------+
| 5896 | 689 | 167 | 11 | 5953 |
+-------+-------+-------+-------+-------+
| 5975 | 488 | 173 | 11 | 6037 |
+-------+-------+-------+-------+-------+
| 6039 | 214 | 173 | 11 | 6101 |
+-------+-------+-------+-------+-------+
| 6102 | 17 | 173 | 11 | 6163 |
+-------+-------+-------+-------+-------+
| 6169 | 469 | 173 | 11 | 6229 |
+-------+-------+-------+-------+-------+
| 6233 | 263 | 179 | 11 | 6299 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 6296 | 309 | 179 | 11 | 6361 |
+-------+-------+-------+-------+-------+
| 6363 | 984 | 179 | 11 | 6427 |
+-------+-------+-------+-------+-------+
| 6427 | 123 | 179 | 11 | 6491 |
+-------+-------+-------+-------+-------+
| 6518 | 360 | 179 | 11 | 6581 |
+-------+-------+-------+-------+-------+
| 6589 | 863 | 181 | 11 | 6653 |
+-------+-------+-------+-------+-------+
| 6655 | 122 | 181 | 11 | 6719 |
+-------+-------+-------+-------+-------+
| 6730 | 522 | 191 | 11 | 6803 |
+-------+-------+-------+-------+-------+
| 6799 | 539 | 191 | 11 | 6871 |
+-------+-------+-------+-------+-------+
| 6878 | 181 | 191 | 11 | 6949 |
+-------+-------+-------+-------+-------+
| 6956 | 64 | 191 | 11 | 7027 |
+-------+-------+-------+-------+-------+
| 7033 | 387 | 191 | 11 | 7103 |
+-------+-------+-------+-------+-------+
| 7108 | 967 | 191 | 11 | 7177 |
+-------+-------+-------+-------+-------+
| 7185 | 843 | 191 | 11 | 7253 |
+-------+-------+-------+-------+-------+
| 7281 | 999 | 193 | 11 | 7351 |
+-------+-------+-------+-------+-------+
| 7360 | 76 | 197 | 11 | 7433 |
+-------+-------+-------+-------+-------+
| 7445 | 142 | 197 | 11 | 7517 |
+-------+-------+-------+-------+-------+
| 7520 | 599 | 197 | 11 | 7591 |
+-------+-------+-------+-------+-------+
| 7596 | 576 | 199 | 11 | 7669 |
+-------+-------+-------+-------+-------+
| 7675 | 176 | 211 | 11 | 7759 |
+-------+-------+-------+-------+-------+
| 7770 | 392 | 211 | 11 | 7853 |
+-------+-------+-------+-------+-------+
| 7855 | 332 | 211 | 11 | 7937 |
+-------+-------+-------+-------+-------+
| 7935 | 291 | 211 | 11 | 8017 |
+-------+-------+-------+-------+-------+
| 8030 | 913 | 211 | 11 | 8111 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 8111 | 608 | 211 | 11 | 8191 |
+-------+-------+-------+-------+-------+
| 8194 | 212 | 211 | 11 | 8273 |
+-------+-------+-------+-------+-------+
| 8290 | 696 | 211 | 11 | 8369 |
+-------+-------+-------+-------+-------+
| 8377 | 931 | 223 | 11 | 8467 |
+-------+-------+-------+-------+-------+
| 8474 | 326 | 223 | 11 | 8563 |
+-------+-------+-------+-------+-------+
| 8559 | 228 | 223 | 11 | 8647 |
+-------+-------+-------+-------+-------+
| 8654 | 706 | 223 | 11 | 8741 |
+-------+-------+-------+-------+-------+
| 8744 | 144 | 223 | 11 | 8831 |
+-------+-------+-------+-------+-------+
| 8837 | 83 | 223 | 11 | 8923 |
+-------+-------+-------+-------+-------+
| 8928 | 743 | 223 | 11 | 9013 |
+-------+-------+-------+-------+-------+
| 9019 | 187 | 223 | 11 | 9103 |
+-------+-------+-------+-------+-------+
| 9111 | 654 | 227 | 11 | 9199 |
+-------+-------+-------+-------+-------+
| 9206 | 359 | 227 | 11 | 9293 |
+-------+-------+-------+-------+-------+
| 9303 | 493 | 229 | 11 | 9391 |
+-------+-------+-------+-------+-------+
| 9400 | 369 | 233 | 11 | 9491 |
+-------+-------+-------+-------+-------+
| 9497 | 981 | 233 | 11 | 9587 |
+-------+-------+-------+-------+-------+
| 9601 | 276 | 239 | 11 | 9697 |
+-------+-------+-------+-------+-------+
| 9708 | 647 | 239 | 11 | 9803 |
+-------+-------+-------+-------+-------+
| 9813 | 389 | 239 | 11 | 9907 |
+-------+-------+-------+-------+-------+
| 9916 | 80 | 239 | 11 | 10009 |
+-------+-------+-------+-------+-------+
| 10017 | 396 | 241 | 11 | 10111 |
+-------+-------+-------+-------+-------+
| 10120 | 580 | 251 | 11 | 10223 |
+-------+-------+-------+-------+-------+
| 10241 | 873 | 251 | 11 | 10343 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 10351 | 15 | 251 | 11 | 10453 |
+-------+-------+-------+-------+-------+
| 10458 | 976 | 251 | 11 | 10559 |
+-------+-------+-------+-------+-------+
| 10567 | 584 | 251 | 11 | 10667 |
+-------+-------+-------+-------+-------+
| 10676 | 267 | 257 | 11 | 10781 |
+-------+-------+-------+-------+-------+
| 10787 | 876 | 257 | 11 | 10891 |
+-------+-------+-------+-------+-------+
| 10899 | 642 | 257 | 12 | 11003 |
+-------+-------+-------+-------+-------+
| 11015 | 794 | 257 | 12 | 11119 |
+-------+-------+-------+-------+-------+
| 11130 | 78 | 263 | 12 | 11239 |
+-------+-------+-------+-------+-------+
| 11245 | 736 | 263 | 12 | 11353 |
+-------+-------+-------+-------+-------+
| 11358 | 882 | 269 | 12 | 11471 |
+-------+-------+-------+-------+-------+
| 11475 | 251 | 269 | 12 | 11587 |
+-------+-------+-------+-------+-------+
| 11590 | 434 | 269 | 12 | 11701 |
+-------+-------+-------+-------+-------+
| 11711 | 204 | 269 | 12 | 11821 |
+-------+-------+-------+-------+-------+
| 11829 | 256 | 271 | 12 | 11941 |
+-------+-------+-------+-------+-------+
| 11956 | 106 | 277 | 12 | 12073 |
+-------+-------+-------+-------+-------+
| 12087 | 375 | 277 | 12 | 12203 |
+-------+-------+-------+-------+-------+
| 12208 | 148 | 277 | 12 | 12323 |
+-------+-------+-------+-------+-------+
| 12333 | 496 | 281 | 12 | 12451 |
+-------+-------+-------+-------+-------+
| 12460 | 88 | 281 | 12 | 12577 |
+-------+-------+-------+-------+-------+
| 12593 | 826 | 293 | 12 | 12721 |
+-------+-------+-------+-------+-------+
| 12726 | 71 | 293 | 12 | 12853 |
+-------+-------+-------+-------+-------+
| 12857 | 925 | 293 | 12 | 12983 |
+-------+-------+-------+-------+-------+
| 13002 | 760 | 293 | 12 | 13127 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 13143 | 130 | 293 | 12 | 13267 |
+-------+-------+-------+-------+-------+
| 13284 | 641 | 307 | 12 | 13421 |
+-------+-------+-------+-------+-------+
| 13417 | 400 | 307 | 12 | 13553 |
+-------+-------+-------+-------+-------+
| 13558 | 480 | 307 | 12 | 13693 |
+-------+-------+-------+-------+-------+
| 13695 | 76 | 307 | 12 | 13829 |
+-------+-------+-------+-------+-------+
| 13833 | 665 | 307 | 12 | 13967 |
+-------+-------+-------+-------+-------+
| 13974 | 910 | 307 | 12 | 14107 |
+-------+-------+-------+-------+-------+
| 14115 | 467 | 311 | 12 | 14251 |
+-------+-------+-------+-------+-------+
| 14272 | 964 | 311 | 12 | 14407 |
+-------+-------+-------+-------+-------+
| 14415 | 625 | 313 | 12 | 14551 |
+-------+-------+-------+-------+-------+
| 14560 | 362 | 317 | 12 | 14699 |
+-------+-------+-------+-------+-------+
| 14713 | 759 | 317 | 12 | 14851 |
+-------+-------+-------+-------+-------+
| 14862 | 728 | 331 | 12 | 15013 |
+-------+-------+-------+-------+-------+
| 15011 | 343 | 331 | 12 | 15161 |
+-------+-------+-------+-------+-------+
| 15170 | 113 | 331 | 12 | 15319 |
+-------+-------+-------+-------+-------+
| 15325 | 137 | 331 | 12 | 15473 |
+-------+-------+-------+-------+-------+
| 15496 | 308 | 331 | 12 | 15643 |
+-------+-------+-------+-------+-------+
| 15651 | 800 | 337 | 12 | 15803 |
+-------+-------+-------+-------+-------+
| 15808 | 177 | 337 | 12 | 15959 |
+-------+-------+-------+-------+-------+
| 15977 | 961 | 337 | 12 | 16127 |
+-------+-------+-------+-------+-------+
| 16161 | 958 | 347 | 12 | 16319 |
+-------+-------+-------+-------+-------+
| 16336 | 72 | 347 | 12 | 16493 |
+-------+-------+-------+-------+-------+
| 16505 | 732 | 347 | 12 | 16661 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 16674 | 145 | 349 | 12 | 16831 |
+-------+-------+-------+-------+-------+
| 16851 | 577 | 353 | 12 | 17011 |
+-------+-------+-------+-------+-------+
| 17024 | 305 | 353 | 12 | 17183 |
+-------+-------+-------+-------+-------+
| 17195 | 50 | 359 | 12 | 17359 |
+-------+-------+-------+-------+-------+
| 17376 | 351 | 359 | 12 | 17539 |
+-------+-------+-------+-------+-------+
| 17559 | 175 | 367 | 12 | 17729 |
+-------+-------+-------+-------+-------+
| 17742 | 727 | 367 | 12 | 17911 |
+-------+-------+-------+-------+-------+
| 17929 | 902 | 367 | 12 | 18097 |
+-------+-------+-------+-------+-------+
| 18116 | 409 | 373 | 12 | 18289 |
+-------+-------+-------+-------+-------+
| 18309 | 776 | 373 | 12 | 18481 |
+-------+-------+-------+-------+-------+
| 18503 | 586 | 379 | 12 | 18679 |
+-------+-------+-------+-------+-------+
| 18694 | 451 | 379 | 12 | 18869 |
+-------+-------+-------+-------+-------+
| 18909 | 287 | 383 | 12 | 19087 |
+-------+-------+-------+-------+-------+
| 19126 | 246 | 389 | 12 | 19309 |
+-------+-------+-------+-------+-------+
| 19325 | 222 | 389 | 12 | 19507 |
+-------+-------+-------+-------+-------+
| 19539 | 563 | 397 | 12 | 19727 |
+-------+-------+-------+-------+-------+
| 19740 | 839 | 397 | 12 | 19927 |
+-------+-------+-------+-------+-------+
| 19939 | 897 | 401 | 12 | 20129 |
+-------+-------+-------+-------+-------+
| 20152 | 409 | 401 | 12 | 20341 |
+-------+-------+-------+-------+-------+
| 20355 | 618 | 409 | 12 | 20551 |
+-------+-------+-------+-------+-------+
| 20564 | 439 | 409 | 12 | 20759 |
+-------+-------+-------+-------+-------+
| 20778 | 95 | 419 | 13 | 20983 |
+-------+-------+-------+-------+-------+
| 20988 | 448 | 419 | 13 | 21191 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 21199 | 133 | 419 | 13 | 21401 |
+-------+-------+-------+-------+-------+
| 21412 | 938 | 419 | 13 | 21613 |
+-------+-------+-------+-------+-------+
| 21629 | 423 | 431 | 13 | 21841 |
+-------+-------+-------+-------+-------+
| 21852 | 90 | 431 | 13 | 22063 |
+-------+-------+-------+-------+-------+
| 22073 | 640 | 431 | 13 | 22283 |
+-------+-------+-------+-------+-------+
| 22301 | 922 | 433 | 13 | 22511 |
+-------+-------+-------+-------+-------+
| 22536 | 250 | 439 | 13 | 22751 |
+-------+-------+-------+-------+-------+
| 22779 | 367 | 439 | 13 | 22993 |
+-------+-------+-------+-------+-------+
| 23010 | 447 | 443 | 13 | 23227 |
+-------+-------+-------+-------+-------+
| 23252 | 559 | 449 | 13 | 23473 |
+-------+-------+-------+-------+-------+
| 23491 | 121 | 457 | 13 | 23719 |
+-------+-------+-------+-------+-------+
| 23730 | 623 | 457 | 13 | 23957 |
+-------+-------+-------+-------+-------+
| 23971 | 450 | 457 | 13 | 24197 |
+-------+-------+-------+-------+-------+
| 24215 | 253 | 461 | 13 | 24443 |
+-------+-------+-------+-------+-------+
| 24476 | 106 | 467 | 13 | 24709 |
+-------+-------+-------+-------+-------+
| 24721 | 863 | 467 | 13 | 24953 |
+-------+-------+-------+-------+-------+
| 24976 | 148 | 479 | 13 | 25219 |
+-------+-------+-------+-------+-------+
| 25230 | 427 | 479 | 13 | 25471 |
+-------+-------+-------+-------+-------+
| 25493 | 138 | 479 | 13 | 25733 |
+-------+-------+-------+-------+-------+
| 25756 | 794 | 487 | 13 | 26003 |
+-------+-------+-------+-------+-------+
| 26022 | 247 | 487 | 13 | 26267 |
+-------+-------+-------+-------+-------+
| 26291 | 562 | 491 | 13 | 26539 |
+-------+-------+-------+-------+-------+
| 26566 | 53 | 499 | 13 | 26821 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 26838 | 135 | 499 | 13 | 27091 |
+-------+-------+-------+-------+-------+
| 27111 | 21 | 503 | 13 | 27367 |
+-------+-------+-------+-------+-------+
| 27392 | 201 | 509 | 13 | 27653 |
+-------+-------+-------+-------+-------+
| 27682 | 169 | 521 | 13 | 27953 |
+-------+-------+-------+-------+-------+
| 27959 | 70 | 521 | 13 | 28229 |
+-------+-------+-------+-------+-------+
| 28248 | 386 | 521 | 13 | 28517 |
+-------+-------+-------+-------+-------+
| 28548 | 226 | 523 | 13 | 28817 |
+-------+-------+-------+-------+-------+
| 28845 | 3 | 541 | 13 | 29131 |
+-------+-------+-------+-------+-------+
| 29138 | 769 | 541 | 13 | 29423 |
+-------+-------+-------+-------+-------+
| 29434 | 590 | 541 | 13 | 29717 |
+-------+-------+-------+-------+-------+
| 29731 | 672 | 541 | 13 | 30013 |
+-------+-------+-------+-------+-------+
| 30037 | 713 | 547 | 13 | 30323 |
+-------+-------+-------+-------+-------+
| 30346 | 967 | 547 | 13 | 30631 |
+-------+-------+-------+-------+-------+
| 30654 | 368 | 557 | 14 | 30949 |
+-------+-------+-------+-------+-------+
| 30974 | 348 | 557 | 14 | 31267 |
+-------+-------+-------+-------+-------+
| 31285 | 119 | 563 | 14 | 31583 |
+-------+-------+-------+-------+-------+
| 31605 | 503 | 569 | 14 | 31907 |
+-------+-------+-------+-------+-------+
| 31948 | 181 | 571 | 14 | 32251 |
+-------+-------+-------+-------+-------+
| 32272 | 394 | 577 | 14 | 32579 |
+-------+-------+-------+-------+-------+
| 32601 | 189 | 587 | 14 | 32917 |
+-------+-------+-------+-------+-------+
| 32932 | 210 | 587 | 14 | 33247 |
+-------+-------+-------+-------+-------+
| 33282 | 62 | 593 | 14 | 33601 |
+-------+-------+-------+-------+-------+
| 33623 | 273 | 593 | 14 | 33941 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 33961 | 554 | 599 | 14 | 34283 |
+-------+-------+-------+-------+-------+
| 34302 | 936 | 607 | 14 | 34631 |
+-------+-------+-------+-------+-------+
| 34654 | 483 | 607 | 14 | 34981 |
+-------+-------+-------+-------+-------+
| 35031 | 397 | 613 | 14 | 35363 |
+-------+-------+-------+-------+-------+
| 35395 | 241 | 619 | 14 | 35731 |
+-------+-------+-------+-------+-------+
| 35750 | 500 | 631 | 14 | 36097 |
+-------+-------+-------+-------+-------+
| 36112 | 12 | 631 | 14 | 36457 |
+-------+-------+-------+-------+-------+
| 36479 | 958 | 641 | 14 | 36833 |
+-------+-------+-------+-------+-------+
| 36849 | 524 | 641 | 14 | 37201 |
+-------+-------+-------+-------+-------+
| 37227 | 8 | 643 | 14 | 37579 |
+-------+-------+-------+-------+-------+
| 37606 | 100 | 653 | 14 | 37967 |
+-------+-------+-------+-------+-------+
| 37992 | 339 | 653 | 14 | 38351 |
+-------+-------+-------+-------+-------+
| 38385 | 804 | 659 | 14 | 38749 |
+-------+-------+-------+-------+-------+
| 38787 | 510 | 673 | 14 | 39163 |
+-------+-------+-------+-------+-------+
| 39176 | 18 | 673 | 14 | 39551 |
+-------+-------+-------+-------+-------+
| 39576 | 412 | 677 | 14 | 39953 |
+-------+-------+-------+-------+-------+
| 39980 | 394 | 683 | 14 | 40361 |
+-------+-------+-------+-------+-------+
| 40398 | 830 | 691 | 15 | 40787 |
+-------+-------+-------+-------+-------+
| 40816 | 535 | 701 | 15 | 41213 |
+-------+-------+-------+-------+-------+
| 41226 | 199 | 701 | 15 | 41621 |
+-------+-------+-------+-------+-------+
| 41641 | 27 | 709 | 15 | 42043 |
+-------+-------+-------+-------+-------+
| 42067 | 298 | 709 | 15 | 42467 |
+-------+-------+-------+-------+-------+
| 42490 | 368 | 719 | 15 | 42899 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 42916 | 755 | 727 | 15 | 43331 |
+-------+-------+-------+-------+-------+
| 43388 | 379 | 727 | 15 | 43801 |
+-------+-------+-------+-------+-------+
| 43840 | 73 | 733 | 15 | 44257 |
+-------+-------+-------+-------+-------+
| 44279 | 387 | 739 | 15 | 44701 |
+-------+-------+-------+-------+-------+
| 44729 | 457 | 751 | 15 | 45161 |
+-------+-------+-------+-------+-------+
| 45183 | 761 | 751 | 15 | 45613 |
+-------+-------+-------+-------+-------+
| 45638 | 855 | 757 | 15 | 46073 |
+-------+-------+-------+-------+-------+
| 46104 | 370 | 769 | 15 | 46549 |
+-------+-------+-------+-------+-------+
| 46574 | 261 | 769 | 15 | 47017 |
+-------+-------+-------+-------+-------+
| 47047 | 299 | 787 | 15 | 47507 |
+-------+-------+-------+-------+-------+
| 47523 | 920 | 787 | 15 | 47981 |
+-------+-------+-------+-------+-------+
| 48007 | 269 | 787 | 15 | 48463 |
+-------+-------+-------+-------+-------+
| 48489 | 862 | 797 | 15 | 48953 |
+-------+-------+-------+-------+-------+
| 48976 | 349 | 809 | 15 | 49451 |
+-------+-------+-------+-------+-------+
| 49470 | 103 | 809 | 15 | 49943 |
+-------+-------+-------+-------+-------+
| 49978 | 115 | 821 | 15 | 50461 |
+-------+-------+-------+-------+-------+
| 50511 | 93 | 821 | 16 | 50993 |
+-------+-------+-------+-------+-------+
| 51017 | 982 | 827 | 16 | 51503 |
+-------+-------+-------+-------+-------+
| 51530 | 432 | 839 | 16 | 52027 |
+-------+-------+-------+-------+-------+
| 52062 | 340 | 853 | 16 | 52571 |
+-------+-------+-------+-------+-------+
| 52586 | 173 | 853 | 16 | 53093 |
+-------+-------+-------+-------+-------+
| 53114 | 421 | 857 | 16 | 53623 |
+-------+-------+-------+-------+-------+
| 53650 | 330 | 863 | 16 | 54163 |
+-------+-------+-------+-------+-------+
+-------+-------+-------+-------+-------+
| 54188 | 624 | 877 | 16 | 54713 |
+-------+-------+-------+-------+-------+
| 54735 | 233 | 877 | 16 | 55259 |
+-------+-------+-------+-------+-------+
| 55289 | 362 | 883 | 16 | 55817 |
+-------+-------+-------+-------+-------+
| 55843 | 963 | 907 | 16 | 56393 |
+-------+-------+-------+-------+-------+
| 56403 | 471 | 907 | 16 | 56951 |
+-------+-------+-------+-------+-------+
Table 2: Systematic Indices and Other Parameters
表2：体系的指標とその他のパラメータ
The remainder of this section describes the arithmetic operations that are used to generate encoding symbols from source symbols and to generate source symbols from encoding symbols. Mathematically, octets can be thought of as elements of a finite field, i.e., the finite field GF(256) with 256 elements, and thus the addition and multiplication operations and identity elements and inverses over both operations are defined. Matrix operations and symbol operations are defined based on the arithmetic operations on octets. This allows a full implementation of these arithmetic operations without having to understand the underlying mathematics of finite fields.
このセクションの残りの部分は、ソースシンボルから符号化シンボルを生成し、符号化シンボルからソースシンボルを生成するために使用される演算を記述する。数学的には、オクテットは256個の要素を有する、すなわち、有限体GF（256）、有限体の要素として考えることができ、従って、両方の操作上加算および乗算演算と同一要素および逆数が定義されます。行列演算とシンボル操作はオクテットで算術演算に基づいて定義されます。これは、有限体の基礎となる数学を理解することなく、これらの算術演算の完全な実装を可能にします。
Octets are mapped to non-negative integers in the range 0 through 255 in the usual way: A single octet of data from a symbol, B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0], where B[7] is the highest order bit and B[0] is the lowest order bit, is mapped to the integer i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0].
オクテットは通常の方法で255を介して範囲0で非負整数にマッピングされる：記号、Bからのデータの単一オクテット[7]、B [6]、B [5]、B [4]、B [ 3]、B [2]、B [1]、B [0]、B [7]最上位ビットとは、B [0]が最下位ビット、整数にマッピングされているここで、i = B [7] * 128 + B [6] * 64 + B [5] * 32 + B [4] * 16 + B [3] * 8 + B [2] * 4 + B [1] * 2 + B [0]。
The addition of two octets u and v is defined as the exclusive-or operation, i.e.,
uおよびvは、排他的論理和演算として定義される2つのオクテット、即ち添加、
u + v = u ^ v.
Y + S = YとC。
Subtraction is defined in the same way, so we also have
減算は同じように定義されているので、我々はまた、持っています
u - v = u ^ v.
そして - = Yです。
The zero element (additive identity) is the octet represented by the integer 0. The additive inverse of u is simply u, i.e.,
ゼロ要素（加法単位元）はUの加法逆数が単に整数0で表されるオクテットであるU、すなわち、
u + u = 0.
= Uはuが0であります+。
The multiplication of two octets is defined with the help of two tables OCT_EXP and OCT_LOG, which are given in Section 5.7.3 and Section 5.7.4, respectively. The table OCT_LOG maps octets (other than the zero element) to non-negative integers, and OCT_EXP maps non-negative integers to octets. For two octets u and v, we define
2つのオクテットの乗算は、それぞれ、5.7.3項および5.7.4項に記載されている二つのテーブルOCT_EXPとOCT_LOG、の助けを借りて定義されます。表OCT_LOGは非負整数に（ゼロ要素以外の）オクテットをマッピングし、そしてOCT_EXPはオクテットに非負の整数をマッピングします。 2つのオクテットuとvのために、私たちは定義します
u * v =
=のy *
0, if either u or v are 0,
0、UまたはVのいずれかが0であれば、
OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise.
OCT_EXP [OCT_LOG [U] + OCT_LOG [V]]そう。
Note that the '+' on the right-hand side of the above is the usual integer addition, since its arguments are ordinary integers.
その引数は通常の整数であることから、「+」上記の右側には、通常の整数の加算であることに注意してください。
The division u / v of two octets u and v, and where v != 0, is defined as follows:
！次のように部門の2つのオクテットuとvのU / V、およびV = 0は、定義されています。
u / v =
Y / C =
0, if u == 0,
0、U == 0の場合、
OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise.
OCT_EXP [OCT_LOG [U] - OCT_LOG [V] + 255]そう。
The one element (multiplicative identity) is the octet represented by the integer 1. For an octet u that is not the zero element, i.e., the multiplicative inverse of u is
一つの要素（乗法アイデンティティ）がゼロ要素、すなわちないオクテットUに対する整数1で表されるオクテットであり、Uの逆数であります
OCT_EXP[255 - OCT_LOG[u]].
OCT_EXP [255 - OCT_LOG [U]]。
The octet denoted by alpha is the octet with the integer representation 2. If i is a non-negative integer 0 <= i < 256, we have
iは非負の整数0である場合、αで表されるオクテットiが256 <= <、我々は整数表現2とオクテットであります
alpha^^i = OCT_EXP[i].
アルファ^^ I = OCT_EXP [I]。
The table OCT_EXP contains 510 octets. The indexing starts at 0 and ranges to 509, and the entries are the octets with the following positive integer representation:
テーブルOCT_EXPは510個のオクテットが含まれています。インデックスは0から始まり、509の範囲であり、エントリは以下の正の整数表現とオクテット以下のとおりです。
1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142
1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142
The table OCT_LOG contains 255 non-negative integers. The table is indexed by octets interpreted as integers. The octet corresponding to the zero element, which is represented by the integer 0, is excluded as an index, and thus indexing starts at 1 and ranges up to 255, and the entries are the following:
表OCT_LOGは255非負の整数が含まれています。テーブルは整数として解釈オクテットによって索引付けされます。整数0で表される零要素に対応するオクテットは、インデックスとして除外され、したがって、索引付けは1から始まり、255までの範囲であり、エントリは以下の通りです。
0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 175
166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 175
Operations on symbols have the same semantics as operations on vectors of octets of length T in this specification. Thus, if U and V are two symbols formed by the octets u[0], ..., u[T-1] and v[0], ..., v[T-1], respectively, the sum of symbols U + V is defined to be the component-wise sum of octets, i.e., equal to the symbol D formed by the octets d[0], ..., d[T-1], such that
シンボルの操作は、この仕様では、長さTのオクテットのベクトルでの操作と同じ意味を持っています。したがって、U及びVは、それぞれのu [0]、...、U [T-1]およびV [0]、...、V [T-1]、の和オクテットによって形成される2つのシンボルである場合記号U + Vは、すなわち、シンボルDに等しいオクテットによって形成されたように、[0]、...、D [T-1] D、オクテットの成分ごとの和であると定義されます
d[i] = u[i] + v[i], 0 <= i < T.
D [I] = U [i]が+ V [i]は、0 <= I <T.
Furthermore, if beta is an octet, the product beta*U is defined to be the symbol D obtained by multiplying each octet of U by beta, i.e.,
ベータは、オクテット、製品ベータ*であればさらに、Uは、すなわち、ベータによってUの各オクテットを乗じたシンボルDと定義されます、
d[i] = beta*u[i], 0 <= i < T.
D [i]は=ベータ* [i]が、0 <= iがTを<
All matrices in this specification have entries that are octets, and thus matrix operations and definitions are defined in terms of the underlying octet arithmetic, e.g., operations on a matrix, matrix rank, and matrix inversion.
本明細書におけるすべての行列は、行列、行列ランク、および行列反転に例えば、操作をオクテットであるエントリを有するので、行列演算や定義は、基礎となるオクテット演算によって定義されます。
If a RaptorQ-compliant decoder receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3 for reconstruction of a source block, then such a decoder SHOULD recover the entire source block.
RaptorQ準拠デコーダは、ソースブロックの再構成のためのセクション5.3でエンコーダの仕様に従って生成符号化シンボルの数学的に十分なセットを受信した場合、そのようなデコーダは、全体ソースブロックを回復するべきです。
A RaptorQ-compliant decoder SHALL have the following recovery properties for source blocks with K' source symbols for all values of K' in Table 2 of Section 5.6.
RaptorQ準拠の復号器は、セクション5.6の表2におけるK「Kのすべての値に対するソースシンボル」でソースブロックのための次の回復性を持たなければなりません。
1. If the decoder receives K' encoding symbols generated according to the encoder specification in Section 5.3 with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 100 times.
1.デコーダはのESI可能のESIの範囲からランダムに独立して、均一に選択された対応するセクション5.3エンコーダの仕様に従って生成K」符号化シンボルを受信した場合、その後、平均して、デコーダは、最大で全体ソースブロックを回復するために失敗します100回のうち1。
2. If the decoder receives K'+1 encoding symbols generated according to the encoder specification in Section 5.3 with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 10,000 times.
前記デコーダはのESI可能のESIの範囲からランダムに独立して、均一に選択された対応するセクション5.3エンコーダの仕様に従って生成K '+ 1つの符号化シンボルを受信した場合、その後、平均してデコーダが全体ソースブロックを回復するために失敗します10000回のうち1高々。
3. If the decoder receives K'+2 encoding symbols generated according to the encoder specification in Section 5.3 with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 1,000,000 times.
前記デコーダはのESI可能のESIの範囲からランダムに独立して、均一に選択された対応するセクション5.3エンコーダの仕様に従って生成K '+ 2符号化シンボルを受信した場合、平均してデコーダが全体ソースブロックを回復するために失敗します100万回のうちで最も1。
Note that the Example FEC Decoder specified in Section 5.4 fulfills both requirements, i.e.,
すなわち、セクション5.4で指定された例FECデコーダは、両方の要件を満たすことに注意してください
1. it can reconstruct a source block as long as it receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3, and
1.それはセクション5.3エンコーダの仕様に従って生成符号化シンボルの数学的に十分なセットを受信する限り、ソースブロックを再構成する、ことができ
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. 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-256 hash [FIPS.180-3.2008] of an object may be appended before transmission, and the SHA-256 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
データの配信は、受信機によって正当なものとして受け入れている破損したパケットを送信する攻撃者によってサービス拒否攻撃の対象にすることができます。破損したパケットが破損したパケットは、多くの受信機に到着した場合にマルチキャストツリーのルートに近いセッションに注入することができるので、これは特に、マルチキャスト配信のための関心事です。符号化データを含む一つでも破損したパケットの使用が完全に破損して使用不能であるオブジェクトの復号化をもたらし得ます。このようにチェック源認証と完全性をアプリケーションにオブジェクトを配信する前にデコードされたオブジェクトに適用することをお勧めします。例えば、オブジェクトのSHA-256ハッシュ[FIPS.180-3.2008]は、送信の前に付加することができる、及びSHA-256ハッシュが計算され、オブジェクトがデコードされた後にチェックし、それがアプリケーションに配信される前にされています。ソース認証は、例えば、ハッシュ値の計算上の受信機でデジタル署名が検証含めることによって、提供されるべきです。また、テスラ[RFC4082]などのパケット認証プロトコル検出および到着時に破損したパケットを廃棄するために使用することを推奨されています。この方法は、ソースの認証を提供するために使用されてもよいです。さらに、次のことが推奨されます
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.
リバースパス転送のチェックが成功したマルチキャストツリーのデータパスに破損したパケットを注入悪いエージェントの可能性を制限するために、受信機への送信者からのパスに沿ってすべてのネットワークルータとスイッチで有効になっています。
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]. IANA has assigned the value 6 under the ietf:rmt:fec:encoding registry to "RaptorQ Code" as the Fully-Specified FEC Encoding ID value associated with this specification.
FEC符号化IDとFECインスタンスIDの値は、IANA登録の対象となっています。彼らは、この文書に適用されるIANA問題に関する一般的なガイドラインについては、[RFC5052]を参照してください。 RMT：FEC：IANAは、IETFの下に値6を割り当てたコードレジストリこの仕様に関連付けられている完全に指定されたFEC符号化ID値として「RaptorQコード」に。
Thanks are due to Ranganathan (Ranga) Krishnan. Ranga Krishnan has been very supportive in finding and resolving implementation details and in finding the systematic indices. In addition, Habeeb Mohiuddin Mohammed and Antonios Pitarokoilis, both from the Munich University of Technology (TUM), and Alan Shinsato have done two independent implementations of the RaptorQ encoder/decoder that have helped to clarify and to resolve issues with this specification.
おかげでRanganathan氏（ランガ）クリシュナンによるものです。ランガクリシュナンは、実装の詳細を発見し、解決にかつ体系的指標を見つけることに非常に支持されています。また、技術のミュンヘン大学（TUM）、そしてアランShinsatoから両方Habeeb MohiuddinモハメッドとアントニオPitarokoilisは、明確にするために、この仕様の問題を解決するために助けたRaptorQエンコーダ/デコーダの二つの独立した実装を行っています。
[FIPS.180-3.2008] National Institute of Standards and Technology, "Secure Hash Standard", FIPS PUB 180-3, October 2008.
[FIPS.180-3.2008]米国国立標準技術研究所は、FIPS PUB 180-3の、2008年10月 "ハッシュ標準セキュア"。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2119]ブラドナーの、S.、 "要件レベルを示すためにRFCsにおける使用のためのキーワード"、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.、歌、D.、カネッティ、R.、Tygar、J.、およびB.ブリスコウ、 "時限効率ストリーム損失トレラント認証（テスラ）：マルチキャスト発信元認証は、はじめの変換"、RFC 4082、 2005年6月。
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction (FEC) Building Block", RFC 5052, August 2007.
[RFC5052]ワトソン、M.、ルビー、M.、およびL. Vicisano、 "前方誤り訂正（FEC）ビルディングブロック"、RFC 5052、2007年8月。
[LTCodes] Luby, M., "LT codes", Annual IEEE Symposium on Foundations of Computer Science, pp. 271-280, November 2002.
[LTCodes]ルビー、M.、 "LTコード"、年次IEEEシンポジウムコンピュータサイエンスの基礎、頁271-280、2002年11月に。
[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]ルビー、M.、Vicisano、L.、Gemmell、J.、リゾー、L.、ハンドレー、M.、およびJ.クロウクロフト、 "信頼できるマルチキャストの前方誤り訂正（FEC）の使用"、RFC 3453 、2002年12月。
[RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, "Raptor Forward Error Correction Scheme for Object Delivery", RFC 5053, October 2007.
[RFC5053]ルビー、M.、ショクロラヒ、A.、ワトソン、M.、およびT. Stockhammer、 "オブジェクトの配信のためのラプター前方誤り訂正方式"、RFC 5053、2007年10月。
[RaptorCodes] Shokrollahi, A. and M. Luby, "Raptor Codes", Foundations and Trends in Communications and Information Theory: Vol. 6: No. 3-4, pp. 213-322, 2011.
【RaptorCodes]ショクロラヒ、A.およびM.ルビー、「ラプターコード」、情報通信理論における基礎と動向：巻。 6：第3-4頁213から322、2011。
Authors' Addresses
著者のアドレス
Michael Luby Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A.
マイケル・ルビーQualcomm社3165 Kifer道州サンタクララ、CA 95051 U.S.A.
EMail: luby@qualcomm.com
メールアドレス：luby@qualcomm.com
Amin Shokrollahi EPFL Laboratoire d'algorithmique Station 14 Batiment BC Lausanne 1015 Switzerland
アミン・ショクロラヒアルゴリズムのEPFL研究所駅14 BCビル1015ローザンヌスイス
EMail: amin.shokrollahi@epfl.ch
メールアドレス：amin.shokrollahi@epfl.ch
Mark Watson Netflix Inc. 100 Winchester Circle Los Gatos, CA 95032 U.S.A.
マーク・ワトソンネットフリックス株式会社100ウィンチェスターサークルロスガトス、CA 95032 U.S.A.
EMail: watsonm@netflix.com
メールアドレス：watsonm@netflix.com
Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541 Germany
トーマスStockhammer Nomor研究Brecherspitzシュトラーセ8 81541ミュンヘンドイツ
EMail: stockhammer@nomor.de
メールアドレス：stockhammer@nomor.de
Lorenz Minder Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A.
ローレンツMinderのQualcomm社3165 Kifer道州サンタクララ、CA 95051 U.S.A.
EMail: lminder@qualcomm.com
メールアドレス：lminder@qualcomm.com