MULTIPLE TONE DATA ENCODING AND DECODING IN VIDEO CARRIER SIGNALS BACKGROUND OF THE INVENTION Field of the Invention This invention relates to the field of transmission of non-visual data via a video signal. In particular, the invention relates to techniques for encoding and transmitting digital data in a visible optical signal.
Description of the Related Art The present invention provides for transmission of digital data along with any standard television or computer video signal for reception by a remote device held near the television screen.
Methods of transmission of data together with television signals from a remote video broadcast site to home television viewers over conventional broadcast channels include, but are not limited to: Vertical Blanking Interval (VBI) data transmissions--typically Teletext and closed captioning for the hearing impaired; FM broadcast radio subcarrier, and Cellular telephone-like data transmission systems. Only television sets specially equipped with decoders for displaying video text in synchronization with the television's raster scan electronics are able to display the captions making such systems complex and not readily available to most television viewers.
Subliminal encoding of data has been used to minimize adverse impact on the effective viewing area of the video program material. A method for subliminally encoding binary data, within the viewing area of a video program image that is substantially invisible to a viewer of the television is described in U. S. Pat. No. 4,807,031 issued to Broughton et al. on Feb. 21,1989. According to the invention of Broughton et al., the data encoding method involves modulating a video signal at frequencies that are related to multiples and sub- multiples of the horizontal line rate, to produce a subtle video subcarrier such as
pulse modulation (PM), phase modulation (PM), amplitude modulation (AM), frequency modulation (FM), time or pulse interval modulation (PIM), frequency shift keying (FSK), return-to-zero (RZ), non-return-to-zero (NRZ), or any other of a variety of spatio-temporal modulation and coding techniques. Although the modulation is within the viewing area of the television screen, it remains substantially invisible to the viewer because of its relatively low intensity. The encoded information can be recovered in a remote receiver aimed at the displayed television image to capture the information.
The problems associated with the Broughton arrangement are caused by generating the subliminal encoding by selectively increasing the intensity of one of each pair of adjacent scan lines in each frame of the video image. The problem with this approach is that the encoded information causes changes in the frequency domain representation of the video portion of the television signal, which occur at one-half of the line rate. Since there is a strong signal present at this frequency even without data present, the encoded information is difficult to capture in the receiver.
An improvement over Broughton et al. is described in U. S. Patent No.
5,633,766 issued to Sizer, II, on Sep. 2,1997 where the digital information is encoded by modulating a carrier signal or tone, using, for example, amplitude shift keying (ASK) or frequency shift keying (FSK), and the modulated carrier is then added to the video signal selectively, only in portions of the television program that (a) are not likely to be perceptible by a viewer, and (b) are of sufficient intensity to transmit the data. However, the subliminal nature of the luminance modulation necessitates transmission of a relatively low intensity signal.
Broughton et al. and Sizer, II, both involve transmitting data in a manner which is imperceptible to the viewer in order to avoid complaints from non- subscribing consumers and FCC restrictions. However, both of these techniques suffer from limitations in performance and bandwidth. In particular, the system used in Sizer uses two tones for encoding a bit and a bit bar signal. This system is not extensible to multiple tones, however, as the decoding techniques
suggested in Sizer are unable to distinguish between multiple frequencies spaced closely together.
Accordingly, it is an object of the present invention to provide a method for encoding and digital data in a visible optical signal and transmitting the data during a remote video broadcast to a remote device by use of a carrier signal superimposed with two or more tones. Another object of the invention is to provide a robust decoding system, which can reliably distinguish between multiple frequencies spaced closely together.
SUMMARY OF THE INVENTION The invention comprises a system and method for encoding and decoding data from modulated carrier signals received optically from a raster- scanned display. Data may be imposed upon the luminance and/or chrominance portion of the display. In an embodiment of the invention, the data is superimposed at a rate four times per field and at frequencies approximately 25 kHz for a mark and 25.6 kHz for a space. Other embodiments involve different frequencies for mark and space, alternatively, bit and bit bar. In one embodiment, the data is imposed at four frequencies, the four frequencies corresponding to the signals {00 01 10 11}. In another embodiment, the data is imposed using eight frequencies, corresponding to the signals {000 001 010 011 100 101 110 111}. Thus the invention multiplies the bandwidth of conventional carrier-signal based encoding systems.
A decoder in the invention may include a photo receiver, an amplifier, and a filter circuit coupled to a DSP processor for decoding the signals received from the display. The DSP processor employs Discrete Fourier Transforms, or DFTs, to decode the signal. This decoding technique allows signals to be discerned more robustly than permissible in conventional systems. Execution of the DFT may include use of a Fast Fourier Transformation, or FFT.
Embodiments of the invention include a method for decoding an optical signal from a raster-scanned display, wherein the optical signal is received in a decoder unit from the raster scanned display. The optical signal in such embodiments may include a carrier signal modulated with a plurality of frequency keys.
The optical signal is processed in a digital signal processor by transforming a plurality of samples of the optical signal to the plurality of keys by a Discrete Fourier Transform. In some embodiments, the plurality of frequency keys comprises four or more frequency keys. In some such embodiments, each of the four or more frequency keys is mapped to a 2-tuple.
In other embodiments, the plurality of frequency keys comprises eight or more frequency keys. In some such embodiments, each of the plurality of frequency keys are mapped to a 3-tuple.
The carrier signal may be luminance or chrominance modulated. In some embodiments, a Fast Fourier Transform is to the plurality of samples to perform the DFT. In some embodiments, the modulated carrier signal is subliminal, thus imperceptible to viewers. The raster scanned display may be a television operating on NTSC, PAL, or SECAM. The display may be interlaced or progressive scanned. These and other embodiments shall be described in greater detail infra.
BRIEF DESCRIPTION OF THE FIGURES Fig. 1 illustrates a raster-scanned display and a decoder used in embodiments of the invention.
Fig. 2 is a schematic illustration of a decoder circuit according to an embodiment of the invention.
Fig. 3 is an envelope of data encoded in a carrier signal.
Fig. 4 shows spectral peaks at two frequencies according to embodiments of the invention.
Fig. 5 is an expanded view of spectral plats according to embodiments of the invention.
Fig. 6 is a flowchart for application of a DFT to decode samples of the optical signal.
DETAILED DESCRIPTION A. System Overview Figure 1 illustrates the operation of an encoding/decoding system as used in the invention. Data is imposed upon the luminance portion of a raster scanned display 100. In alternative embodiments, data may be imposed upon the chrominance portion of the display 100. The data is encoded by modulating the luminance, or alternative chrominance, of a carrier signal fed to the raster scanned display 100. In embodiments of the invention, the modulated carrier signal is subliminal, i. e., imperceptible to a viewer.
Embodiments of the invention employ Frequency Shift Keying, or FSK, to encode data signals. Some such embodiments encode a bit signal and a bit bar signal with different frequency keys. In an embodiment of the invention, the data is superimposed at a rate four times per field and at frequencies approximately 25 kHz for a bit and 25.6 kHz for a bit bar. Other embodiments involve different frequencies for bit and bit bar. In one embodiment, the data is imposed at four frequencies, the four frequencies corresponding to the bit pairs {00 01 10 11}. In another embodiment, the data is imposed using eight frequencies, corresponding to the bit three-tuples {000 001 010 011 100 101 110 111}.
A decoder 102 may include a photo receiver 200, and amplifier 202, and a filter circuit 204, as illustrated schematically in Fig. 2. The decoder also includes a DSP processor 206 for decoding the signals received from the television 100. The DSP 206 employs Discrete Fourier Transforms, or DFTs, to decode the signal. The DSP may include a Field Programmable Gate Array, or FPGA, for performing the DFT. Examples of FPGAs which may be used in the decoder 102 include those developed by Xilinx, Inc., or alternatives apparent to those skilled in the art. The decoder 102 may be a portable handheld unit, or alternatively, a stationary device.
B. Numerics for Frequency Shift Keying An embodiment of the invention employs Frequency Shift Keying, or FSK, for signaling and demodulation. In one such embodiment, the decoder samples the optical signal at a rate of 16. 121856 MHz. Selecting 161 and 157 as divide ratios, an average of 161 yields 100136 Hz, and an average of 157 yields 102687 Hz. As will be apparent to one skilled in the art, multiplying by proper sequences for inphase and quadrature, i. e., I and Q, yields frequencies: 25.034 kHz and 25.672 kHz.
These frequencies may be used for bit and bit bar. Alternative frequencies for bit and bit bar will be apparent to those skilled in the art.
Embodiments of the invention are directed towards an NTSC broadcast standard. In such television systems, there are 525 lines total or 262.5 lines per field of which 22 are retrace, for a total of 242.5 useful per field. Thus, to encode 4 bits per filed, each bit may last up to 60 lines per bit. In such an embodiment, each line is of duration 1/ (30*525) =63.49 (isec which makes a symbol duration of around 60*63.49=3.8095 msec (262.5 baud).
Symbol duration times, as well as line, field, and frame rate, will differ for other television standards, such as PAL and SECAM. It will be clear to one skilled in the art that the FSK techniques described for NTSC are easily portable to other broadcast standards, including but not limited to PAL and SECAM.
C. Signal Decoding Using the DSP Figure 3 shows an envelope of data 300 imposed upon a carrier signal sent to the display 100. Figure 4 illustrates an effective demodulation of the modulated signal received at the decoder 102 comprising 20 milliseconds of 8 bit data sampled at a 500 kHz rate. The originating luminance from the display 100 is the carrier signal modulated with an additive signal at the 25 kHz and 25.6 kHz FSK frequencies according to an embodiment discussed above.
The received signal is gathered in the decoder 102. The demodulation is performed by a DFT, implemented with a series of overlapping Fast Fourier Transforms, or FFT'S, of size 1200 samples apiece (2.4 millisecond window), taken with an overlap of 100 samples (0.2 milliseconds overlap). This may be performed in the DSP 206. Other sample sizes may be also be used, as will be apparent to one skilled in the art. For each FFT the frequency of the maximum of the spectral peak is determined. An interpolation algorithm executed in the DSP 206 provides precise frequency to a resolution of about 4 Hz. Figure 4 shows examples of such spectral peaks. In Figure 4, the frequencies 25.6 kHz 400 and 25 kHz 402 are clearly discernible and the signal is oscillating between the two.
Figure 5 illustrates the spectral of several sections of the data corresponding to primary frequencies of 25 500 and 25.6 kHz 502. As will be apparent to one skilled in the art, the respective spectral peaks 500 502 are clean, well defined and with reasonable excess spreading.
D. Analysis of DFT on Two-Tone FSK A decoding technique used in embodiments of the invention includes DFT components at two frequencies by sampling the input signal at 16.121856 MHz, decimating by 161 and 157, to get effective sample rates at 16.121856 MHz/161 and 16.121856 MHz/157 and then evaluating the DFT at one-fourth of the effective sample rate. As will be apparent to one skilled in the art, such DFT's are easily done since they are performed by multiplying the resulting data by a sequence 1, j,-1,-j, for the duration of a bit period. For a 4 msec symbol period and around 100 kHz sample rate the DFT size is approximately 400 samples in length. Other effective sample rates will be apparent to those skilled in the art. In an embodiment of the invention, the initial decimation is done by simply integrating for 161, or 157 samples and dumping the result. The initial integrate and dump may be modeled as passing the original signal through a boxcar filter of duration 161 or 157 and then sampling the result at the decimated rate.
E. Decoding By Use of Discrete Fourier Transforms The decoding technique used by the decoder 102 is illustrated in the flow chart of Figure 6. The DFT 206 samples the signal received from the display 600. A Discrete Fourier Transform is performed on the samples 602 to retrieve frequency keys. The DFT is computed by use of a Fast Fourier Transformation, or FFT. In embodiments of the invention the DFT 602 and FFT 604 are performed in the DSP 206 of the decoder 102. The frequency keys retrieved are then mapped to bit sets 606 to decode the signal. The mapping step 606 may be illustrated for the example described above, in which the frequency key 25 KHz is mapped to a bit and the frequency key 25.6 KHz is mapped to a bit bar.
The measurements shown in figures 4 and 5 support the high performance of the two level FSK signaling described above. The invention can also support four tones and eight tones, thereby doubling and tripling the bit rates, respectively.
As a non-limiting example, note that the 2-level FSK described above may be expanded to four tones, for example, by using divide ratios 161,159, 157 and 155 which yields final frequencies {25034,25349,25672,26003} which are spaced by around 300 Hz. For a 4 msec symbol period there is essentially no correlation between the tones. These four frequencies may be mapped to the following bit sets, each of which is a 2-tuple: Table 1 FrequencyKeys(inKHz)BitSets 25.034 00 25.349 01 25.672 10 26.00311 Other frequency keys and mappings to 2-tuple bit sets will be apparent to one skilled in the art. Thus, with four tones, the bit rate is doubled.
If instead we use divide ratios separate by one, then the separation between tones would be around 150 Hz, which for a 4 msec symbol period would provide correlation between adjacent tones of 0.5. The total span of all such tones would be around 1250 Hz. It will be apparent to one skilled in the art that eight such tones, or frequency keys, may be mapped to eight different 3- tuple bit sets. This would provide a tripling of the bit rate.
F. Conclusion The foregoing description of various embodiments of the invention has been presented for purposes of illustration and description. It is not intended to limit the invention to the precise forms disclosed. Many modifications and equivalent arrangements will be apparent.