Frequency Hopping Spread Spectrum

The sequence. Both ends must generate the same sequence at the same time. It should look random, so that an adversary cannot predict the next channel and other systems collide only at chance; it should use every channel about equally; and, where several users share the band, sequences must be chosen so that they do not collide systematically. GSM's algorithm does all three, and the program runs it.

GSM's hopping, exactly as specified

3GPP TS 45.002 defines the mapping from a frame number to a carrier. Three parameters set it up:

• MA, the mobile allocation: "Mobile allocation of radio frequency channels, defines the set of radio frequency channels to be used in the mobiles hopping sequence. The MA contains N radio frequency channels, where 1 <= N <= 64."
• MAIO, the mobile allocation index offset, "(0 to N-1, 6 bits)".
• HSN, the hopping sequence (generator) number, "(0 to 63, 6 bits)".

The algorithm gives "the index to an absolute radio frequency channel number (ARFCN) within the mobile allocation (MAI from 0 to N-1, where MAI=0 represents the lowest ARFCN in the mobile allocation".

With HSN = 0 the hopping is cyclic: "MAI = (FN + MAIO) modulo N", simply stepping through the list. With any other HSN the sequence is pseudo-random, computed from the frame number through three time parameters and a fixed table of 114 numbers, the RNTABLE, and finally offset by the MAIO.

The design has a neat property. Mobiles in the same cell are given the same HSN and different MAIOs, so their sequences are the same sequence shifted, and two mobiles never land on the same carrier in the same frame. Mobiles in different cells are given different HSNs, so their sequences are unrelated and collisions happen only at random, which spreads interference between cells evenly instead of concentrating it on one unlucky pair. The program verifies both.

Hopping, computed

The program implements GSM's generator with its own RNTABLE and prints the sequences for a cyclic and a pseudo-random case, checks that two MAIOs never collide and that the carriers are used evenly, measures what a jammer sitting on one of eight channels costs for different hop rates, and separates slow from fast hopping by counting symbols per hop.

GSM hopping (TS 45.002, 6.2.3) over 8 carriers [12, 20, 28, 36, 44, 52, 60, 68]
  HSN 0, MAIO 0: cyclic     12  20  28  36  44  52  60  68  12  20  28  36  44  52  60  68
  HSN 13, MAIO 0            20  60  68  28  68  28  12  36  68  12  20  12  44  28  44  52
  HSN 13, MAIO 3            44  20  28  52  28  52  36  60  28  36  44  36  68  52  68  12
  two mobiles in one cell share the HSN and differ in MAIO, so they never collide:
  in 2000 frames, MAIO 0 and MAIO 3 land on the same carrier 0 times
  over 20000 frames each of the 8 carriers is used 2455 to 2558 times

One channel of 8 jammed, and what a frame loses:
  hops per frame   frames lost outright   frames with some hops lost   bits lost on average
               1                  12.29%                        12.29%                12.29%
               4                   0.03%                        41.09%                12.38%
               8                   0.00%                        65.53%                12.47%
              26                   0.00%                        96.91%                12.50%
  hopping does not avoid the jammer; it spreads the damage so that coding can repair it.

Slow and fast hopping:
  GSM, one hop a burst       1248.1 symbols a hop   slow: many symbols a hop
  Bluetooth, 1600 hops/s      625.0 symbols a hop   slow: many symbols a hop
  a fast hopper                 0.5 symbols a hop   fast: many hops a symbol

The sequences. With HSN 0 the mobile walks its eight carriers in order: 12, 20, 28, 36, 44, 52, 60, 68, and round again. With HSN 13 the order is scrambled and repeats nothing obvious: 20, 60, 68, 28, 68, 28, 12, 36. Notice that the same carrier can come twice in a row and that 68 appears twice in the first five hops: a pseudo-random sequence is allowed to do that, and does.

No collisions within a cell. MAIO 3 produces the same sequence shifted three places along the allocation, and in 2,000 frames the two mobiles landed on the same carrier zero times. That is worth pausing on: two mobiles hopping pseudo-randomly over eight carriers would collide about a quarter of the time if their sequences were independent. GSM gets orthogonality inside a cell and randomness between cells out of one generator, by splitting the parameters into a shared HSN and a per-mobile MAIO.

Evenness. Over 20,000 frames the eight carriers were used between 2,455 and 2,558 times, against an ideal 2,500: even to within about 2 per cent. A hop sequence that favoured some carriers would waste the diversity that hopping exists to provide.

What a jammer costs. With one hop per frame, 12.29 per cent of frames land on the jammed channel and are lost outright. With four hops per frame, only 0.03 per cent of frames are wholly lost, but 41 per cent are damaged somewhere; with 26 hops, essentially every frame is damaged and none is lost. The average fraction of bits lost is the same 12.5 per cent in every case, which is the honest lesson: hopping does not reduce the interference, it redistributes it. What it buys is that the damage arrives as scattered errors inside many frames, which an error-correcting code can repair, instead of as whole frames destroyed, which it cannot.

Slow and fast. GSM hops 217 times a second and sends 270,833 symbols a second, so 1,248 symbols ride on each hop: slow hopping. Bluetooth's 1,600 hops a second at about 1 Msymbol/s gives 625 symbols a hop: also slow. Only a hopper faster than its own symbol rate, 20,000 hops a second against 10,000 symbols, gets several hops into one symbol, which is fast hopping.

Distinctions

What it does not mean

Hopping does not dodge interference. The average fraction of time spent on a jammed channel is unchanged; the damage is spread out so that coding can repair it.

A hopping signal is not wideband at an instant. It is a narrowband signal that moves; its instantaneous spectrum is that of the underlying modulation.

A pseudo-random sequence is not a secret. GSM's generator is published; secrecy needs cryptography, and military hoppers keep their sequence key secret for that reason.

More hops per second is not automatically better. Each hop costs settling time, and the sequence must still be tracked; the gain comes from spreading damage, which a modest hop rate already achieves.

FHSS and DSSS are not rivals in every system. 802.15.4 spreads with a code, and its 2012 amendment hops as well; the two are combined in TSCH.

Quick revision

• FHSS: the carrier moves on a pseudo-random hop sequence known to both ends; narrow at any instant, wide over time. Processing gain = number of channels.
• Slow hopping: several symbols per hop (GSM 1,248, Bluetooth 625). Fast hopping: several hops per symbol; diversity inside a symbol, expensive synthesiser.
• Benefits: interference and jamming resistance, frequency diversity, sharing with other hoppers. Costs: synchronisation, settling time, collisions.
• GSM (TS 45.002, 6.2.3): MA (up to 64 carriers), HSN (0 to 63; 0 = cyclic, MAI = (FN + MAIO) mod N), MAIO (0 to N-1). Same cell: same HSN, different MAIO, so no collisions; different cells: different HSN, random collisions.
• Program: 8 carriers used 2,455 to 2,558 times in 20,000 frames; MAIO 0 and 3 collided 0 times in 2,000; a jammer on 1 of 8 channels loses 12.29 per cent of frames outright at one hop a frame, but with 26 hops a frame no frame is lost and 96.91 per cent are merely damaged, the same 12.5 per cent of bits either way.
• DSSS against FHSS: wide always against narrow and moving; correlator against synthesiser; averaging against avoidance.

Test yourself

1. What is frequency hopping spread spectrum, and how does it spread a signal? The transmitter changes its carrier frequency repeatedly according to a hop sequence known to the receiver, so that although the signal is narrowband at any instant, over many hops it occupies a wide band. The spreading is therefore in time rather than in instantaneous bandwidth, and the processing gain is the number of channels hopped over. Both ends must be synchronised to the sequence and to the hop timing.

2. Distinguish slow and fast frequency hopping. In slow hopping a hop lasts longer than a symbol, so several symbols, often hundreds, are sent on each carrier; GSM sends 1,248 symbols per hop and Bluetooth about 625. In fast hopping a single symbol is spread over several hops, so every symbol samples several channels and gains diversity within itself, but the frequency synthesiser must settle in a fraction of a symbol period, which is costly, so fast hopping is used mainly in military systems.

3. Explain GSM's hopping parameters and how two mobiles in one cell avoid each other. A mobile is given a mobile allocation, the set of up to 64 carriers it may use; a hopping sequence number from 0 to 63, which selects the pseudo-random generator, with 0 meaning cyclic hopping; and a mobile allocation index offset from 0 to N-1. For each frame the algorithm computes an index into the allocation from the frame number and the hopping sequence number and then adds the offset modulo N. Mobiles in the same cell share the hopping sequence number and are given different offsets, so their sequences are the same sequence shifted and they never occupy the same carrier in the same frame; mobiles in different cells use different hopping sequence numbers, so their sequences are unrelated and collisions occur only at random.

4. Does frequency hopping reduce the effect of a jammer? Explain with the chapter's measurements. It does not reduce the total interference: with one channel of eight jammed, about one eighth, 12.5 per cent, of the transmitted bits are hit whatever the hop rate. What it changes is the distribution. With one hop per frame, 12.29 per cent of frames land on the jammed channel and are destroyed entirely. With 26 hops per frame, no frame is entirely lost, although 96.91 per cent contain some damaged bits. Scattered bit errors within a frame can be corrected by an error-correcting code, while a wholly destroyed frame cannot, so hopping converts unrecoverable loss into recoverable loss.

5. Compare DSSS and FHSS. DSSS multiplies each symbol by a fast chipping code, so the signal is wide at every instant; the receiver correlates with the code, which averages narrowband interference down by the processing gain, and multipath echoes past a chip can be separated or combined. FHSS keeps the signal narrow at each instant and moves it between channels on a pseudo-random sequence, so an interferer or a fade costs only the hops that land on it. DSSS needs chip-level synchronisation and a correlator; FHSS needs hop timing and a fast synthesiser. IEEE 802.15.4, W-CDMA and GPS use DSSS; GSM, Bluetooth and the TSCH mode of 802.15.4e hop.

6. Why must a hop sequence use every channel about equally? Because the diversity that hopping provides comes from sampling many channels: if some were visited more often than others, a fade or an interferer on a favoured channel would cost more than its share, and the benefit of hopping would fall. The chapter's run of GSM's generator over 20,000 frames used each of eight carriers between 2,455 and 2,558 times against an ideal 2,500, which is even to within about 2 per cent.