Internet DRAFT - draft-ietf-ipvbi-tv-signal
draft-ietf-ipvbi-tv-signal
INTERNET-DRAFT IPVBI WG editors
< draft-ietf-ipvbi-tv-signal-00.txt >
Obsoletes:
< draft-panabaker-ietf-ipvbi-tv-signal-02.txt > June 1998
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 and WST byte structures to ensure support on NTSC, PAL, SECAM, and other television systems.
Keywords: VBI, NTSC, PAL, broadcast, push, FEC, television, NABTS, WST, 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 . . . . . . . . . . . . . . . . . . . . 3
5.1. VBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
5.1.1. 525 line systems. . . . . . . . . . . . . . . . . . . . . .4
5.1.2. 625 line systems . . . . . . . . . . . . . . . . . . . . .4
5.2. Line Coding . . . . . . . . . . . . . . . . . . . . . . . . .5
5.2.1. NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . .5
5.2.2. WST . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
5.3. FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
5.3.1. FEC use in NABTS . . . . . . . . . . . . . . . . . . . . . 8
IPVBI [Page 1]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
5.3.2. FEC use in WST . . . . . . . . . . . . . . . . . . . . . . 9
5.4. Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .9
5.5. IP compression . . . . . . . . . . . . . . . . . . . . . . . 9
6. Addressing Considerations . . . . . . . . . . . . . . . . . . . 11
7. Security considerations . . . . . . . . . . . . . . . . . . . . 11
8. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . .11
10. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
11. Author's address and contacts . . . . . . . . . . . . . . . . . 13
12. Appendix A: Forward Error Correction Specification . . . . . . 13
12.1. Mathematics used in the FEC . . . . . . . . . . . . . . . . 13
12.2. Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 14
12.3. Correcting Errors . . . . . . . . . . . . . . . . . . . . . 15
12.4. Correction Schemes . . . . . . . . . . . . . . . . . . . . .16
12.5 FEC Performance Considerations. . . . . . . . . . . . . . .19
12.6. Appendix References . . . . . . . . . . . . . . . . . . . . 18
13. Performance analysis . . . . . . . . . . . . . . . . . . . . . 20
14. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 20
15. Scope of proposed protocols . . . . . . . . . . . . . . . . . 21
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 both the North American Basic Teletext Standard (NABTS), and World System Teletext (WST), recognized and industry supported methods of transporting data on the VBI. NABTS has traditionally been used on 525 line television systems such as NTSC, and 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
IPVBI [Page 2]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
system standards will allow the television and Internet communities to provide inexpensive broadcast data services. An identical set of protocols will be layered above the specific FECs for NABTS and WST including a serial stream framing protocol similar to SLIP (RFC 1055 [Romkey 1988]) and a Van Jacobson style compression technique (RFC 1144) for unidirectional multicast UDP/IP headers.
5. 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 or WST 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 | FEC |
|---------|---------|
| NABTS | WST |
| | |
+---------+---------+
| |
| NTSC/PAL/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:
IPVBI [Page 3]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
NTSC signal --> NABTS --> FEC --> serial data stream --> Framing protocol --> Van Jacobson style compressed UDP/IP headers --> application data
, and likewise for the example of a WST over PAL modulated system as:
PAL signal --> WST --> FEC --> serial data stream --> Framing protocol --> Van Jacobson style compressed UDP/IP headers --> application data
This diagram can be read as follows: television signals have NABTS or WST 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 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 [14].
5.1.1. 525 line systems (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 .[15]). 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.1.2. 625 line systems (PAL)
A PAL television frame is comprised of 2 fields of 312.5 horizontal
scan lines each. The first 22 lines of each field are not part of
the visible picture and are collectively called the Vertical Blanking
Interval (VBI). Of these 22 lines, 16 are available for data
transport, each being broadcast 50 times a second.
Some or all of these lines could be used for multicast IP transport.
It should be noted that some of these lines are sometimes used for
IPVBI [Page 4]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
Existing standard and proprietary data and testing services. Multicast IP therefore becomes one more data service using a subset or all of
these lines.
5.2. Line coding
The line coding, or byte coding, used on each line of the VBI is either NABTS or WST depending on the type of television system in use and the performance requirements of the system. Although these protocols are used in a similar manner to carry identically formatted data streams, they are NOT compatible. In addition, compatibility problems with existing receivers are likely to arise if NABTS and WST packet types are mixed in the same TV signal.
5.2.1. 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 an NTSC 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 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
IPVBI [Page 5]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
incremented by one for each 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. 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 most significant bit is always 0 in this implementation. The second 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 least two significant bits are used to indicate the length of the suffix on the Data Block, in this implementation either 2 or 28 bytes. This suffix is used for the forward error correction described in the next section.
The Data Block field is 0 to 26 bytes of useful data. Data is byte ordered most 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. Section 13 of the appendix discusses the resulting bit rates and overheads associated with NABTS.
5.2.2. WST
The World System Teletext Standard is defined in the European
Telecommunication Standard ETS 300 706 "Enhanced Teletext
Specification" Ref.[10]. It provides an industry accepted method of modulating data onto the VBI of many 625 line television signals.
A second standard ETS 300 708 "Data Transmission within Teletext"
Ref.[12] deals specifically with the use of WST packets for data broadcasting purposes. The proposal below frees two more bytes per line for data payload than Ref.[12]. This proposal is currently being considered by the EACEM (EBU) European standards committee as an 'Enhanced Independent Data Line Packet'. It is anticipated that this new Independent Data Line will be incorporated in Ref [12] as "Format B".
This section describes the WST packet format as it is used for the transport of multicast IP. It should be noted that only a subset of the WST standard is used, as is common practice in WST implementations. Further information concerning the WST standard and its implementation can be found in Ref.[10] and Ref.[12].
The WST packet is a 45-byte structure encoded onto one horizontal scan line of a 625 line television signal having the following structure:
IPVBI [Page 6]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
______________________________________________________________________
|Clock|Byte |Magazine|Packet |Serv|Serv|Cont | User Data |FEC |
|Sync |Sync |Address |Address|Type|Prov|Index| | |
| | | | | | | | | |
| 2B | 1B | 1B | 1B | 1B | 1B | 1B | 35B | 2B |
|_____|_______|________|_______|____|____|_____|__________________|____|
To maintain compatibility with existing WST broadcasts, the magazine and packet addresses of packets containing IP Multicast must have values of 1/30,2/30,3/30,7/30 or 7/31 (dependent on regulatory issues) where 1/30 is shorthand for Magazine 1, Packet 30 and so on. So the format of an IP Multicast WST packet will be as follows:
{2 B clock sync}{1 B byte sync}{1 B Magazine address}{1 B Packet address}{1 B service type}{1 B service provider address}{1 B continuity index}{35 B user data}{2 B FEC suffix}
Clock run-in and framing code:
The clock run-in and framing code (bytes 1 to 3) are the standard sequences used for all teletext packets as defined in ETS 300 706.
Data Channel ID:
The Data Channel ID is defined by the magazine and packet address bytes of the packet (bytes 4 and 5). The coding of these bytes is as defined in ETS 300 706.
For reasons of compatibility with existing systems and services, the magazine and packet address will adopt one (or more) of the data channels currently unallocated according to ETS 300 708, i.e. 1/30, 2/30, 3/30, 7/30 or 7/31.
A decision on the choice of Data Channel ID for a particular service should be made after consulting existing data broadcasters and standards authorities.
Service Type:
The Service Type (ST) byte (byte 6) is Hamming 8/4 encoded and provides 4 data bits. The 3 MSBs specify the type of service carried by the packet. This allows a decoder to filter the packet stream at the transport layer and reject packets which carry applications that are not supported. The precise coding has yet to be defined. In addition, these three bits may determine the precise function and coding of the Continuity Index (CI), and the FEC protocol used within the User Data bytes.
The LSB of the Service Type byte, D0, indicates the presence of any filler data in the User Data field, 0 = not present, 1 = present.
Service Provider Address and Service Identifier:
The Service Provider Address (SPA) byte (byte 7) is Hamming 8/4 encoded and provides 4 data bits. This permits up to 16 different services of each service type to share the same data channel.
The 4 SPA bits and the 3 MSBs of the Service Type byte taken together form a 7 bit Service Identifier value.
IPVBI [Page 7]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
Continuity Index:
The Continuity Index (CI) byte (byte 8) is Hamming 8/4 encoded and provides 4 data bits. This value is incremented modulo 16 for each new packet for a given Service Identifier value. Discontinuities in the sequence are not allowed to be transmitted so that a decoder can determine if any packets have been lost. The CI value is not incremented if a packet is repeated.
User Data:
The User Data (bytes 9 to 45) carries the data of the application. These bytes shall be coded as 8 bit data at the transport layer. Depending on the application, certain bytes may be allocated to carry data relating to a forward error correction protocol.
Any filler data required shall consist of the value 0x15 followed by as many instances of 0xEA as necessary to fill the User Data field. The presence of filler data is indicated by the LSB of the Service Type byte.
Sequential data blocks minus the filler data form an asynchronous serial stream of data.
These WST packets are modulated onto a 625 line television signal sequentially and on any combination of lines. Section 13 of this document in the appendix discusses the resulting bit rates and overheads associated with WST.
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 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. The FEC described for WST in the appendix is very similar to that for NABTS but with adjustments for the increased length of the WST payload.
5.3.1. FEC use with NABTS
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 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
IPVBI [Page 8]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
each of these rows, we now have a bundle of 16 NABTS packets ready for sequential modulation onto lines of the NTSC 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.
5.3.2. FEC use with WST
The WST FEC algorithm splits a serial stream of data into 490 byte "bundles". These are arranged as 14 packets of 35 bytes each. A function is applied to the 35 bytes of each packet to determine the two suffix bytes, which (with the addition of a header) complete the WST packet (8+35+2).
Each packet contains 2 FEC suffix bytes for horizontal and 2 suffix bytes for vertical correction.
At the receiving end the FEC scheme is 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 (Section 12).
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 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.
IPVBI [Page 9]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
The following two packet formats are used in a compression scheme which builds index tables on the client using full headers to rebuild packets sent with compressed headers:
[schema:8][0:1][Index:7][full headers:224][data][CRC:32]
[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. We propose one such scheme in this document for the compression of UDP/IP version 4 and assign it the value of 00000000. All other 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 an additional 32768 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.
If the high bit of the Compression Key is set to 1, a compressed version of that protocol's 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 the "fragment offset/flags" 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][fragment flags:3][fragment offset:13]
If (and only if) a compressed packet has the low-bit of Fragment Flags field set to a value of 1 (more fragments flag true) and the Fragment Offset field has a value of 0 (it is the first fragment), then the UDP Message Length and the UDP Checksum are included directly following the Fragment Offset field. This is shown below:
[1:1][Group:7][XX1:3][0000000000000:13][UDP Message Length:16][UDP Checksum:16][data][CRC:32]
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, uncompressed, IP packet, and uses the same algorithm as the MPEG-2 transport stream (ISO/IEC 13818-1). The generator polynomial is:
IPVBI [Page 10]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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
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.
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 injection 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.
WST addressing considerations:
Magazine and Packet addresses of 1/30,2/30,3/30,7/30 or 7/31 should be used depending
on regulatory issues and ETS 300 708 Ref.[12].
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
IPVBI [Page 11]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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
[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] European Telecommunication Standard. ETS 300 706 "Enhanced
Teletext Specification", 1997
[11] MediaComm 95. "Teletext in Multimedia Applications", D.Tarrant &
S.Wegerif, 1995
[12] European Telecommunication Standard. ETS 300 708 "Data
Transmission within Teletext", 1997
[13] European Telecommunication Standard. TR 101 233 DRAFT, " Code of
Practice for the Allocation of Services in the Vertical Blanking
Interval (VBI)", 1997
[14] International Telecommunications Union Recommendation.
ITU-R BT.470-5 (02/98) "Conventional TV Systems"
[15] Recommended Practice for Line 21 Data Service (ANSI/EIA-608-94) (Sept., 1994)
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
IPVBI [Page 12]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
RFC - Request For Comments
IP - Internet Protocol
UDP - User Datagram Protocol
TCP - Transmission Control Protocol
SLIP - Serial Line Internet Protocol
WST - World System Teletext
ETSI - European Telecommunication Standard
11. Author's address and contacts
Ruston Panabaker, co-editor
Microsoft
One Microsoft Way
Redmond, WA 98052
t-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
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. Each element is represented by an 8 bit binary number.
The operations of "addition" and "subtraction" are the same for this
IPVBI [Page 13]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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:
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 (NABTS) or 37 bytes (WST) when the correction bytes are included. The bundle therefore has 16 horizontal codewords interleaved with 28 or 37 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++)
{
IPVBI [Page 14]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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
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 for NABTS or 37 for WST. 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++)
{
IPVBI [Page 15]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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 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))
IPVBI [Page 16]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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.
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:
IPVBI [Page 17]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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)
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
IPVBI [Page 18]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
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.
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.
15.6. Appendix References
IPVBI [Page 19]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
[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. Performance analysis
Description WST NABTS
VBI overhead 17.8% 22.2%
FEC + SLIP overhead 36.9% 37.9%
+UDP/IP overhead 38.9% 39.9%
bps per VBI line 10,992 10,380
bps per entire VBI 175.9K 115K
bps per entire channel 3.36M 2.70M
14. Architecture
The architecture that this document is addressing can be broken down 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 or WST 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
IPVBI [Page 20]
< draft-ietf-ipvbi-tv-signal-00.txt > July 1998
to recover any lost data for the broadcast of data to be effective.
The receiving client must be capable of tuning, NABTS or WST waveform sampling as appropriate, filtering on NABTS group addresses or WST MPAGs and 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.
15. 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.
NABTS and WST represent two standard methods of adding data services to the VBI in various television systems. These systems collectively represent the largest communication network in the world.
The unidirectional framing protocol provides encapsulation of multicast IP datagrams on the serial stream, and the Van Jacobson style 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.
IPVBI [Page 21]
