home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1997 December
/
Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso
/
drafts
/
draft_n_r
/
draft-panabaker-ip-vbi-00.txt
< prev
next >
Wrap
Text File
|
1997-04-28
|
38KB
|
871 lines
INTERNET-DRAFT R. Panabaker
< draft-panabaker-ip-vbi-00.txt > Microsoft Corp.
Obsoletes: NA C. Witty
Category: Newton Research Labs
March 1997
THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A
TELEVISION SIGNAL
1. Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, and
its working groups. Note that other groups may also distribute working
documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.deu (US West Coast).
2. Abstract
This is an Internet-Draft, which describes a method for broadcasting
multicast IP data using the vertical blanking interval of a television
signal. It includes a description for compressing multicast IP headers
on unidirectional networks, a framing protocol identical to SLIP, and a
forward error correction scheme for the NABTS standard.
Keywords: VBI, NTSC, broadcast, push, FEC, television, NABTS, IP
3. Table of Contents
1. Status of this Memo . . . . . . . . . . . . . . . . . . . . . . 1
2. Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
3. Table of Contents . . . . . . . . . . . . . . . . . . . . . . . 1
4. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .2
5. Proposed protocol stack . . . . . . . . . . . . . . . . . . . . 2
5.1. VBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
5.2. NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
5.3. FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
5.4. Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .6
5.5. IP compression . . . . . . . . . . . . . . . . . . . . . . . 6
6. Addressing Considerations . . . . . . . . . . . . . . . . . . . 7
7. Performance analysis . . . . . . . . . . . . . . . . . . . . . .7
Panabaker [Page 1]
< draft-panabaker-ip-vbi-00.txt > March 1997
8. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . .8
9. Scope of proposed protocols . . . . . . . . . . . . . . . . . . 8
10. Security considerations . . . . . . . . . . . . . . . . . . . . 9
11. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 9
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . .9
13. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
14. Author's address and contacts . . . . . . . . . . . . . . . . .10
15. Appendix: Forward Error Correction Specification . . . . . . .11
15.1. Mathematics used in the FEC . . . . . . . . . . . . . . . . 11
15.2. Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 12
15.3. Correcting Errors . . . . . . . . . . . . . . . . . . . . . 12
15.4. Correcting FEC Bundles . . . . . . . . . . . . . . . . . . .15
15.5. Appendix References . . . . . . . . . . . . . . . . . . . . 15
4. Introduction
This Internet-Draft proposes several protocols to be used in the
transmission of IP datagrams across the Vertical Blanking Interval
(VBI) of a television signal. The VBI is an non-viewable portion of
the television signal that can be used to provide point-to-multipoint
IP data services which will relieve congestion and traffic in the
traditional Internet access networks. Wherever possible these
protocols make use of existing RFC standards and non-standards.
Traditionally, point to point connections (TCP/IP) have been used even
for the transmission of broadcast type data. Distribution of the same
content - news feeds, stock quotes, newsgroups, weather reports, and
the like - are typically sent repeatedly to individual clients rather
than being broadcast to the large number of users who want to receive
such data.
Today, multicast-IP is quickly becoming the preferred method of
distributing one-to-many data on Intranets and the Internet. With the
coming availability of low cost PC hardware for receiving television
signals accompanied by broadcast data streams, it is imperative that a
standard be defined for the transmission of data over traditional
broadcast networks. A lack of standards in this area as well as the
expense of hardware has, in the past, prevented traditional broadcast
networks from becoming effective deliverers of data to the home and
office.
This document describes the transmission of multicast-IP using the
North American Basic Teletext Standard (NABTS), a recognized and
industry supported method of transporting data on the VBI. This will
allow existing standards from the television and Internet communities
to provide inexpensive broadcast data services. Additional protocols
will be used to do this including a serial stream framing protocol
similar to SLIP (RFC 1055 [Romkey 1988]) and a Van Jacobson style
compression technique (RFC 1144) for unidirectional multicast UDP/IP
headers.
I would like to acknowledge the tremendous assistance of Ken Birdwell,
Dave Feinleib and Brian Moran, of Microsoft Corp, and Carl Witty, of
Panabaker [Page 2]
< draft-panabaker-ip-vbi-00.txt > March 1997
Newton Research Labs, in writing this document. Many of the ideas
expressed within are the result of their efforts and insight in this
area. Any of these ideas that prove misbegotten are the sole
responsibility of the author.
5. Proposed protocol stack
The following protocol stack demonstrates the layers used in the
transmission of VBI data. Each layer has no knowledge of the data it
encapsulates and is therefore abstracted from the other layers. At the
link layer, the NABTS protocol defines the modulation scheme used to
transport data on the VBI. At the network layer IP handles the
movement of data to the appropriate computers and UDP, in the transport
layer, determines the flow of data to the appropriate processes and
applications.
+-----------+
| |
|Application|
| |
+-----------+
| | )
| UDP | )
| | )
+-----------+ (-- multicast-IP
| | )
| IP | )
| | )
+-----------+
|SLIP style |
| encap- |
| -sulation |
+-----------+
| |
| NABTS |
| with FEC |
+-----------+
| The VBI of NTSC medium
| (cable, off-air, etc)
|--------<----<----<--------
These protocols can be described in a bottom up component model as
follows:
NTSC signal --> NABTS --> FEC --> serial data stream --> Framing
protocol --> Van Jacobson style compressed UDP/IP headers -->
application data
This diagram can be read as follows: NTSC signals have NABTS packets
modulated onto them which contain a Forward Error Correction (FEC)
protocol. The data contained in these sequential, ordered packets form
a serial data stream on which a framing protocol indicates the location
Panabaker [Page 3]
< draft-panabaker-ip-vbi-00.txt > March 1997
of multicast-IP packets, with compressed headers, containing
application data.
The structure of these components and protocols are described in
following subsections.
5.1. VBI
An NTSC television frame is comprised of 2 fields of 262.5 horizontal
scan lines each. The first 21 lines of each field are not part of the
visible picture and are collectively called the Vertical Blanking
Interval (VBI). Of these 21 lines the first 9 are used while
repositioning the cathode ray to the top of the screen, but the
remaining lines are available for data transport.
Line 21 itself is reserved for the transport of closed captioning data.
There are therefore 11 possible VBI lines being broadcast 60 times a
second (each field 30 times a second), some or all of which could be
used for multicast IP transport. It should be noted that some of these
lines are sometimes used for existing, proprietary, data and testing
services. Multicast IP therefore becomes one more data service using a
subset or all of these lines.
5.2. NABTS
The North American Basic Teletext Standard is defined in the
Electronics Industry Associations EIA-516. It provides an industry-
accepted method of modulating data onto the VBI of an NTSC signal.
This section describes the NABTS packet format as it is used for the
transport of multicast IP. It should be noted that only a subset of
the NABTS standard is used, as is common practice in NABTS
implementations. Further information concerning the NABTS standard and
its implementation can be found in EIA-516.
The NABTS packet is a 36-byte structure encoded onto one horizontal
scan line of an NTSC signal having the following structure:
{2 B clock sync}{1 B byte sync}{3 B packet group address}{1 B
continuity index}{1 B packet structure flags}{26 B data block}{2 B FEC
suffix}
The 2 byte Clock Synchronization and the 1 byte Byte Synchronization,
although not part of the NABTS packet, are located at the beginning of
every scan line containing a NABTS packet and are used to synchronize
the decoding sampling rate and byte timing.
The 3 byte Packet Group address field is Hamming encoded (as specified
in EIA-516, and provides 4 data bits per byte, and thus provides 4096
possible packet group addresses. These addresses are used to
distinguish related services originating from the same source. This is
necessary for the receiver to determine which packets are related and
part of the same service. NABTS packet group addresses therefore
Panabaker [Page 4]
< draft-panabaker-ip-vbi-00.txt > March 1997
distinguish different data services, possibly inserted at different
points of the transmission system, and most likely totally unrelated.
Section 5 of this document discusses Packet Group Addresses in greater
detail.
The 1 byte Continuity Index field is a Hamming encoded byte, which is
incremented by one for each packet of a given Packet Group address.
The index number is determined by the packetÆs order in the FEC bundle
mentioned in the FEC section. The first packet in the bundle has count
0, and the two FEC only packets at the end have counts 14 and 15
respectively. This allows the decoder to determine if packets have
been lost during transmission.
The Packet Structure field is also a Hamming encoded byte, which
contains information about the structure of the remaining portions of
the packet. The most significant bit is always 0 in this
implementation. The second significant bit specifies whether the Data
Block is full (0 indicates the data block is full of useful data, 1
indicates some or all of the data is filler data), and the least two
significant bits are used to indicate the length of the suffix on the
Data Block, in this implementation either 2 or 28 bytes. This suffix
is used for the forward error correction described in the next section.
The Data Block field is 0 to 26 bytes of useful data. Filler data is
indicated by a 0x15 followed by as many 0xEA as are needed to fill the
packet. Sequential data blocks minus the filler data form an
asynchronous serial stream of data.
These NABTS packets are modulated onto the NTSC signal sequentially and
on any combination of lines. Section 6 of this document discusses the
resulting bit rates and overheads associated with NABTS.
5.3. FEC
Due to the unidirectional nature of VBI data transport, forward error
correction is needed to ensure the integrity of data at the receiver.
Any FEC could be used to this end. The FEC for NABTS described in the
appendix of this document has been in use for a number of years, and
has proven popular with the broadcast industry. It is capable of
correcting single byte errors and single and double byte erasures in
the data block and suffix of a NABTS packet.
The FEC algorithm splits a serial stream of data into 364 byte
"bundles". These are arranged as 14 packets of 26 bytes each. A
function is applied to the 26 bytes of each packet to determine the two
suffix bytes for that, which (with the addition of a header) complete
the NABTS packet (8+26+2).
For every 14 packets in the bundle an additional 2 packets are appended
which contain only FEC data. That is, they contain 28 bytes of FEC
data. This data is obtained by first writing the packets into a table
of 16 rows and 28 columns. The same expression as above can be used on
Panabaker [Page 5]
< draft-panabaker-ip-vbi-00.txt > March 1997
the columns of the table with the suffix now represented by the bytes
at the base of the columns in rows 15 and 16. With NABTS headers on
each of these rows, we now have a bundle of 16 NABTS packets ready for
sequential modulation onto lines of the NTSC signal.
At the receiving end of the network these formulae can be used to
verify the validity of the data with very high accuracy. If single
byte errors or single and double byte erasures are found in any row or
column (including an entire packet lost) they can be corrected using
the algorithms found in the appendix.
5.4. Framing
A framing protocol identical to SLIP is proposed for encapsulating IP
datagrams, thus abstracting this data from the lower protocol layers.
This protocol uses two special characters: END (0xc0) and ESC (0xdb).
To send a packet, the host will send the packet followed by the END
character. If a data byte in the packet is the same code as END
character, a two byte sequence of ESC (0xdb) and 0xdc is sent instead.
If a data byte is the same code as ESC character, a two-byte sequence
of ESC (0xdb) and 0xdd is sent instead. SLIP implementations are
widely available, see RFC 1055 [Romkey 1988] for more detail.
+--------------+--+------------+--+--+---------+--+
|IP packet |c0| IP packet |db|dd| |c0|
+--------------+--+------------+--+--+---------+--+
END ESC END
5.5. IP compression
Finally we have the multicast IP packet (RFC 1112 [Deering 1989]). Due
to the value of bandwidth, it is desirable to introduce as much
efficiency as possible. One such efficiency is the compression of the
multicast UDP/IP header using a method similar to the TCP/IP header
compression as described by Van Jacobson (RFC 1144). UDP/IP header
compression is not identical due to the limitation of unidirectional
transmission.
The following two packet formats are used in the following compression
scheme:
The first byte of all packets is the Compression Key. It is a 1 byte
value, the first bit of which indicating if the header has been
compressed, and the remaining 7 bits indicating the compression group
it belongs to.
[0:1][Index:7][protocol:16][full headers:224][data][CRC:32]
[1:1][Index:7][compressed header:32][data][CRC:32]
If the high bit of the Compression Key is set to 0, no compression is
performed and the 2-byte protocol number (the same as 802.3 Ethernet)
Panabaker [Page 6]
< draft-panabaker-ip-vbi-00.txt > March 1997
and the full header are sent. The client VBI interface should store the
protocol number and uncompressed header for future potential use.
If the high bit of the Compression Key is set to 1, the protocol number
is not sent, and a compressed version of that protocol's header is
sent. The client VBI interface must then combine the compressed header
with the stored uncompressed header and recreate a full packet.
As indicated, this compression scheme will support any packet protocol.
Currently, and for the purpose of this document, the only protocol
compression defined is for DoD IP, protocol number 0x0800. When
uncompressed, the entire UDP/IP header is sent. When compressed, only
the "IP identification" and the "fragment offset/flags" are sent. The
client VBI interface should combine these with the previously saved
header.
[0:1][Group:7][0x0800][IP header][UDP header]
[1:1][Group:7][IP identification][fragment offset/flags]
A 32 bit CRC has also been added to the end of every packet to ensure
data integrity. It is performed over the entire, uncompressed, IP
packet, and uses the same algorithm as the MPEG-2 transport stream
(ISO/IEC 13818-1). The generator polynomial is:
1 + D + D^2 + D^4 + D^5 + D^7 + D^8 D^10 + D^11 + D^12 + D^16 + D^22 +
D^23 + D^26 + D^32
As in the ISO/IEC 13818-1 specification, the initial state of the sum
is 0xFFFFFFFF. This is not the same algorithm used by Ethernet.
This CRC provides a final check for damaged datagrams, which spanned
FEC bundles or were not corrected properly by FEC.
6. Addressing Considerations
The addressing of multicast IP packets should adhere to existing
standards in this area. The inclusion of an appropriate source address
is needed to ensure the receiving client can distinguish between
sources and thus services.
NABTS packet addressing is not regulated or standardized and requires
care to ensure that unrelated services on the same channel are not
broadcasting with the same packet group address. This could occur due
to multiple possible injection sites, including show production,
network redistribution, regional operator, and local operator.
Traditionally the marketplace has recognized this concern and made
amicable arrangements for the distribution of these addresses for each
channel.
7. Performance analysis
This section performs an analysis of the overheads associated with each
Panabaker [Page 7]
< draft-panabaker-ip-vbi-00.txt > March 1997
of the protocols described above, and the resulting bit rates.
Every line of an NTSC picture is capable of carrying a 36-byte NABTS
packet (including sync bytes). Every line is refreshed once every
1/60th of a second, which results in a bit rate of 17,280 bps.
The NABTS packet has 8 bytes of overhead on each 36 byte packet, or
22.2% overhead. FEC has 2 bytes on every packet plus 2 packets added
for every group of 14. This brings the total overhead so far to 36.8%.
The remaining data can now be treated as an asynchronous serial stream.
Assume an IP packet size of 350 bytes for the following calculations.
The framing of IP packets adds 1.7% overhead to the data stream, or
1.07% to the total overhead on all bits, assuming 2 escapes per packet.
This brings the running total to 37.9% overhead.
IP overhead is reduced with the use of header compression. The
uncompressed version includes the compression index, protocol number,
the entire UDP/IP header, and CRC for a total of 34 bytes overhead.
The compressed version has only 9 bytes in its header. Assuming we
only transmit the uncompressed packet once in every 10 packets, we get
an average header of only 11.5 bytes. This adds an additional 2%
overhead on the total bits transmitted, bringing the total overhead to
39.9%.
The theoretical throughput is therefore 17,280*(1-.399) or 10,380 bps
per line. This is easily scalable to 115 Kbps for all 11 lines of the
VBI, or 2.7 Mbps for the entire screen.
8. Architecture
The architecture that this document is addressing can be broken down
into 3 areas: insertion, distribution network, and receiving client.
The insertion of IP data onto the NTSC signal can occur at any part of
the delivery system. A NABTS hardware encoder accepts a video signal
and an asynchronous serial stream of framed IP as inputs and packetizes
the data onto a selected set of lines using NABTS and an FEC. This
composite signal is then modulated with other channels before being
broadcast onto the distribution network. Operators further down the
distribution chain could then add their own data, to other unused
lines, as well.
The distribution networks include coax plant, off-air, and analog
satellite systems and are primarily unidirectional broadcast networks.
They must provide a signal to noise ratio which is sufficient for FEC
to recover any lost data for the broadcast of data to be effective.
The receiving client must be capable of tuning, NABTS waveform
sampling, filtering on NABTS group addresses, forward error correction,
unframing, verification of the CRC and decompressing the UDP/IP
Panabaker [Page 8]
< draft-panabaker-ip-vbi-00.txt > March 1997
headers. All of the above functions can be carried out in PC software
and inexpensive off-the-shelf hardware.
9. Scope of proposed protocols
The protocols described in this document are for the purpose of
transmitting multicast IP packets. However, their scope may be
extensible to other applications outside this area. Many of the
protocols in this document could be implemented on any unidirectional
network. NABTS is a standard used on NTSC signals and the FEC was
designed primarily for use with NABTS packet data. However, the data
transported is simply an asynchronous serial stream, and is therefore
abstracted from the transport mechanism of these two protocols.
Many NABTS encoders work with PAL, SECAM, and NTSC-J video formats as
well. This would require different waveform sampling and decoding on
the client, but would allow all 900+ million cable subscribers in the
world to receive IP over the VBI. It should also be noted that NABTS
could be used in a full screen mode, in which all lines of the picture
frame were used for data transport. There are obviously issues
concerning the logistics of this service, but the possibility exists,
and many VBI decoders support this functionality.
The unidirectional framing protocol provides encapsulation of multicast
IP datagrams on the serial stream, and the Van Jacobson style
compression of the UDP/IP headers reduces the overhead on transmission,
thus conserving bandwidth. These two protocols could be widely used on
different unidirectional broadcast networks or modulation schemes to
efficiently transport any type of packet data. In particular, new
versions of Internet protocols can be supported to provide a
standardized method of data transport.
10. Security considerations
As with any broadcast network, there are security issues due to the
accessibility of data. It is assumed that the responsibility for
securing data lies in the application layer protocol, which is beyond
the scope of this document.
11. Conclusions
This document provides a method for broadcasting Internet data over a
television signal for reception by client computers. With an
appropriate "push and filter" content model, this will become an
attractive method of providing data services to end users. By using
existing standards and a layered protocol approach, this document has
also provided a model for data transmission on unidirectional and
broadcast networks.
12. References
[1] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC
1112, 17 pages (Aug.).
Panabaker [Page 9]
< draft-panabaker-ip-vbi-00.txt > March 1997
[2] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: North
American Basic Teletext Specification (NABTS)" Washington: Electronic
Industries Association, c1988
[3] Jack, Keith. "Video Demystified: A Handbook for the Digital
Engineer, Second Edition," San Diego: HighText Pub. c1996.
[4] Jacobson, V. 1990a. "Compressing TCP/IP Headers for Low-Speed
Serial Links," RFC 1144, 43 pages (Feb.).
[5] Norpak Corporation "TTX71x Programming Reference Manual", c1996,
Kanata, Ontario, Canada
[6] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder
Software User's Manual." c1996, Kanata, Ontario, Canada
[7] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata,
Ontario, Canada
[8] Romkey, J. L. 1988. "A Nonstandard for Transmission of IP
Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June).
[9] Stevens, W. Richard. "TCP/IP Illustrated, Volume 1,: The
Protocols" Reading: Addison-Wesley Publishing Company, c1994.
13. Acronyms
VBI - Vertical Blanking Interval
FEC - Forward Error Correction
NABTS - North American Basic Teletext Standard
NTSC - National Television Standards Committee
PAL - Phase Alternation Line
SECAM - Sequentiel Couleur Avec Memoire (sequential color with
memory)
NTSC-J - Japanese flavor of NTSC
RFC - Request For Comments
IP - Internet Protocol
UDP - User Datagram Protocol
TCP - Transmission Control Protocol
SLIP - Serial Line Internet Protocol
14. Author's address and contacts
Ruston Panabaker
One Microsoft Way
Redmond, WA
98052-6399
email: BPCfeed@microsoft.com
Other contacts:
Panabaker [Page 10]
< draft-panabaker-ip-vbi-00.txt > March 1997
Brian Moran
One Microsoft Way
Redmond, WA
98052-6399
brianmo@microsoft.com
T: (206) 936-4376
Dave Feinleib
One Microsoft Way
Redmond, WA
98052-6399
davefe@microsoft.com
T: (206) 703-5543
15. Appendix: Forward Error Correction Specification
This FEC is specified as used for the detection and correction of
errors incurred during transmission on the vertical blanking interval
in NABTS packets. Carl Witty (< biblio >) wrote the original
specification, from which this appendix was written. We begin with a
brief description of the mathematics used throughout this
specification.
15.1. Mathematics used in the FEC
Galois fields form the basis for the FEC algorithm presented here.
Rather then explain these fields in general, a specific explanation is
given of the Galois field used in the FEC algorithm.
The Galois field used is GF(2^8). This is a set of 256 elements, along
with the operations of "addition" and "multiplication" on these
elements. Each element is represented by an 8 bit binary number.
The operation of "addition" with this Galois field is the XOR of two
elements. Thus, the "sum" of 00011011 and 00000111 is 00011100.
Division of two elements is done using long division with subtraction
operations replaced by XOR. For multiplication, standard long
multiplication is used but with the final addition stage replaced with
XOR.
All arithmetic in the following FEC is done modulo 100011101; for
instance, after you multiply two numbers, you replace the result with
its remainder when divided by 100011101. There are 256 values in this
field (256 possible remainders), the 8-bit numbers. It is very
important to remember that when we write A*B = C, we more accurately
imply modulo(A*B) = C.
These Galois elements have many properties in common with the real
numbers:
- every nonzero x has an inverse x^-1 , such that x*x^-1=1
- (xy)^-1 = x^-1 * y^-1
Panabaker [Page 11]
< draft-panabaker-ip-vbi-00.txt > March 1997
- x(yz) = (xy)z
- x + (y + z) = (x +y) + z
- xy = yx
- x + y = y + x
- (x + y)z = xz + yz
- if xy = xz then x = 0 or y = z
- if xy = 0 then x = 0 or y = 0
- x^(a+b) = x^a * x^b (here a and b are standard numbers not in the
Galois field and a+b denotes standard addition)
There are also many properties which differ from the real numbers:
- for every nonzero x, x^255 = 1 (this implies that x^254 = x^-1)
- x + x = 0
15.2. Calculating FEC bytes
The FEC algorithm splits a serial stream of data into 364 byte
"bundles". These are arranged as 14 packets of 26 bytes each. Across
each packet the following expression is determined for each of the two
suffix bytes, S0 and S1, which (with the addition of a header) complete
the NABTS packet (8+26+2):
Sum, as i goes from 0-25, of Ci,j * Di = Sj
Where, Ci,j is a tabulated coefficient, Di is the ith data byte of the
data block, and j can be 0 and 1. The multiplications and additions in
this formula are done using Galois fields and modulo arithmetic as
explained above.
The tabulated coefficients are:
Ci,0 = {0x9d, 0x37, 0xe4, 0xcb, 0x7f, 0xab, 0x8d, 0xbb, 0xb1, 0x6a,
0xde, 0x8a, 0x4a, 0x20, 0x98, 0x9d, 0xbb, 0x94, 0x3d, 0x38, 0xa6, 0xe9,
0x42, 0xa0, 0xe2, 0x64, },
and...
Ci,1 = {0x92, 0x97, 0xdd, 0xa0, 0x9a, 0x91, 0x0a, 0x50, 0x1d, 0x60,
0xae, 0x20, 0x3d, 0x2c, 0x01, 0x0a, 0x40, 0xc8, 0xe5, 0xff, 0xf2, 0x68,
0xc9, 0xa1, 0x63, 0x8d, }.
For every 14 packets in the bundle an additional 2 packets are appended
which contain only FEC data. This data is obtained by first writing
the packets into a table of 16 rows and 28 columns. The same formula
as above can be used on the columns of the table with S0 and S1 now
representing the byte at the base of the column in row 15 or 16
respectively. Therefore we calculate
Sum, as i goes from 0-13, of Ci,j * Di = Sj
for each column. Where, Ci,j is a coefficient from the same table as
above, Di is the nth byte of the ith row, and j can be 0 and 1.
15.3. Correcting Errors
Panabaker [Page 12]
< draft-panabaker-ip-vbi-00.txt > March 1997
This section describes the procedure for detecting and correcting
errors using the FEC data calculated above. Upon reception we begin by
arranging the packets in tabular form similar to that in the previous
section. We form a column of 16 packets each containing 28 bytes
ofdata. We will be detecting and correcting errors in these rows and
columns.
Since the horizontal and vertical FEC are the same (except for the
number of byes of data to be protected), the algorithms here will work
in both directions. We will use k as the number of bytes of data to be
protected, so k is either 26 (for horizontal FEC) or 14 (for vertical
FEC). The original, error-free bytes are D0, D1, ....Dk, Dk+1 (note
that the FEC bytes are included as Dk and Dk+1), and the received bytes
with possible errors are R0,....., Rk+1.
We know that if no errors occurred, we would have
the sum, as i goes from 0 to k-1 of Ci,j * Ri = Rk+j,
for j=0,1. In the Galois field this can be written as
(the sum, as i goes from 0 to k-1 of Ci,j * Ri) + Rk+j = 0. Eqn 1
Conversely, if errors did occur, it is most likely that this equation
would not be true. We can therefore assume that if Eqn 1 is satisfied,
no errors occurred.
15.3.1. Detecting and correcting single-byte errors
When Eqn 1 is not satisfied there are one or more errors in the
protected bytes. We will begin by looking at the effect of a single
byte error at position p. There are two basic cases: p >= k and p < k.
The first case: If p >= k then there is an error in one of the two FEC
bytes. This is indicated by Eqn 1 being satisfied when j = 0 or j = 1
but not both.
The second case: If p < k then the error is not in the FEC bytes but in
the protected data. In this case, Eqn 1 will not be satisfied for
either j = 0 or j = 1. Instead we will get
(the sum, as i goes from 0 to k-1 of Ci,j *Ri) + Rk+j = Ej Eqn 2
where Ej = Ci,j * h, and h = Dp - Rp. Thus as long as there is no q
(other then q=p) such that Cp,0 * Cp,1^-1 = Cq,0 * Cq,1^-1, we can
construct a function P(Cp,0 * Cp,1^-1) = p. This condition is in fact
met by the coefficients chosen for Ci,j.
If p is found to be a valid number (less then k), we can subtract h
(where h = Ej * Cp,j^-1, and j = 0 or j = 1) from the value located at
p and the error is corrected. This can be verified by using Eqn 1 on
Panabaker [Page 13]
< draft-panabaker-ip-vbi-00.txt > March 1997
the new protected data block. If p is not a valid number then we
assume there are at least two errors in the block.
It should be noted that by using any of the above corrections it is
possible to mistakenly turn a two-byte error into a three-byte error.
15.3.2. Correcting Single Byte Erasures
If we know where an error is in the protected block we can correct it
and still detect any other single byte error but not correct it. We
might know the location of this erasure because a packet was lost
during transmission, and we are correcting the columns of our table.
Every column in this example will have an erasure at p, where p is the
lost packet row.
First let's consider the case where p >= k, which means the erasure is
in the FEC. We can use Eqn 1 to ensure the other FEC byte satisfies
the equation, and can therefore determine that the packet most likely
has no errors. If it does not, we know there is at least one other
one-byte error and we cannot determine its location to fix it.
The second possibility is that p<k, so the erasure is not in the FEC.
If Eqn 1 is satisfied for both j=0 and j=1 then we leave the erasure as
is, correct. If Eqn 1 is satisfied by j=0 or j=1 but not both, then
there is an error we cannot correct. If Eqn 1 is not satisfied by
either j=0 or j=1 and P(Cp,0/Cp,1) = p then we can correct the byte at
p by adding the result of (Ej * Cp,j^-1) for j=0 or j=1 (it shouldn't
matter which).
15.3.3. 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. There are three possible cases:
In the first case both erasures are in the FEC bytes. In this case we
can use Eqn 1 to determine the correct value of Rk+j.
The second case has one erasure in the FEC, and another in the
protected block outside the FEC bytes at position p. We can correct
the erasure at p as we would a single byte erasure by adding the
expression (Ej * Cp,j^-1), where Rk+j is not the erased FEC byte. This
erasure in the FEC can now be corrected using Eqn 1 and solving for the
erased byte Dp.
In the third case, neither erasure is in the FEC bytes, so p < q <k.
This is the more difficult case. Using our FEC algorithms developed
above we can write:
Ej = Cp,j (Dp + Rp) + Cq,j (Dq + Rq)
where j = 0 and j=1. These two equations form a system of linear
Panabaker [Page 14]
< draft-panabaker-ip-vbi-00.txt > March 1997
equations. Assuming Cp,j and Cq,j are non-zero (which they are in this
implementation), and Cp,0 * Cp,1^-1 does not equal Cq,0 * Cq,1^-1
(which is also true for all p < q < k), we can solve this system for Dp
and Dq.
15.4. Correcting FEC Bundles
We now have a set of tools for detecting and correcting errors in FEC
bundles.
1) With no erasures, we can look at a row or column and say either:
- The FEC bytes match; there are probably no errors.
- The FEC bytes fail to match in a way which could be
caused by a single-byte error; in this case we can
find the location and value of such an error.
- The FEC bytes fail to match in a way which indicates
that there are at least two bytes of error.
2) With one erasure, we can correct it and look at a line and say
either:
- The FEC bytes now match; there are probably no other
errors (beyond the erasure)
- The FEC bytes don't match; there is at least one
more error, which we cannot correct.
3) With two erasures, we can correct the line so that the FEC bytes
match. In this case, we have no error-detecting capability.
All of these tools can be used in an iterative manner on the rows and
columns of the FEC bundle to correct or detect errors.
15.5. Appendix References
[1] Norpak Corporation "TTX71x Programming Reference Manual", c1996,
Kanata, Ontario, Canada
[2] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder
Software User's Manual." c1996, Kanata, Ontario, Canada
[3] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata,
Ontario, Canada
[4] Pretzel, Oliver. ôCorrecting Codes and Finite Fields: Student
Edition" OUP, c1996
[5] Rorabaugh, C. Britton. "Error Coding Cookbook" McGraw Hill, c1996
[6] Witty, Carl. 1997 Newton Research Labs, Seattle, WA
Panabaker [Page 15]