RFC 5053: Raptor Forward Error Correction Scheme for Object Delivery 中文翻译

URL : https://datatracker.ietf.org/doc/html/rfc5053
标题 : RFC 5053
翻译类型 : 自动生成

Network Working Group                                            M. Luby
Request for Comments: 5053                              Digital Fountain
Category: Standards Track                                 A. Shokrollahi
                                                                    EPFL
                                                               M. Watson
                                                        Digital Fountain
                                                          T. Stockhammer
                                                          Nomor Research
                                                            October 2007

Network Working Group                                            M. Luby
Request for Comments: 5053                              Digital Fountain
Category: Standards Track                                 A. Shokrollahi
                                                                    EPFL
                                                               M. Watson
                                                        Digital Fountain
                                                          T. Stockhammer
                                                          Nomor Research
                                                            October 2007

Raptor Forward Error Correction Scheme for Object Delivery

面向对象传输的Raptor前向纠错方案

Status of This Memo

关于下段备忘

This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.

本文件规定了互联网社区的互联网标准跟踪协议，并要求进行讨论和提出改进建议。有关本协议的标准化状态和状态，请参考当前版本的“互联网官方协议标准”（STD 1）。本备忘录的分发不受限制。

Abstract

摘要

This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 1, for the Raptor forward error correction code and its application to reliable delivery of data objects.

本文档描述了一种完全指定的前向纠错（FEC）方案，对应于FEC编码ID 1，用于Raptor前向纠错码及其在数据对象可靠传输中的应用。

Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a source block of data. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols.

Raptor是一种喷泉码，即编码器可以根据需要从数据源块的源符号动态生成尽可能多的编码符号。解码器能够从任何一组编码符号中恢复源块，其数量仅略多于源符号的数量。

The Raptor code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated.

这里描述的Raptor代码是一个系统代码，这意味着所有源符号都在可以生成的编码符号中。

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  3
   3.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  3
     3.1.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  3
     3.2.  FEC Object Transmission Information (OTI)  . . . . . . . .  4
       3.2.1.  Mandatory  . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.2.  Common . . . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.3.  Scheme-Specific  . . . . . . . . . . . . . . . . . . .  5
   4.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  5
     4.1.  Content Delivery Protocol Requirements . . . . . . . . . .  5
     4.2.  Example Parameter Derivation Algorithm . . . . . . . . . .  6
   5.  Raptor FEC Code Specification  . . . . . . . . . . . . . . . .  8
     5.1.  Definitions, Symbols, and Abbreviations  . . . . . . . . .  8
       5.1.1.  Definitions  . . . . . . . . . . . . . . . . . . . . .  8
       5.1.2.  Symbols  . . . . . . . . . . . . . . . . . . . . . . .  9
       5.1.3.  Abbreviations  . . . . . . . . . . . . . . . . . . . . 11
     5.2.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.3.  Object Delivery  . . . . . . . . . . . . . . . . . . . . . 12
       5.3.1.  Source Block Construction  . . . . . . . . . . . . . . 12
       5.3.2.  Encoding Packet Construction . . . . . . . . . . . . . 14
     5.4.  Systematic Raptor Encoder  . . . . . . . . . . . . . . . . 15
       5.4.1.  Encoding Overview  . . . . . . . . . . . . . . . . . . 15
       5.4.2.  First Encoding Step: Intermediate Symbol Generation  . 16
       5.4.3.  Second Encoding Step: LT Encoding  . . . . . . . . . . 20
       5.4.4.  Generators . . . . . . . . . . . . . . . . . . . . . . 21
     5.5.  Example FEC Decoder  . . . . . . . . . . . . . . . . . . . 23
       5.5.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 23
       5.5.2.  Decoding a Source Block  . . . . . . . . . . . . . . . 23
     5.6.  Random Numbers . . . . . . . . . . . . . . . . . . . . . . 28
       5.6.1.  The Table V0 . . . . . . . . . . . . . . . . . . . . . 28
       5.6.2.  The Table V1 . . . . . . . . . . . . . . . . . . . . . 29
     5.7.  Systematic Indices J(K)  . . . . . . . . . . . . . . . . . 30
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 43
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 43
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 44
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 44
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 44
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 44

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  3
   3.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  3
     3.1.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  3
     3.2.  FEC Object Transmission Information (OTI)  . . . . . . . .  4
       3.2.1.  Mandatory  . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.2.  Common . . . . . . . . . . . . . . . . . . . . . . . .  4
       3.2.3.  Scheme-Specific  . . . . . . . . . . . . . . . . . . .  5
   4.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  5
     4.1.  Content Delivery Protocol Requirements . . . . . . . . . .  5
     4.2.  Example Parameter Derivation Algorithm . . . . . . . . . .  6
   5.  Raptor FEC Code Specification  . . . . . . . . . . . . . . . .  8
     5.1.  Definitions, Symbols, and Abbreviations  . . . . . . . . .  8
       5.1.1.  Definitions  . . . . . . . . . . . . . . . . . . . . .  8
       5.1.2.  Symbols  . . . . . . . . . . . . . . . . . . . . . . .  9
       5.1.3.  Abbreviations  . . . . . . . . . . . . . . . . . . . . 11
     5.2.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.3.  Object Delivery  . . . . . . . . . . . . . . . . . . . . . 12
       5.3.1.  Source Block Construction  . . . . . . . . . . . . . . 12
       5.3.2.  Encoding Packet Construction . . . . . . . . . . . . . 14
     5.4.  Systematic Raptor Encoder  . . . . . . . . . . . . . . . . 15
       5.4.1.  Encoding Overview  . . . . . . . . . . . . . . . . . . 15
       5.4.2.  First Encoding Step: Intermediate Symbol Generation  . 16
       5.4.3.  Second Encoding Step: LT Encoding  . . . . . . . . . . 20
       5.4.4.  Generators . . . . . . . . . . . . . . . . . . . . . . 21
     5.5.  Example FEC Decoder  . . . . . . . . . . . . . . . . . . . 23
       5.5.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 23
       5.5.2.  Decoding a Source Block  . . . . . . . . . . . . . . . 23
     5.6.  Random Numbers . . . . . . . . . . . . . . . . . . . . . . 28
       5.6.1.  The Table V0 . . . . . . . . . . . . . . . . . . . . . 28
       5.6.2.  The Table V1 . . . . . . . . . . . . . . . . . . . . . 29
     5.7.  Systematic Indices J(K)  . . . . . . . . . . . . . . . . . 30
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 43
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 43
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 44
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 44
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 44
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 44

1. Introduction

1. 介绍

This document specifies an FEC Scheme for the Raptor forward error correction code for object delivery applications. The concept of an FEC Scheme is defined in [RFC5052] and this document follows the format prescribed there and uses the terminology of that document. Raptor Codes were introduced in [Raptor]. For an overview, see, for example, [CCNC].

本文件规定了用于对象交付应用的Raptor前向纠错码的FEC方案。FEC方案的概念在[RFC5052]中定义，本文件遵循其中规定的格式，并使用该文件的术语。Raptor代码是在[Raptor]中引入的。有关概述，请参阅，例如[CCNC]。

The Raptor FEC Scheme is a Fully-Specified FEC Scheme corresponding to FEC Encoding ID 1.

Raptor FEC方案是与FEC编码ID 1相对应的完全指定的FEC方案。

Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a block. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols.

Raptor是一种喷泉码，即编码器可以根据需要从块的源符号动态生成任意数量的编码符号。解码器能够从任何一组编码符号中恢复源块，其数量仅略多于源符号的数量。

The code described in this document is a systematic code, that is, the original source symbols can be sent unmodified from sender to receiver, as well as a number of repair symbols. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC3453].

本文档中描述的代码是一个系统代码，即原始源符号可以不经修改地从发送方发送到接收方，以及许多修复符号。有关在可靠多播中使用前向纠错码的更多背景信息，请参阅[RFC3453]。

The code described here is identical to that described in [MBMS].

此处描述的代码与[MBMS]中描述的代码相同。

2. Requirements Notation

2. 需求符号

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].

本文件中的关键词“必须”、“不得”、“必需”、“应”、“不应”、“应”、“不应”、“建议”、“可”和“可选”应按照[RFC2119]中所述进行解释。

3. Formats and Codes

3. 格式和代码

3.1. FEC Payload IDs

3.1. 有效载荷ID

The FEC Payload ID MUST be a 4 octet field defined as follows:

FEC有效负载ID必须是定义如下的4个八位字节字段：

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Source Block Number       |      Encoding Symbol ID       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Source Block Number       |      Encoding Symbol ID       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 1: FEC Payload ID format

图1:FEC有效负载ID格式

Source Block Number (SBN), (16 bits): An integer identifier for the source block that the encoding symbols within the packet relate to.

源块编号（SBN）（16位）：数据包内编码符号所涉及的源块的整数标识符。

Encoding Symbol ID (ESI), (16 bits): An integer identifier for the encoding symbols within the packet.

编码符号ID（ESI）（16位）：数据包内编码符号的整数标识符。

The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 5.

第5节定义了源块号和编码符号标识符的解释。

3.2. FEC Object Transmission Information (OTI)

3.2. FEC对象传输信息（OTI）

3.2.1. Mandatory

3.2.1. 强制性的

The value of the FEC Encoding ID MUST be 1 (one), as assigned by IANA (see Section 7).

根据IANA的分配，FEC编码ID的值必须为1（一）（见第7节）。

3.2.2. Common

3.2.2. 常见的

The Common FEC Object Transmission Information elements used by this FEC Scheme are:

该FEC方案使用的公共FEC对象传输信息元素为：

- Transfer Length (F)

- 传输长度（F）

- Encoding Symbol Length (T)

- 编码符号长度（T）

The Transfer Length is a non-negative integer less than 2^^45. The Encoding Symbol Length is a non-negative integer less than 2^^16.

传输长度是小于2^^45的非负整数。编码符号长度是小于2^^16的非负整数。

The encoded Common FEC Object Transmission Information format is shown in Figure 2.

编码的公共FEC对象传输信息格式如图2所示。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Transfer Length                          |
      +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               |           Reserved            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Encoding Symbol Length     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Transfer Length                          |
      +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               |           Reserved            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Encoding Symbol Length     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 2: Encoded Common FEC OTI for Raptor FEC Scheme

图2:Raptor FEC方案的编码公共FEC OTI

      NOTE 1: The limit of 2^^45 on the transfer length is a consequence
      of the limitation on the symbol size to 2^^16-1, the limitation on
      the number of symbols in a source block to 2^^13, and the

      NOTE 1: The limit of 2^^45 on the transfer length is a consequence
      of the limitation on the symbol size to 2^^16-1, the limitation on
      the number of symbols in a source block to 2^^13, and the

limitation on the number of source blocks to 2^^16. However, the Transfer Length is encoded as a 48-bit field for simplicity.

源块数量限制为2^^16。然而，为了简单起见，传输长度被编码为48位字段。

3.2.3. Scheme-Specific

3.2.3. 特定计划

The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC Scheme:

在该FEC方案的方案特定FEC对象传输信息元素中携带以下参数：

- The number of source blocks (Z)

- 源块的数量（Z）

- The number of sub-blocks (N)

- 子块的数量（N）

- A symbol alignment parameter (Al)

- 符号对齐参数（Al）

These parameters are all non-negative integers. The encoded Scheme-specific Object Transmission Information is a 4-octet field consisting of the parameters Z (2 octets), N (1 octet), and Al (1 octet) as shown in Figure 3.

这些参数都是非负整数。编码的方案特定对象传输信息是一个4-八位组字段，由参数Z（2个八位组）、N（1个八位组）和Al（1个八位组）组成，如图3所示。

        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      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |             Z                 |      N        |       Al      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 3: Encoded Scheme-Specific FEC Object Transmission Information

图3：编码方案特定FEC对象传输信息

The encoded FEC Object Transmission Information is a 14-octet field consisting of the concatenation of the encoded Common FEC Object Transmission Information and the encoded Scheme-Specific FEC Object Transmission Information.

编码的FEC对象传输信息是由编码的公共FEC对象传输信息和编码的方案特定的FEC对象传输信息的级联组成的14个八位组字段。

These three parameters define the source block partitioning as described in Section 5.3.1.2.

这三个参数定义了第5.3.1.2节所述的源块分区。

4. Procedures

4. 程序

4.1. Content Delivery Protocol Requirements

4.1. 内容交付协议要求

This section describes the information exchange between the Raptor FEC Scheme and any Content Delivery Protocol (CDP) that makes use of the Raptor FEC Scheme for object delivery.

本节描述Raptor FEC方案与任何使用Raptor FEC方案进行对象交付的内容交付协议（CDP）之间的信息交换。

The Raptor encoder and decoder for object delivery require the following information from the CDP:

用于对象交付的Raptor编码器和解码器需要CDP提供以下信息：

- The transfer length of the object, F, in bytes

- 对象的传输长度F，以字节为单位

- A symbol alignment parameter, Al

- 符号对齐参数Al

- The symbol size, T, in bytes, which MUST be a multiple of Al

- 符号大小T，以字节为单位，必须是Al的倍数

- The number of source blocks, Z

- 源块的数目，Z

- The number of sub-blocks in each source block, N

- 每个源块中的子块数，N

The Raptor encoder for object delivery additionally requires:

用于对象交付的Raptor编码器还需要：

- the object to be encoded, F bytes

- 要编码的对象，F字节

The Raptor encoder supplies the CDP with the following information for each packet to be sent:

Raptor编码器为要发送的每个数据包向CDP提供以下信息：

- Source Block Number (SBN)

- 源块编号（SBN）

- Encoding Symbol ID (ESI)

- 编码符号ID（ESI）

- Encoding symbol(s)

- 编码符号

The CDP MUST communicate this information to the receiver.

CDP必须将此信息传达给接收器。

4.2. Example Parameter Derivation Algorithm

4.2. 示例参数推导算法

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:

本节提供了推导三个传输参数T、Z和N的建议。该建议基于以下输入参数：

- F the transfer length of the object, in bytes

- F对象的传输长度，以字节为单位

- W a target on the sub-block size, in bytes

- W子块大小上的目标，以字节为单位

- P the maximum packet payload size, in bytes, which is assumed to be a multiple of Al

- P最大数据包有效负载大小，以字节为单位，假定为Al的倍数

- Al the symbol alignment parameter, in bytes

- Al符号对齐参数，以字节为单位

- Kmax the maximum number of source symbols per source block.

- Kmax每个源块的最大源符号数。

Note: Section 5.1.2 defines Kmax to be 8192.

注：第5.1.2节将Kmax定义为8192。

- Kmin a minimum target on the number of symbols per source block

- Kmin是每个源块上符号数的最小目标

- Gmax a maximum target number of symbols per packet

- Gmax每个数据包的最大目标符号数

Based on the above inputs, the transport parameters T, Z, and N are calculated as follows:

基于上述输入，传输参数T、Z和N的计算如下：

Let

允许

      G = min{ceil(P*Kmin/F), P/Al, Gmax}

      G = min{ceil(P*Kmin/F), P/Al, Gmax}

      T = floor(P/(Al*G))*Al

      T = floor(P/(Al*G))*Al

      Kt = ceil(F/T)

      Kt = ceil(F/T)

      Z = ceil(Kt/Kmax)

      Z = ceil(Kt/Kmax)

      N = min{ceil(ceil(Kt/Z)*T/W), T/Al}

      N = min{ceil(ceil(Kt/Z)*T/W), T/Al}

The value G represents the maximum number of symbols to be transported in a single packet. The value Kt is the total number of symbols required to represent the source data of the object. The values of G and N derived above should be considered as lower bounds. It may be advantageous to increase these values, for example, to the nearest power of two. In particular, the above algorithm does not guarantee that the symbol size, T, divides the maximum packet size, P, and so it may not be possible to use the packets of size exactly P. If, instead, G is chosen to be a value that divides P/Al, then the symbol size, T, will be a divisor of P and packets of size P can be used.

值G表示单个分组中要传输的最大符号数。值Kt是表示对象源数据所需的符号总数。上面导出的G和N值应视为下限。例如，将这些值增加到最接近的二次方可能是有利的。特别地，上述算法不保证符号大小T除以最大分组大小P，因此可能不可能精确地使用大小为P的分组。相反，如果选择G作为除以P/Al的值，则符号大小T将是P的除数，并且可以使用大小为P的分组。

The algorithm above and that defined in Section 5.3.1.2 ensure that the sub-symbol sizes are a multiple of the symbol alignment parameter, Al. This is useful because the XOR operations used for encoding and decoding are generally performed several bytes at a time, for example, at least 4 bytes at a time on a 32-bit processor. Thus, the encoding and decoding can be performed faster if the sub-symbol sizes are a multiple of this number of bytes.

上述算法和第5.3.1.2节中定义的算法确保子符号大小是符号对齐参数Al的倍数。这是有用的，因为用于编码和解码的异或操作通常一次执行几个字节，例如，在32位处理器上一次至少执行4个字节。因此，如果子符号大小是这个字节数的倍数，则可以更快地执行编码和解码。

Recommended settings for the input parameters, Al, Kmin, and Gmax are as follows: Al = 4, Kmin = 1024, Gmax = 10.

输入参数Al、Kmin和Gmax的建议设置如下：Al=4、Kmin=1024、Gmax=10。

The parameter W can be used to generate encoded data that can be decoded efficiently with limited working memory at the decoder. Note that the actual maximum decoder memory requirement for a given value of W depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than W.

参数W可用于生成可在解码器处使用有限的工作存储器有效解码的编码数据。请注意，给定值W的实际最大解码器内存需求取决于实现，但可以仅使用略大于W的工作内存来实现解码。

5. Raptor FEC Code Specification

5. 猛禽FEC代码规范

5.1. Definitions, Symbols, and Abbreviations

5.1. 定义、符号和缩写

5.1.1. Definitions

5.1.1. 定义

For the purposes of this specification, the following terms and definitions apply.

在本规范中，以下术语和定义适用。

Source block: a block of K source symbols that are considered together for Raptor encoding purposes.

源代码块：为Raptor编码目的而考虑在一起的K个源代码块。

Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size.

源符号：编码过程中使用的最小数据单位。源块中的所有源符号具有相同的大小。

Encoding symbol: a symbol that is included in a data packet. The encoding symbols consist of the source symbols and the repair symbols. Repair symbols generated from a source block have the same size as the source symbols of that source block.

编码符号：包含在数据包中的符号。编码符号包括源符号和修复符号。从源块生成的修复符号的大小与该源块的源符号的大小相同。

Systematic code: a code in which all the source symbols may be included as part of the encoding symbols sent for a source block.

系统代码：一种代码，其中所有源符号可作为为源块发送的编码符号的一部分。

Repair symbol: the encoding symbols sent for a source block that are not the source symbols. The repair symbols are generated based on the source symbols.

修复符号：为非源符号的源块发送的编码符号。修复符号基于源符号生成。

Intermediate symbols: symbols generated from the source symbols using an inverse encoding process . The repair symbols are then generated directly from the intermediate symbols. The encoding symbols do not include the intermediate symbols, i.e., intermediate symbols are not included in data packets.

中间符号：使用反向编码过程从源符号生成的符号。然后直接从中间符号生成修复符号。编码符号不包括中间符号，即，中间符号不包括在数据分组中。

Symbol: a unit of data. The size, in bytes, of a symbol is known as the symbol size.

符号：一种数据单位。符号的大小（以字节为单位）称为符号大小。

Encoding symbol group: a group of encoding symbols that are sent together, i.e., within the same packet whose relationship to the source symbols can be derived from a single Encoding Symbol ID.

编码符号组：一起发送的一组编码符号，即在同一数据包内，其与源符号的关系可从单个编码符号ID中导出。

Encoding Symbol ID: information that defines the relationship between the symbols of an encoding symbol group and the source symbols.

编码符号ID：定义编码符号组的符号与源符号之间关系的信息。

Encoding packet: data packets that contain encoding symbols

编码包：包含编码符号的数据包

Sub-block: a source block is sometimes broken into sub-blocks, each of which is sufficiently small to be decoded in working memory. For a source block consisting of K source symbols, each sub-block consists of K sub-symbols, each symbol of the source block being composed of one sub-symbol from each sub-block.

子块：源块有时被分成子块，每个子块足够小，可以在工作内存中解码。对于由K个源符号组成的源块，每个子块由K个子符号组成，源块的每个符号由来自每个子块的一个子符号组成。

Sub-symbol: part of a symbol. Each source symbol is composed of as many sub-symbols as there are sub-blocks in the source block.

子符号：符号的一部分。每个源符号由与源块中的子块数量相同的子符号组成。

Source packet: data packets that contain source symbols.

源数据包：包含源符号的数据包。

Repair packet: data packets that contain repair symbols.

修复包：包含修复符号的数据包。

5.1.2. Symbols

5.1.2. 象征

i, j, x, h, a, b, d, v, m represent positive integers.

i、 j，x，h，a，b，d，v，m代表正整数。

ceil(x) denotes the smallest positive integer that is greater than or equal to x.

ceil（x）表示大于或等于x的最小正整数。

choose(i,j) denotes the number of ways j objects can be chosen from among i objects without repetition.

choose（i，j）表示可以从i个对象中选择j个对象而无需重复的方式的数量。

floor(x) denotes the largest positive integer that is less than or equal to x.

floor（x）表示小于或等于x的最大正整数。

i % j denotes i modulo j.

i%j表示i模j。

X ^ Y denotes, for equal-length bit strings X and Y, the bitwise exclusive-or of X and Y.

对于等长位字符串X和Y，X^Y表示X和Y的位异或。

Al denotes a symbol alignment parameter. Symbol and sub-symbol sizes are restricted to be multiples of Al.

Al表示符号对齐参数。符号和子符号大小限制为Al的倍数。

A denotes a matrix over GF(2).

A表示GF（2）上的矩阵。

Transpose[A] denotes the transposed matrix of matrix A.

转置[A]表示矩阵A的转置矩阵。

A^^-1 denotes the inverse matrix of matrix A.

A^^-1表示矩阵A的逆矩阵。

K denotes the number of symbols in a single source block.

K表示单个源块中的符号数。

Kmax denotes the maximum number of source symbols that can be in a single source block. Set to 8192.

Kmax表示单个源块中可以包含的最大源符号数。设置为8192。

L denotes the number of pre-coding symbols for a single source block.

L表示单个源块的预编码符号数。

S denotes the number of LDPC symbols for a single source block.

S表示单个源块的LDPC符号数。

H denotes the number of Half symbols for a single source block.

H表示单个源块的半个符号数。

C denotes an array of intermediate symbols, C[0], C[1], C[2],..., C[L-1].

C表示中间符号的数组，C[0]，C[1]，C[2]，…，C[L-1]。

C' denotes an array of source symbols, C'[0], C'[1], C'[2],..., C'[K-1].

C'表示源符号的数组，C'[0]，C'[1]，C'[2]，…，C'[K-1]。

X a non-negative integer value

X一个非负整数值

V0, V1 two arrays of 4-byte integers, V0[0], V0[1],..., V0[255] and V1[0], V1[1],..., V1[255]

V0，V1两个4字节整数数组，V0[0]，V0[1]，…，V0[255]和V1[0]，V1[1]，…，V1[255]

Rand[X, i, m] a pseudo-random number generator

Rand[X，i，m]伪随机数生成器

Deg[v] a degree generator

度[v]度发生器

LTEnc[K, C ,(d, a, b)] a LT encoding symbol generator

LTEnc[K，C，（d，a，b）]一种LT编码符号发生器

Trip[K, X] a triple generator function

跳闸[K，X]三重发电机功能

G the number of symbols within an encoding symbol group

G编码符号组中的符号数

GF(n) the Galois field with n elements.

GF（n）具有n个元素的伽罗瓦场。

N the number of sub-blocks within a source block

N源块内的子块数

T the symbol size in bytes. If the source block is partitioned into sub-blocks, then T = T'*N.

T以字节为单位的符号大小。如果源块被划分为子块，则T=T'*N。

T' the sub-symbol size, in bytes. If the source block is not partitioned into sub-blocks, then T' is not relevant.

T'子符号大小，以字节为单位。如果源块未划分为子块，则T'不相关。

F the transfer length of an object, in bytes

F对象的传输长度，以字节为单位

I the sub-block size in bytes

I子块大小（以字节为单位）

P for object delivery, the payload size of each packet, in bytes, that is used in the recommended derivation of the object delivery transport parameters.

P对于对象传递，每个数据包的有效负载大小，以字节为单位，用于推荐的对象传递传输参数推导。

   Q    Q = 65521, i.e., Q is the largest prime smaller than 2^^16

   Q    Q = 65521, i.e., Q is the largest prime smaller than 2^^16

Z the number of source blocks, for object delivery

Z源块的数量，用于对象传递

J(K) the systematic index associated with K

J（K）与K相关的系统指数

I_S denotes the SxS identity matrix.

I_S表示SxS单位矩阵。

0_SxH denotes the SxH zero matrix.

0_SxH表示SxH零矩阵。

a ^^ b a raised to the power b

a^^b a提升到b的幂

5.1.3. Abbreviations

5.1.3. 缩写

For the purposes of the present document, the following abbreviations apply:

在本文件中，以下缩写词适用：

ESI Encoding Symbol ID

ESI编码符号ID

LDPC Low Density Parity Check

低密度奇偶校验

LT Luby Transform

吕比变换

SBN Source Block Number

源块号

SBL Source Block Length (in units of symbols)

SBL源块长度（以符号为单位）

5.2. Overview

5.2. 概述

The principal component of the systematic Raptor code is the basic encoder described in Section 5.4. First, it is described how to derive values for a set of intermediate symbols from the original source symbols such that knowledge of the intermediate symbols is sufficient to reconstruct the source symbols. Secondly, the encoder produces repair symbols, which are each the exclusive OR of a number of the intermediate symbols. The encoding symbols are the combination of the source and repair symbols. The repair symbols are produced in such a way that the intermediate symbols, and therefore also the source symbols, can be recovered from any sufficiently large set of encoding symbols.

系统猛禽代码的主要组成部分是第5.4节所述的基本编码器。首先，描述如何从原始源符号导出一组中间符号的值，使得中间符号的知识足以重构源符号。其次，编码器产生修复符号，每个修复符号都是多个中间符号的异或。编码符号是源符号和修复符号的组合。修复符号以这样的方式产生，即中间符号以及源符号可以从任何足够大的编码符号集合中恢复。

This document specifies the systematic Raptor code encoder. A number of possible decoding algorithms are possible. An efficient decoding algorithm is provided in Section 5.5.

本文件规定了系统猛禽编码编码器。许多可能的解码算法是可能的。第5.5节提供了一种有效的解码算法。

The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section 5.4.4.1. This generator is based on a fixed set of 512 random numbers that MUST be available to both sender and receiver. These are provided in Section 5.6.

中间符号和维修符号的构造部分基于第5.4.4.1节所述的伪随机数生成器。此生成器基于发送方和接收方都必须可用的512个固定随机数集。这些在第5.6节中提供。

Finally, the construction of the intermediate symbols from the source symbols is governed by a 'systematic index', values of which are provided in Section 5.7 for source block sizes from 4 source symbols to Kmax = 8192 source symbols.

最后，源符号中间符号的构造由“系统索引”控制，第5.7节提供了从4个源符号到Kmax=8192个源符号的源块大小的“系统索引”值。

5.3. Object Delivery

5.3. 对象传递

5.3.1. Source Block Construction

5.3.1. 源块构造

5.3.1.1. General

5.3.1.1. 全体的

In order to apply the Raptor encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The Raptor encoder is applied independently to each source block. Each source block is identified by a unique integer Source Block Number (SBN), where the first source block has SBN zero, the second has SBN one, etc. Each source block is divided into a number, K, of source symbols of size T bytes each. Each source symbol is identified by a unique integer Encoding Symbol Identifier (ESI), where the first source symbol of a source block has ESI zero, the second has ESI one, etc.

为了将Raptor编码器应用于源对象，可以将对象分解为Z>=1个块，称为源块。Raptor编码器独立应用于每个源块。每个源块由唯一的整数源块编号（SBN）标识，其中第一个源块的SBN为零，第二个源块的SBN为一，等等。每个源块被划分为若干个K，每个K的源符号大小为T字节。每个源符号由唯一的整数编码符号标识符（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 5.3.1.2 below.

注意，对于对象的每个源块，K的值不一定相同，对于源块的每个子块，T’的值也不一定相同。然而，对于对象的所有源块，符号大小T是相同的，并且对于源块的每个子块，符号的数目K是相同的。下文第5.3.1.2节描述了将对象精确划分为源块和子块的过程。

5.3.1.2. Source Block and Sub-Block Partitioning

5.3.1.2. 源块和子块分区

The construction of source blocks and sub-blocks is determined based on five input parameters, F, Al, T, Z, and N, and a function Partition[]. The five input parameters are defined as follows:

源块和子块的构造基于五个输入参数F、Al、T、Z和N以及函数划分[]确定。五个输入参数定义如下：

- F the transfer length of the object, in bytes

- F对象的传输长度，以字节为单位

- Al a symbol alignment parameter, in bytes

- 所有符号对齐参数，以字节为单位

- T the symbol size, in bytes, which MUST be a multiple of Al

- T符号大小，以字节为单位，必须是Al的倍数

- Z the number of source blocks

- Z源块的数量

- N the number of sub-blocks in each source block

- N每个源块中的子块数

These parameters MUST be set so that ceil(ceil(F/T)/Z) <= Kmax. Recommendations for derivation of these parameters are provided in Section 4.2.

必须设置这些参数，使ceil（ceil（F/T）/Z）<=Kmax。第4.2节提供了推导这些参数的建议。

The function Partition[] takes a pair of integers (I, J) as input and derives four integers (IL, IS, JL, JS) as output. Specifically, the value of Partition[I, J] is a sequence of four integers (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL. Partition[] derives parameters for partitioning a block of size I into J approximately equal-sized blocks. Specifically, JL blocks of length IL and JS blocks of length IS.

函数分区[]将一对整数（I，J）作为输入，并导出四个整数（IL，IS，JL，JS）作为输出。具体地说，分区[I，J]的值是四个整数（IL，is，JL，JS）的序列，其中IL=ceil（I/J）、is=floor（I/J）、JL=I-is*J和JS=J-JL。Partition[]派生用于将大小为I的块划分为大小大致相同的J块的参数。具体来说，长度为IL的JL块和长度为JS的JS块是。

The source object MUST be partitioned into source blocks and sub-blocks as follows:

源对象必须按如下方式划分为源块和子块：

Let

允许

      Kt = ceil(F/T)

      Kt = ceil(F/T)

(KL, KS, ZL, ZS) = Partition[Kt, Z]

（KL，KS，ZL，ZS）=分区[Kt，Z]

(TL, TS, NL, NS) = Partition[T/Al, N]

（TL，TS，NL，NS）=分区[T/Al，N]

Then, the object MUST be partitioned into Z = ZL + ZS contiguous source blocks, the first ZL source blocks each having length KL*T bytes, and the remaining ZS source blocks each having KS*T bytes.

然后，必须将对象划分为Z=ZL+ZS连续源块，第一个ZL源块每个具有长度KL*T字节，其余ZS源块每个具有KS*T字节。

If Kt*T > F, then for encoding purposes, the last symbol MUST be padded at the end with Kt*T - F zero bytes.

如果Kt*T>F，那么出于编码目的，最后一个符号必须在末尾用Kt*T-F零字节填充。

Next, each source block MUST be divided into N = NL + NS contiguous sub-blocks, the first NL sub-blocks each consisting of K contiguous sub-symbols of size of TL*Al and the remaining NS sub-blocks each consisting of K contiguous sub-symbols of size of TS*Al. The symbol alignment parameter Al ensures that sub-symbols are always a multiple of Al bytes.

接下来，每个源块必须划分为N=NL+NS个连续子块，第一个NL子块每个由大小为TL*Al的K个连续子符号组成，其余的NS子块每个由大小为TS*Al的K个连续子符号组成。符号对齐参数Al确保子符号始终是Al字节的倍数。

Finally, the m-th symbol of a source block consists of the concatenation of the m-th sub-symbol from each of the N sub-blocks. Note that this implies that when N > 1, then a symbol is NOT a contiguous portion of the object.

最后，源块的第m个符号包括来自N个子块中的每一个子块的第m个子符号的串联。注意，这意味着当N>1时，符号不是对象的连续部分。

5.3.2. Encoding Packet Construction

5.3.2. 编码包构造

Each encoding packet contains the following information:

每个编码包包含以下信息：

- Source Block Number (SBN)

- 源块编号（SBN）

- Encoding Symbol ID (ESI)

- 编码符号ID（ESI）

- encoding symbol(s)

- 编码符号

Each source block is encoded independently of the others. Source blocks are numbered consecutively from zero.

每个源块独立于其他源块进行编码。源块从零开始连续编号。

Encoding Symbol ID values from 0 to K-1 identify the source symbols of a source block in sequential order, where K is the number of symbols in the source block. Encoding Symbol IDs from K onwards identify repair symbols.

从0到K-1的编码符号ID值按顺序标识源块的源符号，其中K是源块中的符号数。从K开始的编码符号标识标识修复符号。

Each encoding packet either consists entirely of source symbols (source packet) or entirely of repair symbols (repair packet). A packet may contain any number of symbols from the same source block. In the case that the last source symbol in a source packet includes padding bytes added for FEC encoding purposes, then these bytes need not be included in the packet. Otherwise, only whole symbols MUST be included.

每个编码包要么完全由源符号（源包）组成，要么完全由修复符号（修复包）组成。数据包可以包含来自同一源块的任意数量的符号。在源分组中的最后一个源符号包括为FEC编码目的而添加的填充字节的情况下，则这些字节不需要包括在分组中。否则，只能包含整个符号。

The Encoding Symbol ID, X, carried in each source packet is the Encoding Symbol ID of the first source symbol carried in that packet. The subsequent source symbols in the packet have Encoding Symbol IDs, X+1 to X+G-1, in sequential order, where G is the number of symbols in the packet.

每个源分组中携带的编码符号ID X是该分组中携带的第一个源符号的编码符号ID。分组中的后续源符号以顺序具有编码符号id X+1到X+G-1，其中G是分组中的符号数。

Similarly, the Encoding Symbol ID, X, placed into a repair packet is the Encoding Symbol ID of the first repair symbol in the repair packet and the subsequent repair symbols in the packet have Encoding Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of symbols in the packet.

类似地，放入修复分组中的编码符号ID X是修复分组中的第一个修复符号的编码符号ID，并且分组中的后续修复符号按顺序具有编码符号ID X+1到X+G-1，其中G是分组中的符号数。

Note that it is not necessary for the receiver to know the total number of repair packets.

注意，接收机不必知道修复包的总数。

Associated with each symbol is a triple of integers (d, a, b).

与每个符号相关联的是三重整数（d、a、b）。

The G repair symbol triples (d[0], a[0], b[0]),..., (d[G-1], a[G-1], b[G-1]) for the repair symbols placed into a repair packet with ESI X are computed using the Triple generator defined in Section 5.4.4.4 as follows:

使用第5.4.4.4节中定义的三元组生成器，计算放入带有ESI X的维修包中的维修符号的G维修符号三元组（d[0]，a[0]，b[0]），…，（d[G-1]，a[G-1]，b[G-1]），如下所示：

      For each i = 0, ..., G-1, (d[i], a[i], b[i]) = Trip[K,X+i]

      For each i = 0, ..., G-1, (d[i], a[i], b[i]) = Trip[K,X+i]

The G repair symbols to be placed in repair packet with ESI X are calculated based on the repair symbol triples, as described in Section 5.4, using the intermediate symbols C and the LT encoder LTEnc[K, C, (d[i], a[i], b[i])].

根据第5.4节所述的修复符号三元组，使用中间符号C和LT编码器LTEnc[K，C，（d[i]，a[i]，b[i]），计算要放置在具有ESI X的修复包中的G修复符号。

5.4. Systematic Raptor Encoder

5.4. 系统猛禽编码器

5.4.1. Encoding Overview

5.4.1. 编码概述

The systematic Raptor encoder is used to generate repair symbols from a source block that consists of K source symbols.

系统Raptor编码器用于从由K个源符号组成的源块生成修复符号。

Symbols are the fundamental data units of the encoding and decoding process. For each source block (sub-block), all symbols (sub-symbols) are the same size. The atomic operation performed on symbols (sub-symbols) for both encoding and decoding is the exclusive-or operation.

符号是编码和解码过程的基本数据单元。对于每个源块（子块），所有符号（子符号）的大小相同。对编码和解码的符号（子符号）执行的原子操作是异或操作。

Let C'[0],..., C'[K-1] denote the K source symbols.

设C'[0]，…，C'[K-1]表示K个源符号。

Let C[0],..., C[L-1] denote L intermediate symbols.

设C[0]，…，C[L-1]表示L个中间符号。

The first step of encoding is to generate a number, L > K, of intermediate symbols from the K source symbols. In this step, K source symbol triples (d[0], a[0], b[0]), ..., (d[K-1], a[K-1], b[K-1]) are generated using the Trip[] generator as described in Section 5.4.2.2. The K source symbol triples are associated with the K source symbols and are then used to determine the L intermediate symbols C[0],..., C[L-1] from the source symbols using an inverse encoding process. This process can be realized by a Raptor decoding process.

编码的第一步是从K个源符号生成多个中间符号，L>K。在此步骤中，使用跳闸[]发生器生成K源符号三元组（d[0]，a[0]，b[0]），…，（d[K-1]，a[K-1]，b[K-1]），如第5.4.2.2节所述。K个源符号三元组与K个源符号相关联，然后使用逆编码过程从源符号确定L个中间符号C[0]、…、C[L-1]。这个过程可以通过Raptor解码过程来实现。

Certain "pre-coding relationships" MUST hold within the L intermediate symbols. Section 5.4.2.3 describes these relationships and how the intermediate symbols are generated from the source symbols.

某些“预编码关系”必须在L中间符号中保持。第5.4.2.3节描述了这些关系以及如何从源符号生成中间符号。

Once the intermediate symbols have been generated, repair symbols are produced and one or more repair symbols are placed as a group into a single data packet. Each repair symbol group is associated with an Encoding Symbol ID (ESI) and a number, G, of repair symbols. The ESI is used to generate a triple of three integers, (d, a, b) for each repair symbol, again using the Trip[] generator as described in Section 5.4.4.4. Then, each (d,a,b)-triple is used to generate the

一旦生成了中间符号，就生成修复符号，并且将一个或多个修复符号作为一个组放入单个数据分组中。每个维修符号组与编码符号ID（ESI）和维修符号的数量G相关联。ESI用于为每个维修符号生成三个整数（d、a、b）的三元组，再次使用第5.4.4.4节所述的跳闸[]发生器。然后，每个（d，a，b）-三元组用于生成

corresponding repair symbol from the intermediate symbols using the LTEnc[K, C[0],..., C[L-1], (d,a,b)] generator described in Section 5.4.4.3.

使用第5.4.4.3节中所述的LTEnc[K，C[0]，…，C[L-1]，（d，a，b）]发生器的中间符号对应的维修符号。

5.4.2. First Encoding Step: Intermediate Symbol Generation

5.4.2. 第一编码步骤：中间符号生成

5.4.2.1. General

5.4.2.1. 全体的

The first encoding step is a pre-coding step to generate the L intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], ..., C'[K-1]. The intermediate symbols are uniquely defined by two sets of constraints:

第一编码步骤是从源符号C'[0]、…、C'[K-1]生成L个中间符号C[0]、…、C[L-1]的预编码步骤。中间符号由两组约束唯一定义：

1. The intermediate symbols are related to the source symbols by a set of source symbol triples. The generation of the source symbol triples is defined in Section 5.4.2.2 using the Trip[] generator described in Section 5.4.4.4.

1. 中间符号通过一组源符号三元组与源符号相关。第5.4.2.2节使用第5.4.4.4节所述的跳闸[]发生器定义了源符号三元组的生成。

2. A set of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section 5.4.2.3.

2. 一组预编码关系保存在中间符号本身中。这些在第5.4.2.3节中定义。

The generation of the L intermediate symbols is then defined in Section 5.4.2.4

然后在第5.4.2.4节中定义L中间符号的生成

5.4.2.2. Source Symbol Triples

5.4.2.2. 源符号三元组

Each of the K source symbols is associated with a triple (d[i], a[i], b[i]) for 0 <= i < K. The source symbol triples are determined using the Triple generator defined in Section 5.4.4.4 as:

K个源符号中的每一个都与0<=i<K的三元组（d[i]、a[i]、b[i]）相关联。使用第5.4.4节中定义的三元组生成器确定源符号三元组，如下所示：

      For each i, 0 <= i < K

      For each i, 0 <= i < K

(d[i], a[i], b[i]) = Trip[K, i]

（d[i]，a[i]，b[i]）=行程[K，i]

5.4.2.3. Pre-Coding Relationships

5.4.2.3. 预编码关系

The pre-coding relationships amongst the L intermediate symbols are defined by expressing the last L-K intermediate symbols in terms of the first K intermediate symbols.

通过用前K个中间符号表示最后L-K个中间符号来定义L个中间符号之间的预编码关系。

The last L-K intermediate symbols C[K],...,C[L-1] consist of S LDPC symbols and H Half symbols The values of S and H are determined from K as described below. Then L = K+S+H.

最后的L-K中间符号C[K]、…、C[L-1]由S LDPC符号和H半符号组成。S和H的值根据K确定，如下所述。然后L=K+S+H。

Let

允许

X be the smallest positive integer such that X*(X-1) >= 2*K.

X是最小的正整数，使得X*（X-1）>=2*K。

      S be the smallest prime integer such that S >= ceil(0.01*K) + X

      S be the smallest prime integer such that S >= ceil(0.01*K) + X

      H be the smallest integer such that choose(H,ceil(H/2)) >= K + S

      H be the smallest integer such that choose(H,ceil(H/2)) >= K + S

      H' = ceil(H/2)

      H' = ceil(H/2)

      L = K+S+H

      L = K+S+H

C[0],...,C[K-1] denote the first K intermediate symbols

C[0]，…，C[K-1]表示前K个中间符号

C[K],...,C[K+S-1] denote the S LDPC symbols, initialised to zero

C[K]，…，C[K+S-1]表示初始化为零的S LDPC符号

C[K+S],...,C[L-1] denote the H Half symbols, initialised to zero

C[K+S]，…，C[L-1]表示H半符号，初始化为零

The S LDPC symbols are defined to be the values of C[K],...,C[K+S-1] at the end of the following process:

在以下过程结束时，S LDPC符号被定义为C[K]、…、C[K+S-1]的值：

For i = 0,...,K-1 do

对于i=0，…，K-1 do

         a = 1 + (floor(i/S) % (S-1))

         a = 1 + (floor(i/S) % (S-1))

b = i % S

b=i%S

         C[K + b] = C[K + b] ^ C[i]

         C[K + b] = C[K + b] ^ C[i]

         b = (b + a) % S

         b = (b + a) % S

         C[K + b] = C[K + b] ^ C[i]

         C[K + b] = C[K + b] ^ C[i]

         b = (b + a) % S

         b = (b + a) % S

         C[K + b] = C[K + b] ^ C[i]

         C[K + b] = C[K + b] ^ C[i]

The H Half symbols are defined as follows:

H半符号定义如下：

Let

允许

      g[i] = i ^ (floor(i/2)) for all positive integers i

      g[i] = i ^ (floor(i/2)) for all positive integers i

Note: g[i] is the Gray sequence, in which each element differs from the previous one in a single bit position

注：g[i]是灰色序列，其中每个元素在单个位位置上不同于前一个元素

m[k] denote the subsequence of g[.] whose elements have exactly k non-zero bits in their binary representation.

m[k]表示g[.]的子序列，其元素在二进制表示中正好有k个非零位。

m[j,k] denote the jth element of the sequence m[k], where j=0, 1, 2, ...

m[j，k]表示序列m[k]的第j个元素，其中j=0，1，2。。。

Then, the Half symbols are defined as the values of C[K+S],...,C[L-1] after the following process:

然后，经过以下过程后，将半符号定义为C[K+S]、…、C[L-1]的值：

For h = 0,...,H-1 do

对于h=0，…，h-1 do

For j = 0,...,K+S-1 do

对于j=0，…，K+S-1 do

If bit h of m[j,H'] is equal to 1 then C[h+K+S] = C[h+K+S] ^ C[j].

如果m[j，h']的位h等于1，则C[h+K+S]=C[h+K+S]^C[j]。

5.4.2.4. Intermediate Symbols

5.4.2.4. 中间符号

5.4.2.4.1. Definition

5.4.2.4.1. 释义

Given the K source symbols C'[0], C'[1],..., C'[K-1] the L intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined symbol values that satisfy the following conditions:

给定K个源符号C'[0]、C'[1]、…、C'[K-1]，L个中间符号C[0]、C[1]、…、C[L-1]是满足以下条件的唯一定义的符号值：

1. The K source symbols C'[0], C'[1],..., C'[K-1] satisfy the K constraints

1. K个源符号C'[0]，C'[1]，…，C'[K-1]满足K个约束

C'[i] = LTEnc[K, (C[0],..., C[L-1]), (d[i], a[i], b[i])], for all i, 0 <= i < K.

C'[i]=LTEnc[K，（C[0]，…，C[L-1]），（d[i]，a[i]，b[i]），对于所有i，0<=i<K。

2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the pre-coding relationships defined in Section 5.4.2.3.

2. L中间符号C[0]、C[1]、…、C[L-1]满足第5.4.2.3节中定义的预编码关系。

5.4.2.4.2. Example Method for Calculation of Intermediate Symbols

5.4.2.4.2. 计算中间符号的示例方法

This subsection describes a possible method for calculation of the L intermediate symbols C[0], C[1],..., C[L-1] satisfying the constraints in Section 5.4.2.4.1.

本小节描述了计算满足第5.4.2.4.1节约束条件的L个中间符号C[0]、C[1]、…、C[L-1]的可能方法。

The 'generator matrix' for a code that generates N output symbols from K input symbols is an NxK matrix over GF(2), where each row corresponds to one of the output symbols and each column to one of the input symbols and where the ith output symbol is equal to the sum of those input symbols whose column contains a non-zero entry in row i.

从K个输入符号生成N个输出符号的代码的“生成器矩阵”是GF（2）上的NxK矩阵，其中每行对应一个输出符号，每列对应一个输入符号，其中第i个输出符号等于其列包含第i行中非零项的输入符号之和。

Then, the L intermediate symbols can be calculated as follows:

然后，可以如下计算L个中间符号：

Let

允许

C denote the column vector of the L intermediate symbols, C[0], C[1],..., C[L-1].

C表示L个中间符号的列向量，C[0]，C[1]，…，C[L-1]。

D denote the column vector consisting of S+H zero symbols followed by the K source symbols C'[0], C'[1], ..., C'[K-1]

D表示由S+H零符号后跟K个源符号C'[0]，C'[1]，…，C'[K-1]组成的列向量

Then the above constraints define an LxL matrix over GF(2), A, such that:

然后，上述约束定义了GF（2），A上的LxL矩阵，从而：

A*C = D

A*C=D

The matrix A can be constructed as follows:

矩阵A可以如下构造：

Let:

让我们：

G_LDPC be the S x K generator matrix of the LDPC symbols. So,

G_LDPC是LDPC符号的sxk生成器矩阵。所以

         G_LDPC * Transpose[(C[0],...., C[K-1])] = Transpose[(C[K], ...,
         C[K+S-1])]

         G_LDPC * Transpose[(C[0],...., C[K-1])] = Transpose[(C[K], ...,
         C[K+S-1])]

G_Half be the H x (K+S) generator matrix of the Half symbols, So,

G_Half是半个符号的hx（K+S）生成矩阵，因此，

         G_Half * Transpose[(C[0], ..., C[S+K-1])] = Transpose[(C[K+S],
         ..., C[K+S+H-1])]

         G_Half * Transpose[(C[0], ..., C[S+K-1])] = Transpose[(C[K+S],
         ..., C[K+S+H-1])]

I_S be the S x S identity matrix

I_S是S x S单位矩阵

I_H be the H x H identity matrix

I_H是H×H单位矩阵

0_SxH be the S x H zero matrix

0_SxH是SxH零矩阵

G_LT be the KxL generator matrix of the encoding symbols generated by the LT Encoder. So,

G_LT是LT编码器生成的编码符号的KxL生成器矩阵。所以

         G_LT * Transpose[(C[0], ..., C[L-1])] =
         Transpose[(C'[0],C'[1],...,C'[K-1])]

         G_LT * Transpose[(C[0], ..., C[L-1])] =
         Transpose[(C'[0],C'[1],...,C'[K-1])]

i.e., G_LT(i,j) = 1 if and only if C[j] is included in the symbols that are XORed to produce LTEnc[K, (C[0], ..., C[L-1]), (d[i], a[i], b[i])].

i、例如，G_LT（i，j）=1当且仅当C[j]包括在异或产生LTEnc[K，（C[0]，…，C[L-1]），（d[i]，a[i]，b[i]）的符号中。

Then:

然后：

The first S rows of A are equal to G_LDPC | I_S | 0_SxH.

A的前S行等于G|u LDPC | I|u S | 0|u SxH。

The next H rows of A are equal to G_Half | I_H.

A的下H行等于G|u Half | I|H。

The remaining K rows of A are equal to G_LT.

A的其余K行等于G_LT。

The matrix A is depicted in Figure 4 below:

矩阵A如下图4所示：

                 K               S       H
     +-----------------------+-------+-------+
     |                       |       |       |
   S |        G_LDPC         |  I_S  | 0_SxH |
     |                       |       |       |
     +-----------------------+-------+-------+
     |                               |       |
   H |        G_Half                 |  I_H  |
     |                               |       |
     +-------------------------------+-------+
     |                                       |
     |                                       |
   K |                 G_LT                  |
     |                                       |
     |                                       |
     +---------------------------------------+

                 K               S       H
     +-----------------------+-------+-------+
     |                       |       |       |
   S |        G_LDPC         |  I_S  | 0_SxH |
     |                       |       |       |
     +-----------------------+-------+-------+
     |                               |       |
   H |        G_Half                 |  I_H  |
     |                               |       |
     +-------------------------------+-------+
     |                                       |
     |                                       |
   K |                 G_LT                  |
     |                                       |
     |                                       |
     +---------------------------------------+

Figure 4: The matrix A

图4：矩阵A

The intermediate symbols can then be calculated as:

然后，可以将中间符号计算为：

      C = (A^^-1)*D

      C = (A^^-1)*D

The source symbol triples are generated such that for any K matrix, A has full rank and is therefore invertible. This calculation can be realized by applying a Raptor decoding process to the K source symbols C'[0], C'[1],..., C'[K-1] to produce the L intermediate symbols C[0], C[1],..., C[L-1].

生成源符号三元组，使得对于任何K矩阵，A具有满秩，因此是可逆的。该计算可以通过对K个源符号C'[0]，C'[1]，…，C'[K-1]应用Raptor解码过程来实现，以产生L个中间符号C[0]，C[1]，…，C[L-1]。

To efficiently generate the intermediate symbols from the source symbols, it is recommended that an efficient decoder implementation such as that described in Section 5.5 be used. The source symbol triples are designed to facilitate efficient decoding of the source symbols using that algorithm.

为了从源符号有效地生成中间符号，建议使用第5.5节中描述的高效解码器实现。源符号三元组的设计有助于使用该算法对源符号进行有效解码。

5.4.3. Second Encoding Step: LT Encoding

5.4.3. 第二编码步骤：LT编码

In the second encoding step, the repair symbol with ESI X is generated by applying the generator LTEnc[K, (C[0], C[1],..., C[L-1]), (d, a, b)] defined in Section 5.4.4.3 to the L intermediate symbols C[0], C[1],..., C[L-1] using the triple (d, a, b)=Trip[K,X] generated according to Section 5.3.2

在第二编码步骤中，通过将第5.4.4.3节中定义的发生器LTEnc[K，（C[0]，C[1]，…，C[L-1]），（d，a，b）]应用于根据第5.3.2节生成的三元组（d，a，b）=跳闸[K，X]，生成具有ESI X的修复符号

5.4.4. Generators

5.4.4. 发电机

5.4.4.1. Random Generator

5.4.4.1. 随机发生器

The random number generator Rand[X, i, m] is defined as follows, where X is a non-negative integer, i is a non-negative integer, and m is a positive integer and the value produced is an integer between 0 and m-1. Let V0 and V1 be arrays of 256 entries each, where each entry is a 4-byte unsigned integer. These arrays are provided in Section 5.6.

随机数生成器Rand[X，i，m]定义如下，其中X是非负整数，i是非负整数，m是正整数，生成的值是0到m-1之间的整数。设V0和V1为256个条目的数组，其中每个条目为4字节无符号整数。第5.6节提供了这些阵列。

Then,

然后

      Rand[X, i, m] = (V0[(X + i) % 256] ^ V1[(floor(X/256)+ i) % 256])
      % m

      Rand[X, i, m] = (V0[(X + i) % 256] ^ V1[(floor(X/256)+ i) % 256])
      % m

5.4.4.2. Degree Generator

5.4.4.2. 度发生器

The degree generator Deg[v] is defined as follows, where v is an integer that is at least 0 and less than 2^^20 = 1048576.

度生成器Deg[v]定义如下，其中v是至少为0且小于2^^20＝1048576的整数。

      In Table 1, find the index j such that f[j-1] <= v < f[j]

      In Table 1, find the index j such that f[j-1] <= v < f[j]

Then, Deg[v] = d[j]

然后，Deg[v]=d[j]

                       +---------+---------+------+
                       | Index j | f[j]    | d[j] |
                       +---------+---------+------+
                       | 0       | 0       | --   |
                       | 1       | 10241   | 1    |
                       | 2       | 491582  | 2    |
                       | 3       | 712794  | 3    |
                       | 4       | 831695  | 4    |
                       | 5       | 948446  | 10   |
                       | 6       | 1032189 | 11   |
                       | 7       | 1048576 | 40   |
                       +---------+---------+------+

                       +---------+---------+------+
                       | Index j | f[j]    | d[j] |
                       +---------+---------+------+
                       | 0       | 0       | --   |
                       | 1       | 10241   | 1    |
                       | 2       | 491582  | 2    |
                       | 3       | 712794  | 3    |
                       | 4       | 831695  | 4    |
                       | 5       | 948446  | 10   |
                       | 6       | 1032189 | 11   |
                       | 7       | 1048576 | 40   |
                       +---------+---------+------+

Table 1: Defines the degree distribution for encoding symbols

表1：定义编码符号的度分布

5.4.4.3. LT Encoding Symbol Generator

5.4.4.3. LT编码符号发生器

The encoding symbol generator LTEnc[K, (C[0], C[1],..., C[L-1]), (d, a, b)] takes the following inputs:

编码符号生成器LTEnc[K，（C[0]，C[1]，…，C[L-1]），（d，a，b）]采用以下输入：

K is the number of source symbols (or sub-symbols) for the source block (sub-block). Let L be derived from K as described in Section 5.4.2.3, and let L' be the smallest prime integer greater than or equal to L.

K是源块（子块）的源符号（或子符号）数。如第5.4.2.3节所述，L由K导出，L'是大于或等于L的最小素整数。

(C[0], C[1],..., C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section 5.4.2.4.

（C[0]，C[1]，…，C[L-1]）是按照第5.4.2.4节所述生成的L个中间符号（子符号）的数组。

(d, a, b) is a source triple determined using the Triple generator defined in Section 5.4.4.4, whereby

（d，a，b）是使用第5.4.4.4节中定义的三元组生成器确定的源三元组，其中

d is an integer denoting an encoding symbol degree

d是表示编码符号度数的整数

a is an integer between 1 and L'-1 inclusive

a是介于1和L'-1之间的整数（包括1和L'-1）

b is an integer between 0 and L'-1 inclusive

b是介于0和L'-1之间的整数，包括0和L'-1

The encoding symbol generator produces a single encoding symbol as output, according to the following algorithm:

编码符号生成器根据以下算法生成单个编码符号作为输出：

      While (b >= L) do b = (b + a) % L'

      While (b >= L) do b = (b + a) % L'

Let result = C[b].

设结果=C[b]。

For j = 1,...,min(d-1,L-1) do

对于j=1，…，最小（d-1，L-1）do

         b = (b + a) % L'

         b = (b + a) % L'

         While (b >= L) do b = (b + a) % L'

         While (b >= L) do b = (b + a) % L'

result = result ^ C[b]

结果=结果^C[b]

Return result

返回结果

5.4.4.4. Triple Generator

5.4.4.4. 三重发电机

The triple generator Trip[K,X] takes the following inputs:

三重发电机跳闸[K，X]采用以下输入：

K - The number of source symbols

K-源符号的数量

X - An encoding symbol ID

X-编码符号ID

Let

允许

L be determined from K as described in Section 5.4.2.3

L应根据第5.4.2.3节中所述的K确定

L' be the smallest prime that is greater than or equal to L

L'是大于或等于L的最小素数

Q = 65521, the largest prime smaller than 2^^16.

Q=65521，小于2^^16的最大素数。

J(K) be the systematic index associated with K, as defined in Section 5.7.

J（K）是与K相关的系统指数，如第5.7节所定义。

The output of the triple generator is a triple, (d, a, b) determined as follows:

三重发电机的输出为三重（d、a、b），确定如下：

      A = (53591 + J(K)*997) % Q

      A = (53591 + J(K)*997) % Q

      B = 10267*(J(K)+1) % Q

      B = 10267*(J(K)+1) % Q

      Y = (B + X*A) % Q

      Y = (B + X*A) % Q

      v = Rand[Y, 0, 2^^20]

      v = Rand[Y, 0, 2^^20]

d = Deg[v]

d=度[v]

a = 1 + Rand[Y, 1, L'-1]

a=1+Rand[Y，1，L'-1]

b = Rand[Y, 2, L']

b=兰特[Y，2，L']

5.5. Example FEC Decoder

5.5. 示例FEC解码器

5.5.1. General

5.5.1. 全体的

This section describes an efficient decoding algorithm for the Raptor codes described in this specification. Note that each received encoding symbol can be considered as the value of an equation amongst the intermediate symbols. From these simultaneous equations, and the known pre-coding relationships amongst the intermediate symbols, any algorithm for solving simultaneous equations can successfully decode the intermediate symbols and hence the source symbols. However, the algorithm chosen has a major effect on the computational efficiency of the decoding.

本节描述本规范中描述的Raptor码的有效解码算法。注意，每个接收到的编码符号可被视为中间符号之间的等式的值。根据这些联立方程以及中间符号之间的已知预编码关系，任何求解联立方程的算法都可以成功地解码中间符号，从而解码源符号。然而，所选择的算法对解码的计算效率有重大影响。

5.5.2. Decoding a Source Block

5.5.2. 解码源块

5.5.2.1. General

5.5.2.1. 全体的

It is assumed that the decoder knows the structure of the source block it is to decode, including the symbol size, T, and the number K of symbols in the source block.

假设解码器知道要解码的源块的结构，包括符号大小T和源块中的符号数K。

From the algorithms described in Section 5.4, the Raptor decoder can calculate the total number L = K+S+H of pre-coding symbols and determine how they were generated from the source block to be decoded. In this description, it is assumed that the received

根据第5.4节中描述的算法，Raptor解码器可以计算预编码符号的总数L=K+S+H，并确定如何从要解码的源块生成预编码符号。在该描述中，假设接收到

encoding symbols for the source block to be decoded are passed to the decoder. Note that, as described in Section 5.3.2, the last source symbol of a source packet may have included padding bytes added for FEC encoding purposes. These padding bytes may not be actually included in the packet sent and so must be reinserted at the received before passing the symbol to the decoder.

将要解码的源块的编码符号传递给解码器。注意，如第5.3.2节所述，源数据包的最后一个源符号可能包括为FEC编码目的添加的填充字节。这些填充字节实际上可能不包括在发送的数据包中，因此在将符号传递给解码器之前，必须在接收端重新插入。

For each such encoding symbol, it is assumed that the number and set of intermediate symbols whose exclusive-or is equal to the encoding symbol is also passed to the decoder. In the case of source symbols, the source symbol triples described in Section 5.4.2.2 indicate the number and set of intermediate symbols that sum to give each source symbol.

对于每个这样的编码符号，假定其异或等于编码符号的中间符号的数目和集合也被传递给解码器。在源符号的情况下，第5.4.2.2节中描述的源符号三元组表示中间符号的数量和集合，这些中间符号的总和表示每个源符号。

Let N >= K be the number of received encoding symbols for a source block and let M = S+H+N. The following M by L bit matrix A can be derived from the information passed to the decoder for the source block to be decoded. Let C be the column vector of the L intermediate symbols, and let D be the column vector of M symbols with values known to the receiver, where the first S+H of the M symbols are zero-valued symbols that correspond to LDPC and Half symbols (these are check symbols for the LDPC and Half symbols, and not the LDPC and Half symbols themselves), and the remaining N of the M symbols are the received encoding symbols for the source block. Then, A is the bit matrix that satisfies A*C = D, where here * denotes matrix multiplication over GF[2]. In particular, A[i,j] = 1 if the intermediate symbol corresponding to index j is exclusive-ORed into the LDPC, Half, or encoding symbol corresponding to index i in the encoding, or if index i corresponds to a LDPC or Half symbol and index j corresponds to the same LDPC or Half symbol. For all other i and j, A[i,j] = 0.

设N>=K为一个源块接收到的编码符号数，设M=S+H+N。以下M×L比特矩阵a可从传递给待解码源块解码器的信息中导出。设C为L个中间符号的列向量，设D为具有接收器已知值的M个符号的列向量，其中M个符号的第一个S+H是对应于LDPC和半个符号的零值符号（这些是LDPC和半个符号的检查符号，而不是LDPC和半个符号本身），M个符号中的剩余N个是源块的接收编码符号。然后，A是满足A*C=D的位矩阵，其中*表示GF[2]上的矩阵乘法。特别地，如果与索引j相对应的中间符号在编码中被异或到与索引i相对应的LDPC、半或编码符号中，或者如果索引i对应于LDPC或半符号且索引j对应于相同的LDPC或半符号，则A[i，j]=1。对于所有其他i和j，A[i，j]=0。

Decoding a source block is equivalent to decoding C from known A and D. It is clear that C can be decoded if and only if the rank of A over GF[2] is L. Once C has been decoded, missing source symbols can be obtained by using the source symbol triples to determine the number and set of intermediate symbols that MUST be exclusive-ORed to obtain each missing source symbol.

解码源块相当于从已知的a和D解码C。很明显，当且仅当a在GF[2]上的秩为L时，C才能被解码。一旦C被解码，通过使用源符号三元组来确定中间符号的数量和集合，可以获得缺失的源符号，中间符号的数量和集合必须为异或，才能获得每个缺失的源符号。

The first step in decoding C is to form a decoding schedule. In this step A is converted, using Gaussian elimination (using row operations and row and column reorderings) and after discarding M - L rows, into the L by L identity matrix. The decoding schedule consists of the sequence of row operations and row and column reorderings during the Gaussian elimination process, and only depends on A and not on D. The decoding of C from D can take place concurrently with the forming of the decoding schedule, or the decoding can take place afterwards based on the decoding schedule.

解码C的第一步是形成解码时间表。在这一步中，使用高斯消去法（使用行操作以及行和列重新排序）并在丢弃M-L行之后，将A转换为L-by-L单位矩阵。解码调度由高斯消去过程中的行操作序列和行和列重新排序组成，并且仅依赖于A而不依赖于D。从D对C的解码可以与解码调度的形成同时进行，或者可以基于解码调度随后进行解码。

The correspondence between the decoding schedule and the decoding of C is as follows. Let c[0] = 0, c[1] = 1,...,c[L-1] = L-1 and d[0] = 0, d[1] = 1,...,d[M-1] = M-1 initially.

解码时间表和C的解码之间的对应关系如下。首先设c[0]=0，c[1]=1，…，c[L-1]=L-1和d[0]=0，d[1]=1，…，d[M-1]=M-1。

- Each time row i of A is exclusive-ORed into row i' in the decoding schedule, then in the decoding process, symbol D[d[i]] is exclusive-ORed into symbol D[d[i']].

- 每次A的行i在解码调度中被排他或与行i'异或时，然后在解码过程中，符号D[D[i]]被排他或与符号D[D[i']异或。

- Each time row i is exchanged with row i' in the decoding schedule, then in the decoding process, the value of d[i] is exchanged with the value of d[i'].

- 每次在解码调度中将行i与行i′交换时，然后在解码过程中，将d[i]的值与d[i']的值交换。

- Each time column j is exchanged with column j' in the decoding schedule, then in the decoding process, the value of c[j] is exchanged with the value of c[j'].

- 每次在解码调度中j列与j'列交换时，然后在解码过程中，c[j]的值与c[j']的值交换。

From this correspondence, it is clear that the total number of exclusive-ORs of symbols in the decoding of the source block is the number of row operations (not exchanges) in the Gaussian elimination. Since A is the L by L identity matrix after the Gaussian elimination and after discarding the last M - L rows, it is clear at the end of successful decoding that the L symbols D[d[0]], D[d[1]],..., D[d[L-1]] are the values of the L symbols C[c[0]], C[c[1]],..., C[c[L-1]].

从该对应关系可以清楚地看出，在源块的解码中，符号的异或的总数是高斯消去中的行操作（而不是交换）的数目。由于A是在高斯消去之后并且在丢弃最后M-L行之后的逐L单位矩阵，因此在成功解码结束时，很明显，L符号D[D[0]]、D[D[1]]、…、D[D[L-1]]是L符号C[C[0]]、C[C[1]、…、C[C[L-1]]的值。

The order in which Gaussian elimination is performed to form the decoding schedule has no bearing on whether or not the decoding is successful. However, the speed of the decoding depends heavily on the order in which Gaussian elimination is performed. (Furthermore, maintaining a sparse representation of A is crucial, although this is not described here). The remainder of this section describes an order in which Gaussian elimination could be performed that is relatively efficient.

执行高斯消去以形成解码调度的顺序与解码是否成功无关。然而，解码的速度在很大程度上取决于高斯消去的执行顺序。（此外，保持a的稀疏表示是至关重要的，尽管这里没有描述）。本节的其余部分描述了可以执行相对有效的高斯消去的顺序。

5.5.2.2. First Phase

5.5.2.2. 第一阶段

The first phase of the Gaussian elimination, the matrix A, is conceptually partitioned into submatrices. The submatrix sizes are parameterized by non-negative integers i and u, which are initialized to 0. The submatrices of A are:

高斯消去法的第一阶段，矩阵A，在概念上被划分为子矩阵。子矩阵大小由初始化为0的非负整数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列的交点定义的子矩阵I。这是阶段中每个步骤结束时的单位矩阵。

(2) The submatrix defined by the intersection of the first i rows and all but the first i columns and last u columns. All entries of this submatrix are zero.

(2) 由第一个i行与除第一个i列和最后一个u列以外的所有列的交点定义的子矩阵。此子矩阵的所有条目均为零。

(3) The submatrix defined by the intersection of the first i columns and all but the first i rows. All entries of this submatrix are zero.

(3) 由前i列和除前i行以外的所有行的交点定义的子矩阵。此子矩阵的所有条目均为零。

(4) The submatrix U defined by the intersection of all the rows and the last u columns.

(4) 由所有行和最后U列的交点定义的子矩阵U。

(5) The submatrix V formed by the intersection of all but the first i columns and the last u columns and all but the first i rows.

(5) 子矩阵V由除第一个i列和最后一个u列以外的所有列与除第一个i行以外的所有行的交点构成。

Figure 5 illustrates the submatrices of A. At the beginning of the first phase, V = A. In each step, a row of A is chosen.

图5显示了A的子矩阵。在第一阶段开始时，V=A。在每个步骤中，选择A的一行。

   +-----------+-----------------+---------+
   |           |                 |         |
   |     I     |    All Zeros    |         |
   |           |                 |         |
   +-----------+-----------------+    U    |
   |           |                 |         |
   |           |                 |         |
   | All Zeros |       V         |         |
   |           |                 |         |
   |           |                 |         |
   +-----------+-----------------+---------+

   +-----------+-----------------+---------+
   |           |                 |         |
   |     I     |    All Zeros    |         |
   |           |                 |         |
   +-----------+-----------------+    U    |
   |           |                 |         |
   |           |                 |         |
   | All Zeros |       V         |         |
   |           |                 |         |
   |           |                 |         |
   +-----------+-----------------+---------+

Figure 5: Submatrices of A in the first phase

图5：第一阶段A的子矩阵

The following graph defined by the structure of V is used in determining which row of A is chosen. The columns that intersect V are the nodes in the graph, and the rows that have exactly 2 ones in V are the edges of the graph that connect the two columns (nodes) in the positions of the two ones. A component in this graph is a maximal set of nodes (columns) and edges (rows) such that there is a path between each pair of nodes/edges in the graph. The size of a component is the number of nodes (columns) in the component.

由V结构定义的下图用于确定选择A的哪一行。与V相交的列是图形中的节点，在V中正好有两个列的行是图形的边，它们将两个列（节点）连接在两个列的位置上。此图中的组件是一组最大的节点（列）和边（行），这样图中的每对节点/边之间都有一条路径。组件的大小是组件中节点（列）的数量。

There are at most L steps in the first phase. The phase ends successfully when i + u = L, i.e., when V and the all-zeroes submatrix above V have disappeared and A consists of I, the all zeroes submatrix below I, and U. The phase ends unsuccessfully in decoding failure if, at some step before V disappears, there is no non-zero row in V to choose in that step. Whenever there are non-zero rows in V, then the next step starts by choosing a row of A as follows:

第一阶段最多有L个步骤。当i+u=L时，即当V和V上的全零子矩阵消失，且A由i、i下的全零子矩阵和u组成时，相位成功结束。如果在V消失之前的某个步骤中，V中没有可选择的非零行，则相位在解码失败时失败结束。每当V中有非零行时，下一步开始选择a行，如下所示：

o Let r be the minimum integer such that at least one row of A has exactly r ones in V.

o 设r为最小整数，使得A的至少一行在V中正好有r个。

* If r != 2, then choose a row with exactly r ones in V with minimum original degree among all such rows.

* 如果r！=2，然后从所有这些行中选择一行，该行在V中正好有r个，且原始度最小。

* If r = 2, then choose any row with exactly 2 ones in V that is part of a maximum size component in the graph defined by V.

* 如果r=2，则选择V中正好有2行的任意行，该行是由V定义的图形中最大大小组件的一部分。

After the row is chosen in this step the first row of A that intersects V is exchanged with the chosen row so that the chosen row is the first row that intersects V. The columns of A among those that intersect V are reordered so that one of the r ones in the chosen row appears in the first column of V and so that the remaining r-1 ones appear in the last columns of V. Then, the chosen row is exclusive-ORed into all the other rows of A below the chosen row that have a one in the first column of V. Finally, i is incremented by 1 and u is incremented by r-1, which completes the step.

在此步骤中选择行后，与V相交的A的第一行将与所选行交换，以便所选行是与V相交的第一行。与V相交的A列中的A列将重新排序，以便所选行中的r列之一显示在V的第一列中，而其余的r-1列将显示在V的第一列中V的最后一列。然后，所选行与所选行下面A的所有其他行进行异或运算，这些行在V的第一列中有一个。最后，i递增1，u递增r-1，这完成了该步骤。

5.5.2.3. Second Phase

5.5.2.3. 第二阶段

The submatrix U is further partitioned into the first i rows, U_upper, and the remaining M - i rows, U_lower. Gaussian elimination is performed in the second phase on U_lower to either determine that its rank is less than u (decoding failure) or to convert it into a matrix where the first u rows is the identity matrix (success of the second phase). Call this u by u identity matrix I_u. The M - L rows of A that intersect U_lower - I_u are discarded. After this phase, A has L rows and L columns.

子矩阵U被进一步划分为第一个i行（U_上部）和剩余的M-i行（U_下部）。在第二阶段对U_lower执行高斯消去，以确定其秩小于U（解码失败），或将其转换为矩阵，其中第一U行为单位矩阵（第二阶段成功）。称之为单位矩阵。与U_lower-I_相交的A的M-L行将被丢弃。在此阶段之后，A有L行和L列。

5.5.2.4. Third Phase

5.5.2.4. 第三阶段

After the second phase, the only portion of A that needs to be zeroed out to finish converting A into the L by L identity matrix is U_upper. The number of rows i of the submatrix U_upper is generally much larger than the number of columns u of U_upper. To zero out U_upper efficiently, the following precomputation matrix U' is computed based on I_u in the third phase and then U' is used in the fourth phase to zero out U_upper. The u rows of Iu are partitioned into ceil(u/8) groups of 8 rows each. Then, for each group of 8 rows, all non-zero combinations of the 8 rows are computed, resulting in 2^^8 - 1 = 255 rows (this can be done with 2^^8-8-1 = 247 exclusive-ors of rows per group, since the combinations of Hamming weight one that appear in I_u do not need to be recomputed). Thus, the resulting precomputation matrix U' has ceil(u/8)*255 rows and u columns. Note that U' is not formally a part of matrix A, but will be used in the fourth phase to zero out U_upper.

在第二阶段之后，A的唯一需要调零的部分是U_upper，以完成A到逐L单位矩阵的转换。子矩阵U_upper的行i的数量通常比U_upper的列U的数量大得多。为了有效地将U_上限归零，在第三阶段基于I_计算以下预计算矩阵U′，然后在第四阶段使用U′将U_上限归零。Iu的u行被划分为ceil（u/8）组，每组8行。然后，对于每组8行，计算8行的所有非零组合，得到2^^8-1=255行（这可以通过每组2^^8-8-1=247行的异或来完成，因为不需要重新计算I_中出现的汉明权重1的组合）。因此，得到的预计算矩阵U’具有ceil（U/8）*255行和U列。请注意，U'不是矩阵a的正式组成部分，但将在第四阶段中用于将U_上部归零。

5.5.2.5. Fourth Phase

5.5.2.5. 第四阶段

For each of the first i rows of A, for each group of 8 columns in the U_upper submatrix of this row, if the set of 8 column entries in U_upper are not all zero, then the row of the precomputation matrix U' that matches the pattern in the 8 columns is exclusive-ORed into the row, thus zeroing out those 8 columns in the row at the cost of exclusive-ORing one row of U' into the row.

对于A的前i行中的每一行，对于该行的U_upper子矩阵中的每一组8列，如果U_upper中的8列项集合不全部为零，则与8列中的模式匹配的预计算矩阵U'的行被排他或入该行，因此，将该行中的这8列归零，代价是将一行U'排他ORing到该行中。

After this phase, A is the L by L identity matrix and a complete decoding schedule has been successfully formed. Then, as explained in Section 5.5.2.1, the corresponding decoding consisting of exclusive-ORing known encoding symbols can be executed to recover the intermediate symbols based on the decoding schedule. The triples associated with all source symbols are computed according to Section 5.4.2.2. The triples for received source symbols are used in the decoding. The triples for missing source symbols are used to determine which intermediate symbols need to be exclusive-ORed to recover the missing source symbols.

在此阶段之后，A是逐L单位矩阵，并且成功地形成了完整的解码时间表。然后，如第5.5.2.1节所述，可以执行由已知编码符号组成的相应解码，以基于解码时间表恢复中间符号。根据第5.4.2.2节计算与所有源符号相关的三元组。解码中使用接收到的源符号的三元组。丢失源符号的三元组用于确定需要对哪些中间符号进行异或运算以恢复丢失的源符号。

5.6. Random Numbers

5.6. 随机数

The two tables V0 and V1 described in Section 5.4.4.1 are given below. Each entry is a 32-bit integer in decimal representation.

下面给出了第5.4.4.1节中所述的两个表V0和V1。每个条目都是以十进制表示的32位整数。

5.6.1. The Table V0

5.6.1. 表V0

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

5.6.2. The Table V1

5.6.2. 表V1

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

5.7. Systematic Indices J(K)

5.7. 系统指数J（K）

For each value of K, the systematic index J(K) is designed to have the property that the set of source symbol triples (d[0], a[0], b[0]), ..., (d[L-1], a[L-1], b[L-1]) are such that the L intermediate symbols are uniquely defined, i.e., the matrix A in Section 5.4.2.4.2 has full rank and is therefore invertible.

对于K的每个值，系统索引J（K）被设计为具有以下特性：源符号三元组（d[0]、a[0]、b[0]、…、（d[L-1]、a[L-1]、b[L-1]）的集合使得L个中间符号被唯一定义，即，第5.4.2.4.2节中的矩阵a具有满秩，因此是可逆的。

The following is the list of the systematic indices for values of K between 4 and 8192 inclusive.

以下是K值在4和8192之间（含4和8192）的系统指数列表。

18, 14, 61, 46, 14, 22, 20, 40, 48, 1, 29, 40, 43, 46, 18, 8, 20, 2, 61, 26, 13, 29, 36, 19, 58, 5, 58, 0, 54, 56, 24, 14, 5, 67, 39, 31, 25, 29, 24, 19, 14, 56, 49, 49, 63, 30, 4, 39, 2, 1, 20, 19, 61, 4, 54, 70, 25, 52, 9, 26, 55, 69, 27, 68, 75, 19, 64, 57, 45, 3, 37, 31, 100, 41, 25, 41, 53, 23, 9, 31, 26, 30, 30, 46, 90, 50, 13, 90, 77, 61, 31, 54, 54, 3, 21, 66, 21, 11, 23, 11, 29, 21, 7, 1, 27, 4, 34, 17, 85, 69, 17, 75, 93, 57, 0, 53, 71, 88, 119, 88, 90, 22, 0, 58, 41, 22, 96, 26, 79, 118, 19, 3, 81, 72, 50, 0, 32, 79, 28, 25, 12,

25, 29, 3, 37, 30, 30, 41, 84, 32, 31, 61, 32, 61, 7, 56, 54, 39, 33, 66, 29, 3, 14, 75, 75, 78, 84, 75, 84, 25, 54, 25, 25, 107, 78, 27, 73, 0, 49, 96, 53, 50, 21, 10, 73, 58, 65, 27, 3, 27, 18, 54, 45, 69, 29, 3, 65, 31, 71, 76, 56, 54, 76, 54, 13, 5, 18, 142, 17, 3, 37, 114, 41, 25, 56, 0, 23, 3, 41, 22, 22, 31, 18, 48, 31, 58, 37, 75, 88, 3, 56, 1, 95, 19, 73, 52, 52, 4, 75, 26, 1, 25, 10, 1, 70, 31, 31, 12, 10, 54, 46, 11, 74, 84, 74, 8, 58, 23, 74, 8, 36, 11, 16, 94, 76, 14, 57, 65, 8, 22, 10, 36, 36, 96, 62, 103, 6, 75, 103, 58, 10, 15, 41, 75, 125, 58, 15, 10, 34, 29, 34, 4, 16, 29, 18, 18, 28, 71, 28, 43, 77, 18, 41, 41, 41, 62, 29, 96, 15, 106, 43, 15, 3, 43, 61, 3, 18, 103, 77, 29, 103, 19, 58, 84, 58, 1, 146, 32, 3, 70, 52, 54, 29, 70, 69, 124, 62, 1, 26, 38, 26, 3, 16, 26, 5, 51, 120, 41, 16, 1, 43, 34, 34, 29, 37, 56, 29, 96, 86, 54, 25, 84, 50, 34, 34, 93, 84, 96, 29, 29, 50, 50, 6, 1, 105, 78, 15, 37, 19, 50, 71, 36, 6, 54, 8, 28, 54, 75, 75, 16, 75, 131, 5, 25, 16, 69, 17, 69, 6, 96, 53, 96, 41, 119, 6, 6, 88, 50, 88, 52, 37, 0, 124, 73, 73, 7, 14, 36, 69, 79, 6, 114, 40, 79, 17, 77, 24, 44, 37, 69, 27, 37, 29, 33, 37, 50, 31, 69, 29, 101, 7, 61, 45, 17, 73, 37, 34, 18, 94, 22, 22, 63, 3, 25, 25, 17, 3, 90, 34, 34, 41, 34, 41, 54, 41, 54, 41, 41, 41, 163, 143, 96, 18, 32, 39, 86, 104, 11, 17, 17, 11, 86, 104, 78, 70, 52, 78, 17, 73, 91, 62, 7, 128, 50, 124, 18, 101, 46, 10, 75, 104, 73, 58, 132, 34, 13, 4, 95, 88, 33, 76, 74, 54, 62, 113, 114, 103, 32, 103, 69, 54, 53, 3, 11, 72, 31, 53, 102, 37, 53, 11, 81, 41, 10, 164, 10, 41, 31, 36, 113, 82, 3, 125, 62, 16, 4, 41, 41, 4, 128, 49, 138, 128, 74, 103, 0, 6, 101, 41, 142, 171, 39, 105, 121, 81, 62, 41, 81, 37, 3, 81, 69, 62, 3, 69, 70, 21, 29, 4, 91, 87, 37, 79, 36, 21, 71, 37, 41, 75, 128, 128, 15, 25, 3, 108, 73, 91, 62, 114, 62, 62, 36, 36, 15, 58, 114, 61, 114, 58, 105, 114, 41, 61, 176, 145, 46, 37, 30, 220, 77, 138, 15, 1, 128, 53, 50, 50, 58, 8, 91, 114, 105, 63, 91, 37, 37, 13, 169, 51, 102, 6, 102, 23, 105, 23, 58, 6, 29, 29, 19, 82, 29, 13, 36, 27, 29, 61, 12, 18, 127, 127, 12, 44, 102, 18, 4, 15, 206, 53, 127, 53, 17, 69, 69, 69, 29, 29, 109, 25, 102, 25, 53, 62, 99, 62, 62, 29, 62, 62, 45, 91, 125, 29, 29, 29, 4, 117, 72, 4, 30, 71, 71, 95, 79, 179, 71, 30, 53, 32, 32, 49, 25, 91, 25, 26, 26, 103, 123, 26, 41, 162, 78, 52, 103, 25, 6, 142, 94, 45, 45, 94, 127, 94, 94, 94, 47, 209, 138, 39, 39, 19, 154, 73, 67, 91, 27, 91, 84, 4, 84, 91, 12, 14, 165, 142, 54, 69, 192, 157, 185, 8, 95, 25, 62, 103, 103, 95, 71, 97, 62, 128, 0, 29, 51, 16, 94, 16, 16, 51, 0, 29, 85, 10, 105, 16, 29, 29, 13, 29, 4, 4, 132, 23, 95, 25, 54, 41, 29, 50, 70, 58, 142, 72, 70, 15, 72, 54, 29, 22, 145, 29, 127, 29, 85, 58, 101, 34, 165, 91, 46, 46, 25, 185, 25, 77, 128, 46, 128, 46, 188, 114, 46, 25, 45, 45, 114, 145, 114, 15, 102, 142, 8, 73, 31, 139, 157, 13, 79, 13, 114, 150, 8, 90, 91, 123, 69, 82, 132, 8, 18, 10, 102, 103, 114, 103, 8, 103, 13, 115, 55, 62, 3, 8, 154, 114, 99, 19, 8, 31, 73, 19, 99, 10, 6, 121, 32, 13, 32, 119, 32, 29, 145, 30, 13, 13, 114, 145, 32, 1, 123, 39, 29, 31, 69, 31, 140, 72, 72, 25, 25, 123, 25, 123, 8, 4, 85, 8, 25, 39, 25, 39, 85, 138, 25, 138, 25, 33, 102, 70, 25, 25, 31, 25, 25, 192, 69, 69, 114, 145, 120, 120, 8, 33, 98, 15, 212, 155, 8,

101, 8, 8, 98, 68, 155, 102, 132, 120, 30, 25, 123, 123, 101, 25, 123, 32, 24, 94, 145, 32, 24, 94, 118, 145, 101, 53, 53, 25, 128, 173, 142, 81, 81, 69, 33, 33, 125, 4, 1, 17, 27, 4, 17, 102, 27, 13, 25, 128, 71, 13, 39, 53, 13, 53, 47, 39, 23, 128, 53, 39, 47, 39, 135, 158, 136, 36, 36, 27, 157, 47, 76, 213, 47, 156, 25, 25, 53, 25, 53, 25, 86, 27, 159, 25, 62, 79, 39, 79, 25, 145, 49, 25, 143, 13, 114, 150, 130, 94, 102, 39, 4, 39, 61, 77, 228, 22, 25, 47, 119, 205, 122, 119, 205, 119, 22, 119, 258, 143, 22, 81, 179, 22, 22, 143, 25, 65, 53, 168, 36, 79, 175, 37, 79, 70, 79, 103, 70, 25, 175, 4, 96, 96, 49, 128, 138, 96, 22, 62, 47, 95, 105, 95, 62, 95, 62, 142, 103, 69, 103, 30, 103, 34, 173, 127, 70, 127, 132, 18, 85, 22, 71, 18, 206, 206, 18, 128, 145, 70, 193, 188, 8, 125, 114, 70, 128, 114, 145, 102, 25, 12, 108, 102, 94, 10, 102, 1, 102, 124, 22, 22, 118, 132, 22, 116, 75, 41, 63, 41, 189, 208, 55, 85, 69, 8, 71, 53, 71, 69, 102, 165, 41, 99, 69, 33, 33, 29, 156, 102, 13, 251, 102, 25, 13, 109, 102, 164, 102, 164, 102, 25, 29, 228, 29, 259, 179, 222, 95, 94, 30, 30, 30, 142, 55, 142, 72, 55, 102, 128, 17, 69, 164, 165, 3, 164, 36, 165, 27, 27, 45, 21, 21, 237, 113, 83, 231, 106, 13, 154, 13, 154, 128, 154, 148, 258, 25, 154, 128, 3, 27, 10, 145, 145, 21, 146, 25, 1, 185, 121, 0, 1, 95, 55, 95, 95, 30, 0, 27, 95, 0, 95, 8, 222, 27, 121, 30, 95, 121, 0, 98, 94, 131, 55, 95, 95, 30, 98, 30, 0, 91, 145, 66, 179, 66, 58, 175, 29, 0, 31, 173, 146, 160, 39, 53, 28, 123, 199, 123, 175, 146, 156, 54, 54, 149, 25, 70, 178, 128, 25, 70, 70, 94, 224, 54, 4, 54, 54, 25, 228, 160, 206, 165, 143, 206, 108, 220, 234, 160, 13, 169, 103, 103, 103, 91, 213, 222, 91, 103, 91, 103, 31, 30, 123, 13, 62, 103, 50, 106, 42, 13, 145, 114, 220, 65, 8, 8, 175, 11, 104, 94, 118, 132, 27, 118, 193, 27, 128, 127, 127, 183, 33, 30, 29, 103, 128, 61, 234, 165, 41, 29, 193, 33, 207, 41, 165, 165, 55, 81, 157, 157, 8, 81, 11, 27, 8, 8, 98, 96, 142, 145, 41, 179, 112, 62, 180, 206, 206, 165, 39, 241, 45, 151, 26, 197, 102, 192, 125, 128, 67, 128, 69, 128, 197, 33, 125, 102, 13, 103, 25, 30, 12, 30, 12, 30, 25, 77, 12, 25, 180, 27, 10, 69, 235, 228, 343, 118, 69, 41, 8, 69, 175, 25, 69, 25, 125, 41, 25, 41, 8, 155, 146, 155, 146, 155, 206, 168, 128, 157, 27, 273, 211, 211, 168, 11, 173, 154, 77, 173, 77, 102, 102, 102, 8, 85, 95, 102, 157, 28, 122, 234, 122, 157, 235, 222, 241, 10, 91, 179, 25, 13, 25, 41, 25, 206, 41, 6, 41, 158, 206, 206, 33, 296, 296, 33, 228, 69, 8, 114, 148, 33, 29, 66, 27, 27, 30, 233, 54, 173, 108, 106, 108, 108, 53, 103, 33, 33, 33, 176, 27, 27, 205, 164, 105, 237, 41, 27, 72, 165, 29, 29, 259, 132, 132, 132, 364, 71, 71, 27, 94, 160, 127, 51, 234, 55, 27, 95, 94, 165, 55, 55, 41, 0, 41, 128, 4, 123, 173, 6, 164, 157, 121, 121, 154, 86, 164, 164, 25, 93, 164, 25, 164, 210, 284, 62, 93, 30, 25, 25, 30, 30, 260, 130, 25, 125, 57, 53, 166, 166, 166, 185, 166, 158, 94, 113, 215, 159, 62, 99, 21, 172, 99, 184, 62, 259, 4, 21, 21, 77, 62, 173, 41, 146, 6, 41, 128, 121, 41, 11, 121, 103, 159, 164, 175, 206, 91, 103, 164, 72, 25, 129, 72, 206, 129, 33, 103, 102, 102, 29, 13, 11, 251, 234, 135, 31, 8, 123, 65, 91, 121, 129, 65, 243, 10, 91, 8, 65, 70, 228, 220, 243, 91, 10, 10, 30, 178, 91, 178, 33, 21, 25, 235, 165, 11, 161,

158, 27, 27, 30, 128, 75, 36, 30, 36, 36, 173, 25, 33, 178, 112, 162, 112, 112, 112, 162, 33, 33, 178, 123, 123, 39, 106, 91, 106, 106, 158, 106, 106, 284, 39, 230, 21, 228, 11, 21, 228, 159, 241, 62, 10, 62, 10, 68, 234, 39, 39, 138, 62, 22, 27, 183, 22, 215, 10, 175, 175, 353, 228, 42, 193, 175, 175, 27, 98, 27, 193, 150, 27, 173, 17, 233, 233, 25, 102, 123, 152, 242, 108, 4, 94, 176, 13, 41, 219, 17, 151, 22, 103, 103, 53, 128, 233, 284, 25, 265, 128, 39, 39, 138, 42, 39, 21, 86, 95, 127, 29, 91, 46, 103, 103, 215, 25, 123, 123, 230, 25, 193, 180, 30, 60, 30, 242, 136, 180, 193, 30, 206, 180, 60, 165, 206, 193, 165, 123, 164, 103, 68, 25, 70, 91, 25, 82, 53, 82, 186, 53, 82, 53, 25, 30, 282, 91, 13, 234, 160, 160, 126, 149, 36, 36, 160, 149, 178, 160, 39, 294, 149, 149, 160, 39, 95, 221, 186, 106, 178, 316, 267, 53, 53, 164, 159, 164, 165, 94, 228, 53, 52, 178, 183, 53, 294, 128, 55, 140, 294, 25, 95, 366, 15, 304, 13, 183, 77, 230, 6, 136, 235, 121, 311, 273, 36, 158, 235, 230, 98, 201, 165, 165, 165, 91, 175, 248, 39, 185, 128, 39, 39, 128, 313, 91, 36, 219, 130, 25, 130, 234, 234, 130, 234, 121, 205, 304, 94, 77, 64, 259, 60, 60, 60, 77, 242, 60, 145, 95, 270, 18, 91, 199, 159, 91, 235, 58, 249, 26, 123, 114, 29, 15, 191, 15, 30, 55, 55, 347, 4, 29, 15, 4, 341, 93, 7, 30, 23, 7, 121, 266, 178, 261, 70, 169, 25, 25, 158, 169, 25, 169, 270, 270, 13, 128, 327, 103, 55, 128, 103, 136, 159, 103, 327, 41, 32, 111, 111, 114, 173, 215, 173, 25, 173, 180, 114, 173, 173, 98, 93, 25, 160, 157, 159, 160, 159, 159, 160, 320, 35, 193, 221, 33, 36, 136, 248, 91, 215, 125, 215, 156, 68, 125, 125, 1, 287, 123, 94, 30, 184, 13, 30, 94, 123, 206, 12, 206, 289, 128, 122, 184, 128, 289, 178, 29, 26, 206, 178, 65, 206, 128, 192, 102, 197, 36, 94, 94, 155, 10, 36, 121, 280, 121, 368, 192, 121, 121, 179, 121, 36, 54, 192, 121, 192, 197, 118, 123, 224, 118, 10, 192, 10, 91, 269, 91, 49, 206, 184, 185, 62, 8, 49, 289, 30, 5, 55, 30, 42, 39, 220, 298, 42, 347, 42, 234, 42, 70, 42, 55, 321, 129, 172, 173, 172, 13, 98, 129, 325, 235, 284, 362, 129, 233, 345, 175, 261, 175, 60, 261, 58, 289, 99, 99, 99, 206, 99, 36, 175, 29, 25, 432, 125, 264, 168, 173, 69, 158, 273, 179, 164, 69, 158, 69, 8, 95, 192, 30, 164, 101, 44, 53, 273, 335, 273, 53, 45, 128, 45, 234, 123, 105, 103, 103, 224, 36, 90, 211, 282, 264, 91, 228, 91, 166, 264, 228, 398, 50, 101, 91, 264, 73, 36, 25, 73, 50, 50, 242, 36, 36, 58, 165, 204, 353, 165, 125, 320, 128, 298, 298, 180, 128, 60, 102, 30, 30, 53, 179, 234, 325, 234, 175, 21, 250, 215, 103, 21, 21, 250, 91, 211, 91, 313, 301, 323, 215, 228, 160, 29, 29, 81, 53, 180, 146, 248, 66, 159, 39, 98, 323, 98, 36, 95, 218, 234, 39, 82, 82, 230, 62, 13, 62, 230, 13, 30, 98, 0, 8, 98, 8, 98, 91, 267, 121, 197, 30, 78, 27, 78, 102, 27, 298, 160, 103, 264, 264, 264, 175, 17, 273, 273, 165, 31, 160, 17, 99, 17, 99, 234, 31, 17, 99, 36, 26, 128, 29, 214, 353, 264, 102, 36, 102, 264, 264, 273, 273, 4, 16, 138, 138, 264, 128, 313, 25, 420, 60, 10, 280, 264, 60, 60, 103, 178, 125, 178, 29, 327, 29, 36, 30, 36, 4, 52, 183, 183, 173, 52, 31, 173, 31, 158, 31, 158, 31, 9, 31, 31, 353, 31, 353, 173, 415, 9, 17, 222, 31, 103, 31, 165, 27, 31, 31, 165, 27, 27, 206, 31, 31, 4, 4, 30, 4, 4, 264, 185, 159, 310, 273, 310, 173, 40, 4, 173, 4,

173, 4, 250, 250, 62, 188, 119, 250, 233, 62, 121, 105, 105, 54, 103, 111, 291, 236, 236, 103, 297, 36, 26, 316, 69, 183, 158, 206, 129, 160, 129, 184, 55, 179, 279, 11, 179, 347, 160, 184, 129, 179, 351, 179, 353, 179, 129, 129, 351, 11, 111, 93, 93, 235, 103, 173, 53, 93, 50, 111, 86, 123, 94, 36, 183, 60, 55, 55, 178, 219, 253, 321, 178, 235, 235, 183, 183, 204, 321, 219, 160, 193, 335, 121, 70, 69, 295, 159, 297, 231, 121, 231, 136, 353, 136, 121, 279, 215, 366, 215, 353, 159, 353, 353, 103, 31, 31, 298, 298, 30, 30, 165, 273, 25, 219, 35, 165, 259, 54, 36, 54, 54, 165, 71, 250, 327, 13, 289, 165, 196, 165, 165, 94, 233, 165, 94, 60, 165, 96, 220, 166, 271, 158, 397, 122, 53, 53, 137, 280, 272, 62, 30, 30, 30, 105, 102, 67, 140, 8, 67, 21, 270, 298, 69, 173, 298, 91, 179, 327, 86, 179, 88, 179, 179, 55, 123, 220, 233, 94, 94, 175, 13, 53, 13, 154, 191, 74, 83, 83, 325, 207, 83, 74, 83, 325, 74, 316, 388, 55, 55, 364, 55, 183, 434, 273, 273, 273, 164, 213, 11, 213, 327, 321, 21, 352, 185, 103, 13, 13, 55, 30, 323, 123, 178, 435, 178, 30, 175, 175, 30, 481, 527, 175, 125, 232, 306, 232, 206, 306, 364, 206, 270, 206, 232, 10, 30, 130, 160, 130, 347, 240, 30, 136, 130, 347, 136, 279, 298, 206, 30, 103, 273, 241, 70, 206, 306, 434, 206, 94, 94, 156, 161, 321, 321, 64, 161, 13, 183, 183, 83, 161, 13, 169, 13, 159, 36, 173, 159, 36, 36, 230, 235, 235, 159, 159, 335, 312, 42, 342, 264, 39, 39, 39, 34, 298, 36, 36, 252, 164, 29, 493, 29, 387, 387, 435, 493, 132, 273, 105, 132, 74, 73, 206, 234, 273, 206, 95, 15, 280, 280, 280, 280, 397, 273, 273, 242, 397, 280, 397, 397, 397, 273, 397, 280, 230, 137, 353, 67, 81, 137, 137, 353, 259, 312, 114, 164, 164, 25, 77, 21, 77, 165, 30, 30, 231, 234, 121, 234, 312, 121, 364, 136, 123, 123, 136, 123, 136, 150, 264, 285, 30, 166, 93, 30, 39, 224, 136, 39, 355, 355, 397, 67, 67, 25, 67, 25, 298, 11, 67, 264, 374, 99, 150, 321, 67, 70, 67, 295, 150, 29, 321, 150, 70, 29, 142, 355, 311, 173, 13, 253, 103, 114, 114, 70, 192, 22, 128, 128, 183, 184, 70, 77, 215, 102, 292, 30, 123, 279, 292, 142, 33, 215, 102, 468, 123, 468, 473, 30, 292, 215, 30, 213, 443, 473, 215, 234, 279, 279, 279, 279, 265, 443, 206, 66, 313, 34, 30, 206, 30, 51, 15, 206, 41, 434, 41, 398, 67, 30, 301, 67, 36, 3, 285, 437, 136, 136, 22, 136, 145, 365, 323, 323, 145, 136, 22, 453, 99, 323, 353, 9, 258, 323, 231, 128, 231, 382, 150, 420, 39, 94, 29, 29, 353, 22, 22, 347, 353, 39, 29, 22, 183, 8, 284, 355, 388, 284, 60, 64, 99, 60, 64, 150, 95, 150, 364, 150, 95, 150, 6, 236, 383, 544, 81, 206, 388, 206, 58, 159, 99, 231, 228, 363, 363, 121, 99, 121, 121, 99, 422, 544, 273, 173, 121, 427, 102, 121, 235, 284, 179, 25, 197, 25, 179, 511, 70, 368, 70, 25, 388, 123, 368, 159, 213, 410, 159, 236, 127, 159, 21, 373, 184, 424, 327, 250, 176, 176, 175, 284, 316, 176, 284, 327, 111, 250, 284, 175, 175, 264, 111, 176, 219, 111, 427, 427, 176, 284, 427, 353, 428, 55, 184, 493, 158, 136, 99, 287, 264, 334, 264, 213, 213, 292, 481, 93, 264, 292, 295, 295, 6, 367, 279, 173, 308, 285, 158, 308, 335, 299, 137, 137, 572, 41, 137, 137, 41, 94, 335, 220, 36, 224, 420, 36, 265, 265, 91, 91, 71, 123, 264, 91, 91, 123, 107, 30, 22, 292, 35, 241, 356, 298, 14, 298, 441, 35, 121, 71, 63, 130, 63, 488, 363, 71, 63, 307, 194, 71, 71, 220, 121, 125, 71,

220, 71, 71, 71, 71, 235, 265, 353, 128, 155, 128, 420, 400, 130, 173, 183, 183, 184, 130, 173, 183, 13, 183, 130, 130, 183, 183, 353, 353, 183, 242, 183, 183, 306, 324, 324, 321, 306, 321, 6, 6, 128, 306, 242, 242, 306, 183, 183, 6, 183, 321, 486, 183, 164, 30, 78, 138, 158, 138, 34, 206, 362, 55, 70, 67, 21, 375, 136, 298, 81, 298, 298, 298, 230, 121, 30, 230, 311, 240, 311, 311, 158, 204, 136, 136, 184, 136, 264, 311, 311, 312, 312, 72, 311, 175, 264, 91, 175, 264, 121, 461, 312, 312, 238, 475, 350, 512, 350, 312, 313, 350, 312, 366, 294, 30, 253, 253, 253, 388, 158, 388, 22, 388, 22, 388, 103, 321, 321, 253, 7, 437, 103, 114, 242, 114, 114, 242, 114, 114, 242, 242, 242, 306, 242, 114, 7, 353, 335, 27, 241, 299, 312, 364, 506, 409, 94, 462, 230, 462, 243, 230, 175, 175, 462, 461, 230, 428, 426, 175, 175, 165, 175, 175, 372, 183, 572, 102, 85, 102, 538, 206, 376, 85, 85, 284, 85, 85, 284, 398, 83, 160, 265, 308, 398, 310, 583, 289, 279, 273, 285, 490, 490, 211, 292, 292, 158, 398, 30, 220, 169, 368, 368, 368, 169, 159, 368, 93, 368, 368, 93, 169, 368, 368, 443, 368, 298, 443, 368, 298, 538, 345, 345, 311, 178, 54, 311, 215, 178, 175, 222, 264, 475, 264, 264, 475, 478, 289, 63, 236, 63, 299, 231, 296, 397, 299, 158, 36, 164, 164, 21, 492, 21, 164, 21, 164, 403, 26, 26, 588, 179, 234, 169, 465, 295, 67, 41, 353, 295, 538, 161, 185, 306, 323, 68, 420, 323, 82, 241, 241, 36, 53, 493, 301, 292, 241, 250, 63, 63, 103, 442, 353, 185, 353, 321, 353, 185, 353, 353, 185, 409, 353, 589, 34, 271, 271, 34, 86, 34, 34, 353, 353, 39, 414, 4, 95, 95, 4, 225, 95, 4, 121, 30, 552, 136, 159, 159, 514, 159, 159, 54, 514, 206, 136, 206, 159, 74, 235, 235, 312, 54, 312, 42, 156, 422, 629, 54, 465, 265, 165, 250, 35, 165, 175, 659, 175, 175, 8, 8, 8, 8, 206, 206, 206, 50, 435, 206, 432, 230, 230, 234, 230, 94, 299, 299, 285, 184, 41, 93, 299, 299, 285, 41, 285, 158, 285, 206, 299, 41, 36, 396, 364, 364, 120, 396, 514, 91, 382, 538, 807, 717, 22, 93, 412, 54, 215, 54, 298, 308, 148, 298, 148, 298, 308, 102, 656, 6, 148, 745, 128, 298, 64, 407, 273, 41, 172, 64, 234, 250, 398, 181, 445, 95, 236, 441, 477, 504, 102, 196, 137, 364, 60, 453, 137, 364, 367, 334, 364, 299, 196, 397, 630, 589, 589, 196, 646, 337, 235, 128, 128, 343, 289, 235, 324, 427, 324, 58, 215, 215, 461, 425, 461, 387, 440, 285, 440, 440, 285, 387, 632, 325, 325, 440, 461, 425, 425, 387, 627, 191, 285, 440, 308, 55, 219, 280, 308, 265, 538, 183, 121, 30, 236, 206, 30, 455, 236, 30, 30, 705, 83, 228, 280, 468, 132, 8, 132, 132, 128, 409, 173, 353, 132, 409, 35, 128, 450, 137, 398, 67, 432, 423, 235, 235, 388, 306, 93, 93, 452, 300, 190, 13, 452, 388, 30, 452, 13, 30, 13, 30, 306, 362, 234, 721, 635, 809, 784, 67, 498, 498, 67, 353, 635, 67, 183, 159, 445, 285, 183, 53, 183, 445, 265, 432, 57, 420, 432, 420, 477, 327, 55, 60, 105, 183, 218, 104, 104, 475, 239, 582, 151, 239, 104, 732, 41, 26, 784, 86, 300, 215, 36, 64, 86, 86, 675, 294, 64, 86, 528, 550, 493, 565, 298, 230, 312, 295, 538, 298, 295, 230, 54, 374, 516, 441, 54, 54, 323, 401, 401, 382, 159, 837, 159, 54, 401, 592, 159, 401, 417, 610, 264, 150, 323, 452, 185, 323, 323, 185, 403, 185, 423, 165, 425, 219, 407, 270, 231, 99, 93, 231, 631, 756, 71, 364, 434, 213, 86, 102, 434, 102, 86, 23, 71, 335, 164, 323,

409, 381, 4, 124, 41, 424, 206, 41, 124, 41, 41, 703, 635, 124, 493, 41, 41, 487, 492, 124, 175, 124, 261, 600, 488, 261, 488, 261, 206, 677, 261, 308, 723, 908, 704, 691, 723, 488, 488, 441, 136, 476, 312, 136, 550, 572, 728, 550, 22, 312, 312, 22, 55, 413, 183, 280, 593, 191, 36, 36, 427, 36, 695, 592, 19, 544, 13, 468, 13, 544, 72, 437, 321, 266, 461, 266, 441, 230, 409, 93, 521, 521, 345, 235, 22, 142, 150, 102, 569, 235, 264, 91, 521, 264, 7, 102, 7, 498, 521, 235, 537, 235, 6, 241, 420, 420, 631, 41, 527, 103, 67, 337, 62, 264, 527, 131, 67, 174, 263, 264, 36, 36, 263, 581, 253, 465, 160, 286, 91, 160, 55, 4, 4, 631, 631, 608, 365, 465, 294, 427, 427, 335, 669, 669, 129, 93, 93, 93, 93, 74, 66, 758, 504, 347, 130, 505, 504, 143, 505, 550, 222, 13, 352, 529, 291, 538, 50, 68, 269, 130, 295, 130, 511, 295, 295, 130, 486, 132, 61, 206, 185, 368, 669, 22, 175, 492, 207, 373, 452, 432, 327, 89, 550, 496, 611, 527, 89, 527, 496, 550, 516, 516, 91, 136, 538, 264, 264, 124, 264, 264, 264, 264, 264, 535, 264, 150, 285, 398, 285, 582, 398, 475, 81, 694, 694, 64, 81, 694, 234, 607, 723, 513, 234, 64, 581, 64, 124, 64, 607, 234, 723, 717, 367, 64, 513, 607, 488, 183, 488, 450, 183, 550, 286, 183, 363, 286, 414, 67, 449, 449, 366, 215, 235, 95, 295, 295, 41, 335, 21, 445, 225, 21, 295, 372, 749, 461, 53, 481, 397, 427, 427, 427, 714, 481, 714, 427, 717, 165, 245, 486, 415, 245, 415, 486, 274, 415, 441, 456, 300, 548, 300, 422, 422, 757, 11, 74, 430, 430, 136, 409, 430, 749, 191, 819, 592, 136, 364, 465, 231, 231, 918, 160, 589, 160, 160, 465, 465, 231, 157, 538, 538, 259, 538, 326, 22, 22, 22, 179, 22, 22, 550, 179, 287, 287, 417, 327, 498, 498, 287, 488, 327, 538, 488, 583, 488, 287, 335, 287, 335, 287, 41, 287, 335, 287, 327, 441, 335, 287, 488, 538, 327, 498, 8, 8, 374, 8, 64, 427, 8, 374, 417, 760, 409, 373, 160, 423, 206, 160, 106, 499, 160, 271, 235, 160, 590, 353, 695, 478, 619, 590, 353, 13, 63, 189, 420, 605, 427, 643, 121, 280, 415, 121, 415, 595, 417, 121, 398, 55, 330, 463, 463, 123, 353, 330, 582, 309, 582, 582, 405, 330, 550, 405, 582, 353, 309, 308, 60, 353, 7, 60, 71, 353, 189, 183, 183, 183, 582, 755, 189, 437, 287, 189, 183, 668, 481, 384, 384, 481, 481, 481, 477, 582, 582, 499, 650, 481, 121, 461, 231, 36, 235, 36, 413, 235, 209, 36, 689, 114, 353, 353, 235, 592, 36, 353, 413, 209, 70, 308, 70, 699, 308, 70, 213, 292, 86, 689, 465, 55, 508, 128, 452, 29, 41, 681, 573, 352, 21, 21, 648, 648, 69, 509, 409, 21, 264, 21, 509, 514, 514, 409, 21, 264, 443, 443, 427, 160, 433, 663, 433, 231, 646, 185, 482, 646, 433, 13, 398, 172, 234, 42, 491, 172, 234, 234, 832, 775, 172, 196, 335, 822, 461, 298, 461, 364, 1120, 537, 169, 169, 364, 694, 219, 612, 231, 740, 42, 235, 321, 279, 960, 279, 353, 492, 159, 572, 321, 159, 287, 353, 287, 287, 206, 206, 321, 287, 159, 321, 492, 159, 55, 572, 600, 270, 492, 784, 173, 91, 91, 443, 443, 582, 261, 497, 572, 91, 555, 352, 206, 261, 555, 285, 91, 555, 497, 83, 91, 619, 353, 488, 112, 4, 592, 295, 295, 488, 235, 231, 769, 568, 581, 671, 451, 451, 483, 299, 1011, 432, 422, 207, 106, 701, 508, 555, 508, 555, 125, 870, 555, 589, 508, 125, 749, 482, 125, 125, 130, 544, 643, 643, 544, 488, 22, 643, 130, 335, 544, 22, 130, 544, 544, 488, 426, 426, 4, 180, 4, 695, 35, 54, 433, 500, 592, 433, 262,

94, 401, 401, 106, 216, 216, 106, 521, 102, 462, 518, 271, 475, 365, 193, 648, 206, 424, 206, 193, 206, 206, 424, 299, 590, 590, 364, 621, 67, 538, 488, 567, 51, 51, 513, 194, 81, 488, 486, 289, 567, 563, 749, 563, 338, 338, 502, 563, 822, 338, 563, 338, 502, 201, 230, 201, 533, 445, 175, 201, 175, 13, 85, 960, 103, 85, 175, 30, 445, 445, 175, 573, 196, 877, 287, 356, 678, 235, 489, 312, 572, 264, 717, 138, 295, 6, 295, 523, 55, 165, 165, 295, 138, 663, 6, 295, 6, 353, 138, 6, 138, 169, 129, 784, 12, 129, 194, 605, 784, 445, 234, 627, 563, 689, 627, 647, 570, 627, 570, 647, 206, 234, 215, 234, 816, 627, 816, 234, 627, 215, 234, 627, 264, 427, 427, 30, 424, 161, 161, 916, 740, 180, 616, 481, 514, 383, 265, 481, 164, 650, 121, 582, 689, 420, 669, 589, 420, 788, 549, 165, 734, 280, 224, 146, 681, 788, 184, 398, 784, 4, 398, 417, 417, 398, 636, 784, 417, 81, 398, 417, 81, 185, 827, 420, 241, 420, 41, 185, 185, 718, 241, 101, 185, 185, 241, 241, 241, 241, 241, 185, 324, 420, 420, 1011, 420, 827, 241, 184, 563, 241, 183, 285, 529, 285, 808, 822, 891, 822, 488, 285, 486, 619, 55, 869, 39, 567, 39, 289, 203, 158, 289, 710, 818, 158, 818, 355, 29, 409, 203, 308, 648, 792, 308, 308, 91, 308, 6, 592, 792, 106, 106, 308, 41, 178, 91, 751, 91, 259, 734, 166, 36, 327, 166, 230, 205, 205, 172, 128, 230, 432, 623, 838, 623, 432, 278, 432, 42, 916, 432, 694, 623, 352, 452, 93, 314, 93, 93, 641, 88, 970, 914, 230, 61, 159, 270, 159, 493, 159, 755, 159, 409, 30, 30, 836, 128, 241, 99, 102, 984, 538, 102, 102, 273, 639, 838, 102, 102, 136, 637, 508, 627, 285, 465, 327, 327, 21, 749, 327, 749, 21, 845, 21, 21, 409, 749, 1367, 806, 616, 714, 253, 616, 714, 714, 112, 375, 21, 112, 375, 375, 51, 51, 51, 51, 393, 206, 870, 713, 193, 802, 21, 1061, 42, 382, 42, 543, 876, 42, 876, 382, 696, 543, 635, 490, 353, 353, 417, 64, 1257, 271, 64, 377, 127, 127, 537, 417, 905, 353, 538, 465, 605, 876, 427, 324, 514, 852, 427, 53, 427, 557, 173, 173, 7, 1274, 563, 31, 31, 31, 745, 392, 289, 230, 230, 230, 91, 218, 327, 420, 420, 128, 901, 552, 420, 230, 608, 552, 476, 347, 476, 231, 159, 137, 716, 648, 716, 627, 740, 718, 679, 679, 6, 718, 740, 6, 189, 679, 125, 159, 757, 1191, 409, 175, 250, 409, 67, 324, 681, 605, 550, 398, 550, 931, 478, 174, 21, 316, 91, 316, 654, 409, 425, 425, 699, 61, 699, 321, 698, 321, 698, 61, 425, 699, 321, 409, 699, 299, 335, 321, 335, 61, 698, 699, 654, 698, 299, 425, 231, 14, 121, 515, 121, 14, 165, 81, 409, 189, 81, 373, 465, 463, 1055, 507, 81, 81, 189, 1246, 321, 409, 886, 104, 842, 689, 300, 740, 380, 656, 656, 832, 656, 380, 300, 300, 206, 187, 175, 142, 465, 206, 271, 468, 215, 560, 83, 215, 83, 215, 215, 83, 175, 215, 83, 83, 111, 206, 756, 559, 756, 1367, 206, 559, 1015, 559, 559, 946, 1015, 548, 559, 756, 1043, 756, 698, 159, 414, 308, 458, 997, 663, 663, 347, 39, 755, 838, 323, 755, 323, 159, 159, 717, 159, 21, 41, 128, 516, 159, 717, 71, 870, 755, 159, 740, 717, 374, 516, 740, 51, 148, 335, 148, 335, 791, 120, 364, 335, 335, 51, 120, 251, 538, 251, 971, 1395, 538, 78, 178, 538, 538, 918, 129, 918, 129, 538, 538, 656, 129, 538, 538, 129, 538, 1051, 538, 128, 838, 931, 998, 823, 1095, 334, 870, 334, 367, 550, 1061, 498, 745, 832, 498, 745, 716, 498, 498, 128, 997, 832, 716, 832, 130, 642, 616, 497, 432, 432, 432,

432, 642, 159, 432, 46, 230, 788, 160, 230, 478, 46, 693, 103, 920, 230, 589, 643, 160, 616, 432, 165, 165, 583, 592, 838, 784, 583, 710, 6, 583, 583, 6, 35, 230, 838, 592, 710, 6, 589, 230, 838, 30, 592, 583, 6, 583, 6, 6, 583, 30, 30, 6, 375, 375, 99, 36, 1158, 425, 662, 417, 681, 364, 375, 1025, 538, 822, 669, 893, 538, 538, 450, 409, 632, 527, 632, 563, 632, 527, 550, 71, 698, 550, 39, 550, 514, 537, 514, 537, 111, 41, 173, 592, 173, 648, 173, 173, 173, 1011, 514, 173, 173, 514, 166, 648, 355, 161, 166, 648, 497, 327, 327, 550, 650, 21, 425, 605, 555, 103, 425, 605, 842, 836, 1011, 636, 138, 756, 836, 756, 756, 353, 1011, 636, 636, 1158, 741, 741, 842, 756, 741, 1011, 677, 1011, 770, 366, 306, 488, 920, 920, 665, 775, 502, 500, 775, 775, 648, 364, 833, 207, 13, 93, 500, 364, 500, 665, 500, 93, 295, 183, 1293, 313, 272, 313, 279, 303, 93, 516, 93, 1013, 381, 6, 93, 93, 303, 259, 643, 168, 673, 230, 1261, 230, 230, 673, 1060, 1079, 1079, 550, 741, 741, 590, 527, 741, 741, 442, 741, 442, 848, 741, 590, 925, 219, 527, 925, 335, 442, 590, 239, 590, 590, 590, 239, 527, 239, 1033, 230, 734, 241, 741, 230, 549, 548, 1015, 1015, 32, 36, 433, 465, 724, 465, 73, 73, 73, 465, 808, 73, 592, 1430, 250, 154, 154, 250, 538, 353, 353, 353, 353, 353, 175, 194, 206, 538, 632, 1163, 960, 175, 175, 538, 452, 632, 1163, 175, 538, 960, 194, 175, 194, 632, 960, 632, 94, 632, 461, 960, 1163, 1163, 461, 632, 960, 755, 707, 105, 382, 625, 382, 382, 784, 707, 871, 559, 387, 387, 871, 784, 559, 784, 88, 36, 570, 314, 1028, 975, 335, 335, 398, 573, 573, 573, 21, 215, 562, 738, 612, 424, 21, 103, 788, 870, 912, 23, 186, 757, 73, 818, 23, 73, 563, 952, 262, 563, 137, 262, 1022, 952, 137, 1273, 442, 952, 604, 137, 308, 384, 913, 235, 325, 695, 398, 95, 668, 776, 713, 309, 691, 22, 10, 364, 682, 682, 578, 481, 1252, 1072, 1252, 825, 578, 825, 1072, 1149, 592, 273, 387, 273, 427, 155, 1204, 50, 452, 50, 1142, 50, 367, 452, 1142, 611, 367, 50, 50, 367, 50, 1675, 99, 367, 50, 1501, 1099, 830, 681, 689, 917, 1089, 453, 425, 235, 918, 538, 550, 335, 161, 387, 859, 324, 21, 838, 859, 1123, 21, 723, 21, 335, 335, 206, 21, 364, 1426, 21, 838, 838, 335, 364, 21, 21, 859, 920, 838, 838, 397, 81, 639, 397, 397, 588, 933, 933, 784, 222, 830, 36, 36, 222, 1251, 266, 36, 146, 266, 366, 581, 605, 366, 22, 966, 681, 681, 433, 730, 1013, 550, 21, 21, 938, 488, 516, 21, 21, 656, 420, 323, 323, 323, 327, 323, 918, 581, 581, 830, 361, 830, 364, 259, 364, 496, 496, 364, 691, 705, 691, 475, 427, 1145, 600, 179, 427, 527, 749, 869, 689, 335, 347, 220, 298, 689, 1426, 183, 554, 55, 832, 550, 550, 165, 770, 957, 67, 1386, 219, 683, 683, 355, 683, 355, 355, 738, 355, 842, 931, 266, 325, 349, 256, 1113, 256, 423, 960, 554, 554, 325, 554, 508, 22, 142, 22, 508, 916, 767, 55, 1529, 767, 55, 1286, 93, 972, 550, 931, 1286, 1286, 972, 93, 1286, 1392, 890, 93, 1286, 93, 1286, 972, 374, 931, 890, 808, 779, 975, 975, 175, 173, 4, 681, 383, 1367, 173, 383, 1367, 383, 173, 175, 69, 238, 146, 238, 36, 148, 888, 238, 173, 238, 148, 238, 888, 185, 925, 925, 797, 925, 815, 925, 469, 784, 289, 784, 925, 797, 925, 925, 1093, 925, 925, 925, 1163, 797, 797, 815, 925, 1093, 784, 636, 663, 925, 187, 922, 316, 1380, 709, 916, 916, 187, 355, 948, 916, 187,

916, 916, 948, 948, 916, 355, 316, 316, 334, 300, 1461, 36, 583, 1179, 699, 235, 858, 583, 699, 858, 699, 1189, 1256, 1189, 699, 797, 699, 699, 699, 699, 427, 488, 427, 488, 175, 815, 656, 656, 150, 322, 465, 322, 870, 465, 1099, 582, 665, 767, 749, 635, 749, 600, 1448, 36, 502, 235, 502, 355, 502, 355, 355, 355, 172, 355, 355, 95, 866, 425, 393, 1165, 42, 42, 42, 393, 939, 909, 909, 836, 552, 424, 1333, 852, 897, 1426, 1333, 1446, 1426, 997, 1011, 852, 1198, 55, 32, 239, 588, 681, 681, 239, 1401, 32, 588, 239, 462, 286, 1260, 984, 1160, 960, 960, 486, 828, 462, 960, 1199, 581, 850, 663, 581, 751, 581, 581, 1571, 252, 252, 1283, 264, 430, 264, 430, 430, 842, 252, 745, 21, 307, 681, 1592, 488, 857, 857, 1161, 857, 857, 857, 138, 374, 374, 1196, 374, 1903, 1782, 1626, 414, 112, 1477, 1040, 356, 775, 414, 414, 112, 356, 775, 435, 338, 1066, 689, 689, 1501, 689, 1249, 205, 689, 765, 220, 308, 917, 308, 308, 220, 327, 387, 838, 917, 917, 917, 220, 662, 308, 220, 387, 387, 220, 220, 308, 308, 308, 387, 1009, 1745, 822, 279, 554, 1129, 543, 383, 870, 1425, 241, 870, 241, 383, 716, 592, 21, 21, 592, 425, 550, 550, 550, 427, 230, 57, 483, 784, 860, 57, 308, 57, 486, 870, 447, 486, 433, 433, 870, 433, 997, 486, 443, 433, 433, 997, 486, 1292, 47, 708, 81, 895, 394, 81, 935, 81, 81, 81, 374, 986, 916, 1103, 1095, 465, 495, 916, 667, 1745, 518, 220, 1338, 220, 734, 1294, 741, 166, 828, 741, 741, 1165, 1371, 1371, 471, 1371, 647, 1142, 1878, 1878, 1371, 1371, 822, 66, 327, 158, 427, 427, 465, 465, 676, 676, 30, 30, 676, 676, 893, 1592, 93, 455, 308, 582, 695, 582, 629, 582, 85, 1179, 85, 85, 1592, 1179, 280, 1027, 681, 398, 1027, 398, 295, 784, 740, 509, 425, 968, 509, 46, 833, 842, 401, 184, 401, 464, 6, 1501, 1501, 550, 538, 883, 538, 883, 883, 883, 1129, 550, 550, 333, 689, 948, 21, 21, 241, 2557, 2094, 273, 308, 58, 863, 893, 1086, 409, 136, 1086, 592, 592, 830, 830, 883, 830, 277, 68, 689, 902, 277, 453, 507, 129, 689, 630, 664, 550, 128, 1626, 1626, 128, 902, 312, 589, 755, 755, 589, 755, 407, 1782, 589, 784, 1516, 1118, 407, 407, 1447, 589, 235, 755, 1191, 235, 235, 407, 128, 589, 1118, 21, 383, 1331, 691, 481, 383, 1129, 1129, 1261, 1104, 1378, 1129, 784, 1129, 1261, 1129, 947, 1129, 784, 784, 1129, 1129, 35, 1104, 35, 866, 1129, 1129, 64, 481, 730, 1260, 481, 970, 481, 481, 481, 481, 863, 481, 681, 699, 863, 486, 681, 481, 481, 55, 55, 235, 1364, 944, 632, 822, 401, 822, 952, 822, 822, 99, 550, 2240, 550, 70, 891, 860, 860, 550, 550, 916, 1176, 1530, 425, 1530, 916, 628, 1583, 916, 628, 916, 916, 628, 628, 425, 916, 1062, 1265, 916, 916, 916, 280, 461, 916, 916, 1583, 628, 1062, 916, 916, 677, 1297, 924, 1260, 83, 1260, 482, 433, 234, 462, 323, 1656, 997, 323, 323, 931, 838, 931, 1933, 1391, 367, 323, 931, 1391, 1391, 103, 1116, 1116, 1116, 769, 1195, 1218, 312, 791, 312, 741, 791, 997, 312, 334, 334, 312, 287, 287, 633, 1397, 1426, 605, 1431, 327, 592, 705, 1194, 592, 1097, 1118, 1503, 1267, 1267, 1267, 618, 1229, 734, 1089, 785, 1089, 1129, 1148, 1148, 1089, 915, 1148, 1129, 1148, 1011, 1011, 1229, 871, 1560, 1560, 1560, 563, 1537, 1009, 1560, 632, 985, 592, 1308, 592, 882, 145, 145, 397, 837, 383, 592, 592, 832, 36, 2714, 2107, 1588, 1347, 36, 36, 1443, 1453, 334, 2230, 1588, 1169, 650,

1169, 2107, 425, 425, 891, 891, 425, 2532, 679, 274, 274, 274, 325, 274, 1297, 194, 1297, 627, 314, 917, 314, 314, 1501, 414, 1490, 1036, 592, 1036, 1025, 901, 1218, 1025, 901, 280, 592, 592, 901, 1461, 159, 159, 159, 2076, 1066, 1176, 1176, 516, 327, 516, 1179, 1176, 899, 1176, 1176, 323, 1187, 1229, 663, 1229, 504, 1229, 916, 1229, 916, 1661, 41, 36, 278, 1027, 648, 648, 648, 1626, 648, 646, 1179, 1580, 1061, 1514, 1008, 1741, 2076, 1514, 1008, 952, 1089, 427, 952, 427, 1083, 425, 427, 1089, 1083, 425, 427, 425, 230, 920, 1678, 920, 1678, 189, 189, 953, 189, 133, 189, 1075, 189, 189, 133, 1264, 725, 189, 1629, 189, 808, 230, 230, 2179, 770, 230, 770, 230, 21, 21, 784, 1118, 230, 230, 230, 770, 1118, 986, 808, 916, 30, 327, 918, 679, 414, 916, 1165, 1355, 916, 755, 733, 433, 1490, 433, 433, 433, 605, 433, 433, 433, 1446, 679, 206, 433, 21, 2452, 206, 206, 433, 1894, 206, 822, 206, 2073, 206, 206, 21, 822, 21, 206, 206, 21, 383, 1513, 375, 1347, 432, 1589, 172, 954, 242, 1256, 1256, 1248, 1256, 1256, 1248, 1248, 1256, 842, 13, 592, 13, 842, 1291, 592, 21, 175, 13, 592, 13, 13, 1426, 13, 1541, 445, 808, 808, 863, 647, 219, 1592, 1029, 1225, 917, 1963, 1129, 555, 1313, 550, 660, 550, 220, 660, 552, 663, 220, 533, 220, 383, 550, 1278, 1495, 636, 842, 1036, 425, 842, 425, 1537, 1278, 842, 554, 1508, 636, 554, 301, 842, 792, 1392, 1021, 284, 1172, 997, 1021, 103, 1316, 308, 1210, 848, 848, 1089, 1089, 848, 848, 67, 1029, 827, 1029, 2078, 827, 1312, 1029, 827, 590, 872, 1312, 427, 67, 67, 67, 67, 872, 827, 872, 2126, 1436, 26, 2126, 67, 1072, 2126, 1610, 872, 1620, 883, 883, 1397, 1189, 555, 555, 563, 1189, 555, 640, 555, 640, 1089, 1089, 610, 610, 1585, 610, 1355, 610, 1015, 616, 925, 1015, 482, 230, 707, 231, 888, 1355, 589, 1379, 151, 931, 1486, 1486, 393, 235, 960, 590, 235, 960, 422, 142, 285, 285, 327, 327, 442, 2009, 822, 445, 822, 567, 888, 2611, 1537, 323, 55, 1537, 323, 888, 2611, 323, 1537, 323, 58, 445, 593, 2045, 593, 58, 47, 770, 842, 47, 47, 842, 842, 648, 2557, 173, 689, 2291, 1446, 2085, 2557, 2557, 2291, 1780, 1535, 2291, 2391, 808, 691, 1295, 1165, 983, 948, 2000, 948, 983, 983, 2225, 2000, 983, 983, 705, 948, 2000, 1795, 1592, 478, 592, 1795, 1795, 663, 478, 1790, 478, 592, 1592, 173, 901, 312, 4, 1606, 173, 838, 754, 754, 128, 550, 1166, 551, 1480, 550, 550, 1875, 1957, 1166, 902, 1875, 550, 550, 551, 2632, 551, 1875, 1875, 551, 2891, 2159, 2632, 3231, 551, 815, 150, 1654, 1059, 1059, 734, 770, 555, 1592, 555, 2059, 770, 770, 1803, 627, 627, 627, 2059, 931, 1272, 427, 1606, 1272, 1606, 1187, 1204, 397, 822, 21, 1645, 263, 263, 822, 263, 1645, 280, 263, 605, 1645, 2014, 21, 21, 1029, 263, 1916, 2291, 397, 397, 496, 270, 270, 1319, 264, 1638, 264, 986, 1278, 1397, 1278, 1191, 409, 1191, 740, 1191, 754, 754, 387, 63, 948, 666, 666, 1198, 548, 63, 1248, 285, 1248, 169, 1248, 1248, 285, 918, 224, 285, 1426, 1671, 514, 514, 717, 514, 51, 1521, 1745, 51, 605, 1191, 51, 128, 1191, 51, 51, 1521, 267, 513, 952, 966, 1671, 897, 51, 71, 592, 986, 986, 1121, 592, 280, 2000, 2000, 1165, 1165, 1165, 1818, 222, 1818, 1165, 1252, 506, 327, 443, 432, 1291, 1291, 2755, 1413, 520, 1318, 227, 1047, 828, 520, 347, 1364, 136, 136, 452, 457, 457, 132, 457, 488, 1087, 1013, 2225, 32, 1571, 2009, 483, 67, 483,

740, 740, 1013, 2854, 866, 32, 2861, 866, 887, 32, 2444, 740, 32, 32, 866, 2225, 866, 32, 1571, 2627, 32, 850, 1675, 569, 1158, 32, 1158, 1797, 2641, 1565, 1158, 569, 1797, 1158, 1797, 55, 1703, 42, 55, 2562, 675, 1703, 42, 55, 749, 488, 488, 347, 1206, 1286, 1286, 488, 488, 1206, 1286, 1206, 1286, 550, 550, 1790, 860, 550, 2452, 550, 550, 2765, 1089, 1633, 797, 2244, 1313, 194, 2129, 194, 194, 194, 818, 32, 194, 450, 1313, 2387, 194, 1227, 2387, 308, 2232, 526, 476, 278, 830, 830, 194, 830, 194, 278, 194, 714, 476, 830, 714, 830, 278, 830, 2532, 1218, 1759, 1446, 960, 1747, 187, 1446, 1759, 960, 105, 1446, 1446, 1271, 1446, 960, 960, 1218, 1446, 1446, 105, 1446, 960, 488, 1446, 427, 534, 842, 1969, 2460, 1969, 842, 842, 1969, 427, 941, 2160, 427, 230, 938, 2075, 1675, 1675, 895, 1675, 34, 129, 1811, 239, 749, 1957, 2271, 749, 1908, 129, 239, 239, 129, 129, 2271, 2426, 1355, 1756, 194, 1583, 194, 194, 1583, 194, 1355, 194, 1628, 2221, 1269, 2425, 1756, 1355, 1355, 1583, 1033, 427, 582, 30, 582, 582, 935, 1444, 1962, 915, 733, 915, 938, 1962, 767, 353, 1630, 1962, 1962, 563, 733, 563, 733, 353, 822, 1630, 740, 2076, 2076, 2076, 589, 589, 2636, 866, 589, 947, 1528, 125, 273, 1058, 1058, 1161, 1635, 1355, 1161, 1161, 1355, 1355, 650, 1206, 1206, 784, 784, 784, 784, 784, 412, 461, 412, 2240, 412, 679, 891, 461, 679, 679, 189, 189, 1933, 1651, 2515, 189, 1386, 538, 1386, 1386, 1187, 1386, 2423, 2601, 2285, 175, 175, 2331, 194, 3079, 384, 538, 2365, 2294, 538, 2166, 1841, 3326, 1256, 3923, 976, 85, 550, 550, 1295, 863, 863, 550, 1249, 550, 1759, 146, 1069, 920, 2633, 885, 885, 1514, 1489, 166, 1514, 2041, 885, 2456, 885, 2041, 1081, 1948, 362, 550, 94, 324, 2308, 94, 2386, 94, 550, 874, 1329, 1759, 2280, 1487, 493, 493, 2099, 2599, 1431, 1086, 1514, 1086, 2099, 1858, 368, 1330, 2599, 1858, 2846, 2846, 2907, 2846, 713, 713, 1854, 1123, 713, 713, 3010, 1123, 3010, 538, 713, 1123, 447, 822, 555, 2011, 493, 508, 2292, 555, 1736, 2135, 2704, 555, 2814, 555, 2000, 555, 555, 822, 914, 327, 679, 327, 648, 537, 2263, 931, 1496, 537, 1296, 1745, 1592, 1658, 1795, 650, 1592, 1745, 1745, 1658, 1592, 1745, 1592, 1745, 1658, 1338, 2124, 1592, 1745, 1745, 1745, 837, 1726, 2897, 1118, 1118, 230, 1118, 1118, 1118, 1388, 1748, 514, 128, 1165, 931, 514, 2974, 2041, 2387, 2041, 979, 185, 36, 1269, 550, 173, 812, 36, 1165, 2676, 2562, 1473, 2885, 1982, 1578, 1578, 383, 383, 2360, 383, 1578, 2360, 1584, 1982, 1578, 1578, 1578, 2019, 1036, 355, 724, 2023, 205, 303, 355, 1036, 1966, 355, 1036, 401, 401, 401, 830, 401, 849, 578, 401, 849, 849, 578, 1776, 1123, 552, 2632, 808, 1446, 1120, 373, 1529, 1483, 1057, 893, 1284, 1430, 1529, 1529, 2632, 1352, 2063, 1606, 1352, 1606, 2291, 3079, 2291, 1529, 506, 838, 1606, 1606, 1352, 1529, 1529, 1483, 1529, 1606, 1529, 259, 902, 259, 902, 612, 612, 284, 398, 2991, 1534, 1118, 1118, 1118, 1118, 1118, 734, 284, 2224, 398, 734, 284, 734, 398, 3031, 398, 734, 1707, 2643, 1344, 1477, 475, 1818, 194, 1894, 691, 1528, 1184, 1207, 1501, 6, 2069, 871, 2069, 3548, 1443, 2069, 2685, 3265, 1350, 3265, 2069, 2069, 128, 1313, 128, 663, 414, 1313, 414, 2000, 128, 2000, 663, 1313, 699, 1797, 550, 327, 550, 1526, 699, 327, 1797, 1526, 550, 550, 327, 550, 1426, 1426, 1426, 2285, 1123, 890, 728,

1707, 728, 728, 327, 253, 1187, 1281, 1364, 1571, 2170, 755, 3232, 925, 1496, 2170, 2170, 1125, 443, 902, 902, 925, 755, 2078, 2457, 902, 2059, 2170, 1643, 1129, 902, 902, 1643, 1129, 606, 36, 103, 338, 338, 1089, 338, 338, 338, 1089, 338, 36, 340, 1206, 1176, 2041, 833, 1854, 1916, 1916, 1501, 2132, 1736, 3065, 367, 1934, 833, 833, 833, 2041, 3017, 2147, 818, 1397, 828, 2147, 398, 828, 818, 1158, 818, 689, 327, 36, 1745, 2132, 582, 1475, 189, 582, 2132, 1191, 582, 2132, 1176, 1176, 516, 2610, 2230, 2230, 64, 1501, 537, 1501, 173, 2230, 2988, 1501, 2694, 2694, 537, 537, 173, 173, 1501, 537, 64, 173, 173, 64, 2230, 537, 2230, 537, 2230, 2230, 2069, 3142, 1645, 689, 1165, 1165, 1963, 514, 488, 1963, 1145, 235, 1145, 1078, 1145, 231, 2405, 552, 21, 57, 57, 57, 1297, 1455, 1988, 2310, 1885, 2854, 2014, 734, 1705, 734, 2854, 734, 677, 1988, 1660, 734, 677, 734, 677, 677, 734, 2854, 1355, 677, 1397, 2947, 2386, 1698, 128, 1698, 3028, 2386, 2437, 2947, 2386, 2643, 2386, 2804, 1188, 335, 746, 1187, 1187, 861, 2519, 1917, 2842, 1917, 675, 1308, 234, 1917, 314, 314, 2339, 2339, 2592, 2576, 902, 916, 2339, 916, 2339, 916, 2339, 916, 1089, 1089, 2644, 1221, 1221, 2446, 308, 308, 2225, 2225, 3192, 2225, 555, 1592, 1592, 555, 893, 555, 550, 770, 3622, 2291, 2291, 3419, 465, 250, 2842, 2291, 2291, 2291, 935, 160, 1271, 308, 325, 935, 1799, 1799, 1891, 2227, 1799, 1598, 112, 1415, 1840, 2014, 1822, 2014, 677, 1822, 1415, 1415, 1822, 2014, 2386, 2159, 1822, 1415, 1822, 179, 1976, 1033, 179, 1840, 2014, 1415, 1970, 1970, 1501, 563, 563, 563, 462, 563, 1970, 1158, 563, 563, 1541, 1238, 383, 235, 1158, 383, 1278, 383, 1898, 2938, 21, 2938, 1313, 2201, 2059, 423, 2059, 1313, 872, 1313, 2044, 89, 173, 3327, 1660, 2044, 1623, 173, 1114, 1114, 1592, 1868, 1651, 1811, 383, 3469, 1811, 1651, 869, 383, 383, 1651, 1651, 3223, 2166, 3469, 767, 383, 1811, 767, 2323, 3355, 1457, 3341, 2640, 2976, 2323, 3341, 2323, 2640, 103, 103, 1161, 1080, 2429, 370, 2018, 2854, 2429, 2166, 2429, 2094, 2207, 871, 1963, 1963, 2023, 2023, 2336, 663, 2893, 1580, 691, 663, 705, 2046, 2599, 409, 2295, 1118, 2494, 1118, 1950, 549, 2494, 2453, 2046, 2494, 2453, 2046, 2453, 2046, 409, 1118, 4952, 2291, 2225, 1894, 1423, 2498, 567, 4129, 1475, 1501, 795, 463, 2084, 828, 828, 232, 828, 232, 232, 1818, 1818, 666, 463, 232, 220, 220, 2162, 2162, 833, 4336, 913, 35, 913, 21, 2927, 886, 3037, 383, 886, 876, 1747, 383, 916, 916, 916, 2927, 916, 1747, 837, 1894, 717, 423, 481, 1894, 1059, 2262, 3206, 4700, 1059, 3304, 2262, 871, 1831, 871, 3304, 1059, 1158, 1934, 1158, 756, 1511, 41, 978, 1934, 2603, 720, 41, 756, 41, 325, 2611, 1158, 173, 1123, 1934, 1934, 1511, 2045, 2045, 2045, 1423, 3206, 3691, 2512, 3206, 2512, 2000, 1811, 2504, 2504, 2611, 2437, 2437, 2437, 1455, 893, 150, 2665, 1966, 605, 398, 2331, 1177, 516, 1962, 4241, 94, 1252, 760, 1292, 1962, 1373, 2000, 1990, 3684, 42, 1868, 3779, 1811, 1811, 2041, 3010, 5436, 1780, 2041, 1868, 1811, 1780, 1811, 1868, 1811, 2041, 1868, 1811, 5627, 4274, 1811, 1868, 4602, 1811, 1811, 1474, 2665, 235, 1474, 2665

6. Security Considerations

6. 安全考虑

Data delivery can be subject to denial-of-service attacks by attackers that send corrupted packets that are accepted as legitimate by receivers. This is particularly a concern for multicast delivery because a corrupted packet may be injected into the session close to the root of the multicast tree, in which case, the corrupted packet will arrive at many receivers. This is particularly a concern when the code described in this document is used because the use of even one corrupted packet containing encoding data may result in the decoding of an object that is completely corrupted and unusable. It is thus RECOMMENDED that source authentication and integrity checking are applied to decoded objects before delivering objects to an application. For example, a SHA-1 hash [SHA1] of an object may be appended before transmission, and the SHA-1 hash is computed and checked after the object is decoded but before it is delivered to an application. Source authentication SHOULD be provided, for example, by including a digital signature verifiable by the receiver computed on top of the hash value. It is also RECOMMENDED that a packet authentication protocol, such as TESLA [RFC4082], be used to detect and discard corrupted packets upon arrival. This method may also be used to provide source authentication. Furthermore, it is RECOMMENDED that Reverse Path Forwarding checks be enabled in all network routers and switches along the path from the sender to receivers to limit the possibility of a bad agent successfully injecting a corrupted packet into the multicast tree data path.

数据传输可能受到攻击者的拒绝服务攻击，攻击者发送被接收方视为合法的损坏数据包。这对于多播交付来说尤其令人担忧，因为损坏的分组可能被注入到靠近多播树根的会话中，在这种情况下，损坏的分组将到达多个接收机。当使用本文档中描述的代码时，这尤其令人担忧，因为即使使用一个包含编码数据的损坏包也可能导致对完全损坏和不可用的对象进行解码。因此，建议在将对象交付给应用程序之前，对解码对象应用源身份验证和完整性检查。例如，对象的SHA-1散列[SHA1]可以在传输之前被追加，并且在解码对象之后但在将其交付给应用程序之前计算和检查SHA-1散列。应提供源认证，例如，通过包括可由在散列值之上计算的接收器验证的数字签名。还建议使用数据包认证协议（如TESLA[RFC4082]）在到达时检测并丢弃损坏的数据包。此方法也可用于提供源身份验证。此外，建议在从发送方到接收方的路径上的所有网络路由器和交换机中启用反向路径转发检查，以限制坏代理将损坏的数据包成功注入多播树数据路径的可能性。

Another security concern is that some FEC information may be obtained by receivers out-of-band in a session description, and if the session description is forged or corrupted, then the receivers will not use the correct protocol for decoding content from received packets. To avoid these problems, it is RECOMMENDED that measures be taken to prevent receivers from accepting incorrect session descriptions, e.g., by using source authentication to ensure that receivers only accept legitimate session descriptions from authorized senders.

另一个安全问题是，一些FEC信息可能由会话描述中的带外接收器获得，并且如果会话描述是伪造的或损坏的，则接收器将不会使用正确的协议来解码来自所接收分组的内容。为了避免这些问题，建议采取措施防止接收者接受不正确的会话描述，例如，通过使用源身份验证确保接收者只接受来自授权发送者的合法会话描述。

7. IANA Considerations

7. IANA考虑

Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA registration. For general guidelines on IANA considerations as they apply to this document, see [RFC5052]. This document assigns the Fully-Specified FEC Encoding ID 1 under the ietf:rmt:fec:encoding name-space to "Raptor Code".

FEC编码ID和FEC实例ID的值受IANA注册的约束。有关适用于本文件的IANA注意事项的一般指南，请参见[RFC5052]。本文档将ietf:rmt:FEC:Encoding名称空间下完全指定的FEC编码ID 1分配给“Raptor Code”。

8. Acknowledgements

8. 致谢

Numerous editorial improvements and clarifications were made to this specification during the review process within 3GPP. Thanks are due to the members of 3GPP Technical Specification Group SA, Working Group 4, for these.

在3GPP的审查过程中，对本规范进行了大量的编辑改进和澄清。感谢3GPP技术规范小组SA第4工作组的成员所做的这些工作。

9. References

9. 工具书类

9.1. Normative References

9.1. 规范性引用文件

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2119]Bradner，S.，“RFC中用于表示需求水平的关键词”，BCP 14，RFC 2119，1997年3月。

[RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction", RFC 4082, June 2005.

[RFC4082]Perrig，A.，Song，D.，Canetti，R.，Tygar，J.，和B.Briscoe，“定时高效流丢失容忍认证（TESLA）：多播源认证转换介绍”，RFC 40822005年6月。

[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction (FEC) Building Block", RFC 5052, August 2007.

[RFC5052]Watson，M.，Luby，M.，和L.Vicisano，“前向纠错（FEC）构建块”，RFC 5052，2007年8月。

9.2. Informative References

9.2. 资料性引用

[CCNC] Luby, M., Watson, M., Gasiba, T., Stockhammer, T., and W. Xu, "Raptor Codes for Reliable Download Delivery in Wireless Broadcast Systems", CCNC 2006, Las Vegas, NV , Jan 2006.

[CCNC]Luby，M.，Watson，M.，Gasiba，T.，Stockhammer，T.，和W.Xu，“无线广播系统中可靠下载交付的猛禽代码”，CCNC 2006，内华达州拉斯维加斯，2006年1月。

[MBMS] 3GPP, "Multimedia Broadcast/Multicast Service (MBMS); Protocols and codecs", 3GPP TS 26.346 6.1.0, June 2005.

[MBMS]3GPP，“多媒体广播/多播服务（MBMS）；协议和编解码器”，3GPP TS 26.346.1.0，2005年6月。

[RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002.

[RFC3453]Luby，M.，Vicisano，L.，Gemmell，J.，Rizzo，L.，Handley，M.，和J.Crowcroft，“在可靠多播中使用前向纠错（FEC）”，RFC 3453，2002年12月。

[Raptor] Shokrollahi, A., "Raptor Codes", IEEE Transactions on Information Theory no. 6, June 2006.

[Raptor]Shokrollahi，A.，“Raptor代码”，IEEE信息论交易第6期，2006年6月。

[SHA1] "Secure Hash Standard", Federal Information Processing Standards Publication (FIPS PUB) 180-1, April 2005.

[SHA1]“安全哈希标准”，联邦信息处理标准出版物（FIPS PUB）180-12005年4月。

Authors' Addresses

作者地址

Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538 U.S.A.

迈克尔·鲁比数字喷泉美国加利福尼亚州弗里蒙特市市中心大道300号39141室，邮编94538。

   EMail: luby@digitalfountain.com

   EMail: luby@digitalfountain.com

Amin Shokrollahi EPFL Laboratory of Algorithmic Mathematics IC-IIF-ALGO PSE-A Lausanne 1015 Switzerland

Amin Shokrollahi EPFL算法数学实验室IC-IIF-ALGO PSE-A洛桑1015瑞士

   EMail: amin.shokrollahi@epfl.ch

   EMail: amin.shokrollahi@epfl.ch

Mark Watson Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538 U.S.A.

马克·沃森数字喷泉美国加利福尼亚州弗里蒙特市公民中心大道300号39141室，邮编94538。

   EMail: mark@digitalfountain.com

   EMail: mark@digitalfountain.com

Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541 Germany

Thomas Stockhammer Nomor Research Brecherspitzstrasse 8慕尼黑81541德国

   EMail: stockhammer@nomor.de

   EMail: stockhammer@nomor.de

Full Copyright Statement

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

本文件受BCP 78中包含的权利、许可和限制的约束，除其中规定外，作者保留其所有权利。

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

本文件及其包含的信息以“原样”为基础提供，贡献者、他/她所代表或赞助的组织（如有）、互联网协会、IETF信托基金和互联网工程任务组不承担任何明示或暗示的担保，包括但不限于任何保证，即使用本文中的信息不会侵犯任何权利，或对适销性或特定用途适用性的任何默示保证。

Intellectual Property

知识产权

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

IETF对可能声称与本文件所述技术的实施或使用有关的任何知识产权或其他权利的有效性或范围，或此类权利下的任何许可可能或可能不可用的程度，不采取任何立场；它也不表示它已作出任何独立努力来确定任何此类权利。有关RFC文件中权利的程序信息，请参见BCP 78和BCP 79。

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

向IETF秘书处披露的知识产权副本和任何许可证保证，或本规范实施者或用户试图获得使用此类专有权利的一般许可证或许可的结果，可从IETF在线知识产权存储库获取，网址为http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.

IETF邀请任何相关方提请其注意任何版权、专利或专利申请，或其他可能涵盖实施本标准所需技术的专有权利。请将信息发送至IETF的IETF-ipr@ietf.org.