3/22/2010

Nội dung trình bày:
Mã hóa kênh ( Channel coding )
Mã hóa khối (Block codes)
+ Mã lập (Repetition Code)
+ Hamming codes
+ Cyclic codes
* Reed-Solomon codes
Mã hóa chập (Convolutional codes)
+ Encode
+ Decode
ðiều chế mã lưới (Trellis Coded Modulation)

CHƯƠNG 5: MÃ HÓA KÊNH
ðặng Lê Khoa
Email:

Facuty of Electronics & Telecommunications, HCMUS
1

2

Channel coding là gì?

Sơ ñồ khối DCS

Format

Source
encode

Channel
encode

Pulse
modulate

Bandpass
modulate

Digital demodulation

Format

Source
decode

Channel
decode

Detect

Demod.
Sample

3

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

Channel


Digital modulation

• 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).
• Ý tưởng mã hóa kênh là gởi một chuỗi bit có khả
năng sửa lỗi
• 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ó hai loại mã hóa kênh cơ bản là: Block codes và
Convolutional codes

4

Mã lập

Mã lập (Repetition Code)
Mã khối tuyến tính (Linear Block Code), e.g.
Hamming
Mã vòng (Cyclic Code), e.g. CRC
BCH và RS Code
Mã chập (Convolutional Code)

Recovered state

Truyền thống, giải mã Viterbi
Mã Turbo
Mã LDPC


Coded Modulation
TCM
BICM

5

6

1


3/22/2010

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

Mã khối tuyến tính (Linear block codes)
Chuỗi bit thông tin ñược chia thành từng khối k bit.
Mỗi khối ñược encode thành từng khối lớn hơn có
n bit.
Các bit ñược mã hóa và gửi trên kênh truyền.
Quá trình giải mã ñược thực hiện ở phía thu.
Channel
encoder

Data block

Codeword


k bits

n bits

n-k

Kiểm tra hàng và cột

Ứng dụng: ASCII, truyền dữ liệu qua cổng nối
tiếp

Redundant bits

k
Rc =
Code rate
n

7

8

Linear block codes – cont’d
Khoảng cách Hamming giữa hai vector U và V, là
số các phần tử khác nhau.
d (U, V ) = w(U ⊕ V )

Khoảng các tối thiểu của mã hóa khối là
d min = min d (U i , U j ) = min w(U i )

i≠ j

i

Ví dụ: Tính khoảng cách Hamming của C1: 101101
và C2 :001100
Giải: Vì 101101 ⊕ 001100 = 100001 =>d12=W(1000001)=2
=> Ta có thể giải mã ñể sửa sai bằng cách chọn
codewords có dmin

Linear block codes – cont’d
Khả năng phát hiện lỗi ñược cho bởi:
e = d min − 1

Khả năng sửa lỗi t của mã hóa ñược ñịnh
nghĩa là số lỗi tối ña có thể sửa ñược trên 1 từ
mã (codeword)
 d − 1
t =  min 
 2 

9

Linear block codes – cont’d
Encoding trong bộ mã hóa khối (n,k)

U = mG

 V1 
V 

(u1 , u2 ,… , u n ) = (m1 , m2 ,… , mk ) ⋅  2 
⋮ 
 
Vk 
(u1 , u2 ,… , u n ) = m1 ⋅ V1 + m2 ⋅ V2 + … + m2 ⋅ Vk

10

Linear block codes – cont’d
Example: Block code (6,3)
Message vector

 V1   1 1 0 1 0 0 
G =  V 2  =  0 1 1 0 1 0 
 V 3   1 0 1 0 0 1 

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

11

Codeword

000
100
01 0

000000
110100
011010


110
001

1 011 1 0
1 01 0 0 1

1 01
011
1 11

0 111 0 1
1 1 0 011
0 0 0 111

12

2


3/22/2010

Linear block codes – cont’d

Linear block codes – cont’d

Mã hóa khối (n,k)
k phần tử ñầu tiên (hoặc cuối cùng) trong từ mã là các
bit thông tin.

ðối với bất kỳ mã hóa khối tuyến tính, chúng

ta có một ma trận H ( n − k )× n . Các hàng của
ma trận này trực giao với ma trận G :

G = [P I k ]

GH T = 0

I k = k × k identity matrix
Pk = k × (n − k ) matrix
U = (u1 , u 2 ,..., u n ) = ( p1 , p2 ,..., pn − k , m1 , m2 ,..., mk )
parity bits

H ñược gọi là ma trận kiểm tra parity và các
hàng của chúng ñộc lập tuyến tính.
ðối với mã hóa khối truyến tính:

H = [I n − k

message bits

13

14

Linear block codes – cont’d

Data source

Format


m

Channel
encoding

U

Linear block codes – cont’d
Mảng tiêu chuẩn

Modulation
channel

Data sink

Format

ˆ
m

Channel
decoding

r

Demodulation
Detection

r = U+e


r = (r1 , r2 ,...., rn ) received codeword or vector

Hàng i = 2,3,...,2
với pattern e i

zero
codeword

e = (e1 , e2 ,...., en ) error pattern or vector

Kiểm tra ñặc trưng:
S là ñặc trưng của r, tưng ứng với error pattern e.
S = rHT = eHT

coset leaders

n−k

ñược tạo thành bằng cách cộng U

U1

U2

⋯

e2

e2 ⊕ U 2


⋯

e 2 ⊕ U 2k

⋮

⋯

⋱

⋮

e 2 n −k

Linear block codes – cont’d
Mảng tiêu chuẩn và ñặc trưng bảng giải mã
1. Tính S = rH T
2. Tìm coset chính eˆ = ei , tưng ứng với S .
ˆ = r + eˆ và tưng ứng với m
ˆ .
3. Tính U

ˆ = r + eˆ = (U + e) + eˆ = U + (e + eˆ )
U
•
•

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


U 2k

coset

e 2 n −k ⊕ U 2 ⋯ e 2 n −k ⊕ U 2 k

15

Chú ý:

PT ]

16

Linear block codes – cont’d
Ví dụ: Mảng chuẩn cho mã (6,3)
codewords

000000 110100 011010 101110 101001 011101 110011 000111
000001 110101 011011 101111 101000 011100 110010 000110
000010 110111 011000 101100 101011 011111 110001 000101
000100 110011 011100 101010 101101 011010 110111 000110
001000 111100
010000 100100
100000 010100

⋮

010001 100101


⋮

⋮
coset

⋮
⋯

⋯

010110

Coset leaders

17

18

3


3/22/2010

Linear block codes – cont’d

Hamming codes
Hamming codes

Error pattern Syndrome


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

000000

000

U = (101110) transmitted.

000001
000010
000100
001000
010000
100000

101
011
110
001
010
100

r = (001110) is received.
The syndrome of r is computed :

010001

111


n = 2m − 1

S = rH T = (001110) H T = (100)

Code length :

Error pattern corresponding to this syndrome is
eˆ = (100000)

Number of parity bits :

The corrected vector is estimated
ˆ = r + eˆ = (001110) + (100000) = (101110)
U

Number of information bits : k = 2 m − m − 1

19

20

Mã hóa Hamming

Hamming codes
Example: Systematic Hamming code (7,4)

1 0 0 0 1 1 1
H = 0 1 0 1 0 1 1 = [I 3×3
0 0 1 1 1 0 1
0 1 1 1 0 0 0 

1 0 1 0 1 0 0
 = [P
G=
1 1 0 0 0 1 0


1 1 1 0 0 0 1 

PT ]

I 4×4 ]

Message=[a b c d]
r= (a+b+d) mod 2
s= (a+b+c) mod 2
t= (b+c+d) mod 2

Message=[1 0 1 0]
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 ]

Tốc ñộ mã: 4/7
Càng nhỏ, nhiều redundance bit, ñược bảo vệ tốt hơn.
Khác biệt giữa phát hiện và sửa lỗi

22

Ví dụ mã hóa Hamming


Hamming codes
Example: Systematic Hamming code (7,4)

23

Mã hóa: H(7,4)
Nhiều phép kiểm tra tổng

Code=[r s a t b c d]

21

1 0 0 0 1 1 1
H = 0 1 0 1 0 1 1 = [I 3×3
0 0 1 1 1 0 1
0 1 1 1 0 0 0 
1 0 1 0 1 0 0
 = [P
G=
1 1 0 0 0 1 0


1 1 1 0 0 0 1 

n-k = m

Error correction capability : t = 1

PT ]


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

I 4×4 ]
Vector nhận r và vector lỗi e
24

4


3/22/2010

Sửa lỗi

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

Nếu không có lỗi, vector ñặc trưng (syndrome) z=zeros
Tốc ñộ mã R=k/n, k: số symbol dữ liệu, n tổng
symbol
SNR từ và SNR của bit
Nếu có 1 lỗi ở vị trí thứ 2
Vector ñặc trưng z là

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.

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

25

26

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

Example of the block codes

PB
8PSK

QPSK

Eb / N 0 [dB]
27

28

Cyclic code
Cyclic codes ñược quan tâm và quan trọng vì
Dựa trên cấu trúc ñại số và có thể ứng dụng rộng
rãi.
Dễ dàng thực hiện bằng thanh ghi dịch (shift register)
ðược ứng dụng rộng rãi trong thực nghiệm


Trong thực nghiệm, cyclic codes ñược sử dụng
ñể phát hiện lỗi (Cyclic redundancy check, CRC)
ðược sử dụng trong mạng chuyển mạch gói
Khi có 1 lỗi ñược phát hiện ở bộ nhận, chúng sẽ
ñược yêu cầu truyền lại.
ARQ (Automatic Repeat-reQuest)
29

Cyclic block codes
Một mã tuyến tính (n,k) ñược gọi là Cyclic
code nếu khi dịch vòng 1codeword thì ñó cũng
là codeword.

U = (u0 , u1 , u2 ,..., un −1 )

“i” cyclic shifts of U

U (i ) = (un −i , un −i +1 ,..., un −1 , u0 , u1 , u2 ,..., un −i −1 )
Ví dụ:
U = (1101)
U (1) = (1110) U ( 2) = (0111) U (3) = (1011) U ( 4) = (1101) = U

30

5


3/22/2010

Cyclic block codes


Cyclic block codes

Cấu trúc ñại số của Cyclic codes, suy ra
codewords ñược sinh ra từ
U ( X ) = u0 + u1 X + u2 X + ... + un −1 X
2

n −1

degree (n-1)

Mối quan hệ giữa codeword và thanh ghi
dịch: XU( X ) = u0 X + u1 X 2 + ..., un− 2 X n−1 + u n−1 X n

Thuật toán mã hóa Cyclic code (n,k):
n −k

1. Nhân thông tin với chuỗi m( X ) bằng X
2. Chia kết quả bước 1 với ña thức sinh g (X ) .
Lấy p( X ) là phần dư
n− k
3. Thêm p( X ) vào X m( X ) ñể tạo thành
codeword U ( X )

= un −1 + u0 X + u1 X 2 + ... + un − 2 X n −1 + un −1 X n + u n −1
u n −1 ( X n +1)

U (1 ) ( X )


= U (1) ( X ) + un −1 ( X n + 1)
U (1) ( X ) = XU( X ) modulo ( X n + 1)

Vậy:

By extension

U (i ) ( X ) = X i U ( X ) modulo ( X n + 1)
31

32

Cyclic block codes

Cyclic block codes

Example: For the systematic (7,4) Cyclic
code with generator polynomial g( X ) = 1 + X + X 3
1.

Find the codeword for the message

m = (1011)

n = 7, k = 4, n − k = 3
m = (1011) ⇒ m ( X ) = 1 + X 2 + X 3
X n− k m ( X ) = X 3m ( X ) = X 3 (1 + X 2 + X 3 ) = X 3 + X 5 + X 6
Divide X n− k m ( X ) by g ( X) :
X 3 + X 5 + X 6 = (1 + X + X 2 + X 3 )(1 + X + X 3 ) +
quotient q(X)


generator g(X)

1
remainder p ( X )

Form the codeword polynomial :
U ( X ) = p ( X ) + X 3m ( X ) = 1 + X 3 + X 5 + X 6
U = (1 0 0 1 0 1 1 )

Find the generator and parity check matrices, G and H,
respectively.
g ( X ) = 1 + 1 ⋅ X + 0 ⋅ X 2 + 1 ⋅ X 3 ⇒ ( g 0 , g1 , g 2 , g 3 ) = (1101)
1
0
G=
0

0

1 0 1 0 0 0
1 1 0 1 0 0
0 1 1 0 1 0

0 0 1 1 0 1

1
0
G=
1


1

1
1
1
0

P

parity bits message bits

33

0
1
1
1

1
0
0
0

0
1
0
0

0

0
1
0

Not in systematic form.
We do the following:
row(1) + row(3) → row(3)
row(1) + row(2) + row(4) → row(4)

0
0 
0

1

1 0 0 1 0 1 1
H = 0 1 0 1 1 1 0
0 0 1 0 1 1 1

I 3×3

I 4×4

PT

34

Ví dụ CRC

Cyclic block codes

Giải mã Cyclic code:
Từ mã ở bộ thu ñược cho bởi
Received
codewor
d

r ( X ) = U ( X ) + e( X )

Error
pattern

ðặc trưng ở phần dư có ñược bằng cách chia chuỗi nhận
cho ña thức sinh:

r( X ) = q( X )g( X ) + S( X )

Syndrome

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

35

36

6


3/22/2010


Checking for errors

Khả năng của CRC
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.
Có khả năng mạnh mẽ trong phát hiện lỗi

37

BCH Code

38

BCH Performance

Bose, Ray-Chaudhuri, Hocquenghem
Có khả năng sửa ñược nhiều lỗi
Dễ dàng thực hiện mã hóa và giải mã

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.
(40, 32) mã hóa BCH trong ATM (Asynchronous
Transfer Mode)

39

40


Reed-Solomon Codes
Một trường hợp riêng của non-binary BCH
ðược ứng dụng rộng rãi
Storage devices (tape, CD, DVD…)
Wireless or mobile communication
Satellite communication
Digital television/Digital Video Broadcast(DVB)
High-speed modems (ADSL, xDSL…)

41

7