US006064737A
`6,064,737
`[11] Patent Number:
`United States Patent 15
`
`Rhoads
`[45] Date of Patent:
`May16, 2000
`
`[54] ANTI-PIRACY SYSTEM FOR WIRELESS
`TELEPHONY
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`[75]
`
`Inventor: Geoffrey B. Rhoads, West Linn, Oreg.
`
`[73] Assignee: Digimarce Corporation, Lake Oswego,
`Oreg.
`
`3/1997 Coopermanet al.
`...eceesseeeees 380/28
`5,613,004
`
`6/1997 Rhoads ............
`wee 382/232
`5,636,292
`
`
`11/1997 Moskowitz et al...
`eee 380/28
`5,687,236
`
`1/1998 Rhoads uses 380/18
`5,710,834
`.
`4/1998 Moskowitz et al.
`.. 380/28
`5,745,569
`4/1998 Rhoads oo...
`wu. 380/4
`5,745,604
`5/1998 Rhoads.....
`382/232
`5,748,763
`[21] Appl. No.: 09/172,324
`5/1998 Rhoads.....
`wee 382/232
`5,748,783
`.
`7/1998 Rhoads.....
`wees 382/232
`5,768,426
`Oct. 13, 1998
`Filed:
`[22]
`
`5,822,436 10/1998 Rhoads occeeeceeceneeeeeeoeee 380/54
`5,841,886
`Related U.S. Application Data
`11/1998 Rhoads.....
`382/232
`
`5,841,978eectscreceeteeeeee 380/2811/1998 Rhoads oo
`
`
`12/1998 Rhoads oo.eects ceceeeeeee 382/232
`5,850,481
`[63] Continuation of application No. 08/637,531, Apr. 25, 1996,
`Pat. No. 5,822,436.
`Primary Examiner—Salvatore Cangialosi
`Foreign Application Priority Data
`[57]
`ABSTRACT
`
`
`
`[30]
`
`Nov. 16, 1994 [WO] WIPO wees PCT/US94/13366
`
`[SL] Tt. C07 eeecceccccecsssecesssesessecssseessueeessness HO4L 9/00
`
`[52] U.S. Che eeeeecceeseecseeseesenseneneenseseecee 380/23; 380/28
`
`A method and system are described for reducing the theft of
`wireless telephony services, such as cellular systems and
`PCS systems, altering voice data to steganographically
`embed verification data therein. The verification data com-
`prises 2. plunality of synibels whieh are isteganoeraphieally
`detected at the carrier facility to confirm authorized use of
`the wireless device.
`
`[58] Field of Search occ 380/4, 18, 23,
`380/28, 54; 382/232
`
`10 Claims, 4 Drawing Sheets
`
`UNFORMATTER
`
`
`
`DATA
`
`
`
`Sony Exhibit 1049
`Sony Exhibit 1049
`Sony v. MZ Audio
`Sony v. MZ Audio
`
`

`

`
`
`
`FIG. 1
`
`yusyed“SN
`
`
`0007‘9TARIA
`pbJ9TWoUS
`
`LEL‘v90°9
`
`

`

`36
`
`GAIN
`CONTROL
`CIRCUIT
`
` ENCODED
`OUTPUT
`
`SIGNAL
`
`
`
`(>)
`
`
`
`LOGIC
`CIRCUIT
`
`
`
`
`46
`
`FIG. 2
`
`DIGITIZED
`VOICE
`DATA
`
`AUXILIARY
`DATA
`
`PSEUDO-
`RANDOM
`DATA
`
`yusyed“SN
`
`
`0007‘9TARIA
`bJ97WOUS
`
`LEL‘v90°9
`
`

`

`12
`
`
`
`
` FORMATTER
`
` VOICE
`
`
`DATA
`UNFORMATTER
`
`
`
`RF SECTION
`
`
`
`MODULATOR
`
`DEMODULATOR
`
`
`
`FIG. 3
`
`38
`
`AUX
`DATA
`OUT
`
`PRN
`IN
`
`TO
`CENTRAL
`OFFICE
`
`yusyed“SN
`
`
`0007‘9TARIA
`bJ9¢€WoUS
`
`LEL‘v90°9
`
`

`

`U.S. Patent
`
`May16, 2000
`
`Sheet 4 of 4
`
`6,064,737
`
`FIG. 4A
`
`EMBEDDED
`
`-—
`
`DIFFERENCE
`
`
`
`MEAN-REMOVED HISTOGRAMS OF
`DIFFERENCE SIGNAL AND KNOWN EMBEDDED
`CODE SIGNAL
`
`FIG. 4B
`
`EMBEDDED
`
`>
`
`DIFFERENCE
`
`
`
`™_\
`THRESHOLDING
`
`MEAN-REMOVED HISTOGRAMS OF
`FIRST DERIVATIVES (OR SCALER GRADIENTS
`IN THE CASE OF AN IMAGE)
`
`

`

`6,064,737
`
`1
`ANTI-PIRACY SYSTEM FOR WIRELESS
`TELEPHONY
`
`RELATED APPLICATION DATA
`
`This application is a continuation of application Ser. No.
`08/637,531, filed Apr. 25, 1996 now U.S. Pat. No. 5,822,
`436. The subject matter of the present application is also
`related to that disclosed in application Ser. No. 08/534,005,
`filed Sep. 25, 1995 now US'S. Pat. No. 5,832,119, Ser. No.
`08/512,993, filed Aug. 9, 1995 (abandoned in favor of FWC
`application 08/763,847, now U.S. Pat. No. 5,841,886); Ser.
`No. 08/508,083, filed Jul. 27, 1995 now U.S. Pat. No.
`5,841,978; Ser. No. 08/436,098 (now U.S. Pat. No. 5,636,
`292), Ser. No. 08/436,099 (now U.S. Pat. No. 5,710,834),
`Ser. No. 08/436,102 (now U.S. Pat. No. 5,748,783), Ser. No.
`08/436,134 (now U.S. Pat. No. 5,748,763), and Ser. No.
`08/438,159 now USS. Pat. No. 5,850,481, each filed May 8,
`1995; Ser. No. 08/327,426, filed Oct. 21, 1994 (now US.
`Pat. No. 5,768,426); Ser. No. 08/215,289, filed Mar. 17,
`1994 (now abandoned in favor of FWC application 08/614,
`521, filed Mar. 15, 1996, now USS. Pat. No. 5,745,604); and
`Ser. No. 08/154,866, filed Nov. 18, 1993 (now abandoned),
`which applications and patents are incorporated herein by
`reference. Priority under 35 USC Section 120 is claimed to
`each of these prior applications.
`
`TECHNICAL FIELD
`
`The present invention relates to wireless communication
`systems, such as cellular systems and PCS systems, and
`more particularly relates to methods and systems for reduc-
`ing theft of wireless telephony services by use of stegano-
`graphically encoded authentication data.
`
`BACKGROUND AND SUMMARYOF THE
`INVENTION
`
`this disclosure generally
`(For expository convenience,
`refers to cellular telephony systems. However, it should be
`recognized that the invention is not so limited, but can be
`used with any wireless communications device, whether for
`voice or data; analog or digital.)
`In the cellular telephone industry, hundreds of millions of
`dollars of revenue is lost each year through theft of services.
`While someservicesare lost due to physical theft of cellular
`telephones, the more pernicious threat is posed by cellular
`telephone hackers.
`Cellular telephone hackers employ various electronic
`devices to mimic the identification signals produced by an
`authorized cellular telephone. (These signals are sometimes
`called authorization signals, verification numbers, signature
`data, etc.) Often,
`the hacker learns of these signals by
`eavesdropping on authorized cellular telephone subscribers
`and recording the data exchanged with the cell cite. By artful
`use of this data, the hacker can impersonate an authorized
`subscriber and dupe the carrier into completing pirate calls.
`In the prior art, identification signals are segregated from
`the voice signals. Most commonly,
`they are temporally
`separated, e.g.
`transmitted in a burst at
`the time of call
`origination. Voice data passes through the channel only after
`a verification operation has taken place on this identification
`data. (Identification data is also commonly included in data
`packets sent during the transmission.) Another approach is
`to spectrally separate the identification, e.g. in a spectral
`subband outside that allocated to the voice data.
`
`Other fraud-deterrent schemes have also been employed.
`Oneclass of techniques monitors characteristics of a cellular
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`telephone’s RF signal to identify the originating phone.
`Another class of techniques uses handshaking protocols,
`wherein someof the data returned by the cellular telephone
`is based on an algorithm (e.g. hashing) applied to random
`data sent thereto.
`
`Combinations of the foregoing approachesare also some-
`times employed.
`U.S. Pat. Nos. 5,465,387, 5,454,027, 5,420,910, 5,448,
`760, 5,335,278, 5,345,595, 5,144,649, 5,204,902, 5,153,919
`and 5,388,212 detail various cellular telephone systems, and
`fraud deterrence techniques used therein. The disclosures of
`these patents are incorporated by reference.
`As the sophistication of fraud deterrence systems
`increases, so does the sophistication of cellular telephone
`hackers. Ultimately, hackers have the upper hand since they
`recognize that all prior art systems are vulnerable to the
`same weakness:the identification is based on someattribute
`of the cellular telephone transmission outside the voice data.
`Since this attribute is segregated from the voice data, such
`systemswill always be susceptible to pirates who electroni-
`cally “patch” their voice into a composite electronic signal
`having the attribute(s) necessary to defeat the fraud deter-
`rence system.
`To overcome this failing, the preferred embodiments of
`the present invention steganographically encodes the voice
`signal with identification data, resulting in “in-band” sig-
`naling (in-band both temporally and spectrally). This
`approach allows the carrier to monitor the user’s voice
`signal and decode the identification data therefrom.
`In one form of the invention, someorall of the identifi-
`cation data used in the priorart (e.g. data transmitted at call
`origination) is repeatedly steganographically encoded in the
`user’s voice signal as well. The carrier can thus periodically
`or aperiodically check the identification data accompanying
`the voice data with that sent at call origination to ensure they
`match. If they do not, the call is identified as being hacked
`and steps for remediation can be instigated such as inter-
`rupting the call.
`In another form of the invention, a randomly selected one
`of several possible messages is repeatedly steganographi-
`cally encoded on the subscriber’s voice. An index sent to the
`cellular carrier at call set-up identifies which message to
`expect. If the message steganographically decoded by the
`cellular carrier from the subscriber’s voice does not match
`that expected, the call is identified as fraudulent.
`In the preferred form of the invention, the steganographic
`encoding relies on a pseudo random data signal to transform
`the message or identification data into a low level noise-like
`signal superimposed on the subscriber’s digitized voice
`signal. This pseudo random data signal
`is known, or
`knowable, to both the subscriber’s telephone (for encoding)
`and to the cellular carrier
`(for decoding). Many such
`embodimentsrely on a deterministic pseudo random number
`generator seeded with a datum knownto both the telephone
`and the carrier. In simple embodiments this seed can remain
`constant from one call to the next (e.g. a telephone ID
`number). In more complex embodiments, a pseudo-one-time
`pad system may be used, wherein a new seedis used for each
`session (i.e. telephone call). In a hybrid system, the tele-
`phone and cellular carrier each have a reference noise key
`(e.g. 10,000 bits) from which the telephoneselects a field of
`bits, such as 50 bits beginning at a randomly selected offset,
`and each usesthis excerpt as the seed to generate the pseudo
`random data for encoding. Data sent from the telephone to
`the carrier (e.g.
`the offset) during call set-up allows the
`carrier to reconstruct the same pseudo random data for use
`
`

`

`6,064,737
`
`3
`in decoding. Yet further improvements can be derived by
`borrowing basic techniques from the art of cryptographic
`communications and applying them to the steganographi-
`cally encoded signal detailed in this disclosure.
`Details of applicant’s preferred techniques for stegano-
`graphic encoding/decoding with a pseudo random data
`stream are more particularly detailed in applicant’s prior
`applications, but the present invention is not limited to use
`with such techniques. A brief review of other steganographic
`techniques suitable for use with the present invention fol-
`lows.
`
`British patent publication 2,196,167 to Thorn EMIdis-
`closes a system in which an audio recordingis electronically
`mixed with a marking signal indicative of the owner of the
`recording, where the combinationis perceptually identical to
`the original. U.S. Pat. Nos. 4,963,998 and 5,079,648 dis-
`close variants of this system.
`U.S. Pat. No. 5,319,735 to B.B.N. rests on the same
`principles as the earlier Thorn EMI publication, but addi-
`tionally addresses psycho-acoustic masking issues.
`U.S. Pat. Nos. 4,425,642, 4,425,661, 5,404,377 and
`5,473,631 to Moses disclose various systems for impercep-
`tibly embedding data into audio signals—the latter two
`patents particularly focusing on neural network implemen-
`tations and perceptual coding details.
`US. Pat. No. 4,943,973 to AT&T discloses a system
`employing spread spectrum techniques for adding a low
`level noise signal to other data to convey auxiliary data
`therewith. The patent is particularly illustrated in the context
`of transmitting network control signals along with digitized
`voice signals.
`US. Pat. No. 5,161,210 to U.S. Philips discloses a system
`in which additional low-level quantization levels are defined
`on an audio signal to convey, e.g., a copy inhibit code,
`therewith.
`
`US. Pat. No. 4,972,471 to Gross discloses a system
`intendedto assist in the automated monitoring of audio (e.g.
`radio) signals for copyrighted materials by reference to
`identification signals subliminally embedded therein.
`There are a variety of shareware programs available on
`the internet (e.g. “Stego” and “White Noise Storm”) which
`generally operate by swapping bits from a to-be-concealed
`message stream into the least significant bits of an image or
`audio signal. White Noise Storm effects a randomization of
`the data to enhance its concealment.
`
`A British company, Highwater FBI, Ltd., has introduced
`a software product which is said to imperceptibly embed
`identifying information into photographs and other graphi-
`cal
`images. This technology is the subject of European
`patent applications 9400971.9 (filed Jan. 19, 1994),
`9504221.2 (filed Mar. 2, 1995), and 9513790.7 (filed Jul. 3,
`1995), the first of which has been laid open as PCT publi-
`cation WO 95/20291.
`
`Walter Bender at M.I.T. has done a variety of work in the
`field, as illustrate by his paper “Techniques for Data
`Hiding,” Massachusetts Institute of Technology, Media
`Laboratory, January 1995.
`Dice, Inc. of Palo Alto has developed an audio marking
`technology marketed under the name Argent. While a U.S.
`Patent Application is understood to be pending,it has not yet
`been issued.
`
`Tirkel et al, at Monash University, have published a
`variety of papers on “electronic watermarking” including,
`e.g., “Electronic Water Mark,” DICTA-93, Macquarie
`University, Sydney, Australia, December, 1993,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`pp.666-673, and “A Digital Watermark,” IEEE International
`Conference on Image Processing, Nov. 13-16, 1994, pp.
`86-90.
`
`Cox et al, of the NEC Technical Research Institute,
`discuss various data embedding techniques in their pub-
`lished NEC technical report entitled “Secure Spread Spec-
`trum Watermarking for Multimedia,’ December, 1995.
`Moller et al. discuss an experimental system for imper-
`ceptibly embedding auxiliary data on an ISDN circuit in
`“Rechnergestutzte Steganographie: Wie sie Funktioniert und
`warum folglich jede Reglementierung von Verschlusselung
`unsinnig ist,” DuD, Datenschutz und Datensicherung, 18/6
`(1994) 318-326. The system randomly picks ISDN signal
`samples to modify, and suspends the auxiliary data trans-
`mission for signal samples which fall below a threshold.
`In addition to the foregoing, many of the other cited prior
`art patents and publications disclose systems for embedding
`a data signal on an audio signal. These, too, can generally be
`employed in systems according to the present invention.
`The foregoing and additional features and advantages of
`the present invention will be more readily apparent from the
`following detailed description, which proceeds with refer-
`ence to the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram showing principal components
`of an exemplary wireless telephony system.
`FIG. 2 is a block diagram of an exemplary steganographic
`encoder that can be used in the telephone of the FIG. 1
`system.
`FIG. 3 is a block diagram of an exemplary steganographic
`decoderthat can be used in the cell site of the FIG. 1 system.
`FIGS. 4A and 4B are histogramsillustrating signal rela-
`tionships which may be exploited to facilitate decoding.
`
`DETAILED DESCRIPTION
`
`The reader is presumed to be familiar with cellular
`communications technologies. Accordingly, details known
`from prior art in this field aren’t belabored herein.
`Referring to FIG. 1, an illustrative cellular system
`includes a telephone 10,a cell site 12, and a centraloffice 14.
`Conceptually, the telephone may be viewed as including
`a microphone 16, an A/D converter 18, a data formatter 20,
`a modulator 22, an RF section 24, an antenna 26, a demodu-
`lator 28, a data unformatter 30, a D/A converter 32, and a
`speaker 34.
`In operation, a subscriber’s voice is picked up by the
`microphone 16 and converted to digital form by the A/D
`converter 18. The data formatter 20 puts the digitized voice
`into packet form, adding synchronization and control bits
`thereto. The modulator 22 converts this digital data stream
`into an analog signal whose phase and/or amplitude prop-
`erties change in accordance with the data being modulated.
`The RF section 24 commonly translates this time-varying
`signal to one or more intermediate frequencies, and finally
`to a UHFtransmission frequency. The RFsection thereafter
`amplifies it and provides the resulting signal to the antenna
`26 for broadcast to the cell site 12.
`
`The process works in reverse when receiving. A broadcast
`from the cell cite is received through the antenna 26. RF
`section 24 amplifies and translates the received signal to a
`different frequency for demodulation. Demodulator 28 pro-
`cesses the amplitude and/or phase variations of the signal
`provided by the RF section to produce a digital data stream
`
`

`

`6,064,737
`
`5
`corresponding thereto. The data unformatter 30 segregates
`the voice data from the associated synchronization/control
`data, and passes the voice data to the D/A converter for
`conversion into analog form. The output from the D/A
`converter drives the speaker 34, through which the sub-
`scriber hears the other party’s voice.
`The cell site 12 receives broadcasts from a plurality of
`telephones 10, and relays the data received to the central
`office 14. Likewise, the cell site 12 receives outgoing data
`from the central office and broadcasts same to the tele-
`phones.
`The central office 14 performs a variety of operations,
`including call authentication, switching, and cell hand-off.
`(in some systems, the functional division betweenthe cell
`site and the central station is different than that outlined
`above. Indeed, in some systems, all of this functionality is
`provided at a single site.)
`In an exemplary embodiment of the present invention,
`each telephone 10 additionally includes a steganographic
`encoder 36. Likewise, each cell site 12 includes a stegano-
`graphic decoder 38. The encoder operates to hide an auxil-
`iary data signal amongthe signals representing the subscrib-
`er’s voice. The decoder performs the reciprocal function,
`discerning the auxiliary data signal from the encoded voice
`signal. The auxiliary signal servesto verify the legitimacy of
`the call.
`
`An exemplary steganographic encoder 36 is shown in
`FIG. 2.
`
`The illustrated encoder 36 operates on digitized voice
`data, auxiliary data, and pseudo-random noise (PRN)data.
`The digitized voice data is applied at a port 40 and is
`provided, e.g., from A/D converter 18. The digitized voice
`may comprise 8-bit samples. The auxiliary data is applied at
`a port 42 and comprises, in one form of the invention, a
`stream of binary data uniquely identifying the telephone 10.
`(The auxiliary data may additionally include administrative
`data of the sort conventionally exchanged with a cell site at
`call set-up.) The pseudo-random noise data is applied at a
`port 44 and can be, e.g., a signal that randomly alternates
`between “-1” and “1” values. (More and more cellular
`phonesare incorporating spread spectrum capable circuitry,
`and this pseudo-random noise signal and other aspects of
`this invention can often “piggy-back” or share the circuitry
`which is already being applied in the basic operation of a
`cellular unit).
`For expository convenience, it is assumed that all three
`data signals applied to the encoder 36 are clocked at a
`common rate, although this is not necessary in practice.
`In operation, the auxiliary data and PRN data streamsare
`applied to the two inputs of a logic circuit 46. The output of
`circuit 46 switches between -1 and +1 in accordance with
`the following table:
`
`AUX
`
`0
`0
`1
`1
`
`PRN
`
`-1
`1
`-1
`1
`
`OUTPUT
`
`1
`-1
`-1
`1
`
`(If the auxiliary data signal is conceptualized as switching
`between -—1 and 1, instead of O and 1, it will be seen that
`circuit 46 operates as a one-bit multiplier.)
`The output from gate 46 is thus a bipolar data stream
`whose instantaneous value changes randomly in accordance
`
`6
`with the corresponding values of the auxiliary data and the
`PRNdata. It may be regarded as noise. However,it has the
`auxiliary data encoded therein. The auxiliary data can be
`extracted if the corresponding PRN data is known.
`The noise-like signal from gate 46 is applied to the input
`of a scaler circuit 48. Scaler circuit scales (e.g. multiplies)
`this input signal by a factor set by a gain control circuit 50.
`In the illustrated embodiment, this factor can range between
`0 and 15. The output from scaler circuit 48 can thus be
`represented as a five-bit data word (fourbits, plus a sign bit)
`which changes each clock cycle,
`in accordance with the
`auxiliary and PRN data, and the scale factor. The output
`from the scaler circuit may be regarded as “scaled noise
`data” (but again it is “noise” from which the auxiliary data
`can be recovered, given the PRN data).
`The scaled noise data is summedwith the digitized voice
`data by a summer51 to provide the encoded output signal
`(e.g. binarily added on a sample by sample basis). This
`output signal is a composite signal representing both the
`digitized voice data and the auxiliary data.
`The gain control circuit 50 controls the magnitude of the
`added scaled noise data so its addition to the digitized voice
`data does not noticeably degrade the voice data when
`converted to analog form and heard by a subscriber. The gain
`control circuit can operate in a variety of ways.
`Oneis a logarithmic scaling function. Thus, for example,
`voice data samples having decimal values of 0, 1 or 2 may
`be correspondto scale factors of unity, or even zero, whereas
`voice data samples having values in excess of 200 may
`correspond to scale factors of 15. Generally speaking, the
`scale factors and the voice data values correspond by a
`square root relation. That is, a four-fold increase in a value
`of the voice data corresponds to approximately a two-fold
`increase in a value of the scaling factor associated therewith.
`Another scaling function would be linear as derived from the
`average power of the voice signal.
`(The parenthetical reference to zero as a scaling factor
`alludes to cases, e.g., in which the digitized voice signal
`sample is essentially devoid of information content.)
`More satisfactory than basing the instantaneous scaling
`factor on a single voice data sample, is to base the scaling
`factor on the dynamics of several samples. That is, a stream
`of digitized voice data which is changing rapidly can cam-
`ouflage relatively more auxiliary data than a stream of
`digitized voice data which is changing slowly. Accordingly,
`the gain control circuit 50 can be made responsive to the
`first, or preferably the second- or higher-order derivative of
`the voice data in setting the scaling factor.
`In still other embodiments, the gain control block 50 and
`scaler 48 can be omitted entirely.
`(Those skilled in the art will recognize the potential for
`“rail errors” in the foregoing systems. For example, if the
`digitized voice data consists of 8-bit samples, and the
`samples span the entire range from 0 to 255 (decimal), then
`the addition or subtraction of scaled noise to/from the input
`signal may produceoutputsignals that cannot be represented
`by 8 bits (e.g.—2, or 257). A number of well-understood
`techniques exist
`to rectify this situation, some of them
`proactive and some of them reactive. Among these known
`techniquesare: specifying that the digitized voice data shall
`not have samples in the range of 0-4 or 241-255, thereby
`safely permitting combination with the scaled noise signal;
`and including provision for detecting and adaptively modi-
`fying digitized voice samples that would otherwise cause
`rail errors.)
`Returning to the telephone 10, an encoder 36 like that
`detailed above is desirably interposed between the A/D
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`6,064,737
`
`7
`converter 18 and the data formatter 20, thereby serving to
`steganographically encode all voice transmissions with the
`auxiliary data. Moreover, the circuitry or software control-
`ling operation of the telephone is arranged so that
`the
`auxiliary data is encoded repeatedly. That is, whenall bits of
`the auxiliary data have been encoded, a pointer loops back
`and causesthe auxiliary data to be applied to the encoder 36
`anew. (The auxiliary data may be stored at a known address
`in RAM memoryfor ease of reference.)
`It will be recognized that the auxiliary data in the illus-
`trated embodimentis transmitted at a rate one-eighth that of
`the voice data. That is, for every 8-bit sample of voice data,
`scaled noise data corresponding to a single bit of the
`auxiliary data is sent. Thus, if voice samplesare sentat a rate
`of 4800 samples/second, auxiliary data can be sentat a rate
`of 4800 bits/second. If the auxiliary data is comprised of
`8-bit symbols, auxiliary data can be conveyed at a rate of
`600 symbols/second. If the auxiliary data consists of a string
`of even 60 symbols, each second of voice conveys the
`auxiliary data ten times. (Significantly higher auxiliary data
`rates can be achieved by resorting to more efficient coding
`techniques, such as limited-symbol codes (e.g. 5- or 6-bit
`codes), Huffman coding, etc.) This highly redundant trans-
`mission of the auxiliary data permits lower amplitude scaled
`noise data to be used while still providing sufficient signal-
`to-noise headroom to assure reliable decoding—evenin the
`relatively noisy environmentassociated with radio transmis-
`sions.
`Turning now to FIG. 3, each cell site 12 has a stegano-
`graphic decoder 38 by which it can analyze the composite
`data signal broadcast by the telephone 10 to discern and
`separate the auxiliary data and digitized voice data there-
`from. (The decoder desirably works on unformatted data
`(i.e. data with the packet overhead, control and administra-
`tive bits removed;
`this is not shown for clarity of
`illustration).
`The decoding of an unknown embeddedsignal(i.e. the
`encoded auxiliary signal) from an unknownvoice signal is
`best done by some form ofstatistical analysis of the com-
`posite data signal.
`In one approach, decoding relies on recombining the
`composite data signal with PRN data (identical to that used
`during encoding), and analyzing the entropy of the resulting
`signal. “Entropy” need not be understood in its most strict
`mathematical definition, it being merely the most concise
`word to describe randomness (noise, smoothness,
`snowiness,etc.).
`Most serial data signals are not random. That is, one
`sample usually correlates—to some degree—with adjacent
`samples. This is true in sampled voice signals.
`Noise, in contrast, typically is random. If a random signal
`(e.g. noise) is added to (or subtracted from) a non-random
`signal (e.g. voice), the entropy of the resulting signal gen-
`erally increases. That
`is,
`the resulting signal has more
`random variations than the original signal. This is the case
`with the composite data signal produced by encoder 36; it
`has more entropy than the original, digitized voice data.
`If, in contrast,
`the addition of a random signal to (or
`subtraction from) a non-random (e.g. voice) signal reduces
`entropy,
`then something unusual is happening. It is this
`anomaly that can be used to decode the composite data
`signal.
`To fully understand this entropy-based decoding method,
`it is first helpful to highlight a characteristic of the original
`encoding process: the similar treatment of every Nth (e.g.
`480th) sample.
`In the encoding process discussed above, the auxiliary
`data is 480 bits long. Since it is encoded repeatedly, every
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`480th sample of the composite data signal correspondsto the
`samebit of the auxiliary data. If this bit is a “1”, the scaled
`PRNdata corresponding thereto are added to the digitized
`voice signal;
`if this bit
`is a “0”,
`the scaled PRN data
`corresponding thereto are subtracted. Due to the repeated
`encoding of the auxiliary data, every 480th sample of the
`composite data signal thus shares a characteristic: they are
`all either augmented by the corresponding noise data (which
`may be negative), or they are all diminished, depending on
`whether the bit of the auxiliary data is a “1” or a “O”.
`To exploit this characteristic, the entropy-based decoding
`processtreats every 480th sample of the composite signal in
`like fashion. In particular, the process begins by adding to
`the 1st, 481st, 861st, etc. samples of the composite data
`signal
`the PRN data with which these samples were
`encoded. (That is, a set of sparse PRN data is added: the
`original PRNset, with all but every 480th datum zeroed out.)
`The localized entropy of the resulting signal around these
`points G.e.
`the composite data signal with every 480th
`sample modified) is then computed.
`(Computation of a signal’s entropy or randomnessis well
`understood by artisansin this field. One generally accepted
`technique is to take the derivative of the signal at each
`sample point near a point in question (e.g.
`the modified
`sample and 4 samples either side), square these values, and
`then sum the resulting signals over all of the localized
`regions overthe entire signal. A variety of other well known
`techniques can alternatively be used.)
`The foregoing step is then repeated, this time subtracting
`the PRN data corresponding thereto from the 1st, 481st,
`961st, etc. composite data samples.
`One of these two operations will counteract (e.g. undo)
`the encoding process and reduce the resulting signal’s
`entropy; the other will aggravateit. If adding the sparse PRN
`data to the composite data reducesits entropy, then this data
`must earlier have been subtracted from the original voice
`signal. This indicates that
`the corresponding bit of the
`auxiliary data signal was a “O” when these samples were
`encoded. (A “0”at the auxiliary data inputof logic circuit 46
`caused it to produce an inverted version of the correspond-
`ing PRN datum asits output datum, resulting in subtraction
`of the corresponding PRN datum from the voice signal.)
`Conversely, if subtracting the sparse PRN data from the
`composite data reduces its entropy, then the encoding pro-
`cess must have earlier added this noise. This indicates that
`the value of the auxiliary data bit was a “1” when samples
`1, 481, 961, etc., were encoded.
`By noting in which case entropy is lower by (a) adding or
`(b) subtracting a sparse set of PRN data to/from the com-
`posite data, it can be determined whetherthe first bit of the
`auxiliary data is (a) a “O”, or (b) a “1.” (In real
`life
`applications,
`in the presence of various distorting
`phenomena, the composite signal may be sufficiently cor-
`rupted so that neither adding nor subtracting the sparse PRN
`data actually reduces entropy. Instead, both operations will
`increase entropy.In this case, the “correct” operation can be
`discerned by observing which operation increases the
`entropy less.)
`The foregoing operations can then be conducted for the
`group of spaced samples of the composite data beginning
`with the second sample (i.e. 2, 482, 962, .. . ). The entropy
`of the resulting signals indicate whether the secondbit of the
`auxiliary data signal is a “O” or a “1.” Likewise with the
`following 478 groups of spaced samples in the composite
`signal, until all 480 bits of the code word have been
`discerned.
`It will be appreciated that the foregoing approach is not
`sensitive to corruption mechanismsthat alter the values of
`
`

`

`6,064,737
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Security Considerations
`Security of the present invention depends, in large part, on
`security of the PRN data and/or security of the auxiliary
`data. In the following discussion, a few of many possible
`techniques for assuring the security of these data are dis-
`cussed.
`
`10
`productoperations. If the dot productis positive, the corre-
`sponding bit of the auxiliary data signal is a “1;” if the dot
`product is negative, the corresponding bit of the auxiliary
`data signal is a “0.” If several alignments of the auxiliary
`data signal within the framed composite signal are possible,
`this procedure is repeated at each candidate alignment, and
`the one yielding the highest correlation is taken as true.
`(Oncethe correct alignment is determined for a single bit of
`the auxiliary data signal, the alignmentofall the other bits
`can be determined therefrom. “Alignment,” perhaps better
`knownas “synchronization,” can be achieved by primarily
`through the very same mechanisms whichlock on and track
`the voice signal itself and allow for the basic functioning of
`the cellular unit).
`One principle which did not seem to be explicitly present
`in the Kassam book and which was developed rudimentarily
`by the inventor involves the exploitation of the magnitudes
`of the statistical properties of the auxiliary data signal being
`sought relative to the magnitude of the statistical properties
`of the composite signal as a whole.
`In particular,
`the
`problematic case seems to be where the auxiliary data
`signals we are looking for are of much lowerlevel than the
`noise and corruption present on a difference signal between
`the composite and digitized voice signals. FIG. 4 attempts to
`set the stage for the reasoning behind this approach. FIG. 4