Bài giảng Mã hóa và giải mã LDPC

Ả MÃ HÓA VÀ GI I MÃ LDPC

Ộ N I DUNG

Ế

1. KI N TRÚC MÃ LDPC

Ồ

2. Đ HÌNH TANNER

3. MÃ HÓA

ử ụ

ậ

3.1 Mã hóa s d ng ma tr n sinh G

ử ụ

ậ

ẵ ẻ

3.2 Mã hóa s d ng ma tr n ch n l H

Ả

4. GI

I MÃ

Ế 1. KI N TRÚC MÃ LDPC

ọ

ể • Mã LDPC (LowDensity ParityCheck code – Mã ki m tra ượ ề c đ m t đ th p), hay còn g i là mã Gallager, đ

ẵ ẻ ậ ộ ấ ấ ở

ch n l xu t b i Gallager vào năm 1962

ộ

ạ

ề ơ ả

ế

ể

ặ

ố

ậ

• V c b n đây là m t lo i mã kh i tuy n tính có đ c đi m ẵ ẻ (H) là các ma tr n th a ầ ử ế ầ

ể ứ

ư ỉ ộ là 0, ch m t

là các ma tr n ki m tra ch n l (sparse matrix), t c là có h u h t các ph n t ố s ít là 1.

Ế 1. KI N TRÚC MÃ LDPC

Ồ 2. Đ HÌNH TANNER

ượ

• Đ hình Tanner chính là m t trong nh ng cách đ

c coi là

ấ ể ể

ộ ễ

ồ ệ

ả

ữ hi u qu nh t đ bi u di n mã LDPC.

ộ ồ ị ể

ọ ố

ế

ồ

ấ

ỏ

ả • Đây là m t đ th 2 phía , bên trái g i là nút bit còn bên ph i ọ g i là nút ki m tra. Đ i v i mã kh i tuy n tính thì đ hình Tanner t

ố ớ ả ệ ra r t hi u qu .

Ồ 2. Đ HÌNH TANNER

ế ừ ộ

m t nút

ộ ườ • Chu kì Tanner là m t đ ồ

ạ

ộ

ấ ỳ b t k đi m t vòng r i quay l

ng khép kín liên k t t i chính nó.

•

Ở ụ ừ ồ

ví d v a r i ta có chu kì Tanner là

3. MÃ HÓA

ử ụ ậ 3.1 Mã hóa s d ng ma tr n sinh G

́

ế

ự

• N u sau khi th c hiên ca c b

̣ ̉

ử ̀

̀

́

̣ ̣ ̣ ̣

c

̀

́

̀ ́ ươ c cua phe p th GaussJordan ma ̀ ượ cho ta môt ma trân bâc thang ha ng co môt ha ng toa n 0 thi ta đ ́ phe p bo ha ng đo .

́

̀

• Khó khăn

̣ ̉ ̉

́

ng pha p na y la ma trân G không bao đam đ ượ

́

̀

́

̣ ở

̣ ̣

̀ ươ ́ ̣ ư ́

̀

̃

́

̀

̃ ng tri nh ma ho a c = uG đ ́ ́ ơ

̣ ̣

ượ c ̀ ự ư c th c ̀ ́ bô ma ho a co đô ph c tap gâ n chi nh xa c bă ng n2 phe p ̃ ̀ ư ma l n thi bô ma ho a se

́

́ ự

ở ươ ph ́ ư ti nh th a nh ma trân H. Ph ̃ ́ hiên ̃ ́ ́ ́ ơ ti nh. Đô i v i ca c ma co đô da i t ̀ ư ở tr nên c c ki ph c tap

•

ử ụ ẵ ẻ ậ 3.2 Mã hóa s d ng ma tr n ch n l H

ử ụ

ưở

ườ

ậ

ng pháp này ng

ộ

ị

ng ự ế ng pháp này là s d ng tr c ti p hoán v hàng c t sao cho

ể

ậ

Ở ươ ph ươ ủ c a ph ẫ ữ ượ ặ v n d đ

ự ế i ta s d ng tr c ti p ma tr n H. Ý t ử ụ ủ c đ c đi m c a ma tr n H

ớ

ộ

ể

ố

• V i k là kích th

ố c b n tin, n là đ dài kh i mã, m là s bít ki m tra

ộ ứ ạ

ọ

ướ ả m=nk, g g i là đ ph c t p mã hóa.

ậ ử ụ 3.2 Mã hóa s d ng ma tr n H

Ả 4. GI I MÃ

ồ ị

ể

ế

ặ

ng pháp l p đ tính toán các bi n trên đ th và có

ươ • S d ng ph ọ

ử ụ ề

ư nhi u tên g i nh :

ậ

ổ

§ Thu t toán t ng tích – SPA (Sum Product Algorithm).

ề

ậ

§ Thu t toán lan truy n ni m tin – BPA (Bilief Propagation Algorithm)

ề

ậ

ả

§ Thu t toán chuy n b n tin MPA (Massage Passing Algorithm).

Ả 4. GI I MÃ

ộ ố

ệ

ọ

ả

ậ i thu t gi

• M t s kí hi u tr ng gi ứ ệ

i mã: ể

ủ ồ

ứ

• cn là ký hi u nút bit th n và zm là nút ki m tra th m c a đ hình

tanner.

ậ

ỉ ố ủ

ố ớ

ể

• Mn là t p các ch s c a các nút ki m tra n i t

i nút bit

ỉ ố

ậ

ớ

cn trên đ ồ hình Tanner hay là các t p ch s m v i H(m, n) = 1 trong ma tr n H.

ậ

ỉ ố ủ • Nm là t p các ch s c a các nút bit n i t

ỉ ố

ậ

ể ố ớ i các nút ki m tra zm ớ

ậ

ồ trên đ hình Tanner hay t p các ch s n v i H(m,n) = 1 trong ma tr n H.

ị ằ

ừ

ậ

ợ

• Mn/m là t p h p Mn tr đi các giá tr b ng m.

ị ằ

ừ

ậ

ợ

• Nm/n là t p h p Nm tr đi các gía tr b ng n.

Ả 4. GI I MÃ

ượ

ấ

• Đ u tiên thì xác su t qmn đ ấ

ệ

ươ

ở ạ c kh i t o ng

ầ ằ b ng xác su t tiên nghi m APP t ng.ứ