Truyền thông số Digital Communication-Week 9

Ố

Ề

TRUY N THÔNG S DIGITAL COMMUNICATION

Week 9

•

Reference “Digital communications: Fundamentals and Applications” by Bernard Sklar

• Telecommunication Networks - Information Theory, Vinh

Dang

(*) H Văn Quân – Khoa CNTT – ĐH Bách Khoa TpHCM ồ

[1]. R. E. Ziemer & W. H. Transter, “Information Theory and

Coding”, Principles of Communications: Systems, Modulation, and Noise, 5th edition. John Wiley, pp. 667-720, 2002.

[2]. A. Bruce Carlson, “Communications Systems”, Mc Graw-

Hill, 1986, ISBN 0-07-100560-9

[3]. S. Haykin, “Fundamental Limits in Information Theory”,

Communication Systems, 4th edition, John Wiley & Sons Inc, pp. 567-625, 2001

Tu n tr ầ

c ướ

ộ ả

• B gi i mã Maximum likelihood • Quy t đ nh m m / c ng (soft decisions

ế ị

ứ

ề

and hard decisions) i thu t Viterbi

• Gi

ả

ậ

Block diagram of the DCS

Modulator

Information source

Rate 1/n Conv. encoder

U

,...) 

mm=m im ( , ,...,     1 Input sequence

,...) 

C h a n n e

u 1 i 

= G(m) = ( UUU , ,    1 2 Codeword ,...,u   Branch wo ( rd

U ,...,  i sequence ,...,u   n coded bits)

Demodulator

Information sink

,...,

,...)

mm=m ˆ ˆ,ˆ( 1

Rate 1/n Conv. decoder =Z ˆ im

,...) 

ZZZ Z ( , , ,...,     i 1 2 3 received sequence z ,...,z ,...,z 1 i      n outputs per Branch wor

Z  i Demodulato for

Branch wor

outputs i d

Quy t đ nh m m / c ng

ế ị

ứ

ề

Gi

i thu t Viterbi

ả

ậ

i thu t Viterbi bi u di n gi

i mã Maximum

• Gi

ể

ễ

ả

ấ

ng có s t ự ươ ỏ

ng quan l n nh t ớ ấ

ậ likelihood. • Nó tìm 1 đ ườ ả ặ Là 1 quá trình l p. ặ

ho c kho ng cách nh nh t. – – Trong m i b

ỗ ướ

the ả ọ ỏ ng nào đ ỉ ữ ườ ng s ng ( ố ườ

c tính toán, nó ch gi có kho ng cách nh nh t, g i là đ ấ survivor).

Ví d ½ Conv. code

ụ

Tail bits

Input bits

1

0 11 0/00

10 0/00

1 Output bits 00 0/00

11 0/00

10 0/00

1/11

0/11

1/00

0/10

1/01

0/01

1/01

VD 1 hard-decision Viterbi decoding

11(=Z

)01

ˆ =m ˆ =U

( 10000 ) 11( 10

)11

(=m 11(=U

10100 ) 10

)11

2

1

2

1

0

1

2

0

(

)

Partial metric ),

( tS

0

1

2

Branch metric

1

VD 1 soft-decision Viterbi decoding

,1,

)1,

,1(

2 3

ˆ =m ˆ =U

( 10100 ) 11( 10

)11

2 2 2 3 3 3 (=m 10100 ) 11(=U 10

)11

-5/3

10/3

1/3

14/3

- - - -

-5/3

-1/3

0 1/3

5/3

8/3

5/3

1/3

-1/3

-5/3

1/3

4/3

5/3

13/3

5/3

-4/3

-5/3

5/3

1/3

10/3

-5/3

Tu n này

ầ

• Mã hóa kênh (Channel Coding):

ự

• Mã hóa ngu n (Source Coding):

– S đan xen (Interleaving) – Mã ghép (Concatenated codes) – Mã Turbo (Turbo Codes) ồ

ồ

ế

ồ

ế ả ủ

ệ

ồ

– Ngu n (sources) – Entropy và Information rate – Lý thuy t mã hóa ngu n (Thuy t Shannon) – Hi u qu c a mã hóa ngu n – Mã Shannon-Fano – Mã Huffman

S đan xen (Interleaving)

ự

• Mã ch p ậ (Convolutional codes) thích h p cho

ợ

ề

ớ (memoryless channels) vì (random error events).

kênh truy n không nh i là ng u nhiên các l ẫ

ỗ

, có lo i l

i chùm (bursty errors) vì

ạ ỗ ớ

• Trên th c t ự ế ề i trong kênh multipath fading, l ụ ỗ

kênh truy n có nh (channel with memory). – Ví d : l ễ

• S đan xen (Interleaving) giúp cho kênh truy n

ề

ự ở

tr thành nh kênh truy n không nh ớ (memoryless channel)

i mã.

ề b gi ở ộ ả

i do nhi u … ỗ

Interleaving …

• S đan xen đ

ự

ệ

ề

ằ ượ coded symbols theo th i gian tr c l

ờ i đ u thu g i là gi

• Quá trình ng

i đan xen

c th c hi n b ng cách chia các c khi truy n đi. ướ ọ

i t ượ ạ ạ ầ

ả

(deinterleaving).

ỗ

i chùm (bursty errors) gi ng ố  có

• S đan xen giúp cho l ẫ

nh tr thành l th dùng mã ch p.

ự ư ở ể

i ng u nhiên (random errors) ỗ ậ • Các lo i đan xen: ạ

– Đan xen kh i (Block interleaving) – Đan xen ch ng ch p/chéo (Convolutional or cross ậ

ố ồ interleaving)

Ví d minh h a

ụ

ọ

A1 A2 A3 B1 B2 B3 C1 C2 C3

– Xét 1 mã có 3 coded bits. – N u 1 chùm l i có đ dài 3 bit: ế ộ ỗ

2 errors

– N u dùng 1 kh i đan xen 3X3: ố

ế

A1 A2 A3 B1 B2 B3 C1 C2 C3

A1 B1 C1 A2 B2 C2 A3 B3 C3

Interleaver

Deinterleaver

A1 B1 C1 A2 B2 C2 A3 B3 C3

A1 A2 A3 B1 B2 B3 C1 C2 C3

1 errors 1 errors

1 errors

Ví dụ Đan xen ch ng ồ ch pậ

i mã Viterbi

ườ

ả

ở

ph n mã hóa

ng 1 mã ghép dùng mã ch p và gi ầ

ở

an inner code ố ộ

Mã ghép (Concatenated codes) • Mã ghép dùng 2 l n mã hóa, g i là mã hóa trong và ọ ầ mã hóa ngoài (có t c đ cao h n) - ơ and an outer code (higher rate). – Thông th ậ ph n mã hóa trong, mã Reed-Solomon ầ ngoài

Interleaver

Modulate

Input data

Outer encoder

Inner encoder

C h a n n e

Deinterleaver

Demodulate

Output data

Outer decoder

Inner decoder

• Mã ghép gi m s ph c t p, tăng hi u qu s a l ứ ạ i. ả ử ỗ ự ệ ả

Mã Turbo (Turbo codes)

• Mã Turbo là mã ghép nh ng có thêm gi

i ả

thu t l p (iterative algorithm)

ậ ặ

• Dùng soft-decision  l p nhi u l n đ có

ề ầ

ể

ặ

giá tr tin c y h n.

ậ

ị

ụ

ạ

Ví d 1 d ng mã Turbo: RSC code

Mã hóa ngu n (Source Coding)

ồ

• Ngu n (sources) • Entropy và Information rate • Lý thuy t mã hóa ngu n (Thuy t

ế

ồ

ế Shannon)

ệ

ả ủ

ồ

• Hi u qu c a mã hóa ngu n • Mã Shannon-Fano • Huffman Coding

Ngu n tin - Sources

ồ

• Ngu n tin ta đang xét là ngu n r i r c (discrete sources) có ồ ờ ạ ồ

1 chu i X(k), k =1… N symbols ỗ

j là P(XJ)

ấ ủ ỗ • Xác su t c a m i symbol X

XI (

)

log

(

)

ị ơ ị • Ta đ nh nghĩa I(XJ) - self-information là đ n v thông tin:

Ngu n tin - Sources

ồ

bit/symbol

( XH

)

• Tr trung bình c a các symbol g i là source entropy: ủ ọ ị

E

({

)}

( XIp

)

log

(

)

= 1

(cid:229) (cid:229)

• E{X} là giá tr trung bình (expected value) c a ủ X. ị

• Source entropy H(X): l ng thông tin trung bình c a ngu n ượ ủ ồ

tin X là l ng tin trung bình ch a trong m t kí hi u b t kỳ ượ ứ ệ ấ ộ Xj

X. c a ngu n tin ủ ồ

Entropy và Information rate

• Entropy = information = uncertainty

• N u 1 tín hi u hoàn toàn có th tiên đoán đ c ế ệ ể ượ

(completely predictable), thì entropy = 0 và không có

thông tin

( XH

)

log

• Entropy = là s bits trung bình đòi h i đ truy n tín hi u ệ ỏ ể ề £ £ ố 0

Ví d (*):ụ

Tr l

ả ờ

Lý thuy t mã hóa ngu n

ế

ồ

• T c đ ngu n thông tin - Source information rate

ố

ồ

ộ

(bit/s):

Rs = rH(X) (bit/s)

– H(X): entropy ngu n (bits/symbol) ồ

• Gi

ả ử

s ngu n này là đ u vào c a 1 kênh : ầ

ủ

ồ

– r : t c đ symbol (symbol rate) (symbols/s) ộ ố

– C: dung l ng - capacity (bits/symbol) ượ

– S: t c đ symbol - available symbol rate (symbols/s) ố ộ

– S.C = bits/s

Mã hóa ngu n (t.t)

ồ

• Thuy t Shannon (noiseless coding theorem):

ế

ộ

ề

ồ

ộ

ể

ề

ằ

ng kênh truy n.

– Cho m t kênh truy n và m t ngu n phát sinh thông tin. Ta có th mã hóa ngu n b ng cách phát trên kênh truy n này khi ồ ngu n tin có t c đ nh h n dung l ộ

ỏ ơ

ượ

ề

ố

ồ

– “Given a channel and a source that generates information at a rate less than the channel capacity, it is possible to encode the source output in such a manner that it can be transmitted through the channel”

Ví d Source encoding

ụ

C = 1 bit/symbol

Source encoder

Binary channel

Discrete binary source

S = 2 symbols/s

SC = 2 bits/s

Tốc độ symbol nguồn (Source symbol rate) = r = 3.5 symbols/s

p=0.9), B (p=0.1) • Cho ngu n nh phân r i r c: A ( ị ờ ạ ồ

• Source symbol rate (3.5) >channel capacity (2)  ngu n ồ

symbols không th truy n đi tr c ti p ể ự ế ề

– H(X)= -0.1 log20.1 -0.9log20.9 = 0.469bits/symbol

– Rs = rH(X) = 3.5(0.469)=1.642 bits/s < S.C = 2 bits/s

• Ki m tra thuy t Shannon: ể ế

ể • Có th truy n đi b ng cách mã hóa ngu n đ gi m t c đ ộ ể ả ề ằ ố

ồ symbol trung bình (average symbol rate)

• Codewords đ

c nhóm thành

n-symbol

ượ

groups of source symbols

• Quy lu t:ậ

– Codewords ng n nh t gán cho nhóm có xác su t

ấ

ắ ấ Shortest codewords for the

x y ra nhi u nh t ( ề ả most probable group)

ấ

– Codewords dài nh t gán cho nhóm có xác su t ấ ấ Longest codewords for the least

x y ra ít nh t ( ả probable group)

• Có n -symbol groups t c là có n b c m r ng ứ

ở ộ

ậ

(n th-order extension of original source)

First-Order extension

P () Codeword

[P()].[Number of Code Symbols] Source symbol

A 0.9 0 0.9

B 0.1 1 0.1

L: độ dài code trung bình (average code length)

L=1.0

( xp i

l i

= 1

p(xi): xác suất của symbol thứ i th

li : độ dài của codeword tương ứng với symbol thứ i th

(cid:229)

Second-Order extension

Source symbol P () Codeword [P()].[Number of Code

0.81 0 0.09 10 0.09 110 0.01 111

Symbols] 0.81 0.18 0.27 0.03

AA AB BA BB L=1.29

Grouping 2 source symbols at a time:

( xp i

l i

= 1

(cid:229)

Second-Order extension

645.0

code symbols/so

urce symbol

L n

29.1 2

)645.0(5.3

258.2

L n

code symbols/sec >2

Tốc độ symbol (symbol rate) tại ngõ ra bộ mã hóa:

 Tốc độ symbol > dung lượng kênh là 2 symbols/second

 Ta tiếp tục làm mã hóa mở rộng bậc 3 (the thirdorder extension)

Third-Order extension

P ()

Codeword [P()].[Number of Code Symbols] 0.729 0.243 0.243 0.243 0.045 0.045 0.045 0.005

0.729 0 0.081 100 0.081 101 0.081 110 0.009 11100 0.009 11101 0.009 11110 0.001 11111

Source symbol AAA AAB ABA BAA ABB BAB BBA BBB L=1.598

Grouping 3 source symbols at a time:

Third-Order extension

533.0

L n

598.1 3

code symbols/source symbol

864.1)533.0(5.3

code symbols/se

cond

L n

The symbol rate at the encoder output:

 Kênh truy n ch p nh n t c đ này ấ ậ ố ề ộ

Hi u qu c a mã hóa ngu n

ả ủ

ệ

ồ

min

eff

min L

• Efficiency là th ướ c đo đo hi u qu c a mã hóa ngu n ả ủ ệ ồ

( i lxp ) i

= 1

where

H(X): entropy nguồn

min

(= XH log

) D

D : số symbols trong coding alphabet

eff



( XH log

) D

)

for a binary alphabet

eff

( XH L

(cid:229)

ệ

ả ủ

ồ

Hi u qu c a mã hóa ngu n nh ị phân

n b c ậ :

ồ

ở ộ

ệ

)

• Entropy c a ngu n m r ng ủ H (X n)=n*H (X) • Hi u qu c a ngu n m r ng: ả ủ .=

eff

ồ ( XHn L

Mã Shannon-Fano[1]

ồ

G m 3 b ướ t kê source symbols theo th t 1. Li ệ d nầ

2. Chia chúng thành 2 nhóm nh : “ỏ 0” đ t cho nhóm

ứ ự xác su t gi m ấ ả

ặ

trên và “1” cho nhóm d iướ

3. Ti p t c chia t ế ụ

i khi không th chia n a ớ ữ ể

Ví d v Shannon-Fano Coding

ụ ề

5 Codewords

Ui pi

.34

.23

.19

110

.07

1110

.06

11110

.01

11111

Shannon-Fano coding

45.2

= (cid:229)

ilp

= 1

UH (

)

log

37.2

-= (cid:229)

p i

= 1

)

eff

97.0

UH ( L

37.2 45.2

Th c hi n theo 3 b

Huffman Coding [1][2][3] ệ

ướ

ự

1. Li

t kê source symbols theo th t ệ

ầ ả c gán 0 và xác su t gi m d n. ỏ ứ ự ấ

ấ Hai source symbols có xác su t nh nh t đ ấ ượ 1.

ế ợ

ấ ằ ấ ố ấ ổ

2. Hai source symbols này k t h p thành 1 source symbol m i có xác su t b ng t ng 2 xác su t g c. Xác su t ớ m i đ ớ ượ in accordance with its value.

c ghi vào The new probability is placed in the list

3. L p l

i cho t i khi xác su t m i k t h p cu i cùng = 1.0. ớ ớ ế ợ ấ ố ặ ạ

Examples of Huffman Coding

1.0

Codewords

pi .34

Ui U1

.58

Ui U1

.42

.23 .19

U2 U3

.24

011

0100

.1 .07

U4 U5

.14

01010

.07

01011

.06 .01

U6 U7

Khuy t đi m c a Huffman Coding

ủ

ể

ế

• Khi ngu n có nhi u symbols thì mã Huffman tr ở

ề

ồ

nên quá l n.ớ

• V n còn nhi u s d th a (redundancy)

ự ư ừ

ề

ẫ

• S codewords tăng theo c p s mũ

ấ

ố

(exponentially), mã tr nên ph c t p và tăng đ ộ

ứ ạ

ở

trì hoãn.

Bài t pậ

• M t ngu n r i r c có 3 sysbols: A, B, và C v i xác

ớ

ộ ồ ờ ạ ng ng là 0.9, 0.08 và 0.02. Tìm entropy su t t ứ ấ ươ c a ngu n ồ ủ

Bài t pậ

ẽ ơ ồ ạ ệ ố ủ

V s đ tr ng thái (dùng trellis diagram) c a h th ng RSC trên

Next time

ng ngh 1. Ngày 3/5 nhà tr ỉ 2. Ngày 10/5: bu i h c cu i: ố ể ố ể

ề

ậ

ườ ổ ọ – Công b đi m gi a kỳ (đi m bài t p v nhà) ữ – H c ti p + Ôn t p ế

ậ

ọ

Bài t p n p cho GV ộ

ậ

ổ ọ

ỗ

• Cách 1: n p tr c ti p cho GV (sau m i bu i h c) ự ế • Cách 2: g i email t ớ

ộ ử

truyenthongsodtvt@gmail.com

ộ

ờ ạ

ọ

ố

• Th i h n n p bài: th ba ngày 26 tháng 4 ứ • Trong email và file n p ghi rõ h tên và mã s SV ộ • Đi m bài t p: 30% t ng đi m ổ

ể

ậ

• H n chót nh n email: th 2 ngày 2/5

ứ

ậ

ạ

Bài t p n p cho GV ộ

ậ

ọ

Ch n 1 trong các bài sau: 1. Tìm hi u v Non-coherent detection (D-

ề

ể

PSK và Bin D-PSK)

ề

ể

ỏ

ể ề

ủ

ể

2. Tìm hi u v Cyclic block codes 3. Dùng Matlab mô ph ng đ so sánh s ự khác nhau c a các ki u đi u ch (v ế ẽ SNR vs PE)

Truyền thông số Digital Communication-Week 9

Chủ đề:

Điện toán biên mạng phân tán

Ố

Ề

TRUY N THÔNG S DIGITAL COMMUNICATION

Reference “Digital communications: Fundamentals and Applications” by Bernard Sklar

Tu n tr ầ

c ướ

Block diagram of the DCS

U

Quy t đ nh m m / c ng

ế ị

ứ

ề

Gi

i thu t Viterbi

ả

ậ

Ví d ½ Conv. code

ụ

1

0

0

0

11 0/00

10 0/00

1 Output bits 00 0/00

11 0/00

10 0/00

1/11

1/11

1/11

0/11

0/11

0/11

1/00

0/10

0/10

0/10

1/01

1/01

0/01

0/01

1/01

2

1

2

1

1

1

0

0

0

1

1

1

2

0

0

1

2

2

1

1

-5/3

-1/3

-1/3

0

1/3

1/3

0

1/3

5/3

1/3

-1/3

-5/3

1/3

4/3

5/3