INTERNET-DRAFT R. Panabaker < draft-panabaker-ip-vbi-00.txt > Microsoft Corp. Obsoletes: NA C. Witty Category: Newton Research Labs March 1997 THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A TELEVISION SIGNAL 1. Status of this Memo This document is an Internet-Draft. 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 "1id-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), ds.internic.net (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 a television signal. It includes a description for compressing multicast IP headers on unidirectional networks, a framing protocol identical to SLIP, and a forward error correction scheme for the NABTS standard. Keywords: VBI, NTSC, broadcast, push, FEC, television, NABTS, IP 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.2. NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 5.3. FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 5.4. Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .6 5.5. IP compression . . . . . . . . . . . . . . . . . . . . . . . 6 6. Addressing Considerations . . . . . . . . . . . . . . . . . . . 7 7. Performance analysis . . . . . . . . . . . . . . . . . . . . . .7 Panabaker [Page 1] < draft-panabaker-ip-vbi-00.txt > March 1997 8. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . .8 9. Scope of proposed protocols . . . . . . . . . . . . . . . . . . 8 10. Security considerations . . . . . . . . . . . . . . . . . . . . 9 11. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 9 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . .9 13. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 14. Author's address and contacts . . . . . . . . . . . . . . . . .10 15. Appendix: Forward Error Correction Specification . . . . . . .11 15.1. Mathematics used in the FEC . . . . . . . . . . . . . . . . 11 15.2. Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 12 15.3. Correcting Errors . . . . . . . . . . . . . . . . . . . . . 12 15.4. Correcting FEC Bundles . . . . . . . . . . . . . . . . . . .15 15.5. Appendix References . . . . . . . . . . . . . . . . . . . . 15 4. Introduction This Internet-Draft proposes several protocols to be used in the transmission of IP datagrams across the Vertical Blanking Interval (VBI) of a television signal. The VBI is an 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. This will allow existing standards from the television and Internet communities to provide inexpensive broadcast data services. Additional protocols will be used to do this 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. I would like to acknowledge the tremendous assistance of Ken Birdwell, Dave Feinleib and Brian Moran, of Microsoft Corp, and Carl Witty, of Panabaker [Page 2] < draft-panabaker-ip-vbi-00.txt > March 1997 Newton Research Labs, in writing this document. Many of the ideas expressed within are the result of their efforts and insight in this area. Any of these ideas that prove misbegotten are the sole responsibility of the author. 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 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 computers and UDP, in the transport layer, determines the flow of data to the appropriate processes and applications. +-----------+ | | |Application| | | +-----------+ | | ) | UDP | ) | | ) +-----------+ (-- multicast-IP | | ) | IP | ) | | ) +-----------+ |SLIP style | | encap- | | -sulation | +-----------+ | | | NABTS | | with FEC | +-----------+ | The VBI of NTSC medium | (cable, off-air, etc) |--------<----<----<-------- These protocols can be described in a bottom up component model as follows: NTSC signal --> NABTS --> FEC --> serial data stream --> Framing protocol --> Van Jacobson style compressed UDP/IP headers --> application data This diagram can be read as follows: NTSC 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 the location Panabaker [Page 3] < draft-panabaker-ip-vbi-00.txt > March 1997 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 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. 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 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: {2 B clock sync}{1 B byte sync}{3 B packet group address}{1 B continuity index}{1 B packet structure flags}{26 B data block}{2 B FEC suffix} The 2 byte Clock Synchronization and the 1 byte Byte Synchronization, although not part of the NABTS packet, 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 Panabaker [Page 4] < draft-panabaker-ip-vbi-00.txt > March 1997 distinguish different data services, possibly inserted at different points of the transmission system, and most likely totally unrelated. Section 5 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 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. 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 NTSC signal sequentially and on any combination of lines. Section 6 of this document discusses the resulting bit rates and overheads associated with NABTS. 5.3. FEC Due to the unidirectional nature of VBI data transport, forward error correction is needed to ensure the integrity of data at the receiver. Any FEC could be used to this end. The FEC for NABTS described in the appendix of this document 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 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 for that, 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 Panabaker [Page 5] < draft-panabaker-ip-vbi-00.txt > March 1997 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 NTSC signal. At the receiving end of the network 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.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 is 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. The following two packet formats are used in the following compression scheme: The first byte of all packets is the Compression Key. It is a 1 byte value, the first bit of which indicating if the header has been compressed, and the remaining 7 bits indicating the compression group it belongs to. [0:1][Index:7][protocol:16][full headers:224][data][CRC:32] [1:1][Index:7][compressed header:32][data][CRC:32] If the high bit of the Compression Key is set to 0, no compression is performed and the 2-byte protocol number (the same as 802.3 Ethernet) Panabaker [Page 6] < draft-panabaker-ip-vbi-00.txt > March 1997 and the full header are sent. The client VBI interface should store the protocol number and uncompressed header for future potential use. If the high bit of the Compression Key is set to 1, the protocol number is not sent, and 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. As indicated, this compression scheme will support any packet protocol. Currently, and for the purpose of this document, the only protocol compression defined is for DoD IP, protocol number 0x0800. 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][0x0800][IP header][UDP header] [1:1][Group:7][IP identification][fragment offset/flags] A 32 bit CRC has also been added to the end of every packet 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: 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 D^10 + D^11 + D^12 + D^16 + D^22 + D^23 + D^26 + D^32 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. 7. Performance analysis This section performs an analysis of the overheads associated with each Panabaker [Page 7] < draft-panabaker-ip-vbi-00.txt > March 1997 of the protocols described above, and the resulting bit rates. Every line of an NTSC picture is capable of carrying a 36-byte NABTS packet (including sync bytes). Every line is refreshed once every 1/60th of a second, which results in a bit rate of 17,280 bps. The NABTS packet has 8 bytes of overhead on each 36 byte packet, or 22.2% overhead. FEC has 2 bytes on every packet plus 2 packets added for every group of 14. This brings the total overhead so far to 36.8%. The remaining data can now be treated as an asynchronous serial stream. Assume an IP packet size of 350 bytes for the following calculations. The framing of IP packets adds 1.7% overhead to the data stream, or 1.07% to the total overhead on all bits, assuming 2 escapes per packet. This brings the running total to 37.9% overhead. IP overhead is reduced with the use of header compression. The uncompressed version includes the compression index, protocol number, the entire UDP/IP header, and CRC for a total of 34 bytes overhead. The compressed version has only 9 bytes in its header. Assuming we only transmit the uncompressed packet once in every 10 packets, we get an average header of only 11.5 bytes. This adds an additional 2% overhead on the total bits transmitted, bringing the total overhead to 39.9%. The theoretical throughput is therefore 17,280*(1-.399) or 10,380 bps per line. This is easily scalable to 115 Kbps for all 11 lines of the VBI, or 2.7 Mbps for the entire screen. 8. 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 NTSC signal can occur at any part of the delivery system. A NABTS hardware encoder 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, filtering on NABTS group addresses, forward error correction, unframing, verification of the CRC and decompressing the UDP/IP Panabaker [Page 8] < draft-panabaker-ip-vbi-00.txt > March 1997 headers. All of the above functions can be carried out in PC software and inexpensive off-the-shelf hardware. 9. 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 is a standard used on NTSC signals and the FEC was designed primarily for use with NABTS packet data. However, the data transported is simply an asynchronous serial stream, and is therefore abstracted from the transport mechanism of these two protocols. Many NABTS encoders work with PAL, SECAM, and NTSC-J video formats as well. This would require different waveform sampling and decoding on the client, but would allow all 900+ million cable subscribers in the world to receive IP over the VBI. It should also be noted that NABTS could be used in a full screen mode, in which all lines of the picture frame were used for data transport. There are obviously issues concerning the logistics of this service, but the possibility exists, and many VBI decoders support this functionality. 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. 10. 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. 11. Conclusions This document provides a method for broadcasting Internet data over a television signal for reception by client computers. 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. 12. References [1] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC 1112, 17 pages (Aug.). Panabaker [Page 9] < draft-panabaker-ip-vbi-00.txt > March 1997 [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 [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. 13. 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 14. Author's address and contacts Ruston Panabaker One Microsoft Way Redmond, WA 98052-6399 email: BPCfeed@microsoft.com Other contacts: Panabaker [Page 10] < draft-panabaker-ip-vbi-00.txt > March 1997 Brian Moran One Microsoft Way Redmond, WA 98052-6399 brianmo@microsoft.com T: (206) 936-4376 Dave Feinleib One Microsoft Way Redmond, WA 98052-6399 davefe@microsoft.com T: (206) 703-5543 15. Appendix: Forward Error Correction Specification This FEC is specified as used for the detection and correction of errors incurred during transmission on the vertical blanking interval in NABTS packets. Carl Witty (< biblio >) wrote the original specification, from which this appendix was written. We begin with a brief description of the mathematics used throughout this specification. 15.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). This is a set of 256 elements, along with the operations of "addition" and "multiplication" on these elements. Each element is represented by an 8 bit binary number. The operation of "addition" with this Galois field is 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. These Galois elements have many properties in common with the real numbers: - every nonzero x has an inverse x^-1 , such that x*x^-1=1 - (xy)^-1 = x^-1 * y^-1 Panabaker [Page 11] < draft-panabaker-ip-vbi-00.txt > March 1997 - x(yz) = (xy)z - x + (y + z) = (x +y) + z - xy = yx - x + y = y + x - (x + y)z = xz + yz - if xy = xz then x = 0 or y = z - if xy = 0 then x = 0 or y = 0 - x^(a+b) = x^a * x^b (here a and b are standard numbers not in the Galois field and a+b denotes standard addition) There are also many properties which differ from the real numbers: - for every nonzero x, x^255 = 1 (this implies that x^254 = x^-1) - x + x = 0 15.2. Calculating FEC bytes The FEC algorithm splits a serial stream of data into 364 byte "bundles". These are arranged as 14 packets of 26 bytes each. Across each packet the following expression is determined for each of the two suffix bytes, S0 and S1, which (with the addition of a header) complete the NABTS packet (8+26+2): Sum, as i goes from 0-25, of Ci,j * Di = Sj Where, Ci,j is a tabulated coefficient, Di is the ith data byte of the data block, and j can be 0 and 1. The multiplications and additions in this formula are done using Galois fields and modulo arithmetic as explained above. The tabulated coefficients are: Ci,0 = {0x9d, 0x37, 0xe4, 0xcb, 0x7f, 0xab, 0x8d, 0xbb, 0xb1, 0x6a, 0xde, 0x8a, 0x4a, 0x20, 0x98, 0x9d, 0xbb, 0x94, 0x3d, 0x38, 0xa6, 0xe9, 0x42, 0xa0, 0xe2, 0x64, }, and... Ci,1 = {0x92, 0x97, 0xdd, 0xa0, 0x9a, 0x91, 0x0a, 0x50, 0x1d, 0x60, 0xae, 0x20, 0x3d, 0x2c, 0x01, 0x0a, 0x40, 0xc8, 0xe5, 0xff, 0xf2, 0x68, 0xc9, 0xa1, 0x63, 0x8d, }. For every 14 packets in the bundle an additional 2 packets are appended which contain only FEC data. This data is obtained by first writing the packets into a table of 16 rows and 28 columns. The same formula as above can be used on the columns of the table with S0 and S1 now representing the byte at the base of the column in row 15 or 16 respectively. Therefore we calculate Sum, as i goes from 0-13, of Ci,j * Di = Sj for each column. Where, Ci,j is a coefficient from the same table as above, Di is the nth byte of the ith row, and j can be 0 and 1. 15.3. Correcting Errors Panabaker [Page 12] < draft-panabaker-ip-vbi-00.txt > March 1997 This section describes the procedure for detecting and correcting errors using the FEC data calculated above. Upon reception we begin by arranging the packets in tabular form similar to that in the previous section. We form a column of 16 packets each containing 28 bytes ofdata. We will be detecting and correcting errors in these rows and columns. Since the horizontal and vertical FEC are the same (except for the number of byes of data to be protected), the algorithms here will work in both directions. We will use k as the number of bytes of data to be protected, so k is either 26 (for horizontal FEC) or 14 (for vertical FEC). The original, error-free bytes are D0, D1, ....Dk, Dk+1 (note that the FEC bytes are included as Dk and Dk+1), and the received bytes with possible errors are R0,....., Rk+1. We know that if no errors occurred, we would have the sum, as i goes from 0 to k-1 of Ci,j * Ri = Rk+j, for j=0,1. In the Galois field this can be written as (the sum, as i goes from 0 to k-1 of Ci,j * Ri) + Rk+j = 0. Eqn 1 Conversely, if errors did occur, it is most likely that this equation would not be true. We can therefore assume that if Eqn 1 is satisfied, no errors occurred. 15.3.1. Detecting and correcting single-byte errors When Eqn 1 is not satisfied there are one or more errors in the protected bytes. We will begin by looking at the effect of a single byte error at position p. There are two basic cases: p >= k and p < k. The first case: If p >= k then there is an error in one of the two FEC bytes. This is indicated by Eqn 1 being satisfied when j = 0 or j = 1 but not both. The second case: If p < k then the error is not in the FEC bytes but in the protected data. In this case, Eqn 1 will not be satisfied for either j = 0 or j = 1. Instead we will get (the sum, as i goes from 0 to k-1 of Ci,j *Ri) + Rk+j = Ej Eqn 2 where Ej = Ci,j * h, and h = Dp - Rp. Thus as long as there is no q (other then q=p) such that Cp,0 * Cp,1^-1 = Cq,0 * Cq,1^-1, we can construct a function P(Cp,0 * Cp,1^-1) = p. This condition is in fact met by the coefficients chosen for Ci,j. If p is found to be a valid number (less then k), we can subtract h (where h = Ej * Cp,j^-1, and j = 0 or j = 1) from the value located at p and the error is corrected. This can be verified by using Eqn 1 on Panabaker [Page 13] < draft-panabaker-ip-vbi-00.txt > March 1997 the new protected data block. If p is not a valid number then we assume there are at least two errors in the block. It should be noted that by using any of the above corrections it is possible to mistakenly turn a two-byte error into a three-byte error. 15.3.2. Correcting Single Byte Erasures If we know where an error is in the protected block we can correct it and still detect any other single byte error but not correct it. We might know the location of this erasure because a packet was lost during transmission, and we are correcting the columns of our table. Every column in this example will have an erasure at p, where p is the lost packet row. First let's consider the case where p >= k, which means the erasure is in the FEC. We can use Eqn 1 to ensure the other FEC byte satisfies the equation, and can therefore determine that the packet most likely has no errors. If it does not, we know there is at least one other one-byte error and we cannot determine its location to fix it. The second possibility is that p March 1997 equations. Assuming Cp,j and Cq,j are non-zero (which they are in this implementation), and Cp,0 * Cp,1^-1 does not equal Cq,0 * Cq,1^-1 (which is also true for all p < q < k), we can solve this system for Dp and Dq. 15.4. Correcting FEC Bundles We now have a set of tools for detecting and correcting errors in FEC bundles. 1) With no erasures, we can look at a row or column and say either: - The FEC bytes match; there are probably no errors. - The FEC bytes fail to match in a way which could be caused by a single-byte error; in this case we can find the location and value of such an error. - The FEC bytes fail to match in a way which indicates that there are at least two bytes of error. 2) With one erasure, we can correct it and look at a line and say either: - The FEC bytes now match; there are probably no other errors (beyond the erasure) - The FEC bytes don't match; there is at least one more error, which we cannot correct. 3) With two erasures, we can correct the line so that the FEC bytes match. In this case, we have no error-detecting capability. All of these tools can be used in an iterative manner on the rows and columns of the FEC bundle to correct or detect errors. 15.5. 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] Witty, Carl. 1997 Newton Research Labs, Seattle, WA Panabaker [Page 15]