Multiple access coding for radio communication

The present invention relates to the use of Code Division Multiple Access (CDMA) communication methods in radiotelephone communications systems, and more particularly to an improved CDMA encoding scheme involving encryption sequences for distinguishing and protecting information signals in a broad-spectrum environment.

BACKGROUND

The cellular telephone industry has made great efforts in commercial activities in the United States and the rest of the world. Growth in major cities has far exceeded expectations and exceeds system capacity. If this trend continues, the effects of rapid growth will soon reach even the smallest markets. Innovative solutions are required to meet these increasing capacity requirements, as well as to ensure high quality of service and prevention of price increases.

Throughout the world, it is an important step in cellular systems to switch from analog to digital transmission. Equally important is the choice of an effective digital transmission scheme for implementing the next generation of cellular technology. It is also widely believed that the first generation of personal communication networks (PCNs), using pocket-size, cheap, cordless telephones that can be conveniently carried and used to make calls from home, office, on the street, in the car, etc., by which cellular providers are provided using the next generation of digital cellular system infrastructure and cellular frequencies. The key feature required for these new systems is increased traffic capacity.

Currently, channel access is performed using Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) techniques. In FDMA, as illustrated in Fig. 1 (a), a communication channel is a single radio frequency band to which signal transmission power is concentrated. An interference with adjacent channels is limited by the use of bandpass filters which pass only pass signal energy within the frequency bands of the spezifierten filter. Thus, since each channel is assigned a different frequency, system capacity is limited by the frequencies available, as well as by restrictions imposed by channel reuse.

In the TDMA system, as shown in Fig. 1 (b), a channel consists of a time slot in a periodic series of time intervals over the same frequency. Each period of time slots is called a frame. The energy of a given signal is assigned to one of these time slots. Adjacent channel interference is limited by the use of a time interval (Tor) or other synchronization element that passes only signal energy received at an appropriate time.

Thus, the problem of interference from different relative signal strength levels is reduced.

A capacity in TDMA systems is increased by compressing the transmission signal to a shorter time slot. As a consequence, the information must be transmitted at a correspondingly faster burst rate, which proportionally increases the proportion of the occupied spectrum. The occupied frequency bandwidths are thus larger in FIG. 1 (b) than in FIG. 1 (a).

In FDMA or TDMA systems or hybrid FDMA / TDMA systems, the goal is to ensure that two potentially interfering signals do not occupy the same frequency at the same time. In contrast, Code Division Multiple Access (CDMA) allows signals to overlap in both time and frequency, as shown in Figure 1 (c). Thus, all CDMA signals share the same frequency spectrum. Multiple access signals overlap both in the frequency domain and in the time domain. Various aspects of CDMA communication are described in "On the Capacity of a Cellular CDMA System", Gillhousen, Jacobs, Viterbi, Weaver and Wheatley, IEEE Trans. On Vehicular Technology, May 1991.

WO92 / 00639 describes a system and method for communicating information signals using spread spectrum communication techniques and PN sequences that provide orthogonality between users. Different PN sequences are assigned to different voice channel signals for different mobile stations. Signals are communicated between a cell station and mobile units using direct sequence spread spectrum communication signals.

Information transmitted on a cell-to-mobile station link is generally encoded, interleaved, bi-phase shift key modulated (BPSK) with orthogonal occupancy of each BPSK symbol, along with phase quadrature shift keys (FIG. QPSK) (quadrature phase shift key) -Spreading of the occupied symbols. Information transmitted on the mobile station cell link is generally encoded, interleaved, transmitted orthogonally, along with QPSK spreading.

EP-A-336832 describes a demodulator for modulating (in quadrature) a complex signal formed by two carriers, the spectrum being spread by a pseudonoise signal and modulated by an M-ary, Walsh, code. The demodulator includes a chain of registers for storing 256 bits of a pseudo-random signal, a multiplexer for temporarily multiplexing the processing of the two carriers, a chain of correlation macrocells having a systolic structure allowing temporal multiplexing, and having interposed outputs Provide partial correlation values ​​on 16 chips, a device for the calculation of linear combinations of the functions of the partial correlation, to calculate two functions of the correlation corresponding to the two carriers for each M-ary code, a demultiplexing and calculating device to calculate the modulus of the function of the correlation for each of the Walsh codes that can modulate the signal to be modulated, and a device to select the largest value of the correlation function and to select the corresponding piece of data.

In a typical CDMA system, the informational data stream to be transmitted is imposed on a much higher bit rate data stream generated by a pseudo-random code generator. The informational data stream and the high bit rate data stream are typically multiplied together. This combination of a higher bit rate signal with the lower bit rate data stream is called encoding or spreading of the informational data stream signal. Each informational data stream or channel is assigned a unique spreading code. A plurality of coded information signals are transmitted on radio frequency carrier waves and received collectively as a composite signal at a receiver. Each of the encoded signals overlaps all other encoded signals, as well as noise related signals, in both frequency and time. By correlating the composite signal with one of the unique spreading codes, the corresponding information signal is isolated and decoded.

There are a number of advantages associated with CDMA communication techniques. The capacity limits of a CDMA based cellular system are said to be up to twenty times the existing analog technology as a consequence of the broadband CDMA system characteristics such as improved coding gain / modulation density, voice activity switching, sectorization, and reuse of the same Spectrum in each cell. A CDMA system is virtually immune to multipath interference and eliminates fading and static effects to increase performance in urban areas. Speech CDMA transmission with a high-guess encoder provides superior and realistic voice quality. CDMA also provides variable data councils, which allows to offer many different language quality grades. The encrypted signal format of CDMA completely eliminates crosstalk and makes it very difficult and costly to track or listen to calls, ensuring greater user privacy and greater user fraud immunity.

Despite the many advantages offered by CDMA systems, the capacity of conventional CDMA systems is limited by the decoding process. Since so many different user communications overlap in time and frequency, the task of correlating the right information signal with the appropriate user is complex. In practical implementations of CDMA communications, capacitance is limited by a signal to noise ratio, which is essentially a measure of the interference caused by other overlapping signals, as well as background noise. The general problem to be solved is therefore to increase system capacity while still maintaining system integrity and useful signal-to-noise ratio. A particular aspect of this problem is to optimize the process of separating each coded information signal from all other information signals and noise related interference.

Another aspect to be addressed in CDMA systems is system security and personal user privacy. Since all of the coded subscriber signals overlap, the CDMA decoding techniques typically require that the particular codes used to distinguish each information signal be well known. This public awareness of the actual codes used in a particular cell invites you to listen.

SUMMARY

Coding of individual information signals is simplified by encoding each signal with a common block error correction code that can be immediately decoded using a correlator such as a Fast Walsh Transform circuit. According to claims 1, 36, 43, 59 and 65, each coded information signal is assigned a unique encryption mask, or signature sequence, of a set of encryption masks having certain selected auto and cross correlation properties. These encryption masks are ordered based on the signal strength of their respective associated coded information signals. To improve the decoding process, the highest ranked encryption masks are initially selected in a sequence to decrypt the received composite signal. Generally speaking, the encryption mask is selected such that the sum of any two encryption masks using modulo-2 arithmetic is equal in magnitude to all code words of the common block error correction code. In the event that the block error correction code is a Walsh-Hadamard code, if any two encryption masks are summed using modulo-2 arithmetic, and the binary values ​​of the product are represented as + 1 and -1 values, then Walsh transform this sum a maximum flat Walsh spectrum. Sequences with such a spectrum are sometimes referred to as "bent" sequences.

In the field of cellular radiotelephone systems using subtractive CDMA modulation techniques, the present invention includes a two-stage encryption system to ensure cellular-level security and privacy of the individual mobile user level. At the system level, a pseudo-randomized code key is used to select one of the encryption masks common to all mobile stations in a particular cell. At the subscriber level, a pseudo-randomized encoding key encodes individual information signals prior to the encryption operation.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will now be described in more detail with reference to preferred embodiments of the invention, given by way of example only and illustrated in the accompanying drawings:

Figs. 2 (a) - (c) show representations of access channels using different multiple access methods;

Fig. 2 illustrates, in a series of diagrams, the generation of CDMA signals;

Figures 3 and 4 show a series of diagrams to illustrate how CDMA signals are decoded;

Fig. 5 illustrates in a series of diagrams a subtractive CDMA demodulation method;

Fig. 6 shows a generalized scheme of a spread spectrum communication system;

Fig. 7 is a functional block diagram of a system that may be used to implement one of the preferred embodiments of the invention;

Fig. 8 is a block diagram of another receiver in accordance with the present invention;

and

Fig. 9 shows a functional block diagram of a system that may be used to implement another of the preferred embodiments of the present invention.

DETAILED DESCRIPTION

While the following description will be in the field of cellular communication systems involving portable or mobile radiotelephones and / or personal communication networks (PCNs), it will be apparent to those skilled in the art that the present invention may be applied to other communication applications. In addition, while the present invention may be used in a subtractive CDMA demodulation system, it may also be used in applications of other types of spread spectrum communication systems.

CDMA demodulation techniques will now be described with reference to the signal representations of Figs. 2-4 which show exemplary waveforms in the encoding and decoding process used in traditional CDMA systems. Using the waveform examples of Figs. 2-4, the improved performance of a subtractive CDMA demodulation method is illustrated in Fig. 5. Additional descriptions of known and subtractive CDMA demodulation techniques can be found in commonly assigned US Pat. No. 5,151,919 and US Pat. No. 5,218,619.

Two different data streams, shown as signal representations (a) and (d) in Fig. 2, represent digitized information to be communicated over two separate communication channels. Information signal 1 is modulated using a high bit-rate digital code unique to the signal 1 and shown in signal representation (b). For purposes of this description, "bit" denotes a binary symbol or symbol of the information signal. The term "bit period" refers to the period of time between the beginning and the end of a bit of the information signal. The term "chip" refers to a binary number of the high-order code signal. Thus, the term "chip period" refers to the time period between the beginning and the end of a chip of the code signal. Of course, the bit period is much larger than the chip period. The result of this modulation, which is essentially the product of the two signal waveforms, is shown in the signal representation (c). In Boolean notation, the modulation of the two waveforms is essentially an exclusive-OR operation. A similar series of operations is performed on the information signal 2 as shown in signal representations (d) - (f). In practice, of course, much more than two coded information signals can be spread over the frequency spectrum available for cellular telephone communication.

Each coded signal is used to modulate a radio frequency (RF) carrier using a number of modulation techniques, such as Binary Phase Shift Keying (BPSK) or Quadrature Phase Shif Keying (QPSK). In a cellular telephone system, each modulated carrier is transmitted over a radio interface. At a radio receiver, such as a cellular base station, all signals that overlap in the allocated frequency bandwidth are received together. The individually coded signals are added as shown in the signal representations (a) - (c) of Fig. 3 to form a composite signal waveform (graph (c)).

After a demodulation of the received signal to the appropriate baseband frequency, the decoding of the composite signal takes place. The information signal 1 may be decoded or despread by multiplying the received composite signal shown in FIG. 3 (c) by the unique code used to initially encode the modulated signal 1 shown in signal graph (d) modulate. The resulting signal is analyzed to determine the polarity (high or low, +1 or -1, "1" or "0") of each information bit period of the signal. The details of how the code generator of the receiver is time synchronized with the transmitted code are well known in the art.

These decisions may be made by taking an average or majority vote of the chip polarities during each bit period. Processes that make such a "hard" decision are acceptable as long as there is no signal ambiguity. For example, during the first bit period in signal representation (f), the average chip value is +1.00, which immediately indicates a bit polarity +1. Similarly, during the third bit period, the average chip value is +0.75, and the bit polarity is also most likely +1. However, in the second bit period, the average chip value is 0, and the majority vote or average test fails to provide an acceptable polarity value.

In such ambiguous situations, a "soft" decision making process must be used to determine the bit polarity. For example, after despreading, an analog voltage proportional to the received signal may be integrated over the number of chip periods corresponding to a single bit of information. The sign or polarity of the net integration result then indicates the bit value as a +1 or -1.

The decoding of signal 2, similar to that of signal 1, is shown in the signal representations (a) - (d) of FIG. After decoding, however, there are no ambiguous bit polarity situations.

Theoretically, this decoding scheme can be used to decode any signal that forms a composite signal. Ideally, the contribution of unwanted, interfering signals is minimized when the digital spreading codes are orthogonal to the unwanted signals. (Two binary sequences are orthogonal if they differ exactly by one-half their bit positions.) However, impractically, only a certain number of orthogonal codes exist for a given word length. Another problem is that orthogonality can only be maintained if the relative time alignment between two signals is strictly maintained. In communications environments where portable radio units are constantly moving, such as in cellular systems, precise timing is difficult to achieve. If the code orthogonality can not be guaranteed, noise-based signals may be mixed with those generated by different code generators, e.g. B. Mobile phones, interfere with actual bit sequences generated. In comparison with the originally coded signal energies, however, the energy of the noise signals is normally small.

A "processing gain" is a parameter of spread spectrum systems, and for a direct spreading system it is defined as the ratio of the spreading or coding bit rate to the underlying information bit rate, ie the number of chips per information bit or symbol. Thus, the processing gain is substantially the bandwidth spreading ratio, that is, the ratio of the bandwidths of the spreading code and the information signal. The higher the code bit rates, the wider the spread of information and the greater the spreading ratio. For example, one kilobit per second information rate used to modulate one megabit per second code signal has a processing gain of 1000: 1. The processing gain shown in Fig. 2 is, for example, 8: 1, the ratio of the code chip rate to the information data stream bit rate.

Great processing gains reduce the likelihood of decoding noise signals modulated using uncorrelated codes. For example, a processing gain in military areas is used to measure the suppression of hostile spurious signals. In other environments, such as cellular systems, a processing gain helps suppress other "friendly" signals that reside in the same communication channel but use codes that are uncorrelated with the desired code. In the field of a subtractive CDMA demodulation method, "noise" includes both "hostile" and "friendly" signals and may be defined as any signals other than the signal of interest, ie, the signal to be decoded. If the above example is extended, if a signal to interference ratio of 10: 1 is required, and the processing gain is 1000: 1, conventional CDMA systems have a capacity to allow up to 101 equal energy signals to share the same channel , During decoding, 100 of the 101 signals are suppressed to 1/1000 of their original interfering energy. The total interference energy is thus 100/1000 or 1/10, compared to the desired information energy unit. When the information signal energy is ten times larger than the interference energy, the information signal can be accurately correlated.

Along with the required signal-to-interference ratio, the processing gain determines the number of allowed overlapping signals on the same channel. That this is still the current view of the capacity constraints of a TDMA system is apparent from reading, for example, the article by Gillhousen et al. Cited above. seen.

In contrast to the known CDMA, an important aspect of the subtractive CDMA demodulation method is the recognition that the suppression of "friendly" CDMA signals is not limited by the processing gain of the wide-spectrum demodulator, as in the case of suppression of interference signals of a military nature. A large percentage of the other signals contained in a received composite signal are not unknown spurs or environmental noise that can not be correlated. Instead, most of the noise, as defined above, is known and used to decode the signal of interest. The fact that the characteristics of most of these noise signals are known, including their respective spreading codes, is used in the subtractive CDMA demodulation method to increase the system capacity and accuracy of the signal decoding process. Instead of simply decoding each information signal from the composite signal, the subtractive CDMA demodulation method also removes any information signal from the composite signal after it has decoded it. These signals, which then remain, are decoded only from the rest of the composite signal. As a result, the already decoded signals do not interfere with the decoding of the remaining signal.

For example, if signal 2 has already been decoded in Fig. 5, as shown in signal representation (a), the coded form of signal 2 can be reconstructed as shown in signal representations (d) and (c) (the beginning of the first Bit period of the reconstructed data stream for signal 2, aligned with the beginning of the fourth chip of the code for signal 2, as shown in the signal representations (d) and (e) in Fig. 2 shown) and subtracted from the composite signal in the diagram (d) (again with the first chip of the reconstructed coded signal 2 aligned with the fourth chip of the received composite signal) to supply the coded signal 1 in the signal representation (e) leave. This can easily be verified by comparing the signal representation (e) in FIG. 5 with the signal representation (c) in FIG. 2 is compared (cut off by removing the first three and the very last chip). Signal 1 can be easily retrieved by multiplying the coded signal 1 by the code 1 to reconstruct the signal 1. It should be noted that due to the fact that the bit periods for data streams for signals 1 and 2 are shifted relative to each other by two chips, only six +1 chips in the first bit period of the recovered signal 1 in the signal representation (f) in Fig. 5 are shown. Significantly, while the known CDMA decoding method was incapable of determining whether the polarity of the information bit in the second bit period of signal 1 was +1 or -1 in the signal representation (f) of FIG , the decoding method of the subtractive CDMA demodulation method effectively resolves this ambiguity simply by removing the signal 2 from the composite signal.

A general CDMA system will now be described with reference to FIG. An information source, such as speech, is converted from an analog format to a digital format in a known source coder 20. The digital bitstream generated by the transmitter source encoder 20 may be further processed in a transmitter error correction coder 22 which adds redundancy that broadens the transmission bandwidth or bit rate. In response to a spreading code selection signal from a suitable control mechanism, such as a programmable microprocessor (not shown), a particular spreading code is generated by a transmit spreading code generator 24 which, as described above, may be a pseudo noise figure generator. The selected spreading code is summed in a Modudo 2 adder 26 with the coded information signal from the error correction encoder 22. It will be appreciated that the modulo-2 addition of two binary sequences is basically an exclusive OR processing with binary logic. The modulo-2 summation effectively spreads each bit of information from the coder 22 into a plurality of "chips."

The encoded signal output by the adder 26 is used to modulate a radio frequency (RF) carrier in a modulator 28 using any of a number of modulation techniques, such as QPSK.

The modulated carrier is transmitted via a radio interface by means of a known radio transmitter 30. A plurality of signals overlapping in the associated frequency band are received together in the form of a composite signal waveform at a radio receiver 32, such as a cellular base station. After demodulation in a demodulator 34 into the baseband, the composite signal is decoded.

An individual information signal is decoded or "despreaded" by multiplying the composite signal by the corresponding unique spreading code generated by a receiver spreading code generator 36. This unique code corresponds to the spreading code originally used in the transmission spreading code generator 24 to spread the information signal. The spreading code and the demodulated signal are combined by a multiplier 38. Since multiple received chips represent a single bit of the transmitted information, the output of multiplier 38 may be sequentially integrated over a given number of chips to obtain the actual values ​​of the information bit. As described above, these bit value decisions may be made by taking an average or majority decision of the chip polarities during each bit period. In either case, the output signals of the multiplier 38 are last applied to a receiver error correction decoder 40 to reverse the process applied by the transmitter error correction decoder 22, and the resulting digital information is converted to analog format (e.g., speech) by a source decoder 42.

As described above, this decoding scheme can theoretically be used to decode each signal in the composite signal. Ideally, the contribution of unwanted interfering signals is minimized if the digital spreading codes are orthogonal to these unwanted signals and if the relative timing between the signals is strictly maintained.

In a preferred embodiment of the present invention, the error correction is based on orthogonal or bi-orthogonal block coding of the information to be transmitted. In orthogonal block coding, a number of M bits to be transmitted is converted into a 2M 2M bit orthogonal codeword. Decoding an orthogonal codeword involves a correlation with all elements of the set of N = 2M codewords. The binary index of the codeword that provides the highest correlation gives the desired information. For example, if a correlation of sixteen 16-bit codewords numbered 0-15 produces the highest correlation in the tenth 16-bit codeword, the underlying information signal is the 4-bit binary codeword 1010 (which is the integer 10 in decimal notation) , and therefore index 10). Such a code is also referred to as a [16,4] orthognathic block code and has a spreading ratio of R = 16/4 = 4. By inverting all bits of the codewords, one more information bit per codeword may be transmitted. This type of coding is known as bi-orthogonal block coding.

An important feature of such coding is that simultaneous correlation with all orthogonal block codewords in a sentence can be efficiently performed by means of a Fast Walsh Transformations (FWT) device. For example, in the case of a [128.7] block code, 128 input signal samples are transformed into a 128-point Walsh spectrum in which each point of the spectrum represents the value of the correlation of the input signal samples to one of the codewords in the set. A suitable FWT processor is described in commonly assigned U.S. Patent No. 5,357,454.

In accordance with one aspect of the present invention, the coding for each information signal is unique by using a different binary mask, also called an encryption mask or signature sequence, to encrypt each block-coded information signal. Using modulo-2 addition, such an encryption mask may be added to the already block-coded information and result. The same encryption mask is subsequently used at the receiver to decrypt the information signal from the composite signal.

It is understood that maximum length sequences, also known as m-sequences, have been used for encryption masks. Maximum length sequences are the maximum period sequences that can be generated by a k-stage, linear feedback linear shift register. The maximum period of a binary sequence generated by such a shift register is 2k-1 bits. Since an encryption mask normally consists of one period of such a sequence, maximum period means maximum length. Maximum length pseudorandom encryption masks have the useful autocorrelation property that each mask has a correlation of 1 with itself unshifted, and -1 / N with any bit shift of itself, where N is the number of bits or length of the encryption mask. In principle, different shifts of a maximum length sequence could be used to obtain encryption masks for a number of spread spectrum signals, provided that these signals are accurately time synchronized with each other to obtain the desired relative bit shifts. However, disadvantageously, it is usually impractical to arrange transmissions from a number of mobile stations to be received at a base station with a relative time alignment accuracy of better than +/- a few chips (in the examples of a CDMA shown in Figs. Demodulation, the bit periods of the data streams for signals 1 and 2 have been shifted by two chips relative to each other). Under these conditions, maximum length sequences are not suitable encryption masks because a time alignment error of one mask can make it look exactly like another mask.

Gold codes can be used to address the time alignment problem. Gold codes are sequences that have minimal, cross-correlation, not only when they are time-aligned, but also when the time alignment is shifted by several bits. However, this property is achieved only if the underlying source information is either 000000 .... 00 or 111111 ... 11 along the entire code sequence. Since block coding is used to spread the signal, not the encryption mask, the underlying information bits form a codeword with different bit values. Thus, the desired mutual cross-correlation properties can not be achieved in a viable communication system.

The disadvantages of the approaches of the prior art are solved by the present invention. Code bits resulting from a transmitter error correction coder are combined with one of a set of encryption masks. When the error correction encoder uses orthogonal block coding, one block of M information bits is encoded using one of 2M codewords of 2M bits in length. The present invention is also applicable to bi-orthogonal block coding in which M + 1 bits are encoded using one of 2M codewords (of 2M-bits in length) or their inverses (also 2M-length). According to the present invention, the encryption masks are arranged to minimize the cross-correlation of any orthogonal codeword masked by a first encryption mask with any orthogonal codeword masked by any other encryption mask.

As mentioned above, orthogonal and bi-orthogonal block codes can be conveniently decoded using an FWT circuit which correlates a composite signal with all possible N = 2M codewords of an input block with N = 2M samples. The FWT is an information lossless process that can be reversed to recover the original information signal samples from the correlations. Like the Fourier transform, the FWT satisfies the Parseval theorem by making 1 / N times the sum of the squares of the input samples equal to the sum of the squares of the calculated correlations. For an input sequence of ± 1 values, the correlation values ​​between -1 and 1 increase. Decoding an orthogonally encoded information signal includes determining which of the correlations calculated by the FWT circuit has the largest value, the binary index of the largest correlation representing the decoded information bits. When a bi-orthogonal coded information signal is decoded, the correlation with the largest value is determined, which provides an index for all but one of the information bits. The last information bit is determined from the sign of the largest-value correlation.

The goal of minimizing errors due to interference from overlapping signals means that the interference signals do not produce one or more large correlations in transforming that could be mistaken for the desired signal to be decoded. Instead, the interference signals should be transformed so as to be evenly distributed, ie, the same size in terms of all correlations. This condition of evenly distributed correlations can be called a flat Walsh spectrum. A more mathematical definition provides that if the interfering energy is normalized to one (namely, 1 / N times the sum of the squares of the input samples one), then each of the calculated correlations will be the same value ± 1 / N¹ / 2. having.

Encryption masks that cause interfering signals to have a flat Walsh spectrum when decoded using a different encryption mask can only be obtained when N is an integer and N is an even power of two (ie, N = 22Z , where Z = 1, 2, 3, ...), z. 4, 16, 64, etc. Systematic approaches to constructing cryptographic masks generating flat Walsh spectra are described below.

The encryption masks to be created are the same length as the orthogonal codewords to which they are added modulo-2. When a unique encryption mask is added to all N codewords in a Walsh-Hadamard code set modulo-2, the result is a unique set of N "encrypted" codewords that are a co-set of the original Walsh-Hadamard code set form (ie another code set). The encryption masks are selected so that the correlation between the coded codewords of different co-sets has constant size, no matter what two co-sets are compared, and regardless of which coded codewords within the two codices are compared.

To achieve this property, the modulo-2 sum of any two encryption masks must be a "bent" sequence. As noted above, Bent sequences are sequences that have a shallow Walsh transform, ie, sequences that are equal in magnitude to all N possible Walsh-Hadamar codewords. For example, consider F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, Parts I and II (New York: North-Holland, 1977). A set of encryption masks with this property may be called an "ideal" set.

The present invention includes two methods for generating ideal encryption mask sets. The first method, method A, generates a set of encryption masks of length N. The second method, method B, generates a set of N / 2 encryption masks of length N.

Method A:

Let n = N1 / 2; Let w &, w₁, ..., wn-1 be the n Walsh-Hadamard codewords of lengths; and let k = log 2 (n). The set of encryption masks is formed using the following procedure.

1. Choose a primitive polynomial p (X) over a Galois field FG (2) of degree k from, for example, R. Marsh, "Table of Irreducible Polynomials on GF (2) thorugh Degree 19", National Security Agency, Washington, DC (1957) or W.

Peterson, Error-Correcting Codes, (New York: John Wiley & Sons, 1961). If k = 1, step 1 can be omitted.

For example, for n = 4 and k = 2, p (X) = 1 + X + X².

Second Use p (X) to define a Galois field GF (2k) with a primitive element "a" such that p (a) = 0. The Galois field GF (2k) consists of n = 2k elements: 0 , 1, a, a², a³, ..., an-2. If k = 1, the standard Galois field GF (2) with elements 0 and 1 is formed.

For the above example where N = 4, the GF (2 2) is formed with elements (0, 1, a, a 2), where p (a) = 0 defines the element "a".

Third Make the sequence: {1, a, a², a³ ..., an-2}, consisting of n - 1 = 2k - 1 elements of the Galois field GF (2k), ie all elements except zero. (For k = 1, this is {1}.)

For the n = 4 example, this yields the sequence {1, a, a²}.

4th Replace each element in the sequence with its polynomial representation, forming the sequence:

{b¹ (a) = 1, ba (a) = a, ba2 (a) = a2, ..., ban-2 (a) = an-2}

This can be done as follows. Each of the elements GF (2k) can be expressed as a polynomial in "a" of degree k-1: b & sub0; + b1a + ... + bk-1ak-1. The coefficients (b0, b1, ..., bk-1) give the "k-tuple" representation of an element in GF (2k)

Consider the N = 4 example above. The fact that p (a) = 0 gives:

0 = 1 + a + a² or a² = -1 - a = 1 + a

since + and - are equivalent in modulo 2 arithmetic. Thus, in this example, the sequence {1, a, a²} would be replaced by {1, a, 1 + a}.

5th Evaluate each polynomial representation in the sequence with a = 2, using normal integer arithmetic. This results in a sequence of integers 1, 2, ..., n-1, not necessarily in this order.

For the above = 4 example this gives the sequence {1, 2, 3}.

6th Interpreting each integer as an index of a Walsh-Hadamard codeword, substituting every integer (index) in the sequence with the n-bit Walsh-Hadamard codeword of that index. This results in a ((n-1) n) -bit sequence.

For the above = 4 example, the Walsh-Hadamark codewords are: w & sub1; = 0101, w & sub2; = 0011, and w & sub3; = 01110, and this yields the 12-bit sequence: {410101, 0011, 0110} or {010100110110}.

7th Further n-2 such sequences are obtained by simply rotating circularly (or circularly permuting) one shift per time to the left, the sequence in step 5, and repeating step 6. (This is equivalent to a circular one Rotate n shifts in the sequence in step 6 at a time.)

For the n = 4 example, this results in two additional sequences:

{0011,01010,0101} = {001101100101}, for {2,3,1}; and

{0110,0101,0011} = {011001010011}, for {3,1,2}.

8th. Extend the length of the sequences of steps 6 and 7 to n 2 = N bits by inserting the n-bit Walsh-Hadamard codeword w 0 consisting of n zeros before each sequence.

For the n = 4 example, this yields the three 16-bit sequences:

{0000010100110110}, {0000001101100101}, and

{0000011001010011}.

9th The set of n-1 n 2 bit sequences is increased by the all-zero sequence consisting of n 2 zeros. For the above n = 4 example, this is the 16-bit sequence

{0000000000000000}.

10th After the n sequences of length n 2 are constructed, they can be converted into a set of n scrambling masks by modulo-2 adding a "base" sequence of n 2 bits. These encryption masks make up a set of n (ie N1 / 2) encryption masks of length n 2 (ie N).

The basic sequence may be chosen so that the encrypted information signals have desirable autocorrelation properties, as well as cross-correlation properties when there are echoes or time misalignments. Also, in the case of cellular mobile communication, a different basic sequence may be assigned to different cells. In this case, the correlation properties between different base station sequences can be taken into account.

For the n = 4 example, it is assumed that the base sequence is {0000111100001111}. The resulting set of encryption masks is given by:

{0000 1010 0011 1001}

{0000 1100 0110 1010}

{0000 1001 0101 1100}

{0000 1111 0000 1111}.

This completes method A for constructing an ideal set of N1 / 2 encryption masks of length N.

Method B:

In method B, a set of N / 2 encryption masks of length N is formed. The method is based on the use of N / 2 of the length N N 2 codewords forming a Kerdock code. These codewords are permuted and then added to a common base sequence as in step 10 of method A. A Kerdock code is a "supercode" in that it consists of N / 2 code sets, each of which is a bi-orthogonal code. With the correct permutation, the permuted Kerdock code contains the Walsh-Hadamard code as well as (N / 2 - 1) Co-phrases of the Walsh-Hadamard code. It is recalled that a co-sentence is obtained by applying an encryption mask to all code words in a sentence.

A Kerdoc code is formed by combining a Reed-Muller first-order cyclic code set with (N / 2 - 1) Co-sets as mentioned in the above-mentioned book by MacWilliams and Sloane. Thus, it consists of N / 2 code sets each containing 2 N bi-orthogonal codewords of length N, giving a total of (N / 2) (2 N) = N 2 length N codewords. By permuting each codeword in a particular manner, the Kerdoc code has the property that the modulo-2 sum of a codeword of one codeword with a codeword of another codeword is a Bent sequence.

The procedure for generating N / 2 encryption masks of length N is as follows:

1. Create N / 2 code set representatives (CSR) of a Kerdoc code. A method for generating the entire Kerdock code is available from A. Kerdock, "A Class of Low-Rate Nonlinear Codes," Info. and Control, Vol. 20, pages 182-187 (1972) and in the above cited MacWilliams and Sloane text at pages 456-457.

One method that directly generates the code set representatives (CSR) is in the MacWilliams and Sloane text on pages 457-459. The method separately generates the left half (N / 2 bits) and right half (N / 2 bits) of each CSR. Each N-bit CSR (crsj) has the form:

wherein ABCD denotes the combination of A (1 bit), B (N / 2 - 1 bits), C (1 bit) and D (N / 2 - 1 bits) into a sequence; xj () the cyclic right shift operation by j places what is inside the parentheses; Li = 1 + 2i; t = (log 2 (N) - 2) / 2; and θk * denotes a specific primitive idempotent polynomial (which can be interpreted as a sequence) of length N / 2 - 1 as defined in the MacWilliams and Sloane text mentioned above. Note that the left half of the CSR consists of AB and the right half consists of CD. The csr & sub0; is defined by the zero-only sequence.

It is important to note that the special primitive member polynomials are based on a Galois field GF (2R = N / 2) 3 where r = log 2 (N / 2). Thus, a GF (N / 2) is used to form each half of the Kerdock code set representative.

For example, consider N = 16, N / 2 = 8, r = 3 and t = 1. Then the special idempotent polynomials (and thus series) in the MacWillsams and Sloane text mentioned above are given as:

& thetav; & sub1; * = 1 + X 3 + X & sup5; + X? - {1001011}

& thetav; & sub3; * = 1 + X¹ + X² + X & sup4; - {1110100}

so in modulo-2 arithmetic:

θ 1 * + θ 3 * = {0111111}.

Thus, every CSR has the form

csrj = 0 xj (θ 3 *) 0 xj (θ 1 * + θ 3 *)

= 0 xj ({1110100}) 0 xj ({0111111})

Evaluating this expression for j = 0, 1, ..., N / 2 - 1 gives the eight SCR in Table 1 below. Table 1 Example of 16-bit Kerdock CSR

Second Permute every (N / 2-bit) half of each Kerdock CSR to obtain the left and right halves of a permuted sequence.

The permutation is based on the primitive element "a" in the Galois field GF (N / 2), used to form each half of the Kerdock CSRs. The permutation is defined by forming the Galois field elements in the order 0, 1, a, a², ..., aN / 2-2. These correspond to positions 0 to N / 2 - 1 in each half of the Kerdock CSR. The corresponding position in the permuted sequence is obtained by expressing each element as an r-tuple, where r = log 2 (N / 2). The r-tuple has the form b & sub0; + h1a + ... + br-1ar-1. By interpreting the coefficients b & sub0; to br-1 as coefficients to the power of 2 (ie b 0 + 2b 1 + 4b 2 + ... + 2r-1br-1), an integer in the range [0, N / 2 - 1] ( with bs = 0 or 1, for all s), where the coefficients bs provide a binary representation of an integer indicating the corresponding position in each half of the permuted sequence. It should be noted that the binary number for the corresponding position is exactly br-1br-2... B 2 b 1 b 0. is.

For the above example, the primitive element "a" in GF (8) is used to form the Kerdock code, defined by the primitive polynomial p (X) = X 3 + X + 1, representing 3-tuple representations of the elements in GF (8) in Table 2 (see the MaxWilliams and Sloane text, page 110). Using the approach described above, the permutation mapping for each half of the sequence giving the corresponding new position in the permuted sequence is also shown in the following Table 2 (which can be easily verified by reading the 3-tuples backwards). Table 2 GF (8) and half-sequence permutations

Applying the permutations to each Kerdock CSR in Table 1 gives the set of permuted sequences in the following Table 3. Table 3 Set of 16-bit permuted sequences

Third Once the N / 2 permutated sequences of length N have been established, they can be converted to N / 2 scrambling masks by modulo-2 adding a "base" sequence of N bits. As in method A, the base sequence may be chosen such that the encrypted information signals have desirable autocorrelation properties, as well as cross-correlation properties when echoes or time misalignments are present. Also, in the case of cellular mobile communication, another base sequence may be assigned to other cells. In this case, correlation properties between different base station sequences would be considered.

For the above example, assume that the arbitrary base sequence is {0000111100001111}. The resulting set of encryption masks is given in Table 4. Table 4 Set of 16-bit encryption masks

This completes method B for forming an ideal set of N / 2 encryption masks of length N.

It is understood that the encryption mask methods A and B provide masks having good cross-correlation properties when two signal waveforms are time aligned, regardless of the selected basic sequence or mask. The base mask can provide good autocorrelation properties, which is important when there are echoes of a signal. The base mask may also provide good cross-correlation properties when two signals are not time aligned or there are echoes.

The present invention may be incorporated directly into a multiple access spread spectrum communication system by storing these encryption masks in a lookup table in, for example, a RAM or ROM memory from which a particular mask is retrieved by providing the associated address. A system for implementing the encryption masks into a spread spectrum system is illustrated in FIG. While described in the context of a memory look-up table, it will be understood that a suitable code generator, such as a digital logic circuit or microcomputer, that provides the encryption masks online, as indicated by selection control input signals, may also be used.

Source information, e.g. Speech, is converted in a source coder 50 into blocks of M (or M + 1) binary bits, and these bit blocks are coded by an error correction orthogonal (or bi-orthogonal) block coder 5. The orthogonal 2M-bit block codewords are encrypted using a modulo-2 N-bit adder 53 with an encryption mask constructed as described above, retrieved from a look-up table into a memory 60. In the case of ideal encryption masks, there are either nA = N1 / 2 or nB = N / 2 encryption masks, depending on the method used to generate the encryption mask set. Thus, the number of bits needed to address each mask in memory 60 is either ba = log2 (nA) or bB = log2 (nB), and by transmitting the ba-bit or bB-bit encryption mask select address , associated with a particular encryption mask, to memory 60, the mask is fetched from memory and added to the block coded signal modulo-2.

The ability to selectively address and retrieve a particular encryption mask may be important in determining an order in which signals from a received composite signal are decoded. For example, if stronger coded information signals are first decoded and removed from the composite signal before weaker signals are decoded, the scrambling masks must be ordered according to the signal strength of the associated coded information signals. In subtractive CDMA demodulation according to the patent applications incorporated by the above reference, the encryption mask would be selected according to the strongest information signal for decoding. After the signal is removed, the scramble mask is selected according to the next strongest information signal, and so on, until the weakest signal is decoded.

The masked block code words from the N-bit adder 53 may be applied to a parallel-to-serial converter and modulator 54 where they are impressed on a radio frequency carrier. The modulated signal is amplified and transmitted via a transmitter 56 and an antenna 58.

At the receiver, the composite signal is received by an antenna 61 and applied to a receiver demodulator 62 which demodulates, samples and digitizes the composite signal. A serial to parallel converter 64 converts the serial samples into parallel blocks of signal samples (which may be complex, corresponding to in-phase and quadrature signal components). The order in which each information signal is decoded in the receiver is determined by the receive encryption mask selection address bA or bB applied to an encryption mask memory 66. In a specialized N sample multiplier 68, each of the N parallel samples is buffered in the serial / parallel converter 64, multiplied by a +1 or -1, depending on the encryption mask retrieved from memory 66. One way to perform this multiplication is an exclusive-OR processing of each bit of the digital sample with the corresponding encryption mask bit. For example, if the first of the N digital samples is 1011 and the first encryption mask bit is -1, the first of the N output samples would be 0100. If the received samples are complex, different encryption masks could be used for the in-phase and quadrature components.

The decrypted signals are decoded in a block decoder 70, which may include an FWT circuit 72. The index of the transformation component having the largest correlation amount (bi-orthogonal code) or value (orthogonal code) is determined, and selected as the decoded information by an ordering and selecting circuit 74. A suitable apparatus for determining the largest of a number of input values ​​is disclosed in commonly assigned US Pat. 5,187,675. For simplicity, in this application the term "size" is used to refer to correlations with both orthogonal and bi-orthogonal codes. The FWT circuit 72 would preferably operate on complex numbers when the demodulator and converter 64 provide complex signal samples, which is often the case when the phase of the received signal is not known. The decoded M or M + 1 bits of information are received by a source decoder 76 for analog-to-analog conversion, e.g. Eg language.

Using the encryption masks generated as described above, interference of signals having such encryption masks that differ from that selected at the receiver is at least theoretically evenly distributed across each of the FWT circuit correlation outputs.

Since no spurious peaks occur, the risk of minimizing an error in determining the largest correlation as the decoded information is minimized.

In multiple access spread spectrum communications, it is not uncommon for the receiver to use the HAKE combining method to combine correlations of different signal beams (ie, to collect energy from a signal and its echoes). In the system shown in FIG. 7, this would appear as a RAKE combiner 73 between the FWT circuit 72 and the order and selection circuit 74 as illustrated in FIG. For each of the N outputs of the FWT circuit, results from different signal arrival times would be weighted and accumulated before being sent to the ordering and selecting circuit. Data corresponding to different arrival times would be applied to the serial / parallel converter 64. Further, a new method called WRAKE combining could be used instead of conventional RAKE combining. The RAKE combining method and the new efficient WRAKE approach can be found in detail in US Patent No. 5,237,586, assigned to the same assignee.

If the length N of the encryption masks, or signature sequences, is an odd power of two (ie, if N = 22Z-1, where Z = 1, 2, 3, ...), ideal correlation properties are not available. In other words, it is impossible to construct the encryption masks so that the sum of any two is a Bent sequence that is evenly sized in size to all N Walsh-Hadamard codewords. In this case, however, one can use a half-Bent sequence, which is a sequence which is equal in magnitude to half of the N codewords, and which has a zero correlation with the other half. Thus, it is possible to construct sets of encryption masks such that the sum of any two is a half-Bent sequence. A set of encryption masks with this property may be referred to as a particular "semi-ideal" set.

In accordance with the invention, two ways of constructing semi-ideal sets of encryption masks are provided. The first method uses either method A or method B (the two methods described above for generating ideal sets of encryption masks) to generate a set of either (N ') 1/2 or N' / 2 encryption masks of length N '. convince, where N '= 2 N (where N is an odd power of two). The modulo-2 sum of any two of these encryption masks of length N 'would be a Bent sequence, uniformly correlated in size to N' = 2 N codewords of length N '= 2 N. Then, the last half of each encryption mask (the N- Bits long), leaving masks of length N '/ 2 = N. Thus, the modulo-2 sum of any two of these truncated encryption masks of length N would be a sequence of length N that could be uniformly correlated in magnitude with at most only N '/ 4 = N / 2 codewords of length N' / 2 = N. Thus, depending on the method used, a set of either (2 N) 1/2 or N encryption masks of length N is formed so that the sum of any two encryption masks is half Bent.

In the second approach to building semi-ideal sets of encryption masks, again either method A or method B is used to form a set of either (N ') 1/2 or N' / 2 encryption masks of length N ', where N '= N / 2 (where N is an odd power of two). The modulo-2 sum of any of these two encryption masks of length N 'would be a Bent sequence, equally correlated in size to N' = N / 2 codewords of length N '= N / 2. Then, for each sequence of N 'length, a copy is added to it, yielding masks of length 2N' = N. Alternatively, it is also possible to attach a copy of another mask to each mask instead of attaching a copy of it. Therefore, a modulo-2 sum of any two of these duplicated N-length scrambled masks would be a sequence of length N which would still be equally correlated in size with at most only N '= N / 2 codewords of length 2N' = N. Thus, depending on the method used, a set of either (N / 2) 1/2 or N / 4 encryption masks of length N is formed such that the sum of any two encryption masks is half Bent.

For both cases of N (ie, N is either an even or odd power of two), the above methods may provide sets of encryption masks that are not large enough. These sets can be extended by additional encryption masks, however, the modulo-2 sum of any two masks can no longer be a bent or half-Bent sequence. However, these sets may be advantageously extended so that the modulo-2 sum of any two masks is equally correlated in magnitude with at least some subset of the code words. A sequence that is equally correlated in size to a subset of the codewords and uncorrelated to the remaining codewords is referred to as a "partial Bent" sequence.

To extend ideal or semi-ideal sets of encryption masks, two methods (methods 1 and 2) can be used. Both methods use special masks which are added to each encryption mask in the original ideal or semi-ideal modulo-2 set. Each particular mask generates a different set of encryption masks, and these sets can be combined to form an extended set of encryption masks. If U is the number of encryption masks in the original ideal or semi-ideal set, then the number of masks in the extended set is SU, where S is the number of special masks. These special masks are formed by concatenating P patterns of length L, where PL = N and P and L are also powers of two.

In method 1, there are two possible patterns: the zero-only pattern (L zero) and the one-only pattern (L ones). A set of Sa encryption masks of length P is formed using either Method A or Method B (the two methods described above for forming ideal sets of encryption masks, also known as "good" sets of encryption masks, due to their "good" "Correlation properties, such as having minimal cross-correlation between members of sentences). Each of these P length encryption masks is extended into an N length special mask (complementary mask) by replacing each "0" with the pattern of L zeros and replacing each "1" with the pattern of L ones. Then the original set of U encryption masks of length N are extended to S 1 U masks by modulo-adding each special mask to the U masks of the original set.

For example, consider the previous example set of four 16-bit length encryption masks by which method A generates. To extend this sentence using method 1, a set of encryption masks of length P = 4 is needed. Using method A for this sentence, two masks result: {0000} and {0001}. Replacing each 0-bit with four zeroes and each 1-bit with four ones provides two special masks:

{0000 0000 0000 0000}

{0000 0000 0000 1111}

Applying the first special mask to the original sentence yields elements of the original sentence:

{0000 1010 0011 1001}

{0000 1100 0110 1010}

{0000 1001 0101 1100}

{0000 1111 0000 1111}

Applying the second special form to the original set yields the following elements of a new set:

{0000 1010 0011 0110}

{0000 1100 0110 0101}

{0000 1111 0101 0011}

{0000 1111 0000 0000}

Thus, using both special masks, an extended set of eight 16-bit length encryption masks is obtained.

In method 2, each special mask consists of a single L-bit pattern that is repeated P times. A set of S & sub2; Encryption masks of length L are formed using either Method A or Method B. Each of these length L masks is then repeated P times, giving S & sub2; Special masks (pattern masks) of length N results. As in method 1, each special mask is modulo-2 added to the original set of U encryption masks to form U new encryption masks. Thus, an extended set of S & sub2; U encryption masks formed:

For example, consider the previous example set of four 16-bit length encryption masks by which method A generates. To extend this sentence using method 2, a set of encryption masks of length L = 4 is needed. Again, using Method A for this set provides two masks: {0000} and {0001}. Repeating each pattern P = 4 times gives two special masks:

{0000 0000 0000 0000}

{0001 0001 0001 0001}

Applying the first special mask to the original sentence yields the elements of the original sentence:

{0000 1010 0011 1001}

{0000 1100 0110 1010}

{0000 1001 0101 1100}

{0000 1111 0000 1111}

Applying the second special form to the original set yields the following elements of a new set:

{0001 1011 0010 1000}

{0001 1101 0111 1011}

{0001 1000 0100 1101}

{0001 1110 0001 1110}

Thus, using both special masks, an extended set of eight 16-bit length encryption masks is obtained.

It will be understood that methods 1 and 2 can be advantageously used together, either by individually combining what S & sub1; + S & sub2; Special masks, or preferably by mutual application, gives S & sub1; S & sub2; = ST results in special masks. Thus, up to STU encryption masks can be formed, where U is the number of encryption masks in the original set (method A or B).

For example, consider the special masks generated in the above examples. Applying the first special mask of method 2 to both special masks of method 1 gives both methods 1 special masks:

{0000 0000 0000 0000}

{0000 0000 0000 1111}

Applying the second special mask of method 2 to both special masks of method 1 yields two new special masks:

{0001 0001 0001 0001}

{0001 0001 0001 1110}

Thus, four special masks are obtained using both methods 1 and 2. Generally, S & sub1; S & sub2; > S & sub1; + S & sub2; except when S & sub1; = S & sub2; = 2.

Applying the first special mask to the original sentence yields the original sentence:

{0000 1010 0011 1001}

{0000 1100 0110 1010}

{0000 1001 0101 1100}

{0000 1111 0000 1111}

Applying the second special mask to the original set yields the new set (encountered in procedures):

{0000 1010 0011 0110}

{0000 1100 0110 0101}

{0000 1001 0101 0011}

{0000 1111 0000 0000}

Applying the third special mask to the original sentence yields the new sentence (found in Method 2):

{0001 1011 0010 1000}

{0001 1101 0111 1011}

{1101 1000 0100 1101}

{0001 1110 0001 1110}

Applying the fourth special mask to the original sentence yields the new sentence (not yet encountered):

{0001 1011 0010 0111}

{0001 2101 0111 0100}

{0001 1000 0100 0010}

{0001 1110 0001 0001}

A cellular communication system consists of base stations and users in each cell. For both the uplink (base station to base station) and downlink (base station to user) transmissions, interference from adjacent or non-adjacent cell signals can be minimized by carefully assigning different encryption masks to the signals in different cells. The problem is analogous to frequency allocation or assignment in current cellular mobile radio systems.

There are a certain limited number of encryption masks that make up a set of encryption masks with the desired correlation properties. Among the entire encryption masks, there are subsets of encryption masks that have good correlation properties, whereas correlation properties between masks of different subsets need not be so good. Likewise, if there are more signals than encryption masks, the encryption masks must be reused. To minimize interference, encryption masks with certain "good" correlation properties (ie with the property that the mean correlation of the sum of two encryption masks to all possible codewords is minimal) should be used in close proximity (e.g. in the same cell or adjacent cells); those with correlation properties that are not so "good" (ie with the property that the mean correlation of the sum of two encryption masks to all possible codewords is greater than minimum) should be used far apart (eg, in non-contiguous ones) cells). Correlation properties may include the mean correlation to all possible codewords of the sum of two encryption masks, with one of the masks shifted with respect to the other.

In the above, detailed procedures have been performed to generate extended sets of SU encryption masks, where S is the number of special masks used (S = S 1 or S 2 or S 1 S 2). In this way, there are S sub-sets of U masks each. Two masks from the same sub-set have better cross-correlation properties (ie the sum of the masks has on average lower correlations to all possible codewords) than two masks of different sub-sets.

This property can be exploited when masks are mapped to different signals in a CDMA system. Nearby-neighbor signals may be assigned masks from the same subset, while far-flung signals may be associated with scrambling masks from different sub-sets.

For example, each cell in a cellular system may be associated with one of the S sub-sets of U masks. Signals within a particular cell are assigned a mask from the subset associated with that cell. Thus, interference within the cell is minimized because each subset has special optimal correlation properties (ie, the sum of two encryption masks is Bent or Half Bent). Thus, within each cell, the available encryption masks are in the form s + u, where s is one of the S special masks, u is one of the masks in the original set of U masks, and "+" denotes a bit by bit modulo 2 addition. Thus, all masks used within a cell have the same special mask s, which can be considered as a base station identification (ID) mask. The mask u can then be referred to as a user ID mask. Thus, by storing or generating S base station ID masks and U user ID masks, a transmitter or receiver can receive any of the SU encryption masks. This is usually more economical than inidvidually saving or creating all SU masks.

As a first numerical example, it is assumed that the mask length N = 128 bits. The above-mentioned second way of generating masks when N is an odd power of two, along with method B, gives N / 4 = 32 128-bit encryption scripts. A single maximum length sequence of 127-bit length extended to 128-bits can be added to all 32 encryption masks. This yields a subset of U masks, where U = 32.

It is assumed that this sentence is extended using both complementary masks (method 2) and pattern masks (method 2) using P-patterns each of length L such that PxL = N = 128. For the complementary masks (method 1) It is assumed that P is chosen as sixteen, and L is chosen as eight. Using Method B this yields P / 2 = 8 complementary masks. For the pattern masks (method 2), it is assumed that P is eight and L is sixteen. Using method B, this gives L / 2 = 8 pattern masks. Using both complement and pattern masks, this adds up to 8 x 8 = 64 special masks. Thus, there are 64 sub-sets of each 32 masks. Therefore, there are 64 different base station ID masks, and 32 different user ID masks (U = 32). If only eight base station ID masks are needed, then either pattern masks or complementary masks may be used to provide eight sub-sets of each 32 different user ID masks.

As a second numerical example with N = 128, the above-mentioned first mode for generating masks when N is an odd power of two, together with the method A yields (2 N) 1/2 = 16 128-bit length encryption masks. Using the same eight pattern masks and the same eight complementary masks as in the first numerical example, 64 different base station ID masks and 16 different user (signal) ID masks can be obtained.

As another example, 512 encryption masks may be formed using 16 base station ID masks and 32 user ID masks. A set of 32 encryption masks is assigned to a maximum of 32 calls that take place in a particular cell. Another set of 32 encryption masks is assigned to a maximum of 32 calls taking place in a neighboring cell, and so on. In this way, up to 16 different base stations / cells can be provided with sufficient masks that are unique to each support up to 32 calls, all on the same frequency channel. Moreover, it is possible to factorize the mask set into 16 base station ID masks and 32 user ID masks, so that any desired mask can be generated by bit modulo-2 adding a desired base station ID mask to a desired one User ID mask, which reduces the memory requirements of 512 masks to 16 + 32 = 48 masks.

In addition, in the case that cross-correlations between the masks are not all uniformly low, it is possible to choose each set of 32 masks used within the same cell and therefore more likely to interfere with each other so that they have the lowest mutual cross-correlations, while the cross-correlations with masks in different sentences in different cells can have higher values.

Which of the 32 user ID masks would use a particular mobile phone (in the case of a static, non-cyclical mapping) would be communicated to the mobile by the base station at the pager. In the case of a pseudo-random cycle mask assignment described below, the number of shifts to be used by a particular mobile phone would be communicated by the base station to the mobile in the call setup. The base ID mask used by surrounding base stations would be transmitted by a base station to all cell phones in its cell by broadcast on a broadcast channel. The base ID may be static while the user ID mask selection to which the base ID is connected is cyclic. The reason for this is to make it easier for a mobile station to listen to fixed base ID codes to identify which base stations it can hear.

In situations where N is an odd power of two, or if more than one of nA = N1 / 2 or nB = N / 2 scramble masks is desired, the desired flatness of the Walsh spectrum may not be achieved. In this case, it may be preferable that the "non-flat" encryption masks, which should be as "flat" as possible, are generated by numerical synthesis techniques performed by a computer search. Using non-flat masks, it is desirable to average out an uneven distribution of interference correlations to avoid having a particular pair of orthogonal codewords having more than the mean value of mutual interference, or to avoid having a particular codeword / information bit block Error rate that is higher than normal. The effect of any non-smoothness can be reduced by cycling the selection of encryption masks using a systematic or pseudorandom counter to select the masks, as described below.

It should be understood that such an approach is a form of code hopping, analogous to the idea of ​​frequency hopping, and that it can be applied in any CDMA system that uses a fixed set of codes or signature sequences. Each CDMA system can be considered to encode an information signal into blocks of L code symbols. Each block is then impressed with an encryption mask (ie signature sequence) of length L. For example, conventional CDMA, as a result, repeats each information bit L times (the coding) and then applies an encryption mask of length L (either a length L sequence or a length L subsequence).

The method described below yields a form of orthogonal code hopping in which no two signals within the same group (e.g., a cell or a cluster of cells in a cellular system) use the same signature sequence at the same time. An alternative to orthogonal code hopping is semi-orthogonal code hopping in which hopping sequences are designed such that two signals within the same group rarely use the same signature sequence. This alternative is used when there are more signals than there are signature sequences. A third alternative is random code hopping, in which the signature sequence for each signal is chosen in a pseudo-random manner, independent of the other signals. Such an alternative is easier to implement but performance degrades.

If the mapping of encryption masks to signals is fixed, and the mutual correlation properties between the elements of the set of encryption masks are not flat (e.g., the modulo-2 sum of two elements of the sentence is not a bent sequence), the disadvantageous In this situation, two signals having more than the mean level of correlation therebetween permanently interfere with each other at more than an average extent. This situation can be prevented by changing the assignment of encryption masks to signals time-cycled or cyclic, in such a way that each still receives a unique mask at each time, but the signals having more than the average value of correlation between each other, are not always the same signals. For example, the interfering signal, which has a strong correlation with a given signal, could be a weaker signal at one time, and a stronger signal at a different time, but the interfering signal will thus not always be a stronger signal. Therefore, the adverse interference situations are not always present but rather transient. A general description of the effect is to say that the deterioration is evenly distributed so that it is tolerable to all, rather than intolerable to some.

This desired cyclic or time-varying assignment of encryption masks to signals may be effected by generating a random number as a function of a codeword counter. The generated pseudo-random number is the same at all transmitters and receivers. To ensure that each transmitter-receiver selects a different encryption mask at any one time, this pseudorandom number is offset by zero for the first signal, offset by one for the second signal, etc., using modulo-t addition, where t is the number of encryption masks in the set. In this way, a clear but time-variable selection of encryption masks can be ensured for t different signals. The offset pseudorandom number may be used to address a memory containing a set of encryption masks to retrieve the encryption mask that is valid for each time point. Also, to provide an even more random relationship between the selections for different signals, the addressing order that each offset pseudorandom number assigns to a particular encryption mask may also be varied from one time to another using another pseudorandom number. This change may be achieved by modulo-2 adding this second pseudorandom number to the first offset pseudorandom number, and / or by using the second pseudorandom number to permute the bits of the first offset pseudorandom number before these address the encryption mask store.

The present invention may be used in a cellular radiotelephone communications system, although it will be apparent to those skilled in the art that it may be used in other types of communication systems. In CDMA-based cellular systems that use subtractive demodulation, each set of encryption masks generated in accordance with the present invention provides private protected communications in each cell. In other words, even if it were possible to decode the composite signal using the appropriate orthogonal block codes, it would still be necessary to know which encryption masks are associated with each mobile communication before the information signal could be decrypted. However, in order for each mobile station to be able to decode its own signal from the received composite signal, it must be able to decode and remove stronger signals received for other mobile phones within the cell. As a consequence of this subtractive decoding procedure, each mobile station within a cell must know the encryption masks associated with all other mobile stations communicating with the base station's cell. In addition, these encryption masks may be selected in a pseudorandom manner based on a code key available to all mobile stations served by that particular cell. To prevent mobile stations within the cell from listening to other communications, preferred embodiments of the present invention provide private, individual conversations by encrypting the individual information signal before it is block-coded and encrypted. Only the mobile station and the associated base station know the individual encryption key.

The system security and individual privacy features of the present invention will now be described with reference to FIG. A source coder 80 converts speech information into digital form and arranges the information in blocks of M (or M + 1) information bits for subsequent orthogonal (or bi-orthogonal) block coding. Only the M-bit alternative is illustrated in FIG. 9, however, the M + 1 bit alternative is obtained simply by referring to FIG. 9 everywhere M is replaced by M + 1. Although not an essential aspect of this invention, the source coder may also provide conventional error correction coding capabilities. Prior to orthogonal coding, the M-bit (or (M + 1) -bit) block is individually ciphered by adding in a M-bit (or (M + 1) bit) adder 82 a unique cipher bit sequence generated by a transmitter sequence generator 84 , modulo-added.

The random number generated as a function of a cipher key K1 and a key K2 is combined with the information from the source coder 80 by the M-bit adder 82 to generate ciphered information signals. These ciphered information signals are then spread spectrum coded, preferably using orthogonal or bi-orthogonal block error correction coding, in an orthogonal block encoder 86 before selected encryption masks are applied to the block codes in a bitwise exclusive OR circuit 88.

The M-bit cipher block is coded orthogonally (or bi-orthogonally) in the orthogonal block coder 86, yielding an N-bit coded signal block (N = 2M or 2M-1 for orthogonal or block). bi-orthogonal coding), which is bit-by-bit exclusive-OR processed in the parallel exclusive OR circuit 88, with an encryption mask retrieved from a transmitter encryption mask memory 90, and then converted to a serial bit stream and modulated onto a radio bearer as shown in function block 92. The modulated signal is amplified by a suitable amplifier 94 and transmitted through an antenna 96.

The encryption mask is selected from a look-up table of masks in the memory 90 by applying an N 1 bit address to the encryption mask memory 90. Thus, N & sub1; the number of bits in the address for the encryption mask memory 90 and 2N1 is the maximum number of encryption masks in the memory 90 uniquely addressable by an N1 bit address. An important feature of this embodiment of the present invention is the cyclic or pseudorandom change of the encryption masks retrieved by a special lookup table address. Thus, a unique encryption mask must be generated, and this mask selection procedure must be pseudorandomly changed. The table address is advantageously determined in part by the N1 bit sequence mentioned above at Code K2. When an access code is received to select a particular encryption mask, the code key K2 may be combined with the received access code in the N1-bit adder 98 using modulo arithmetic.

The code key K2 is preferably not pseudo-randomly generated, but rather is a constant that determines the operation of the pseudo-random number generator used for selecting encryption masks. As described in greater detail below, the code key K2 ensures that the actual encryption mask address changes pseudorandomly for each mobile station. The adder 82 may be a bitwise exclusive-OR circuit or a modulo-2 M-bit adder or other equivalent circuit.

A modulo-2 adder may be modified to generate different cipher keys, such as K1, by changing the number of bit carry connections in the adder. The only thing that is required is that every possible M-bit input block map to a unique output block depending on the cipher key K1 sequence and, as described below, the K2 sequence code key. Of course, the encryption key K1 for individual mobile stations is preferably unique in order to achieve the required privacy. The cipher key K1 may also change for each new M-bit input block, so that during a single conversation the cipher key K1 changes many times. The desired receiver must therefore synchronize its receiver sequence generator with the transmitter sequence generator 84.

Synchronization can be facilitated by driving the transmitter sequence generator 84 with a systematically variable time counter, such as a frame counter 100. The receiver and transmitter then coordinate with the frame or block number of the signal block that is being decoded to synchronize operations. The details for obtaining an initial frame counter match and maintenance are not described in detail here, as day-time synchronization of cipher systems is well known in the art of communications.

The pseudo-random number generator 84 to randomize a label mask selection must generate the same value in each of the transmitter receivers, requiring mutually unique selection. Each is therefore in possession of the same system key K2, which is advantageously a multi-bit digital control word, upon which the pseudo-random number sequences generated by generator 84 depend. This system code key K2 can be used globally in a cell, a network, a leaf, or anywhere in which case it could be permanently determined in the design of the pseudorandom number generator. Otherwise, means could be provided for either programming a mobile station transmitter receiver with or receiving the code key K2 for a particular cell or network. Such means may include physically connecting the mobile station to a programming unit, inserting a mobile station or code card into the mobile station, acoustically connecting the mobile station to a programming unit via an acoustic coupler to its microphone, or receiving information by radio from the network associated with Generating a network code K2 key is used.

Since the code key K2 used for this purpose must be globally known by a number of different users, it does not provide a high level of security against eavesdropping. Thus, a preferred anti-eavesdropping system includes the encryption key K1, which is unique to each user.

Just as procedures may be required to set up a correct system code key K2 at the mobile station, the preferred implementation of a user privilege with the aid of a unique user cipher key K1 requires procedures to set up the proper cipher key K1 at the base station for each user. These procedures may include that the mobile station identifies itself to the network by transmitting its ID code over the air; the network would then poll a secret database in which ciphers are stored in accordance with mobile ID codes to obtain the correct cipher key K1. It may also be advantageous for both the mobile station and the network stations to combine such an encryption key K1 with an extemporarily generated pseudorandom number to generate a temporary encryption key K1 which is used only for one or a few communications.

The extemporaneously generated pseudorandom number may be transmitted from the network to the mobile station during an authentication process that the mobile station is the one it specifies to be, as described in US Patent No. 5,091,942, which is expressly incorporated herein by reference.

An advantage of pseudorandomly selecting encryption masks is preventing the adverse interference situation mentioned above, in which two signals in adjacent cells are unavoidably associated with encryption masks having above-average mutual correlation, and the arrangement of the mobile stations is such that the interference is effected and continues. With a pseudorandom change in the selection of the encryption mask, such an interference condition would only be transitional, and at the next block code period these two encryption masks would be assigned to another pair of mobile stations with a different relative arrangement.

The receiver section of Fig. 9 has hardware analogous to the transmitter section. A receiver demodulator 102 receives a composite signal from an antenna 104, demodulates it into a baseband frequency, and converts the serial signal into parallel signal samples or blocks of N bits. As described above, the signal samples may be complex due to in-phase and quadrature components. The signal blocks are combined in a specialized N-sample multiplier 106 with a suitably selected encryption mask retrieved from a recipient encryption mask storage device 108.

In the specialized N sample multiplier 106, each of the N parallel samples provided by the receiver / demodulator 102 is multiplied by a +1 or -1, depending on the encryption mask provided by the storage device 108. Thus, a sample is either passed through as it is or negated. One way to perform this multiplication is to exclusively-OR each bit of the digital sample with the appropriate encryption mask bit. For example, if the first of the N digital samples is 1011 and the first encryption mask bit is -1, the first of the N output samples would be 0100.

The decrypted signal produced by the multiplier 106 is decoded in an orthogonal block decoder 110 using, for example, the subtractive demodulation procedure described above. The decoded signal is decrypted by combining the appropriate cipher key K1 generated by a receiver sequence generator 112 with the decoded signal in an M-bit adder 114. Error correction codes are removed from the decrypted digital information in a source decoder 116, and the result is converted to speech.

In FIG. 9, the RAKE combiner described above with respect to FIG. 8 would be part of the orthogonal block decoder 110. Data corresponding to different times of arrival would be provided by the receiver / demodulator 102.

The encryption mask used in decrypting the received composite signal is provided in part by the code key K2 provided to the receiver sequence generator 112. The code key K2 is combined in an Nt-bit adder 118 with an access code selected by the receiver system from a list of unused access codes designated by an information broadcast by the system. The Nt-bit adder 118 generates the Nt-bit address which is applied to the receiver encryption mask memory 108.

The receiver sequence generator 112 is arranged to generate the same pseudorandom Nt-bit sequence for all memory accesses by ensuring that the sequences depend only on the code key K2, which is the same for all encryption-mask memory accesses. The pseudorandom sequence for a particular memory access is generated by adding an offset to the access, modulo the number of stored encryption masks, as described above. This process is described below in another way.

Each mobile station in a particular group is preferably associated with a unique encryption mask. If there are four encryption masks M0, M1, M2 and M3, they may be assigned four signals S0, S1, S2, S3 as follows:

S0 gets M0

S1 receives M1

S2 receives M2

S3 gets M3

Alternatively, they could be associated with any of the other 23 other types, such as:

S0 receives M2

S1 receives M0

S2 receives M3

S3 receives M1

It is desirable to pseudorandomly alter the association between these different types while still guaranteeing that a signal will receive a unique assignment. A first method of making the allocation random is to generate in each mobile station transceiver a pseudorandom number, using the same recipe, so that they all receive the same pseudorandom number as a result. This number is z. B. 3. Then each mobile station transceiver adds a different offset, e.g. For example, its own signal number, to this same pseudorandom number, so signal S0 adds 0 to 3, giving 3 (M3), signal S1 adds 1 to 3, giving 4, which is modulated by modulo-4 to 0 (M0 ), signal S2 adds 2 to 3, giving 5, which is reduced to (M1) by modulo-4 processing, and signal S3 adds 3 to 3, giving 6, which is modulated by modulo-4 to 2 (M2 ) is reduced. When starting with other pseudorandom numbers 0-2, the possible mappings are:

These are just four of the 24 possible ways in which codes could have been assigned to these signals.

A second method of randomizing the mapping may also be used. This involves generating a second pseudorandom number that is modulo-added to the offset, the first pseudorandom number (which is the same as the mask number associated with above).

A bitwise modulo-2 addition can be chosen to illustrate the effect of this. The four possible 2-bit patterns 00, 01, 10 ,. 11 can thus be bit-modulo-2 added to the addresses (mask numbers) of the encryption masks from above, resulting in the following possible associations:

For example, to create the eighth column from the fourth column, one must add bitwise 01 modulo-2 to the binary representation of the mask number in the fourth column. Thus, for signal S0, 11 + 01 = 10 modulo-2, so that S0 obtains M2, while for signal 1.00 + 01 = 01, modulo-2, so that S1 receives M1, and for signal S2, is 01 + 01 = 00 modulo-2, so that S2 yields M0, and for signal S3, 10 + 01 = 11 modulo-2, so that S3 obtains M3, etc.

Some of these patterns generated with two pseudorandom numbers are the same as the patterns generated with a pseudorandom number, but the number of different patterns has increased from four to eight.

A third method to randomize the allocation is to use more bits from the pseudo-random number generator to control a permutation of the address bits. In the above, the only other permutation is obtained by reversing the order of the address bits, such that 0 maps to 0, 1 maps to 2, and vice versa, and 3 to 3, resulting in the following patterns:

For example, to create these 16 assignments from the previous 16 assignments you simply have to swap M1 and M2 everywhere. This creates another eight different patterns so that 16 of the possible 24 sets of assignments are now covered.

If a number of address bits is greater than two, it is apparent that there are a greater number of ways to randomize the selection, for example, by modifying the modulus of the arithmetic used in adding the offset, or the first pseudo Random number, and / or the second pseudorandom number.

It is understood that an encryption engine generates pseudo-random numbers in accordance with a recipe that depends on a secret code or key that is normally set for the length of a message or longer. However, the pseudorandom stream still changes during the message. The sequence of pseudorandom numbers generated by the cipher machine is commonly referred to as the "keystream", and the secret code that defines the recipe for generating the keystream is called "key", "key variable", or "cipher variable". The part of the machine that generates a keystream for the key is called the "key generator". This differs from some other machines that generate pseudorandom, secret keys that code the cipher machine. To avoid confusion, this other machine would not be called a "key generator", but a "key management unit". Keys generated by a key management unit may be communicated to an encryption engine and then initiated electronically using a "filling gun".

Sometimes, in cellular systems, the key used to encrypt a communication is only used for that one communication. He is sometimes called the "communication key" or "conversation variable". Such a temporary key is generated by mixing the specified key with a random number transmitted from one party to another, e.g. From the base (network) to the mobile station. This is not desirable in the case of the pseudo-random generator that drives an encryption mask selection because it must generate the same sequence, before the offsets, in all stations. However, the method of generating a temporary communication key to the pseudorandom number generator that ciphers the source encoded information prior to CDMA spreading could be well applied.

Another simple example is useful in illustrating how cyclic pseudo-random encryption mask addresses can be generated. If there are five encryption masks, labeled (M0, ..., M4), a 3-bit address (N1 = 3) can be used to select one of the five. If, at some time, the receiver sequence generator 112 produces an offset of two, an access code of zero is offset by two, resulting in the selection of an encryption mask numbered 2 (M2). Alternatively, an access code of 3 is offset by an encryption mask address of 5. Due to the modulo-5 condition, since only five encryption masks are stored, the counter number 5 is actually reset to counter 0, so that access 3 results in a mask address 0 (M0). In the same way, access 1 is set to address 3 (M3), access 2 is set to address 4 (M4), and access 4 is set to address 6, which is reset to 1 (M1) due to modulo-5 Condition. Of course, the offset number changes pseudo-randomly, so that the addresses vary pseudorandomly.

If the number of encryption masks is a power of two, ie, 2N1, then Nt-bit adders 98, 118 may be either modulo-2N1 adders or bitwise modulo-2 (bitwise exclusive-OR) adders. If the number of encryption masks is a composite number (a product of factors, some or all of which may be the same or different) L = n1 * n2 * n3 ... Then, adder 98 may be either a modulo-L adder or a combination of modulo-n1, modulo-n2, modulo-n3, ... adders, separated for each factor or root. Of course, it is much easier to generate pseudorandom sequences of numbers over a range that is a power of two.

From the above discussion, it can be seen that the use of encryption masks can be applied to control signals as well as to user signals. In fact, it is sometimes desirable to use the fixed set of encryption masks with optimal correlation properties only for control signals. The optimal correlation properties help to minimize interference between different control signals. In a cellular system, the correlation properties also help to minimize interference between control signals in the nearby cells. These control signals or channels include broadcast, paging, synchronization and pilot channels. The technique of using pseudorandom numbers to encipher the data or addresses of an encryption mask can not be used if the channel is a control channel.

It will be understood by those skilled in the art that the foregoing methods and functions may be practiced by suitably arranged general purpose digital signal processor circuits and components. However, specialized, application-specific integrated circuits (ASICs) are preferable for better efficiency.

While the specific embodiments of the present invention have been described and illustrated, it should be understood that the invention is not so limited since modifications may be made by those skilled in the art.