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

Versions: 00 01 02 03 04 05 rfc2728                                     
INTERNET-DRAFT                                         IPVBI WG editors
< draft-ietf-ipvbi-nabts-00.txt >
Obsoletes:
< draft-ietf-ipvbi-tv-signal-00.txt >                          Oct 1998
Expires in six months



    THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A
                        TELEVISION SIGNAL

1. Status of this Memo

This document is an Internet-Draft of the IPVBI working group.
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."

To learn the current status of any Internet-Draft, please check the
"id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
ftp.isi.deu (US West Coast).

2. Abstract

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

Keywords: VBI, broadcast, push, FEC, television, NABTS, IP, multicast.

3. Table of Contents

1.    Status of this Memo . . . . . . . . . . . . . . . . . . . . . . 1
2.    Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
3.    Table of Contents . . . . . . . . . . . . . . . . . . . . . . . 1
4.    Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .2
5.    Proposed protocol stack . . . . . . . . . . . . . . . . . . . . 2
5.1.     VBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
5.1.1.     525 line systems. . . . . . . . . . . . . . . . . . . . . .4
5.2.     NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
5.3.     FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
5.4.     Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .6
5.5.     IP compression . . . . . . . . . . . . . . . . . . . . . . . 6
6.   Addressing Considerations . . . . . . . . . . . . . . . . . . . .7
7.   Security considerations . . . . . . . . . . . . . . . . . . . . .8
8.   Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . .8
9.   References . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
10.  Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

IPVBI                                                          [Page 1]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998

11.  Author's address and contacts . . . . . . . . . . . . . . . . . .9
12.  Appendix A: Forward Error Correction Specification  . . . . . . 10
12.1.    Mathematics used in the FEC . . . . . . . . . . . . . . . . 10
12.2.    Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 11
12.3.    Correcting Errors . . . . . . . . . . . . . . . . . . . . . 11
12.4.    Correction Schemes . . . . . . . . . . . . . . . . . . . . .13
12.5     FEC Performance Considerations. . . .  . . . . . . . . . . .15
12.6.    Appendix References . . . . . . . . . . . . . . . . . . . . 16
15.   Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 16
16.   Scope of proposed protocols . . . . . . . . . . . . . . . . .  17

4. Introduction

This Internet-Draft 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
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, multicast-IP is quickly becoming the preferred method of
distributing one-to-many data on Intranets and the Internet.  With the
coming availability of low cost PC hardware for receiving television
signals accompanied by broadcast data streams, it is imperative that a
standard be defined for the transmission of data over traditional
broadcast networks.  A lack of standards in this area as well as the
expense of hardware has, in the past, prevented traditional broadcast
networks from becoming effective deliverers of data to the home and
office.

This document describes the transmission of multicast-IP using the
North American Basic Teletext Standard (NABTS) a recognized and
industry-supported method of transporting data on the VBI.  NABTS has
traditionally been used on 525 line television systems such as NTSC,
and another byte structure, WST, on 625 line systems such as PAL and
SECAM, but this generalization has exceptions, and countries should be
treated on an individual basis. These existing television system
standards will allow 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 multicast UDP/IP headers.


5. Proposed protocol stack

IPVBI                                                          [Page 2]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998


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 and UDP, in the transport
layer, determines the flow of data to the appropriate processes and
applications.

        +-------------------+
        |                   |
        |    Application    |
        |                   |
        +-------------------+
        |                   |  )
        |        UDP        |   )
        |                   |   )
        +-------------------+   (-- multicast-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:

NTSC 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 modulated onto them which contain a Forward Error Correction
(FEC) protocol.  The data contained in these sequential, ordered
packets form a serial data stream on which a framing protocol indicates

IPVBI                                                          [Page 3]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998

 the location of multicast-IP packets, with compressed headers,
containing application data.

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

5.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 [11].

5.1.1. 525 line systems (example: NTSC)

An NTSC television frame is comprised of 2 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 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.

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

5.2.  NABTS

The North American Basic Teletext Standard is defined in the
Electronics Industry Associations EIA-516.  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 multicast 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 group|Cont.|Packet   |    User Data      |FEC |
|Sync |Sync     | Address     |Index|Structure|                   |    |
|     |     |             |     |Flags    |                   |    |
| 2B  | 1B  |   3B        | 1B  |    1B   |       26B         | 2B |
|_____|_____|_____________|_____|_________|___________________|____|


The 2 byte Clock Synchronization and the 1 byte Byte Synchronization
are located at the beginning of every scan line containing a NABTS

IPVBI                                                          [Page 4]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998

packet and are used to synchronize the decoding sampling rate and byte
timing.

The 3 byte Packet Group address field is Hamming encoded (as specified
in EIA-516, and provides 4 data bits per byte, and thus provides 4096
possible packet group 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 group addresses therefore
distinguish different data services, possibly inserted at different
points of the transmission system, and most likely totally unrelated.
Section 6 of this document discusses Packet Group Addresses in greater
detail.

The 1 byte Continuity Index field is a Hamming encoded byte, which is
incremented by one for each subsequent packet of a given Packet Group
address.  The index number is determined by the packet's order 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 have been 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 whether the
Data Block is full (0 indicates the data block is full of useful data,
1 indicates some or all of the data is filler data), and the two most
significant bits are used to indicate the length of the suffix on 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 Data Block field is 26 bytes, 0 to 26 of which is useful data (part
of a multicast IP packet or SLIP frame), the remainder being 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.

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

IPVBI                                                          [Page 5]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998

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 an additional 2 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 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.

5.4. Framing

A framing protocol identical to SLIP is proposed for encapsulating IP
datagrams, 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.

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

5.5.    IP compression

Finally we have the multicast IP packet (RFC 1112 [Deering 1989]).  Due
to the value of bandwidth, it may be desirable to introduce as much
efficiency as possible.  One such efficiency is the optional
compression of the multicast 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.

The following two packet formats are used in a compression scheme which
builds index tables on the client using occasionally transmitted full
headers to rebuild packets sent with compressed headers:

[schema:8][0:1][Index:7][full headers:224][data][CRC:32]

IPVBI                                                          [Page 6]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



[schema:8][1:1][Index:7][compressed header:32][data][CRC:32]

The first byte of all packets is the schema type.  This field is used
to identify the compression scheme that is being used.  One such scheme
is proposed in this document for the compression of UDP/IP version 4.
It is assigned a value of 00000000.  All future encapsulation schemes
should use a unique value in this field.  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.

The next byte in the 00000000 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 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. The client VBI
interface should store the uncompressed header for future potential use
in rebuilding subsequent compressed headers.

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
and recreate a full packet.

When uncompressed, the entire UDP/IP header is sent.  When compressed,
only the "IP identification", and “UDP checksum” fields are sent.  The
client VBI interface should combine these with the previously saved
header.

[0:1][Group:7][IP header:160][UDP header:64]
[1:1][Group:7][IP identification:16][UDP checksum:16]

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, which spanned FEC
bundles or were not corrected properly by FEC.

6. Addressing Considerations

IPVBI                                                          [Page 7]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



The addressing of multicast 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 group 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 group address.  This could occur due
to multiple possible NABTS insertion sites, including show 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.

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

8. Conclusions

This document provides a method for broadcasting Internet data over a
television signal for reception by client devices.  With an appropriate
"push and filter" 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.

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.

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

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

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

IPVBI                                                          [Page 8]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



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

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

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

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

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

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         - Japanese flavor of NTSC
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. Author's address and contacts

Ruston Panabaker, co-editor
Microsoft
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
305 Lytton Avenue
Palo Alto, CA 94301

IPVBI                                                          [Page 9]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998


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

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:

IPVBI                                                         [Page 10]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



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

IPVBI                                                         [Page 11]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



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 whether 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)
           {
           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++)
         {

IPVBI                                                         [Page 12]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998


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

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

IPVBI                                                         [Page 13]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998



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 a lot of calculations.  There are
tricks that can be used to 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/2LOGalpha(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

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)


IPVBI                                                         [Page 14]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998


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
   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 has not suggested 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.


IPVBI                                                         [Page 15]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998


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.

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

The architecture that this document is addressing can be broken down

IPVBI                                                         [Page 16]


< draft-ietf-ipvbi-nabts-00.txt >                              Oct 1998

into 3 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 group 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.

14. Scope of proposed protocols

The protocols described in this document are for the purpose of
transmitting multicast 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 multicast
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.




                                     END









IPVBI                                                         [Page 17]

 see comment above concerning standardizing this
 This has to be checked