Study Unit 5 - Chapter Five Making Connections Efficient: Multiplexing and Compression

Question 1

Introduction

Answer 1

Introduction
* Under simplest conditions, medium can carry only one signal
at any moment in time
* For multiple signals to share a medium, medium must
somehow be divided, giving each signal a portion of the total
bandwidth
* Current techniques include:
– Frequency division multiplexing
– Time division multiplexing
– Code division multiplexing

Question 2

Frequency Division Multiplexing

Answer 2

Frequency Division Multiplexing
* Assignment of nonoverlapping frequency ranges to each
“user” or signal on a medium
– Thus, all signals are transmitted at the same time, each using
different frequencies
* A multiplexor accepts inputs and assigns frequencies to each
device

Question 3

Frequency Division Multiplexing
(continued)

Answer 3

Frequency Division Multiplexing
(continued)
* Each channel is assigned a set of frequencies and is
transmitted over the medium
* A corresponding multiplexor, or demultiplexor, is on the
receiving end of the medium and separates the multiplexed
signals
* A common example is broadcast radio

Question 4

Frequency Division Multiplexing
(continued)

Answer 4

Frequency Division Multiplexing
(continued)
* Analog signaling is used in older systems; discrete analog
signals in more recent systems
* Broadcast radio and television, cable television, and cellular
telephone systems use frequency division multiplexing
* This technique is the oldest multiplexing technique
* Since it involves a certain level of analog signaling, it may be
susceptible to noise

Question 5

Time Division Multiplexing

Answer 5

Time Division Multiplexing
* Sharing of the signal is accomplished by dividing available
transmission time on a medium among users
* Digital signaling is used exclusively
* Time division multiplexing comes in two basic forms:
– Synchronous time division multiplexing
– Statistical time division multiplexing

Question 6

Synchronous Time Division Multiplexing

Answer 6

Synchronous Time Division Multiplexing
* The original time division multiplexing
* The multiplexor accepts input from attached devices in a
round-robin fashion and transmits the data in a never -ending
pattern
* T-1 and SONET telephone systems are common examples
of synchronous time division multiplexing

Question 7

Synchronous Time Division Multiplexing
(continued)

Answer 7

Synchronous Time Division Multiplexing
(continued)
* So that the receiver may stay synchronized with the
incoming data stream, the transmitting multiplexor can insert
alternating 1s and 0s into the data stream

Question 7

Synchronous Time Division Multiplexing
(continued)

Answer 7

Synchronous Time Division Multiplexing
(continued)
* If one device generates data at faster rate than other
devices, then the multiplexor must either sample the
incoming data stream from that device more often than it
samples the other devices, or buffer the faster incoming
stream
* If a device has nothing to transmit, the multiplexor must still
insert something into the multiplexed stream

Question 7

SONET/SDH Multiplexing

Answer 7

SONET/SDH Multiplexing
* Similar to T-1, SONET incorporates a continuous series of
frames
* SONET is used for high-speed data transmission
* Telephone companies have traditionally used a lot of SONET
but this may be giving way to other high-speed transmission
services
* SDH is the European equivalent to SONET

Question 7

T-1 Multiplexing

Answer 7

T-1 Multiplexing
* The T-1 multiplexor stream is a continuous series of frames
* Note how each frame contains the data (one byte) for
potentially 24 voice-grade telephone lines, plus one sync bit
* It is possible to combine all 24 channels into one channel for
a total of 1.544 Mbps

Question 8

Statistical Time Division Multiplexing

Answer 8

Statistical Time Division Multiplexing
* A statistical multiplexor transmits the data from active
workstations only
* If a workstation is not active, no space is wasted in the
multiplexed stream

Question 9

Statistical Time Division Multiplexing
(continued)

Answer 9

Statistical Time Division Multiplexing
(continued)
* A statistical multiplexor accepts the incoming data streams
and creates a frame containing the data to be transmitted
* To identify each piece of data, an address is included

Question 10

Statistical Time Division Multiplexing

Answer 10

Statistical Time Division Multiplexing
(continued)
* If the data is of variable size, a length is also included

Question 11

Statistical Time Division Multiplexing
(continued)

Answer 11

Statistical Time Division Multiplexing
(continued)
* More precisely, the transmitted frame contains a collection of
data groups

Question 12

Wavelength Division Multiplexing

Answer 12

Wavelength Division Multiplexing
* Wavelength division multiplexing multiplexes multiple data
streams onto a single fiber-optic line
* Different wavelength lasers (called lambdas) transmit the
multiple signals

Question 13

Wavelength Division Multiplexing
(continued)

Answer 13

Wavelength Division Multiplexing
(continued)
* Each signal carried on the fiber can be transmitted at a
different rate from the other signals
* Dense wavelength division multiplexing combines many (30,
40, 50 or more) onto one fiber
* Coarse wavelength division multiplexing combines only a
few lambdas

Question 14

Discrete Multitone

Answer 14

• Discrete Multitone (DMT) – a multiplexing technique
  commonly found in digital subscriber line (DSL) systems
• DMT combines hundreds of different signals, or
  subchannels, into one stream
• Interestingly, all of these subchannels belong to a single
  user, unlike the previous multiplexing techniques

Question 15

Discrete Multitone (continued)

Answer 15

Discrete Multitone (continued)
* Each subchannel is quadrature amplitude modulated (recall
eight phase angles, four with double amplitudes)
* Theoretically, 256 subchannels, each transmitting 60 kbps,
yields 15.36 Mbps
* Unfortunately, there is noise, so the subchannels back down
to slower speeds

Question 16

Code Division Multiplexing

Answer 16

Code Division Multiplexing
* Also known as code division multiple access
* An advanced technique that allows multiple devices to
transmit on the same frequencies at the same time
* Each mobile device is assigned a unique 64-bit code

Question 17

Code Division Multiplexing (continued)

Answer 17

Code Division Multiplexing (continued)
* To send a binary 1, a mobile device transmits the unique code
* To send a binary 0, a mobile device transmits the inverse of the code
* To send nothing, a mobile device transmits zeros

Question 18

Code Division Multiplexing (continued)

Answer 18

Code Division Multiplexing (continued)
* Receiver gets summed signal, multiplies it by receiver code,
adds up the resulting values
– Interprets as a binary 1 if sum is near +64
– Interprets as a binary 0 if sum is near -64

Question 19

Code Division Multiplexing (continued)

Answer 19

Code Division Multiplexing (continued)
* For simplicity, assume 8-bit code
* Example
– Three different mobile devices use the following codes:
* Mobile A: 11110000
* Mobile B: 10101010
* Mobile C: 00110011
– Assume Mobile A sends a 1, B sends a 0, and C sends a 1
– Signal code: 1-chip = +N volt; 0-chip = -N volt

Question 20

Code Division Multiplexing (continued)

Answer 20

Code Division Multiplexing (continued)
* Example (continued)
– Three signals transmitted:
* Mobile A sends a 1, or 11110000, or ++++—-
* Mobile B sends a 0, or 01010101, or -+-+-+-+
* Mobile C sends a 1, or 00110011, or –++–++
– Summed signal received by base station: -1, +1, +1, +3, -3, -1, -1, +1

Question 21

Code Division Multiplexing (continued)

Answer 21

Code Division Multiplexing (continued)
* Example (continued)
– Base station decode for Mobile A:
* Signal received: -1, +1, +1, +3, -3, -1, -1, +1
* Mobile A’s code: +1, +1, +1, +1, -1, -1, -1, -1
* Product result: -1, +1, +1, +3, +3, +1, +1, -1
– Sum of Products: +8
– Decode rule: For result near +8, data is binary 1

Question 22

Code Division Multiplexing (continued)

Answer 22

Code Division Multiplexing (continued)
* Example (continued)
– Base station decode for Mobile B:
* Signal received: -1, +1, +1, +3, -3, -1, -1, +1
* Mobile B’s code: +1, -1, +1, -1, +1, -1, +1, -1
* Product result: -1, -1, +1, -3, -3, +1, -1, -1
– Sum of Products: -8
– Decode rule: For result near -8, data is binary 0

Question 23

Compression–Lossless versus Lossy

Answer 23

Compression–Lossless versus Lossy
* Compression is another technique used to squeeze more
data over a communications line
– If you can compress a data file down to one half of its original size, file
will obviously transfer in less time
* Two basic groups of compression:
– Lossless – when data is uncompressed, original data returns
– Lossy – when data is uncompressed, you do not have the original
data

Question 24

Compression–Lossless versus Lossy
(continued)

Answer 24

Compression–Lossless versus Lossy
(continued)
* Compress a financial file?
– You want lossless
* Compress a video image, movie, or audio file?
– Lossy is OK
* Examples of lossless compression include:
– Huffman codes, run-length compression, and Lempel-Ziv
compression
* Examples of lossy compression include:
– MPEG, JPEG, MP3

Question 25

Run-length encoding

Answer 25

Run-length encoding
– Replaces runs of 0s with a count of how many 0s.
00000000000000100000000011000000000000000000001…11000000000001
^
(30 0s)
14 9 0 20 30 0 11

Question 26

Run-length encoding (continued)

Answer 26

Run-length encoding (continued)
– Now replace each decimal value with a 4-bit binary value (nibble)
* Note: If you need to code a value larger than 15, you need to use two
consecutive 4-bit nibbles
– The first is decimal 15, or binary 1111, and the second nibble is the
remainder
» For example, if the decimal value is 20, you would code 1111
0101 which is equivalent to 15 + 5

Question 27

Run-length encoding (continued)

Answer 27

Run-length encoding (continued)
– If you want to code the value 15, you still need two nibbles: 1111
0000
* The rule is that if you ever have a nibble of 1111, you must follow it with
another nibble

Question 28

Relative or differential encoding

Answer 28

Relative or differential encoding
– Video does not compress well using run-length encoding
– In one color video frame, not much is alike
– But what about from frame to frame?
* Send a frame, store it in a buffer
* Next frame is just difference from previous frame
* Then store that frame in buffer, etc.

Question 29

Image Compression

Answer 29

mage Compression
– One image (JPEG) or continuous images (MPEG)
– A color picture can be defined by red/green/blue, or
luminance/chrominance/chrominance which are based on RGB
values
* Either way, you have 3 values, each 8 bits, or 24 bits total (224 colors!)

Question 30

• Image Compression (continued)

Answer 30

• Image Compression (continued)
  – A VGA screen is 640 x 480 pixels
• 24 bits x 640 x 480 = 7,372,800 bits – Ouch!
• And video comes at you 30 images per second – Double Ouch!
• We need compression!

Question 31

JPEG (Joint Photographic Experts Group)

Answer 31

JPEG (Joint Photographic Experts Group)
– Compresses still images
– Lossy
– JPEG compression consists of 3 phases:
* Discrete cosine transformations (DCT)
* Quantization
* Run-length encoding

Question 32

JPEG Step 1 – DCT

Answer 32

JPEG Step 1 – DCT
– Divide image into a series of 8x8 pixel blocks
– If the original image was 640x480 pixels, the new picture would be 80
blocks x 60 blocks (next slide)
– If B&W, each pixel in 8x8 block is an 8-bit value (0-255)
– If color, each pixel is a 24-bit value (8 bits for red, 8 bits for blue, and
8 bits for green)

Question 33

JPEG Step 1 – DCT (continued)

Answer 33

JPEG Step 1 – DCT (continued)
– So what does DCT do?
* Takes an 8x8 array (P) and produces a new 8x8 array (T) using cosines
* T matrix contains a collection of values called spatial frequencies
* These spatial frequencies relate directly to how much the pixel values
change as a function of their positions in the block

Question 34

JPEG Step 1 – DCT (continued)

Answer 34

JPEG Step 1 – DCT (continued)
– An image with uniform color changes (little fine detail) has a P array
with closely similar values and a corresponding T array with many
zero values
– An image with large color changes over a small area (lots of fine
detail) has a P array with widely changing values, and thus a T array
with many non-zero values

Question 35

JPEG Step 2 -Quantization

Answer 35

JPEG Step 2 -Quantization
– The human eye can’t see small differences in color
* So take T matrix and divide all values by 10
– Will give us more zero entries
» More 0s means more compression!
– But this is too lossy
– And dividing all values by 10 doesn’t take into account that upper left
of matrix has more action (the less subtle features of the image, or
low spatial frequencies)

Question 36

Business Multiplexing In Action

Answer 36

Business Multiplexing In Action
* Bill’s Market has 10 cash registers at the front of their store
* Bill wants to connect all cash registers together to collect
data transactions
* List some efficient techniques to link the cash registers

Question 36

JPEG Step 3 – Run-length encoding

Answer 36

JPEG Step 3 – Run-length encoding
– Now take the quantized matrix Q and perform run-length encoding on
it
* But don’t just go across the rows
– Longer runs of zeros if you perform the run-length encoding in a
diagonal fashion

Question 37

How do you get the image back?

Answer 37

How do you get the image back?
– Undo run-length encoding
– Multiply matrix Q by matrix U yielding matrix T
– Apply similar cosine calculations to get original P matrix back

Question 38

Business Multiplexing In Action
(continued)

Answer 38

Business Multiplexing In Action
(continued)
* Possible solutions
– Connect each cash register to a server using point-to-point lines
– Transmit the signal of each cash register to a server using wireless
transmissions
– Combine all the cash register outputs using multiplexing, and send
the multiplexed signal over a conducted-medium line