Chapter 12

Multiple Access
K. Sujatha
Associate Professor
Dept of ECE, BMSCE

12.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Introduction

 Data link control- mechanism which provides a link

with reliable communication

 Protocols described- assumed there is an available

dedicated link between the sender & receiver

 This assumption may or may not be true

 If we have a dedicated link when we connect to the

Internet using PPP as the data link control protocol,
then the assumption is true & we do not need anything
else

12.2 K. Sujatha ECE , BMSCE

Figure 12.1 Data link layer divided into two functionality-oriented sublayers

 Upper sub-layer is responsible for data link control (flow

& error control called Logical Link Control)
 Lower sub-layer is responsible for resolving access to
shared media (called Media Access Control- MAC
layer)

12.3
Figure 12.2 Taxonomy of multiple-access protocols discussed in this chapter

12.4
 12-1 RANDOM ACCESS
In random access or contention methods, no station is
superior to another station & none is assigned the control
over another
 No station permits, or does not permit, another station
to send
At each instance, a station that has data to send uses a
procedure defined by the protocol to make a decision on
whether or not to send
Topics discussed in this section:
ALOHA
Carrier Sense Multiple Access
Carrier Sense Multiple Access with Collision Detection
Carrier Sense Multiple Access with Collision Avoidance
12.5
 Random Access
 Two features give this method its name
 First, there is no scheduled time for a station to
transmit
 Transmission is random among the stations- that is why
these methods are called random access
 Second, no rules specify which station should send next.
 Stations compete with one another to access the medium
- that is why these methods are also called contention
methods
 Random access methods have evolved from a very
interesting protocol known as ALOHA, which used a
very simple procedure called Multiple Access (MA)

12.6
 ALOHA
 ALOHA, the earliest random access method, was
developed at the University of Hawaii in early 1970

 Designed for a radio (wireless) LAN, but it can be used

on any shared medium

 There are potential collisions in this arrangement

 Medium is shared between stations-when a station sends

data, another station may attempt to do so at the same
time- data from the two stations collide & become
garbled

12.7
 PURE ALOHA
 Original ALOHA protocol is called pure ALOHA
 Simple, but elegant protocol
 Idea is that each station sends a frame whenever it has a
frame to send
 However, since there is only one channel to share, there
is the possibility of collision between frames from
different stations
 Pure ALOHA protocol relies on acknowledgments from
the receiver
 If the acknowledgment does not arrive after a time-out
period, the station assumes that the frame (or the
acknowledgment) has been destroyed & resends the
frame

12.8
 Figure 12.3 Frames in a pure ALOHA network
 There are four stations that contend with one another for access to the shared
channel
 Some of these frames collide because multiple frames are in contention for the
shared channel

12.9
Figure 13.3 ALOHA network
Figure 13.4 Procedure for Pure ALOHA protocol
 Example 1
The stations on a wireless ALOHA network are a maximum of 600
km apart. If we assume that signals propagate at 3 x 108 ms,
we find Tp = (600 x 105) / (3 x 108) = 2 ms. Find the value of TB
for different values of K.

a. For K = 1, the range is {O, 1}. The station needs to generate a random
number with a value of 0 or 1. This means that TB is either 0ms (0 x 2)
or 2 ms (l x 2), based on the outcome of the random variable.

b. For K =2, the range is {O, 1, 2, 3}. This means that TB can be 0, 2, 4, or
6 ms, based on the outcome of the random variable.

c. For K =3, the range is {0, 1,2,3,4,5,6, 7}. This means that TB can be
0,2,4, ... , 14 ms, based on the outcome of the random variable.

d. We need to mention that if K > 10, it is normally set to 10.

 Vulnerable time for pure ALOHA protocol
Vulnerable time: length of time, in which there is a possibility of collision.

We assume stations send fixed-length frames with each frame

taking Tfr s to send
Station A sends frame at time t-Now imagine station B has already
sent a frame between t - Tfr and t->leads to a collision between frames
from station A & B- > end of B's frame collides with beginning of
A's frame
On the other hand, suppose that station C sends a frame between t
and t + Tfr . Here, there is a collision between frames from station A
and station C.
The beginning of C's frame collides with the end of A's frame.
The vulnerable time, during which a collision may occur in pure
ALOHA, is 2 times the frame transmission time.
Pure ALOHA vulnerable time = 2 x Tfr
12.13
 Figure 12.5 Vulnerable time for pure ALOHA protocol

12.14
 Example 12.2

A pure ALOHA network transmits 200-bit frames on a

shared channel of 200 kbps. What is the requirement to
make this frame collision-free?

Solution
Average frame transmission time Tfr is 200 bits/200 kbps or
1 ms. The vulnerable time is 2 × 1 ms = 2 ms
This means no station should send later than 1 ms before
this station starts transmission and no station should start
sending during the one 1-ms period that this station is
sending.

12.15
 Pure ALOHA – Throughput
 G ->average number of frames generated by the system during
one frame transmission time
Can be proved that the average number of successful
transmissions for pure ALOHA is S = G x e-2G
Maximum throughput Smax is 0.184, for G = 1/2
 i.e if one-half a frame is generated during one frame
transmission time, then 18.4 percent of these frames reach their
destination successfully
 This is an expected result because the vulnerable time is 2 times
the frame transmission time
 Therefore, if a station generates only one frame in this
vulnerable time (& no other stations generate a frame during this
time), the frame will reach its destination successfully

12.16
 Pure ALOHA – Throughput

The throughput for pure ALOHA is S =G x e-2G

The maximum throughput Smax =0.184 when G =(1/2)

12.17
 Example 12.3

A pure ALOHA network transmits 200-bit frames on a

shared channel of 200 kbps. What is the throughput if the
system (all stations together) produces

a. 1000 frames per second

b. 500 frames per second

c. 250 frames per second

12.18
 Example 12.3
The frame transmission time is 200/200 kbps or 1 ms.

a. If the system creates 1000 frames per second, this is 1 frame per
millisecond

The load is 1

In this case S =G x e-2G or S =0.135 (13.5 percent)

This means that the throughput is 1000 X 0.135 =135 frames

Only 135 frames out of 1000 will probably survive

12.19
 Example 12.3

b. If the system creates 500 frames per second, this is (1/2) frame
per millisecond
The load is (1/2)

In this case S = G x e-2G or S = 0.184 (18.4 percent)

This means that the throughput is 500 x 0.184 =92 and that only
92 frames out of 500 will probably survive

Note that this is the maximum throughput case, percentagewise

12.20
 Example 12.3

c. If the system creates 250 frames per second, this is (1/4) frame
per millisecond

The load is (1/4)

In this case S = G x e-2G or S =0.152 (15.2 percent)

This means that the throughput is 250 x 0.152 = 38

Only 38 frames out of 250 will probably survive.

12.21
 Slotted ALOHA

 In slotted ALOHA we divide the time into slots of

Tfr s and force the station to send only at the
beginning of the time slot

12.22
 Figure 12.6 Frames in a slotted ALOHA network
In slotted ALOHA we divide the time into slots of Tfr s and force the station to
send only at the beginning of the time slot.

12.23
 Figure 12.7 Vulnerable time for slotted ALOHA protocol

12.24
 Slotted ALOHA

Vulnerable time is now reduced to one-half, equal to Tfr

Can be proved that the average number of successful

transmissions for slotted ALOHA is S = G x e-G
Maximum throughput Smax is 0.368, when G = 1

In other words, if a frame is generated during one frame

transmission time, then 36.8 percent of these frames reach their
destination successfully. This result can be expected because the
vulnerable time is equal to the frame transmission time.

Therefore, if a station generates only one frame in this

vulnerable time (and no other station generates a frame during this
time), the frame will reach its destination successfully.

12.25
 Example 12.4

A slotted ALOHA network transmits 200-bit frames using

a shared channel with a 200-kbps bandwidth. Find the
throughput if the system (all stations together) produces

a. 1000 frames per second

b. 500 frames per second
c. 250 frames per second

12.26
 Example 12.4

Solution
This situation is similar to the previous exercise except that the
network is using slotted ALOHA instead of pure ALOHA. The
frame transmission time is 200/200 kbps or 1 ms.

a. In this case G is 1. So S =G x e-G or S = 0.368 (36.8 percent).

This means that the throughput is 1000 x 0.0368 =368 frames

Only 368 out of 1000 frames will probably survive

Note that this is the maximum throughput case, Percentagewise

12.27
 Example 12.4

Solution
b. Here G is ½

In this case S =G x e-G or S =0.303 (30.3 percent)

This means that the throughput is 500 x 0.0303 =151

Only 151 frames out of 500 will probably survive

12.28
 Example 12.4

Solution
c. Now G is ¼

In this case S =G x e-G or S =0.195 (19.5 percent)

This means that the throughput is 250 x 0.195 = 49

Only 49 frames out of 250 will probably survive.

12.29
 Carrier Sense Multiple Access (CSMA)

Chance of collision can be reduced if a station senses the

medium before trying to use it

Carrier sense multiple access (CSMA) requires that each

station first listen to the medium before sending

In other words, CSMA is based on the principle "sense

before transmit" or "listen before talk”

CSMA can reduce the possibility of collision, but it

cannot eliminate it

12.30
 Carrier Sense Multiple Access (CSMA)

Possibility of collision still exists because of propagation

delay

When a station sends a frame, it still takes time (although

very short) for the first bit to reach every station & for
every station to sense it

In other words, a station may sense the medium & find it
idle, only because the first bit sent by another station has
not yet been received

12.31
 Figure 12.8 Space/time model of the collision in CSMA

At time t1 station B senses the medium and finds it idle, so it sends a frame. At time t2
(t2> t1) station C senses the medium and finds it idle because, at this time, the first bits
from station B have not reached station C. Station C also sends a frame. The two signals
collide and both frames are destroyed.

12.32
 Figure 12.9 Vulnerable time in CSMA
Vulnerable time for CSMA is the propagation time Tp
When a station sends a frame, & any other station tries to send a frame
during this time, a collision will result
 But if the first bit of the frame reaches the end of the medium, every
station will already have heard the bit and will refrain from sending.
Fig shows the worst case.

12.33
 Persistence Methods

What should a station do if the channel is busy?

 What should a station do if the channel is idle?

Three methods have been devised to answer these

questions:

1. the 1-persistent method,

2. the nonpersistent method, and
3. the p-persistent method

12.34
 Persistence Methods
(i)1-persistent method : simple & straightforward
 After the station finds the line idle, it sends its frame
immediately (with probability 1)
 Highest chance of collision because two or more stations may
find the line idle & send their frames immediately
(ii)Nonpersistent method:
 A station that has a frame to send senses the line. If the line is
idle, it sends immediately. If the line is not idle, it waits a
random amount of time & then senses the line again
 Reduces the chance of collision because it is unlikely that two
or more stations will wait the same amount of time & retry to
send simultaneously
 Reduces the efficiency of the network because the medium
remains idle when there may be stations with frames to send

12.35
 Persistence Methods
(iii)P-persistent:
This method used if the channel has time slots with a slot duration
equal to or greater than the maximum propagation time
This approach combines the advantages of the other two strategies
 Reduces the chance of collision & improves efficiency
 In this method, after the station finds the line idle it follows these
steps:
1. With probability p, the station sends its frame
2. With probability q = 1 - p, the station waits for the beginning of the
next time slot & checks the line again
a. If the line is idle, it goes to step 1
b. If the line is busy, it acts as though a collision has occurred &
uses the backoff procedure

12.36
 Figure 12.10 Behavior of three persistence methods

12.37
 Figure 12.11 Flow diagram for three persistence methods

12.38
 Carrier Sense Multiple Access with Collision Detection
(CSMA/CD)

CSMA method does not specify the procedure

following a collision

 Carrier sense multiple access with collision detection

(CSMA/CD) augments the algorithm to handle the
collision

In this method, a station monitors the medium after it

sends a frame to see if the transmission was successful. If
so, the station is finished. If, however, there is a collision,
the frame is sent again

12.39
 Figure 12.12 Collision of the first bit in CSMA/CD

12.40
 Figure 12.13 Collision and abortion in CSMA/CD

12.41
 Collision of the first bit in CSMA/CD
At time t1, station A has executed its persistence procedure & starts
sending the bits of its frame
 At time t2, station C has not yet sensed the first bit sent by A &
executes its persistence procedure & starts sending the bits in its frame,
which propagate both to the left & to the right
Collision occurs sometime after time t2 -Station C detects a collision at
time t3 when it receives the first bit of A's frame. Station C immediately
(or after a short time, but we assume immediately) aborts transmission
Station A detects collision at time t4 when it receives the first bit of C's
frame; it also immediately aborts transmission
Looking at the figure, we see that A transmits for the duration t4 - tl; C
transmits for the duration t3 - t2‘
 Later we show that, for the protocol to work, the length of any frame
divided by the bit rate in this protocol must be more than either of these
durations.
 At time t4, the transmission of A’s frame, though incomplete, is
aborted; at time t3, the transmission of C's frame, though incomplete, is
aborted.
12.42
 Minimum Frame Size
For CSMA/CD to work, we need a restriction on the frame size
Before sending the last bit of the frame, sending station must detect
a collision, if any, & abort the transmission
 This is so because the station, once the entire frame is sent, does
not keep a copy of the frame & does not monitor the line for collision
detection
Therefore, the frame transmission time Tfr must be at least two
times the maximum propagation time Tp
To understand the reason, let us think about the worst-case
scenario. If the two stations involved in a collision are the maximum
distance apart, the signal from the first takes time Tp to reach the
second, & the effect of the collision takes another time Tp to reach
the first
So the requirement is that the first station must still be transmitting
after 2Tp

12.43
 Example 12.5

A network using CSMA/CD has a bandwidth of 10 Mbps.

If the maximum propagation time (including the delays in
the devices and ignoring the time needed to send a
jamming signal, as we see later) is 25.6 μs, what is the
minimum size of the frame?
Solution
The frame transmission time is Tfr = 2 × Tp = 51.2 μs.
This means, in the worst case, a station needs to transmit
for a period of 51.2 μs to detect the collision. The
minimum size of the frame is 10 Mbps × 51.2 μs = 512
bits or 64 bytes. This is actually the minimum size of the
frame for Standard Ethernet.
12.44
 Figure 12.14 Flow diagram for the CSMA/CD

12.45
 Figure 12.15 Energy level during transmission, idleness, or collision

12.46
 Throughput

Throughput of CSMA/CD is greater than that of pure or

slotted ALOHA
 Maximum throughput occurs at a different value of G &
is based on the persistence method & the value of p in the
p-persistent approach
 For 1-persistent method the maximum throughput is
around 50 percent when G =1
For nonpersistent method, the maximum throughput can
go up to 90 percent when G is between 3 & 8

12.47
 Carrier Sense Multiple Access with collision Avoidance
(CSMA/CA)

Collisions are avoided through the use of CSMA/CA's

three strategies

 Interframe space (IFS)

 Contention window and
 Acknowledgments

12.48
 Carrier Sense Multiple Access with collision CSMA/CA

(i)Interframe Space (IFS):

First, collisions are avoided by deferring transmission even if
channel is found idle
When idle channel is found, station does not send
immediately-waits for a period of time , interframe space or IFS
Even if channel appear idle when it is sensed, distant station
may have already started transmitting
IFS time allows the front of the transmitted signal by the
distant station to reach this station
 If after IFS time if channel is still idle, station can send, but it
still needs to wait a time equal to the contention time
IFS variable can also be used to prioritize stations or frame
types eg - station that is assigned a shorter IFS has a higher
priority
12.49
 Carrier Sense Multiple Access with collision CSMA/CA

(ii)Contention Window :
 Contention window is an amount of time divided into slots
 A station ready to send chooses a random number of slots as its
wait time
 number of slots in window changes according to binary
exponential back-off strategy - set to one slot first time &then
doubles each time station cannot detect an idle channel after
IFS time - similar to p-persistent method except that a
random outcome defines number of slots taken by waiting
station
 Station needs to sense channel after each time slot- if station
finds the channel busy, it does not restart the process; it just
stops the timer & restarts it when the channel is sensed as idle-
gives priority to station with longest waiting time
12.50
 Carrier Sense Multiple Access with collision CSMA/CA

(iii) Acknowledgment :

With all these precautions, there still may be a collision

resulting in destroyed data

In addition, the data may be corrupted during the

transmission

The positive acknowledgment & time-out timer can help

guarantee that receiver has received the frame

12.51
 Figure 12.16 Timing in CSMA/CA

12.52
 Note

In CSMA/CA, the IFS can also be used to

define the priority of a station or a frame.

12.53
 Note

In CSMA/CA, if the station finds the

channel busy, it does not restart the
timer of the contention window;
it stops the timer and restarts it when
the channel becomes idle.

12.54
 Figure 12.17 Flow diagram for CSMA/CA

12.55
 Exercise problem
In Figure 12.12, the data rate is 10 Mbps, the distance between station A and C
is 2000 m, and the propagation speed is 2 x 108 m/s. Station A starts sending a
long frame at time t1 =0; station C starts sending a long frame at time t2 =3µs.
The size of the frame is long enough to guarantee the detection of collision by
both stations. Find:
a. The time when station C hears the collision (t3)'
b. The time when station A hears the collision (t4)'
c. The number of bits station A has sent before detecting the collision.
d. The number of bits station C has sent before detecting the collision.

12.56
 12-2 CONTROLLED ACCESS

In controlled access, stations consult one another to

find which station has the right to send

 A station cannot send unless it has been authorized by

other stations

Discuss three popular controlled-access methods

Topics discussed in this section:

Reservation
Polling
Token Passing
12.57
 Control Access 1) Reservation
Reservation method: a station needs to make a reservation before
sending data
Time is divided into intervals - In each interval, a reservation
frame precedes dataframes sent in that interval

If there are N stations in system, there are exactly N reservation

minislots in reservation frame

Each minislot belongs to a station

 When a station needs to send a data frame, it makes a

reservation in its own minislot- stations that have made
reservations can send their data frames after reservation frame

12.58
 Figure 12.18 Reservation access method

12.59
 Control Access 2) Polling
Polling works with topologies in which one device is designated as
a primary station & other devices are secondary stations

 All data exchanges must be made through primary device even

when ultimate destination is a secondary device

Primary device controls link; the secondary devices follow its

instructions

If primary wants to receive data, it asks secondaries if they have

anything to send; this is called poll function

 If primary wants to send data, it tells the secondary to get ready to

receive; this is called select function

12.60
 Control Access 2) Polling - Select function
Select function is used whenever primary device has
something to send

 If primary is neither sending nor receiving data, it knows the

link is available

If it has something to send, primary device sends it

Primary must alert secondary to the upcoming transmission

& wait for an acknowledgment of the secondary's ready status

Before sending data, primary creates & transmits a select

(SEL) frame, one field of which includes address of the
intended secondary
12.61
 Control Access 2) Polling : Poll function
Poll function is used by primary device to solicit transmissions
from secondary devices

When the primary is ready to receive data, it must ask (poll)

each device in turn if it has anything to send

Secondary responds either with a NAK frame if it has nothing

to send or with data

If response is negative (a NAK frame), then primary polls next

secondary until it finds one with data to send

When response is positive , primary reads frame & returns an

acknowledgment (ACK frame), verifying its receipt
12.62
 Figure 12.19 Select and poll functions in polling access method

12.63
 Control Access 3) Token Passing
Token-passing: stations in a n/w are organized in a logical
ring
For each station, there is a predecessor & a successor

Right to this access has been passed from predecessor to the

current station-right will be passed to successor when the
current station has no more data to send

Right to access the channel is passed from one station to

another by a special packet called a token that circulates
through ring

Possession of the token gives the station the right to access

the channel & send its data.
12.64
 Control Access 3) Token Passing
Token management is needed for this access method
Stations must be limited in the time they can have possession
of the token
Token must be monitored to ensure it has not been lost or
destroyed – eg if a station that is holding the token fails, the
token will disappear from the network

Another function of token management is to assign priorities

to the stations & to the types of data being transmitted

And finally, token management is needed to make low-

priority stations release the token to highpriority stations

12.65
 Control Access 3) Token Passing
Logical Ring:
In token-passing network, stations do not have to be physically
connected in a ring; ring can be a logical one
High-speed Token Ring networks called FDDI (Fiber Distributed
Data Interface) & CDDI (Copper Distributed Data Interface) use dual
ring topology
Token Bus LAN, standardized by IEEE, uses bus ring topology
In a star ring topology, physical topology is a star- hub, however,
that acts as the connector - wiring inside the hub makes the ring;
This topology makes the network less prone to failure because if a
link goes down, it will be bypassed by hub & rest of stations can
operate. This topology is still used in the Token Ring LAN designed
by IBM

1
Figure 12.20 Logical ring and physical topology in token-passing access method

12.67
 12-3 CHANNELIZATION

Channelization is a multiple-access method in which

the available bandwidth of a link is shared in time,
frequency, or through code, between different stations

 In this section, we discuss three channelization

protocols.

Topics discussed in this section:

Frequency-Division Multiple Access (FDMA)
Time-Division Multiple Access (TDMA)
Code-Division Multiple Access (CDMA)

12.68
 Channelization- 1)FDMA
Frequency-Division Multiple Access (FDMA):

Available bandwidth is divided into frequency bands- Each

station is allocated a band to send its data
Station uses a bandpass filter to confine transmitter frequencies
To prevent station interferences, the allocated bands are
separated from one another by small guard bands
Data link layer in each station tells its physical layer to make a
bandpass signal from data passed to it- signal must be created in
the allocated band
No physical multiplexer at the physical layer
Signals created at each station are automatically bandpass-
filtered- They are mixed when they are sent to the common channel

12.69
 Figure 12.21 Frequency-division multiple access (FDMA)

12.70
 Note

In FDMA, the available bandwidth

of the common channel is divided into
bands that are separated by guard
bands.

12.71
 Channelization- 2)TDMA
In time-division multiple access (TDMA), stations share bandwidth
of channel in time
 Each station is allocated a time slot during which it can send data
Each station transmits its data in is assigned time slot.
main problem with TDMA lies in achieving synchronization between
the different stations
Each station needs to know beginning of its slot & location of its
slot- difficult because of propagation delays introduced in system if
stations are spread over a large area
 compensate for delays, we can insert guard times
Synchronization is normally accomplished by having some
synchronization bits at the beginning of each slot
data link layer in each station tells its physical layer to use allocated
time slot-no physical multiplexer at the physical layer

12.72
 Figure 12.22 Time-division multiple access (TDMA)

12.73
 Note

In TDMA, the bandwidth is just one

channel that is timeshared between
different stations.

12.74
 Channelization- 3)CDMA

CDMA differs from FDMA because only one channel

occupies the entire bandwidth of the link

 It differs from TDMA because all stations can send

data simultaneously; there is no timesharing

12.75
 Note

In CDMA, one channel carries all

transmissions simultaneously.

12.76
 Figure 12.23 Simple idea of communication with code
Assume we have four stations 1, 2, 3, & 4 connected to the same channel. Data from
station 1 are d1 … Code assigned to the first station is c1... We assume that the assigned
codes have two properties.
1. If we multiply each code by another, we get O.
2. If we multiply each code by itself, we get 4 (no. of stations).
Station 1 multiplies (a special kind of multiplication) its data by its code to get d1.c1
Data that go on the channel are the sum of all these terms

12.77
 Figure 12.23 Simple idea of communication with code
Any station that wants to receive data from one of the other three , multiplies
the data on the channel by the code of the sender.
suppose stations 1 & 2 are talking to each other. Station 2 wants to hear
what station 1 is saying. It multiplies the data on the channel by c1 the code
of station 1.
Because (c1 . c1) is 4, but (c2 . c1), (c3 . c1), and (c4 . c1) are all 0s, station 2
divides the result by 4 to get the data from station 1.
data =(d1. c1 + d2.c2 +d3.c3 + d4.c4) . c1
=d1.c1 . c1+ d2. c2 . c1 + d3 . c3 . c1 + d4 . C4. c1 =4 X d1

12.78
 Figure 12.24 Chip sequences
CDMA is based on coding theory.
Each station is assigned a code, which is a sequence of
numbers called chips, as shown - codes are for the previous
example.
Later we show how we chose these sequences.
For now, we need to know that we did not choose the
sequences randomly; they were carefully selected.
They are called orthogonal sequences and have the specific
properties:

12.79
 Figure 12.24 Chip sequences
Orthogonal sequences have the following properties:
1. Each sequence is made of N elements, where N is the number
of stations.
2. If we multiply a sequence by a number, every element in the
sequence is multiplied by that element- multiplication of a
sequence by a scalar. Eg 2.[+1 +1-1-1]=[+2+2-2-2]
3. If we multiply two equal sequences, element by element, and
add the results, we get N, where N is the number of elements in
the each sequence- called the inner product of two equal
sequences. eg [+1 +1 -1 -1]· [+1 +1 -1 -1] = 1 + 1 + 1 + 1 = 4
4. If we multiply two different sequences, element by element,
and add the results,we get 0- inner product of two different
sequences.[+1 +1 -1 -1] . [+1 +1 +1 +1] = 1 + 1 - 1 - 1 = 0
5. Adding two sequences means adding the corresponding
elements. The result is another sequence. For example,
[+1+1-1-1]+[+1+1+1+1]=[+2+2 00]
12.80
 Figure 12.25 Data representation in CDMA

We follow these rules for encoding:

If a station needs to send a 0 bit, it encodes it as -1;

if it needs to send a 1 bit, it encodes it as +1.

When a station is idle, it sends no signal, which is

interpreted as a 0.

12.81
 Figure 12.26 Sharing channel in CDMA-simple example

Simple example: four stations share the link during a 1-bit

interval.
The procedure can easily be repeated for additional
intervals.
We assume that stations 1 and 2 are sending a 0 bit and
channel 4 is sending a 1 bit. Station 3 is silent.
Data at the sender site are translated to -1, -1, 0, and +1.
Each station multiplies the corresponding number by its
chip
Result is a new sequence which is sent to the channel. For
simplicity, we assume that all stations send the resulting
sequences at the same time.
The sequence on the channel is the sum of all four
sequences
12.82
 Figure 12.26 Sharing channel in CDMA

12.83
 Figure 12.27 Digital signal created by four stations in CDMA
Signal Level
The process can be better understood if we show the digital signal produced by each
station and the data recovered at the destination. fig shows the corresponding signals
for each station (using NRZ-L for simplicity) and the signal that is on the common
channel.

12.84
 Figure 12.28 Decoding of the composite signal for one in CDMA
Fig shows how station 3 can detect the data sent by station 2 by using the
code for station 2. The total data on the channel are multiplied (inner product operation)
by the signal representing station 2 chip code to get a new signal. The station then
integrates and adds the area under the signal, to get the value -4, which is divided by 4
and interpreted as bit O.

12.85
 Figure 12.29 General rule and examples of creating Walsh tables
Sequence Generation
To generate chip sequences, we use a Walsh table -a two-dimensional table with an
equal number of rows and columns, as shown
In the Walsh table, each row is a sequence of chips. W1 for a one-chip sequence has
one row and one column. We can choose -1 or +1 for the chip for this trivial table.
According to Walsh, if we know the table for N sequences WN we can create
the table for 2N sequences W2N. The WN with the overbar WN stands for the
complement of WN' where each +1 is changed to -1 and vice versa.
Figure 12.29 also shows how we can create W2 and W4 from WI' After we select WI,
W2

12.86
 Note

The number of sequences in a Walsh

table needs to be N = 2m.

12.87
 Example 12.6

Find the chips for a network with

a. Two stations b. Four stations

Solution
We can use the rows of W2 and W4 in Figure 12.29:
a. For a two-station network, we have
[+1 +1] and [+1 −1].

b. For a four-station network we have

[+1 +1 +1 +1], [+1 −1 +1 −1],
[+1 +1 −1 −1], and [+1 −1 −1 +1].

12.88
 Example 12.7

What is the number of sequences if we have 90 stations in

our network?

Solution
The number of sequences needs to be 2m. We need to
choose m = 7 and N = 27 or 128. We can then use 90
of the sequences as the chips.

12.89
 Example 12.8

Prove that a receiving station can get the data sent by a

specific sender if it multiplies the entire data on the
channel by the sender’s chip code and then divides it by
the number of stations.

Solution
Let us prove this for the first station, using our previous
four-station example. We can say that the data on the
channel
D = (d1 ⋅ c1 + d2 ⋅ c2 + d3 ⋅ c3 + d4 ⋅ c4).
The receiver which wants to get the data sent by station 1
multiplies these data by c1.
12.90
 Example 12.8 (continued)

When we divide the result by N, we get d1 .

12.91
 Exercise problem

Recreate the W2 and W4 tables in Figure 12.29

using WI = [-1]. Compare the recreated tables with
the ones in Figure 12.29.

12.92