Method and system for inserting and retrieving data in an audio signal

[0002] (This application is a Continuation of U.S. patent application Ser. No. 08/890,533 abandoned as of Jul. 9, 1997 which is a Continuation of Patent Cooperation Treaty Application No. PCT/US97/03517, filed Mar. 3, 1997 which claims priority of U.S. Provisional Application Ser. No. 60/012,749, filed Mar. 4, 1996)

[0003] The transmission and reception of audio information pervades our environment. Radio broadcasts and the audio channel of television broadcasts issue virtually unending streams of audio. Audio recordings are manufactured, distributed and played back on a variety of equipment. Entire industries exist for the creation and dissemination of such products.

[0004] The maintenance of records concerning the transmission and reception of such audio data is a daunting task which is faced in various forms by numerous entities. Broadcasters are required to keep logs of their transmissions. Both individual stations and their affiliated networks need to know, for example, that a particular sponsor's promotion or “spot”, for which the station and network have received revenue, was in fact broadcast in accordance with the agreement with the sponsor. Similarly, the sponsor and/or its advertising agency require assurances that the sponsor has received full value for its payment, and that its spot was broadcast by the contracted-for station or stations, at the contracted time or times, in its entirety.

[0005] Producers and distributors of audio recordings can obtain valuable marketing data from the analysis of the time and frequencies of broadcast of their releases. Such data can be of particular value in the analysis of the efficacy of promotional efforts for a particular artist or recording in a particular market. Licensing organizations can use frequency-of-broadcast data in their royalty disbursement calculations.

[0006] Traditional methods for the collection and auditing of broadcast data has been both laborious, time-intensive, and costly. Typically, a monitoring organization would monitor the transmission of a station of interest and manually record the identity of a particular broadcast segment and its air time. The continuous monitoring of a station requires the continuous presence of a listener. If more than one station is to be monitored, additional monitoring personnel are required. While the recordation of broadcasts are sometimes utilized for subsequent review, current methodology still requires the playback and monitoring of the recording, and thus serves only to time-shift the monitoring process, without effecting its actual duration. It has been estimated that an overall accuracy of no more than 70% typically results from conventional monitoring methodologies.

[0007] Various methods have been proposed to automate the auditing process. Such proposals have included the monitoring of a broadcast for a particular audio “signature”, which would correspond to a known signature for a given broadcast segment. Such methods have met with only limited success.

[0008] To be of value, an automated system for audio signal recognition and identification must be essentially inaudible to at least the typical listener. It also must be “robust”, providing a high degree of accuracy and being capable of detection after the audio track with which it is employed has passed through any of the variety of transmission and processing media and equipment typically utilized in conventional broadcasts. It also should be relatively immune from detection or modification.

[0009] The above and other objectives and purposes are met by the present invention, which masks a stream of digital data with a primary audio signal in a manner which does not perceptively change the quality of the primary audio signal. The combined composite signal is capable of recordation and transmission over a wide range of media, and demonstrates a high degree of covertness.

[0010] The digital format data stream to be inserted is preferably divided into a plurality of strings of a chosen length, and each of the strings is algebraically added or “inserted,” on a bit-by-bit basis, with the audio program material along a determined portion of the program material, the portion being chosen to maximize the covertness of the inserted data. In order to facilitate the subsequent identification and extraction of the inserted data, each insertion may comprise, in addition to chosen data, which may for example be specific to the program material, synchronization data of a consistent format which is searched for as part of the decoding process and which identifies the insertion of the digital data string.

[0011] The particular portion of the program material along which a data string is inserted is preferably determined by a process whereby the data string to be inserted is algebraically added with the audio program along each of a plurality of potential portions or sites within a given longer segment of the audio program. At each potential data bit insertion location along a particular portion of the program material, the amplitude required for each inserted bit is individually determined so that the audio program signal at that bit location will not cause an incorrect detection of that bit (i.e., a one detected as a zero or a zero detected as a one) when an attempt is made to extract the inserted data bit at the receiver. A series of tests is applied to each of the resulting composite signal portions, and the results of the tests are compared to determine which of the alternative portions produces a composite signal best demonstrating sufficient covertness. It has been found that one meaningful covertness criterion is the consideration of signal energy of the composite signal in particular frequency bands, over an interval of time equal to the insertion interval, with smaller energy deviations from that of the original signal indicating increasing covertness. Another meaningful covertness criterion has been found to be the extent of deviation of energy of the original signal from its mean value in a particular frequency band over the same time interval, with smaller deviations from the mean indicating increasing covertness.

[0012] Once the optimal location for the data string is found along a given segment or interval of the audio program and the insertion is performed, a next audio segment can be chosen for possible data insertion. Potential insertion portions are again identified and tested with the data string to be inserted therealong. The testing and insertion process can be repeated as desired through a series of potential insertion portions, and with data to be inserted, across any chosen total duration or extent of the audio program material.

[0013] The inserted digital data is retrieved from the composite signal by processing the composite signal, such as by filtering, to first eliminate portions of the signal which are unrelated to the inserted data. The remaining signal is compared to the known synchronization data pattern present in each insertion to identify the portion of the received signal which includes the inserted data string. The identification of the synchronization data pattern allows the remaining portion of the data string to be located and retrieved for subsequent processing. In a preferred embodiment, the composite audio signal is digitized, bandpass-filtered, matched-filtered, and threshold-detected. The detected bits are passed in a step-wise manner through a shift register which allows the composite signal to be compared on a step-wise, bit-by-bit basis with the sync data pattern. With use of a data signal of known length, the data bits can then be identified from their positional relationship to the identified sync data, and thus can be extracted and processed.

[0014] A fuller understanding of the present invention, and the features and characteristics thereof can be obtained upon consideration of the following detailed description of a preferred, but nonetheless illustrative embodiment thereof when reviewed in conjunction with the annexed drawings, wherein:

[0015] FIG. 1 is a representation of a representative data stream intended to be embedded in an audio track in accordance with the present invention;

[0016] FIG. 1ais a representation of a preferred arrangement of synchronization and data bits in a data string;

[0017] FIG. 2 is a representation of a portion of a data string in a biphase modulation format;

[0018] FIG. 3 is a frequency-domain plot of a phase-shift keyed burst signal of fundamental frequency F_cwith a bit interval of T seconds;

[0019] FIG. 4ais a depiction of a bit in a sinusoidally-weighted biphase-modulation format, while FIG. 4bis a frequency-domain plot of the bit in FIG. 4a;

[0020] FIG. 5 is a representation (not to scale) of the alternative locations for insertion of a data string in an audio program segment;

[0021] FIG. 6 is a detailed representation of a portion of a frequency-domain plot of a preferred sinusoidally-weighted biphase-shift-keyed signal utilized in the present invention; and

[0022] FIG. 7 is a block diagram of a receiver of the present invention.

[0023] As depicted in FIG. 1, data which is intended to be embedded in an audio signal in accordance with the present invention is preferably in the form of a binary data string 10 of a chosen fixed length. In a preferred embodiment of the invention, the data string 10 may be 60 bits in length, comprising 24 bits of synchronization data 12 and 36 bits of information data 14. The synchronization data is placed at a given location on the string, the information data filling the remaining locations. The synchronization data string is further of a fixed, known pattern, chosen as known in the art to enable the locating of the information data, while the information data is typically of “random” content. The information data may be constant, or may vary from data string to data string, either because each data string is intended to carry varying information, or because the amount of constant information to be encoded extends beyond the space allocated to information data in a single string. For broadcast audio identification purposes, such information could include a coded identification of the program material. In such a case, the information may merely be repeated in each string, it being intended that data strings be embedded along the entire length of the associated audio track.

[0024] As shown in FIG. 1, the synchronization data 12 may be the leading portion of the data string, although it can be at other locations, and can be broken into parts along the data string. In a preferred embodiment, as shown in FIG. 1a, the synchronization bits S may be interleaved with data bits D so that every pair of sync bits has one data bit between them. The remaining 13 data bits (36 total−23 interleaved) are divided into two groups, with a group of six bits immediately preceding the synchronization pattern, and the remaining seven bits immediately following. In order to facilitate combining the data string 10 with the analog audio signal, the data string may be converted to a biphase modulated waveform string 16 of a chosen audio frequency as shown in FIG. 2. As known in such a modulation technique, the waveforms for digital “1s” (18) and “0s” (20) have a phase difference of 180 degrees, such that the resulting signal for the data consists of a series of fixed-frequency sinusoidal bursts each of fixed duration T differing only in their relative phase. Known demodulation techniques are available for converting such signals back into digital data.

[0025] Although the time domain representation of the phase-encoded signal for a bit is a single-frequency signal of frequency F_cover the interval T, in the frequency domain the signal has the characteristics shown in FIG. 3. As shown therein, the data burst frequency spectrum has an energy maxima at center frequency F_ccorresponding to the frequency F_cof the sinusoid (here 5333.3 Hz), with subsequent lesser maxima extending at frequencies both above and below the center frequency. The energy minima on either side of the peak maxima at F_care located at a series of frequencies equal to F_c±n/T (n=1,2, . . . ) with the first maximas being approximately 13 db below the peak energy of the center frequency component. Consideration of the frequency domain is important, since the total energy of the data burst signal is seen to spread across a range of frequencies. As the available bandwidth associated with certain transmission media may be limited, it may be of value that the energy of the data waveform to be inserted be maximized at one or more frequencies which comfortably fit within the available bandwidth range.

[0026] A bit in a biphase-modulated bit stream can be thought of as a sinusoid (the carrier) multiplied by a rectangular pulse that is either positive or negative, depending on the value of the bit. The use of a rectangular pulse is sometimes referred to as “rectangular weighting”. In order to lessen the division of energy of the inserted data across a plurality of frequencies, the use of half-sinusoid weighting is currently preferred. As known in the art, such a technique envelops the fixed-frequency burst with a sinusoidal envelope, as shown in FIG. 4a. The resulting frequency domain representation for the signal is shown in FIG. 4b. While the harmonic maxima are somewhat greater displaced from the center frequency F_c, the first harmonic maxima are depressed approximately 20 db below the peak of central lobe. Thus, a greater proportion of the total energy content is located at the central lobe at F_c. As shown in FIG. 4a, 3.5 cycles of the carrier are enveloped by a sinusoid having a period equal to twice the duration of the burst to be enveloped.

[0027] When the specific locations along the audio signal for combining the audio with the digital data bits are chosen in accordance with the present invention, and the digital data bits—in their carrier modulated form—are algebraically added to the audio, the resulting composite signal is substantially indistinguishable from the original signal and thus can be transmitted, broadcast and received without listener perception that, in addition to the perceived audio, a data track is present.

[0028] In order to determine the appropriate positions for data insertion within a continuously varying audio program, the phase-modulated data string to be inserted is “tested” at a plurality of positions within a referenced length of audio. Accordingly, the audio program material is initially divided into segments of a chosen, predetermined duration into each of which a data string 16 is intended to be inserted. Typically, the length of the audio signal is chosen such that the data string to be inserted can be tested at a plurality of alternative positions. In a presently preferred embodiment of the invention, the segment duration is one second. In order to conveniently combine the data string with the audio signal, the audio signal segment itself may be digitized or segmented. The bits of the data string can then be combined algebraically with a corresponding segment of the digitized audio signal to yield the encoded composite signal. A chosen sampling or digitizing frequency for the audio program of 32 kHz, a center frequency F_cfor the sinusoidally-weighted biphase-modulated data bits of 5333.3 hertz, and a bit length of 3.5 cycles of carrier at F_cis presently contemplated.

[0029] An entire data signal of 60 bits in length is tested against successive 60 insertion location portions of the selected audio segment to determine, of the alternative locations available therein, which location provides sufficient covertness for the inserted data while still allowing the encoded data to be retrieved at the receiver location. In accordance with an aspect of the present invention, covertness can be characterized as a function of energy gain of the combined signal in certain frequency bands; the smaller the energy gain, the greater the covertness.

[0030] In order to determine the energy values of the alternative insertions for purposes of comparison, the insertion methodology includes the replication of the decoder mechanism to be used at the receiver at the insertion point. The program audio signal to which the data stream is to be added is passed through the replicated decoder by itself to determine an output “profile” when no data signal is present. The output of the decoder may then be used to compute the amplitude required of each modulated bit of data to be added such that, when the composite signal in that bit location is passed through the actual receiver detector, a correct determination will be made with respect to the presence and value for that bit. The process of determining bit amplitude may include incorporation of a safety margin to allow for anticipated distortions that the composite signal may experience before processing by the receiver. This safety margin would be tailored to the individual application. Once the needed amplitude for each bit in the 60-bit data string is determined and the data string combined with the audio in accordance with the determined formula, an energy analysis of the composite signal portion is performed. The energy analysis allows a relative covertness value for the sum total of the necessary amplitude adjustments to be calculated.

[0031] Determination of the necessary amplitude for each data bit proceeds on a bit-by-bit incremental basis through a proposed 60-bit location set in a one second audio track insertion interval. A first location set is identified, and the audio program signal present at the intended location of the first bit of data in the location set is passed through the receiver-equivalent circuitry implemented as part of the insertion system. The magnitude and polarity of the signal appearing at the output of the receiver due to the presence of audio program signal is noted. Since the output of the receiver due to an inserted data bit of unit amplitude is a determined known value, and since the receiver-equivalent circuitry is linear, it is a simple matter, and well known in the art, to compute the amplitude required of the inserted bit to overcome the “interference” at the output of the receiver due to the program signal. The computed amplitude may be zero. This would occur, for example, whenever the polarity at the output of the receiver due to the program signal is the same as the polarity that would be produced by an inserted data bit. In other words, so long as the program material produces a response at the output of the receiver that is the desired response due to an inserted bit, it is not necessary to modify the program material by addition of a bit signal. However, in a practical system where distortions are to be encountered between data insertion and extraction, it is important that the amplitude of a bit signal never be zero. To accommodate such distortions, in a preferred embodiment no bit signal has an amplitude smaller than 0.2 times the largest amplitude in the insertion interval. The required amplitude of each data bit is computed on a bit-by-bit basis until all 60 amplitudes have been computed.

[0032] The set of required amplitude values needed to successfully decode each of the 60 bits is then stored in memory along with their corresponding insertion locations within the audio track insertion interval. A next location set for the proposed insertion is then identified, typically by incrementing the starting location by a desired value, and the entire 60-bit insertion is repeated, again computing the needed amplitude for each data bit on a bit-by-bit basis until the entire 60-bit sequence can be fully demodulated. In a preferred embodiment, the increment corresponds to 60 degrees of phase of the 5333.3 Hz carrier, or 1/32,000 second. The procedure is repeated until a full data insertion at each available 60-bit location set commencing along the entire length of the insertion interval is performed.

[0033] The foregoing is depicted in FIG. 5. As shown therein, a 1-second interval 100 of the audio program is capable of receiving a starting bit of 60-bit data string 102, each bit being 3.5 cycles in duration at 5333.3 Hz, at 32,000 alternative locations, where the offset T between successive starting locations is 1/32000 second.

[0034] In order to avoid having to store and test thousands of amplitude value sets (in the preferred embodiment 32,000 sets for a 1 second duration of audio program), a preliminary test may be performed on a set of amplitude values to reduce the number of sets to be stored. The test consists of computing the total energy of the insertion from the amplitude values, and comparing this energy to the energy of the audio program signal alone over the insertion interval. The comparison may be over a frequency range or band corresponding to the frequency width of the main lobe of the data signal. If the ratio of total energy to audio program energy exceeds a certain value, the amplitude set is discarded. In the presently preferred embodiment this ratio is 4:1.

[0035] Once a matrix of insertion amplitude value sets is created for all the possible location sets of an insertion interval, the methodology of the present invention calls for the analysis of each set of amplitude values to determine which set, overall, adds the minimum amount of energy to the original audio signal. This analysis can preferably be performed in certain frequency bands. The set having minimal added energy is chosen for actual insertion into the audio signal for transmission.

[0036] As a first measurement of energy, the mean or average energy in two frequency bands over the 60 insertion points can be calculated. While consideration of the energy added by a particular insertion is a measure of its relative covertness, guidelines can be developed to further insure that the “best” insertion location meets minimal requirements for covertness. It has been found, for example, that the ratio of composite signal energy to program material energy in each of the frequency bands over the duration of the insertion should be less than four, in order to have a combined signal in which the added data signal is “inaudible”. In addition, the energy of the program material alone should be above another, fixed threshold, to avoid insertion locations in which there is no or little program material. Currently, this criteria is met by having the average energy for the program material to be no more than 70 db below the nominal peak energy of the material. It is only when these two criteria are met for a given insertion location set that the set remains viable for comparison against other candidates.

[0037] In addition, it has been found experimentally that, as a result of the wide variability of audio program material, a choice of insertion point calculated solely upon an analysis of mean energy may be in some circumstances insufficient to identify the preferred location for data insertion. Accordingly, additional tests of the energy value of the insertion can be performed. A presently preferred energy analysis consists of several calculations.

[0038] FIG. 6 depicts the central portion of the frequency spectrum for a sinusoidally-weighted biphase-modulated signal having a center frequency of 5333.3 Hz and a repetition rate of 1523.8 bps (bits per second). A first calculation determines the mean energy ratio between the composite signal and the audio program material alone over a frequency band centered on the center frequency and extending from 4381 to 6286 Hz. A second energy calculation computes the ratio of the standard deviation of energy to energy of the program signal in that frequency band. It has been found that such a ratio allows the system to discriminate against audio signals having a high harmonic content, such as are present in certain musical passages. A third calculation determines the energy ratio between the composite signal and program material alone over a band extending from 6286 Hz to 7238 Hz.

[0039] Benchmark criteria can be set for the results of each of these tests. For a set of insertion points to be further tested for viability, the energy ratio over the first band (4381-6286 Hz) should be less than 4, while the standard deviation ratio in the same band should be less than 1.6. When employed, the energy ratio over the second band (6286-7238 Hz) should also be less than 4. For the sets of insertion points which meet each of the criteria, a further comparison between sets is performed to identify the optimal location. The values for each insertion are compared to each other, and the location having the best overall figures is designated. In the preferred embodiment, the insertion candidate with the minimum sum-of-squares of the three ratios is chosen.

[0040] Providing for data insertion at one-second intervals can provide redundancy over the extended course of an audio program. It is possible, however, to have multiple insertions within a one-second interval. In general, the greater the number of insertions the greater the likelihood that the overall audio quality of the original program may be modified sufficiently such that some “difference”, albeit undefined, from the original source may be able to be perceived. It has been found that a maximum of one insertion per second of audio provides an acceptable compromise between the amount of data able to be inserted and the risk of audio signal degradation as a result of “excessive” insertion.

[0041] A receiver in accordance with the present invention is depicted in FIG. 7. As shown therein, the composite signal 20 is digitized by digitizer 22, at a sample rate of at least twice the highest frequency of interest in the spectrum of the inserted signal. In the present embodiment, the sample rate is 16 kHz. The digitized signal is then passed through an appropriate bandpass filter 24 chosen to pass at least the highest energy portion of the frequency spectrum of the modulated data signal. For the preferred embodiment, the frequencies passed would include those of the main lobe shown in FIG. 4b; all other frequencies would be excluded. For a data signal subject to sinusoidally-weighted biphase-shift keying, the signal is then passed through a matched filter 28, as known in the art. Such a filter has a frequency response which closely replicates the spectrum of the bit, and further tailors the received signal to maximize the information content of the signal portion to be analyzed.

[0042] The next step in the demodulation process is to sample the output of the matched filter at a time corresponding to the width and timing for passage of an entire bit through the matched filter. If the sample, for example, is of “positive” value or voltage, a “one” bit is detected, if the sample is of “negative” value or voltage, a zero bit is detected. Such a method is well known in the art. It is important, however, that the filter output sampling be precisely coordinated with data bit passage. To determine the correct sample times, and to demodulate the data, the matched-filter output is passed to a signal processor/detector 26.

[0043] The matched-filter output is analyzed by the detector to locate the sync data. This is performed by inspecting, on a step-wise basis, the matched-filter output to determine if the synchronization data is present, indicating that an embedded data string has been located. This inspection may be done by passing the matched-filter output across an analysis window of a width corresponding to at least the sync data portion of the 60-bit width of a data string, and inspecting the appropriate portions thereof for the existence of the known sync bit pattern. As may be appreciated, it is necessary that the location of the data string in the continuous composite signal be determined with precision to allow proper inspection and identification of both the sync and accompanying data bit portions.

[0044] To aid in locating the sync pattern and detecting the data, the sampling rate at the output of the matched filter is increased by the signal processor/detector to a rate high enough to insure that at least one sample corresponds closely enough in time to the correct sampling instant for each bit to insure accurate detection. In the preferred embodiment, this sample rate is 64,000 samples per second (42 samples per bit). The process of sample rate conversion is well known in the art. After sample rate conversion the samples are “detected”, that is, for example, positive samples are converted to logical ones and negative samples are converted to logical zeros, whereby a data train is produced.

[0045] After sample rate conversion and detection, the process of locating the synchronization pattern can preferably be performed by passing the data train through a shift register, as known in the art, synchronized to the increased 64kHz sampling rate. The “bins” of the shift register are 42 samples wide, corresponding to the full width of each inserted data bit. The “length” of the shift register is chosen to span the length of the synchronization data portion of the data string. Taps are spaced at intervals along the shift register corresponding to the temporal spacing between individual bits of the synchronization pattern at insertion. At each shift of the register, the tap outputs are compared to the known synchronization data pattern. When a high correlation is found, it is assumed that the remaining bits in the 60-bit sequence represent the transmitted data portion of the data string. In the preferred embodiment, a perfect match with the sync word pattern is required. Assuming the shift register is long enough to encompass the complete 60-bit data sequence, the data string can be obtained by merely providing shift register taps at cells spaced appropriately relative to the synchronization bit taps.

[0046] The data string data may itself include test and error correction bits, subject to procedures as known in the art, whereby the integrity of the data may be determined. The use of such error correction methodology is encouraged, as it is possible that the audio signal alone may, in certain circumstances, replicate the synchronization bits. Error checking within the data field will substantially minimize the risk of such “false positives” carrying artificial “data” into the processing stream.

[0047] Because of the robustness of the insertion methodology of the present invention, it is possible for data to be embedded in an audio track early on in the distribution chain. Information can be added, for example, to a master tape recording, and will be carried forward through transmission and duplication processes which may occur prior to an ultimate broadcast of the track. The subsequent broadcast can be received and decoded with results equivalent to usage of the master recording for broadcast purposes.

[0048] Certain processes utilized particularly in the radio broadcast industry, however, subject audio tracks to time compression or time expansion prior to broadcast. Such techniques have the effect of varying the apparent frequencies of the audio to which the processing is applied, thus shifting the frequency spectrum of the inserted data signal and consequently affecting the ability of a receiver and filter system of the present invention to isolate the particular frequency band or bands in which the embedded data is located.

[0049] In order to combat this problem, the receiver may be provided with a set of parallel processing paths each in accordance with FIG. 7. Each path includes a bandpass filter 24 and a matched filter which are tuned to a different center frequency, the frequencies and passbands of the filters being chosen to extend across the possible variation in frequency resulting from the broadcast time compression or expansion. The outputs of the decoding process for each of the parallel paths may be compared to determine which path corresponds to the compression or expansion utilized. This procedure is known in the art as “Doppler bin searching”.