INTERNET-DRAFT N. Thorne
Expires in six months
Obsoletes: NA
Category: ipvbi
THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A
PAL TELEVISION SIGNAL
1. Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.deu (US West Coast).
2. Abstract
This is an Internet-Draft, which describes a method for broadcasting
multicast IP data using the vertical blanking interval of a PAL
television signal. It includes a description for compressing
multicast IP headers on unidirectional networks, a framing protocol
identical to SLIP, forward error correction schemes for the WST
standards. A related Internet-Draft, Ref.[1], is progressing
transmission of IP over the VBI of an NTSC television signal.
Keywords: VBI, PAL, broadcast, push, FEC, television, NABTS, WST, IP
3. Table of Contents
1. Status of this Memo
2. Abstract
3. Table of Contents
4. Introduction
5. Proposed protocol stack
5.1. PAL VBI Overview
5.2. WST VBI Standard
5.3. WST Forward Error Correction (FEC)
5.4. Framing
5.5. IP compression
6. WST Addressing Considerations
7. WST Performance analysis
7.2. Summary of Performance of IP over PAL and NTSC(Ref.[1]) VBI
8. Architecture
9. Scope of proposed protocols
10. Security considerations
11. Conclusions
12. References
13. Acronyms
14. Author's address and contacts
15. Appendix: WST Forward Error Correction Specification
15.1. Mathematics used in the WST FEC
15.2. Calculating WST FEC bytes
15.3. Correcting Errors using the WST FEC
15.3.1. Detecting & Correcting Single Byte Errors
15.3.2. Correcting Double Byte Erasures
15.4. Correcting WST FEC Bundles
15.5. WST FEC Appendix References
4. Introduction
This Internet-Draft proposes several protocols to be used in the
transmission of IP datagrams across the Vertical Blanking Interval
(VBI) of a PAL television signal. The VBI is a non-viewable portion
of the television signal that can be used to provide point-to-
multipoint IP data services which will relieve congestion and traffic
in the traditional Internet access networks. Wherever possible these
protocols make use of existing RFC standards and non-standards.
Traditionally, point to point connections (TCP/IP) have been used
even for the transmission of broadcast type data. Distribution of
the same content - news feeds, stock quotes, newsgroups, weather
reports, and the like - are typically sent repeatedly to individual
clients rather than being broadcast to the large number of users who
want to receive such data.
Today, multicast-IP is quickly becoming the preferred method of
distributing one-to-many data on Intranets and the Internet. With
the coming availability of low cost PC hardware for receiving
television signals accompanied by broadcast data streams, it is
imperative that a standard be defined for the transmission of data
over traditional broadcast networks. A lack of standards in this
area as well as the expense of hardware has, in the past, prevented
traditional broadcast networks from becoming effective deliverers of
data to the home and office. This document describes the transmission
of multicast-IP using the World System Teletext (WST) Standard
Ref.[7]. WST is recognized and industry supported method of
transporting data on the VBI. This will allow existing standards
from the television and Internet communities to provide inexpensive
broadcast data services. Additional protocols will be used to do
this including a serial stream framing protocol similar to SLIP (RFC
1055 [Romkey 1988]) and a Van Jacobson style compression technique
(RFC 1144) for unidirectional multicast UDP/IP headers.
The author would like to acknowledge Ruston Panabaker of Microsoft
Corp and Carl Witty of Newton Research for writing the Internet-Draft
for IP over the VBI (of a NABTS) TV signal, Ref.[1]., and Bruce
Murray and Ian Willis of Philips Semiconductors Systems Laboratory
Southampton in writing this document. Many of the ideas expressed
within are the result of their efforts and insight in this area. Any
of these ideas that prove misbegotten are the sole responsibility of
the author.
5. Proposed protocol stack
The following protocol stack demonstrates the layers used in the
transmission of VBI data. Each layer has no knowledge of the data it
encapsulates and is therefore abstracted from the other layers. At
the link layer, the WST protocol defines the modulation scheme used
to transport data on the VBI. At the network layer IP handles the
movement of data to the appropriate computers and UDP, in the
transport layer, determines the flow of data to the appropriate
processes and applications.
+-----------+
| |
|Application|
| |
+-----------+
| | )
| UDP | )
| | )
+-----------+ (-- multicast-IP
| | )
| IP | )
| | )
+-----------+
|SLIP style |
| encap- |
| -sulation |
+-----------+
| |
| WST |
| with FEC |
| |
+-----------+
| The VBI of PAL medium
| (cable, off-air, etc.)
|--------<----<----<--------
These protocols can be described in a bottom up component model as
follows:
PAL signal --> WST --> FEC --> serial data stream --> Framing
protocol --> Van Jacobson style compressed UDP/IP headers -->
application data
This diagram can be read as follows: PAL signals have WST packets
modulated onto them which contain a Forward Error Correction (FEC)
protocol. The data contained in these sequential, ordered packets
form a serial data stream on which a framing protocol indicates the
location of multicast-IP packets, with compressed headers, containing
application data.
The structure of these components and protocols are described in
following subsections.
5.1 PAL VBI Overview
A PAL television frame is comprised of 2 fields of 312.5 horizontal
scan lines each. The first 22 lines of each field are not part of
the visible picture and are collectively called the Vertical Blanking
Interval (VBI). Of these 22 lines, 16 are available for data
transport, each being broadcast 50 times a second.
Some or all of these lines could be used for multicast IP transport.
It should be noted that some of these lines are sometimes used for
existing, proprietary, data and testing services. Multicast IP
therefore becomes one more data service using a subset or all of
these lines.
5.2. WST VBI Standard
The World System Teletext Standard is defined in the European
Telecommunication Standard ETS 300 706 "Enhanced Teletext
Specification" Ref.[7]. It provides an industry accepted method of
modulating data onto the VBI of a PAL signal.
A second standard ETS 300 708 "Data Transmission within Teletext"
Ref.[9] deals specifically with the use of WST packets for data
broadcasting purposes. The proposal below frees two more bytes per
line for data payload than Ref.[9], though there may be regulatory
hurdles to be overcome in doing this.
This section describes the WST packet format as it is used for the
transport of multicast IP. It should be noted that only a subset of
the WST standard is used, as is common practice in WST
implementations. Further information concerning the WST standard and
its implementation can be found in Ref.[7] and Ref.[9].
The WST packet is a 45-byte structure encoded onto one horizontal
scan line of a PAL signal having the following structure:
{2 B clock sync}{1 B byte sync}{2 B magazine and packet address}{40 B
data}
To maintain compatibility with existing WST broadcasts, the magazine
and packet address group (MPAG) of IP Multicast packets must have
MPAGs (Magazine and Packet Address Groups) of
0/30,1/30,2/30,3/30,7/30 or 7/31 (dependent on regulatory issues)
where 0/30 is shorthand for Magazine 0, Packet 30 and so on. So the
format of an IP Multicast WST packet will be as follows:
{2 B clock sync}{1 B byte sync}{2 B MPAG}{1 B service type}{2 B
packet group address}{1 B continuity index}{35 B data block}{2 B FEC
suffix}
The 2 byte Clock Synchronization and the 1 byte Byte Synchronization,
although not part of the WST packet, are located at the beginning of
every scan line containing a WST packet and are used to synchronize
the decoding sampling rate and byte timing.
The 2 byte Magazine and Packet Address Group (MPAG) is Hamming
encoded (as specified in Ref.[7]) and provides 4 data bits per byte.
3 bits specify the magazine and 5 bits the packet. MPAGs of
0/30,1/30,2/30,3/30,7/30 or 7/31 (subject to regulations and Ref.[9])
should always be used to guarantee compatibility with existing WST
transmissions.
The 1 byte Service Type byte is Hamming Encoded and provides 4 data
bits. Bits d3 (MSB), d2 and d1 specify the service type. Service type 000
is IP over VBI. Other service types are to be specified. The meaning
of d0 (the LSB) depends on the service type. For service type 000, d0
indicates the presence of filler in the data payload. If d0 is
cleared to 0, no filler data is present. If d0 is set to 1, filler data is
present. The meaning of d0 with other service types is not specified.
The 1 byte Packet Group address field is Hamming encoded and provides
4 data bits per byte, and thus provides 16 possible packet group
addresses. These addresses are used to distinguish related services
originating from the same source. This is necessary for the receiver
to determine which packets are related and part of the same service.
Packet Group Addresses therefore distinguish different data
services, possibly inserted at different points of the transmission
system, and most likely totally unrelated. Section 6 of this
document discusses Packet Group Addresses in greater detail.
The 1 byte Continuity Index field is a Hamming encoded byte, which is
incremented by one for each packet of a given Packet Group Address.
The index number is determined by the packet's order in the FEC
bundle mentioned in the FEC section. The first packet in the bundle
has count 0, and the last count 15. This allows the decoder to
determine if packets have been lost during transmission. No
discontinuities in the CI sequence shall be transmitted.
The Data Block field 35 bytes. Filler data is indicated by a 0x15
followed by as many 0xEA as are needed to fill the packet.
Sequential data blocks minus the filler data form an asynchronous
serial stream of data.
These WST packets are modulated onto the PAL signal sequentially and
on any combination of lines. Section 7 of this document discusses
the resulting bit rates and overheads associated with WST.
5.3.WST Forward Error Correction (FEC)
Due to the unidirectional nature of VBI data transport, forward error
correction is needed to ensure the integrity of data at the receiver.
The FEC for WST described in the appendix of this document (Section
16) is based on the industry standard t=1 RS scheme, popular in CD
ROM systems.
The WST FEC algorithm splits a serial stream of data into 448 byte
"bundles". These are arranged as 16 packets of 35 bytes each. A
function is applied to the 35 bytes of each packet to determine the
two suffix bytes for that, which (with the addition of a header)
complete the WST packet (8+35+2).
Each packet contains 2 FEC suffix bytes for horizontal and 2 suffix
bytes for vertical correction.
At the receiving end the t=1 RS FEC scheme is used to verify the
validity of the data with very high accuracy. If single byte errors
or single and double byte erasures are found in any row or column
(including an entire packet lost) they can be corrected using the
algorithms found in the appendix (Section 15).
5.4. Framing
A framing protocol identical to SLIP is proposed for encapsulating IP
datagrams, thus abstracting this data from the lower protocol layers.
This protocol uses two special characters: END (0xc0) and ESC (0xdb).
To send a packet, the host will send the packet followed by the END
character. If a data byte in the packet is the same code as END
character, a two byte sequence of ESC (0xdb) and 0xdc is sent
instead. If a data byte is the same code as ESC character, a two-
byte sequence of ESC (0xdb) and 0xdd is sent instead. SLIP
implementations are widely available, see RFC 1055 [Romkey 1988] for
more detail.
+--------------+--+------------+--+--+---------+--+
|IP packet |c0| IP packet |db|dd| |c0|
+--------------+--+------------+--+--+---------+--+
END ESC END
5.5. IP compression
Finally we have the multicast IP packet (RFC 1112 [Deering 1989]).
Due to the value of bandwidth, it is desirable to introduce as much
efficiency as possible. One such efficiency is the compression of
the multicast UDP/IP header using a method similar to the TCP/IP
header compression as described by Van Jacobson (RFC 1144). UDP/IP
header compression is not identical due to the limitation of
unidirectional transmission.
The following two packet formats are used in the following
compression scheme:
The first byte of all packets is the Compression Key. It is a 1 byte
value, the first bit of which indicating if the header has been
compressed, and the remaining 7 bits indicating the compression group
it belongs to.
[0:1][Index:7][protocol:16][full headers:224][data][CRC:32]
[1:1][Index:7][compressed header:32][data][CRC:32]
If the high bit of the Compression Key is set to 0, no compression is
performed and the 2-byte protocol number (the same as 802.3 Ethernet)
and the full header are sent. The client VBI interface should store
the protocol number and uncompressed header for future potential use.
If the high bit of the Compression Key is set to 1, the protocol
number is not sent, and a compressed version of that protocol's
header is sent. The client VBI interface must then combine the
compressed header with the stored uncompressed header and recreate a
full packet.
As indicated, this compression scheme will support any packet
protocol. Currently, and for the purpose of this document, the only
protocol compression defined is for DoD IP, protocol number 0x0800.
When uncompressed, the entire UDP/IP header is sent. When
compressed, only the "IP identification" and the "fragment
offset/flags" are sent. The client VBI interface should combine
these with the previously saved header.
[0:1][Group:7][0x0800][IP header][UDP header]
[1:1][Group:7][IP identification][fragment offset/flags]
A 32 bit CRC has also been added to the end of every packet to ensure
data integrity. It is performed over the entire, uncompressed, IP
packet, and uses the same algorithm as the MPEG-2 transport stream
(ISO/IEC 13818-1). The generator polynomial is:
1 + D + D^2 + D^4 + D^5 + D^7 + D^8 D^10 + D^11 + D^12 + D^16 + D^22
+ D^23 + D^26 + D^32
As in the ISO/IEC 13818-1 specification, the initial state of the sum
is 0xFFFFFFFF. This is not the same algorithm used by Ethernet.
This CRC provides a final check for damaged datagrams, which spanned
FEC bundles or were not corrected properly by FEC.
6. WST Addressing Considerations
The addressing of multicast IP packets should adhere to existing
standards in this area Refs.[7] & [9]. The inclusion of an
appropriate source address is needed to ensure the receiving client
can distinguish between sources and thus services.
MPAGs of 0/30,1/30,2/30,3/30,7/30 or 7/31 should be used depending
on regulatory issues and ETS 300 708 Ref.[9].
The 1 byte Service Type and 1 byte Packet Address Group then follow.
These provide addressing between different Multicast IP providers.
7. WST Performance analysis
This section performs an analysis of the overheads associated with
each of the protocols described above, and the resulting bit rates.
Every line of a PAL picture is capable of carrying a 45-byte WST
packet (including sync bytes). Every line is refreshed once every
1/50th of a second, which results in a bit rate of 18,000bps.
The WST packet has 8 bytes of overhead on each 45 byte packet, or
17.8% overhead (run in + framing code + MPAG + Service Type + Packet
Address Group + Continuity Index). FEC has 2 bytes on every packet
plus equivalent of 2 packets added for every group of 14: ((2 * 14 +
2 * 35) / (14 * 35)) * (100 - 17.8) = 18.0% (overhead on remainder
from VBI overhead), so 18.0% + 17.8% = 35.8%. This brings the total
overhead so far to 35.8%.
The remaining data can now be treated as an asynchronous serial
stream. Assume an IP packet size of 350 bytes for the following
calculations.
The framing of IP packets adds 1.7% overhead to the data stream, or
1.02% (0.017 * (100 - 35.8%) =1.09%) to the total overhead on all
bits, assuming 2 escapes per packet. This brings the running total
to 36.9% overhead.
IP overhead is reduced with the use of header compression. The
uncompressed version includes the compression index, protocol number,
the entire UDP/IP header, and CRC for a total of 34 bytes overhead.
The compressed version has only 9 bytes in its header. Assuming we
only transmit the uncompressed packet once in every 10 packets, we
get an average header of only 11.5 bytes. This adds an additional 2%
overhead on the total bits transmitted, bringing the total overhead
to 38.9%%.
The theoretical throughput is therefore 18,000*(1-.389) or 10,992Kbps
per line. This is easily scaleable to 175.9 Kbps for all 16 lines of
the VBI, or 3.36 Mbps for the entire screen.
7.3. Summary of Performance of IP over PAL and NTSC (Ref.[1]) VBI
Description WST NABTS
VBI overhead 17.8% 22.2%
FEC + SLIP overhead 36.9% 37.9%
+UDP/IP overhead 38.9% 39.9%
bps per VBI line 10,992 10,380
bps per entire VBI 175.9K 115K
bps per entire channel 3.36M 2.70M
8. Architecture
The architecture that this document is addressing can be broken down
into 3 areas: insertion, distribution network, and receiving client.
The insertion of IP data onto the PAL television signal can occur at
any part of the delivery system. A WST hardware encoder accepts a
video signal and an asynchronous serial stream of framed IP as inputs
and packetizes the data onto a selected set of lines using WST and an
FEC. This composite signal is then modulated with other channels
before being broadcast onto the distribution network. Operators
further down the distribution chain could then add their own data to
other unused lines as well. For example some sophisticated systems
can dynamically insert packets on any VBI line not in use.
The distribution networks include coax plant, off-air, and analog
satellite systems and are primarily unidirectional broadcast
networks. They must provide a signal to noise ratio which is
sufficient for FEC to recover any lost data for the broadcast of data
to be effective.
The receiving client must be capable of tuning, WST data recovery,
filtering on WST MPAGs and group addresses, forward error correction,
unframing, verification of the CRC and decompressing the UDP/IP
headers. All of the above functions can be carried out in PC
software and inexpensive off-the-shelf hardware.
9. Scope of proposed protocols
The protocols described in this document are for the purpose of
transmitting multicast IP packets. However, their scope may be
extensible to other applications outside this area. Many of the
protocols in this document could be implemented on any unidirectional
network. WST is a standard used on PAL signals. The FEC is designed
primarily for use with WST. However, the data transported is simply
an asynchronous serial stream, and is therefore abstracted from the
transport mechanism of these protocols.
Many WST encoders work with the SECAM video format as well. This
would require different waveform sampling and decoding on the client,
but would allow more subscribers in the world to receive IP over the
VBI. It should also be noted that PAL could be used in a full screen
(also called full field) mode, in which all lines of the picture
frame were used for data transport. There are obviously issues
concerning the logistics of this service, but the possibility exists,
and many VBI decoders support this functionality.
The unidirectional framing protocol provides encapsulation of
multicast IP datagrams on the serial stream, and the Van Jacobson
style compression of the UDP/IP headers reduces the overhead on
transmission, thus conserving bandwidth. These two protocols could
be widely used on different unidirectional broadcast networks or
modulation schemes to efficiently transport any type of packet data.
In particular, new versions of Internet protocols can be supported to
provide a standardized method of data transport.
10. Security considerations
As with any broadcast network, there are security issues due to the
accessibility of data. It is assumed that the responsibility for
securing data lies in the application layer protocol, which is beyond
the scope of this document.
11. Conclusions
This document provides a method for broadcasting Internet data over a
PAL television signal for reception by client computers. With an
appropriate "push and filter" content model, this will become an
attractive method of providing data services to end users. By using
existing standards and a layered protocol approach, this document has
also provided a model for data transmission on unidirectional and
broadcast networks.
12. References
[1] Internet-Draft (Work in Progress) "The Transmission of IP over
the Vertical Blanking Interval of a Television Signal", R. Panabaker,
Microsoft Corp. C.Witty, Newton Research Labs. March 97
[2] Deering, S. E. 1989. "Host Extensions for IP Multicasting," RFC
1112, 17 pages (Aug.)
[3] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: North
American Basic Teletext Specification (NABTS)" Washington: Electronic
Industries Association, c1988
[4] Jacobson, V. 1990a. "Compressing TCP/IP Headers for Low-Speed
Serial Links," RFC 1144, 43 pages (Feb.).
[5] Romkey, J. L. 1988. "A Nonstandard for Transmission of IP
Datagrams Over Serial Lines: SLIP," RFC 1055, 6 pages (June).
[6] Stevens, W. Richard. "TCP/IP Illustrated, Volume 1,: The
Protocols" Reading: Addison-Wesley Publishing Company, c1994.
[7] European Telecommunication Standard. ETS 300 706 "Enhanced
Teletext Specification", 1997
[8] MediaComm 95. "Teletext in Multimedia Applications", D.Tarrant &
S.Wegerif, 1995
[9] European Telecommunication Standard. ETS 300 708 "Data
Transmission within Teletext", 1997
[10] European Telecommunication Standard. TR 101 233 DRAFT, " Code of
Practice for the Allocation of Services in the Vertical Blanking
Interval (VBI)", 1997
13. Acronyms
VBI - Vertical Blanking Interval
FEC - Forward Error Correction
NABTS - North American Basic Teletext Standard
NTSC - National Television Standards Committee
PAL - Phase Alternation Line
SECAM - Sequentiel Couleur Avec Memoire (sequential color
with memory)
NTSC-J - Japanese flavor of NTSC
RFC - Request For Comments
IP - Internet Protocol
UDP - User Datagram Protocol
TCP - Transmission Control Protocol
SLIP - Serial Line Internet Protocol
WST - World System Teletext
ETSI - European Telecommunication Standard
14. Author's address and contacts
Nick Thorne
Philips Semiconductors Systems Laboratory - Southampton
Millbrook Industrial Estate
Southampton
Hampshire, UK
SO15 0DJ
email: nick.thorne@soton.sc.philips.com
Other contacts:
Simon Wegerif
Philips Semiconductors Systems Laboratory - Southampton
Millbrook Industrial Estate
Southampton
Hampshire, UK
SO15 0DJ
email: simon.wegerif@soton.sc.philips.com
15. Appendix: WST Forward Error Correction Specification
This FEC is specified as used for the detection and correction of
errors incurred during transmission on the vertical blanking interval
in WST packets. This FEC is based on the same standard Galois field
operations as the NABTS FEC (Ref.[1]), but with a pure t=1 Reed
Solomon (RS) code instead. Use of the RS code reduces the number of
tables required.
15.1. Mathematics used in the WST FEC
Galois fields form the basis for the FEC algorithm presented here.
Rather then explain these fields in general, a specific explanation
is given of the Galois field used in the FEC algorithm.
The Galois field used is GF(2^8). This is a set of 256 elements,
along with the operations of "addition" and "multiplication" on these
elements. Each element is represented by an 8 bit binary number.
The operation of "addition" with this Galois field is the XOR of two
elements. Thus, the "sum" of 00011011 and 00000111 is 00011100.
Division of two elements is done using long division with subtraction
operations replaced by XOR. For multiplication, standard long
multiplication is used but with the final addition stage replaced
with XOR.
All arithmetic in the following FEC is done modulo 100011101; for
instance, after you multiply two numbers, you replace the result with
its remainder when divided by 100011101. There are 256 values in
this field (256 possible remainders), the 8-bit numbers. It is very
important to remember that when we write A*B = C, we more accurately
imply modulo(A*B) = C.
These Galois elements have many properties in common with the real
numbers:
- every nonzero x has an inverse x^-1 , such that x*x^-1=1
- (xy)^-1 = x^-1 * y^-1
- x(yz) = (xy)z
- x + (y + z) = (x +y) + z
- xy = yx
- x + y = y + x
- (x + y)z = xz + yz
- if xy = xz then x = 0 or y = z
- if xy = 0 then x = 0 or y = 0
- x^(a+b) = x^a * x^b (here a and b are standard numbers not in the
Galois field and a+b denotes standard addition)
There are also many properties which differ from the real numbers:
- for every nonzero x, x^255 = 1 (this implies that x^254 = x^-1)
- x + x = 0
15.2. Calculating WST FEC bytes
The FEC algorithm splits a serial stream of data into 448 byte
"bundles". These are arranged as 14 packets of 35 bytes each.
Across each packet the following expression is determined for each of
the two suffix bytes, bN and bN+1, which (with the addition of a
header) complete the WST packet (8+35+2):
We calculate:
b0 + b1 + b2 + b3 + .... + bN-1 = bN + bN+1 = X EQN [1]
and
a N+1.b0 + aN.b1 + .... + a2.bN-1 = a.bN + bN+1 = Y EQN[2]
Where N = number of characters in a row = 35, or characters in a
columns = 14.
bN is the Nth data element of the row or column.
a is the primitive element of the GF(2^8) Galois Field such that:
1, a, a2, a3, a4, ..... a253, a254
would be all of the 255 non-zero elements and a255 = a0 = 1.
The powers of a are tabulated in a look up table of log_a[ n]
and the inverse table,
a_to_power[n]
>From the two equations above,
bN + bN+1 = X
a.bN + bN+1 = Y
gives
X + Y = (1 + a). bN
giving
bN = (X + Y) / (1+a)
(where 1+a = 0x03 and use log_a[j] - log_a[k] to perform the
division, and
X + Y implies X xor Y)
and
bN+1 = bN + X
There is an exception case to account for when X = Y. If this occurs,
X + Y = 0
and the log_a[0] cannot be taken. Then by definition bN must be zero,
otherwise:
X = bN + bN+1 and
Y = a.bN + bN+1
cannot simultaneously be true. When bN = 0 then bN+1 = X + Y.
The multiplications and additions in this formula are done using
Galois fields and modulo 100011101 arithmetic.
Once we have encoded the block of data it looks like:
1 2 3 4.....................................................35 36 37
1 ---------------------------------------------------------------P P
2 ---------------------------------------------------------------P P
. ---------------------------------------------------------------P P
. ...................................................................
. ---------------------------------------------------------------P P
. ---------------------------------------------------------------P P
. ---------------------------------------------------------------P P
. ---------------------------------------------------------------P P
14 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP P
15 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP P
Where '-' denotes a data byte and 'P' denotes a suffix byte.
15.3. Correcting Errors using the WST FEC
This section describes the procedure for detecting and correcting
errors using the FEC data calculated above. Upon reception we begin
by arranging the packets in tabular form similar to that in the
previous section. We form a column of 16 packets each containing 37
bytes of data. We will be detecting and correcting errors in these
rows and columns.
Since the horizontal and vertical FEC are the same (except for the
number of bytes of data to be protected), the algorithms here will
work in both directions.
15.3.1. Detecting and correcting single-byte errors
>From section 15.2, equations [1] and [2], we have
b0 + b1 + b2 + b3 + .... + bN-1 + bN + bN+1 = 0 EQN [1]
and
a N+1.b0 + aN.b1 + .... + a2.bN-1 + a.bN + bN+1 = 0 EQN[2]
where bx are the broadcast data bytes.
So we calculate:
r0 + r1 + r2 + r3 + .... + rN-1 + rN + rN+1 = S0
and
a N+1.r0 + aN.r1 + .... + a2.rN-1 + a.rN + rN+1 = S1
where rx are the received data bytes.
If S0=S1=0, there are no errors.
Otherwise
S0 = Ei and S1 = aN+1-i.Ei
The error value is therefore given directly by syndrome byte S0 and
the error position (p) by S1 with use of the log_a[n] table.
If the position p > N then we assume that there are at least two
errors in the block.
It should be noted that by using any of the above corrections it is
possible to mistakenly turn a two-byte error into a three-byte error.
15.3.2. Correcting Double-byte Erasures
In the case of a double byte erasure, we lose all error-detecting
capability. Given the location of two erasures we can correct them
assuming all other bytes are correct. It is possible to utilize this
FEC to correct double errors by marking erasures and performing
multiple passes.
The subject of erasure marking and processing is not discussed in
detail here.
15.4. Correcting WST FEC Bundles
We now have a set of tools for detecting and correcting errors in FEC
bundles.
1) With no erasures, we can look at a row or column and say either:
- The FEC bytes match; there are probably no errors.
- The FEC bytes fail to match in a way which could be
caused by a single-byte error; in this case we can
find the location and value of such an error.
- The FEC bytes fail to match in a way which indicates
that there are at least two bytes of error.
2) With one erasure, we can correct it and look at a line and say
either:
- The FEC bytes now match; there are probably no other
errors (beyond the erasure)
- The FEC bytes don't match; there is at least one
more error, which we cannot correct.
3) With two erasures, we can correct the line so that the FEC bytes
match. In this case, we have no error-detecting capability.
All of these tools can be used in an iterative manner on the rows and
columns of the FEC bundle to correct or detect errors.
15.5. WST FEC Appendix References
[1] Philips Semiconductors Systems Laboratory Southampton Internal
Report "CD-ROM Third Level Error Correction Algorithmic Background",
1995, Bruce Murray
[2] Philips Semiconductors Systems Laboratory Southampton. "SAA5284
User Guide STX/UM96009", 1996, Nick Thorne