[Search] [txt|pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 rfc2728                                     
IPVBI                                          R. Panabaker, Microsoft
Internet Draft                      S. Wegerif, Philips Semiconductors
                                             D. Zigmond, WebTV Networks
Document: <draft-ietf-ipvbi-nabts-02.txt>                 February 1999

           The Transmission of IP Over the Vertical Blanking Interval
           of a Television Signal

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  Internet-Drafts are
   working documents of the Internet Engineering Task Force (IETF), its
   areas, and its working groups.  Note that other groups may also
   distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other documents
   at any time.  It is inappropriate to use Internet-Drafts as
   reference material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


   To view the entire list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
   Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific
   Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).

   A revised version of this draft document will be submitted to the
   RFC editor as a Proposed Standard for the Internet Community.
   Discussion and suggestions for improvement are requested.  This
   document will expire before August 1999.  Distribution of this draft
   is unlimited.

1. Abstract

   This document describes a method for broadcasting IP data using the
   vertical blanking interval of television signals.  It includes a
   description for compressing IP headers on unidirectional networks, a
   framing protocol identical to SLIP, a forward error correction
   scheme, and the NABTS byte structures.

2. Introduction

   This RFC proposes several protocols to be used in the transmission
   of IP datagrams using the Vertical Blanking Interval (VBI) of a
   television signal.  The VBI is a non-viewable portion of the
   television signal that can be used to provide point-to-multipoint IP
   data services which will relieve congestion and traffic in the

Panabaker                                                            1
                                IPVBI                   February, 1999

   traditional Internet access networks.  Wherever possible these
   protocols make use of existing RFC standards and non-standards.

   Traditionally, point to point connections (TCP/IP) have been used
   even for the transmission of broadcast type data.  Distribution of
   the same content - news feeds, stock quotes, newsgroups, weather
   reports, and the like - are typically sent repeatedly to individual
   clients rather than being broadcast to the large number of users who
   want to receive such data.

   Today, IP is quickly becoming the preferred method of distributing
   one-to-many data on intranets and the Internet. The coming
   availability of low cost PC hardware for receiving television
   signals accompanied by broadcast data streams makes a defined
   standard for the transmission of data over traditional broadcast
   networks imperative.  A lack of standards in this area as well as
   the expense of hardware has prevented traditional broadcast networks
   from becoming effective deliverers of data to the home and office.

   This document describes the transmission of IP using the North
   American Basic Teletext Standard (NABTS), a recognized and industry-
   supported method of transporting data on the VBI.  NABTS is
   traditionally used on 525-line television systems such as NTSC.
   Another byte structure, WST, is traditionally used on 625-line
   systems such as PAL and SECAM.  These generalizations have
   exceptions, and countries should be treated on an individual basis.
   These existing television system standards will enable the
   television and Internet communities to provide inexpensive broadcast
   data services.  A set of existing protocols will be layered above
   the specific FEC for NABTS including a serial stream framing
   protocol similar to SLIP (RFC 1055 [Romkey 1988]) and a compression
   technique for unidirectional UDP/IP headers.

3. Proposed protocol stack

   The following protocol stack demonstrates the layers used in the
   transmission of VBI data.  Each layer has no knowledge of the data
   it encapsulates, and is therefore abstracted from the other layers.
   At the link layer, the NABTS protocol defines the modulation scheme
   used to transport data on the VBI.  At the network layer, IP handles
   the movement of data to the appropriate clients.  In the transport
   layer, UDP determines the flow of data to the appropriate processes
   and applications.

           +-------------------+
           |                   |
           |    Application    |
           |                   |
           +-------------------+
           |                   |  )
           |        UDP        |   )
           |                   |   )

Panabaker                                                            2
                                IPVBI                   February, 1999

           +-------------------+   (-- IP
           |                   |   )
           |        IP         |   )
           |                   |  )
           +-------------------+
           |    SLIP style     |
           |   encapsulation   |
           |                   |
           +-------------------+
           |        FEC        |
           |-------------------|
           |       NABTS       |
           |                   |
           +---------+---------+
           |                   |
           |     NTSC/other    |
           |                   |
           +-------------------+
                     |
                     |
                     |            cable, off-air, etc.
                     |--------<----<----<--------

   These protocols can be described in a bottom up component model
   using the example of NABTS carried over NTSC modulation as follows:

   Video signal --> NABTS --> FEC --> serial data stream --> Framing
   protocol --> compressed UDP/IP headers --> application data

   This diagram can be read as follows: television signals have NABTS
   packets, which contain a Forward Error Correction (FEC) protocol,
   modulated onto them.  The data contained in these sequential,
   ordered packets form a serial data stream on which a framing
   protocol indicates the location of IP packets, with compressed
   headers, containing application data.

   The structure of these components and protocols are described in
   following subsections.

3.1. VBI

   The characteristics and definition of the VBI is dependent on the
   television system in use, be it NTSC, PAL, SECAM or some other.  For
   more information on Television standards worldwide, see ref [12].

3.1.1. 525 line systems

   A 525-line television frame is comprised of two fields of 262.5
   horizontal scan lines each.  The first 21 lines of each field are
   not part of the visible picture and are collectively called the

Panabaker                                                            3
                                IPVBI                   February, 1999

   Vertical Blanking Interval (VBI).  Of these 21 lines, the first 9
   are used while repositioning the cathode ray to the top of the
   screen, but the remaining lines are available for data transport.

   There are 12 possible VBI lines being broadcast 60 times a second
   (each field 30 times a second).  In some countries Line 21 is
   reserved for the transport of closed captioning data (Ref.[11]).  In
   that case, there are 11 possible VBI lines, some or all of which
   could be used for IP transport.  It should be noted that some of
   these lines are sometimes used for existing, proprietary, data and
   testing services. IP delivery therefore becomes one more data
   service using a subset or all of these lines.

3.1.2. 625 Line Systems

   A 625-line television frame is comprised of two fields of 312.5
   horizontal scan lines each.  The first few lines of each field are
   used while repositioning the cathode ray to the top of the screen.
   The lines available for data insertion are 6-22 in the first field
   and 319-335 in the second field.

   There are, therefore, 17 possible VBI lines being broadcast 50 times
   a second (each field 25 times a second), some or all of which could
   be used for IP transport.  It should be noted that some of these
   lines are sometimes used for existing, proprietary, data and testing
   services. IP, therefore, becomes one more data service using a
   subset or all of these lines.

3.2.  NABTS

   The North American Basic Teletext Standard is defined in the
   Electronic Industry Association's EIA-516, Ref. [2], and ITU.R
   BT.653-2, system C, Ref. [13].  It provides an industry-accepted
   method of modulating data onto the VBI, usually of an NTSC signal.
   This section describes the NABTS packet format as it is used for the
   transport of IP.

   It should be noted that only a subset of the NABTS standard is used,
   as is common practice in NABTS implementations.  Further information
   concerning the NABTS standard and its implementation can be found in
   EIA-516.

   The NABTS packet is a 36-byte structure encoded onto one horizontal
   scan line of a television signal having the following structure:

   |Clock|Byte | Packet      |Cont.|Packet   |    User Data      |FEC |
   |Sync |Sync | Address     |Index|Structure|                   |    |
   |     |     |             |     |Flags    |                   |    |
   | 2B  | 1B  |   3B        | 1B  |    1B   |       26B         | 2B |
   |_____|_____|_____________|_____|_________|___________________|____|

Panabaker                                                            4
                                IPVBI                   February, 1999

   The two-byte Clock Synchronization and one-byte Byte Synchronization
   are located at the beginning of every scan line containing a NABTS
   packet and are used to synchronize the decoding sampling rate and
   byte timing.

   The three-byte Packet Address field is Hamming encoded (as specified
   in EIA-516), provides 4 data bits per byte, and thus provides 4096
   possible packet addresses.  These addresses are used to distinguish
   related services originating from the same source.  This is
   necessary for the receiver to determine which packets are related,
   and part of the same service.  NABTS packet addresses therefore
   distinguish different data services, possibly inserted at different
   points of the transmission system, and most likely totally
   unrelated.  Section 4 of this document discusses Packet Addresses in
   detail.

   The one-byte Continuity Index field is a Hamming encoded byte, which
   is incremented by one for each subsequent packet of a given Packet
   Address.  The index number is determined by position of the packet
   in the FEC bundle mentioned in the FEC section of this document.
   The first packet in the bundle has count 0, and the two FEC only
   packets at the end have counts 14 and 15 respectively.  This allows
   the decoder to determine if packets were lost during transmission.

   The Packet Structure field is also a Hamming encoded byte, which
   contains information about the structure of the remaining portions
   of the packet.  The least significant bit is always "0" in this
   implementation.  The second least significant bit specifies if the
   Data Block is full--"0" indicates the data block is full of useful
   data, and "1" indicates some or all of the data is filler data.  The
   two most significant bits are used to indicate the length of the
   suffix of the Data Block--in this implementation, either 2 or 28
   bytes (10 for 2-bit FEC suffix, 11 for 28-byte FEC suffix).  This
   suffix is used for the forward error correction described in the
   next section.  The following table shows the possible values of the
   Packet Structure field:

            Type of Packet                       PS field value
          -------------------------------------------------------
            Data Packet, no filler                     D0
            Data Packet, with filler                   8C
            FEC Packet                                 A1

   The Data Block field is 26 bytes, zero to 26 of which is useful data
   (part of a IP packet or SLIP frame), the remainder is filler data.
   Data is byte-ordered least significant bit first.  Filler data is
   indicated by a 0x15 followed by as many 0xEA as are needed to fill
   the packet.  Sequential data blocks minus the filler data form an
   asynchronous serial stream of data.

   These NABTS packets are modulated onto the television signal
   sequentially and on any combination of lines.

Panabaker                                                            5
                                IPVBI                   February, 1999

3.3. FEC

   Due to the unidirectional nature of VBI data transport, Forward
   Error Correction (FEC) is needed to ensure the integrity of data at
   the receiver.  The type of FEC described here and in the appendix of
   this document for NABTS has been in use for a number of years, and
   has proven popular with the broadcast industry.  It is capable of
   correcting single-byte errors and single- and double-byte erasures
   in the data block and suffix of a NABTS packet.

   In a system using NABTS, the FEC algorithm splits a serial stream of
   data into 364-byte "bundles".  These are arranged as 14 packets of
   26 bytes each.  A function is applied to the 26 bytes of each packet
   to determine the two suffix bytes, which (with the addition of a
   header) complete the NABTS packet (8+26+2).

   For every 14 packets in the bundle, two additional packets are
   appended which contain only FEC data.  That is, they contain 28
   bytes of FEC data.  This data is obtained by first writing the
   packets into a table of 16 rows and 28 columns.  The same expression
   as above can be used on the columns of the table with the suffix now
   represented by the bytes at the base of the columns in rows 15 and
   16.  With NABTS headers on each of these rows, we now have a bundle
   of 16 NABTS packets ready for sequential modulation onto lines of
   the television signal.

   At the receiver, these formulae can be used to verify the validity
   of the data with very high accuracy.  If single bit errors, double
   bit errors, single-byte errors or single- and double-byte erasures
   are found in any row or column (including an entire packet lost)
   they can be corrected using the algorithms found in the appendix.
   The success at correcting errors will depend on the particular
   implementation used on the receiver.

3.4. Framing

   A framing protocol identical to SLIP is proposed for encapsulating
   the packets described in the following section, thus abstracting
   this data from the lower protocol layers.  This protocol uses two
   special characters: END (0xc0) and ESC (0xdb).  To send a packet,
   the host will send the packet followed by the END character.  If a
   data byte in the packet is the same code as END character, a two-
   byte sequence of ESC (0xdb) and 0xdc is sent instead.  If a data
   byte is the same code as ESC character, a two-byte sequence of ESC
   (0xdb) and 0xdd is sent instead.  SLIP implementations are widely
   available, see RFC 1055 [Romkey 1988] for more detail.

   +--------------+--+------------+--+--+---------+--+
   |   packet     |c0|    packet  |db|dd|         |c0|
   +--------------+--+------------+--+--+---------+--+
                   END              ESC            END

Panabaker                                                            6
                                IPVBI                   February, 1999

   The packet framed in this manner shall be formatted according to its
   schema type identified by the schema field, which shall start every
   packet:

   +-----------+---------------------------------------------+
   |  schema   |   packet (formatted according to schema)    |
   |    1B     |             ??B (schema dependant length)   |
   +-----------+---------------------------------------------+

   In the case where the most significant bit in this field
   is set to "1", the length of the field extends to two bytes,
   allowing for 32768 additional schemas:

   +-----------+---------------------------------------------+
   | extended  |   packet (formatted according to schema)    |
   |  schema   |             ??B (schema dependant length)   |
   |    2B     |                                             |
   +-----------+---------------------------------------------+

   In the following section, one such schema for sending IP is
   described.  This is the only schema specified by this document.
   Additional schemas may be proposed for other packet types or other
   compression schemes as described in section 7.

3.5.  IP Header Compression Scheme

   The one-byte scheme defines the format for encoding the IP packet
   itself.  Due to the value of bandwidth, it may be desirable to
   introduce as much efficiency as possible in this encoding.  One such
   efficiency is the optional compression of the UDP/IP header using a
   method similar to the TCP/IP header compression as described by Van
   Jacobson (RFC 1144).  UDP/IP header compression is not identical due
   to the limitation of unidirectional transmission.  One such scheme
   is proposed in this document for the compression of UDP/IP version
   4.  It is assigned a value of 0x00.  All future encapsulation
   schemes should use a unique value in this field.

   Only schema 0x00 is defined in this document; this schema must be
   supported by all receivers.  In schema 0x00, the format of the IP
   packet itself takes one of two forms.  Packets can be sent with
   full, uncompressed headers as follows:

   +----+-------+----------------+---------------+-----------+--------+
   |  0 | Group |   IP Header    |  UDP Header   |  Payload  |  CRC   |
   | 1b |   7b  |      20B       |      8B       |   <1472B  |   4B   |
   |    |       | (uncompressed) | (uncompressed)|           |        |
   +----+-------+----------------+---------------+-----------+--------+

   The first byte in the 0x00 scheme is the Compression Key.  It is a
   one-byte value: the first bit indicates if the header has been
   compressed, and the remaining seven bits indicate the compression

Panabaker                                                            7
                                IPVBI                   February, 1999

   group it belongs to.  If the high bit of the Compression Key is set
   to "0", no compression is performed and the full header is sent, as
   shown above.  The client VBI interface should store the uncompressed
   header for future potential use in rebuilding subsequent compressed
   headers.  Packets with identical group bits are assumed to have
   identical UDP/IP headers, with the exception of the "IP
   identification" and "UDP checksum" fields.

   If the high bit of the Compression Key is set to 1, a compressed
   version of the UDP/IP header is sent.  The client VBI interface must
   then combine the compressed header with the stored uncompressed
   header of the same group and recreate a full packet.  For compressed
   packets, the only portions of the UDP/IP header sent are the "IP
   identification" and "UDP checksum" fields:

   +----+-------+----------------+---------------+-----------+--------+
   |  1 | Group |      IP        | UDP checksum  |  Payload  |  CRC   |
   | 1b |   7b  | identification |      4B       |   <1472B  |   4B   |
   |    |       |      4B        |               |           |        |
   +----+-------+----------------+---------------+-----------+--------+

   All datagrams belonging to a multi fragment IP packet shall be sent
   with full headers, in the uncompressed header format.  Therefore,
   only packets that have not been fragmented can be sent with the most
   significant bit of the compression key set to "1".

   A 32-bit CRC has also been added to the end of every packet in this
   scheme to ensure data integrity.  It is performed over the entire
   packet including schema byte, compression key, and either compressed
   or uncompressed headers.  It uses the same algorithm as the MPEG-2
   transport stream (ISO/IEC 13818-1).  The generator polynomial is:

   1 + D + D2 + D4 + D5 + D7 + D8 + D10 + D11 + D12 + D16 + D22 + D23 +
   D26 + D32

   As in the ISO/IEC 13818-1 specification, the initial state of the
   sum is 0xFFFFFFFF.  This is not the same algorithm used by Ethernet.
   This CRC provides a final check for damaged datagrams that spanned
   FEC bundles or were not properly corrected by FEC.

4. Addressing Considerations

   The addressing of IP packets should adhere to existing standards in
   this area.  The inclusion of an appropriate source address is needed
   to ensure the receiving client can distinguish between sources and
   thus services if multiple hosts are sharing an insertion point and
   NABTS packet address.

   NABTS packet addressing is not regulated or standardized and
   requires care to ensure that unrelated services on the same channel
   are not broadcasting with the same packet address.  This could occur
   due to multiple possible NABTS insertion sites, including show

Panabaker                                                            8
                                IPVBI                   February, 1999

   production, network redistribution, regional operator, and local
   operator.  Traditionally, the marketplace has recognized this
   concern and made amicable arrangements for the distribution of these
   addresses for each channel.

5. IANA Considerations

   IANA will register new schemes for header compression on a "First
   Come First Served" basis [RFC 2434].  Anyone can register a scheme,
   so long as they provide a point of contact and a brief description.
   The scheme number will be assigned by IANA.  Registrants are
   encouraged to publish complete specifications for new schemes
   (preferably as standards-track RFCs), but this is not required.

6. Security considerations

   As with any broadcast network, there are security issues due to the
   accessibility of data.  It is assumed that the responsibility for
   securing data lies in the application layer protocol, which is
   beyond the scope of this document.

7. Conclusions

   This document provides a method for broadcasting Internet data over
   a television signal for reception by client devices.  With an
   appropriate broadcast content model, this will become an attractive
   method of providing data services to end users.  By using existing
   standards and a layered protocol approach, this document has also
   provided a model for data transmission on unidirectional and
   broadcast networks.

8. Acknowledgements

   The description of the FEC in Appendix A is taken from a document
   prepared by Trevor Dee of Norpak Corporation.

9. References

   [1] Deering, S. E. 1989.  "Host Extensions for IP Multicasting," RFC
   1112, 17 pages (Aug.).

   [2] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext:
   North American Basic Teletext Specification (NABTS)" Washington:
   Electronic Industries Association, c1988

   [3] Jack, Keith. "Video Demystified: A Handbook for the Digital
   Engineer, Second Edition," San Diego: HighText Pub.  c1996.

Panabaker                                                            9
                                IPVBI                   February, 1999

   [4] Jacobson, V.  1990a.  "Compressing TCP/IP Headers for Low-Speed
   Serial Links," RFC 1144, 43 pages (Feb.).

   [5] Narten, T. Alvestrand, H. 1998.  "Guidelines for Writing an IANA
   Considerations Section in RFCs," RFC 2434, (Oct.).

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

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

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

   [9] Romkey, J. L.  1988.  "A Nonstandard for Transmission of IP
   Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June).

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

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

   [12] International Telecommunications Union Recommendation.
   ITU-R BT.470-5 (02/98) "Conventional TV Systems"

   [13] International Telecommunications Union Recommendation.
   ITU.R BT.653-2, system C

10. Acronyms

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

11. Editors' address and contacts

   Ruston Panabaker, co-editor
   Microsoft

Panabaker                                                           10
                                IPVBI                   February, 1999

   One Microsoft Way
   Redmond, WA  98052
   i-rustop@microsoft.com

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

   Dan Zigmond, WG Chair
   WebTV Networks
   One Microsoft Way
   Redmond, WA 98052
   djz@corp.webtv.net

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 in to 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.

Panabaker                                                           11
                                IPVBI                   February, 1999

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

   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]]];
              }
            }

Panabaker                                                           12
                                IPVBI                   February, 1999

   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
   tot1 and tot2.

      Sum0=0=tot0^power[0+alog[codeword[0]]]^power[1+alog[codeword[1]]]
      sum1=0=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:

        for(i = 0;i < 16;i++)
          {
          Sum0 = 0;
          Sum1 = 0;
          for(j = 0;j < hor;j++)
            {
            If(codeword[i][j] != 0)
              {

Panabaker                                                           13
                                IPVBI                   February, 1999

              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.

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]]];
     if(Byte & 1)

Panabaker                                                           14
                                IPVBI                   February, 1999

       Byte = Byte + 255;
     Byte = Byte >> 1;
     Bit = alog[power[255 + alog[sum0] - Byte]] << 3;
     while(Bit > 255)
       Bit = Bit - 255;

   The error is correctable if Byte is less than the number of bytes in
   the codeword and Bit is less than eight.  For this math to be valid
   both sum0 and sum1 must be non-zero.  The codeword is corrected by:

     codeword[Byte] = codeword[Byte] ^ (1 << Bit);

12.4.2. Double Bit Correction

   Double bit correction is much more complex than single bit
   correction for two reasons.  First, not all double bit errors are
   deterministic.  That is two different bit patterns can generate the
   same sums.  Second, the solution is iterative.  To find two bit
   errors you assume one bit in error and then solve for the second
   error as a single bit error.

   The procedure is to iteratively move through the bits of the
   codeword changing each bit's state.  The new sums are calculated for
   the modified codeword. Then the single bit calculation above
   determines if this is the correct solution.  If not, the bit is
   restored and the next bit is tried.

   For a long codeword, this can involve many calculations.  However,
   tricks can speed the process.  For example, the vertical sums give a
   strong indication of which bytes are in error horizontally.  Bits in
   other bytes need not be tried.

12.4.3. Single Byte Correction

   For single byte correction, the byte position and bits to correct
   must be calculated.  The equations are:

     Byte = 1/2*LOGalpha(S1/S0)
     Mask = S0/POWERalpha[Byte]

   Notice that the byte position is the same calculation as for single
   bit correction.  The mask will allow more than one bit in the byte
   to be corrected.  In "C" the mask calculation looks like:

     Mask = power[255 + alog[sum0] - Byte]

   Both sum0 and sum1 must be non-zero for the calculations to be
   valid.  The Byte value must be less than the codeword length but
   Mask can be any value.  This corrects the byte in the codeword by:

     Codeword[Byte] = Codeword[Byte] ^ Mask

Panabaker                                                           15
                                IPVBI                   February, 1999

12.4.4. Packet Replacement

   If a packet is missing, as determined by the continuity index, then
   its byte position is known and does not need to be calculated.  The
   formula for single packet replacement is therefore the same as for
   the Mask calculation of single byte correction.  Instead of XORing
   an existing byte with the Mask, the Mask replaces the missing
   codeword position:

     Codeword[Byte] = Mask

   When two packets are missing, both the codeword positions are known
   by the continuity index.  This again gives two equations with two
   unknowns, which is solved to give the following equations.

     Mask2 = POWERalpha(2*Byte1)*S0+S1
             -------------------------------
             POWERalpha(2*Byte1+Byte2) +POWERalpha(3*BYTE2)

     Mask1 = S0 + Mask2*POWERalpha(Byte2)/POWERalpha(BYTE1)

   In "C" these equations are written:

   if(sum0 == 0)
     {
     if(sum1 == 0)
      mask2 = 0;
     else
      mask2=power[255+alog[sum1]-alog[power[byte2+2*byte1]^
            power[3*Byte2]]];
     }
    else
     {
     if((a=sum1^power[alog[sum0]+2*byte1]) == 0)
      mask2 = 0;
     else
      mask2 = power[255+alog[a]-alog[power[byte2+2*byte1]^
              power[3*byte2]]];
     }
     if(mask2 = 0)
     {
     if(sum0 == 0)
      mask1 = 0;
     else
      mask1 = power[255+alog[sum0]-byte1];
     }
    else
     {
     if((a=sum0^power[alog[mask2] + byte2]) == 0)
      mask1 = 0;
     else

Panabaker                                                           16
                                IPVBI                   February, 1999

      mask1 = power[255+alog[a]-byte1];
     }

   Notice that, in the code above, care is taken to check for zero
   values.  The missing codeword position can be fixed by:

     codeword[byte1] = mask1;
     codeword[byte2] = mask2;

12.5. FEC Performance Considerations

   The section above shows how to correct the different types of
   errors.  It does not suggest how these corrections may be used in an
   algorithm to correct a bundle.  There are many possible algorithms
   and the one chosen depends on many variables.  These include:

      . The amount of processing power available.
      . The number of packets per VBI to process.
      . The type of hardware capturing the data.
      . The delivery path of the VBI.
      . How the code is implemented.

   As a minimum, it is recommended that the algorithm use single bit or
   single byte correction for one pass in each direction followed by
   packet replacement if appropriate.  It is possible to do more than
   one pass of error correction in each direction.  The theory is that
   errors not corrected in the first pass may be corrected in the
   second pass because error correction in the other direction has
   removed some errors.

   In making choices, it is important to remember that the code has
   several possible states:

   1)Shows codeword as correct and it is.
   2)Shows codeword as correct and it is not (detection failure).
   3)Shows codeword as incorrect but cannot correct (detection).
   4)Shows codeword as incorrect and corrects it correctly
   (correction).
   5)Shows codeword as incorrect but corrects wrong bits (false
   correction).

   There is actually overlap among the different types of errors.  For
   example, a pair of sums may indicate both a double bit error and a
   byte error.  It is not possible to know at the code level which is
   correct and which is a false correction.  In fact, neither might be
   correct if both are false corrections.

   If you know something about the types of errors in the delivery
   channel, you can greatly improve efficiency.  If you know that
   errors are randomly distributed (as in a weak terrestrial broadcast)
   then single and double bit correction are more powerful than single
   byte.

Panabaker                                                           17
                                IPVBI                   February, 1999

12.6. Appendix References

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

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

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

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

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

   [6] Mortimer, Brian.  "An Error-correction system for the Teletext
   Transmission in the Case of Transparent Data" c1989 Department of
   Mathematics and Statistics, Carleton University, Ottawa Canada

13. Appendix B: Architecture

   The architecture that this document is addressing can be broken down
   into three areas: insertion, distribution network, and receiving
   client.

   The insertion of IP data onto the television signal can occur at any
   part of the delivery system.  A VBI encoder typically accepts a
   video signal and an asynchronous serial stream of framed IP as
   inputs and packetizes the data onto a selected set of lines using
   NABTS and an FEC.  This composite signal is then modulated with
   other channels before being broadcast onto the distribution network.
   Operators further down the distribution chain could then add their
   own data, to other unused lines, as well.

   The distribution networks include coax plant, off-air, and analog
   satellite systems and are primarily unidirectional broadcast
   networks.  They must provide a signal to noise ratio, which is
   sufficient for FEC to recover any lost data for the broadcast of
   data to be effective.

   The receiving client must be capable of tuning, NABTS waveform
   sampling as appropriate, filtering on NABTS addresses as
   appropriate, forward error correction, unframing, verification of
   the CRC and decompressing the UDP/IP header if they are compressed.
   All of the above functions can be carried out in PC software and
   inexpensive off-the-shelf hardware.

Panabaker                                                           18
                                IPVBI                   February, 1999

14. Appendix C: Scope of proposed protocols

   The protocols described in this document are for transmitting IP
   packets.  However, their scope may be extensible to other
   applications outside this area.  Many of the protocols in this
   document could be implemented on any unidirectional network.

   The unidirectional framing protocol provides encapsulation of IP
   datagrams on the serial stream, and the compression of the UDP/IP
   headers reduces the overhead on transmission, thus conserving
   bandwidth.  These two protocols could be widely used on different
   unidirectional broadcast networks or modulation schemes to
   efficiently transport any type of packet data.  In particular, new
   versions of Internet protocols can be supported to provide a
   standardized method of data transport.

Panabaker                                                           19