METHODS AND APPARATUS FOR ENCODING AND DECODING
DATA
The present invention relates to methods and apparatus for encoding and decoding data. More particularly, it relates to the encoding and decoding of data using spreading codes such as Walsh-Hadamard codes or the like to enable multiple channels of data to be encoded into a single expanded bandwidth, and to be selectively decoded upon reception.
Code division multiplexing allows multiple signals to be transmitted in a common bandwidth over a common transmission path, and to be selectively extracted and decoded, to enable a particular user to receive data intended for that user without receiving data intended for another user. In particular, spreading codes such as Walsh-Hadamard codes may be employed, as illustrated in Fig. 1. In Fig. 1, d
n ω 10 represents the time variance of a data signal to be transmitted on a particular code, i. One or more from a set of Walsh-Hadamard codes, C
n 1*1 12, is allocated to the user i. The corresponding time-variance of the code is illustrated at c
m w 12 in Fig. 1. The code c
m is composed of a number of chips 14, as is known in the art. The number of chips in a code is also known as the spreading factor (SF) of that code. The data signal d
n (l 10 is then multiplied by the Walsh-Hadamard code c
m (l) 12, to produce a spread spectrum data signal
16, illustrated in Fig. 1. This signal 16 is then modulated onto a carrier signal exp(jωt) by multiplication, to produce a modulated spread-spectrum data signal Σd
n (l).c
m (l).g(t-mT
c).exp(jωt) 20, as illustrated in Fig. 1. In the preceding expression, g() represents a pulse shaping function, while t represents time and T
c represents the chip period. As may be seen from the figure, the effect of the modulation is to reverse the phase of the carrier signal at every level transition 22 of the spread spectrum data signal.
Walsh-Hadamard codes have the property of being orthogonal, that is, if the coded (spread spectrum) data signal dn (l).cm w 16 is further multiplied by the Walsh- Hadamard code cm (l), de-spreading takes place and the original data signal dn (l 10 is obtained. However, another coded (spread spectrum) data signal dn 0).cm®, intended for a different user j, and using a different code c^* will return a zero value when multiplied by the Walsh-Hadamard code cm (l).
Accordingly, when the modulated signal dn (l*l.cm (l).exp(jωt) 20 is received at the user, it is first demodulated by multiplication by exp(-jωt) to reconstruct the spread spectrum data signal dn ω.cm w 16, which is then de-spread by multiplication by cm (l) to reproduce the data signal dn w 10. Fig. 2 shows an example of a multi-user code-division multiplex system, in which numerous users will receive their own specific data. Data dn (l), dn® 10 for each user i, j is encoded in a corresponding spreading modulator 24, and the resultant signals dn (l).cm (l , dn ()).cm 0) 16 may be summed together at a summer 26 before modulation by a modulator 28 before transmission as transmit signal tx. A user i will then receive the sum of the data signals rx, demodulate the summed data signals in demodulator 30 and then multiply the summed data signals by the corresponding Walsh-Hadamard code cm (l) in a de-spreader 32 corresponding to the spreading modulator 24, then to a summer which sums the returned values for all chips in the code, thereby to reconstruct the original data signal dn(l) 10 at the output for that user, but will return a zero value for all other data signals dn .
Often it is necessary to transmit multiple channels, where each channel has its own data source, and the spreading process is performed for different channels using a different Walsh-Hadamard code. In some circumstances the data for each channel may not be independent so that the data symbols from each source are similar for long periods. This may occur for example in a multi-cast scenario, where each channel is essentially sending the same data. It may also occur when for example data sources produce long sequences of the same data symbol. With multiple sources of this type the same data symbols will occur at the same time on different channels. With spreading performed using Walsh-Hadamard codes the result causes a high peak transmit power. At any such peak value of such transmission, a very large power demand is placed on the transmitter, possibly causing compression of the signal to be transmitted, leading to errors in reproduction. Alternatively, or in addition, degradation of the received signal may occur in the receiver due to the very high magnitude of the received signal. The table shown in Figure 3 gives the sum of different numbers of Walsh-
Hadamard codes of length 16, that is, the spreading factor SF has a value of 16.
In the example set of Walsh-Hadamard codes used to generate the sequences of Fig. 3, the rows represent sequential time periods, indicated by the arrow t, each row corresponding to one chip length within the spreading code which is preferably a Walsh Hadamard code, see for example cm (l) in Fig. 1. The first row, for example, shows the sum of the values of all 8, 12 or 16 corresponding Walsh-Hadamard codes during the first chip. The second row shows the sum of their values during the second chip, and so on for the other rows. The illustrated example is a worst- case scenario illustrating the signal strength (voltage) transmitted if a same data signal is transmitted to each of the 8, 12 or 16 users. The present invention aims to reduce such peaks of power and the attendant drawbacks, while remaining within the Walsh-Hadamard coding scheme or other selected orthogonal spreading factors.
According to an aspect of the present invention, a phase shift is applied to the spread spectrum (coded) data signal tin (l).cm (l . In accordance with the present invention, there is provided a method for encoding data, comprising the steps of: (i) generating a respective data signal for each of a plurality of users; (ii) coding (24) each of the data signals with a respective orthogonal spreading code to produce respective encoded data signals; and (iii) summing the encoded data signals to produce a total encoded data signal, the method further comprising the step of applying a phase shift to one of the data signal, the encoded data signal and the total encoded data signal.
The step of applying a phase shift may comprise multiplication of the corresponding term by a term of the form exp(jφ), between steps (i) and (ii) or between steps (ii) and (iii). Such methods according to the present invention may comprise the steps of:
(i) receiving an encoded signal comprising a summation of coded data signals for each of a plurality of users; and (ii) extracting and decoding a respective one of the data signals by application of a respective orthogonal spreading code to produce a respective data signal. The method may further comprise the step of applying a phase shift to one of the data signal and the encoded signal. In such a method, the step of applying a phase shift may comprise multiplication of the corresponding term by a term of the form exp(-jφ), before or after step (ii).
The orthogonal spreading code may comprise a plurality of chips, and the method may further comprise summing the resultant respective data signal, to produce an output data signal.
The present invention also provides data encoding apparatus comprising: (i) a data encoder for encoding a respective data signal with a respective orthogonal spreading code to produce respective encoded data signal ; and (ii) a complex summer for summing the encoded data signals to produce a total encoded data signal, characterised in that the apparatus further comprises a phase shift element for applying a phase shift to one of the data signal, the encoded data signal and the total encoded data signal.
The phase shift element may comprise a multiplier arranged to multiply the corresponding term by a term of the form exp(jφ), any such multiplier preferably being located in the signal path before or after the data encoder.
The present invention also provides data decoding apparatus comprising a data decoder for decoding a respective data signal from a combined data signal by application of a respective orthogonal spreading code to produce a respective decoded data signal. The apparatus further comprises a phase shift element arranged to apply a phase shift to one of the data signal and the respective decoded signal. The phase shift element may be arranged in the signal path before or after the data decoder, to multiply the corresponding term by a term of the form exp(-jφ).
The orthogonal spreading code may comprise a plurality of chips, and the apparatus may further comprise a summer arranged to sum the resultant respective data signal, to produce an output data signal. Each orthogonal spreading code may consist of one of a set of Walsh-
Hadamard codes.
The above, and further, objects, characteristics and advantages of the present invention will become more apparent with reference to the following description of certain embodiments thereof, given by way of examples only, with reference to the accompanying drawings in which:
Fig. 1 shows examples of signals used in an encoding method of the prior art;
Fig. 2 shows an example of data encoding and decoding apparatus according to the prior art; Fig. 3 shows transmit signal strength, voltage, values for multicast spreading code encoded signals according to the prior art;
Fig. 4 shows an embodiment of data encoding and decoding apparatus according to the present invention; and
Fig. 5 shows transmit signal strength, voltage, values for multicast spreading code encoded signals according to' the present invention.
According to an aspect of the present invention, a phase shift φi is applied to the spread spectrum (coded) data signal dn (l).crn (l) 16. This may conveniently be regarded as a phase shift in the associated Walsh-Hadamard or other code.
For example, the known modulated, spread spectrum (coded) data signal tx may be represented by the simplified expression: tx=Re[Σm dn (i).cm (i).g(t-mTc).expαωt)], or by the full expression:
Re ∑di?∑c_?8(! -mTe -nSFTc)exV(jωt)
where SF is the spreading factor. The application of a phase shift φi according to the present invention gives rise to a transmitted modulated, spread spectrum (coded) data signal tx' which may be represented by the simplified expression: tx'=Re[Σm dn ( ).cm ω.g(t-mTc).exp(jφ .exp(jωt)]., or by the complete expression:
Re ∑ J X c» g(t - mTc - nSFTc ) eκp jφ, ) exp(;ωt)
The effect may conveniently be regarded as a phase shift in the associated Walsh-Hadamard code. The phase shifted Walsh-Hadamard codes retain their orthogonal characteristics, that is, that in the receiver, by multiplying the received signal by the corresponding phase-shifted Walsh-Hadamard code, the original data
signal may be retrieved. On reception, the phase shift of the Walsh-Hadamard code is reversed, that is, to retrieve a data signal encoded with a Walsh-Hadamard code of cm (l).exp(jφi), the received signal is multiplied by cm (1*1.exp(-jφ*).
Fig. 4 illustrates one possible embodiment of the present invention. Features common with those illustrated in Fig. 2 have common reference numerals. According to this embodiment of the invention, data signal dn (l 10 to be transmitted is multiplied by the corresponding Walsh-Hadamard code c ^ at spreading modulator 24, as in the prior art, but is then further multiplied at complex multiplier 40 by a phase shift term, exp(jφi). This operation may be correspondingly replicated for the other data signals dn ()) to be transmitted. The phase shifted spread spectrum (coded) data signals dn (l).cm (l-l.exp(jφ*) etc. 42 are then summed at a complex summer 26 before being modulated at modulator 28 by multiplication by the carrier signal expQ'ωt) to produce signal tx' for transmission. The signal tx' may accordingly be expressed as dn ω.cm (l .exp(jφi).exp(jωt). When the phase shift φ; is applied, every chip in a certain code is multiplied by a same value exp(jφi). However, each code uses a value of φ which is preferably different from that used by all other codes in use. It is essential, however, that the phase shift φ, applied must be known by the receiver to allow the appropriate decoding at the receiver. The transmitted signal tx' then propagates along a suitable propagation path, e.g. over the air, until it arrives as a received signal rx' at a receiver of user i. The received signal rx' is first demodulated at demodulator 30 by multiplication by exp(-jωt), then is decoded at de-spreader 32 by further multiplication by the Walsh- Hadamard code cm (l). According to an aspect of this embodiment of the invention, the resultant signal is then subjected to a phase shift opposite to that applied to the transmission signal, by multiplication by exp(-jφj) by complex multiplication at complex multiplier 44. The resultant signal is fed to a complex summer 34, where the resultant signals of each chip of the spreading (Walsh-Hadamard) code are
< summed, to produce an output data signal d^ corresponding to the transmitted data signal dn (i).
One advantage of the encoding and decoding method and apparatus of the present invention will now be described. Fig. 3, already described above, illustrates the time-variant sum of different numbers of Walsh-Hadamard codes of length 16. Each row represents the time occupied by a particular chip. For example, if all 16 codes are used, a very high magnitude occurs at the first code. This may translate into a very high signal voltage at the receiver, which may cause distortion in the received signal, or may mean that a more costly receiver is necessary, to cope with the high voltage signals. Transmission of such high voltage signals may also lead to distortion of the transmitted signals in the transmitter. As shown in Fig. 3, selection of a subset of, say 8 or 12 of the 16 codes leads to a more dispersed power output but there is still a high voltage signal peak at the beginning.
Fig. 5 shows an example of signal strength values for sums of Walsh- Hadamard codes corresponding to those shown in Fig. 3, but having a phase offset applied, according to the present invention. Again, the various rows represent the sum of the values of 8, 12 or all 16 corresponding Walsh-Hadamard codes during the respective chip. As can be clearly seen from the table of Fig. 5, the signal strength (voltage) to be transmitted is much more evenly distributed over the length of the spreading code (Walsh-Hadamard code). This significantly reduces the impact of any signal strength peaks caused by same data being transmitted to multiple or all users.
In certain preferred embodiments of the present invention, the phase shift applied to the spreading code may be selected as follows.
The phase shift φ* may be selected to be pj.2π/SF, where SF is the spreading factor, that is, the number of chips included within the spreading code, and pi is a member of a selected permutation of the integer set [ 1 ,SF] .
Taking an example, the integer set [1,4] consists of the integers 1, 2, 3 and 4. [2 ,3 , 1 ,4] is a permutation of the integer set [ 1 ,4] .
This leads to the following expression for the value c'm (l) of the phase shifted version of the spreading code i, as compared to the prior art, un-phase-shifted spreading code cm w: c'm ω = cm (i) exp(j.pi.2π/SF).
In certain particularly preferred embodiments, a constraint is placed on the acceptable values of pi, limiting them to values q;, such that q; *= 4 ;. The values of Pi and qi may only take integer values. The values of pi are preferably integer fractions of SF. This leads to the following expression for the value c'm w of the phase shifted encoded data symbol of spreading code i, as compared to the prior art, un-phase-shifted spreading code i, cm ω: c'm (i) = cm (i) exp(j.qi.π/2) When the phase shift is applied, every chip in a certain code is multiplied by a same value. In the above examples, this value is fixed by selection of the value of pi or qj. However, each code uses a value of φ, fixed by pj or q; in the above examples, which is preferably different from that used by all other codes in use.
While the present invention has been described with reference to a limited number of particular embodiments, those skilled in the art will appreciate that numerous modifications and amendments may be made within the scope of the present invention. For example, while the embodiments have been discussed with respect to Walsh-Hadamard spreading codes of particular chip lengths, other types of orthogonal code and other chip lengths may be used without departing from the invention. Furthermore, while the transmit apparatus shown in Fig. 4 has the phase shift exp(jφi) 40 applied after spreading (Walsh-Hadamard) coding 24, the phase shift 40 may alternatively be applied prior to spreading (Walsh-Hadamard) coding. While the receive apparatus shown in Fig. 4 has the phase shift exp(-jφ) 44 applied after spreading (Walsh-Hadamard) decoding 32, the phase shift may alternatively be applied prior to spreading (Walsh-Hadamard) decoding, or even prior to demultiplexing 30.