rfc2728.txt

<VC++网络游戏建摸与实现>源代码

   [10] Norpak Corporation "TTX71x Programming Reference Manual", c1996,
        Kanata, Ontario, Canada

   [11] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder
        Software User's Manual." c1996, Kanata, Ontario, Canada

   [12] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata,
        Ontario, Canada

   [13] Pretzel, Oliver. "Correcting Codes and Finite Fields: Student
        Edition" OUP, c1996

   [14] Rorabaugh, C. Britton.  "Error Coding Cookbook" McGraw Hill,
        c1996

   [15] Romkey, J., "A Nonstandard for Transmission of IP Datagrams Over
        Serial Lines: SLIP", STD 47, RFC 1055, June 1988.

   [16] Recommended Practice for Line 21 Data Service (ANSI/EIA-608-94)
        (Sept., 1994)

   [17] Stevens, W. Richard.  "TCP/IP Illustrated, Volume 1,: The
        Protocols"  Reading: Addison-Wesley Publishing Company, c1994.




Panabaker, et al.           Standards Track                    [Page 12]

RFC 2728                         IPVBI                     November 1999


10. Acronyms

   FEC            - Forward Error Correction
   IP             - Internet Protocol
   NABTS          - North American Basic Teletext Standard
   NTSC           - National Television Standards Committee
   NTSC-J         - NTSC-Japanese
   PAL            - Phase Alternation Line
   RFC            - Request for Comments
   SECAM          - Sequentiel Couleur Avec Memoire
                    (sequential color with memory)
   SLIP           - Serial Line Internet Protocol
   TCP            - Transmission Control Protocol
   UDP            - User Datagram Protocol
   VBI            - Vertical Blanking Interval
   WST            - World System Teletext

11. Editors' Addresses and Contacts

   Ruston Panabaker, co-editor
   Microsoft
   One Microsoft Way Redmond, WA 98052

   EMail: [e-mail]


   Simon Wegerif, co-editor
   Philips Semiconductors
   811 E. Arques Avenue
   M/S 52, P.O. Box 3409 Sunnyvale, CA 94088-3409

   EMail: [e-mail]


   Dan Zigmond, WG Chair
   WebTV Networks
   One Microsoft Way Redmond, WA 98052

   EMail: [e-mail]












Panabaker, et al.           Standards Track                    [Page 13]

RFC 2728                         IPVBI                     November 1999


12. Appendix A: Forward Error Correction Specification

   This FEC is optimized for data carried in the VBI of a television
   signal.  Teletext has been in use for many years and data
   transmission errors have been categorized into three main types: 1)
   Randomly distributed single bit errors 2) Loss of lines of NABTS data
   3) Burst Errors

   The quantity and distribution of these errors is highly variable and
   dependent on many factors.  The FEC is designed to fix all these
   types of errors.

12.1. Mathematics used in the FEC

   Galois fields form the basis for the FEC algorithm presented here.
   Rather then explain these fields in general, a specific explanation
   is given of the Galois field used in the FEC algorithm.

   The Galois field used is GF(2^8) with a primitive element alpha of
   00011101.  This is a set of 256 elements, along with the operations
   of "addition", "subtraction", "division", and "multiplication" on
   these elements.  An 8-bit binary number represents each element.

   The operations of "addition" and "subtraction" are the same for this
   Galois field.  Both operations are the XOR of two elements.  Thus,
   the "sum" of 00011011 and 00000111 is 00011100.

   Division of two elements is done using long division with subtraction
   operations replaced by XOR.  For multiplication, standard long
   multiplication is used but with the final addition stage replaced
   with XOR.

   All arithmetic in the following FEC is done modulo 100011101; for
   instance, after you multiply two numbers, you replace the result with
   its remainder when divided by 100011101.  There are 256 values in
   this field (256 possible remainders), the 8-bit numbers.  It is very
   important to remember that when we write A*B = C, we more accurately
   imply modulo(A*B) = C.

   It is obvious from the above description that multiplication and
   division is time consuming to perform.  Elements of the Galois Field
   share two important properties with real numbers.

   A*B = POWERalpha(LOGalpha(A) + LOGalpha(B))
   A/B = POWERalpha(LOGalpha(A) - LOGalpha(B))






Panabaker, et al.           Standards Track                    [Page 14]

RFC 2728                         IPVBI                     November 1999


   The Galois Field is limited to 256 entries so the power and log
   tables are limited to 256 entries.  The addition and subtraction
   shown is standard so the result must be modulo alpha.  Written as a
   "C" expression:

   A*B = apower[alog[A] + alog[B]]
   A/B = apower[255 + alog[A] - alog[B]]

   You may note that alog[A] + alog[B] can be greater than 255 and
   therefore a modulo operation should be performed.  This is not
   necessary if the power table is extended to 512 entries by repeating
   the table.  The same logic is true for division as shown.  The power
   and log tables are calculated once using the long multiplication
   shown above.

12.2. Calculating FEC bytes

   The FEC algorithm splits a serial stream of data into "bundles".
   These are arranged as 16 packets of 28 bytes when the correction
   bytes are included.  The bundle therefore has 16 horizontal codewords
   interleaved with 28 vertical codewords.  Two sums are calculated for
   a codeword, S0 and S1.  S0 is the sum of all bytes of the codeword
   each multiplied by alpha to the power of its index in the codeword.
   S1 is the sum of all bytes of the codeword each multiplied by alpha
   to the power of three times its index in the codeword.  In "C" the
   sum calculations would look like:

   Sum0 = 0;
      Sum1 = 0;
      For (i = 0;i < m;i++)
      {
         if (codeword[i] != 0)
         {
            Sum0 = sum0 ^ power[i + alog[codeword[i]]];
            Sum1 = sum1 ^ power[3*i + alog[codeword[i]]];
            }
         }


   Note that the codeword order is different from the packet order.
   Codeword positions 0 and 1 are the suffix bytes at the end of a
   packet horizontally or at the end of a column vertically.

   When calculating the two FEC bytes, the summation above must produce
   two sums of zero.  All codewords except 0 and 1 are know so the sums
   for the known codewords can be calculated.  Let's call these values
   tot0 and tot1.




Panabaker, et al.           Standards Track                    [Page 15]

RFC 2728                         IPVBI                     November 1999


   Sum0 = tot0^power[0+alog[codeword[0]]]^power[1+alog[codeword[1]]]
   Sum1 = tot1^power[0+alog[codeword[0]]]^power[3+alog[codeword[1]]]

   This gives us two equations with the two unknowns that we can solve:

   codeword[1] = power[255+alog[tot0^tot1]-alog[power[1]^power[3]]]
   codeword[0] = tot0^power[alog[codeword[1]]+alog[power[1]]]

12.3. Correcting Errors

   This section describes the procedure for detecting and correcting
   errors using the FEC data calculated above.  Upon reception, we begin
   by rebuilding the bundle.  This is perhaps the most important part of
   the procedure because if the bundle is not built correctly it cannot
   possibly correct any errors.  The continuity index is used to
   determine the order of the packets and if any packets are missing
   (not captured by the hardware).  The recommendation, when building
   the bundle, is to convert the bundle from packet order to codeword
   order.  This conversion will simplify the codeword calculations. This
   is done by taking the last byte of a packet and making it the second
   byte of the codeword and taking the second last byte of a packet and
   making it the first byte of a codeword.  Also the packet with
   continuity index 15 becomes codeword position one and the packet with
   continuity index 14 becomes codeword position zero.  The same FEC is
   used regardless of the number of bytes in the codeword.  So let's
   think of the codewords as an array codeword[vert][hor] where vert is
   16 packets and hor is 28.  Each byte in the array is protected by
   both a horizontal and a vertical codeword.  For each of the
   codewords, the sums must be calculated. If both the sums for a
   codeword are zero then no errors have been detected for that
   codeword.  Otherwise, an error has been detected and further steps
   need to be taken to see if the error can be corrected.  In "C" the
   horizontal summation would look like:


















Panabaker, et al.           Standards Track                    [Page 16]

RFC 2728                         IPVBI                     November 1999


   for (i = 0; i < 16; i++)
   {
      sum0 = 0;
      sum1 = 0;
      for (j = 0;j < hor;j++)
      {
         if (codeword[i][j] != 0)
         {
            sum0 = sum0 ^ power[j + alog[codeword[i][j]];
            sum1 = sum1 ^ power[3*j + alog[codeword[i][j]];
         }
      }
      if ((sum0 != 0) || (sum1 != 0))
      {
         Try Correcting Packet
      }
   }

   Similarly, vertical looks like:

   for (j = 0;i < hor;i++)
   {
      sum0 = 0;
      sum1 = 0;
      for (i = 0;i < 16;i++)
      {
         if (codeword[i][j] != 0)
         {
            sum0 = sum0 ^ power[i + alog[codeword[i][j]];
            sum1 = sum1 ^ power[3*i + alog[codeword[i][j]];
         }
      }
      if ((sum0 != 0) || (sum1 != 0))
      {
         Try Correcting Column
      }
   }

12.4. Correction Schemes

   This FEC provides four possible corrections:
   1)    Single bit correction in codeword.  All single bit errors.
   2)    Double bit correction in a codeword.  Most two-bit errors.
   3)    Single byte correction in a codeword.  All single-byte errors.
   4)    Packet replacement.  One or two missing packets from a bundle.






Panabaker, et al.           Standards Track                    [Page 17]

RFC 2728                         IPVBI                     November 1999


12.4.1. Single Bit Correction

   When correcting a single-bit in a codeword, the byte and bit position
   must be calculated.  The equations are:

   Byte = 1/2LOGalpha(S1/S0)
   Bit  = 8LOGalpha(S0/POWERalpha(Byte))

   In "C" this is written:

   Byte = alog[power[255 + alog[sum1] - alog[sum0]]];