Chapter 5 Low Density Parity Check Codes
(Mã hóa ki m tra ch n l m t đ th p)ể ẵ ẻ ậ ộ ấ
Mã hóa ki m tra ch n l m t đ th p (LDPC), đ xu t c a Gallager trongể ẵ ẻ ậ ộ ấ ề ấ ủ 1962
[19],và sau đó đc phát hi n b i MacKay [18] và Neal xu t hi n nh là m t l p h c ượ ệ ở ấ ệ ư ộ ớ ọ
c aủ mã có th mang l i hi u su t r t t t trên kênh nhi u tr ng Gaussian (AWGN).Mãể ạ ệ ấ ấ ố ễ ắ
hóa LDPC có th đt đc gi i h n ch tiêu l i g n Shannon v i gi i mã th c t ph cể ạ ượ ớ ạ ỉ ỗ ầ ớ ả ự ế ứ
t p trên m t kênh AWGN, mã turbo t t h n v i cùng m t kích th c kh i và t l mã.ạ ộ ố ơ ớ ộ ướ ố ỷ ệ
5.1 Gi i thi uớ ệ
Mã hóa LDPC là nh ng ví d đc bi t c a mã kh i tuy n tính.ữ ụ ặ ệ ủ ố ế C u trúc c a m t mã kh i ấ ủ ộ ố
tuy n tính đc mô t b i ma tr n G ho c ma tr n ki m tra ch n l H. Kh năng s a l i kí t ế ượ ả ở ậ ặ ậ ể ẵ ẻ ả ử ỗ ự
trong m t t mã đc xác đnh b i kho ng cách t i thi u dộ ừ ượ ị ở ả ố ể min. Dmin đc đnh nghĩa là kh i ượ ị ố
l ng ít nh t c a các hàng trong ma tr n G ho c nó có th đc đnh nghĩa là s l ng ít nh t các ượ ấ ủ ậ ặ ể ượ ị ố ượ ấ
c t trong H có t ng t i 0.ộ ổ ớ T mã c a m t mã ki m tra ch n l đc hình thành b ng cách k t h p ừ ủ ộ ể ẵ ẻ ượ ằ ế ợ
m t kh i các ch s thông tin nh phân v i m t kh i các ch s ki m tra.ộ ố ữ ố ị ớ ộ ố ữ ố ể Nh ngữ ch s ki m tra ữ ố ể
này đc bi u di n d i d ng ma tr n đc g i là ma tr n ki m tra ch n l . ượ ể ễ ướ ạ ậ ượ ọ ậ ể ẵ ẻ
Ma tr n này đi di n cho m t t p h p các ph ng trình tuy n tính đng nh t, và thi t l p ậ ạ ệ ộ ậ ợ ươ ế ồ ấ ế ậ
các t mã là b các gi i pháp c a các ph ng trìnhừ ộ ả ủ ươ
Trong ma tr n này b n ch s đu tiên là ch s thông tin và ba ch s cu i cùng là ch s ki m ậ ố ữ ố ầ ữ ố ữ ố ố ữ ố ể
tra. Ph ng trình ki m tra ch n l cho ma tr n này có th đc đa ra nh :ươ ể ẵ ẻ ậ ể ượ ư ư
x5= X1 © x2 © x3 (5.1)
x6= X1 © x2 © x4 (5.2)
x7= X1 © x3 © x4 (5.3)
Nh ng ma tr n ki m tra ch n l không ph i là r t đn gi n đ gi i mã khi ữ ậ ể ẵ ẻ ả ấ ơ ả ể ả
thông tin bên trong là l n, do đó m t k thu t mã hóa khác đc đa ra b i Gallager ớ ộ ỹ ậ ượ ư ở
đc bi t đn nh là mã hóa LDPC.ượ ế ế ư Mã hóa LDPC là mã xác đnh b i m t ma tr n i.e, ị ở ộ ậ
nó ch a ch y u là 0’s và ch có m tứ ủ ế ỉ ộ s nh c a 1’s.ố ỏ ủ Mã hóa LDPC có th đc chia ể ượ
thành hai lo iạ
• Mã hóa LDPC có quy t c: S l ng c a 1 m i hàng và c t là h ng s .ắ ố ượ ủ ỗ ộ ằ ố
• Mã háo LDPC b t quy t c: S l ng c a 1 m i hàng và c t ấ ắ ố ượ ủ ỗ ộ không c đnh.ố ị Nh ng ữ
mã b t quy t c cho hi u su t t t h n so v i Mã có quy t c. Gi s ki m tra tính ch n ấ ắ ệ ấ ố ơ ớ ắ ả ử ể ẵ
l m t đ th p ma tr n H có N c t và M hàng. T l mã đc cho b i R= 1-(M / N), ẻ ậ ộ ấ ậ ộ ỷ ệ ượ ở
đ th hai phía t ng ng bao g m N bit node, các node ki m tra M và m t s l ng ồ ị ươ ứ ồ ể ộ ố ượ
nh t đnh c a các c nh.ấ ị ủ ạ M i bit node, đc g i là "left node", đi di n cho m t bit c aỗ ượ ọ ạ ệ ộ ủ
t mã.ừ M i nút ki m tra, đc g i là m t "right node" đi di n choỗ ể ượ ọ ộ ạ ệ ki m tra ch n l ể ẵ ẻ
c a mã.ủ M t c nh t n t i gi a m t bit node và m t node ki m tra khi và ch khi có ộ ạ ồ ạ ữ ộ ộ ể ỉ
m t 1 trong m c t ng ng trong ma tr n ki m tra ch n l . Mã hóa LDPC có quy t c ộ ụ ươ ứ ậ ể ẵ ẻ ắ
là nh ng ma tr n mà t t c các node cùng lo i có cùng m t m c đ, n u m c đ ữ ậ ấ ả ạ ộ ứ ộ ế ứ ộ
c aủ m t node là s c nh cho m t node lân c n.ộ ố ạ ộ ậ Mã A(n, j, k) m t đ th p là m t mã ậ ộ ấ ộ
c a chi u dài kh i n v i s j c a 1’s trong m i c t c a ma tr n và s k c a 1’s trong ủ ề ố ớ ố ủ ỗ ộ ủ ậ ố ủ
m i hang c a ma tr n. Ma tr n ki m tra ch n l c a mã hóa LDPC có quy t c (3, 4) ỗ ủ ậ ậ ể ẵ ẻ ủ ắ
đc hi n th d i đây. Hình 5,1 cho th y đ th hai phía liên quan c a nó.ượ ể ị ướ ấ ồ ị ủ
Hình 5.1 đ th đi di n c a m t mà LDPC có quy t c (3,6) chi u dài 12.ồ ị ạ ệ ủ ộ ắ ề Các left
node đi di n cho các variable node trong khi các right node đi di n cho ki m ạ ệ ạ ệ ể
tra các nút. [20]
Các ph ng trình đi di n b i nh ng ma tr n luôn luôn có th đc gi i quy t ươ ạ ệ ở ữ ậ ể ượ ả ế
đ cung c p cho các s ki m tra là t ng h p rõ ràng c a các s thông tin. Phân tích ể ấ ố ể ổ ợ ủ ố
m t mã m t đ th p ộ ậ ộ ấ chi u dài kh i l n là r t khó khăn vì s l ng bao la c a ề ố ớ ấ ố ượ ủ
codewords tham gia. Nó là đn gi n đ phân tích m t qu n th toàn b t mã nh v y ơ ả ể ộ ầ ể ộ ừ ư ậ
b i vì s li u th ng kê c a m t qu n th cho phép m t m c trung bình trên s l ng ở ố ệ ố ủ ộ ầ ể ộ ứ ố ượ
mà không ph i là d x lý trong mã riêng bi t.T các hành vi qu n th ta có th l p ả ễ ử ệ ừ ầ ể ể ậ
báo cáo th ng kê v các thu c tính c aố ề ộ ủ mã riêng bi t.ệ Cho phân tích m t ma tr n này ộ ậ
đc chia thành submatrices j, m i submatric có ch a duy nh t 1 trong m i c t.ượ ỗ ứ ấ ỗ ộ
5.2 Mã LDPC trong MIMO
Trong các h th ng MIMO, chuy n ti p mã hóa s a l i là đi u c n thi t ệ ố ể ế ử ỗ ề ầ ế
cho k t n i ch t l ng cao.ế ố ấ ượ Các thu t toán VBLAST đc s d ng trong h th ng ậ ượ ử ụ ệ ố
MIMO cho phép x lý tuy n tính thông tin. Các v n đ g p ph i v i m t l p thu t ử ế ấ ề ặ ả ớ ộ ớ ậ
toán là s hi n di n c a l i truy n và l p đc phát hi n đu tiên, mà th ng có ự ệ ệ ủ ỗ ề ớ ượ ệ ầ ườ
singnal-to-noise ratio (SNR) do m t tín hi u đi n nulling tuy n tính,ấ ệ ệ ế có nhi u kh năngề ả
đc gi i mã không chính xác.ượ ả T i u hóa sóng vô tuy n là m t ố ư ế ộ gi i pháp đc th o ả ượ ả
lu n trong ậch ngươ tr cướ . Đ nâng cao h n n a đ tin c y c a liên k tể ơ ữ ộ ậ ủ ế và ch ng ố
l iỗ liên ký t là v n đ Forward th c hi n đc ch ng trình s a l i LDPC.ự ấ ề ự ệ ượ ươ ử ỗ Các th ủ
t c mã hóaụ c b n d li u truy n v i m t s bit b o v giúp nh n bi t xem có l i ơ ả ữ ệ ề ớ ộ ố ả ệ ậ ế ỗ
x y ra trong quá trình truy n.ả ề Mã hóa LDPC là r t hi u qu (đi v i mã hóa và gi i mãấ ệ ả ố ớ ả
ph c t p) .ứ ạ S d ng mã hóa LDPC giúp th c hi n t t ti m năng c a h th ng MIMO ử ụ ự ệ ố ề ủ ệ ố
m t cách hi u qu . ộ ệ ả
5. 3 mã hóa
Mã LDPC là mã tuy n tính.ế Do đó,nó có th đc th hi n nh không gian c a m tể ượ ể ệ ư ủ ộ
ma tr nậ ch n l ki m traẵ ẻ ể , ví d , là m t t mã khi và ch khiụ ộ ừ ỉ
H xT= 0T (5.4)
S a đi "m t đ th p" áp d ng cho ma tr n nên đn gi n.ử ổ ậ ộ ấ ụ ậ ơ ả Ví d ,n u có kích th cụ ế ướ
[(n / 2) x n], trong đó n là ch n, sau đó nó có th đc yêu c u cho H có 3 c t và 6 ẵ ể ượ ầ ộ
hàng. Chúng ta tham kh o các mã liên k t nh là m tả ế ư ộ mã LDPC có quy t c.ắ S đn ự ơ
gi n c a H cho phép hi u qu (t i u) gi i mã, trong khi tính ng u nhiênvđm b o ả ủ ệ ả ố ư ả ẫ ả ả
(theo nghĩa xác su t) m t mã t t .[20]ấ ộ ố
Hình 5.2 (a) M t ma tr n ki m tra-ch n l t ng đng trong hình tam ộ ậ ể ẵ ẻ ươ ươ
giác th p h n.ấ ơ (b)ma tr n ki m tra ch n l tính g n đúng hình tam giác ậ ể ắ ẻ ầ
th p h nấ ơ
5.3.1 Mã hóa hi u qu d a trên kho ng tam giác th p h nệ ả ự ả ấ ơ
Hi u qu c a các b mã hóa phát sinh t các ma tr n ki m tra ch n l Hệ ả ủ ộ ừ ậ ể ẵ ẻ và
thu t toán có th đc áp d ng cho b t k (đn gi n)H. Các hàng c a H là đc l p ậ ể ượ ụ ấ ỳ ơ ả ủ ộ ậ
tuy n tính.ế Chúng ta xem xét m t ma tr n ki m tra ch n l H m x n trên môt lĩnh v c ộ ậ ể ẵ ẻ ự
Galva F (GF (2)). Mã liên quan bao g m các thi t l p c a n-tuplesồ ế ậ ủ x h nơ F như
H xT= 0T (4.5)
Đi v i các mã đ đt đc công su t kênh, và có th i gian x lý tuy n tính ố ớ ể ạ ượ ấ ờ ử ế
chúng ta đa ra ma tr n ki m tra ch n l đc đa ra trong hình tam giác th p h n ư ậ ể ẵ ẻ ượ ư ấ ơ
b ng cách s d ng thu t toán Greedy.Đi u này có th đc th c hi n đn gi n v i ằ ử ụ ậ ề ể ượ ự ệ ơ ả ớ
hoán v hàng và c t.ị ộ Chúng ta s d ng thu t toán Greedy A ,đa ma tr n b t đu m t ử ụ ậ ư ậ ắ ầ ộ
hình tam giác th p h n.ấ ơ
Hình 4.3 S đ Đi di n c a thu t toán Greedyơ ồ ạ ệ ủ ậ
C t lõi c a thu t toán là ố ủ ậ b c đng chéo m r ng. ướ ườ ở ộ Thu t toán Greedy A b t đu v i ậ ắ ầ ớ
ma tr n (1-r)ậl x l; A nh hìnhư 4.4 (a). Trong b c kh i t o, d ki n ph n nh (1 – ướ ở ạ ự ế ầ ỏ α)
c a t t c các c t đc phân lo i nh đc bi t đn và ph n còn l i đc phân lo i ủ ấ ả ộ ượ ạ ư ượ ế ế ầ ạ ượ ạ
là xóa. L n đu tiên các thu t toán ầ ầ ậ th c hi n m t b c này (1 – ự ệ ộ ướ α )l c t đc bi t ộ ượ ế
đn đc s p x p l i đ hình thành các c t đuế ượ ắ ế ạ ể ộ ầ c a ma tr n A hi n th nh trong ủ ậ ể ị ư
hình 4.4 (b). Gi s r ng các ma tr n còn l i có hàng b c m t, c t k t n i v i các ả ử ằ ậ ạ ậ ộ ộ ế ố ớ
hàng b ng-m t đc xác đnh trong b c th hai.ằ ộ ượ ị ướ ứ Hãy đ các c t này là cể ộ 1..... ck và cho
r1 .... rk có b c m t hàng nh v y mà cậ ộ ư ậ i đc k t n i v i rượ ế ố ớ i. Trong l n th hai áp d ngầ ứ ụ
b c m t các c t m i này đc bi t đn và hàng liên quan c a nó đc s p x p d c ướ ộ ộ ớ ượ ế ế ủ ượ ắ ế ọ
theo m t đng chéo nh trong Hìnhộ ườ ư 4.4 (c). H n n a, trong m i l n l p b sung này ơ ữ ỗ ầ ặ ổ
đng chéo đc m r ng h n n a.ườ ượ ở ộ ơ ữ N u th t c này không ch d ng l i tr c sau đó ế ủ ụ ỉ ừ ạ ướ
các đng chéo k t qu đã d ki n chi u dài ườ ế ả ự ế ề αl và, do đó, kho ng cách hàng đã d ả ự
ki n có kích c (1-r-ế ỡ α)l và kho ng cách c t kích th c (1 -ả ộ ướ α)l nh th hi n trong ư ể ệ
hình. 4.4 (d)
Hình 5.4. (A) cho ma tr n A. (b) Sau khi ng d ng đu tiên c a b c m t, (1 -ậ ứ ụ ầ ủ ướ ộ α)l
c t đc bi t đnđc s p x p l i đ t o thành đu tiên (1 -ộ ượ ế ế ượ ắ ế ạ ể ạ ầ α)l c t c a ma ộ ủ
tr n A. (c) Sau khi ng d ng th hai c aậ ứ ụ ứ ủ b c m t, k m i đc bi t đn c t và ướ ộ ớ ượ ế ế ộ
các hàng liên quan c a h đc s p x p l i đ t o thành m t đng ủ ọ ượ ắ ế ạ ể ạ ộ ườ
chéo c aủ chi u dài k.ề (D) N u th t c khôngch m d t s m sau đó đng chéo ế ủ ụ ấ ứ ớ ườ
đc m r ng đ cóchi u dài ượ ở ộ ể ề αl và, do đó, kho ng cách hàng làả b ng ằ
(1-r -α)l và kho ng cách c t b ng (1 -ả ộ ằ α)l. [20]