Data Communication and

Networking

M.Eng. Dang Ngoc Hanh

hanhdn@hcmut.edu.vn

Telecomm. Dept. DCN-2013

1
Faculty of EEE HCMUT
 Content
Chapter 1: Medium of PHY Layer
Wired and Wireless Media
Physical layer standards: RS232, RS422, RS485
Line Coding
Digital modulation/demodulation
Channel parameters
Gaussian noise and BER
Chapter 2: Data Transmission
Asynchronous transmission
Synchronous transmission
Channel Coding
Data Compression
Telecomm. Dept. DCN-2013
2
Faculty of EEE HCMUT
 Coding schemes
 EBCDIC (Extended Binary Coded Decimal Interchange Code):
 Invented by IBM
 8-bit character encoding used mainly on IBM mainframe and IBM
midrange computer operating systems.

 ASCII (American Standards Committee for Information Interchange):

defined by ITU-T
 character-encoding scheme originally based on the English alphabet
that encodes 128 specified characters - the numbers 0-9, the letters a-
z and A-Z, some basic punctuation symbols, some control codes that
originated with Teletype machines, and a blank space - into the 7-bit
binary integers.
 ASCII codes represent text in computers, communications equipment,
and other devices that use text. Most modern character-encoding
schemes are based on ASCII, though they support many additional
characters.

Telecomm. Dept. DCN-2013

3
Faculty of EEE HCMUT
 EBCDIC Table

 Data characters

 Control characters

Telecomm. Dept. DCN-2013

4
Faculty of EEE HCMUT
 ASCII Table
 Data characters
 Control characters

Telecomm. Dept. DCN-2013

5
Faculty of EEE HCMUT
 ASCII Table
 ASCII unprintable
characters:

Telecomm. Dept. DCN-2013

6
Faculty of EEE HCMUT
 Network Topology
 Bus  Point-to point

 Star  Multipoint

 Ring  Mesh

Telecomm. Dept. DCN-2013

7
Faculty of EEE HCMUT
 Communication types
 Simplex communication is
permanent uni-directional
communication (e.g. Radio, TV)

 Half duplex: A half duplex link

can communicate in only one
direction, at a time. Two way
communication is possible, but
not simultaneously. E.g. talk-
back radio, Citizen Bands radio

 Full duplex communication is

two-way communication
achieved over a physical link that
has the ability to communicate in
both directions simultaneously.
E.g. Telephone system

Telecomm. Dept. DCN-2013

8
Faculty of EEE HCMUT
 Transmission modes
 The transmission of binary data across a link can be
accomplished in either parallel or serial mode. In parallel
mode, multiple bits are sent with each clock tick. In serial
mode, 1 bit is sent with each clock tick. While there is only one
way to send parallel data, there are three subclasses of serial
transmission: asynchronous, synchronous, and isochronous.

Telecomm. Dept. DCN-2013

9
Faculty of EEE HCMUT
 Parallel transmission
 Bits are transmitted in bus at the same time
 High speed over short distance
 Example: PC-printer

Telecomm. Dept. DCN-2013

10
Faculty of EEE HCMUT
 Serial transmission
 Bits are transmitted over one line sequentially
 Low speed over long distance
 Asynchronous and Synchronous transmission

Telecomm. Dept. DCN-2013

11
Faculty of EEE HCMUT
 Timing
 Timing problems require a mechanism to synchronize the
transmitter and receiver
 Timing of bits is the key!

 How can we control the timing?

System A System B

……101101

Telecomm. Dept. DCN-2013

12
Faculty of EEE HCMUT
 Asynchronous transmission
 Asynchronous here means “asynchronous at the byte level,”
but the bits are still synchronized; their durations are the
same.
 Each character of data is treated independently

Telecomm. Dept. DCN-2013

13
Faculty of EEE HCMUT
 Synchronous transmission
 In synchronous transmission, we send bits one after another
without start or stop bits or gaps. It is the responsibility of the
receiver to group the bits.
 For sending large blocks of data
 Control schemes
 Character-oriented
 Bit-oriented

Telecomm. Dept. DCN-2013

14
Faculty of EEE HCMUT
 Asynchronous Transmission
Asynchronous
Data transmitted one character at a time
5 to 8 bits
Timing only needs to be maintained within each character
Transmitter and Receiver clocks need not be in sync
Resynchronize at the beginning of each character

Behavior:
In a steady stream, interval between characters is uniform
• Length of stop element
In idle state
• Receiver looks for transition 1 to 0
Then samples next seven intervals
• Char length
Then looks for next 1 to 0 for next char
Telecomm. Dept. DCN-2013
15
Faculty of EEE HCMUT
 Asynchronous Transmission
Diagram

Advantages:
Simple
Cheap
Overhead of 2 or 3
bits per character
(~20%)
Good for data with
large gaps (e.g.
keyboard)

Telecomm. Dept. DCN-2013

16
Faculty of EEE HCMUT
 Asynchronous Transmission
 How can the receiver detect bits?
 How can the receiver receive the whole byte?
 How can the receiver receive the whole frame?

Common synchronization techniques

Bit synchronization
Byte synchronization
Frame synchronization

Telecomm. Dept. DCN-2013

17
Faculty of EEE HCMUT
 Asynchronous Transmission
Bit Synchronization
Clock rate at the
receiver is N times
clock rate at
transmitter

When detecting the

start bit transition,
using N/2 and N
counters to sample
bits until the end of
the character

Telecomm. Dept. DCN-2013

18
Faculty of EEE HCMUT
 Asynchronous Transmission
If N is larger, the
sampling is more
precise

Usually, N=16

Telecomm. Dept. DCN-2013

19
Faculty of EEE HCMUT
 Asynchronous Transmission
 Byte synchronization: the configuration of transmission must
be the same at the transmitter and receiver
 Start bit: 1
 Data bits: 4,5,6,7,8
 Parity bit: 0, 1 (even or odd)
 Stop bit: 1, 1.5, 2

Telecomm. Dept. DCN-2013

20
Faculty of EEE HCMUT
 Asynchronous Transmission
Frame synchronization:
If Blocks of printable characters
Encapsulate complete block between two special (non-
printable) transmission control characters
• STX : Start-of-text
• ETX : End-of-text

Telecomm. Dept. DCN-2013

21
Faculty of EEE HCMUT
 Asynchronous Transmission
If Binary data
e.g., Contents of a file
containing a compiled
program
Use of single ETX not
sufficient to indicate the
end of a file
• One of the bytes might be the
same as an ETX character
Solution: STX and ETX are
preceded by another
transmission control
character
• Data link escape (DLE)
Character or byte stuffing

Telecomm. Dept. DCN-2013

22
Faculty of EEE HCMUT
 Example
 DTE A transmits to DTE B a sequence of characters:
T S L DLE
 The message is transmitted in Asynchronous mode using
RS232 (8-bit data, 1 parity bit, 1 stop bit), R=1200 bps and
characters are in ASCII code
 Show the data frame? (If transmitting: T S L DLE ETX? What is
the transmitted frame?)
 Determine the time to transmit this data frame (ignoring the
processing time) and the effficiency?

DLE STX T S L DLE DLE DLE ETX

T = (9 x 11)/1200 = 82.5 ms
Telecomm. Dept. DCN-2013
23
Faculty of EEE HCMUT
 Synchronous Transmission
Disadvantages of Asynchronous transmission
Bit synchronization is too difficult when increasing bit
rate
High overhead

Synchronous transmission
Data has been transmitted in blocks
Two approaches
• Character-oriented
• Bit-oriented
Both use the same bit synchronization methods
Major difference is in how they achieve character &
frame synchronization
Telecomm. Dept. DCN-2013
24
Faculty of EEE HCMUT
 Synchronous Transmission
Bit level: Block of data transmitted without start or
stop bits
Tx and Rx clocks must be synchronized!!!
Option 1 -- Can use separate clock line
Good over short distances
Subject to impairments
Option 2 -- Embed clock signal in data
Manchester encoding
Carrier frequency (analog)

Telecomm. Dept. DCN-2013

25
Faculty of EEE HCMUT
 Synchronous Transmission
 Bit synchronization using clock
encoding:
 Transmitter embedded clock into
data signal
 Receiver extracts clock from
received signal
 Using: Manchester, RZ line codes
 Using differential Manchester: a
transition at the start of bit cell
only occurs if the next bit is 0.

Telecomm. Dept. DCN-2013

26
Faculty of EEE HCMUT
 Synchronous Transmission
 Bit synchronization using DPLL:
 Which holds its frequency
sufficiently constant to require
only very small adjustment at
irregular intervals.
 Assuming the incoming bit
stream and the local clock are
in synchronism. The state (1 or
0) will be sampled at the center
of each bit cell with exactly 32
clock periods between each
sample.
 To sync clock at receiver, the
transmitted bit stream must be
encoded to have enough
transitions for synchronization:
using line codes NRZ,
Manchester, AMI, HDB3, B8ZS
Telecomm. Dept. DCN-2013
27
Faculty of EEE HCMUT
 Synchronous Transmission
 In case the clock at
transmitter and receiver is
not in sync, the sampling
pulse will be adjusted in 30-
34 clock periods
 If there are no transitions
on the line, DPLL simply
generates a sampling pulse
every 32 clocks after the
previous one.
 Whenever a transition is
detected, the time interval
between the previously
generated sampling pulse
and the next us determined
according to the position of
the transition relative to
where DPLL thought it
should occurs

Telecomm. Dept. DCN-2013

28
Faculty of EEE HCMUT
 Synchronous Transmission
 Each bit is divided into 5 segments: A, B,C,D,E. For example, a
transition during segment A indicates that the last sampling pulse
was too close the next transition and hence late. The time period to
the next sampling pulse is shortened to 30 clock periods. Similarly,
transition occurring in segment E means the previous sampling
pulse was too early relative to the transition. Hence, the time
period to the next pulse is lengthened to 34 clock periods.
 Transition in segments B and D are clearly nearer to the assumed
transition and hence the relative adjustments are less (-1 and +1).
Finally, a transition in segment C is deemed to be close enough to
the assumed transition to warrant no adjustment.
 In practice, A=E=10, B=D=4, C=4 (clock periods). The worst case, 10
bits are needed for synchronization (5 bit periods of coarse
adjustments (2), 5 bit periods for fine adjustments (1): need to
transmit a number of bytes/characters for synchronization.

Telecomm. Dept. DCN-2013

29
Faculty of EEE HCMUT
 Synchronous Transmission
 Bit synchronization using
Hybrid method:
 When bit rate increases, it is
too difficult for bit sync.
Hybrid scheme uses both
DPLL and Manchester
encoding
 The DPLL keeps the local clock
synchronized with the
incoming bit stream.
Manchester encoding means
that there is at least one
signal transition every bit cell
 Need more bandwidth
required for Manchester
encoding compared with NRZI

Telecomm. Dept. DCN-2013

30
Faculty of EEE HCMUT
 Synchronous Transmission
Character-Oriented:
Used for transmission of block of characters
• e.g., files of ASCII characters
Character synchronization
• Achieved with synchronous idle character (SYN)
Frame synchronization
• STX-ETX sequence preceded by SYN char
• Once bit-synchronization is achieved
• Receiver enters “hunt mode”
• Bit stream is interpreted in windows of 8 bits
Low efficiency because of using many STX, ETX,..

Telecomm. Dept. DCN-2013

31
Faculty of EEE HCMUT
 Synchronous Transmission
 Example: transmitting
the characters
DATACANTXDLECHAR.

 What is the frame in

character-oriented
transmission mode with
printable characters and
unprintable characters?

Telecomm. Dept. DCN-2013

32
Faculty of EEE HCMUT
 Synchronous Transmission
 Bit-Oriented:
Used for transmission of binary data
• Preferred control scheme
Point-to-point links
• Uses a flag pattern for start and end of frame
– Idle bytes: 01111111 (0x7F)
– Flag pattern: 01111110 (0x7E)
• Bit stuffing (or zero bit insertion)
– Inserts a “0” after five consecutive 1s
• LANs use a similar scheme
• More efficient (lower overhead) than asynchronous transmission

Telecomm. Dept. DCN-2013

33
Faculty of EEE HCMUT
 Synchronous Transmission
 Bit-Oriented:

Telecomm. Dept. DCN-2013

34
Faculty of EEE HCMUT
 Channel Coding
 Channel coding is a technique used for controlling errors in data
transmission over unreliable or noisy communication channels. The central
idea is the sender encodes their message in a redundant way by using an
error-correcting code (ECC).
 The redundancy allows the receiver to detect a limited number of errors
that may occur anywhere in the message, and often to correct these errors
without retransmission.

Telecomm. Dept. DCN-2013

35
Faculty of EEE HCMUT
 Error control coding
 Forward Error Control (FEC) gives the receiver the ability to
correct errors without needing a reverse channel to request
retransmission of data, but at the cost of a fixed, higher forward
channel bandwidth.
 FEC is therefore applied in situations where retransmissions are
costly or impossible, such as one-way communication links and
when transmitting to multiple receivers in multicast.
 Errors can come from:
 Human
 Equipment
 Transmission channel
 Detection methods:
 Parity check
 Block sum check
 Cyclic Redundant Check
Telecomm. Dept. DCN-2013
36
Faculty of EEE HCMUT
 Error control coding
 Types of Errors
 Single Bit Errors:
• only one bit in a given data unit (byte, packet, etc.) gets corrupted

 Burst Errors
• two or more bits in the data unit have been corrupted errors do not have to
occur in consecutive bits
• burst errors are typically caused by external noise (environmental noise)
• burst errors are more difficult to detect / correct

Telecomm. Dept. DCN-2013

37
Faculty of EEE HCMUT
 Example: Detect Error On Credit Card
 Let d2, d4, d6, d8, d10, d12, d14, d16 be all the even values in the credit
card number.
 Let d1, d3, d5, d7, d9, d11, d13, d15 be all the odd values in the credit
card number.
 Let n be the number of all the odd digits which have a value that exceeds 4
 Credit card has an error if the following is true:
(d1 + d3 + d5 + d7 + d9 + d11 + d13 + d15) x 2 + n +
(d2 + d4 + d6 + d8 + d10 + d12 + d14 + d16)
 0 mod (10)

Telecomm. Dept. DCN-2013

38
Faculty of EEE HCMUT
Example: Detect Error On Credit Card

n=3

d1

d2 d3 … d15 d16

Telecomm. Dept. DCN-2013

39
Faculty of EEE HCMUT
Example: Detect Error On Credit Card
(4 + 4 + 8 + 1 + 3 + 5 + 7 + 9) = 41
(5 + 2 + 1 + 0 + 3 + 4 + 6 + 8) x 2 + 3 = 61
41 + 61 = 102 mod (10) = 2

Typing error 3
Telecomm. Dept. DCN-2013
40
Faculty of EEE HCMUT
 Example: Detect Error On Credit Card
 The test performed on the credit card number is called a
parity check equation. The last digit is a function of the other
digits in the credit card. This is how credit card numbers are
generated by Visa and Mastercard. They start with an account
number that is 15 digits long and use the parity check
equation to find the value of the 16th digit.
 “This method allows computers to detect 100% of single-
position errors and about 98% of other common errors”

 Other examples:
 ISBN (international standard book number)
• 0 – 20 – 1 – 36186 – 8
 UPC (universal product codes): 12-digit sequence
• 0 16000 66610 8
Telecomm. Dept. DCN-2013
41
Faculty of EEE HCMUT
 Parity Check
 Value of parity bit is such that
character has even (even
parity) or odd (odd parity)
number of ones
 Even parity: number of bits 1
(including parity bit, excluding
Start and Stop bits) is even
 Odd parity: number of bits 1
(including parity bit, excluding
Start and Stop bits) is odd
 Requires retransmission if an
error is detected
 Simple implementation in
hardware

Telecomm. Dept. DCN-2013

42
Faculty of EEE HCMUT
 Parity Check
 Info Bits: b1, b2, b3, …, Encoder and decoder for single parity check code
 Check Bit: bk+1= b1+ b2+ b3+ …+ bk
 Codeword: [b1, b2, b3, …, bk+1]

 Receiver CAN DETECT all single-bit

errors& burst errors with odd
number of corrupted bits
 Single-bit errors CANNOT be
CORRECTED: position of corrupted
bit remains unknown
 All even-number burst errors are
undetectable
 What is the error detection
probability? (50%?)

Telecomm. Dept. DCN-2013

43
Faculty of EEE HCMUT
 Single parity check code C(5,4)

Telecomm. Dept. DCN-2013

44
Faculty of EEE HCMUT
 Parity Check: Example
Single Even parity check
Information (7 bits): [b1..b7]= [0, 1, 0, 1, 1, 0, 0]
Parity Bit: b8= (0 + 1 + 0 + 1 +1 + 0) mod 2 = 1
Codeword (8 bits): [0, 1, 0, 1, 1, 0, 0, 1]
If single error in bit 3 : [0, 1, 1, 1, 1, 0, 0, 1]
# of 1’s = 5, odd: Error detected ☺
If errors in bits 3 and 5: [0, 1, 1, 1, 0, 0, 0, 1]
# of 1’s = 4, even: Error not detected
If errors in bit 3, 5, 6 : [0, 1, 1, 1, 0, 1, 0, 1]
# of 1’s = 5, odd: Error detected ☺

Telecomm. Dept. DCN-2013

45
Faculty of EEE HCMUT
Block Sum Check (2-D Parity Check)
 Parity check can detect
single-bit errors
 Improve by adding BCC at
end, doing column-wise
parity
 Used in Asynchronous
transmission
 BCC defeated by four bits in
error
 BSC can:
 All 1-bit errors CAN BE
DETECTED and CORRECTED
 All 2-, 3- bit errors can be
DETECTED
 4- and more bit errors can
be detected in some cases

Telecomm. Dept. DCN-2013

46
Faculty of EEE HCMUT
 Example

Telecomm. Dept. DCN-2013

47
Faculty of EEE HCMUT
 Example
A transmitter sends an ASCII 7-bit sequence of
characters MOBIFONE to the receiver based on
asynchronous transmission using BSC (even parity in
rows, odd parity in columns)
Determine the BCC and the transmitted bit sequence if
MSB is transmitted first
During the transmission, 12th bit and 30th bit has error. Can
the receiver detect and correct the errors?

Telecomm. Dept. DCN-2013

48
Faculty of EEE HCMUT
 Cyclic Redundant Check
 Cyclic codes are special linear block codes with one extra property.
In a cyclic code, if a codeword is cyclically shifted (rotated), the
result is another codeword.
 Useful to detect error bursts
 Process Steps:
 For a block of k bits (message), transmitter generates an (n – k) bit
sequence. Known as the Frame Check Sequence (FCS)
 Transmit n bits which is exactly divisible by some number/generator
 Receiver divides frame by that number/generator
 If no remainder, assume no error
 Definition:
 T(x) : the transmitted codeword has n bits
 M(x) : the dataword to be transmitted has k bits
 G(x) : the divisor or generator has n-k+1 bits
 R(x) : remainder has n-k bit
 Q(x) : quotient

Telecomm. Dept. DCN-2013

49
Faculty of EEE HCMUT
 CRC procedure
 Transmitter:
 Multiply M(x) by xn-k: shift the binary stream to the left with n-k cycles
(n-k bits)
 Perform the division: n-k
x .M(x) Rx 
=Q  x  +
G x  G x 
 The codeword: T(x) = xn-k . M(x) + R(x)

Telecomm. Dept. DCN-2013

50
Faculty of EEE HCMUT
 CRC procedure
 Receiver: assuming that the error polynomial of the transmission
channel is E(x) with the same size of the transmitted polynomial
T(x). The receiver will get: System A System B

Y(x) = T(x) + E(x)

 Receiver perform: T(x) E(x) Y(x)

Y  x  T(x)+0 xn-k .M x  +R  x  xn-kM x  R  x  R x  R x 

= = = + =Q  x  + + =Q  x 
G(x) G(x) G x  G x  G x  Gx  Gx 
1 42 43
=0

 In case there is no error: there is no remainder in the above

division or the receiver can not detect errors. Otherwise, there is
errors

Telecomm. Dept. DCN-2013

51
Faculty of EEE HCMUT
CRC division using polynomials

Telecomm. Dept. DCN-2013

52
Faculty of EEE HCMUT
 Division in CRC encoder

Telecomm. Dept. DCN-2013

53
Faculty of EEE HCMUT
Division in the CRC decoder for two cases

Telecomm. Dept. DCN-2013

54
Faculty of EEE HCMUT
 A CRC code with C(7, 4)

Telecomm. Dept. DCN-2013

55
Faculty of EEE HCMUT
 CRC encoder and decoder

- If s(x) ≠ 0, one or more bits is corrupted.

- If s(x) = 0, either No bit is corrupted. Or Some bits are corrupted, but the
decoder failed to detect them.
Telecomm. Dept. DCN-2013
56
Faculty of EEE HCMUT
 CRC
 General design of encoder and decoder of a CRC code

Telecomm. Dept. DCN-2013

57
Faculty of EEE HCMUT
 CRC
 The CRC encoder
design using shift
registers

Telecomm. Dept. DCN-2013

58
Faculty of EEE HCMUT
 Standard polynomials

Telecomm. Dept. DCN-2013

59
Faculty of EEE HCMUT
 Example
Given the dataword M = 110101, G(x)= x3+1
Find the CRC and the codeword T(x)
If E=110100011, can the receiver detect the errors?
If E=000010010, can the receiver detect the errors?
Give the conclusion of CRC error detection based on the
relationship between E(x) and G(x)?
Design the shift-register for CRC encoder and decoder?

Telecomm. Dept. DCN-2013

60
Faculty of EEE HCMUT
 Data Compression
 Data compression implies sending or storing a smaller number
of bits.
 Benefits
Reduce storage needed
Reduce transmission cost / latency / bandwidth
 Although many methods are used for this purpose, in general
these methods can be divided into two broad categories:
lossless and lossy methods.
 Lossless
• Preserves all information
• Exploits redundancy in data
• Applied to general data
 Lossy
• May lose some information
• Exploits redundancy & human perception
• Applied to audio, image, video

Telecomm. Dept. DCN-2013

61
Faculty of EEE HCMUT
 Sources of Compressibility
Redundancy
Recognize repeating patterns
Exploit using
• Dictionary
• Variable length encoding
Human perception
Less sensitive to some information
Can discard less important data

Telecomm. Dept. DCN-2013

62
Faculty of EEE HCMUT
 Data Compression
 Packed Decimal: A packed decimal representation stores two
decimal digits in one byte. For example, the value 23 would be
stored in two nibbles, using the hexadecimal digits 2 and 3
(the bit representation would be 0010 0011).
 Relative coding: instead of transmitting the whole number
value, the transmitter only transmits the difference between
values.
 Character Suppression: when transmitting the same
continuous printable characters, all the same continuous
characters will be encoded with a representative character
and the number of this character. Example: AAAAABBBBCC =
A5B4C2

Telecomm. Dept. DCN-2013

63
Faculty of EEE HCMUT
 Huffman
 What is difference in this
table?
 Why the length of letter A,
E is shorter than the length
of letter Y, Z?

 What is the basic principle

to build this table?

Telecomm. Dept. DCN-2013

64
Faculty of EEE HCMUT
 Huffman code
 Huffman coding is statistical coding technique
 Approach
 Variable length encoding of symbols
 Exploit statistical frequency of symbols
 Efficient when symbol probabilities vary widely
 Principle
 Use fewer bits to represent frequent symbols
 Use more bits to represent infrequent symbols

A A B A

A A B A

Telecomm. Dept. DCN-2013

65
Faculty of EEE HCMUT
 Huffman Code Example
 Expected size
Symbol A B C D
Frequency 13% 25% 50% 12%
Original 00 01 10 11
Encoding 2 bits 2 bits 2 bits 2 bits
Huffman 110 10 0 111
Encoding 3 bits 2 bits 1 bit 3 bits

 Original  1/82 + 1/42 + 1/22 + 1/82 = 2 bits/symbol

 Huffman  1/83 + 1/42 + 1/21 + 1/83 = 1.75 bits/symbol

Telecomm. Dept. DCN-2013

66
Faculty of EEE HCMUT
 Huffman coding principle
Encoding
Calculate frequency of symbols
Create binary tree representing “best” encoding
Use binary tree to encode symbols
• For each symbol, output path from root to leaf
• Size of encoding = length of path
Save binary tree
Symbol Stage 1 Stage 2 Stage 3 Stage 4 Codeword
S0 0.4 0.4 0.4 0.6 0 00
1
S1 0.2 0.2 0.4 0 0.4 10
1
S2 0.2 0.2 0 0.2 11
S3 0.1 0 0.2 1 010
1
S4 0.1 011

Telecomm. Dept. DCN-2013

67
Faculty of EEE HCMUT
 Huffman coding principle
Decoding
Read compressed file & binary tree
Use binary tree to decode file
Follow path from root to leaf
Example:
Encoder Decoder

Telecomm. Dept. DCN-2013

68
Faculty of EEE HCMUT
 Performance Evaluation
 Entropy:
H=pi log2 (1/pi) (bits/symbol)
 Average length of codewords:
N =  piNi (bits/symbol)
 Variance: measure what?
2=pi .(Ni-N)2
 Efficiency of codeword set:
h = H/N
 Bit rate (after encoding):
Rb= RS.N (bps), RS is the symbol rate (symbol/s)
Telecomm. Dept. DCN-2013
69
Faculty of EEE HCMUT
 Huffman Code Properties
Prefix code
No code is a prefix of another code
Example:
• Huffman(“I”) 00
• Huffman(“X”) 001 // not legal prefix code
Can stop as soon as complete code found
No need for end-of-code marker
Nondeterministic
Multiple Huffman coding possible for same input
If more than two trees with same minimal weight

Telecomm. Dept. DCN-2013

70
Faculty of EEE HCMUT
 Run-Length coding
 Run-length encoding is probably the simplest method of compression. It
can be used to compress data made of any combination of symbols. It
does not need to know the frequency of occurrence of symbols and can be
very efficient if data is represented as 0s and 1s.
 The general idea behind this method is to replace consecutive repeating
occurrences of a symbol by one occurrence of the symbol followed by the
number of occurrences.
 The method can be even more efficient if the data uses only two symbols
(for example 0 and 1) in its bit pattern and one symbol is more frequent
than the other.

Telecomm. Dept. DCN-2013

71
Faculty of EEE HCMUT
 Run-Length coding
 Used in Black-White
Facsimile
 1 Page is divided into:
 Height: 3.85-7.7
lines/mm
 Width: 8.05 (pels/mm)

 Each unencoded Fax

page contains about
2Mb

Telecomm. Dept. DCN-2013

72
Faculty of EEE HCMUT
 Run-Length coding
 Each line in a page will have a
number of black/white pixel
continuous sequence
 Each continuous bit sequence is
encoded by
 Termination code: in the range 0..63
switches between black and white code
 Makeup code: can extend length of a
run by a multiple of 64
 EOL is inserted at the end of each
line (EOL=00000000001)
 End of each page will be ended with
6 EOL

Telecomm. Dept. DCN-2013

73
Faculty of EEE HCMUT
 Run-Length coding
 Example 1: line with 2 w, 4 b, 200
w, 3 b, EOL!
0111 011 010111 10011 10 00000000001

 Example 2:

What is the transmitted bit stream?

Telecomm. Dept. DCN-2013

74
Faculty of EEE HCMUT
 Lempel Ziv encoding
 Lempel Ziv (LZ) encoding is an example of a category of
algorithms called dictionary-based encoding. The idea is to
create a dictionary (a table) of strings used during the
communication session. If both the sender and the receiver
have a copy of the dictionary, then previously-encountered
strings can be substituted by their index in the dictionary to
reduce the amount of information transmitted.

Telecomm. Dept. DCN-2013

75
Faculty of EEE HCMUT
 Lossy Compression Methods
JPEG (Joint Photographic Experts Group)
MPEG (Moving Picture Experts Group)
MP3 (MPEG audio layer 3)

Telecomm. Dept. DCN-2013

76
Faculty of EEE HCMUT