Trang chủ » Kỹ Thuật - Công Nghệ » Điện - Điện tử - Viễn thông

14 trang

127 lượt xem

Bài i giảng Thông tin số-Chương 2 - Channel coding

Channel codings nhằm tăng khả năng chống các tác nhân nhiễu trên đường truyền Phân làm 2 loại: Waveform codings: mã hoá dạng tín hiệu để giảm BER khi tách sóng: đối xứng (antipodal), trực giao (orthogonal), và song trực giao (biorthogonal). Structured sequences: thêm vào một số bít để tăng khả năng phát hiệu lỗi và sửa lỗi.

kakahungkakahung

Friday, March 06, 2009

TrTrầần Nhn Nhựựt Kht Khảải Ho

i Hoàànn

BBàài gi

ng Thông tin sốố i giảảng Thông tin s

Chương 2 - Channel coding

Slide 1

ĐH Cần Thơ

i dung NNộội dung

(cid:132) Giới thiệu (cid:132) Các phương pháp điều khiển lỗi (cid:132) Mã khối tuyến tính – Linear block codes (cid:132) Mã Hamming – Hamming codes (cid:132) Mã vòng – cyclic codes

Slide 2

ĐH Cần Thơ

GiGiớới thi

i thiệệuu

(cid:132) Channel codings nhằm tăng khả năng chống các tác nhân nhiễu

trên đường truyền

(cid:132) Phân làm 2 loại:

(cid:41) Waveform codings: mã hoá dạng tín hiệu để giảm BER khi tách sóng:

đối xứng (antipodal), trực giao (orthogonal), và song trực giao (biorthogonal)

(cid:41) Structured sequences: thêm vào một số bít để tăng khả năng phát hiệu

lỗi và sửa lỗi

Slide 3

ĐH Cần Thơ

antipodal Mã đMã đốối xi xứứng ng -- antipodal

(cid:132) Hai thành phần ngược pha nhau

Slide 4

ĐH Cần Thơ

Mã trMã trựực giao

Orthogonal c giao –– Orthogonal

(cid:132) Định nghĩa:

Slide 5

ĐH Cần Thơ

Mã trMã trựực giao

c giao –– Orthogonal

Orthogonal –– tttt

số bits giống nhau

số bits khác nhau

Ví dụ: tập mã trực giao – Ma trận Hadamard

Slide 6

ĐH Cần Thơ

Song trựực giao Song tr

biorthogonal c giao –– biorthogonal

(cid:132) Tập mã song trực giao M từ mã (code word) được tạo ra bằng cách ghép 1 bộ mã trực giao M/2 từ mã và đảo của bộ mã đó.

(cid:132) Ví dụ:

Slide 7

ĐH Cần Thơ

Song trựực giao Song tr

c giao –– biorthogonal

biorthogonal –– tttt

(cid:132) Tổng quát: tập song trực giao có hệ số tương quan chéo được định

nghĩa:

(cid:132) Ưu điểm: số bits mã hoá giảm ½ so với orthogonal

Slide 8

ĐH Cần Thơ

CCáác phương ph

c phương phááp đip điềều khi

u khiểển ln lỗỗii

(cid:132) Phát hiện lỗi và truyền lại (error detection & retransmission)

(cid:132) Phát hiện lỗi và sửa lỗi FEC (Forward Error correction)

Slide 9

ĐH Cần Thơ

MMộột st sốố PP ph

PP pháát hi

t hiệện ln lỗỗi vi vàà truytruyềền ln lạạii

Slide 10

ĐH Cần Thơ

Mã khMã khốối tuy

Linear block codes i tuyếến tn tíính nh –– Linear block codes

(cid:132) Ký hiệu (n,k) là tập mã khối tt gồm k bits thông tin và từ mã có

chiều dài n bits

(cid:132) Ví dụ mã khối tt (6,3)

(cid:41)Chứa 1 từ mã có tất cả bít là 0s (cid:41)Tổng của 2 từ mã bất kỳ là một từ mã khác trong tập (Closure

property)

Slide 11

ĐH Cần Thơ

Mã khMã khốối tuy

Linear block codes i tuyếến tn tíính nh –– Linear block codes

(cid:132) Ký hiệu (n,k) là tập mã khối tt gồm k bits thông tin và từ mã có

chiều dài n bits

(cid:132) Gọi:

(cid:41) U là từ mã truyền (code word) (cid:41)m = m1,m2,...,mk là k bits thông tin (cid:41)G là ma trận sinh, Vi là các vectơ độc lập tuyến tính (tổng của

2 từa mã bất kỳ không tạo ra từ mã trong tập

(cid:132) Ta có U = m.G, đây là công thức tìm U từ m khi biết G

Slide 12

ĐH Cần Thơ

Mã khMã khốối tuy

Linear block codes i tuyếến tn tíính nh –– Linear block codes

(cid:132) Thường tìm Gkxn ở dạng ma trận chính tắc, khi đó u = m.G là mã

khối tuyến tính

Slide 13

ĐH Cần Thơ

Mã khMã khốối tuy

Linear block codes i tuyếến tn tíính nh –– Linear block codes

(cid:132) Thường cho G ở dạng không chính tắc, phải chuyển về dạng

chính tắc

(cid:132) Ví dụ ở slide 11, rút ra được Gkxn:

(cid:132) Suy ra Gkxn dạng chính tắc, và tìm các codeword U = m.G:

Slide 14

ĐH Cần Thơ

Mã khMã khốối tuy

n ktra H i tuyếến tn tíính nh –– Ma trMa trậận ktra H

(cid:132) Định nghĩa mà trận kiểm tra Hn-kxn dùng để giải mã khối:

(cid:132) Do các dòng G và H là trực giao, ta có 2 phương trình sau,

phương trình này cũng có thể vận dụng để tìm U:

Slide 15

ĐH Cần Thơ

GiGiảải mã kh

i mã khốối tuy

i tuyếến tn tíínhnh

(cid:132) Gọi r (r1, r2,...rn) là từ mã nhận, e (e1,e2,...en) là vecto sai, ta có:

(cid:132) Để xác định vị trí sai, tính Syndrome:

(cid:132) S trùng với cột nào của ma trận H thì vị trí đó bị sai

Slide 16

ĐH Cần Thơ

nh Syndrome S CCáách xch xáác đc địịnh Syndrome S

Slide 17

ĐH Cần Thơ

Sơ đSơ đồồ ssửửa la lỗỗii

Slide 18

ĐH Cần Thơ

KhoKhoảảng cng cáách Hamming

năng dò sai ch Hamming -- khkhảả năng dò sai

(cid:132) Khoảng cách Hamming: số bits khác nhau giữa 2 từ mã

(cid:132) Khả năng dò sai, sửa sai:

(cid:132) Trong đó, dmin là khoảng cách ngắn nhất giữa 2 từ mã

Slide 19

ĐH Cần Thơ

mã (n,k) ThiThiếết kt kếế mã (n,k)

(cid:132) Chọn số bits thông tin k (cid:132) Khả năng dò sai và sửa sai của mã (cid:132) Khoảng cách ngắn nhất giữa 2 từ mã trong tập tính theo công thức

Plotkin (Plotkin bound)

(cid:132) ⇒ chiều dài mã n (cid:132) Chọn tập mã, với các bits thông tin đặc theo thứ tự bên phải (cid:132) Nguyên tắc: tập mã phải chứa từ mã 0s và thoả closure property (cid:132) Suy ra mâ trận G và HT

Slide 20

ĐH Cần Thơ

: Mã (8,2) VVíí ddụụ: Mã (8,2)

(cid:132) Số lượng từ mã là 2k = 4 (cid:132) Phải chứa từ mã 0s (cid:132) Thoả tính chất closure: Tổng 2 từ mã bất từ là 1 từ mã trong tập (cid:132) Mỗi từ mã dài 8 bits (cid:132) Sửa được 2 lỗi: dmin = 5 ⇒ Trọng số (weight of codeword) của

mỗi từ mã ≤ 5

(cid:132) Giả thuyết mã có tính hệ thống, các bits thông tin được bố trí bên

phải từ mã

Slide 21

ĐH Cần Thơ

VVíí ddụụ: Mã (8,2)

: Mã (8,2) –– tttt

(cid:132) Suy ra ma trận Gk x n và H n-k x n

(cid:132) Tính S = e.HT = r.HT

Slide 22

ĐH Cần Thơ

Mã Hamming Mã Hamming

(cid:132) là một dạng mã khối (cid:132) Với mọi m ≥ 3, tồn tại mã Hamming với thông số sau:

(cid:41) Chiều dài từ mã: n = 2m – 1 (cid:41) Chiều dài phần tin: k = 2m – m – 1. (cid:41) Chiều dài phần kiểm tra: m = n –k (cid:41) Khả năng sửa sai: t = 1 (dmin =3)

(cid:132) MT kiểm tra H có dạng: H = [Im.Q]; với Q là ma trận 2m–m–1 cột, mỗi cột là vector m chiều có trọng số là 2 hoặc lớn hơn

(cid:132) Ví dụ: với m = 3:

Slide 23

ĐH Cần Thơ

Mã Hamming –– tttt Mã Hamming

(cid:132) Thực tế: Để tạo và giải mã đơn giản, các bits kiểm tra được đặc

xen kẻ các bits thông tin (khác mã khối). Ví dụ: với m = 3, có ma trận H như sau:

(cid:132) Các bits kiểm tra x, y, z, ...được đặt ở vị trí 2i, với i = 0, 1, 2, ...

Codeword: U = (x, y, u0, z, u1, u2, u3, ...)

(cid:132) Để tạo mã, giải phương trình U.HT = 0 (cid:132) Để giải mã, tính syndrome S1xn = r.HT; với r là từ mã thu, r = e + U với e là vectơ sai. S giống cột nào của H là bit tương ứng sai

Slide 24

ĐH Cần Thơ