idnits 2.17.1 draft-ietf-ipvbi-nabts-00.txt: ** The Abstract section seems to be numbered -(341): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(492): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(596): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. 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 the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == There are 14 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 2 longer pages, the longest (page 1) being 59 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 17 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 4 instances of lines with control characters in the document. 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 (Oct 1998) is 9297 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 295 -- Looks like a reference, but probably isn't: 'Deering 1989' on line 304 -- Looks like a reference, but probably isn't: 'A' on line 526 -- Looks like a reference, but probably isn't: 'B' on line 526 -- Looks like a reference, but probably isn't: 'Byte' on line 717 == Unused Reference: '7' is defined on line 419, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 422, but no explicit reference was found in the text == Unused Reference: '9' is defined on line 425, 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' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' Summary: 9 errors (**), 0 flaws (~~), 7 warnings (==), 15 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT IPVBI WG editors 2 < draft-ietf-ipvbi-nabts-00.txt > 3 Obsoletes: 4 < draft-ietf-ipvbi-tv-signal-00.txt > Oct 1998 5 Expires in six months 7 THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A 8 TELEVISION SIGNAL 10 1. Status of this Memo 12 This document is an Internet-Draft of the IPVBI working group. 13 Internet-Drafts are working documents of the Internet Engineering Task 14 Force (IETF), its areas, and its working groups. Note that other groups 15 may also distribute working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference material 20 or to cite them other than as "work in progress." 22 To learn the current status of any Internet-Draft, please check the 23 "id-abstracts.txt" listing contained in the Internet-Drafts Shadow 24 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 25 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 26 ftp.isi.deu (US West Coast). 28 2. Abstract 30 This is an Internet-Draft, which describes a method for broadcasting 31 multicast IP data using the vertical blanking interval of television 32 signals. It includes a description for compressing multicast IP headers 33 on unidirectional networks, a framing protocol identical to SLIP, a 34 forward error correction scheme, and the NABTS byte structures. 36 Keywords: VBI, broadcast, push, FEC, television, NABTS, IP, multicast. 38 3. Table of Contents 40 1. Status of this Memo . . . . . . . . . . . . . . . . . . . . . . 1 41 2. Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 42 3. Table of Contents . . . . . . . . . . . . . . . . . . . . . . . 1 43 4. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .2 44 5. Proposed protocol stack . . . . . . . . . . . . . . . . . . . . 2 45 5.1. VBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 46 5.1.1. 525 line systems. . . . . . . . . . . . . . . . . . . . . .4 47 5.2. NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 48 5.3. FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 49 5.4. Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .6 50 5.5. IP compression . . . . . . . . . . . . . . . . . . . . . . . 6 51 6. Addressing Considerations . . . . . . . . . . . . . . . . . . . .7 52 7. Security considerations . . . . . . . . . . . . . . . . . . . . .8 53 8. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . .8 54 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 55 10. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 56 11. Author's address and contacts . . . . . . . . . . . . . . . . . .9 57 12. Appendix A: Forward Error Correction Specification . . . . . . 10 58 12.1. Mathematics used in the FEC . . . . . . . . . . . . . . . . 10 59 12.2. Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 11 60 12.3. Correcting Errors . . . . . . . . . . . . . . . . . . . . . 11 61 12.4. Correction Schemes . . . . . . . . . . . . . . . . . . . . .13 62 12.5 FEC Performance Considerations. . . . . . . . . . . . . . .15 63 12.6. Appendix References . . . . . . . . . . . . . . . . . . . . 16 64 15. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 16 65 16. Scope of proposed protocols . . . . . . . . . . . . . . . . . 17 67 4. Introduction 69 This Internet-Draft proposes several protocols to be used in the 70 transmission of IP datagrams using the Vertical Blanking Interval (VBI) 71 of a television signal. The VBI is a non-viewable portion of the 72 television signal that can be used to provide point-to-multipoint IP 73 data services which will relieve congestion and traffic in the 74 traditional Internet access networks. Wherever possible these 75 protocols make use of existing RFC standards and non-standards. 77 Traditionally, point to point connections (TCP/IP) have been used even 78 for the transmission of broadcast type data. Distribution of the same 79 content - news feeds, stock quotes, newsgroups, weather reports, and 80 the like - are typically sent repeatedly to individual clients rather 81 than being broadcast to the large number of users who want to receive 82 such data. 84 Today, multicast-IP is quickly becoming the preferred method of 85 distributing one-to-many data on Intranets and the Internet. With the 86 coming availability of low cost PC hardware for receiving television 87 signals accompanied by broadcast data streams, it is imperative that a 88 standard be defined for the transmission of data over traditional 89 broadcast networks. A lack of standards in this area as well as the 90 expense of hardware has, in the past, prevented traditional broadcast 91 networks from becoming effective deliverers of data to the home and 92 office. 94 This document describes the transmission of multicast-IP using the 95 North American Basic Teletext Standard (NABTS) a recognized and 96 industry-supported method of transporting data on the VBI. NABTS has 97 traditionally been used on 525 line television systems such as NTSC, 98 and another byte structure, WST, on 625 line systems such as PAL and 99 SECAM, but this generalization has exceptions, and countries should be 100 treated on an individual basis. These existing television system 101 standards will allow the television and Internet communities to provide 102 inexpensive broadcast data services. A set of existing protocols will 103 be layered above the specific FEC for NABTS including a serial stream 104 framing protocol similar to SLIP (RFC 1055 [Romkey 1988]) and a 105 compression technique for unidirectional multicast UDP/IP headers. 107 5. Proposed protocol stack 108 The following protocol stack demonstrates the layers used in the 109 transmission of VBI data. Each layer has no knowledge of the data it 110 encapsulates and is therefore abstracted from the other layers. At the 111 link layer, the NABTS protocol defines the modulation scheme used to 112 transport data on the VBI. At the network layer IP handles the 113 movement of data to the appropriate clients and UDP, in the transport 114 layer, determines the flow of data to the appropriate processes and 115 applications. 117 +-------------------+ 118 | | 119 | Application | 120 | | 121 +-------------------+ 122 | | ) 123 | UDP | ) 124 | | ) 125 +-------------------+ (-- multicast-IP 126 | | ) 127 | IP | ) 128 | | ) 129 +-------------------+ 130 | SLIP style | 131 | encapsulation | 132 | | 133 +-------------------+ 134 | FEC | 135 |-------------------| 136 | NABTS | 137 | | 138 +---------+---------+ 139 | | 140 | NTSC/other | 141 | | 142 +-------------------+ 143 | 144 | 145 | cable, off-air,etc 146 |--------<----<----<-------- 148 These protocols can be described in a bottom up component model using 149 the example of NABTS carried over NTSC modulation as follows: 151 NTSC signal --> NABTS --> FEC --> serial data stream --> Framing 152 protocol --> compressed UDP/IP headers --> application data 154 This diagram can be read as follows: television signals have NABTS 155 packets modulated onto them which contain a Forward Error Correction 156 (FEC) protocol. The data contained in these sequential, ordered 157 packets form a serial data stream on which a framing protocol indicates 158 the location of multicast-IP packets, with compressed headers, 159 containing application data. 161 The structure of these components and protocols are described in 162 following subsections. 164 5.1. VBI 166 The characteristics and definition of the VBI is dependent on the 167 television system in use, be it NTSC, PAL, SECAM or some other. For 168 more information on Television standards worldwide, see ref [11]. 170 5.1.1. 525 line systems (example: NTSC) 172 An NTSC television frame is comprised of 2 fields of 262.5 horizontal 173 scan lines each. The first 21 lines of each field are not part of the 174 visible picture and are collectively called the Vertical Blanking 175 Interval (VBI). Of these 21 lines the first 9 are used while 176 repositioning the cathode ray to the top of the screen, but the 177 remaining lines are available for data transport. 179 Line 21 itself is reserved for the transport of closed captioning data 180 (Ref.[10]). There are therefore 11 possible VBI lines being broadcast 181 60 times a second (each field 30 times a second), some or all of which 182 could be used for multicast IP transport. It should be noted that some 183 of these lines are sometimes used for existing, proprietary, data and 184 testing services. Multicast IP therefore becomes one more data service 185 using a subset or all of these lines. 187 5.2. NABTS 189 The North American Basic Teletext Standard is defined in the 190 Electronics Industry Associations EIA-516. It provides an industry- 191 accepted method of modulating data onto the VBI, usually of an NTSC 192 signal. This section describes the NABTS packet format as it is used 193 for the transport of multicast IP. It should be noted that only a 194 subset of the NABTS standard is used, as is common practice in NABTS 195 implementations. Further information concerning the NABTS standard and 196 its implementation can be found in EIA-516. 198 The NABTS packet is a 36-byte structure encoded onto one horizontal 199 scan line of a television signal having the following structure: 201 ___________________________________________________________________ 202 |Clock|Byte | Packet group|Cont.|Packet | User Data |FEC | 203 |Sync |Sync | Address |Index|Structure| | | 204 | | | | |Flags | | | 205 | 2B | 1B | 3B | 1B | 1B | 26B | 2B | 206 |_____|_____|_____________|_____|_________|___________________|____| 208 The 2 byte Clock Synchronization and the 1 byte Byte Synchronization 209 are located at the beginning of every scan line containing a NABTS 210 packet and are used to synchronize the decoding sampling rate and byte 211 timing. 213 The 3 byte Packet Group address field is Hamming encoded (as specified 214 in EIA-516, and provides 4 data bits per byte, and thus provides 4096 215 possible packet group addresses. These addresses are used to 216 distinguish related services originating from the same source. This is 217 necessary for the receiver to determine which packets are related and 218 part of the same service. NABTS packet group addresses therefore 219 distinguish different data services, possibly inserted at different 220 points of the transmission system, and most likely totally unrelated. 221 Section 6 of this document discusses Packet Group Addresses in greater 222 detail. 224 The 1 byte Continuity Index field is a Hamming encoded byte, which is 225 incremented by one for each subsequent packet of a given Packet Group 226 address. The index number is determined by the packet's order in the 227 FEC bundle mentioned in the FEC section of this document. The first 228 packet in the bundle has count 0, and the two FEC only packets at the 229 end have counts 14 and 15 respectively. This allows the decoder to 230 determine if packets have been lost during transmission. 232 The Packet Structure field is also a Hamming encoded byte, which 233 contains information about the structure of the remaining portions of 234 the packet. The least significant bit is always 0 in this 235 implementation. The second least significant bit specifies whether the 236 Data Block is full (0 indicates the data block is full of useful data, 237 1 indicates some or all of the data is filler data), and the two most 238 significant bits are used to indicate the length of the suffix on the 239 Data Block, in this implementation either 2 or 28 bytes (10 for 2 bit 240 FEC suffix, 11 for 28 byte FEC suffix). This suffix is used for the 241 forward error correction described in the next section. 243 The Data Block field is 26 bytes, 0 to 26 of which is useful data (part 244 of a multicast IP packet or SLIP frame), the remainder being filler 245 data. Data is byte ordered least significant bit first. Filler data 246 is indicated by a 0x15 followed by as many 0xEA as are needed to fill 247 the packet. Sequential data blocks minus the filler data form an 248 asynchronous serial stream of data. 250 These NABTS packets are modulated onto the television signal 251 sequentially and on any combination of lines. 253 5.3. FEC 255 Due to the unidirectional nature of VBI data transport, Forward Error 256 Correction (FEC) is needed to ensure the integrity of data at the 257 receiver. The type of FEC described here and in the appendix of this 258 document for NABTS has been in use for a number of years, and has 259 proven popular with the broadcast industry. It is capable of 260 correcting single byte errors and single and double byte erasures in 261 the data block and suffix of a NABTS packet. 263 In a system using NABTS the FEC algorithm splits a serial stream of 264 data into 364 byte "bundles". These are arranged as 14 packets of 26 265 bytes each. A function is applied to the 26 bytes of each packet to 266 determine the two suffix bytes, which (with the addition of a header) 267 complete the NABTS packet (8+26+2). 269 For every 14 packets in the bundle an additional 2 packets are appended 270 which contain only FEC data. That is, they contain 28 bytes of FEC 271 data. This data is obtained by first writing the packets into a table 272 of 16 rows and 28 columns. The same expression as above can be used on 273 the columns of the table with the suffix now represented by the bytes 274 at the base of the columns in rows 15 and 16. With NABTS headers on 275 each of these rows, we now have a bundle of 16 NABTS packets ready for 276 sequential modulation onto lines of the television signal. 278 At the receiver these formulae can be used to verify the validity of 279 the data with very high accuracy. If single byte errors or single and 280 double byte erasures are found in any row or column (including an 281 entire packet lost) they can be corrected using the algorithms found in 282 the appendix. The success at correcting errors will depend on the 283 particular implementation used on the receiver. 285 5.4. Framing 287 A framing protocol identical to SLIP is proposed for encapsulating IP 288 datagrams, thus abstracting this data from the lower protocol layers. 289 This protocol uses two special characters: END (0xc0) and ESC (0xdb). 290 To send a packet, the host will send the packet followed by the END 291 character. If a data byte in the packet is the same code as END 292 character, a two byte sequence of ESC (0xdb) and 0xdc is sent instead. 293 If a data byte is the same code as ESC character, a two-byte sequence 294 of ESC (0xdb) and 0xdd is sent instead. SLIP implementations are 295 widely available, see RFC 1055 [Romkey 1988] for more detail. 297 +--------------+--+------------+--+--+---------+--+ 298 |IP packet |c0| IP packet |db|dd| |c0| 299 +--------------+--+------------+--+--+---------+--+ 300 END ESC END 302 5.5. IP compression 304 Finally we have the multicast IP packet (RFC 1112 [Deering 1989]). Due 305 to the value of bandwidth, it may be desirable to introduce as much 306 efficiency as possible. One such efficiency is the optional 307 compression of the multicast UDP/IP header using a method similar to 308 the TCP/IP header compression as described by Van Jacobson (RFC 1144). 309 UDP/IP header compression is not identical due to the limitation of 310 unidirectional transmission. 312 The following two packet formats are used in a compression scheme which 313 builds index tables on the client using occasionally transmitted full 314 headers to rebuild packets sent with compressed headers: 316 [schema:8][0:1][Index:7][full headers:224][data][CRC:32] 317 [schema:8][1:1][Index:7][compressed header:32][data][CRC:32] 319 The first byte of all packets is the schema type. This field is used 320 to identify the compression scheme that is being used. One such scheme 321 is proposed in this document for the compression of UDP/IP version 4. 322 It is assigned a value of 00000000. All future encapsulation schemes 323 should use a unique value in this field. In the case where the most 324 significant bit in this field is set to 1, the length of the field 325 extends to two bytes, allowing for 32768 additional schemas. 327 The next byte in the 00000000 scheme is the Compression Key. It is a 328 one byte value, the first bit indicates if the header has been 329 compressed, and the remaining seven bits indicate the compression group 330 it belongs to. If the high bit of the Compression Key is set to 0, no 331 compression is performed and the full header is sent. The client VBI 332 interface should store the uncompressed header for future potential use 333 in rebuilding subsequent compressed headers. 335 If the high bit of the Compression Key is set to 1, a compressed 336 version of the UDP/IP header is sent. The client VBI interface must 337 then combine the compressed header with the stored uncompressed header 338 and recreate a full packet. 340 When uncompressed, the entire UDP/IP header is sent. When compressed, 341 only the "IP identification", and �UDP checksum� fields are sent. The 342 client VBI interface should combine these with the previously saved 343 header. 345 [0:1][Group:7][IP header:160][UDP header:64] 346 [1:1][Group:7][IP identification:16][UDP checksum:16] 348 All datagrams belonging to a multi fragment IP packet shall be sent 349 with full headers, in the uncompressed header format. Therefore, only 350 packets that have not been fragmented can be sent with the most 351 significant bit of the compression key set to 1. 353 A 32 bit CRC has also been added to the end of every packet in this 354 scheme to ensure data integrity. It is performed over the entire 355 packet including schema byte, compression key, and either compressed or 356 uncompressed headers. It uses the same algorithm as the MPEG-2 357 transport stream (ISO/IEC 13818-1). The generator polynomial is: 359 1 + D + D2 + D4 + D5 + D7 + D8 + D10 + D11 + D12 + D16 + D22 + D23 + 360 D26 + D32 362 As in the ISO/IEC 13818-1 specification, the initial state of the sum 363 is 0xFFFFFFFF. This is not the same algorithm used by Ethernet. This 364 CRC provides a final check for damaged datagrams, which spanned FEC 365 bundles or were not corrected properly by FEC. 367 6. Addressing Considerations 368 The addressing of multicast IP packets should adhere to existing 369 standards in this area. The inclusion of an appropriate source address 370 is needed to ensure the receiving client can distinguish between 371 sources and thus services if multiple hosts are sharing an insertion 372 point and NABTS packet group address. 374 NABTS packet addressing is not regulated or standardized and requires 375 care to ensure that unrelated services on the same channel are not 376 broadcasting with the same packet group address. This could occur due 377 to multiple possible NABTS insertion sites, including show production, 378 network redistribution, regional operator, and local operator. 379 Traditionally the marketplace has recognized this concern and made 380 amicable arrangements for the distribution of these addresses for each 381 channel. 383 7. Security considerations 385 As with any broadcast network, there are security issues due to the 386 accessibility of data. It is assumed that the responsibility for 387 securing data lies in the application layer protocol, which is beyond 388 the scope of this document. 390 8. Conclusions 392 This document provides a method for broadcasting Internet data over a 393 television signal for reception by client devices. With an appropriate 394 "push and filter" content model, this will become an attractive method 395 of providing data services to end users. By using existing standards 396 and a layered protocol approach, this document has also provided a 397 model for data transmission on unidirectional and broadcast networks. 399 9. References 401 [1] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC 402 1112, 17 pages (Aug.). 404 [2] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: North 405 American Basic Teletext Specification (NABTS)" Washington: Electronic 406 Industries Association, c1988 408 [3] Jack, Keith. "Video Demystified: A Handbook for the Digital 409 Engineer, Second Edition," San Diego: HighText Pub. c1996. 411 [4] Jacobson, V. 1990a. "Compressing TCP/IP Headers for Low-Speed 412 Serial Links," RFC 1144, 43 pages (Feb.). 414 [5] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 415 Kanata, Ontario, Canada 417 [6] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 418 Software User's Manual." c1996, Kanata, Ontario, Canada 419 [7] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 420 Ontario, Canada 422 [8] Romkey, J. L. 1988. "A Nonstandard for Transmission of IP 423 Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June). 425 [9] Stevens, W. Richard. "TCP/IP Illustrated, Volume 1,: The 426 Protocols" Reading: Addison-Wesley Publishing Company, c1994. 428 [10] Recommended Practice for Line 21 Data Service (ANSI/EIA-608-94) 429 (Sept., 1994) 431 [11] International Telecommunications Union Recommendation. 432 ITU-R BT.470-5 (02/98) "Conventional TV Systems" 434 10. Acronyms 436 VBI - Vertical Blanking Interval 437 FEC - Forward Error Correction 438 NABTS - North American Basic Teletext Standard 439 NTSC - National Television Standards Committee 440 PAL - Phase Alternation Line 441 SECAM - Sequentiel Couleur Avec Memoire (sequential color with 442 memory) 443 NTSC-J - Japanese flavor of NTSC 444 RFC - Request For Comments 445 IP - Internet Protocol 446 UDP - User Datagram Protocol 447 TCP - Transmission Control Protocol 448 SLIP - Serial Line Internet Protocol 449 WST - World System Teletext 451 11. Author's address and contacts 453 Ruston Panabaker, co-editor 454 Microsoft 455 One Microsoft Way 456 Redmond, WA 98052 457 i-rustop@microsoft.com 459 Simon Wegerif, co-editor 460 Philips Semiconductors 461 811 E. Arques Avenue 462 M/S 52, P.O. Box 3409 463 Sunnyvale, CA 94088-3409 464 Simon.Wegerif@sv.sc.philips.com 466 Dan Zigmond, WG Chair 467 WebTV Networks 468 305 Lytton Avenue 469 Palo Alto, CA 94301 470 Djz@corp.webtv.net 472 12. Appendix A: Forward Error Correction Specification 474 This FEC is optimized for data carried in the VBI of a television 475 signal. Teletext has been in use for many years and data transmission 476 errors have been categorized in to three main types: 477 1) Randomly distributed single bit errors 478 2) Packet loss 479 3) Burst Errors 480 The quantity and distribution of these errors is highly variable and 481 dependent on many factors. The FEC is designed to fix all these types 482 of errors. 484 12.1. Mathematics used in the FEC 486 Galois fields form the basis for the FEC algorithm presented here. 487 Rather then explain these fields in general, a specific explanation is 488 given of the Galois field used in the FEC algorithm. 490 The Galois field used is GF(2^8) with a primitive element alpha of 491 00011101. This is a set of 256 elements, along with the operations of 492 "addition", �subtraction�, �division� and "multiplication" on these 493 elements. An 8 bit binary number represents each element. 495 The operations of "addition" and �subtraction� are the same for this 496 Galois field. Both operations are the XOR of two elements. Thus, the 497 "sum" of 00011011 and 00000111 is 00011100. 499 Division of two elements is done using long division with subtraction 500 operations replaced by XOR. For multiplication, standard long 501 multiplication is used but with the final addition stage replaced with 502 XOR. 504 All arithmetic in the following FEC is done modulo 100011101; for 505 instance, after you multiply two numbers, you replace the result with 506 its remainder when divided by 100011101. There are 256 values in this 507 field (256 possible remainders), the 8-bit numbers. It is very 508 important to remember that when we write A*B = C, we more accurately 509 imply modulo(A*B) = C. 511 It is obvious from the above description that multiplication and 512 division is time consuming to perform. Elements of the Galois Field 513 share two important properties with real numbers. 515 A*B = POWERalpha(LOGalpha(A) + LOGalpha(B)) 516 A/B = POWERalpha(LOGalpha(A) - LOGalpha(B)) 518 The Galois Field is limited to 256 entries so the power and log tables 519 are limited to 256 entries. The addition and subtraction shown is 520 standard so the result must be modulo alpha. Written as a �C� 521 expression: 523 A*B = apower[alog[A] + alog[B]] 524 A/B = apower[255 + alog[A] - alog[B]] 526 You may note that alog[A] + alog[B] can be greater than 255 and 527 therefore a modulo operation should be performed. This is not 528 necessary if the power table is extended to 512 entries by repeating 529 the table. The same logic is true for division as shown. The power 530 and log tables are calculated once using the long multiplication shown 531 above. 533 12.2. Calculating FEC bytes 535 The FEC algorithm splits a serial stream of data into "bundles". These 536 are arranged as 16 packets of 28 bytes when the correction bytes are 537 included. The bundle therefore has 16 horizontal codewords interleaved 538 with 28 vertical codewords. Two sums are calculated for a codeword; S0 539 and S1. S0 is the sum of all bytes of the codeword each multiplied by 540 alpha to the power of its index in the codeword. S1 is the sum of all 541 bytes of the codeword each multiplied by alpha to the power of three 542 times its index in the codeword. In �C� the sum calculations would 543 look like: 545 Sum0 = 0; 546 Sum1 = 0; 547 For(i = 0;i < m;i++) 548 { 549 if(codeword[i] != 0) 550 { 551 Sum0 = sum0 ^ power[i + alog[codeword[i]]]; 552 Sum1 = sum1 ^ power[3*i + alog[codeword[i]]]; 553 } 554 } 556 Note that the codeword order is different from the packet order. 557 Codeword positions 0 and 1 are the suffix bytes at the end of a packet 558 horizontally or at the end of a column vertically. 560 When calculating the two FEC bytes, the summation above must produce 561 two sums of zero. All codewords except 0 and 1 are know so the sums 562 for the known codewords can be calculated. Let�s call these values 563 tot1 and tot2. 565 Sum0=0=tot0^power[0+alog[codeword[0]]]^power[1+alog[codeword[1]]] 566 sum1=0=tot1^power[0+alog[codeword[0]]]^power[3+alog[codeword[1]]] 568 This gives us two equations with the two unknowns which we can solve: 570 codeword[1]=power[255+alog[tot0^tot1]-alog[power[1]^power[3]]] 571 codeword[0]=tot0^power[alog[codeword[1]]+alog[power[1]]] 573 12.3. Correcting Errors 574 This section describes the procedure for detecting and correcting 575 errors using the FEC data calculated above. Upon reception we begin by 576 rebuilding the bundle. This is perhaps the most important part of the 577 procedure because if the bundle is not built correctly it cannot 578 possibly correct any errors. The continuity index is used to determine 579 the order of the packets and whether any packets are missing (not 580 captured by the hardware). The recommendation, when building the 581 bundle is to convert the bundle from packet order to codeword order. 582 This conversion will simplify the codeword calculations. This is done 583 by taking the last byte of a packet and making it the second byte of 584 the codeword and taking the second last byte of a packet and making it 585 the first byte of a codeword. Also the packet with continuity index 15 586 becomes codeword position one and the packet with continuity index 14 587 becomes codeword position zero. 589 The same FEC is used regardless of the number of bytes in the codeword. 590 So let�s think of the codewords as an array codeword[vert][hor] where 591 vert is 16 packets and hor is 28. Each byte in the array is protected 592 by both a horizontal and a vertical codeword. For each of the 593 codewords the sums must be calculated. If both the sums for a codeword 594 are zero then no errors have been detected for that codeword. 595 Otherwise an error has been detected and further steps need to be taken 596 to see if the error can be corrected. In �C� the horizontal summation 597 would look like: 599 for(i = 0;i < 16;i++) 600 { 601 Sum0 = 0; 602 Sum1 = 0; 603 for(j = 0;j < hor;j++) 604 { 605 If(codeword[i][j] != 0) 606 { 607 Sum0 = sum0 ^ power[j + alog[codeword[i][j]]; 608 Sum1 = sum1 ^ power[3*j + alog[codeword[i][j]]; 609 } 610 } 611 if((sum0 != 0) || (sum1 != 0)) 612 { 613 Try Correcting Packet 614 } 615 } 617 Similarly vertical looks like: 619 for(j = 0;i < hor;i++) 620 { 621 Sum0 = 0; 622 Sum1 = 0; 623 for(i = 0;i < 16;i++) 624 { 625 If(codeword[i][j] != 0) 626 { 627 Sum0 = sum0 ^ power[i + alog[codeword[i][j]]; 628 Sum1 = sum1 ^ power[3*i + alog[codeword[i][j]]; 629 } 630 } 631 if((sum0 != 0) || (sum1 != 0)) 632 { 633 Try Correcting Column 634 } 635 } 637 12.4. Correction Schemes 639 This FEC provides four possible corrections: 641 1) Single bit correction in codeword. All single bit errors. 642 2) Double bit correction in a codeword. Most two bit errors. 643 3) Single byte correction in a codeword. All single byte errors. 644 4) Packet replacement. One or two missing packets from a bunble. 646 12.4.1. Single Bit Correction 648 When correcting a single bit in a codeword, the byte and bit position 649 must be calculated. The equations are: 651 Byte = 1/2LOGalpha(S1/S0) 652 Bit = 8LOGalpha(S0/POWERalpha(Byte)) 654 In �C� this is written: 656 Byte = alog[power[255 + alog[sum1] - alog[sum0]]]; 657 if(Byte & 1) 658 Byte = Byte + 255; 659 Byte = Byte >> 1; 660 Bit = alog[power[255 + alog[sum0] - Byte]] << 3; 661 while(Bit > 255) 662 Bit = Bit - 255; 664 The error is correctable if Byte is less than the number of bytes in 665 the codeword and Bit is less than eight. For this math to be valid 666 both sum0 and sum1 must be non-zero. The codeword is corrected by: 668 codeword[Byte] = codeword[Byte] ^ (1 << Bit); 670 12.4.2. Double Bit Correction 672 Double bit correction is much more complex than single bit correction 673 for two reasons. First, not all double bit errors are deterministic. 674 That is two different bit patterns can generate the same sums. Second, 675 the solution is iterative. To find two bit errors you assume one bit 676 in error and then solve for the second error as a single bit error. 678 The procedure is to iteratively move through the bits of the codeword 679 changing each bit�s state. The new sums are calculated for the 680 modified codeword. Then the single bit calculation above determines if 681 this is the correct solution. If not, the bit is restored and the next 682 bit is tried. 684 For a long codeword this can involve a lot of calculations. There are 685 tricks that can be used to speed the process. For example, the 686 vertical sums give a strong indication of which bytes are in error 687 horizontally. Bits in other bytes need not be tried. 689 12.4.3. Single Byte Correction 691 For single byte correction, the byte position and bits to correct must 692 be calculated. The equations are: 694 Byte = 1/2LOGalpha(S1/S0) 695 Mask = S0/POWERalpha[Byte] 697 Notice that the byte position is the same calculation as for single bit 698 correction. The mask will allow more than one bit in the byte to be 699 corrected. In �C� the mask calculation looks like: 701 Mask = power[255 + alog[sum0] - Byte] 703 Both sum0 and sum1 must be non-zero for the calculations to be valid. 704 The Byte value must be less than the codeword length but Mask can be 705 any value. This corrects the byte in the codeword by: 707 Codeword[Byte] = Codeword[Byte] ^ Mask 709 12.4.4. Packet Replacement 711 If a packet is missing, as determined by the continuity index, then its 712 byte position is known and does not need to be calculated. The formula 713 for single packet replacement is therefore the same as for the Mask 714 calculation of single byte correction. Instead of XORing an existing 715 byte with the Mask, the Mask replaces the missing codeword position: 717 Codeword[Byte] = Mask 719 When two packets are missing, both the codeword positions are known by 720 the continuity index. This again gives two equations with two unknowns 721 which is solved to give the following equations. 723 Mask2 = POWERalpha(2*Byte1)*S0+S1 724 ------------------------------- 725 POWERalpha(2*Byte1+Byte2) +POWERalpha(3*BYTE2) 727 Mask1 = S0 + Mask2*POWERalpha(Byte2)/POWERalpha(BYTE1) 729 In �C� these equations are written: 731 if(sum0 == 0) 732 { 733 if(sum1 == 0) 734 mask2 = 0; 735 else 736 mask2=power[255+alog[sum1]-alog[power[byte2+2*byte1]^ 737 power[3*Byte2]]]; 738 } 739 else 740 { 741 if((a=sum1^power[alog[sum0]+2*byte1]) == 0) 742 mask2 = 0; 743 else 744 mask2 = power[255+alog[a]-alog[power[byte2+2*byte1]^ 745 power[3*byte2]]]; 746 } 747 if(mask2 = 0) 748 { 749 if(sum0 == 0) 750 mask1 = 0; 751 else 752 mask1 = power[255+alog[sum0]-byte1]; 753 } 754 else 755 { 756 if((a=sum0^power[alog[mask2] + byte2]) == 0) 757 mask1 = 0; 758 else 759 mask1 = power[255+alog[a]-byte1]; 760 } 762 Notice that, in the code above, care is taken to check for zero values. 763 The missing codeword position can be fixed by: 765 codeword[byte1] = mask1; 766 codeword[byte2] = mask2; 768 12.5. FEC Performance Considerations 770 The section above shows how to correct the different types of errors. 771 It has not suggested how these corrections may be used in an algorithm 772 to correct a bundle. There are many possible algorithms and the one 773 chosen depends on many variables. These include: 775 . The amount of processing power available. 776 . The number of packets per VBI to process. 777 . The type of hardware capturing the data. 778 . The delivery path of the VBI. 779 . How the code is implemented. 781 As a minimum, it is recommended that the algorithm use single bit or 782 single byte correction for one pass in each direction followed by 783 packet replacement if appropriate. It is possible to do more than one 784 pass of error correction in each direction. The theory is that errors 785 not corrected in the first pass may be corrected in the second pass 786 because error correction in the other direction has removed some 787 errors. 789 In making choices it is important to remember that the code has several 790 possible states: 792 1)Shows codeword as correct and it is. 793 2)Shows codeword as correct and it is not (detection failure). 794 3)Shows codeword as incorrect but cannot correct (detection). 795 4)Shows codeword as incorrect and corrects it correctly (correction). 796 5)Shows codeword as incorrect but corrects wrong bits (false 797 correction). 799 There is actually overlap among the different types of errors. For 800 example, a pair of sums may indicate both a double bit error and a byte 801 error. It is not possible to know at the code level which is correct 802 and which is a false correction. In fact, neither might be correct if 803 both are false corrections. 805 If you know something about the types of errors in the delivery channel 806 you can greatly improve efficiency. If you know that errors are 807 randomly distributed (as in a weak terrestrial broadcast) then single 808 and double bit correction are more powerful than single byte. 810 12.6. Appendix References 812 [1] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 813 Kanata, Ontario, Canada 815 [2] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 816 Software User's Manual." c1996, Kanata, Ontario, Canada 818 [3] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 819 Ontario, Canada 821 [4] Pretzel, Oliver. "Correcting Codes and Finite Fields: Student 822 Edition" OUP, c1996 824 [5] Rorabaugh, C. Britton. "Error Coding Cookbook" McGraw Hill, c1996 826 [6] Mortimer, Brian. �An Error-correction system for the Teletext 827 Transmission in the Case of Transparent Data� c1989 Department of 828 Mathematics and Statistics, Carleton University, Ottawa Canada 830 13. Architecture 832 The architecture that this document is addressing can be broken down 833 into 3 areas: insertion, distribution network, and receiving client. 835 The insertion of IP data onto the television signal can occur at any 836 part of the delivery system. A VBI encoder typically accepts a video 837 signal and an asynchronous serial stream of framed IP as inputs and 838 packetizes the data onto a selected set of lines using NABTS and an 839 FEC. This composite signal is then modulated with other channels 840 before being broadcast onto the distribution network. Operators 841 further down the distribution chain could then add their own data, to 842 other unused lines, as well. 844 The distribution networks include coax plant, off-air, and analog 845 satellite systems and are primarily unidirectional broadcast networks. 846 They must provide a signal to noise ratio which is sufficient for FEC 847 to recover any lost data for the broadcast of data to be effective. 849 The receiving client must be capable of tuning, NABTS waveform sampling 850 as appropriate, filtering on NABTS group addresses as appropriate, 851 forward error correction, unframing, verification of the CRC and 852 decompressing the UDP/IP header if they are compressed. All of the 853 above functions can be carried out in PC software and inexpensive off- 854 the-shelf hardware. 856 14. Scope of proposed protocols 858 The protocols described in this document are for the purpose of 859 transmitting multicast IP packets. However, their scope may be 860 extensible to other applications outside this area. Many of the 861 protocols in this document could be implemented on any unidirectional 862 network. 864 The unidirectional framing protocol provides encapsulation of multicast 865 IP datagrams on the serial stream, and the compression of the UDP/IP 866 headers reduces the overhead on transmission, thus conserving 867 bandwidth. These two protocols could be widely used on different 868 unidirectional broadcast networks or modulation schemes to efficiently 869 transport any type of packet data. In particular, new versions of 870 Internet protocols can be supported to provide a standardized method of 871 data transport. 873 END 875 see comment above concerning standardizing this 876 This has to be checked