idnits 2.17.1 draft-ietf-ipvbi-nabts-02.txt: ** The Abstract section seems to be numbered Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 1006 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 1999) is 9201 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'Romkey 1988' on line 324 -- Looks like a reference, but probably isn't: 'RFC 2434' on line 453 -- Looks like a reference, but probably isn't: 'A' on line 626 -- Looks like a reference, but probably isn't: 'B' on line 626 -- Looks like a reference, but probably isn't: 'Byte' on line 834 == Unused Reference: '7' is defined on line 505, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 508, but no explicit reference was found in the text == Unused Reference: '9' is defined on line 511, but no explicit reference was found in the text == Unused Reference: '10' is defined on line 514, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' ** Obsolete normative reference: RFC 2434 (ref. '5') (Obsoleted by RFC 5226) -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' Summary: 7 errors (**), 0 flaws (~~), 6 warnings (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IPVBI R. Panabaker, Microsoft 2 Internet Draft S. Wegerif, Philips Semiconductors 3 D. Zigmond, WebTV Networks 4 Document: February 1999 6 The Transmission of IP Over the Vertical Blanking Interval 7 of a Television Signal 9 Status of this Memo 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026. Internet-Drafts are 13 working documents of the Internet Engineering Task Force (IETF), its 14 areas, and its working groups. Note that other groups may also 15 distribute working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six 18 months and may be updated, replaced, or obsoleted by other documents 19 at any time. It is inappropriate to use Internet-Drafts as 20 reference material or to cite them other than as "work in progress." 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 25 The list of Internet-Draft Shadow Directories can be accessed at 26 http://www.ietf.org/shadow.html. 28 To view the entire list of current Internet-Drafts, please check the 29 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 30 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 31 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 32 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 34 A revised version of this draft document will be submitted to the 35 RFC editor as a Proposed Standard for the Internet Community. 36 Discussion and suggestions for improvement are requested. This 37 document will expire before August 1999. Distribution of this draft 38 is unlimited. 40 1. Abstract 42 This document describes a method for broadcasting IP data using the 43 vertical blanking interval of television signals. It includes a 44 description for compressing IP headers on unidirectional networks, a 45 framing protocol identical to SLIP, a forward error correction 46 scheme, and the NABTS byte structures. 48 2. Introduction 50 This RFC proposes several protocols to be used in the transmission 51 of IP datagrams using the Vertical Blanking Interval (VBI) of a 52 television signal. The VBI is a non-viewable portion of the 53 television signal that can be used to provide point-to-multipoint IP 54 data services which will relieve congestion and traffic in the 56 Panabaker 1 57 IPVBI February, 1999 59 traditional Internet access networks. Wherever possible these 60 protocols make use of existing RFC standards and non-standards. 62 Traditionally, point to point connections (TCP/IP) have been used 63 even for the transmission of broadcast type data. Distribution of 64 the same content - news feeds, stock quotes, newsgroups, weather 65 reports, and the like - are typically sent repeatedly to individual 66 clients rather than being broadcast to the large number of users who 67 want to receive such data. 69 Today, IP is quickly becoming the preferred method of distributing 70 one-to-many data on intranets and the Internet. The coming 71 availability of low cost PC hardware for receiving television 72 signals accompanied by broadcast data streams makes a defined 73 standard for the transmission of data over traditional broadcast 74 networks imperative. A lack of standards in this area as well as 75 the expense of hardware has prevented traditional broadcast networks 76 from becoming effective deliverers of data to the home and office. 78 This document describes the transmission of IP using the North 79 American Basic Teletext Standard (NABTS), a recognized and industry- 80 supported method of transporting data on the VBI. NABTS is 81 traditionally used on 525-line television systems such as NTSC. 82 Another byte structure, WST, is traditionally used on 625-line 83 systems such as PAL and SECAM. These generalizations have 84 exceptions, and countries should be treated on an individual basis. 85 These existing television system standards will enable the 86 television and Internet communities to provide inexpensive broadcast 87 data services. A set of existing protocols will be layered above 88 the specific FEC for NABTS including a serial stream framing 89 protocol similar to SLIP (RFC 1055 [Romkey 1988]) and a compression 90 technique for unidirectional UDP/IP headers. 92 3. Proposed protocol stack 94 The following protocol stack demonstrates the layers used in the 95 transmission of VBI data. Each layer has no knowledge of the data 96 it encapsulates, and is therefore abstracted from the other layers. 97 At the link layer, the NABTS protocol defines the modulation scheme 98 used to transport data on the VBI. At the network layer, IP handles 99 the movement of data to the appropriate clients. In the transport 100 layer, UDP determines the flow of data to the appropriate processes 101 and applications. 103 +-------------------+ 104 | | 105 | Application | 106 | | 107 +-------------------+ 108 | | ) 109 | UDP | ) 110 | | ) 112 Panabaker 2 113 IPVBI February, 1999 115 +-------------------+ (-- IP 116 | | ) 117 | IP | ) 118 | | ) 119 +-------------------+ 120 | SLIP style | 121 | encapsulation | 122 | | 123 +-------------------+ 124 | FEC | 125 |-------------------| 126 | NABTS | 127 | | 128 +---------+---------+ 129 | | 130 | NTSC/other | 131 | | 132 +-------------------+ 133 | 134 | 135 | cable, off-air, etc. 136 |--------<----<----<-------- 138 These protocols can be described in a bottom up component model 139 using the example of NABTS carried over NTSC modulation as follows: 141 Video signal --> NABTS --> FEC --> serial data stream --> Framing 142 protocol --> compressed UDP/IP headers --> application data 144 This diagram can be read as follows: television signals have NABTS 145 packets, which contain a Forward Error Correction (FEC) protocol, 146 modulated onto them. The data contained in these sequential, 147 ordered packets form a serial data stream on which a framing 148 protocol indicates the location of IP packets, with compressed 149 headers, containing application data. 151 The structure of these components and protocols are described in 152 following subsections. 154 3.1. VBI 156 The characteristics and definition of the VBI is dependent on the 157 television system in use, be it NTSC, PAL, SECAM or some other. For 158 more information on Television standards worldwide, see ref [12]. 160 3.1.1. 525 line systems 162 A 525-line television frame is comprised of two fields of 262.5 163 horizontal scan lines each. The first 21 lines of each field are 164 not part of the visible picture and are collectively called the 166 Panabaker 3 167 IPVBI February, 1999 169 Vertical Blanking Interval (VBI). Of these 21 lines, the first 9 170 are used while repositioning the cathode ray to the top of the 171 screen, but the remaining lines are available for data transport. 173 There are 12 possible VBI lines being broadcast 60 times a second 174 (each field 30 times a second). In some countries Line 21 is 175 reserved for the transport of closed captioning data (Ref.[11]). In 176 that case, there are 11 possible VBI lines, some or all of which 177 could be used for IP transport. It should be noted that some of 178 these lines are sometimes used for existing, proprietary, data and 179 testing services. IP delivery therefore becomes one more data 180 service using a subset or all of these lines. 182 3.1.2. 625 Line Systems 184 A 625-line television frame is comprised of two fields of 312.5 185 horizontal scan lines each. The first few lines of each field are 186 used while repositioning the cathode ray to the top of the screen. 187 The lines available for data insertion are 6-22 in the first field 188 and 319-335 in the second field. 190 There are, therefore, 17 possible VBI lines being broadcast 50 times 191 a second (each field 25 times a second), some or all of which could 192 be used for IP transport. It should be noted that some of these 193 lines are sometimes used for existing, proprietary, data and testing 194 services. IP, therefore, becomes one more data service using a 195 subset or all of these lines. 197 3.2. NABTS 199 The North American Basic Teletext Standard is defined in the 200 Electronic Industry Association's EIA-516, Ref. [2], and ITU.R 201 BT.653-2, system C, Ref. [13]. It provides an industry-accepted 202 method of modulating data onto the VBI, usually of an NTSC signal. 203 This section describes the NABTS packet format as it is used for the 204 transport of IP. 206 It should be noted that only a subset of the NABTS standard is used, 207 as is common practice in NABTS implementations. Further information 208 concerning the NABTS standard and its implementation can be found in 209 EIA-516. 211 The NABTS packet is a 36-byte structure encoded onto one horizontal 212 scan line of a television signal having the following structure: 214 |Clock|Byte | Packet |Cont.|Packet | User Data |FEC | 215 |Sync |Sync | Address |Index|Structure| | | 216 | | | | |Flags | | | 217 | 2B | 1B | 3B | 1B | 1B | 26B | 2B | 218 |_____|_____|_____________|_____|_________|___________________|____| 220 Panabaker 4 221 IPVBI February, 1999 223 The two-byte Clock Synchronization and one-byte Byte Synchronization 224 are located at the beginning of every scan line containing a NABTS 225 packet and are used to synchronize the decoding sampling rate and 226 byte timing. 228 The three-byte Packet Address field is Hamming encoded (as specified 229 in EIA-516), provides 4 data bits per byte, and thus provides 4096 230 possible packet addresses. These addresses are used to distinguish 231 related services originating from the same source. This is 232 necessary for the receiver to determine which packets are related, 233 and part of the same service. NABTS packet addresses therefore 234 distinguish different data services, possibly inserted at different 235 points of the transmission system, and most likely totally 236 unrelated. Section 4 of this document discusses Packet Addresses in 237 detail. 239 The one-byte Continuity Index field is a Hamming encoded byte, which 240 is incremented by one for each subsequent packet of a given Packet 241 Address. The index number is determined by position of the packet 242 in the FEC bundle mentioned in the FEC section of this document. 243 The first packet in the bundle has count 0, and the two FEC only 244 packets at the end have counts 14 and 15 respectively. This allows 245 the decoder to determine if packets were lost during transmission. 247 The Packet Structure field is also a Hamming encoded byte, which 248 contains information about the structure of the remaining portions 249 of the packet. The least significant bit is always "0" in this 250 implementation. The second least significant bit specifies if the 251 Data Block is full--"0" indicates the data block is full of useful 252 data, and "1" indicates some or all of the data is filler data. The 253 two most significant bits are used to indicate the length of the 254 suffix of the Data Block--in this implementation, either 2 or 28 255 bytes (10 for 2-bit FEC suffix, 11 for 28-byte FEC suffix). This 256 suffix is used for the forward error correction described in the 257 next section. The following table shows the possible values of the 258 Packet Structure field: 260 Type of Packet PS field value 261 ------------------------------------------------------- 262 Data Packet, no filler D0 263 Data Packet, with filler 8C 264 FEC Packet A1 266 The Data Block field is 26 bytes, zero to 26 of which is useful data 267 (part of a IP packet or SLIP frame), the remainder is filler data. 268 Data is byte-ordered least significant bit first. Filler data is 269 indicated by a 0x15 followed by as many 0xEA as are needed to fill 270 the packet. Sequential data blocks minus the filler data form an 271 asynchronous serial stream of data. 273 These NABTS packets are modulated onto the television signal 274 sequentially and on any combination of lines. 276 Panabaker 5 277 IPVBI February, 1999 279 3.3. FEC 281 Due to the unidirectional nature of VBI data transport, Forward 282 Error Correction (FEC) is needed to ensure the integrity of data at 283 the receiver. The type of FEC described here and in the appendix of 284 this document for NABTS has been in use for a number of years, and 285 has proven popular with the broadcast industry. It is capable of 286 correcting single-byte errors and single- and double-byte erasures 287 in the data block and suffix of a NABTS packet. 289 In a system using NABTS, the FEC algorithm splits a serial stream of 290 data into 364-byte "bundles". These are arranged as 14 packets of 291 26 bytes each. A function is applied to the 26 bytes of each packet 292 to determine the two suffix bytes, which (with the addition of a 293 header) complete the NABTS packet (8+26+2). 295 For every 14 packets in the bundle, two additional packets are 296 appended which contain only FEC data. That is, they contain 28 297 bytes of FEC data. This data is obtained by first writing the 298 packets into a table of 16 rows and 28 columns. The same expression 299 as above can be used on the columns of the table with the suffix now 300 represented by the bytes at the base of the columns in rows 15 and 301 16. With NABTS headers on each of these rows, we now have a bundle 302 of 16 NABTS packets ready for sequential modulation onto lines of 303 the television signal. 305 At the receiver, these formulae can be used to verify the validity 306 of the data with very high accuracy. If single bit errors, double 307 bit errors, single-byte errors or single- and double-byte erasures 308 are found in any row or column (including an entire packet lost) 309 they can be corrected using the algorithms found in the appendix. 310 The success at correcting errors will depend on the particular 311 implementation used on the receiver. 313 3.4. Framing 315 A framing protocol identical to SLIP is proposed for encapsulating 316 the packets described in the following section, thus abstracting 317 this data from the lower protocol layers. This protocol uses two 318 special characters: END (0xc0) and ESC (0xdb). To send a packet, 319 the host will send the packet followed by the END character. If a 320 data byte in the packet is the same code as END character, a two- 321 byte sequence of ESC (0xdb) and 0xdc is sent instead. If a data 322 byte is the same code as ESC character, a two-byte sequence of ESC 323 (0xdb) and 0xdd is sent instead. SLIP implementations are widely 324 available, see RFC 1055 [Romkey 1988] for more detail. 326 +--------------+--+------------+--+--+---------+--+ 327 | packet |c0| packet |db|dd| |c0| 328 +--------------+--+------------+--+--+---------+--+ 329 END ESC END 331 Panabaker 6 332 IPVBI February, 1999 334 The packet framed in this manner shall be formatted according to its 335 schema type identified by the schema field, which shall start every 336 packet: 338 +-----------+---------------------------------------------+ 339 | schema | packet (formatted according to schema) | 340 | 1B | ??B (schema dependant length) | 341 +-----------+---------------------------------------------+ 343 In the case where the most significant bit in this field 344 is set to "1", the length of the field extends to two bytes, 345 allowing for 32768 additional schemas: 347 +-----------+---------------------------------------------+ 348 | extended | packet (formatted according to schema) | 349 | schema | ??B (schema dependant length) | 350 | 2B | | 351 +-----------+---------------------------------------------+ 353 In the following section, one such schema for sending IP is 354 described. This is the only schema specified by this document. 355 Additional schemas may be proposed for other packet types or other 356 compression schemes as described in section 7. 358 3.5. IP Header Compression Scheme 360 The one-byte scheme defines the format for encoding the IP packet 361 itself. Due to the value of bandwidth, it may be desirable to 362 introduce as much efficiency as possible in this encoding. One such 363 efficiency is the optional compression of the UDP/IP header using a 364 method similar to the TCP/IP header compression as described by Van 365 Jacobson (RFC 1144). UDP/IP header compression is not identical due 366 to the limitation of unidirectional transmission. One such scheme 367 is proposed in this document for the compression of UDP/IP version 368 4. It is assigned a value of 0x00. All future encapsulation 369 schemes should use a unique value in this field. 371 Only schema 0x00 is defined in this document; this schema must be 372 supported by all receivers. In schema 0x00, the format of the IP 373 packet itself takes one of two forms. Packets can be sent with 374 full, uncompressed headers as follows: 376 +----+-------+----------------+---------------+-----------+--------+ 377 | 0 | Group | IP Header | UDP Header | Payload | CRC | 378 | 1b | 7b | 20B | 8B | <1472B | 4B | 379 | | | (uncompressed) | (uncompressed)| | | 380 +----+-------+----------------+---------------+-----------+--------+ 382 The first byte in the 0x00 scheme is the Compression Key. It is a 383 one-byte value: the first bit indicates if the header has been 384 compressed, and the remaining seven bits indicate the compression 386 Panabaker 7 387 IPVBI February, 1999 389 group it belongs to. If the high bit of the Compression Key is set 390 to "0", no compression is performed and the full header is sent, as 391 shown above. The client VBI interface should store the uncompressed 392 header for future potential use in rebuilding subsequent compressed 393 headers. Packets with identical group bits are assumed to have 394 identical UDP/IP headers, with the exception of the "IP 395 identification" and "UDP checksum" fields. 397 If the high bit of the Compression Key is set to 1, a compressed 398 version of the UDP/IP header is sent. The client VBI interface must 399 then combine the compressed header with the stored uncompressed 400 header of the same group and recreate a full packet. For compressed 401 packets, the only portions of the UDP/IP header sent are the "IP 402 identification" and "UDP checksum" fields: 404 +----+-------+----------------+---------------+-----------+--------+ 405 | 1 | Group | IP | UDP checksum | Payload | CRC | 406 | 1b | 7b | identification | 4B | <1472B | 4B | 407 | | | 4B | | | | 408 +----+-------+----------------+---------------+-----------+--------+ 410 All datagrams belonging to a multi fragment IP packet shall be sent 411 with full headers, in the uncompressed header format. Therefore, 412 only packets that have not been fragmented can be sent with the most 413 significant bit of the compression key set to "1". 415 A 32-bit CRC has also been added to the end of every packet in this 416 scheme to ensure data integrity. It is performed over the entire 417 packet including schema byte, compression key, and either compressed 418 or uncompressed headers. It uses the same algorithm as the MPEG-2 419 transport stream (ISO/IEC 13818-1). The generator polynomial is: 421 1 + D + D2 + D4 + D5 + D7 + D8 + D10 + D11 + D12 + D16 + D22 + D23 + 422 D26 + D32 424 As in the ISO/IEC 13818-1 specification, the initial state of the 425 sum is 0xFFFFFFFF. This is not the same algorithm used by Ethernet. 426 This CRC provides a final check for damaged datagrams that spanned 427 FEC bundles or were not properly corrected by FEC. 429 4. Addressing Considerations 431 The addressing of IP packets should adhere to existing standards in 432 this area. The inclusion of an appropriate source address is needed 433 to ensure the receiving client can distinguish between sources and 434 thus services if multiple hosts are sharing an insertion point and 435 NABTS packet address. 437 NABTS packet addressing is not regulated or standardized and 438 requires care to ensure that unrelated services on the same channel 439 are not broadcasting with the same packet address. This could occur 440 due to multiple possible NABTS insertion sites, including show 442 Panabaker 8 443 IPVBI February, 1999 445 production, network redistribution, regional operator, and local 446 operator. Traditionally, the marketplace has recognized this 447 concern and made amicable arrangements for the distribution of these 448 addresses for each channel. 450 5. IANA Considerations 452 IANA will register new schemes for header compression on a "First 453 Come First Served" basis [RFC 2434]. Anyone can register a scheme, 454 so long as they provide a point of contact and a brief description. 455 The scheme number will be assigned by IANA. Registrants are 456 encouraged to publish complete specifications for new schemes 457 (preferably as standards-track RFCs), but this is not required. 459 6. Security considerations 461 As with any broadcast network, there are security issues due to the 462 accessibility of data. It is assumed that the responsibility for 463 securing data lies in the application layer protocol, which is 464 beyond the scope of this document. 466 7. Conclusions 468 This document provides a method for broadcasting Internet data over 469 a television signal for reception by client devices. With an 470 appropriate broadcast content model, this will become an attractive 471 method of providing data services to end users. By using existing 472 standards and a layered protocol approach, this document has also 473 provided a model for data transmission on unidirectional and 474 broadcast networks. 476 8. Acknowledgements 478 The description of the FEC in Appendix A is taken from a document 479 prepared by Trevor Dee of Norpak Corporation. 481 9. References 483 [1] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC 484 1112, 17 pages (Aug.). 486 [2] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: 487 North American Basic Teletext Specification (NABTS)" Washington: 488 Electronic Industries Association, c1988 490 [3] Jack, Keith. "Video Demystified: A Handbook for the Digital 491 Engineer, Second Edition," San Diego: HighText Pub. c1996. 493 Panabaker 9 494 IPVBI February, 1999 496 [4] Jacobson, V. 1990a. "Compressing TCP/IP Headers for Low-Speed 497 Serial Links," RFC 1144, 43 pages (Feb.). 499 [5] Narten, T. Alvestrand, H. 1998. "Guidelines for Writing an IANA 500 Considerations Section in RFCs," RFC 2434, (Oct.). 502 [6] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 503 Kanata, Ontario, Canada 505 [7] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 506 Software User's Manual." c1996, Kanata, Ontario, Canada 508 [8] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 509 Ontario, Canada 511 [9] Romkey, J. L. 1988. "A Nonstandard for Transmission of IP 512 Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June). 514 [10] Stevens, W. Richard. "TCP/IP Illustrated, Volume 1,: The 515 Protocols" Reading: Addison-Wesley Publishing Company, c1994. 517 [11] Recommended Practice for Line 21 Data Service (ANSI/EIA-608-94) 518 (Sept., 1994) 520 [12] International Telecommunications Union Recommendation. 521 ITU-R BT.470-5 (02/98) "Conventional TV Systems" 523 [13] International Telecommunications Union Recommendation. 524 ITU.R BT.653-2, system C 526 10. Acronyms 528 VBI - Vertical Blanking Interval 529 FEC - Forward Error Correction 530 NABTS - North American Basic Teletext Standard 531 NTSC - National Television Standards Committee 532 PAL - Phase Alternation Line 533 SECAM - Sequentiel Couleur Avec Memoire (sequential color 534 with memory) 535 NTSC-J - NTSC-Japanese 536 RFC - Request for Comments 537 IP - Internet Protocol 538 UDP - User Datagram Protocol 539 TCP - Transmission Control Protocol 540 SLIP - Serial Line Internet Protocol 541 WST - World System Teletext 543 11. Editors' address and contacts 545 Ruston Panabaker, co-editor 546 Microsoft 548 Panabaker 10 549 IPVBI February, 1999 551 One Microsoft Way 552 Redmond, WA 98052 553 i-rustop@microsoft.com 555 Simon Wegerif, co-editor 556 Philips Semiconductors 557 811 E. Arques Avenue 558 M/S 52, P.O. Box 3409 559 Sunnyvale, CA 94088-3409 560 Simon.Wegerif@sv.sc.philips.com 562 Dan Zigmond, WG Chair 563 WebTV Networks 564 One Microsoft Way 565 Redmond, WA 98052 566 djz@corp.webtv.net 568 12. Appendix A: Forward Error Correction Specification 570 This FEC is optimized for data carried in the VBI of a television 571 signal. Teletext has been in use for many years and data 572 transmission errors have been categorized in to three main types: 573 1) Randomly distributed single bit errors 574 2) Loss of lines of NABTS data 575 3) Burst Errors 577 The quantity and distribution of these errors is highly variable and 578 dependent on many factors. The FEC is designed to fix all these 579 types of errors. 581 12.1. Mathematics used in the FEC 583 Galois fields form the basis for the FEC algorithm presented here. 584 Rather then explain these fields in general, a specific explanation 585 is given of the Galois field used in the FEC algorithm. 587 The Galois field used is GF(2^8) with a primitive element alpha of 588 00011101. This is a set of 256 elements, along with the operations 589 of "addition", "subtraction", "division", and "multiplication" on 590 these elements. An 8-bit binary number represents each element. 592 The operations of "addition" and "subtraction" are the same for this 593 Galois field. Both operations are the XOR of two elements. Thus, 594 the "sum" of 00011011 and 00000111 is 00011100. 596 Division of two elements is done using long division with 597 subtraction operations replaced by XOR. For multiplication, 598 standard long multiplication is used but with the final addition 599 stage replaced with XOR. 601 Panabaker 11 602 IPVBI February, 1999 604 All arithmetic in the following FEC is done modulo 100011101; for 605 instance, after you multiply two numbers, you replace the result 606 with its remainder when divided by 100011101. There are 256 values 607 in this field (256 possible remainders), the 8-bit numbers. It is 608 very important to remember that when we write A*B = C, we more 609 accurately imply modulo(A*B) = C. 611 It is obvious from the above description that multiplication and 612 division is time consuming to perform. Elements of the Galois Field 613 share two important properties with real numbers. 615 A*B = POWERalpha(LOGalpha(A) + LOGalpha(B)) 616 A/B = POWERalpha(LOGalpha(A) - LOGalpha(B)) 618 The Galois Field is limited to 256 entries so the power and log 619 tables are limited to 256 entries. The addition and subtraction 620 shown is standard so the result must be modulo alpha. Written as a 621 "C" expression: 623 A*B = apower[alog[A] + alog[B]] 624 A/B = apower[255 + alog[A] - alog[B]] 626 You may note that alog[A] + alog[B] can be greater than 255 and 627 therefore a modulo operation should be performed. This is not 628 necessary if the power table is extended to 512 entries by repeating 629 the table. The same logic is true for division as shown. The power 630 and log tables are calculated once using the long multiplication 631 shown above. 633 12.2. Calculating FEC bytes 635 The FEC algorithm splits a serial stream of data into "bundles". 636 These are arranged as 16 packets of 28 bytes when the correction 637 bytes are included. The bundle therefore has 16 horizontal 638 codewords interleaved with 28 vertical codewords. Two sums are 639 calculated for a codeword, S0 and S1. S0 is the sum of all bytes of 640 the codeword each multiplied by alpha to the power of its index in 641 the codeword. S1 is the sum of all bytes of the codeword each 642 multiplied by alpha to the power of three times its index in the 643 codeword. In "C" the sum calculations would look like: 645 Sum0 = 0; 646 Sum1 = 0; 647 For(i = 0;i < m;i++) 648 { 649 if(codeword[i] != 0) 650 { 651 Sum0 = sum0 ^ power[i + alog[codeword[i]]]; 652 Sum1 = sum1 ^ power[3*i + alog[codeword[i]]]; 653 } 654 } 656 Panabaker 12 657 IPVBI February, 1999 659 Note that the codeword order is different from the packet order. 660 Codeword positions 0 and 1 are the suffix bytes at the end of a 661 packet horizontally or at the end of a column vertically. 663 When calculating the two FEC bytes, the summation above must produce 664 two sums of zero. All codewords except 0 and 1 are know so the sums 665 for the known codewords can be calculated. Let's call these values 666 tot1 and tot2. 668 Sum0=0=tot0^power[0+alog[codeword[0]]]^power[1+alog[codeword[1]]] 669 sum1=0=tot1^power[0+alog[codeword[0]]]^power[3+alog[codeword[1]]] 671 This gives us two equations with the two unknowns that we can solve: 673 codeword[1]=power[255+alog[tot0^tot1]-alog[power[1]^power[3]]] 674 codeword[0]=tot0^power[alog[codeword[1]]+alog[power[1]]] 676 12.3. Correcting Errors 678 This section describes the procedure for detecting and correcting 679 errors using the FEC data calculated above. Upon reception, we 680 begin by rebuilding the bundle. This is perhaps the most important 681 part of the procedure because if the bundle is not built correctly 682 it cannot possibly correct any errors. The continuity index is used 683 to determine the order of the packets and if any packets are missing 684 (not captured by the hardware). The recommendation, when building 685 the bundle, is to convert the bundle from packet order to codeword 686 order. This conversion will simplify the codeword calculations. 687 This is done by taking the last byte of a packet and making it the 688 second byte of the codeword and taking the second last byte of a 689 packet and making it the first byte of a codeword. Also the packet 690 with continuity index 15 becomes codeword position one and the 691 packet with continuity index 14 becomes codeword position zero. 693 The same FEC is used regardless of the number of bytes in the 694 codeword. So let's think of the codewords as an array 695 codeword[vert][hor] where vert is 16 packets and hor is 28. Each 696 byte in the array is protected by both a horizontal and a vertical 697 codeword. For each of the codewords, the sums must be calculated. 698 If both the sums for a codeword are zero then no errors have been 699 detected for that codeword. Otherwise an error has been detected 700 and further steps need to be taken to see if the error can be 701 corrected. In "C" the horizontal summation would look like: 703 for(i = 0;i < 16;i++) 704 { 705 Sum0 = 0; 706 Sum1 = 0; 707 for(j = 0;j < hor;j++) 708 { 709 If(codeword[i][j] != 0) 710 { 712 Panabaker 13 713 IPVBI February, 1999 715 Sum0 = sum0 ^ power[j + alog[codeword[i][j]]; 716 Sum1 = sum1 ^ power[3*j + alog[codeword[i][j]]; 717 } 718 } 719 if((sum0 != 0) || (sum1 != 0)) 720 { 721 Try Correcting Packet 722 } 723 } 725 Similarly, vertical looks like: 727 for(j = 0;i < hor;i++) 728 { 729 Sum0 = 0; 730 Sum1 = 0; 731 for(i = 0;i < 16;i++) 732 { 733 If(codeword[i][j] != 0) 734 { 735 Sum0 = sum0 ^ power[i + alog[codeword[i][j]]; 736 Sum1 = sum1 ^ power[3*i + alog[codeword[i][j]]; 737 } 738 } 739 if((sum0 != 0) || (sum1 != 0)) 740 { 741 Try Correcting Column 742 } 743 } 745 12.4. Correction Schemes 747 This FEC provides four possible corrections: 749 1) Single bit correction in codeword. All single bit errors. 750 2) Double bit correction in a codeword. Most two-bit errors. 751 3) Single byte correction in a codeword. All single-byte errors. 752 4) Packet replacement. One or two missing packets from a bundle. 754 12.4.1. Single Bit Correction 756 When correcting a single-bit in a codeword, the byte and bit 757 position must be calculated. The equations are: 759 Byte = 1/2LOGalpha(S1/S0) 760 Bit = 8LOGalpha(S0/POWERalpha(Byte)) 762 In "C" this is written: 764 Byte = alog[power[255 + alog[sum1] - alog[sum0]]]; 765 if(Byte & 1) 767 Panabaker 14 768 IPVBI February, 1999 770 Byte = Byte + 255; 771 Byte = Byte >> 1; 772 Bit = alog[power[255 + alog[sum0] - Byte]] << 3; 773 while(Bit > 255) 774 Bit = Bit - 255; 776 The error is correctable if Byte is less than the number of bytes in 777 the codeword and Bit is less than eight. For this math to be valid 778 both sum0 and sum1 must be non-zero. The codeword is corrected by: 780 codeword[Byte] = codeword[Byte] ^ (1 << Bit); 782 12.4.2. Double Bit Correction 784 Double bit correction is much more complex than single bit 785 correction for two reasons. First, not all double bit errors are 786 deterministic. That is two different bit patterns can generate the 787 same sums. Second, the solution is iterative. To find two bit 788 errors you assume one bit in error and then solve for the second 789 error as a single bit error. 791 The procedure is to iteratively move through the bits of the 792 codeword changing each bit's state. The new sums are calculated for 793 the modified codeword. Then the single bit calculation above 794 determines if this is the correct solution. If not, the bit is 795 restored and the next bit is tried. 797 For a long codeword, this can involve many calculations. However, 798 tricks can speed the process. For example, the vertical sums give a 799 strong indication of which bytes are in error horizontally. Bits in 800 other bytes need not be tried. 802 12.4.3. Single Byte Correction 804 For single byte correction, the byte position and bits to correct 805 must be calculated. The equations are: 807 Byte = 1/2*LOGalpha(S1/S0) 808 Mask = S0/POWERalpha[Byte] 810 Notice that the byte position is the same calculation as for single 811 bit correction. The mask will allow more than one bit in the byte 812 to be corrected. In "C" the mask calculation looks like: 814 Mask = power[255 + alog[sum0] - Byte] 816 Both sum0 and sum1 must be non-zero for the calculations to be 817 valid. The Byte value must be less than the codeword length but 818 Mask can be any value. This corrects the byte in the codeword by: 820 Codeword[Byte] = Codeword[Byte] ^ Mask 822 Panabaker 15 823 IPVBI February, 1999 825 12.4.4. Packet Replacement 827 If a packet is missing, as determined by the continuity index, then 828 its byte position is known and does not need to be calculated. The 829 formula for single packet replacement is therefore the same as for 830 the Mask calculation of single byte correction. Instead of XORing 831 an existing byte with the Mask, the Mask replaces the missing 832 codeword position: 834 Codeword[Byte] = Mask 836 When two packets are missing, both the codeword positions are known 837 by the continuity index. This again gives two equations with two 838 unknowns, which is solved to give the following equations. 840 Mask2 = POWERalpha(2*Byte1)*S0+S1 841 ------------------------------- 842 POWERalpha(2*Byte1+Byte2) +POWERalpha(3*BYTE2) 844 Mask1 = S0 + Mask2*POWERalpha(Byte2)/POWERalpha(BYTE1) 846 In "C" these equations are written: 848 if(sum0 == 0) 849 { 850 if(sum1 == 0) 851 mask2 = 0; 852 else 853 mask2=power[255+alog[sum1]-alog[power[byte2+2*byte1]^ 854 power[3*Byte2]]]; 855 } 856 else 857 { 858 if((a=sum1^power[alog[sum0]+2*byte1]) == 0) 859 mask2 = 0; 860 else 861 mask2 = power[255+alog[a]-alog[power[byte2+2*byte1]^ 862 power[3*byte2]]]; 863 } 864 if(mask2 = 0) 865 { 866 if(sum0 == 0) 867 mask1 = 0; 868 else 869 mask1 = power[255+alog[sum0]-byte1]; 870 } 871 else 872 { 873 if((a=sum0^power[alog[mask2] + byte2]) == 0) 874 mask1 = 0; 875 else 877 Panabaker 16 878 IPVBI February, 1999 880 mask1 = power[255+alog[a]-byte1]; 881 } 883 Notice that, in the code above, care is taken to check for zero 884 values. The missing codeword position can be fixed by: 886 codeword[byte1] = mask1; 887 codeword[byte2] = mask2; 889 12.5. FEC Performance Considerations 891 The section above shows how to correct the different types of 892 errors. It does not suggest how these corrections may be used in an 893 algorithm to correct a bundle. There are many possible algorithms 894 and the one chosen depends on many variables. These include: 896 . The amount of processing power available. 897 . The number of packets per VBI to process. 898 . The type of hardware capturing the data. 899 . The delivery path of the VBI. 900 . How the code is implemented. 902 As a minimum, it is recommended that the algorithm use single bit or 903 single byte correction for one pass in each direction followed by 904 packet replacement if appropriate. It is possible to do more than 905 one pass of error correction in each direction. The theory is that 906 errors not corrected in the first pass may be corrected in the 907 second pass because error correction in the other direction has 908 removed some errors. 910 In making choices, it is important to remember that the code has 911 several possible states: 913 1)Shows codeword as correct and it is. 914 2)Shows codeword as correct and it is not (detection failure). 915 3)Shows codeword as incorrect but cannot correct (detection). 916 4)Shows codeword as incorrect and corrects it correctly 917 (correction). 918 5)Shows codeword as incorrect but corrects wrong bits (false 919 correction). 921 There is actually overlap among the different types of errors. For 922 example, a pair of sums may indicate both a double bit error and a 923 byte error. It is not possible to know at the code level which is 924 correct and which is a false correction. In fact, neither might be 925 correct if both are false corrections. 927 If you know something about the types of errors in the delivery 928 channel, you can greatly improve efficiency. If you know that 929 errors are randomly distributed (as in a weak terrestrial broadcast) 930 then single and double bit correction are more powerful than single 931 byte. 933 Panabaker 17 934 IPVBI February, 1999 936 12.6. Appendix References 938 [1] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 939 Kanata, Ontario, Canada 941 [2] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 942 Software User's Manual." c1996, Kanata, Ontario, Canada 944 [3] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 945 Ontario, Canada 947 [4] Pretzel, Oliver. "Correcting Codes and Finite Fields: Student 948 Edition" OUP, c1996 950 [5] Rorabaugh, C. Britton. "Error Coding Cookbook" McGraw Hill, 951 c1996 953 [6] Mortimer, Brian. "An Error-correction system for the Teletext 954 Transmission in the Case of Transparent Data" c1989 Department of 955 Mathematics and Statistics, Carleton University, Ottawa Canada 957 13. Appendix B: Architecture 959 The architecture that this document is addressing can be broken down 960 into three areas: insertion, distribution network, and receiving 961 client. 963 The insertion of IP data onto the television signal can occur at any 964 part of the delivery system. A VBI encoder typically accepts a 965 video signal and an asynchronous serial stream of framed IP as 966 inputs and packetizes the data onto a selected set of lines using 967 NABTS and an FEC. This composite signal is then modulated with 968 other channels before being broadcast onto the distribution network. 969 Operators further down the distribution chain could then add their 970 own data, to other unused lines, as well. 972 The distribution networks include coax plant, off-air, and analog 973 satellite systems and are primarily unidirectional broadcast 974 networks. They must provide a signal to noise ratio, which is 975 sufficient for FEC to recover any lost data for the broadcast of 976 data to be effective. 978 The receiving client must be capable of tuning, NABTS waveform 979 sampling as appropriate, filtering on NABTS addresses as 980 appropriate, forward error correction, unframing, verification of 981 the CRC and decompressing the UDP/IP header if they are compressed. 982 All of the above functions can be carried out in PC software and 983 inexpensive off-the-shelf hardware. 985 Panabaker 18 986 IPVBI February, 1999 988 14. Appendix C: Scope of proposed protocols 990 The protocols described in this document are for transmitting IP 991 packets. However, their scope may be extensible to other 992 applications outside this area. Many of the protocols in this 993 document could be implemented on any unidirectional network. 995 The unidirectional framing protocol provides encapsulation of IP 996 datagrams on the serial stream, and the compression of the UDP/IP 997 headers reduces the overhead on transmission, thus conserving 998 bandwidth. These two protocols could be widely used on different 999 unidirectional broadcast networks or modulation schemes to 1000 efficiently transport any type of packet data. In particular, new 1001 versions of Internet protocols can be supported to provide a 1002 standardized method of data transport. 1004 Panabaker 19