Note: Descriptions are shown in the official language in which they were submitted.
CA 02300064 2000-02-11
GR 97 P 2148 P
Description
Method and device for generating a random number. sequence
for carrier frequencies of a mobile radio transmission
The present invention relates to a method and a
device for generating a random number sequence which is
converted into carrier frequencies for a mobile radio
transmission.
The so-called frequency hopping spread spectrum
is a known method for transmitting data on a plurality of
carrier frequencies. A frequency hopping spread spectrum
system is in this case to be understood as meaning a
system in which, for the purpose of radio transmission of
data, a multiplicity of carrier frequencies are provided
and the currently used carrier frequency is periodically
changed. In a time division multiplex (TDMA) system, in
particular, the carrier frequency may be changed after
each time slot or time frame of the time division multi-
plex transmission (or multiples thereof). Such a fre-
quency hopping spread spectrum system has advantages to
the extant that the energy of the entire radio trans-
mission is distributed over all the carrier frequencies.
This is important particularly when a generally available
frequency band, such as the 2.4 Gfiz ISM (Industrial,
Scientific, Medical) band, for example, is used. For the
use of this frequency band, an upper limit for the
maximum energy occurring per carrier frequency is defined
in accordance with the relevant specifications ("FCC part
15", Federal Communications Commission), in order to
minimize interference of other subscribers. Furthermore,
it is prescribed by the specification "FCC part:l5" that
at least 75 different carrier frequencies must be pro-
vided.
A further advantage of the frequency hopping
spread spectrum system that may be mentioned is that the
system becomes more insensitive to interference as a
result of the provision of a large number of carrier
frequencies. Furthermore, the security of the system
CA 02300064 2000-02-11
GR 97 P 2148 P - 2 -
against eavesdropping by third parties is increased since
the third party generally does not know the carrier
frequency to which a change is made after a certain
period of time.
The sequence of carrier .frequencies which are
used one after the other for transmission is determined
by an algorithm. Such an algorithm is implemented in an
identical manner in the fixed station and also in each
mobile station of the mobile radio transmission.
Consequently, if a mobile part is synchronized with the
associated fixed station, the mobile part and the fixed
station will perform the carrier frequency change pre-
determined by the sequence of the (identical) algorithm.
in synchronism with one another.
The algorithm should ensure that each carrier
frequency is used in the same number of instances and for
the same length in a certain period of time.
The present invention therefore has the object of
providing a method and a device for generating a random
number sequence for carrier frequencies of a mobile radio
transmission which make it possible to realize a random
number algorithm in a simple manner.
This object is achieved by means of the features
of the independent claims. The dependent claims develop
the central concept of the invention in a particularly
advantageous manner.
The invention, then, provides a method for
generating. a random number sequence, the random number
sequence being converted into carrier frequencies for a
mobile radio transmission. In this case, first of all a
shift register with n bits is provided. This is followed
by feedback modulo-2 addition of one bit of the shift
register with one or more other bits of the shift regis-
ter. The register content of the shift register is then
shifted cyclically by one bit. The result of the modulo-2
addition is then inserted into the bit position freed by
the shifting operation. The content of the shift register
is cyclically converted into a~carrier frequency fx for
a mobile radio transmission. Consequently, as a result of
CA 02300064 2000-02-11
GR 97 P 2148 P - 3 -
the feedback of the shift register, a random number
sequence having a maximum periodicity (depending on the
type of feedback) of 2n-1, where n is the number of bits
of the shift register, is created in a particularly
simple manner.
Different sequences can be generated by altering
the feedback, that is to say by altering the shift
register bits which are used for the modulo-2 addition.
For example, 2048 different sequences having a maximum
length of (2n-1) can be generated given a shift register
with 16 bits.
The step of converting the content of the shift
register into carrier frequencies for a mobile radio.
transmission has the addition of the content of the shift
register to the current carrier frequency. Afterwards, it
is decided whether the result of the addition is greater
than the number of carrier frequencies that are present.
If the decision is positive, the result of the addition
is then decremented by the number of carrier frequencies
that are present until the decision turns out negative,
that is to say until the result of the addition is no
longer greater than the number of carrier frequencies
that are present. If the decision turns out negative, the
result of the addition is used as the next carrier
frequency. Subsequently, the shift register is shifted by
one bit and the sequence starts afresh.
The invention furthermore provides a device for
converting a random number sequence into carrier fre-
quencies fx for a mobile radio transmission. This device
has a shift register with n bits. An addition device fo;~.~
the modulo-2 addition of one bit of the shift register
with one or more other bits of the shift register after
the manner of a feedback is furthermore provided. After
the addition, the register content is shifted cyclically
by one bit, preferably to the right. The result of the
addition device is then inserted into the bit position
freed by the shifting operation. A device for converting
the content of the shift register cyclically into a
carrier frequency for a mobile radio transmission is
CA 02300064 2000-02-11
GR 97 P 2148 P - 4 -
furthermore provided.
The nature of the feedback, that is to say the
bits used for the modulo-2 addition and also the number
of these bits, can be altered in order to generate
different sequences.
The device for converting the content of the
shift register into carrier frequencies furthermore has
means for adding the content of the shift register to the
current carrier frequency. Furthermore, means for decid-
ing whether the result of the addition is greater than
the number of carrier frequencies that are present are
provided. In this case, if the decision is positive, the
result of the addition is decreased by the number of.
carrier frequencies that are present until the decision
turns out negative, that is to say until the result of
the addition is no longer greater than the number of
carrier frequencies that are present. If the decision
turns out negative, the result of the addition is used as
the next carrier frequency and the shift register is then
shifted cyclically by one position to the right.
The shift register preferably has 16 bits.
The shift register can be implemented in an 8-bit
or 16-bit processor.
The invention furthermore relates to a mobile
radio transceiver having a device of the abovementioned
type.
The invention will now be explained in more
detail using an exemplary embodiment and with reference
to the accompanying drawings, in which:
Figure 1 shows a mobile radio transmission system
having a fixed station according to the inven-
tion,
Figure 2 shows a time frame of a data trans
mission standard of the kind that can be employed
in the case of the present invention,
Figure 3 shows, in detail, the internal structure
of a fixed station according to the invention,
and
Figure 4a shows a shift register of the kind used
CA 02300064 2000-02-11
GR 97 P 2148 P - 5 -
in the present invention.
Figure 4b shows the content of the shift register
for the various clock cycles of a period, and
Figure 5 shows a flow diagram for the conversion
of the random number sequence into carrier fre-
quencies.
Referring to Figure 1, it is intended first of
all to give an explanation of the general structure of a
mobile radio transmission. As is generally customary, the
arrangement for the radio transmission of data has a
fixed station 1 and a plurality of mobile parts (mobile
stations), cordless telephones 2, 3 ... The fixed station
1 is connected by a terminal line 10 to the fixed net-
work. For the purpose of communication, it is possible to
provide an interface device (not illustrated) between the
fixed station 1 and the terminal line 10. The fixed
station 1 has an antenna 6 by means of which, for
example, a communication with the mobile part 2 takes
place via a first radio transmission path 8 or a communi-
cation with the mobile part 3 takes place via a second
radio transmission path 9. The mobile parts 2, 3 ... each
have an antenna 7 for receiving and/or for transmitting
data. Figure 1 diagrammatically illustrates the state in
which the fixed station 1 is actively communicating with
the mobile part 2 and, consequently, is exchanging data.
The mobile part 3, on the other hand, is in the so-called
idle locked mode, in which it Waits in standby-like
fashion for a call from the fixed station 1. In this
state, the mobile part 3 is not communicating with the
fixed station 1, but rather it receives only periodically
the data for example of a time slot from the fixed
station, in order to be able to be resynchronized with
the carrier frequencies fx.
The internal structure of the fixed station 1 is
illustrated diagrammatically in Figure 1. The voice
information data are fed to an RF module 4, which is
driven by a carrier frequency sequence unit. The exact
structure of a fixed station 1 according to the invention
will be described later.
CA 02300064 2000-02-11
GR 97 P 2148 P - 6 -
Referring to Figure 2, it is now intended to give
an explanation of a transmission standard of the kind
that can be used in the case of the present invention. As
is evident from Figure 2, data are transmitted
chronologically successively on a plurality of carrier
frequencies fx, ten of which are illustrated, in a
plurality of time slots, 24 time slots Zx in the case
illustrated, using a time division multiplex method TDMA
(Time Division Multiple Access) . In the case illustrated,
operation is in the duplex mode, that is to say after the
first twelve time slots Zx have been transmitted from the
fixed station l, a switch is made to reception, and the
fixed station 1 receives, in the opposite direction, the -
second twelve time slots (Z13 to Z24) from one or more
mobile stations.
If the so-called DECT standard is used for the
transmission, the time duration of a time frame is 10 ms,
and 24 time slots Zx are provided, namely twelve time
slots for transmission from the fixed station to mobile
parts and a further twelve time slots Zx for transmission
from the mobile parts to the fixed statiori. According to
the DECT standard, ten carrier frequencies fx between
1.88 GHz and 1.90 GHz are provided.
Of course, other frame structures can also be
used in the present invention, for example those having
a number of time slots that is halved in comparison with
the DECT standard.
However, the present invention is also used in
particular for transmissions in the so-called 2.4 GHz ISM
(Industrial, Scientific, Medical) frequency band. The
generally accessible ISM frequency band has a bandwidth
of 83.5 MHz. In accordance with the FCC part 15, at least
75 carrier frequencies fx must be distributed over these
83.5 MHz. What is particularly advantageous is a division
of the bandwidth of 83.5 MHz between 96 carrier fre-
quencies, i.e. a channel spacing of 864 kHz. The above-
mentioned frequency bands and standards are cited purely
as an example. The only fundamental precondition for
applicability of the present invention is that a so-
CA 02300064 2000-02-11
GR 97 P 2148 P - 7 -
called frequency hopping spread spectrum is used, i.e.
that a plurality of carrier frequencies are available,
and that the carrier frequency selected for transmission
is periodically changed. For such a change, it is advan-
tageous if the data are transmitted in time slots Zx
(time division multiplex method). The DECT standard is
therefore suitable, for example, as well as any other
modified standard based on this DECT staadard.
Referring to Figure 3, it is now intended to give
a more detailed explanation of the internal structure of
a fixed station 1 according to the invention. As can be
seen in Figure 3. information data are fed to the RF
module 4 when transmission is to be effected from the -
fixed station 1 to a mobile part 2, 3 ... by means of the
antenna 6, and information data are output from the RF
module 4 when data from mobile parts are received. The RF
module 4 modulates the digital encoded information data
onto a carrier frequency fx. The carrier frequency fx
that is currently to be used is in this case predeter-
mined by a carrier frequency sequence unit, which is
designated in general by 20. Provided in the carrier
frequency sequence unit 20 is a detection device 24, to
which the demodulated signal from the RF module 4 is fed.
Interference in this context means that either inter-
ference in the actual sense or seizure by another trans-
mitter is present. Interference in the sense of the
present description can therefore be detected by
demodulating a received signal on a carrier frequency and
detecting whether or not a signal level is present on
this carrier frequency. In this case, a carrier frequency
which is subjected to interference is therefore a carrier
frequency onto which a signal which exceeds a specific
threshold value is modulated.
Interference in the actual sense can be detected
by the occurrence of CRC errors or burst losses.
The detection device 24 therefore uses the
demodulated signal from the RF module 4 to determine how
high the signal component modulated onto a specific
carrier frequency fx is. If the signal component detected
CA 02300064 2000-02-11
GR 97 P 2148 P - 8 -
lies above a predetermined limit value or if one of the
abovementioned errors has occurred, the detection device
24 passes an interference detection signal to an
inhibit/enable unit 21. Depending on the interference-
source detection signal from the detection device 24, the
inhibit/enable unit 21 passes an inhibit/enable informa-
tion item to a processor 23. This inhibit/enable informs-
tion item indicates which of the carrier frequencies fx
are inhibited or enabled again on account of the detec-
tion of interference by the detection device 24, as will
be explained later.
In other words, the detection device 24 and the
inhibit/enable device 21 provide an independent procedure
by means of which frequencies subjected to interference
can be inhibited and enabled again. In addition to the
inhibit/enable information items from the inhibit/enable
unit 21, a sequence from a random number generator 22 is
fed to the processor 23. On the basis of a random
algorithm implicit in it, the random number generator 22
generates a randomly distributed sequence of carrier
frequency values within the predetermined frequency band.
The random number generator 22 consequently carries out
a procedure which is independent of the procedure of
frequency inhibition for the case of interference.
Finally, the processor 23 passes to the RF module 4 a
drive signal which predetermines for the RF module 4 the
carrier frequency value that is to be used.
As is illustrated in Figure 3 by an arrow from
the processor 23 to the random number generator 22, the
processor 23 predetermines how many different values the
said random number generator is to generate. This number
of values to be generated corresponds- to the number of
carrier frequencies to be generated, which, for example
in accordance with the US specification "FCC part 15",
must be at least 75.
In particular in a mobile part, the processor 23
furthermore predetermines for the random number generator
22 a start value for the algorithm thereof . This start
value is communicated to the mobile station by the fixed
CA 02300064 2000-02-11
GR 97 P 2148 P - 9 -
station for the purpose of synchronization, which is
achieved by virtue of the fact that the same start value
and the same algorithm are used. Given the same start
value and the same algorithm, the same sequences are
compulsorily generated by the fixed station and the
mobile part.
The fixed station 1 is the master during fre-
quency allocation, i.e. at the beginning of a connection
set-up, the random number generator in a mobile part is
initialized with the state of the random number generator
22 of the fixed station 1. The random number generators
in the mobile part 2, 3 ... and in the fixed station 1
then generate the same carrier frequency values.
synchronously in timing and autonomously of one another.
The procedure for frequency inhibition which is
carried out by the detection device 24 and the
inhibit/enable unit 21 uses a unidirectional protocol on
the radio interface during the entire connection time
between the fixed station 1 and a mobile part 2, 3 ... If
the detection device 24 finds one of the possible fre-
quencies fx from the fixed station 1 to be subjected to
interference, then the fixed station 1 therefore coa~uni-
cates to all mobile parts with which it is operating
connections that this frequency which is subjected to
interference, if it is generated by the sequence of the
random number generator, must be replaced by a different
carrier frequency that is not detected as being subjected
to interference. The random number generator 22 is not
influenced by the frequency inhibition. This frequency
inhibition is cancelled again by the inhibit/enable unit
21 when the inhibited carrier frequency is again suitable
for transmission, or when it has been inhibited for
longer than a previously defined time.
Referring to Figures 4a and 4b, it is now
intended to give an explanation of how the random numbers
can be generated by an algorithm which can be implemented
in a simple manner in a processor, and, at the same time,
how the computing time required can be kept short.
As is evident in Figure 4a, the basis of the
CA 02300064 2000-02-11
GR 97 P 2148 P - 10 -
algorithm is a feedback shift register 25 having the
length x, where the length x is equal to 4 in the example
illustrated. The feedback structure of the register is
I==f1,4~. In accordance with the example illustrated,
this means that in the sense of a feedback, the first bit
is combined with the fourth bit by modulo-2 addition 26
and the result of this modulo-2 addition 26 is inserted
at the position of the most significant bit, this posi-
tion becoming free as a result of the register content
being shifted by one bit to the right.
At the beginning, the shift register 25 is loaded
with the value 0001, as illustrated. For each new value,
the contents of the shift register 25 are shifted by one
bit to the right, the left-hand bit being recalculated
each time in the manner illustrated. The aature of the
feedback, that is to say the modulo-2 addition of the
left-hand bit with the extreme right-hand bit of the
shift register 25 in the present example, can be altered.
Consequently, different sequences of varying length can
be generated by altering the nature of the feedback 27
and the number of bits that are fed back. Depending on
the feedback, the sequence length, that is to say the
periodicity according to which the sequence generated is
periodically repeated, is a maximum of 2n-l, where n is
the number of bits of the shift register 25. In the case
of the arrangement illustrated (n=4, Ir~l,4~), the
sequence length is thus equal to 15 (and thus a maximum
for a four-bit register), that is to say after 15 gener-
ated values, the generated values are repeated period-
ically. The value 0 is not generated in feedback shift
registers. Figure 4b illustrates the content of the shift
register 25 for the corresponding clock cycles of a
period for the example illustrated in Figure 4a.
Figure 4a should be understood in particular as
being an example of the generation of random numbers by
a feedback shift register. In practice, a shift register
with 16 bits can be used, for example. Such a shift
register can be easily implemented in 8- and 16-bit
processors. As a result of the various possible options
CA 02300064 2000-02-11
GR 97 P 2148 P - 11 -
for the feedback 27, it is possible to generate 2048
different sequences given a 16-bit shift register. The
sequence length is a maximum of 216-1=65535 given a 16-
bit shift register. Consequently, if a carrier frequency
corresponding to a value of the random number sequence
generated is maintained for the duration of a frame of
ms, for example, the time duration of the period is
65535 x 10 ms = 10.9 min. This means that a sequence of
maximum leagth is repeated only every 10.9 min given a
10 16-bit register.
The use of a random number generator having the
algorithm illustrated furthermore has the advantage that
it is possible to generate different carrier frequency.
hopping sequences by means of feedbacks which can be
defined in a simple manner.
In the case of a shift register with 16 bits, the
number of possible values of the sequence of carrier
frequencies is 65535, as explained. However, the number
of actually used carrier frequencies may be significantly
smaller and, furthermore, variable. Consequently, the
carrier frequency cannot be obtained directly by a
conversion of the values of the random number sequence.
Figure 5 illustrates how the actually used
frequencies are obtained in an endless loop from the
content of the shift register 25. As is evident in Figure
5, first of all the frequency fxn_1 is set to 0. The
current content of the shift register 25 is then added
(28) to this value. Subsequently, a calculation is made
and it is decided whether the result of the addition
calculated in step 28 is greater than the number y of
useable carrier frequencies fx. If the result of this
decision 29 is positive, that is to say if the result of
the addition in step 28 is greater than the number y of
actually useable carrier frequencies fx, then this value
is decreased (30) by the value of the number y of useable
carrier frequencies. This decrease in the result of the
addition 28 by the number y of useable carrier fre-
quencies fx is carried out until the decision in step 29
yields a negative result, that is to say until the value
CA 02300064 2000-02-11
GR 97 P 2148 P - 12 -
fxn_1 is used as the carrier frequency of the next time
slot or time frame fx. Subsequently, the shift register
25 is shifted (32) further by one bit, for example to the
right. The procedure is thus ended and the sequence
returns to step 28.
The maximum number of used frequencies can be
adapted by altering the variable y.
Consequently, the invention enables the gener
ation of random numbers by means of an algorithm which
can be implemented in a simple manner in a processor. At
the same time, the computing time required is kept short.
CA 02300064 2000-02-11
GR 97 P 2148 P - 13 -
List of reference symbols
1: Fixed station
2: Mobile part
3: Mobile part
4: RF module
6: Antenna fixed station
7: Antenna mobile part
8: First radio transmission path
9: Second radio transmission path
10: Terminal line
20: Carrier frequency sequence unit
21: Inhibit/enable unit
22: Random number generator
23: Processor
24: Detection device
25: Shift register
26: Adder
27: Feedback
28: Addition
29: Decision
30: Decrease
31: Conversion
32: Shifting
fx: Carrier frequency
Rx: Frame
Zx: Time slot
