Chương 5 mã hóa kênh

3/22/2010

Nội dung trình bày:

CHƯƠNG 5: MÃ HÓA KÊNH

(cid:1) Mã hóa kênh ( Channel coding ) (cid:1) Mã hóa khối (Block codes) + Mã lập (Repetition Code) + Hamming codes + Cyclic codes

* Reed-Solomon codes

ðặng Lê Khoa Email: dlkhoa@fetel.hcmuns.edu.vn

(cid:1) Mã hóa chập (Convolutional codes)

+ Encode + Decode

(cid:1) ðiều chế mã lưới (Trellis Coded Modulation)

Facuty of Electronics & Telecommunications, HCMUS

Channel coding là gì?

Sơ ñồ khối DCS

• Tín hiệu truyền qua kênh truyền sẽ bị ảnh hưởng bởi nhiễu, can nhiễu, fading… là tín hiệu ñầu thu bị sai. • Mã hóa kênh: dùng ñể bảo vệ dữ liệu không bị sai bằng cách thêm vào các bit dư thừa (redundancy).

Format

Source encode

Channel encode

Pulse modulate

Bandpass modulate

• Ý tưởng mã hóa kênh là gởi một chuỗi bit có khả

năng sửa lỗi

Digital modulation

• Mã hóa kênh không làm giảm lỗi bit truyền mà chỉ làm

giảm lỗi bit dữ liệu (bảng tin)

C h a n n e

Digital demodulation

• Có hai loại mã hóa kênh cơ bản là: Block codes và

Convolutional codes

Format

Detect

Source decode

Demod. Sample

Channel decode

Các loại mã hóa sửa sai

Mã lập

(cid:1) Mã lập (Repetition Code) (cid:1) Mã khối tuyến tính (Linear Block Code), e.g.

Hamming

Recovered state

(cid:1) Mã vòng (Cyclic Code), e.g. CRC (cid:1) BCH và RS Code (cid:1) Mã chập (Convolutional Code) (cid:1) Truyền thống, giải mã Viterbi (cid:1) Mã Turbo (cid:1) Mã LDPC

(cid:1) Coded Modulation

(cid:1) TCM (cid:1) BICM

3/22/2010

Mã khối tuyến tính (Linear block codes)

Kiểm tra chẵn lẻ (Parity Check)

(cid:1) Chuỗi bit thông tin ñược chia thành từng khối k bit. (cid:1) Mỗi khối ñược encode thành từng khối lớn hơn có

(cid:1) Thêm 1 bit ñể xor các bit có kết quả là 0 (cid:1) Dữ liệu truyền, sửa lỗi, không thể sửa lỗi

n bit.

(cid:1) Các bit ñược mã hóa và gửi trên kênh truyền. (cid:1) Quá trình giải mã ñược thực hiện ở phía thu.

Data block

Codeword

Channel encoder

k bits

n bits

n-k

Redundant

bits

(cid:1) Kiểm tra hàng và cột

Code rate

(cid:1) Ứng dụng: ASCII, truyền dữ liệu qua cổng nối

R c

k n

tiếp

Linear block codes – cont’d

(cid:1) Khoảng cách Hamming giữa hai vector U và V, là

số các phần tử khác nhau.

(cid:1) Khả năng phát hiện lỗi ñược cho bởi: e

min

- ¯

VU

VU,

)

(

= w (

= d (cid:1) Khả năng sửa lỗi t của mã hóa ñược ñịnh

) (cid:1) Khoảng các tối thiểu của mã hóa khối là

w (

U

)

UU , i

min

nghĩa là số lỗi tối ña có thể sửa ñược trên 1 từ mã (codeword)

d (min i j

min i

= ) (cid:1) Ví dụ: Tính khoảng cách Hamming của C1: 101101

„

và C2 :001100

  

  

mind 2

101101

001100

Giải: Vì =>d12=W(1000001)=2 100001 (cid:1) => Ta có thể giải mã ñể sửa sai bằng cách chọn

codewords có dmin

- ¯

Linear block codes – cont’d

(cid:1) Example: Block code (6,3)

(cid:1) Encoding trong bộ mã hóa khối (n,k)

Message vector Codeword

U =

mG

V

G

…

)

(

)

0 0 0

0 0 1

0 1 0

0 0 1

0 1 1

0 0 0 1 0 0

0 0 1

0 1 0

( uu , 1

, mm 1 2

(cid:215)

V 1 V 2 ⋮

V V

0 1

1 0

1 1

0 0

1 0

0 1

    

    

    

    

0 1

1 0

0 1 1 1

0 0

1 1

1 0

      +

(cid:215) (cid:215) (cid:215)

     V  k + …

…

)

( uu , 1

m 1

V 1

V 2

V k

(cid:1) Các hàng của G thì ñộc lập tuyến tính.

1 0 1

0 1 1

1 0 1 1 1 0

1 1 0

1 0 0

1 0 1

0 1 1

1 1 1

3/22/2010

Linear block codes – cont’d

(cid:1) Mã hóa khối (n,k)

(cid:1) k phần tử ñầu tiên (hoặc cuối cùng) trong từ mã là các

)

bit thông tin.

· -

G

]

0

IPG [ ·=

I

k identity

matrix

(cid:1) ðối với bất kỳ mã hóa khối tuyến tính, chúng (H ta có một ma trận . Các hàng của kn ma trận này trực giao với ma trận : GH =T (cid:1) H ñược gọi là ma trận kiểm tra parity và các

·= k

(

)

matrix

k P k

hàng của chúng ñộc lập tuyến tính.

,...,

)

(

,...,

)

uu , ( 1

mm , 1

pp m , , (cid:3)(cid:3)(cid:4)(cid:3)(cid:3)(cid:5)(cid:6)(cid:3)(cid:3) (cid:4)(cid:3)(cid:3) (cid:5)(cid:6) k 1

(cid:1) ðối với mã hóa khối truyến tính: ]

- T

= IH [

P

parity

bits

message bits

- kn

Linear block codes – cont’d

m

U

Data source

Format

Modulation

Channel encoding

(cid:1)

channel

(cid:1) Mảng tiêu chuẩn i Hàng ñược tạo thành bằng cách cộng U với pattern

,...,3,2 ie

Data sink

Format

Channel decoding

Demodulation Detection

r

mˆ

zero codeword

⋯

U

U 1

= + eUr codeword received or vector

,....,

r

)

⋯

¯ ¯

e

2 U

e

2 U

pattern

or vector

(

e

error

)

rr ,( 2 1 ee , 2 1

r n e n

coset

e 2 ⋮

⋯

⋮

⋱

,...., (cid:1) Kiểm tra ñặc trưng:

⋯

¯ ¯ - - -

e

U

e

U

coset leaders

(cid:1) S là ñặc trưng của r, tưng ứng với error pattern e. =

= rHS

eH

Linear block codes – cont’d

(cid:1) Ví dụ: Mảng chuẩn cho mã (6,3)

(cid:1) Mảng tiêu chuẩn và ñặc trưng bảng giải mã

codewords

TrHS =

000000 110100 011010 101110 101001 011101 110011 000111

S

ˆ += rU =+=

mˆ ++

=++

011011 011000 011100 101111 101100 101010 101000 101011 101101 011100 011111 011010 110010 110001 110111 000110 000101 000110 000001 000010 000100 110101 110111 110011

1. Tính e =ˆ 2. Tìm coset chính , tưng ứng với . ˆ e 3. Tính và tưng ứng với . ˆ ˆ e)Ue ( (eUe

)ˆ e

⋮ ⋮ ⋮

ˆ rU (cid:1) Chú ý:

coset

• •

Nếu , error ñược sửa. Nếu , bộ giải mã không thể phát hiện lỗi.

⋮ 001000 010000 100000 111100 100100 010100

e =ˆ e „ˆ

e e

⋯ ⋯ 010001 100101 010110

Coset leaders

3/22/2010

Linear block codes – cont’d

Hamming codes

(cid:1) Hamming codes

Error pattern Syndrome

000000

000

U

(101110)

transmit

ted.

(cid:1) Là trường hợp riêng của linear block codes (cid:1) Diễn tả theo hàm của một số nguyên . 2‡m

is received. r is of

computed

Code length

(001110) syndrome =

H

r The = rHS

(001110)

(100)

2 =

Number

informatio

bits

: k

correspond

ing

this syndrome

2 =

000001 000010 000100 001000 010000 100000

101 011 110 001 010 100

Number

parity

bits

- -

Error = ˆ e

pattern (100000)

010001

111

n-k =

Error

correction

capability

: t

corrected

vector

=+=

is +

estimated =

The ˆ rU

ˆ e

(001110)

(100000)

(101110)

Mã hóa Hamming

Hamming codes

(cid:1) Example: Systematic Hamming code (7,4)

(cid:1) Mã hóa: H(7,4)

Message=[1 0 1 0]

H

[

I

]

  1110001   1101010     1011100  

r=(1+0+0) mod 2 =1 s=(1+0+1) mod 2 =0 t=(0+1+0) mod 2 =1

Code=[ 1 0 1 1 0 1 0 ]

Nhiều phép kiểm tra tổng Message=[a b c d] r= (a+b+d) mod 2 s= (a+b+c) mod 2 t= (b+c+d) mod 2 Code=[r s a t b c d]

(cid:1) Tốc ñộ mã: 4/7

G

[

P

I

]

44·

(cid:1) Càng nhỏ, nhiều redundance bit, ñược bảo vệ tốt hơn. (cid:1) Khác biệt giữa phát hiện và sửa lỗi

 0001110  0010101   0100011  1000111 

     

Hamming codes

Ví dụ mã hóa Hamming

(cid:1) Example: Systematic Hamming code (7,4)

H

[

I

]

H(7,4) (cid:1) Ma trận sinh G: ñầu tiên là ma trận ñơn vị 4x4 (cid:1) Dữ liệu truyền là vector p (cid:1) Vector truyền x (G=[I/P])

  1110001   1101010     1011100  

G

P

I

[

]

44·

(cid:1) Vector nhận r và vector lỗi e

 0001110  0010101   0100011  1000111 

     

3/22/2010

ðộ lợi mã hóa (Coding Gain)

Sửa lỗi (cid:1) Nếu không có lỗi, vector ñặc trưng (syndrome) z=zeros

(cid:1) Tốc ñộ mã R=k/n, k: số symbol dữ liệu, n tổng

symbol

(cid:1) SNR từ và SNR của bit

(cid:1) Nếu có 1 lỗi ở vị trí thứ 2

(cid:1) Vector ñặc trưng z là

(cid:1) Với một sơ ñồ mã hóa, ñộ lợi mã hóa tại một

sắc xuất lỗi bit ñược ñịnh nghĩa là sự khác biệt giữa năng lượng cần thiết cho 1 bit thông tin ñã mã hóa ñể ñạt ñược sắc xuất lỗi cho trước và truyền dẫn không mã hóa

tương với cột thứ 2 của H. Vậy, lỗi ñuợc phát hiện ở vị trí thứ 2 và có thể sửa lại cho ñúng.

Example of the block codes

Ví dụ ñộ lợi mã hóa

8PSK

QPSK

[dB]

0NEb /

Cyclic block codes

Cyclic code

(cid:1) Cyclic codes ñược quan tâm và quan trọng vì

(cid:1) Một mã tuyến tính (n,k) ñược gọi là Cyclic

(cid:1) Dựa trên cấu trúc ñại số và có thể ứng dụng rộng

rãi.

code nếu khi dịch vòng 1codeword thì ñó cũng là codeword.

“i” cyclic shifts of U

U

,...,

)

(cid:1) Dễ dàng thực hiện bằng thanh ghi dịch (shift register) (cid:1) ðược ứng dụng rộng rãi trong thực nghiệm

i )(

uuu , ( 1 =

U

0 u (

2 u

1 n u ,...,

,...,

)

+- 1

uuu , 1

- - - -

(cid:1) Ví dụ: = U

(cid:1) Trong thực nghiệm, cyclic codes ñược sử dụng ñể phát hiện lỗi (Cyclic redundancy check, CRC) (cid:1) ðược sử dụng trong mạng chuyển mạch gói (cid:1) Khi có 1 lỗi ñược phát hiện ở bộ nhận, chúng sẽ

)1(

)2(

)3(

)4(

( 1101 ) =

ñược yêu cầu truyền lại.

( 1110

U

)

U

(

0111

)

U

( 1011

)

U

( 1101 )

U

(cid:1) ARQ (Automatic Repeat-reQuest)

3/22/2010

Cyclic block codes

(cid:1) Cấu trúc ñại số của Cyclic codes, suy ra

(cid:1)

( Xm

)

(Xg

U

)

(

degree

n- )1(

Thuật toán mã hóa Cyclic code (n,k): knX - 1. Nhân thông tin với chuỗi bằng ) 2. Chia kết quả bước 1 với ña thức sinh .

codewords ñược sinh ra từ -++ ...

+ XuXu 1

Xu n 1

( Xp

(cid:1) Mối quan hệ giữa codeword và thanh ghi

( X

)

X kn m-

3. Thêm vào ñể tạo thành

dịch:

U XX (

)

...,

Lấy là phần dư ) ) ( Xp ( XU ) codeword

Xu n 1

+ XuXu +

Xu n 2

Xu n 1

u (cid:6) n

)1(

- - - - - - -

+ XuXu (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) 1 1 U

(

)1(

Xu n 2 ++ + n 2 1 ... (cid:5) (cid:4) (cid:3)(cid:3)(cid:4)(cid:3)(cid:3)(cid:5)(cid:6)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) 1 X ( ) +

U

(

)

(

U

()1(

)

U XX (

)

modulo (

(cid:1) Vậy:

By extension

U

i ()(

)

U

(

)

modulo

(

Cyclic block codes

(cid:1)

Find the generator and parity check matrices, G and H, respectively.

(cid:1) Example: For the systematic (7,4) Cyclic 1)

+ XX

= g ( X (cid:215)+= 11) X (cid:215)+ 0 X ⇒(cid:215)+ X 1 ( , , ) ( 1101 ) gggg , 1

g X ( 1011 )

(=m

code with generator polynomial Find the codeword for the message 1. =

Not in systematic form. We do the following:

row(3)

+ +

row(1) row(1)

row(3) row(2)

row(4)

= = - n kn k ,7 = 3 += + = ,4 ⇒ m m ( 1011 ) ( X X X G - ﬁ 1) = = + + = + + m m X X ) ( X ) X ( X 1( X X ) X X X ﬁ 0101100 1011000  0001011  0010110           - m X : g by Divide + + + + X X X + XX 1() X X X) ( ( ) += + + 2 3 XX 1( ) (cid:3)(cid:3)(cid:3) (cid:5)(cid:6) (cid:3)(cid:4)(cid:3)(cid:5)(cid:6)(cid:3)(cid:3)(cid:3) (cid:4) quotient (X) q

generator g

(X)

)

1 (cid:3)(cid:4)(cid:3)(cid:5)(cid:6) ( remainder X

p

H

 1101001  0111010   1110100 

    

33·I

G Form : the codeword polynomial = + += + +  0001011  0010110   0100111  1000101        ( X 1) X ( p X X X X ( = U U

P

44·I

message

bits

X m ) ) )1 1 0 1 0 0 1( (cid:4)(cid:5)(cid:6)(cid:4)(cid:5)(cid:6) parity bits

Ví dụ CRC

Cyclic block codes

(cid:1) Giải mã Cyclic code:

(cid:1) Từ mã ở bộ thu ñược cho bởi r e (

U

)

(

)

Error pattern

Received codewor d

(cid:1) ðặc trưng ở phần dư có ñược bằng cách chia chuỗi nhận

cho ña thức sinh: =

Syndrome

r (

)

q (

g ()

)

S (

)

(cid:1) Với ñặc trưng và mảng tiêu chuẩn, lỗi sẽ ñược ước

lượng.

3/22/2010

Checking for errors

Khả năng của CRC

(cid:1) Một lỗi E(X) không thể phát hiện khi chúng chia hết cho G(x). Ngược lại, thì có thể phát hiện lỗi.

(cid:1) Có khả năng mạnh mẽ trong phát hiện lỗi

BCH Code

BCH Performance

(cid:1) Bose, Ray-Chaudhuri, Hocquenghem

(cid:1) Có khả năng sửa ñược nhiều lỗi (cid:1) Dễ dàng thực hiện mã hóa và giải mã

(cid:1) Các chuẩn trong công nghiệp

- (511, 493) mã hóa BCH trong ITU-T. Chuẩn H.261- một chuẩn mã hóa video ñược sử dụng cho video conferencing và video phone. (cid:1) (40, 32) mã hóa BCH trong ATM (Asynchronous

Transfer Mode)

Reed-Solomon Codes

(cid:1) Một trường hợp riêng của non-binary BCH (cid:1) ðược ứng dụng rộng rãi

(cid:1) Storage devices (tape, CD, DVD…) (cid:1) Wireless or mobile communication (cid:1) Satellite communication (cid:1) Digital television/Digital Video Broadcast(DVB) (cid:1) High-speed modems (ADSL, xDSL…)