Unit - II

Wireless Transmission - Communication Satellites - Telephone System:

Structure, Local Loop, Trunks and Multiplexing and Switching. Data Link Layer:
Design Issues - Error Detection and Correction.

2.1 WIRELESS TRANSMISSION

Unguided media, also called as wireless communication, transport electromagnetic

waves without using a physical conductor. The signals propagate through air (or sometimes
water).

1. The Electromagnetic Spectrum

2. Radio Transmission

3. Microwave Transmission

4. Infrared and Millimeter Waves

5. Lightwave Transmission

1. The Electromagnetic Spectrum

The number of oscillations per second of a wave is called its frequency, f, and is
measured in Hz (in honor of Heinrich Hertz). The distance between two consecutive maxima
(or minima) is called the wavelength, which is universally designated by the Greek letter λ
(lambda). In a vacuum, all electromagnetic waves travel at the same speed, no matter what
their frequency. This speed, usually called the speed of light, c, is approximately 3 × 108
m/sec, or about 1 foot (30 cm) per nanosecond.

The fundamental relation between f, λ, and c (in a vacuum) is λf = c

Most transmissions use a relatively narrow frequency band (i.e., Δf / f << 1). They
concentrate their signals in this narrow band to use the spectrum efficiently and obtain
reasonable data rates by transmitting with enough power. However, in some cases, a wider
band is used, with three variations.

In frequency hopping spread spectrum, the transmitter hops from frequency to

frequency hundreds of times per second. It is popular for military communication because it

1
makes transmissions hard to detect and next to impossible to jam. It also offers good
resistance to multipath fading and narrowband interference because the receiver will not be
stuck on an impaired frequency for long enough to shut down communication.

The second form of spread spectrum, direct sequence spread spectrum, uses a code
sequence to spread the data signal over a wider frequency band. It is widely used
commercially as a spectrally efficient way to let multiple signals share the same frequency
band. These signals can be given different codes, a method called CDMA (Code Division
Multiple Access).

A third method of communication with a wider band is UWB (Ultra- WideBand)

communication. UWB sends a series of rapid pulses, varying their positions to communicate
information. The rapid transitions lead to a signal that is spread thinly over a very wide
frequency band. UWB is defined as signals that have a bandwidth of at least 500 MHz or at
least 20% of the center frequency of their frequency band.

2. Radio Transmission

Radio waves are the electromagnetic waves that are transmitted in all the directions of
free space. Radio waves are omnidirectional, i.e., the signals are propagated in all the
directions. The range in frequencies of radio waves is from 3Khz to 10 khz. In the case of
radio waves, the sending and receiving antenna are not aligned, i.e., the wave sent by the
sending antenna can be received by any receiving antenna. An example of the radio wave
is FM radio.

Figure 2.1: Radio Waves

Applications Of Radio waves:

 A Radio wave is useful for multicasting when there is one sender and many receivers.
 An FM radio, television, cordless phones are examples of a radio wave.
2
Advantages Of Radio transmission:

 Radio transmission is mainly used for wide area networks and mobile cellular phones.
 Radio waves cover a large area, and they can penetrate the walls.
 Radio transmission provides a higher transmission rate.

Figure 2.2: Radio Waves

1. Very Low Frequency (VLF) waves propagate as surface waves, usually through air, but
sometimes also through water. VLF waves do not suffer attenuation, but atmospheric noise
affects them. VLF waves are usually used for long-range radio navigation and submarine
communication.

2. Low Frequency (LF) waves also propagate as surface waves. Attenuation is higher during
the daytime. These wave are used for long MCA-301 92 range radio navigation or navigation
locators.

3. Middle Frequency (MF) waves rely on line-of-sight antennas to increase and control
absorption problems. These waves are used for AM radio, radio direction finding and
emergency frequencies.

4. High Frequency (HF) waves are used for amateur radio, citizen's band radio, international
broadcasting, military communication, telephone, telegraph and facsimile communication.

5. Very High Frequency (VHF) waves use line-of-sight propagation, and are used for VHF
television, FM radio, aircraft AM radio and aircraft navigation.

6. Ultra High Frequency (UHF) waves use line-of-sight propagation. They are used for
television, mobile phone, cellular radio, paging and microwave links.

3
7. Super High Frequency (SHF) waves are transmitted as either line-ofsight or into the
space. They are used for terrestrial and satellite microwave and radar communication.

8. Extreme high Frequency (EHF) waves are transmitted into space, and are used for
scientific applications such as radar, satellite and experimental communication.

3. Microwave Transmission

Electromagnetic waves having frequencies between 1 and 300 GHz are called
microwaves. Microwaves are unidirectional. The sending and receiving antennas need to be
aligned. The unidirectional property has an obvious advantage. A pair of antennas can be
aligned without interfering with another pair of aligned antennas.

Microwave communication is so widely used for long-distance telephone

communication, mobile phones, television distribution, and other purposes that a severe
shortage of spectrum has developed. It has several key advantages over fiber. The main one is
that no right of way is needed to lay down cables. By buying a small plot of ground every 50
km and putting a microwave tower on it, one can bypass the telephone system entirely. This
is how MCI managed to get started as a new long-distance telephone company so quickly.

Microwave is also relatively inexpensive. Putting up two simple towers (which can be
just big poles with four guy wires) and putting antennas on each one may be cheaper than
burying 50 km of fiber through a congested urban area or up over a mountain, and it may also
be cheaper than leasing the telephone company’s fiber, especially if the telephone company
has not yet even fully paid for the copper it ripped out when it put in the fiber.

Unidirectional Antenna

Microwaves need unidirectional antennas that send out signals in one direction. Two
types of antennas are used for microwave communications: the parabolic dish and the horn

4
Figure 2.3: Types of Antenna

Applications:

Microwaves are used for unicast communication such as cellular telephones, satellite
networks, and wireless LANs

4. Infrared and Millimeter Waves

Unguided infrared waves are widely used for short-range communication. The remote
controls used for televisions, VCRs, and stereos all use infrared communication. They are
relatively directional, cheap, and easy to build but have a major drawback: they do not pass
through solid objects. On the other hand, the fact that infrared waves do not pass through
solid walls well is also a plus. It means that an infrared system in one room of a building will
not interfere with a similar system in adjacent rooms or buildings.

Infrared waves, with frequencies from 300 GHz to 400 THz (wavelengths from 1 mm
to 770 nm), can be used for short-range communication. Infrared waves, having high
frequencies, cannot penetrate walls. This advantageous characteristic prevents interference
between one system and another; a short range communication system in one room cannot be
affected by another system in the next room.

When we use our infrared remote control, we do not interfere with the use of the
remote by our neighbors. Infrared signals useless for long-range communication. In addition,
we cannot use infrared waves outside a building because the sun's rays contain infrared
waves that can interfere with the communication. Infrared communication has a limited use
on the desktop, for example, to connect notebook computers and printers with the IrDA
(Infrared Data Association) standard, but it is not a major player in the communication game.

Applications:

Infrared signals can be used for short-range communication in a closed area using line-of-
sight propagation.

5. Light Transmission

Optical signaling using lasers is inherently unidirectional, so each end needs its own
laser and its own photodetector. This scheme offers very high bandwidth at very low cost and

5
is relatively secure because it is difficult to tap a narrow laser beam. It is also relatively easy
to install and, unlike microwave transmission, does not require an FCC license.

One of the authors (AST) once attended a conference at a modern hotel in Europe at
which the conference organizers thoughtfully provided a room full of terminals to allow the
attendees to read their email during boring presentations. Since the local PTT was unwilling
to install a large number of telephone lines for just 3 days, the organizers put a laser on the
roof and aimed it at their university’s computer science building a few kilometers away. They
tested it the night before the conference and it worked perfectly. At 9 A.M. on a bright, sunny
day, the link failed completely and stayed down all day. The pattern repeated itself the next
two days. It was not until after the conference that the organizers discovered the problem:
heat from the sun during the daytime caused convection currents to rise up from the roof of
the building, as shown in Fig. 2-14. This turbulent air diverted the beam and made it dance
around the detector, much like a shimmering road on a hot day. The lesson here is that to
work well in difficult conditions as well as good conditions, unguided optical links need to be
engineered with a sufficient margin of error.

Figure 2.4: Light Transmission

Unguided optical communication may seem like an exotic networking technology

today, but it might soon become much more prevalent. We are surroundedby cameras (that
sense light) and displays (that emit light using LEDs and other technology). Data
communication can be layered on top of these displays by encoding information in the pattern
at which LEDs turn on and off that is below the threshold of human perception.
Communicating with visible light in this way is inherently safe and creates a low-speed
network in the immediate vicinity of the display. This could enable all sorts of fanciful
ubiquitous computing scenarios. The flashing lights on emergency vehicles might alert

6
nearby traffic lights and vehicles to help clear a path. Informational signs might broadcast
maps. Even festive lights might broadcast songs that are synchronized with their display.

2.2 COMMUNICATION SATELLITES

A communication satellite is an artificial satellite that acts as a large repeater in the

sky. It receives signals from the source transmitter, amplifies using transponders, and relays
them to the receiver. Thus, it creates a communication channel between locations of the earth
that would not have been able to communicate due to long distance or obstruction by earth’s
curvature. Communication satellites may be owned by government or private organizations.
Presently, there are more than 2000 communication satellites in the sky. Some of its uses are
as follows.

 Internet
 Military operations
 Television
 Telephone
 Radio

Communication satellites are broadly categorized into three types depending upon the
orbit in which they are placed.

Figure 2.5: Communication satellites

Communication satellites and some of their properties,including altitude above the earth,
round-trip delay time and number of satellites needed for global coverage

Geostationary Satellite (GEO) − They are at 36,000 km from the earth’s surface. They have
same orbital period as earth’s rotation. So they appear to be still in the sky. At least 3 GEOs
are needed for global coverage.

7
Table 2.1 : The principal satellite bands

A recent development in the communication satellite world is the development of

low-cost microstations, sometimes called VSATs (Very Small Aperture Terminals)
(Abramson, 2000). These tiny terminals have 1-meter or smaller antennas (versus 10 m for a
standard GEO antenna) and can put out about 1 watt of power. The uplink is generally good
for up to 1 Mbps, but the downlink is often up to several megabits/sec.

Figure 2.6: VSATs using a hub

Medium Earth Orbit Satellite (MEO) − They are placed between the two Van Allen belts,
at a distance between 2,000 km to 36,000 km from the earth’s surface. At least 10 MEOs are
needed for global coverage. Accordingly, they must be tracked as they move through the sky.
Because they are lower than the GEOs, they have a smaller footprint on the ground and
require less powerful transmitters to reach them. Currently they are used for navigation
systems rather than telecommunications, so we will not examine them further here. The
constellation of roughly 30 GPS (Global Positioning System) satellites orbiting at about
20,200 km are examples of MEO satellites.

Low Earth Orbit Satellite (LEO) − They are situated below the Lower Van Allen belt.
Their orbital altitude is 160 km to 2000 km. For global coverage, as high as 50 LEOs are
required. For the first 30 years of the satellite era, low-orbit satellites were rarely used
because they zip into and out of view so quickly. Each satellite has a maximum of 48 cells

8
(spot beams) and a capacity of 3840 channels, some of which are used for paging and
navigation, while others are used for data and voice.

2.3 PUBLIC SWITCHED TELEPHONE SYSTEM

PSTN (Public Switched Telephone Network), were usually designed many years ago,
with a completely different goal in mind: transmitting the human voice in a more-or-less
recognizable form. Their suitability for use in computer-computer communication is often
marginal at best. To see the size of the problem, consider that a cheap commodity cable
running between two computers can transfer data at 1 Gbps or more. In contrast, typical
ADSL, the blazingly fast alternative to a telephone modem, runs at around 1 Mbps. The
difference between the two is the difference between cruising in an airplane and taking a
leisurely stroll.

In the following sections we will describe the telephone system and show how it
works.

i) Structure of the Telephone System

Alexander Graham Bell patented the telephone in 1876 , there was an enormous
demand for his new invention. The initial market was for the sale of telephones, which came
in pairs. It was up to the customer to string a single wire between them. If a telephone owner
wanted to talk to n other telephone owners, separate wires had to be strung to all n houses.
Within a year, the cities were covered with wires passing over houses and trees in a wild
jumble. It became immediately obvious that the model of connecting every telephone to
every other telephone, as shown in Fig.(a), was not going to work.

To his credit, Bell saw this problem early on and formed the Bell Telephone
Company, which opened its first switching office in 1878. The company ran a wire to each
customer’s house or office. To make a call, the customer would crank the phone to make a
ringing sound in the telephone company office to attract the attention of an operator, who
would then manually connect the caller to the callee by using a short jumper cable to connect
the caller to the callee. The model of a single switching office is illustrated in Fig.(b).

Pretty soon, Bell System switching offices were springing up everywhere and people
wanted to make long-distance calls between cities, so the Bell System began to connect the
switching offices. The original problem soon returned: to connect every switching office to

9
every other switching office by means of a wire between them quickly became
unmanageable, so second-level switching offices were invented. After a while, multiple
second-level offices were needed, as illustrated in Fig. (c). Eventually, the hierarchy grew to
five levels

Figure 2.7: (a) Fully-interconnected network. (b) Centralized switch (c) Two-level
hierarchy

By 1890, the three major parts of the telephone system were in place: the switching
offices, the wires between the customers and the switching offices (bynow balanced,
insulated, twisted pairs instead of open wires with an earth return), and the long-distance
connections between the switching offices.

If a subscriber attached to a given end office calls another subscriber attached to the
same end office, the switching mechanism within the office sets up a direct electrical
connection between the two local loops. This connection remains intact for the duration of
the call.

If the called telephone is attached to another end office, a different procedure has to
be used. Each end office has a number of outgoing lines to one or more nearby switching
centers, called toll offices (or, if they are within the same local area, tandem offices). These
lines are called toll connecting trunks. The number of different kinds of switching centers
and their topology varies from country to country depending on the country’s telephone
density.

If both the caller’s and callee’s end offices happen to have a toll connecting trunk to
the same toll office (a likely occurrence if they are relatively close by), the connection may
be established within the toll office. A telephone network consisting only of telephones (the
small dots), end offices (the large dots), and toll offices (the squares) is shown in Fig. (c).

10
If the caller and callee do not have a toll office in common, a path will have to be
established between two toll offices. The toll offices communicate with each other via high-
bandwidth intertoll trunks (also called interoffice trunks). Prior to the 1984 breakup of
AT&T, the U.S. telephone system used hierarchical routing to find a path, going to higher
levels of the hierarchy until there was a switching office in common. This was then replaced
with more flexible, nonhierarchical routing. Figure below shows how a long-distance
connection might be routed.

In summary, the telephone system consists of three major components:

1. Local loops (analog twisted pairs going to houses and businesses).

2. Trunks (digital fiber optic links connecting the switching offices).

3. Switching offices (where calls are moved from one trunk to another).

Figure 2.8: A typical circuit route for a medium-distance call.

ii) The Politics of Telephones

For decades prior to 1984, the Bell System provided both local and long-distance
service throughout most of the United States. The United States was divided up into 164
LATAs (Local Access and Transport Areas). Very roughly, a LATA is about as big as the
area covered by one area code. Within each LATA, there was one LEC (Local Exchange
Carrier) with a monopoly on traditional telephone service within its area. The most important
LECs were the BOCs, although some LATAs contained one or more of the 1500 independent
telephone companies operating as LECs.

The new feature was that all inter-LATA traffic was handled by a different kind of
company, an IXC (IntereXchange Carrier). Originally, AT&T Long Lines was the only
serious IXC, but now there are well-established competitors such as Verizon and Sprint in the
IXC business. One of the concerns at the breakup was to ensure that all the IXCs would be
treated equally in terms of line quality, tariffs, and the number of digits their customers would
have to dial to use them. The way this is handled is illustrated in Fig. 2-31.

11
Here we see three example LATAs, each with several end offices. LATAs 2 and 3
also have a small hierarchy with tandem offices (intra-LATA toll offices). Any IXC that
wishes to handle calls originating in a LATA can build a switching office called a POP (Point
of Presence) there. The LEC is required to connect each IXC to every end office, either
directly, as in LATAs 1 and 3, or indirectly, as in LATA 2. Furthermore, the terms of the
connection, both technical and financial, must be identical for all IXCs. This requirement
enables, a subscriber in, say, LATA 1, to choose which IXC to use for calling subscribers in
LATA 3.

As part of the MFJ, the IXCs were forbidden to offer local telephone service and the
LECs were forbidden to offer inter-LATA telephone service, although both were free to enter
any other business, such as operating fried chicken restaurants. In 1984, that was a fairly
unambiguous statement. Unfortunately, technology has a funny way of making the law
obsolete. Neither cable television nor mobile phones were covered by the agreement. As
cable television went from one way to two way and mobile phones exploded in popularity,
both LECs and IXCs began buying up or merging with cable and mobile operators.

Figure 2.9: The Politics of Telephones

• The relationship of Local Access and Transport Areas (LATAs), Local Exchange
Carriers (LECs), and IntereXchange Carriers (IXCs).

• All the circles are LEC switching offices. Each hexagon belongs to the IXC whose
number is on it.

iii) The Local Loop: Modems, ADSL, and Wireless

a) Telephone Modems

12
A device that converts between a stream of digital bits and an analog signal that
represents the bits is called a modem, which is short for ‘‘modulator demodulator.’’ Modems
come in many varieties: telephone modems, DSL modems, cable modems, wireless modems,
etc. The modem may be built into the computer (which is now common for telephone
modems) or be a separate box (which is common for DSL and cable modems). Logically, the
modem is inserted between the (digital) computer and the (analog) telephone system, as seen
in Figure below.

Figure 2.10: Telephone modem

Telephone modems are used to send bits between two computers over a voice-grade
telephone line, in place of the conversation that usually fills the line. The main difficulty in
doing so is that a voice-grade telephone line is limited to 3100 Hz, about what is sufficient to
carry a conversation.

b) Digital Subscriber Lines

Initially, there were many overlapping high-speed offerings, all under the general name
of xDSL (Digital Subscriber Line), for various x. Services with more bandwidth than
standard telephone service are sometimes called broadband, although the term really is more
of a marketing concept than a specific technical concept.

A typical ADSL arrangement is shown in Figure below. In this scheme, a telephone

company technician must install a NID (Network Interface Device) on the customer’s
premises. This small plastic box marks the end of the telephone company’s property and the
start of the customer’s property. Close to the NID (or sometimes combined with it) is a
splitter, an analog filter that separates the 0–4000-Hz band used by POTS from the data. The
POTS signal is routed to the existing telephone or fax machine. The data signal is routed to
an ADSL modem, which uses digital signal processing to implement OFDM. Since most
ADSL modems are external, the computer must be connected to them at high speed. Usually,
this is done using Ethernet, a USB cable, or 802.11.

13
At the other end of the wire, on the end office side, a corresponding splitter is installed.
Here, the voice portion of the signal is filtered out and sent to the normal voice switch. The
signal above 26 kHz is routed to a new kind of device called a DSLAM (Digital Subscriber
Line Access Multiplexer), which contains the same kind of digital signal processor as the
ADSL modem. Once the bits have been recovered from the signal, packets are formed and
sent off to the ISP. This complete separation between the voice system and ADSL makes it
relatively easy for a telephone company to deploy ADSL. All that is needed is buying a
DSLAM and splitter and attaching the ADSL subscribers to the splitter. Other high-
bandwidth services (e.g., ISDN) require much greater changes to the existing switching
equipment.

Figure 2.11: Digital Subscriber Line

c) Fiber To The Home

Deployed copper local loops limit the performance of ADSL and telephone modems.
To let them provide faster and better network services, telephone companies are upgrading
local loops at every opportunity by installing optical fiber all the way to houses and offices.
The result is called FttH (Fiber To The Home).

While FttH technology has been available for some time, deployments only began to
take off in 2005 with growth in the demand for high-speed Internet from customers used to
DSL and cable who wanted to download movies.

14
Usually, the fibers from the houses are joined together so that only a single fiber
reaches the end office per group of up to 100 houses. In the downstream direction, optical
splitters divide the signal from the end office so that it reaches all the houses. Encryption is
needed for security if only one house should be able to decode the signal. In the upstream
direction, optical combiners merge the signals from the houses into a single signal that is
received at the end office. This architecture is called a PON (Passive Optical Network), and it
is shown in Fig. 2-36. It is common to use one wavelength shared between all the houses for
downstream transmission, and another wavelength for upstream transmission.

Figure 2.12: Passive optical network for Fiber To The Home

iv) Trunks and Multiplexing

Trunks in the telephone network are not only much faster than the local loops, they
are different in two other respects. The core of the telephone network carries digital
information, not analog information; that is, bits not voice. This necessitates a conversion at
the end office to digital form for transmission over the longhaul trunks. The trunks carry
thousands, even millions, of calls simultaneously. This sharing is important for achieving
economies of scale, since it costs essentially the same amount of money to install and
maintain a high-bandwidth trunk as a low-bandwidth trunk between two switching offices. It
is accomplished with versions of TDM and FDM multiplexing.

a) Digitizing Voice Signals

FDM techniques were used for many years to multiplex 4000-Hz voice channels into
larger and larger units. For example, 12 calls in the 60 kHz–to–108 kHz band is known as a
group and five groups (a total of 60 calls) are known as a supergroup, and so on. These
FDM methods are still used over some copper wires and microwave channels. However,
FDM requires analog circuitry and is not amenable to being done by a computer. In contrast,
TDM can be handled entirely by digital electronics, so it has become far more widespread in
recent years. Since TDM can only be used for digital data and the local loops produce analog

15
signals, a conversion is needed from analog to digital in the end office, where all the
individual local loops come together to be combined onto outgoing trunks.

b) Time Division Multiplexing

TDM based on PCM is used to carry multiple voice calls over trunks by sending a
sample from each call every 125 μsec. When digital transmission began emerging as a
feasible technology, ITU (then called CCITT) was unable to reach agreement on an
international standard for PCM. Consequently, a variety of incompatible schemes are now in
use in different countries around the world.

The method used in North America and Japan is the T1 carrier, depicted in Fig. 2-37.
(Technically speaking, the format is called DS1 and the carrier is called T1, but following
widespread industry tradition, we will not make that subtle distinction here.) The T1 carrier
consists of 24 voice channels multiplexed together. Each of the 24 channels, in turn, gets to
insert 8 bits into the output stream.

Figure 2.13: Each channel has 8bits, 24 channels and one framing bit form a frame of
125 µsec The T1 carrier (1.544 Mbps).

c) SONET/SDH

In 1985, Bellcore, the RBOC’s research arm, began working on a standard, called
SONET (Synchronous Optical NETwork). The SONET design had four major goals.

First and foremost, SONET had to make it possible for different carriers to
interwork. Achieving this goal required defining a common signaling standard with respect to
wavelength, timing, framing structure, and other issues.

Second, some means was needed to unify the U.S., European, and Japanese digital
systems, all of which were based on 64-kbps PCM channels but combined them in different
(and incompatible) ways.

16
Third, SONET had to provide a way to multiplex multiple digital channels. At the
time SONET was devised, the highest-speed digital carrier actually used widely in the United
States was T3, at 44.736 Mbps. T4 was defined, but not used much, and nothing was even
defined above T4 speed. Part of SONET’s mission was to continue the hierarchy to
gigabits/sec and beyond. A standard way to multiplex slower channels into one SONET
channel was also needed.

Fourth, SONET had to provide support for operations, administration, and

maintenance (OAM), which are needed to manage the network. Previous systems did not do
this very well.

Figure 2.14: SONET and SDH multiplex rates.

d) Wavelength Division Multiplexing

A form of frequency division multiplexing is used as well as TDM to harness the

tremendous bandwidth of fiber optic channels. It is called WDM (Wavelength Division
Multiplexing). The basic principle of WDM on fibers is depicted in Fig. 2-41. Here four
fibers come together at an optical combiner, each with its energy present at a different
wavelength. The four beams are combined onto a single shared fiber for transmission to a
distant destination. At the far end, the beam is split up over as many fibers as there were on
the input side. Each output fiber contains a short, specially constructed core that filters out all
but one wavelength. The resulting signals can be routed to their destination or recombined in
different ways for additional multiplexed transport.

17
Figure 2.15: Wavelength division multiplexing

v) Switching techniques

In large networks, there can be multiple paths from sender to receiver. The switching
technique will decide the best route for data transmission. Switching technique is used to
connect the systems for making one-to-one communication.

Classification Of Switching Techniques

Figure 2.16: Classification Of Switching Techniques

1. Circuit Switching

 Circuit switching is a switching technique that establishes a dedicated path between sender
and receiver.
 In the Circuit Switching Technique, once the connection is established then the dedicated
path will remain to exist until the connection is terminated.
 Circuit switching in a network operates in a similar way as the telephone works.
 A complete end-to-end path must exist before the communication takes place.
 In case of circuit switching technique, when any user wants to send the data, voice, video,
a request signal is sent to the receiver then the receiver sends back the acknowledgment to

18
ensure the availability of the dedicated path. After receiving the acknowledgment, dedicated
path transfers the data.
 Circuit switching is used in public telephone network. It is used for voice transmission.
 Fixed data can be transferred at a time in circuit switching technology.

Communication through circuit switching has 3 phases:3Mgers in SQL (Hindi)

 Circuit establishment
 Data transfer
 Circuit Disconnect

Figure 2.17: Circuit Switching

Circuit Switching can use either of the two technologies:

Space Division Switches:

 Space Division Switching is a circuit switching technology in which a single transmission

path is accomplished in a switch by using a physically separate set of crosspoints.
 Space Division Switching can be achieved by using crossbar switch. A crossbar switch is a
metallic crosspoint or semiconductor gate that can be enabled or disabled by a control unit.
 The Crossbar switch is made by using the semiconductor. For example, Xilinx crossbar
switch using FPGAs.
 Space Division Switching has high speed, high capacity, and nonblocking switches.

Space Division Switches can be categorized in two ways:

i) Crossbar Switch
ii) Multistage Switch

i) Crossbar Switch

19
The Crossbar switch is a switch that has n input lines and n output lines. The crossbar switch
has n2 intersection points known as crosspoints.

Disadvantage of Crossbar switch:

The number of crosspoints increases as the number of stations is increased. Therefore, it

becomes very expensive for a large switch. The solution to this is to use a multistage switch.

ii) Multistage Switch

 Multistage Switch is made by splitting the crossbar switch into the smaller units and then
interconnecting them.
 It reduces the number of crosspoints.
 If one path fails, then there will be an availability of another path.

Advantages Of Circuit Switching:

 In the case of Circuit Switching technique, the communication channel is dedicated.

 It has fixed bandwidth.

Disadvantages Of Circuit Switching:

 Once the dedicated path is established, the only delay occurs in the speed of data
transmission.
 It takes a long time to establish a connection approx 10 seconds during which no data can
be transmitted.
 It is more expensive than other switching techniques as a dedicated path is required for
each connection.
 It is inefficient to use because once the path is established and no data is transferred, then
the capacity of the path is wasted.
 In this case, the connection is dedicated therefore no other data can be transferred even if
the channel is free.

2. Message Switching

 Message Switching is a switching technique in which a message is transferred as a

complete unit and routed through intermediate nodes at which it is stored and forwarded.

20
 In Message Switching technique, there is no establishment of a dedicated path between the
sender and receiver.
 The destination address is appended to the message. Message Switching provides a
dynamic routing as the message is routed through the intermediate nodes based on the
information available in the message.
 Message switches are programmed in such a way so that they can provide the most
efficient routes.
 Each and every node stores the entire message and then forward it to the next node. This
type of network is known as store and forward network.
 Message switching treats each message as an independent entity.

Figure 2.18: Message Switching

Advantages Of Message Switching

 Data channels are shared among the communicating devices that improve the efficiency of
using available bandwidth.
 Traffic congestion can be reduced because the message is temporarily stored in the nodes.
 Message priority can be used to manage the network.
 The size of the message which is sent over the network can be varied. Therefore, it
supports the data of unlimited size.

Disadvantages Of Message Switching

 The message switches must be equipped with sufficient storage to enable them to store the
messages until the message is forwarded.
 The Long delay can occur due to the storing and forwarding facility provided by the
message switching technique.

3.Packet Switching

21
 The packet switching is a switching technique in which the message is sent in one go, but
it is divided into smaller pieces, and they are sent individually.
 The message splits into smaller pieces known as packets and packets are given a unique
number to identify their order at the receiving end.
 Every packet contains some information in its headers such as source address, destination
address and sequence number.
 Packets will travel across the network, taking the shortest path as possible.
 All the packets are reassembled at the receiving end in correct order.
 If any packet is missing or corrupted, then the message will be sent to resend the message.
 If the correct order of the packets is reached, then the acknowledgment message will be
sent.

Figure 2.19: Packet Switching

Approaches Of Packet Switching:

There are two approaches to Packet Switching:

Datagram Packet switching:

 It is a packet switching technology in which packet is known as a datagram, is considered

as an independent entity. Each packet contains the information about the destination and
switch uses this information to forward the packet to the correct destination.
 The packets are reassembled at the receiving end in correct order.
 In Datagram Packet Switching technique, the path is not fixed.
 Intermediate nodes take the routing decisions to forward the packets.
 Datagram Packet Switching is also known as connectionless switching.

Virtual Circuit Switching

 Virtual Circuit Switching is also known as connection-oriented switching.

22
 In the case of Virtual circuit switching, a preplanned route is established before the
messages are sent.
 Call request and call accept packets are used to establish the connection between sender
and receiver.
 In this case, the path is fixed for the duration of a logical connection.

Let's understand the concept of virtual circuit switching through a diagram:

Figure 2.20: Virtual Circuit Switching

 In the above diagram, A and B are the sender and receiver respectively. 1 and 2 are the
nodes.
 Call request and call accept packets are used to establish a connection between the sender
and receiver.
 When a route is established, data will be transferred.
 After transmission of data, an acknowledgment signal is sent by the receiver that the
message has been received.
 If the user wants to terminate the connection, a clear signal is sent for the termination.

Differences b/w Datagram approach and Virtual Circuit approach

Datagram approach Virtual Circuit approach

Node takes routing decisions to forward the packets. Node does not take any routing decision.

Congestion cannot occur as all the packets travel in Congestion can occur when the node is busy,
different directions. and it does not allow other packets to pass
through.

23
It is more flexible as all the packets are treated as an It is not very flexible.
independent entity.

Advantages Of Packet Switching:

 Cost-effective: In packet switching technique, switching devices do not require

massive secondary storage to store the packets, so cost is minimized to some extent.
Therefore, we can say that the packet switching technique is a cost-effective technique.
 Reliable: If any node is busy, then the packets can be rerouted. This ensures that the
Packet Switching technique provides reliable communication.
 Efficient: Packet Switching is an efficient technique. It does not require any
established path prior to the transmission, and many users can use the same communication
channel simultaneously, hence makes use of available bandwidth very efficiently.

Disadvantages Of Packet Switching:

 Packet Switching technique cannot be implemented in those applications that require

low delay and high-quality services.
 The protocols used in a packet switching technique are very complex and requires
high implementation cost.
 If the network is overloaded or corrupted, then it requires retransmission of lost
packets. It can also lead to the loss of critical information if errors are nor recovered.

2.4 DATA LINK LAYER FUNCTIONS (SERVICES)

1. Providing services to the network layer:

1 Unacknowledged connectionless service. Appropriate for low error rate and real-time
traffic. Ex: Ethernet
2.Acknowledged connectionless service. Useful in unreliable channels, WiFi.
Ack/Timer/Resend
3. Acknowledged connection-oriented service. Guarantee frames are received exactly
once and in the right order. Appropriate over long, unreliable links such as a satellite
channel or a long distance telephone circuit

2. Framing: Frames are the streams of bits received from the network layer into manageable
data units. This division of stream of bits is done by Data Link Layer.

24
3. Physical Addressing: The Data Link layer adds a header to the frame in order to define
physical address of the sender or receiver of the frame, if the frames are to be distributed to
different systems on the network.

4. Flow Control: A receiving node can receive the frames at a faster rate than it can process
the frame. Without flow control, the receiver's buffer can overflow, and frames can get lost.
To overcome this problem, the data link layer uses the flow control to prevent the sending
node on one side of the link from overwhelming the receiving node on another side of the
link. This prevents traffic jam at the receiver side.

5. Error Control: Error control is achieved by adding a trailer at the end of the frame.
Duplication of frames are also prevented by using this mechanism. Data Link Layers adds
mechanism to prevent duplication of frames.

i) Error detection: Errors can be introduced by signal attenuation and noise. Data Link
Layer protocol provides a mechanism to detect one or more errors. This is achieved by
adding error detection bits in the frame and then receiving node can perform an error check.

ii) Error correction: Error correction is similar to the Error detection, except that receiving
node not only detects the errors but also determine where the errors have occurred in the
frame.

6. Access Control: Protocols of this layer determine which of the devices has control over
the link at any given time, when two or more devices are connected to the same link

7. Reliable delivery: Data Link Layer provides a reliable delivery service, i.e., transmits the
network layer datagram without any error. A reliable delivery service is accomplished with
transmissions and acknowledgements. A data link layer mainly provides the reliable delivery
service over the links as they have higher error rates and they can be corrected locally, link at
which an error occurs rather than forcing to retransmit the data.

8. Half-Duplex & Full-Duplex: In a Full-Duplex mode, both the nodes can transmit the data
at the same time. In a Half-Duplex mode, only one node can transmit the data at the same
time.

2.4.1 DATA LINK LAYER DESIGN ISSUES

 Providing a well-defined service interface to the network layer.

25
 Dealing with transmission errors.
 Regulating the flow of data so that slow receivers are not swamped by fast senders

For this, the data link layer takes the packets it gets from the network layer and
encapsulates them into frames for transmission. Each frame contains a frame header, a
payload field for holding the packet, and a frame trailer

Figure 2.21: Frame

i) Services Provided to the Network Layer

 The function of the data link layer is to provide services to the network layer.
 The principal service is transferring data from the network layer on the source
machine to the network layer on the destination machine.
 The data link layer can be designed to offer various services.
 The actual services offered can vary from system to system.
 Three reasonable possibilities that are commonly provided are

1) Unacknowledged Connectionless service

2) Acknowledged Connectionless service

3) Acknowledged Connection-Oriented service

1. Unacknowledged Connectionless Service

Unacknowledged connectionless service consists of having the source machine send

independent frames to the destination machine without having the destination machine
acknowledge them. No logical connection is established beforehand or released afterward. If
a frame is lost due to noise on the line, no attempt is made to detect the loss or recover from it
in the data link layer. This class of service is appropriate when the error rate is very low so
that recovery is left to higher layers. It is also appropriate for real- time traffic, such as voice,

26
in which late data are worse than bad data. Most LANs use unacknowledged connectionless
service in the data link layer.

2. Acknowledged Connectionless Service

When this service is offered, there are still no logical connections used, but each
frame sent is individually acknowledged. In this way, the sender knows whether a frame has
arrived correctly. If it has not arrived within a specified time interval, it can be sent again.
This service is useful over unreliable channels, such as wireless systems. Adding Ack in the
DLL rather than in the Network Layer is just an optimization and not a requirement. If
individual frames are acknowledged and retransmitted, entire packets get through much
faster. On reliable channels, such as fiber, the overhead of a heavyweight data link protocol
may be unnecessary, but on wireless channels, with their inherent unreliability, it is well
worth the cost.

3. Acknowledged Connection-Oriented Service

Here, the source and destination machines establish a connection before any data are
transferred. Each frame sent over the connection is numbered, and the data link layer.
Guarantees that each frame sent is indeed received. Furthermore, it guarantees that each
frame is received exactly once and that all frames are received in the right order. When
connection-oriented service is used, transfers go through three distinct phases. In the first
phase, the connection is established by having both sides initialize variables and counters
needed to keep track of which frames have been received and which ones have not. In the
second phase, one or more frames are transmitted. In the third and final phase, the connection
is released, freeing up the variables, buffers, and other resources used to maintain the
connection

ii) Framing

DLL translates thephysical layer's raw bit stream into discrete units (messages) called
frames. How can frame be transmitted so the receiver can detect frame boundaries? That is,
how can the receiver recognize the start and end of a frame?

1. Byte count.

2. Flag bytes with byte stuffing.

3. Flag bits with bit stuffing.

27
4. Physical layer coding violations.

Figure 2.22: Payload

1. FRAMING – Byte count

The first framing method uses a field in the header to specify the number of characters
in the frame. When the data link layer at the destination sees the character count, it knows
how many characters follow and hence where the end of the frame is.

Figure 2.23: Framing

The trouble with this algorithm is that the count can be garbled by a transmission
error.

2. FRAMING – Flag bytes with byte stuffing.

Use reserved characters to indicate the start and end of a frame. For instance, use the
two-character sequence DLE STX (Data-Link Escape, Start of TeXt) to signal the beginning
of a frame, and the sequence DLE ETX (End of TeXt) to flag the frame's end. The second
framing method, Starting and ending character stuffing, gets around the problem of
resynchronization after an error by having each frame start with the ASCII character
sequence DLE STX and end with the sequence DLE ETX.

 Problem: What happens if the two-charactersequence DLE

ETX happens to appear in the frame itself?
 Solution: Use character stuffing; within the frame, replace every occurrence of DLE with
the two-character sequence DLE DLE. The receiver reverses the processes, replacing every
occurrence of DLE DLE with a single DLE.

28
 Example: If the frame contained ``A B DLE D E DLE'', the characters transmitted over
the channel would be ``DLE STX A B DLE DLE D E DLE DLE DLE ETX''.
 Disadvantage: character is the smallest unit that can be operated on; not all architectures
are byte oriented.

Figure 2.24: Framing- Flag bytes with byte stuffing.

3. FRAMING – Flag bits with bit stuffing

This technique allows data frames to contain an arbitrary number of bits and allows character
codes with an arbitrary number of bits per character. It works like this. Each frame begins and
ends with a special bit pattern, 01111110 (in fact, a flag byte). Whenever the sender's data
link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the
outgoing bit stream. This bit stuffing is analogous to byte stuffing, in which an escape byte is
stuffed into the outgoing character stream before a flag byte in the data. When the receiver
sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically destuffs (i.e.,
deletes) the 0 bit

29
Figure 2.25: FRAMING – Flag bits with bit stuffing

4. Physical Layer Coding Violations

This Framing Method is used only in those networks in which Encoding on the
Physical Medium contains some redundancy. Some LANs encode each bit of data by using
two Physical Bits. i.e. Manchester coding is Used. Here, Bit 1 is encoded into high – low (10)
pair and Bit 0 is encoded into low-high(01) pair. The scheme means that every data bit has a
transition in the middle, making it easy for the receiver to locate the bit boundaries. The
combinations high-high and low-low are not used for data but are used for delimiting frames
in some protocols.

Figure 2.26: Bit streams

iii) Error Control

Error control is concerned with insuring that all frames are eventually delivered
(possibly in order) to a destination. How? Three items are required.

i) Acknowledgements: Typically, reliable delivery is achieved using the “acknowledgments

with retransmission” paradigm, whereby the receiver returns a special acknowledgment
(ACK) frame to the sender indicating the correct receipt of a frame. In some systems, the
receiver also returns a negative acknowledgment (NACK) for incorrectly-received frames.
This is nothing more than a hint to the sender so that it can retransmit a frame right away
without waiting for a timer to expire.

30
ii) Timers: One problem that simple ACK/NACK schemes fail to address is recovering from
a frame that is lost, and as a result, fails to solicit an ACK or NACK. What happens if an
ACK or NACK becomes lost? Retransmission timers are used to resend frames that don't
produce an ACK. When sending a frame, schedule a timer to expire at some time after the
ACK should have been returned. If the timer goes o, retransmit the frame.

iii) Sequence Numbers: Retransmissions introduce the possibility of duplicate frames. To

suppress duplicates, add sequence numbers to each frame, so tha1t a receiver can distinguish
between new frames and old copies.

iv) Flow Control

Flow control deals with throttling the speed of the sender to match that of the receiver.
Two Approaches:

1. Feedback-based flow control, the receiver sends back information to the sender giving it
permission to send more data or at least telling the sender how the receiver is doing.

2.Rate-based flow control, the protocol has a built-in mechanism that limits the rate at
which senders may transmit data, without using feedback from the receiver.

Various Flow Control schemes uses a common protocol that contains well-defined rules
about when a sender may transmit the next frame. These rules often prohibit frames from
being sent until the receiver has granted permission, either implicitly 20 or explicitly.

2.5 ERROR CORRECTION AND DETECTION

It is physically impossible for any data recording or transmission medium to be 100%

perfect 100% of the time over its entire expected useful life. In data communication, line
noise is a fact of life (e.g., signal attenuation, natural phenomenon such as lightning, and the
telephone repairman). As more bits are packed onto a square centimeter of disk storage, as
communications transmission speeds increase, the likelihood of error increases-- sometimes
geometrically. Thus, error detection and correction is critical to accurate data transmission,
storage and retrieval. Detecting and correcting errors requires redundancy -- sending
additional information along with the data.

2.5.1 Types of Errors

There are two main types of errors in transmissions:

31
1.Single bit error : It means only one bit of data unit is changed from 1 to 0 or from 0 to 1.

Figure 2.27: Single bit error

2. Burst error : It means two or more bits in data unit are changed from 1 to 0 from 0 to 1.
In burst error, it is not necessary that only consecutive bits are changed. The length of burst
error is measured from first changed bit to last changed bit

Figure 2.28: Burst error

2.5.2 Error Detection Vs Error Correction

There are two types of attacks against errors:

1. Error Detecting Codes: Include enough redundancy bits to detect errors and use ACKs
and retransmissions to recover from the errors.

2. Error Correcting Codes: Include enough redundancy to detect and correct errors. The
use of error-correcting codes is often referred to as forward error correction.

Figure 2.29: Error Detection Vs Error Correction

2.5.3 Error Correcting Codes

32
Error Correction codes are used to detect and correct the errors when data is
transmitted from the sender to the receiver. Error Correction can be handled in two ways:

1. Backward error correction: Once the error is discovered, the receiver requests the
sender to retransmit the entire data unit.

2. Forward error correction: In this case, the receiver uses the error-correcting code
which automatically corrects the errors. A single additional bit can detect the error,
but cannot correct it

The four different error-correcting codes:

1. Hamming codes.
2. Binary convolutional codes.
3. Reed-Solomon codes.
4. Low-Density Parity Check codes

1. Hamming codes.

For correcting the errors, one has to know the exact position of the error. For example,
If we want to calculate a single-bit error, the error correction code will determine which one
of seven bits is in error. To achieve this, we have to add some additional redundant bits.
Suppose r is the number of redundant bits and d is the total number of the data bits.

The number of redundant bits r can be calculated by using the formula:

2 r >=d+r+1 The value of r is calculated by using the above formula.

For example, if the value of d is 4, then the possible smallest value that satisfies the
above relation would be 3.

To determine the position of the bit which is in error, a technique developed by R.W
Hamming is Hamming code which can be applied to any length of the data unit and uses the
relationship between data units and redundant units.

Hamming Code Parity bits: The bit which is appended to the original data of binary bits so
that the total number of 1s is even or odd.

33
Even parity: To check for even parity, if the total number of 1s is even, then the value of the
parity bit is 0. If the total number of 1s occurrences is odd, then the value of the parity bit is
1.

Odd Parity: To check for odd parity, if the total number of 1s is even, then the value of
parity bit is 1. If the total number of 1s is odd, then the value of parity bit is 0.

Algorithm of Hamming code: An information of 'd' bits are added to the redundant bits 'r' to
form d+r. The location of each of the (d+r) digits is assigned a decimal value. The 'r' bits are
placed in the positions 1,2,.....2k-1 At the receiving end, the parity bits are recalculated. The
decimal value of the parity bits determines the position of an error

Relationship b/w Error position & binary number

Error Binary Number

Position
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111

Let's understand the concept of Hamming code through an example:

Suppose the original data is 1010 which is to be sent. Total number of data bits 'd' = 4
Number of redundant bits r : 2r >= d+r+1 2r >= 4+r+1. Therefore, the value of r is 3 that
satisfies the above relation.

Total number of bits = d+r = 4+3 = 7;

Determining the position of the redundant bits

 The number of redundant bits is 3. The three bits are represented by r1, r2, r4.

 The position of the redundant bits is calculated with corresponds to the raised power
of 2.

34
 Therefore, their corresponding positions are 2 0, 21, 22. The position of r1 = 1, The
position of r2 = 2, The position of r4 = 4 Representation of Data on the addition of
parity bits:

Figure 2.30: Redundant bit

Determining the Parity bits

Determining the r1 bit:

 The r1 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the first position.

Figure 2.31: Redundant bit

• We observe from the above figure that the bit position that includes 1 in the first
position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit positions.

• The total number of 1 at these bit positions corresponding to r1 is even, therefore, the
value of the r1 bit is 0.

Determining r2 bit:

• The r2 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the second position

Figure 2.32: Redundant bit

35
 We observe from the above figure that the bit positions that includes 1 in the second
position are 2, 3, 6, 7. Now, we perform the even-parity check at these bit positions.
The total number of 1 at these bit positions corresponding to r2 is odd, therefore, the
value of the r2 bit is 1.

Determining r4 bit:

 The r4 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the third position

Figure 2.33: Redundant bit

• We observe from the above figure that the bit positions that includes 1 in the third
position are 4, 5, 6, 7. Now, we perform the even-parity check at these bit positions.

• The total number of 1 at these bit positions corresponding to r4 is even, therefore, the
value of the r4 bit is 0.

Data transferred is given below:

Figure 2.34: Redundant bit

 Suppose the 4th bit is changed from 0 to 1 at the receiving end, then parity bits are
recalculated.

R1 bit

 The bit positions of the r1 bit are 1,3,5,7

36
Figure 2.35: Redundant bit

• We observe from the above figure that the binary representation of r1 is 1100. Now,
we perform the even-parity check, the total number of 1s appearing in the r1 bit is an
even number. Therefore, the value of r1 is 0.

R2 bit

• The bit positions of r2 bit are 2,3,6,7

Figure 2.36: Redundant bit

• We observe from the above figure that the binary representation of r2 is 1001. Now,
we perform the even-parity check, the total number of 1s appearing in the r2 bit is an
even number. Therefore, the value of r2 is 0.

R4 bit

The bit positions of r4 bit are 4,5,6,7.

Figure 2.37: Redundant bit

We observe from the above figure that the binary representation of r4 is 1011. Now, we
perform the even-parity check, the total number of 1s appearing in the r4 bit is an odd
number. Therefore, the value of r4 is 1. The binary representation of redundant bits, i.e.,
r4r2r1 is 100, and its corresponding decimal value is 4. Therefore, the error occurs in a 4th bit
position. The bit value must be changed from 1 to 0 to correct the error.

37
2. Binary convolutional codes.

In convolutional codes, the message comprises of data streams of arbitrary length and
a sequence of output bits are generated by the sliding application of Boolean functions to the
data stream.

In block codes, the data comprises of a block of data of a definite length. However, in
convolutional codes, the input data bits are not divided into block but are instead fed as
streams of data bits, which convolve to output bits based upon the logic function of the
encoder. Also, unlike block codes, where the output codeword is dependent only on the
present inputs, in convolutional codes, output stream depends not only the present input bits
but also only previous input bits stored in memory.

Convolutional codes were first introduced in 1955, by Elias. After that, there were
many interim researches by many mathematicians. In 1973, Viterbi developed an algorithm
for maximum likelihood decoding scheme, called Viterbi scheme that lead to modern
convolutional codes.

a) Encoding by Convolutional Codes

For generating a convolutional code, the information is passed sequentially through a

linear finite-state shift register. The shift register comprises of (-bit) stages and Boolean
function generators.

A convolutional code can be represented as (n,k, K) where k is the number of bits

shifted into the encoder at one time. Generally, k = 1. n is the number of encoder output bits
corresponding to k information bits. The code-rate, Rc = k/n .

The encoder memory, a shift register of size k, is the constraint length. n is a function
of the present input bits and the contents of K.The state of the encoder is given by the value
of (K - 1) bits.

b) Example of Generating a Convolutional Code

Let us consider a convolutional encoder with k = 1, n = 2 and K = 3.

The code-rate, Rc = k/n = 1/2 .

38
Figure 2.38: Generating a Convolutional Code

The input string is streamed from right to left into the encoder. When the first bit, 1, is
streamed in the encoder, the contents of encoder will be

Figure 2.39: Generating a Convolutional Code

When the next bit, 1 is streamed in the encoder, the contents of encoder will be –

Figure 2.40: Generating a Convolutional Code

When the next bit, 0 is streamed in the encoder, the contents of encoder will be –

39
Figure 2.41: Generating a Convolutional Code

When the last bit, 1 is streamed in the encoder, the contents of encoder will be –

Figure 2.42: Generating a Convolutional Code

c) Representing Convolution Encoder with State Transition Diagram and State Table

From the above example, we can see that any particular binary convolutional encoder
is associated with a set of binary inputs, a set of binary outputs and a set of states. The
transitions and the output may be effectively represented by a state transition diagram and a
state table.

For the binary convolution encoder given in the example −

The set of inputs = {0, 1}

The set of outputs = { 00, 10, 11}

The set of states = { 00, 01, 10, 11}

We can see that in the initial state, 00, when the input 1 was given, the next state
became 10 and the corresponding output was 11. In this state 10, when the input 1 was given,

40
the next state was 11 and the encoder outputs were 10. In the same manner we get the other
transitions. When this is tabulated, we get the state transition table as follows −

The corresponding state transition diagram will be –

Figure 2.43: State Transition

3. Reed-Solomon codes.

Reed - Solomon error correcting codes are one of the oldest codes that were
introduced in 1960s by Irving S. Reed and Gustave Solomon. It is a subclass of non - binary
BCH codes. BCH codes (Bose-Chaudhuri-Hocquenghem codes) are cyclic ECCs that are
constructed using polynomials over data blocks.

A Reed - Solomon encoder accepts a block of data and adds redundant bits (parity
bits) before transmitting it over noisy channels. On receiving the data, a decoder corrects the
error depending upon the code characteristics.

41
Figure 2.44: Reed - Solomon Codes

a) Parameters of Reed - Solomon Codes

 A Reed-Solomon code is specified as RS(n,k).

 Here, n is the block length which is recognizable by symbols, holding the relation, n =
2m - 1.
 The message size is of k bits.
 So the parity check size is (n - k) bits
 The code can correct up to (t) errors in a codeword, where (2t = n - k).

The following diagram shows a Reed-Solomon codeword −

Figure 2.45: Reed - Solomon Codes

b) Generator Polynomial of Reed Solomon Code

In coding systems with block codes, valid code words consists of polynomials that are
divisible by another fixed polynomial of short length. This fixed polynomial is called
generator polynomial.

In Reed Solomon code, generator polynomial with factors is constructed where each
root is a consecutive element in the Galois field. The polynomial is of the form −

42
g(x) = (x - α) (x - α2) (x - α3) ......(x - α2t)where α is a primitive element.

c) Encoding using Reed Solomon Code

The method of encoding in Reed Solomon code has the following steps −

 The message is represented as a polynomial p(x), and then multiplied with the generator
polynomial g(x).
 The message vector [x1,x2,x3.....xk] is mapped to a polynomial of degree less than k such
that px(αi) = xi for all i = 1,...k
 The polynomial is evaluated using interpolation methods like Lagrange Interpolation.
 Using this polynomial, the other points αk + 1....αn, are evaluated.
 The encoded message is calculated as s(x) = p(x) * g(x). The sender sends this encoded
message along with the generator polynomial g(x).

d) Decoding using Reed Solomon Code

At the receiving end, the following decoding procedure done −

 The receiver receives the message r(x) and divides it by the generator polynomial g(x).
 If r(x)/g(x)=0, then it implies no error.
 If r(x)/g(x)≠0, then the error polynomial is evaluated using the expression: r(x) = p(x) *
g(x) + e(x)
 The error polynomial gives the error positions.

e) Application Areas of Reed-Solomon Codes

The prominent application areas are −

 Storage areas like CDs, DVDs, Blu-ray Discs

 High speed data transmission technologies such as DSL and WiMAX
 High speed modems
 QR Codes
 Broadcast systems such as satellite communications
 Storage systems such as RAID 6

4. Low-Density Parity Check codes

43
a) Encoding by Low-Density Parity Check Codes

A low - density parity check (LFPC) code is specified by a parity-check matrix

containing mostly 0s and a low density of 1s. The rows of the matrix represent the equations
and the columns represent the bits in the codeword, i.e. code symbols.

A LDPC code is represented by , where is the block length, is the number of 1s in

each column and is the number of 1s in each row, holding the following properties −

 j is the small fixed number of 1’s in each column, where j > 3

 k is the small fixed number of 1’s in each row, where k > j.

b) Example 1 − Parity Check Matrix of Hamming Code

The following parity check matrix Hamming code having , with 4 information bits
followed by 3 even parity bits. The check digits are diagonally 1. The parity equations are
given alongside −

Figure 2.46: Parity Check Matrix of Hamming Code

c) Example 2 − Low - Density Parity Check Matrix

This examples illustrates an (12, 3, 4) LDPC matrix, i.e. n = 12, j = 3 and k = 4. This
implies that each equation operates on 4 code symbols and each code symbol appears in 3
equations. Unlike parity check matrix of the Hamming code, this code does not have any
diagonal 1s in parity bits.

44
Figure 2.47: Low - Density Parity Check Matrix

d) Decoding of LDPC Codes

There are two possible decoding techniques of LDPC codes.

 In the first technique, the decoder does all the parity checks as per the parity equations. If
any bit is contained in more than a fixed number of unsatisfied parity equations, the value of
that bit is reversed. Once the new values are obtained, parity equations are recomputed using
the new values. The procedure is repeated until all the parity equations are satisfied.
 This decoding procedure is simple and but is applicable only when the parity-check sets
are small.
 The second method performs probabilistic algorithms on LDPC graphs. The graph is a
sparse bipartite graph that contains two sets of nodes, one set representing the parity
equations and the other set representing the code symbols. A line connects node in first set
to the second if a code symbol is present in the equation. Decoding is done by passing
messages along the lines of the graph. Messages are passed from message nodes to check
nodes, and from check nodes back to message nodes and their parity values are calculated.
 The two subclasses of these methods are belief propagation and maximum likelihood
decoding. Though these decoding algorithms are complex, they yield better results than the
former.

2.5.4 Error Detection

A condition when the receiver’s information does not matches with the sender’s
information. During transmission, digital signals suffer from noise that can introduce errors in
the binary bits travelling from sender to receiver. That means a 0 bit may change to 1 or a 1
bit may change to 0.

45
Error Detecting Codes

Whenever a message is transmitted, it may get scrambled by noise or data may get
corrupted. To avoid this, we use error-detecting codes which are additional data added to a
given digital message to help us detect if any error has occurred during transmission of the
message. Basic approach used for error detection is the use of redundancy bits, where
additional bits are added to facilitate detection of errors.

Some popular techniques for error detection are:

1. Simple Parity check

2. Two-dimensional Parity check
3. Checksum
4. Cyclic redundancy check
1. Simple Parity check
Blocks of data from the source are subjected to a check bit or parity bit generator
form, where a parity of 1 is added to the block if it contains odd number of 1’s, and 0 is
added if it contains even number of 1’s. This scheme makes the total number of 1’s even, that
is why it is called even parity checking.

Figure 2.48: Simple Parity check

2. Two-dimensional Parity check

Parity check bits are calculated for each row, which is equivalent to a simple parity
check bit. Parity check bits are also calculated for all columns, then both are sent along with
the data. At the receiving end these are compared with the parity bits calculated on the
received data.

46
Figure 2.49: Two-dimensional Parity check

3. Checksum

In checksum error detection scheme, the data is divided into k segments each of m
bits. In the sender’s end the segments are added using 1’s complement arithmetic to get the
sum. The sum is complemented to get the checksum.

The checksum segment is sent along with the data segments. At the receiver’s end, all
received segments are added using 1’s complement arithmetic to get the sum. The sum is
complemented. If the result is zero, the received data is accepted; otherwise discarded

47
Figure 2.50: Checksum

4.Cyclic redundancy check (CRC)

Unlike checksum scheme, which is based on addition, CRC is based on binary

division. In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are
appended to the end of data unit so that the resulting data unit becomes exactly divisible by a
second, predetermined binary number. At the destination, the incoming data unit is divided
by the same number. If at this step there is no remainder, the data unit is assumed to be
correct and is therefore accepted. A remainder indicates that the data unit has been damaged
in transit and therefore must be rejected.

48
Figure 2.51: Cyclic redundancy check (CRC)

49