INTERNET-DRAFT N. Thorne Expires in six months Obsoletes: NA Category: ipvbi THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A PAL 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 PAL television signal. It includes a description for compressing multicast IP headers on unidirectional networks, a framing protocol identical to SLIP, forward error correction schemes for the WST standards. A related Internet-Draft, Ref.[1], is progressing transmission of IP over the VBI of an NTSC television signal. Keywords: VBI, PAL, broadcast, push, FEC, television, NABTS, WST, IP 3. Table of Contents 1. Status of this Memo 2. Abstract 3. Table of Contents 4. Introduction 5. Proposed protocol stack 5.1. PAL VBI Overview 5.2. WST VBI Standard 5.3. WST Forward Error Correction (FEC) 5.4. Framing 5.5. IP compression 6. WST Addressing Considerations 7. WST Performance analysis 7.2. Summary of Performance of IP over PAL and NTSC(Ref.[1]) VBI 8. Architecture 9. Scope of proposed protocols 10. Security considerations 11. Conclusions 12. References 13. Acronyms 14. Author's address and contacts 15. Appendix: WST Forward Error Correction Specification 15.1. Mathematics used in the WST FEC 15.2. Calculating WST FEC bytes 15.3. Correcting Errors using the WST FEC 15.3.1. Detecting & Correcting Single Byte Errors 15.3.2. Correcting Double Byte Erasures 15.4. Correcting WST FEC Bundles 15.5. WST FEC Appendix References 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 PAL 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 World System Teletext (WST) Standard Ref.[7]. WST is 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. The author would like to acknowledge Ruston Panabaker of Microsoft Corp and Carl Witty of Newton Research for writing the Internet-Draft for IP over the VBI (of a NABTS) TV signal, Ref.[1]., and Bruce Murray and Ian Willis of Philips Semiconductors Systems Laboratory Southampton 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 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 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 | +-----------+ | | | WST | | with FEC | | | +-----------+ | The VBI of PAL medium | (cable, off-air, etc.) |--------<----<----<-------- These protocols can be described in a bottom up component model as follows: 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: PAL signals have 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 PAL VBI Overview 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 existing, proprietary, data and testing services. Multicast IP therefore becomes one more data service using a subset or all of these lines. 5.2. WST VBI Standard The World System Teletext Standard is defined in the European Telecommunication Standard ETS 300 706 "Enhanced Teletext Specification" Ref.[7]. It provides an industry accepted method of modulating data onto the VBI of a PAL signal. A second standard ETS 300 708 "Data Transmission within Teletext" Ref.[9] 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.[9], though there may be regulatory hurdles to be overcome in doing this. 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.[7] and Ref.[9]. The WST packet is a 45-byte structure encoded onto one horizontal scan line of a PAL signal having the following structure: {2 B clock sync}{1 B byte sync}{2 B magazine and packet address}{40 B data} To maintain compatibility with existing WST broadcasts, the magazine and packet address group (MPAG) of IP Multicast packets must have MPAGs (Magazine and Packet Address Groups) of 0/30,1/30,2/30,3/30,7/30 or 7/31 (dependent on regulatory issues) where 0/30 is shorthand for Magazine 0, 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}{2 B MPAG}{1 B service type}{2 B packet group address}{1 B continuity index}{35 B data block}{2 B FEC suffix} The 2 byte Clock Synchronization and the 1 byte Byte Synchronization, although not part of the WST packet, are located at the beginning of every scan line containing a WST packet and are used to synchronize the decoding sampling rate and byte timing. The 2 byte Magazine and Packet Address Group (MPAG) is Hamming encoded (as specified in Ref.[7]) and provides 4 data bits per byte. 3 bits specify the magazine and 5 bits the packet. MPAGs of 0/30,1/30,2/30,3/30,7/30 or 7/31 (subject to regulations and Ref.[9]) should always be used to guarantee compatibility with existing WST transmissions. The 1 byte Service Type byte is Hamming Encoded and provides 4 data bits. Bits d3 (MSB), d2 and d1 specify the service type. Service type 000 is IP over VBI. Other service types are to be specified. The meaning of d0 (the LSB) depends on the service type. For service type 000, d0 indicates the presence of filler in the data payload. If d0 is cleared to 0, no filler data is present. If d0 is set to 1, filler data is present. The meaning of d0 with other service types is not specified. The 1 byte Packet Group address field is Hamming encoded and provides 4 data bits per byte, and thus provides 16 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. 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 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 last count 15. This allows the decoder to determine if packets have been lost during transmission. No discontinuities in the CI sequence shall be transmitted. The Data Block field 35 bytes. 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 WST packets are modulated onto the PAL signal sequentially and on any combination of lines. Section 7 of this document discusses the resulting bit rates and overheads associated with WST. 5.3.WST Forward Error Correction (FEC) Due to the unidirectional nature of VBI data transport, forward error correction is needed to ensure the integrity of data at the receiver. The FEC for WST described in the appendix of this document (Section 16) is based on the industry standard t=1 RS scheme, popular in CD ROM systems. The WST FEC algorithm splits a serial stream of data into 448 byte "bundles". These are arranged as 16 packets of 35 bytes each. A function is applied to the 35 bytes of each packet to determine the two suffix bytes for that, 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 t=1 RS 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 15). 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) 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. WST Addressing Considerations The addressing of multicast IP packets should adhere to existing standards in this area Refs.[7] & [9]. The inclusion of an appropriate source address is needed to ensure the receiving client can distinguish between sources and thus services. MPAGs of 0/30,1/30,2/30,3/30,7/30 or 7/31 should be used depending on regulatory issues and ETS 300 708 Ref.[9]. The 1 byte Service Type and 1 byte Packet Address Group then follow. These provide addressing between different Multicast IP providers. 7. WST Performance analysis This section performs an analysis of the overheads associated with each of the protocols described above, and the resulting bit rates. Every line of a PAL picture is capable of carrying a 45-byte WST packet (including sync bytes). Every line is refreshed once every 1/50th of a second, which results in a bit rate of 18,000bps. The WST packet has 8 bytes of overhead on each 45 byte packet, or 17.8% overhead (run in + framing code + MPAG + Service Type + Packet Address Group + Continuity Index). FEC has 2 bytes on every packet plus equivalent of 2 packets added for every group of 14: ((2 * 14 + 2 * 35) / (14 * 35)) * (100 - 17.8) = 18.0% (overhead on remainder from VBI overhead), so 18.0% + 17.8% = 35.8%. This brings the total overhead so far to 35.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.02% (0.017 * (100 - 35.8%) =1.09%) to the total overhead on all bits, assuming 2 escapes per packet. This brings the running total to 36.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 38.9%%. The theoretical throughput is therefore 18,000*(1-.389) or 10,992Kbps per line. This is easily scaleable to 175.9 Kbps for all 16 lines of the VBI, or 3.36 Mbps for the entire screen. 7.3. Summary of Performance of IP over PAL and NTSC (Ref.[1]) VBI 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 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 PAL television signal can occur at any part of the delivery system. A WST 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 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. For example some sophisticated systems can dynamically insert packets on any VBI line not in use. 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, WST data recovery, filtering on WST MPAGs and group addresses, forward error correction, unframing, verification of the CRC and decompressing the UDP/IP 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. WST is a standard used on PAL signals. The FEC is designed primarily for use with WST. However, the data transported is simply an asynchronous serial stream, and is therefore abstracted from the transport mechanism of these protocols. Many WST encoders work with the SECAM video format as well. This would require different waveform sampling and decoding on the client, but would allow more subscribers in the world to receive IP over the VBI. It should also be noted that PAL could be used in a full screen (also called full field) 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 PAL 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] Internet-Draft (Work in Progress) "The Transmission of IP over the Vertical Blanking Interval of a Television Signal", R. Panabaker, Microsoft Corp. C.Witty, Newton Research Labs. March 97 [2] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC 1112, 17 pages (Aug.) [3] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: North American Basic Teletext Specification (NABTS)" Washington: Electronic Industries Association, c1988 [4] Jacobson, V. 1990a. "Compressing TCP/IP Headers for Low-Speed Serial Links," RFC 1144, 43 pages (Feb.). [5] Romkey, J. L. 1988. "A Nonstandard for Transmission of IP Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June). [6] Stevens, W. Richard. "TCP/IP Illustrated, Volume 1,: The Protocols" Reading: Addison-Wesley Publishing Company, c1994. [7] European Telecommunication Standard. ETS 300 706 "Enhanced Teletext Specification", 1997 [8] MediaComm 95. "Teletext in Multimedia Applications", D.Tarrant & S.Wegerif, 1995 [9] European Telecommunication Standard. ETS 300 708 "Data Transmission within Teletext", 1997 [10] European Telecommunication Standard. TR 101 233 DRAFT, " Code of Practice for the Allocation of Services in the Vertical Blanking Interval (VBI)", 1997 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 WST - World System Teletext ETSI - European Telecommunication Standard 14. Author's address and contacts Nick Thorne Philips Semiconductors Systems Laboratory - Southampton Millbrook Industrial Estate Southampton Hampshire, UK SO15 0DJ email: nick.thorne@soton.sc.philips.com Other contacts: Simon Wegerif Philips Semiconductors Systems Laboratory - Southampton Millbrook Industrial Estate Southampton Hampshire, UK SO15 0DJ email: simon.wegerif@soton.sc.philips.com 15. Appendix: WST 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 WST packets. This FEC is based on the same standard Galois field operations as the NABTS FEC (Ref.[1]), but with a pure t=1 Reed Solomon (RS) code instead. Use of the RS code reduces the number of tables required. 15.1. Mathematics used in the WST 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 - 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 WST FEC bytes The FEC algorithm splits a serial stream of data into 448 byte "bundles". These are arranged as 14 packets of 35 bytes each. Across each packet the following expression is determined for each of the two suffix bytes, bN and bN+1, which (with the addition of a header) complete the WST packet (8+35+2): We calculate: b0 + b1 + b2 + b3 + .... + bN-1 = bN + bN+1 = X EQN [1] and a N+1.b0 + aN.b1 + .... + a2.bN-1 = a.bN + bN+1 = Y EQN[2] Where N = number of characters in a row = 35, or characters in a columns = 14. bN is the Nth data element of the row or column. a is the primitive element of the GF(2^8) Galois Field such that: 1, a, a2, a3, a4, ..... a253, a254 would be all of the 255 non-zero elements and a255 = a0 = 1. The powers of a are tabulated in a look up table of log_a[ n] and the inverse table, a_to_power[n] >From the two equations above, bN + bN+1 = X a.bN + bN+1 = Y gives X + Y = (1 + a). bN giving bN = (X + Y) / (1+a) (where 1+a = 0x03 and use log_a[j] - log_a[k] to perform the division, and X + Y implies X xor Y) and bN+1 = bN + X There is an exception case to account for when X = Y. If this occurs, X + Y = 0 and the log_a[0] cannot be taken. Then by definition bN must be zero, otherwise: X = bN + bN+1 and Y = a.bN + bN+1 cannot simultaneously be true. When bN = 0 then bN+1 = X + Y. The multiplications and additions in this formula are done using Galois fields and modulo 100011101 arithmetic. Once we have encoded the block of data it looks like: 1 2 3 4.....................................................35 36 37 1 ---------------------------------------------------------------P P 2 ---------------------------------------------------------------P P . ---------------------------------------------------------------P P . ................................................................... . ---------------------------------------------------------------P P . ---------------------------------------------------------------P P . ---------------------------------------------------------------P P . ---------------------------------------------------------------P P 14 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP P 15 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP P Where '-' denotes a data byte and 'P' denotes a suffix byte. 15.3. Correcting Errors using the WST FEC 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 37 bytes of data. 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 bytes of data to be protected), the algorithms here will work in both directions. 15.3.1. Detecting and correcting single-byte errors >From section 15.2, equations [1] and [2], we have b0 + b1 + b2 + b3 + .... + bN-1 + bN + bN+1 = 0 EQN [1] and a N+1.b0 + aN.b1 + .... + a2.bN-1 + a.bN + bN+1 = 0 EQN[2] where bx are the broadcast data bytes. So we calculate: r0 + r1 + r2 + r3 + .... + rN-1 + rN + rN+1 = S0 and a N+1.r0 + aN.r1 + .... + a2.rN-1 + a.rN + rN+1 = S1 where rx are the received data bytes. If S0=S1=0, there are no errors. Otherwise S0 = Ei and S1 = aN+1-i.Ei The error value is therefore given directly by syndrome byte S0 and the error position (p) by S1 with use of the log_a[n] table. If the position p > N then we assume that 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 Double-byte Erasures In the case of a double byte erasure, we lose all error-detecting capability. Given the location of two erasures we can correct them assuming all other bytes are correct. It is possible to utilize this FEC to correct double errors by marking erasures and performing multiple passes. The subject of erasure marking and processing is not discussed in detail here. 15.4. Correcting WST 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. WST FEC Appendix References [1] Philips Semiconductors Systems Laboratory Southampton Internal Report "CD-ROM Third Level Error Correction Algorithmic Background", 1995, Bruce Murray [2] Philips Semiconductors Systems Laboratory Southampton. "SAA5284 User Guide STX/UM96009", 1996, Nick Thorne