USOO7280580B1
`
`(12) Unlted States Patent
`(10) Patent No.:
`US 7,280,580 B1
`
`Haartsen
`(45) Date of Patent:
`Oct. 9, 2007
`
`(54) HOP SEQUENCE ADAPTATION IN A
`FREQUENCY-HOPPING COMMUNICATIONS
`SYSTEM
`
`5,832,026 A
`5,848,095 A
`5,870,391 A
`5,898,733 A
`
`11/1998 Li
`12/1998 Deutsch
`2/1999 Nago
`4/1999 Satyanarayana
`
`(75)
`
`Inventor:
`
`Jacobus C. Haartsen, Hardenberg (NL)
`
`............... 455/464
`6,480,721 B1* 11/2002 Sydon et al.
`FOREIGN PATENT DOCUMENTS
`
`(73) Assignee: Telefonaktlebolaget LM Ericsson
`(publ.), Stockholm (SE)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/418,562
`
`(22)
`
`Filed:
`
`Oct. 15, 1999
`
`(2006.01)
`
`(51)
`
`S
`
`(56)
`
`Int. Cl.
`H043 1/00
`375/138' 375/132
`(52) U S Cl
`’375/200
`58
`F'- Id f Cl""",fimt """S """"i'l'"
`(
`)
`1e 379202215120? 5131126311255/450464 370/338,
`’
`7
`’
`’
`’
`37’0/333 330’
`1 t
`f
`t'
`fil
`h h' t
`’
`1.
`e or comp e e searc
`ee app 1ca 1011
`1s ory.
`References Cited
`
`US PATENT DOCUMENTS
`4,023,103 A
`5/1977 Malm
`.......................... 375/132
`4,476,566 A * 10/1984 Dent
`4,606,040 A
`8/1986 David et 31.
`4,716,573 A * 12/1987 Bergstrom et a1.
`.......... 375/132
`
`4,780,885 A * 10/1988 Paul et al.
`............... 375/267
`5,307,348 A *
`4/1994 131104111012 et 3L
`233:21:; :
`$133451
`$11115 etafl' """"""""" 455/464
`5,515,369 A
`5/1996 Fltz eter .III et 31
`5:619:493 A
`4/1997 Ritz et ai.
`5,737,358 A
`4/1998 Ritz et 31.
`5,809,059 A
`9/1998 Souissi et a1.
`
`
`EP
`WO
`
`0182762 A1
`WO99/09671
`
`5/1986
`2/1999
`
`WO99/19993
`W0
`* cited by examiner
`
`4/1999
`
`.
`Primary Examiner%urt1s Odom
`(74) Attorney, Agent, or FirmiPotomac Patent Group
`PLLC
`
`(57)
`
`ABSTRACT
`
`.
`.
`.
`A hop channel 1s selected for use 1n a channel hopping
`communication system that
`includes a sequence of hop
`channels, wherein the sequence comprises a set of forbidden
`hop channels and a remaining set of allowable hop channels.
`Selection involves
`selecting a hop channel
`from the
`sequence as a function of a present phase. 1fthe selected hop
`channel is an allowable hop channel, then the selected hop
`channel is used for communication during the present phase.
`1f the selected hop channel is a forbidden hop channel, then
`a time-varying parameter is used to select a substitute hop
`channel from the set of allowable ho
`channels. The sub-
`.
`.
`P
`.
`.
`.
`stltute hOP channel 1s then used for communlcatlon (111mg
`the present phase. The time-varying parameter may, for
`example, be a clock value. With this strategy, the resultant
`hopping sequence is
`identical
`to the original hopping
`sequence whenever the original sequence calls for an allow-
`able hop channel. In all other cases, a substitute hop channel
`is dynamically selected from the set of allowable hop
`Channels
`
`42 Claims, 15 Drawing Sheets
`
`901
`
`DETERMINE PRESET HOP
`CHANNEL AS FUNCTION OF PHASE
`
`
` PRESENT HOP
`
`
`909
`
`
`
`903
`
`
`CHANNEL ALLOWABLE?
`
`N0
`
`|NDEX=MOD(CLOCK,N2)+BASE VALUE ‘/
`
`905
`
`907
`
`PRESENT HOP CHANNEL=TABLE(INDEX)
`
`
`
`I
`
`USE PRESENT HOP CHANNEL
`
`}’
`
`Ex. 1008 / Page 1 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 1 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 1 0f 15
`
`US 7,280,580 B1
`
`
`
`24802K?!Freq(MHz)
`
`ooéy‘WJ-iilm—flLj—I—LLF--‘-MH
`
`FIGUREI
`
`Ex. 1008 / Page 2 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 2 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 2 of 15
`
`US 7,280,580 B1
`
`8%£3.j«N23:09E£3“.83as.“
`«N13:gm5?.
`a:SE3a8%8355°
`
`3%0E
`
`8%a:3x8%SE3&6
`
`
`
`ByM.(Eu
`
`Ex 1008 / Page 3 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 3 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`9m
`
`M3m
`
`7.,
`
`1B0
`
`m0%cam,«NEEFEE3%.2348%.kc}.«sag8E238%SN5%
`
`43.....A;
`
`fl.6masmEu
`
`m«N12»DEE$523¢v§w838:3%3a8:8xEmu
`
`Ex 1008 / Page 4 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 4 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`9O
`
`700
`
`f04teeh
`
`5
`
`US 7,280,580 B1
`
`/\
`
`§
`‘E
`
`Q 3 & \
`
`J
`
`/\
`
`Q <
`
`t V E
`
`a“.
`
`Ex. 1008 / Page 5 of 29
`ERICSSON v. UNILOC
`
`2,mm:
`
`S......
`
`1lllllll
`
`>wound—wow
`
`m0 }
`
`own—E
`
`E
`
`82m
`
`Ex. 1008 / Page 5 of 29
`ERICSSON v. UNILOC
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 5 0f 15
`
`US 7,280,580 B1
`
`8‘
`a:
`
`\
`
`C)“5&0
`as
`g
`'E
`.5
`5*
`a
`5
`
`In
`
`E
`D
`O
`H
`LL
`
`«L\
`W
`
`phase
`
`in
`600
`
`Ex. 1008 / Page 6 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 6 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 6 0f 15
`
`US 7,280,580 B1
`
`C34
`0
`.51
`
`
`H0?
`
`CWEZS’T‘pfiE—A’WHDED
`
`(address)
`
`
` sale-arm]
`
`H019
`
`'5
`.9.
`0
`
`Ex. 1008 / Page 7 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 7 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 7 of 15
`
`US 7,280,580 B1
`
`\flnNHHHQflm
`:wwowW3“,
`
`5.0333322:awhm.nvmNfi
`
`”0%:
`
`Em
`
`xin
`
`Ex 1008 / Page 8 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 8 of 29
`ERICSSON v. UNILOC
`
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 8 of 15
`
`US 7,280,580 B1
`
`3:33E,3NJ.2
`§v§¥¥
`
`«2.x,w\\\q\m¢vhdM\Vmw.fiu§H
`
`Ex 1008 / Page 9 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 9 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 9 0f 15
`
`US 7,280,580 B1
`
`DETERMINE PRESET HOP
`
`CHANNEL AS FUNCTION OF PHASE
`
` 901
`903
`
` PRESENT HOP
`CHANNEL ALLOWABLE?
`
`
`
` 907
` 909
`
`|NDEX=MOD(CLOCK,N2)+BASE VALUE
`
`905
`
`PRESENT HOP CHANNEL=TABLE(INDEX)
`
`USE PRESENT HOP CHANNEL
`
`FIG. 9
`
`Ex. 1008 / Page 10 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 10 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 10 0f 15
`
`US 7,280,580 B1
`
`1001
`
`INDEX
`
`HOP CHANNEL
`
`INDICATOR
`
`FORBIDDEN
`
`
`
`FIG. 10
`
`EX. 1008 / Page 11 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 11 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 11 0f 15
`
`US 7,280,580 B1
`
`1107
`
`UPDATE
`
`PHASE
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1101
`
`1103
`
`YES
`
`
`
`ORBIDDEN INDICATOR (PHASE) = 0.
`
`1105
`
`PRESENT HOP CHANNEL =
`
`
`
`HOP CHANNEL (PHASE)
`
`NO
`
`OFFSET = MOD (CLOCK,N2)
`
`INDEX = 1
`
`1109
`
`1111
`
`
`
`1113
`
`FORBIDDEN INDICATOR (INDEX) = 0?
`
`
`
`NO
`
`
`
`INDEX = |NDEX+1
`
`
`
`YES
`
`1115
`
`NO
`
`OFFSET=OFFSET—1
`INDEX = |NDEX+1
`
`1117
`
`1119
`
`YES
`
`1121
`
`PRESENT HOP CHANNEL = HOP CHANNEL(INDEX)
`
`FIG. 11
`
`EX. 1008 / Page 12 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 12 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 12 0f 15
`
`US 7,280,580 B1
`
`1201
`
`N
`
`K 1003
`
`f 1005
`
`FORBIDDEN
`
`r 1203
`
`INDEX
`
`HOP CHANNEL
`
`INDICATOR
`
`GAP COUNT
`
`_L
`
`(DmNCDU'l-hCON
`
`FIG. 12
`
`Ex. 1008 / Page 13 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 13 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 13 0f 15
`
`US 7,280,580 B1
`
`
`
`1307
`
`UPDATE
`PHASE
`
`N2 = NUMBER OF ALLOWABLE
`HOPS
`
`1 303
`
`
`
`
`
`YES
`
`1305
`
`
`
`ORBIDDEN INDICATOR (PHASE) = O.
`
`PRESENT HOP CHANNEL =
`
`
`
`HOP CHANNEL (PHASE)
`
`NO
`
`OFFSET = MOD (CLOCK,N2) + 1
`
`LAST GAP COUNT = 0
`
`1301
`
`1309
`
`1311
`
`YES
`
`
`
`
`
`
`GAP COUNT(OFFSET+LAST GAP COUNT)
`= LAST GAP COUNT?
`
`NO
`
`PRESENT HOP CHANNEL=
`
`HOP CHANNEL(OFFSET+LAST GAP COUNT)
`
`1315
`
`1317
`
`LAST GAP COUNT =
`
`GAP COUNT(OFFSET + LAST GAP COUNT)
`
`FIG= 13
`
`EX. 1008 / Page 14 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 14 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`\a\\m?......................................................mamflmmmwmmmwmmwm:
`
`\ O
`
`ct. 9, 2007
`
`Sheet 14 of 15
`
`US 7,280,580 B1
`
`gEL?
`
`SEas.
`
`\ififl
`
`A®t\
`v50Haas
`
`Ex. 1008 / Page 15 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 15 of 29
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Oct. 9, 2007
`
`Sheet 15 of 15
`
`US 7,280,580 B1
`
`M;Q\4\Vo$\
`
`
`
`.monvfimmofizcmmmmfl.wmmwmeN
`
`NMEUQHQVQQNW
`
`in
`
`REES
`
`AQV\,GE
`
`
`
`gmmwnEmmS:omowmfi.ocmwmnN
`
`
`
`mmSwimsglwwIu@m{Em
`@E
`
`Ex. 1008 / Page 16 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 16 of 29
`ERICSSON v. UNILOC
`
`
`

`

`US 7,280,580 B1
`
`1
`HOP SEQUENCE ADAPTATION IN A
`FREQUENCY-HOPPING COMMUNICATIONS
`SYSTEM
`
`BACKGROUND
`
`The invention relates to communication systems where
`transmitter and receiver make use of a hop sequence to
`remain in contact. More particularly, the invention relates to
`techniques for dynamically skipping certain hops of the hop
`sequence.
`
`In the last several decades, progress in radio and Very
`Large Scale Integrated circuit (VLSI) technology has fos-
`tered widespread use of radio communications in consumer
`applications. Portable devices, such as mobile radios, can
`now be produced having acceptable cost, size and power
`consumption.
`Although wireless technology is today focused mainly on
`voice communications
`(e.g., with respect
`to handheld
`radios), this field will likely expand in the near future to
`provide greater information flow to and from other types of
`nomadic devices and fixed devices. More specifically, it is
`likely that further advances in technology will provide very
`inexpensive radio equipment that can easily be integrated
`into many devices. This will reduce the number of cables
`currently used. For instance,
`radio communication can
`eliminate or reduce the number of cables used to connect
`
`master devices (e.g., personal computers) with their respec-
`tive peripherals (e.g., printers).
`The aforementioned radio communications will require
`an unlicensed band with sufficient capacity to allow for high
`data rate transmissions. A suitable band is the Industrial
`
`Scientific and Medical (ISM) band at 2.45 GHz, which is
`globally available. The band provides 83.5 MHZ of radio
`spectrum.
`To allow different radio networks to share the same radio
`
`medium without coordination, signal spreading is usually
`applied. In fact, the Federal Communications Commission
`(FCC) in the United States currently requires radio equip-
`ment operating in the 2.4 GHz band to apply some form of
`spectrum spreading technique when the transmit power
`exceeds about 0 dBm. Spread spectrum communication
`techniques, which have been around since the days of World
`War II, are of interest in today’s commercial applications
`because they provide robustness against interference, and
`allow for multiple signals to occupy the same radio band at
`the same time.
`
`Spreading can either be at the symbol level by applying
`direct-sequence (DS) spread spectrum techniques or at the
`channel level by applying frequency hopping (FH) spread
`spectrum techniques. In DS spread spectrum, the informa-
`tional data stream to be transmitted is impressed upon a
`much higher rate data stream known as a signature sequence.
`Typically, the signature sequence data are binary, thereby
`providing a bit stream. One way to generate this signature
`sequence is with a pseudo-noise (PN) process that appears
`random, but can be replicated by an authorized receiver. The
`informational data stream and the high bit rate signature
`a,
`sequence stream are combined to generate a stream of
`so-called “chips
`by multiplying the two bit
`streams
`together, assuming the binary values of the two bit streams
`are represented by +1 or —1. This combination of the higher
`bit rate signal with the lower bit rate data stream is called
`spreading the informational data stream signal. Each infor-
`mational data stream or channel
`is allocated a unique
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`signature sequence. At the receiver, the same unique signa-
`ture sequence is used to recover the underlying informa-
`tional data stream signal.
`In frequency hopping systems, the spreading is achieved
`by transmitting the informational data stream over ever-
`changing radio frequencies. For each communication, the
`particular frequencies used by both the transmitter and
`receiver are determined by a predefined frequency hop
`sequence. The use of frequency hopping is attractive for the
`radio applications mentioned above because it more readily
`allows the use of cost effective radios.
`
`A system called Bluetooth was recently introduced to
`provide pervasive connectivity especially between portable
`devices like mobile phones, laptops, personal digital assis-
`tants (PDAs), and other nomadic devices. This system
`applies frequency hopping to enable the construction of
`low-power,
`low-cost radios with a small footprint. The
`system supports both data and voice. The latter is optimized
`by applying fast frequency hopping in combination with a
`robust voice coding. The fast frequency hopping has a
`nominal rate of 800 hops per second (hops/s) through the
`entire 2.4 GHz ISM band. Devices based on the Bluetooth
`
`system concept can create so called piconets, which com-
`prise a master device and one or more slave devices con-
`nected via the FH piconet channel. The FH sequence used
`for the piconet channel is completely determined by the
`address or identity of the device acting as the master. The
`system clock of the master device determines the phase in
`the hopping sequence (i.e., the designation of which one of
`the possible hops in the sequence is the “current” hop). In the
`Bluetooth system, each device has a free-running system
`clock. Each of the slave devices adds a corresponding time
`offset to its clock that enables it to become aligned with the
`clock of the master device. By using the master address to
`select the proper hopping sequence and by using the time
`offset to align to the master clock, each slave device keeps
`in hop synchrony to the master device; that is, master and
`slave devices remain in contact by hopping synchronously to
`the same hop frequency or hop carrier. For more details,
`reference is made to US. patent application Ser. No. 08/932,
`911, filed on Sep. 18, 1997 in the name of]. C. Haartsen and
`entitled “Frequency Hopping Piconets in an Uncoordinated
`Wireless Multi-user System,” which is hereby incorporated
`herein by reference in its entirety.
`The hop sequences used in the Bluetooth system are
`generated through a hop selection mechanism as described
`in US. patent application Ser. No. 08/950,068, filed on Oct.
`24, 1997 in the name of J. C. Haartsen and entitled “Method
`and Apparatus for the Generation of Frequency Hopping
`Sequences,” which is hereby incorporated herein by refer-
`ence in its entirety. With this method, hop carriers are
`generated “on the fly”. The mechanism has no inherent
`memory: address and clock information instantaneously
`determine the sequence and phase and therefore directly
`determine the desired hop carrier. The advantages of such a
`selection scheme are numerous. By changing address and
`clock, a device can jump from one FH piconet channel
`controlled by one address/clock combination to another
`piconet controlled by another address/clock combination. In
`this regard, reference is also made to the aforementioned
`application U.S. Ser. No. 08/932,911 describing FH piconets
`in an uncoordinated wireless multi-user system.
`Radio communications intended for local connectivity
`between consumer applications require the use of a free and
`unlicensed band. As mentioned before, the ISM band at 2.45
`GHz is a suitable band because it
`is available globally
`(although the specific part of the ISM band that may be used
`
`EX. 1008 / Page 17 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 17 of 29
`ERICSSON v. UNILOC
`
`

`

`US 7,280,580 B1
`
`3
`may differ per country or continent). Because no license is
`needed, more applications that use radios in these bands are
`emerging. Applications range from low-power baby moni-
`tors and garage door openers, to high-power radio frequency
`(RF) identification (ID) and Wireless Local Area Network
`(LAN) systems. For a wireless system such as Bluetooth,
`these other users are experienced as interferers. Frequency
`hopping provides a certain level of immunity against these
`interferers: when a Bluetooth connection lands on a hop
`carrier already in use by another radio system,
`it may
`experience interference for the duration of the hop dwell
`time. However, since the Bluetooth radio hops at a nominal
`rate of 800 hops/s, the dwell time is only 1.25 milliseconds
`(ms) after which the radio will hop to another channel. Since
`the range over which the radio is hopping is 80 MHZ wide,
`the probability that the next hop is also occupied is rather
`small. Data protocols at a higher layer level can deal with
`distorted information, for example by applying a retrans-
`mission scheme or an error-correction scheme. However,
`performance can be improved if the FH channel can avoid
`those hop frequencies associated with heavy interference. In
`particular,
`if there are narrowband interference sources
`(“jammers”) that continuously occupy one or more hop
`channels (so-called continuous-wave or CW jammers), the
`throughput of the piconet channel can especially be
`improved if both the hopping transmitter and the receiver
`can skip the interfered hop frequencies and instead hop to a
`clean hop carrier. Skipping certain hops may also be ben-
`eficial in those instances in which a certain band in the
`
`spectrum is reserved for high-rate links, which do not
`tolerate interference. Frequency hopping Bluetooth devices
`within range of such high-rate links could prioritize these
`links by avoiding hopping into the reserved band. An
`advanced system that makes use of both a hopping channel
`for low-rate services and a dynamically selected semi-fixed
`channel for high-rate services is described in US. patent
`application Ser. No. 09/385,024, filed on Aug. 30, 1999 in
`the name of J. C. Haartsen and entitled “Resource Manage-
`ment in Uncoordinated Frequency Hopping System”, which
`is hereby incorporated herein by reference in its entirety.
`Another situation in which adapting the hop sequence
`may be beneficial is the one in which a fast hopper and a
`slow hopper share the same spectrum. The fast hopper may
`then remove the hop carrier out of his FH sequence that
`corresponds to the hop carrier the slow hopper currently
`occupies. When the slow hopper hops to the next hop
`channel, the fast hopper must adapt its FH sequence.
`Skipping certain hop frequencies means changing the hop
`sequence such that one or more hop frequencies are removed
`from the sequence. However, hop removal must be adapt-
`able because the interference cannot be predicted (the band
`is unlicensed and any radio can make use of it) and may vary
`over time (for example, the band to avoid may be based on
`dynamic channel selection). That
`is,
`the hop sequences
`should be capable of dynamic adaptation in order to avoid
`one or more hop frequencies.
`In conventional systems like FH systems based on the
`IEEE 802.11 Wireless LAN (WLAN) standard, a restricted
`number of hopping sequences has been defined. In each
`sequence, each hop carrier is only visited once. Conse-
`quently, with 79 hop frequencies defined in this standard, the
`sequence length is only 79. These sequences are fixed,
`limited in size, limited in number, and can simply be stored
`as a list in a Read Only Memory (ROM) or other non-
`volatile memory. When a new channel
`is established, a
`sequence is selected that preferably interferes as little as
`possible with already established hopping channels in the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`same or adjacent areas. Since the sequences are stored,
`off-line processing can simply be carried out for example to
`remove one or more frequencies from the sequence.
`In contrast,
`there are a large number of possible FH
`sequences in the Bluetooth system. The sequence selected is
`based on 28 bits in the master identity. As a result, 200(i.e.,
`2 raised to the 28th power) or 268,435,456 different hop
`sequences are defined.
`In addition,
`the length of each
`sequence is determined by the master clock which counts
`from 0 to 2827—1 at a rate of 1600 increments per second.
`The clock value wraps around back to zero after about 23.3
`hours.
`
`The number of possible sequences and the size of each
`sequence make it
`impossible to store the Bluetooth FH
`sequences and process them off-line. Instead, a selection
`mechanism is used as described in the above-referenced
`
`US. patent application Ser. No. 08/950,068. Adapting the
`FH sequences to avoid certain hop frequencies is not trivial,
`especially if there is also a requirement to preserve the
`feature whereby switching between different FH channels is
`performed by merely replacing the address and clock infor-
`mation.
`
`Conventional techniques are inadequate for this purpose.
`For example, US. Pat. No. 5,848,095, which issued to
`Deutsch on Dec. 8, 1998, discloses a system and method for
`adaptive hopping, whereby frequencies are selected for
`substitution in a frequency hopping system by reference to
`time slots. In the exemplary embodiment, all units have four
`frequency hopping sequences allocated to them, designated
`A, B, C and D. A unit may, for example, be in a talking mode
`in which it uses group B to hop from channels B1, B2, B3,
`and so on. If, for example, channel B3 is found to interfere,
`the channel would be “marked” as bad, and channel C3
`would substitute for channel B3. The result would be a
`
`hopping sequence consisting of B1, B2, C3, B4, B5 and so
`on. This strategy has a number of drawbacks. To begin with,
`it requires changes to the hop sequence generator. Moreover,
`because the strategy involves selecting a substitute channel
`from another hopping sequence, there is no guarantee that
`the selected substitute will be a suitable channel. For
`
`example, in the above-illustrated case, there is no certainty
`that the substitute channel C3 is usable. In such cases, this
`document describes making yet another selection from
`another group (e.g., selecting channel D3 from group D) and
`repeating this operation until a suitable substitute channel is
`selected. However,
`this strategy can’t guarantee that an
`acceptable substitute channel will always be found without
`prestoring an overwhelming number of hopping sequences.
`US. Pat. No. 5,515,369, which issued to Flammer, III et
`al. on May 7, 1996 discloses a method for frequency sharing
`and frequency punchout in a frequency hopping communi-
`cations network. Bad channels are eliminated by means of a
`punchout mask. Having eliminated bad channels, a seed
`value is used to generate a randomly ordered channel
`hopping sequence from the remaining good channels.
`US. Pat. No. 5,619,493, which issuedto Ritz et al. on Apr.
`8, 1997, discloses a spread-spectrum frequency-hopping
`radio telephone system with voice activation. A set of N
`carrier frequencies are reused in adjacent communications
`sites to provide more than N minimally cross-correlated
`frequency-hopping communication channels. A second hop-
`ping sequence is derived from a first hopping sequence by
`selecting frequencies from the first set in their sequential
`order, skipping a first decimation number of frequencies in
`the sequence, and repeating this process on the remaining
`
`Ex. 1008 / Page 18 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 18 of 29
`ERICSSON v. UNILOC
`
`

`

`US 7,280,580 B1
`
`5
`frequencies in the first sequence in their remaining order.
`Other hop sequences are similarly derived by using different
`decimation numbers.
`
`US. Pat. No. 5,809,059, which issued to Souissi et al. on
`Sep. 15, 1998, discloses a method and apparatus for spread
`spectrum channel assignment. The technique includes com-
`puting average noise and interference levels for different
`sequences of channels, and then selecting that one of the
`sequences of channels having the lowest average noise and
`interference level for a next transmission of information.
`
`US. Pat. No. 4,606,040, which issued to David et al. on
`Aug. 12, 1986, discloses a transmitting-receiving station for
`a system for transmitting data by frequency hopping. In
`order to facilitate synchronization between two units when
`one is in a standby mode, a code generator defines the use
`of a plurality of channels in accordance with a so-called
`high-speed skip law for a transmitting-receiving station in
`either of the transmitting or receiving modes, and in accor-
`dance with a so-called low-speed skip law for a transmitting-
`receiving station in the stand-by mode. The high-speed skip
`law consists of the use of each of the channels during a time
`TP, while the low-speed skip law governs the changes of the
`listening channels employed during NxTP, each correspond-
`ing to a center channel of a sequence of N channels of the
`high-speed skip law.
`US. Pat. No. 4,023,103, which issued to Malm on May
`10, 1977, discloses a synchronizer for synchronizing a
`frequency hopping receiver with a companion frequency
`hopping transmitter. The synchronizer includes an electronic
`clock that provides timing pulses for activating a pseudo-
`random sequence generator at the frequency hopping rate,
`and means that cause the clock to skip one activating pulse
`every N successive frequency hopping periods, until a
`frequency hopping local signal and a frequency hopping
`signal from the companion receiver are out of sync by less
`than one frequency hopping period.
`Each of the above-cited documents discloses a technique
`for skipping certain hops that has drawbacks, including the
`fact that each requires changes to the hop sequence genera-
`tor.
`
`There is therefore a need for methods and apparatuses for
`removing specific hop frequencies from an arbitrary hopping
`sequence. There is also a need for accomplishing this
`without requiring off-line processing. It is also desirable to
`be able to adapt hop sequences dynamically, and to apply
`this adaptation to any existing hop selection scheme or
`existing hop sequence.
`
`SUMMARY
`
`In accordance with the present invention, a hop channel is
`selected for use in a channel hopping communication system
`that
`includes a sequence of hop channels, wherein the
`sequence comprises a set of forbidden hop channels and a
`remaining set of allowable hop channels. In accordance with
`one aspect of the invention, selection involves selecting a
`hop channel from the sequence as a function of a present
`phase. If the selected hop channel
`is an allowable hop
`channel, then the selected hop channel is used for commu-
`nication during the present phase. If the selected hop channel
`is a forbidden hop channel, then a time-varying parameter is
`used to select a substitute hop channel from the set of
`allowable hop channels. The substitute hop channel is then
`used for communication during the present phase. With this
`strategy, the resultant hopping sequence is identical to the
`original hopping sequence whenever the original sequence
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`calls for an allowable hop channel. In all other cases, a
`substitute hop channel is dynamically selected from the set
`of allowable hop channels.
`the time-varying
`In another aspect of the invention,
`parameter may be a clock value. In some embodiments, the
`time-varying parameter and the present phase may be
`derived from a same clock value. In alternative embodi-
`
`ments, the time-varying parameter may be a random value
`or a pseudo-random value.
`In yet another aspect of the invention, hop selection
`further comprises forming a sequence of allowable hop
`channels from the set of allowable hop channels. In this case,
`the operation of using a time-varying parameter to select a
`substitute hop channel from the set of allowable hop chan-
`nels comprises forming an index value from the time-
`varying parameter; using the index value to select one of the
`allowable hop channels from the sequence of allowable hop
`channels; and using the selected allowable hop channel as
`the substitute hop channel.
`In still another aspect of the invention, the operation of
`forming the index value from the time-varying parameter
`comprises determining the expression:
`index value:mod(time-varying parameter, N2)+
`BASE VALUE,
`
`where mod (j,k) denotes j modulo k, N2 is the number of
`allowable hop channels in the sequence of allowable chop
`channels and BASE VALUE represents an index value of the
`first allowable hop channel in the sequence of allowable hop
`channels.
`
`In yet another aspect of the invention, the operation of
`using a time-varying parameter to select a substitute hop
`channel from the set of allowable hop channels comprises
`determining an index value,
`i, as a function of the time-
`varying parameter; designating one of the allowable hop
`channels in the sequence of hop channels as a first hop
`channel; starting at the first hop channel, processing the
`sequence of hop channels to determine an ith allowable hop
`channel in the sequence of hop channels; and selecting the
`ith allowable hop channel for use as the substitute hop
`channel.
`
`In some embodiments, the first hop channel may be the
`first hop channel
`in the sequence of hop channels.
`In
`alternative embodiments, the first hop channel may be a first
`hop channel after a last forbidden hop channel
`in the
`sequence of hop channels. In this case, the operation of
`processing the sequence of hop channels to determine an ith
`allowable hop channel
`in the sequence of hop channels
`wraps around to the start of the sequence of hop channels
`when i is greater than the number of hop channels following
`the last forbidden hop channel
`in the sequence of hop
`channels.
`
`In still another aspect of the invention, the operation of
`processing the sequence of hop channels to determine an ith
`allowable hop channel in the sequence of hop channels may
`alternatively comprise, starting at the first hop channel and
`continuing with each successive hop channel in the sequence
`of hop channels, determining whether the hop channel is an
`allowable hop channel; and stopping when an ith allowable
`hop channel has been identified in the sequence of hop
`channels.
`
`the technique
`In yet another aspect of the invention,
`further comprises determining a gap count for each of the
`hop channels in the sequence of hop channels, wherein the
`gap count represents how many forbidden hop channels are
`in the sequence of hop channels from the first hop channel
`
`Ex. 1008 / Page 19 of 29
`ERICSSON v. UNILOC
`
`Ex. 1008 / Page 19 of 29
`ERICSSON v. UNILOC
`
`

`

`US 7,280,580 B1
`
`7
`up to and including said each of the hop channels. In these
`embodiments, the operation of processing the sequence of
`hop channels to determine an ith allowable hop channel in
`the sequence of hop channels comprises (a) using the index
`value plus a previous gap count to select one of the hop
`channels from the sequence of hop channels; and (b) using
`the selected hop channel as the substitute hop channel if the
`selected hop channel is associated with a present gap count
`that is equal to the previous gap count, otherwise setting the
`previous gap count equal
`to the present gap count and
`repeating operations (a) and (b).
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The objects and advantages of the invention will be
`understood by reading the following detailed description in
`conjunction with the drawings in which:
`FIG. 1 is a graph depicting an exemplary hop carrier
`definition in the ISM band;
`FIGS. 2(a) and 2(b) are graphs depicting examples of hop
`carrier definitions in the ISM band in case of three individual
`narrowband interferers;
`FIGS. 3(a) and 3(b) are graphs depicting examples of hop
`carrier definitions in the ISM band in case of a single
`wideband interferer;
`FIGS. 4(a) and 4(b) illustrate a hop carrier selection
`technique that utilizes a pre-stored sequence;
`FIG. 5 is a block diagram of an exemplary hop carrier
`selector for the case of on-the-fly sequence generation;
`FIG. 6 is a block diagram illustrating the general concept
`of a hop avoidance scheme in accordance with the invention;
`FIG. 7 is a diagram of a hop sequence having a total of N1
`hop channels;
`FIG. 8 is a block diagram illustrating a set of N2 remain-
`ing allowable hop channels in accordance with one aspect of
`the invention;
`FIG. 9 is a flow chart of operations in accordance with one
`embodiment of the invention;
`FIG. 10 is a diagram of a table that may be stored in a
`memory for use in determining a substitute hop channel in
`accordance with an embodiment of the invention;
`FIG. 11 is a flow chart of operations for determining a
`suitable hop channel in accordance with one embodiment of
`the invention;
`FIG. 12 is a diagram of a table that may be stored in a
`memory for use in determining a substitute hop channel in
`accordance with an alternative embodiment of the invention;
`FIG. 13 is a flow chart of operations for determining a
`suitable hop channel
`in accordance with an alternative
`embodiment of the invention;
`FIG. 14 is a block diagram of a frequency hop generator
`for use in a Bluetooth system,
`in accordance with an
`embodiment of invention; and
`FIGS. 15(a) and 15(b) depict a comparison between an
`original and a corresponding revised hopping scheme, in
`accordance with the invention.
`
`DETAILED DESCRIPTION
`
`The various features of the invention will now be
`
`described with respect to the figures, in which like parts are
`identified with the same reference characters.
`
`The techniques described herein achieve the skipping of
`certain hops in a hop sequence without having to change the
`hop sequence generator. Instead, a transformation operation
`is performed in which a “forbidden” hop serves as the basis
`for determining an “allowed” hop. For example, if the hop
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`selection mechanism visits a “forbidden” hop, an offset may
`be temporarily added to the phase such that an allowed hop
`is instead selected. The offset
`is only a