Nghiên cứu kỹ thuật giải mã mềm với thuật toán BPA-EH cải tiến cho mã LDPC

ma trận kiểm tra tương đương nhằm khắc phục vấn đề vịng kín ngắn trong mã LDPC. Phương pháp này khơng những cho phép giảm đáng kể thời gian giải mã so với thuật tốn BPA-EH (Belief Propagation Algorithm based on Equivalent Parity Check Matrix H), mà cịn mang lại độ lợi mã hĩa cao hơn so với phương pháp giải mã BPA truyền thống khoảng 0,75 dB trên kênh Gauss và 1,2 dB trên kênh pha-đinh. Từ khĩa— Mã LDPC, ma trận kiểm tra tương đương, giải mã BPA, kênh Gauss, kênh pha-đinh. I. GIỚI THIỆU Mã kiểm tra chẵn lẻ mật độ thấp (LDPC-Low Density Parity Check) được biết đến cùng với các thuật tốn giải mã: BPA, SPA, MPA...[2]. Các thuật tốn này cho chất lượng giải mã khá tốt, tuy nhiên trong các hệ thống thơng tin hiện đại việc tiết kiệm cơng suất phát mà vẫn đảm bảo được chất lượng thơng tin của hệ thống là vấn đề thực sự cĩ ý nghĩa. Vì thế, đã cĩ rất nhiều cơng trình nghiên cứu nhằm cải thiện hiệu quả giải mã cho mã LDPC, trong đĩ cải tiến nâng cao chất lượng giải mã vẫn là nội dung đang tiếp tục được nghiên cứu. Với tính chất của một mã khối tuyến tính, cơ chế phát hiện và sửa sai của mã LDPC dựa vào đa thức kiểm tra H . Mặt khác, với đặc điểm riêng của mình, mã LDPC lại cho phép áp dụng kỹ thuật giải mã lặp. Từ hai yếu tố trên đây gợi cho ta hướng nghiên cứu sử dụng kỹ thuật giải mã mềm cho mã LDPC. II. CÁC THUẬT TỐN GIẢI Mà BPA, BPA-EH VÀ Ý TƯỞNG NGHIÊN CỨU A. Thuật tốn giải mã BPA Xét mã LDPC ( , )n k với tỷ lệ mã R = k/n (m = n -k là số lượng các bit kiểm tra). Các bit tin 1 2 , ,... k u u u=u được mã hĩa thành từ mã 1 2 , ,... n y y y=y sau đĩ được điều chế và truyền trên kênh. ðầu vào bộ giải mã BPA là tỷ lệ ước lượng theo hàm log (Log Likelihood Ratio – LLR) [2,3]: ˆPr( 0 | ) ˆ( ) log ˆPr( 1 | ) i i i y r L y y r = = = (1) Ở đây r là tập các symbol nhận từ kênh và xác suất điều kiện ˆPr( 0 | ) i y r= . Thuật tốn BPA [2,3] là thuật tốn giải mã lặp cĩ hai cơng đoạn chính: 1. Cập nhật bản tin cho tất cả các nút kiểm tra và gửi bản tin ( ) ji r b từ nút kiểm tra tới các nút bít nối với nĩ. 2. Cập nhật bản tin cho tất cả các nút bít và gửi bản tin ( ) ji q b từ các nút bit tới các nút kiểm tra nối với nĩ. ðầu ra của bộ giải mã là giá trị LLR của các bít mã được sử dụng để quyết định thành từ mã thăm dị 1 2 ˆ ˆ ˆ ˆ, ,..., n y y y=y . Khi hội chứng s thỏa mãn điều kiện: ˆ [0, 0,..., 0]T =s = y.H (2) Thì dừng lặp đưa ra từ mã hợp lệ yˆ . Nếu điều kiện (2) khơng thỏa mãn thì quá trình được thực hiện lại cho đến khi đạt số lần lặp cực đại axm γ và đưa ra từ mã. B. Thuật tốn giải mã BPA-EH Như ta đã biết thuật tốn BPA-EH là thuật tốn sử dụng các ma trận kiểm tra tương đương [1]. Từ lý thuyết của mã tuyến tính, ta thấy một từ mã dùng đúng y bao giờ cũng phải thỏa mãn điều kiện (2). ðây là một hệ phương trình tuyến tính nên việc thay thế một hàng bằng việc cộng các hàng bất kỳ với nhau để được ma trận kiểm tra tương đương e H thì ma trận này vẫn thỏa mãn (2). Ở đây mới chỉ chỉ xét trường hợp thành lập e H Hội thảo quốc gia 2014 về Điện tử, Truyền thơng và Cơng nghệ thơng tin (ECIT2014) ISBN: 978-604-67-0349-5 422 bằng việc thay thế hàng ( )h a của ma trận H bằng cách cộng modulo-2 hàng ( )h b và ( )h c . Việc lựa chọn các hàng ( )h a , ( )h b , ( )h c được trình bày cụ thể trong [1]. C. ðặt vấn đề nghiên cứu Trong cách giải quyết vấn đề của [1] vẫn cịn các hạn chế. Thứ nhất, kết quả đánh giá chưa được thực hiện với kênh pha-đinh, loại kênh cĩ chất lượng tồi hơn kênh tạp âm Gao-xơ trắng cộng tính AWGN (Addative White Gaussan Noise) rất nhiều, nhưng lại thường gặp hơn trong các hệ thống truyền tin vơ tuyến. Thứ hai, việc sử dụng các ma trận kiểm tra tương đương để giải mã làm cho khối lượng tính tốn tăng lên rất nhiều (ít nhất là bằng số ma trận H tương đương). Các nhược điểm này được giải quyết, khắc phục nhờ các nghiên cứu được đề xuất trong bài báo này. III. CÁC ðỀ XUẤT MỚI ðỐI VỚI PHƯƠNG PHÁP GIẢI Mà BPA-EH A. ðề xuất ứng dụng phương pháp giải mã BPA-EH cho kênh pha-đinh đa đường Trong các hệ thống thơng tin vơ tuyến, để tạo ra tính độc lập thống kê giữa các tia sĩng, ở phía thu người ta đặt các máy thu RAKE, khi đĩ tín hiệu trên các tia nhận được là độc lập và cĩ thể được xử lý song song. Lợi dụng tính chất này, bài báo đề xuất ý tưởng sử dụng thuật tốn giải mã BPA-EH cho kênh pha-đinh đa đường theo phương án sau: Thực hiện giải mã độc lập trên mỗi tia, tại đĩ sử dụng tất cả các ma trận H tương đương, và kết quả là trên mỗi tia nhận được một từ mã 1 2 ˆ ˆ ˆ ˆ, ,..., i n y y y=y , các từ mã này được đưa vào bộ quyết định cứng để tìm ra từ mã chính xác nhất. Với ý tưởng này đã kết hợp được tính phân tập trong khơng gian khi truyền sĩng đa đường với tính phân tập theo thời gian khi sử dụng mã một cách tối đa. B. ðề xuất phương pháp xây dựng ma trận kiểm tra tương đương rút ngắn thời gian giải mã Như đã trình bày trên đây, trong [1] thực hiện thuật tốn BPA-EH bằng việc sử dụng các ma trận kiểm tra tương đương e H , các ma trận này được tạo ra bằng việc thay thế hàng (tương ứng với nút kiểm tra kém tin cậy). ðiều này dẫn đến khối lượng tính tốn khi thực hiện giải mã lớn. Ở đây bài báo đề xuất phương án xây dựng các ma trận kiểm tra mới như sau: Ngồi việc thay thế hàng cĩ độ tin cậy kém của ma trận H gốc, bên cạnh đĩ ta thực hiện thay một số hàng cịn lại bằng hàng tồn “0” điều này sẽ làm giảm khối lượng tính tốn và do đĩ dẫn đến giảm thời gian giải mã đáng kể. Cơ sở lý luận của ý tưởng này được giải thích như sau: Với mã LDPC, một nút bit được nối tới nhiều nút kiểm tra, nên khi ta bỏ bớt một số nút kiểm tra vẫn đảm bảo là nút bit tin cậy dựa vào các bản tin từ nút kiểm tra khác. Mặt khác, điều quan trọng hơn là khi thực hiện thay các hàng của H bằng các hàng tồn “0” ta đã loại bỏ được các vịng kín ngắn trong H , các vịng kín này là nguyên nhân dẫn đến giảm chất lượng mã LDPC. Ý tưởng trên đây về mặt định tính sẽ thực sự cĩ ý nghĩa đối với các mã LDPC đặc biệt là các mã cĩ ma trận H kích thước lớn, tuy nhiên việc xác định số lượng cũng như vị trí hàng bị thay thế tối ưu đối với các mã này sẽ cực kỳ phức tạp vì ta khơng thể xác định cụ thể vị trí các vịng kín ngắn trong các ma trận này. Do vậy giải pháp đề xuất trong bài báo được trình bày như sau: Khi xây dựng ma trận tương đương e H ta thực hiện thay thế các hàng của ma trận H gốc với số lượng ≤1/3 tổng số hàng của ma trận này bằng các hàng tồn “0”, việc thay thế sẽ thực hiện luân phiên với mỗi e H tương ứng ở mỗi vịng lặp. Với việc thực hiện như trên ta đã trả lại những thơng tin về các bit tin bị mất ở vịng lặp trước và giảm lượng thơng tin mất mát với mỗi bít tin. Kết quả mơ phỏng được trình bày dưới đây sẽ cho ta những đánh giá định lượng những khằng định trên. IV. KẾT QUẢ MƠ PHỎNG, ðÁNH GIÁ A. Sơ đồ mơ phỏng hệ thống Hình 1. Sơ đồ mơ phỏng hệ thống Trong sơ đồ này, mã LDPC được sử dụng là mã bất quy tắc [4]. Thuật tốn giải mã dựa trên thuật tốn BPA-EH cải tiến. Theo lý thuyết mã tuyến tính, thì từ ma trận H gốc cĩ thể tạo ra các ma trận e H bằng việc thay thế 1 hàng ( )h a bằng tổng modulo-2 hàng ( )h b và ( )h c : ow( ) ow( ) ow( ), | r a r b r c a b c= ⊕ ≠ ≠e H = H (3) Việc lựa chọn các hàng ( )h a , ( )h b , ( )h c được chọn trên việc xét giá trị syndrome mềm [1]: ( ) ( ( ))min | ( |L s sign L y L y i j j j V i j V i ≈ ∏ ∈ ∈ ) ) (4) ( ) | min | ( ) | min | ( ) | min 1,2... 1,2... | L s L s L y i ji m j n = = = = ) (5) Hội thảo quốc gia 2014 về Điện tử, Truyền thơng và Cơng nghệ thơng tin (ECIT2014) ISBN: 978-604-67-0349-5 423 Ở đây min s là nút cĩ giá trị tuyệt đối của syndrome nhỏ nhất trong lần giải mã đầu tiên. Như ta đã biết nút kiểm tra cĩ syndrome nhỏ nhất sẽ kết nối với nút tin cĩ độ tin cậy thấp nhất, nên ta chọn a là hàng ứng với min ( )L s cĩ giá trị nhỏ nhất mang dấu dương (việc lựa chọn dấu dương đảm bảo chắc chắn syndrome này bị lỗi), hàng b ứng với max ( )L s cĩ giá trị lớn nhất mang dấu âm, cịn hàng c ứng với ( ) i L s cĩ giá trị tăng dần với a b c≠ ≠ . Ngồi việc thay thế hàng như ở trên, ta cịn thực hiện xĩa bỏ (thay thế bằng hàng cĩ tất cả các phần tử đều là “0”) ngẫu nhiên một số hàng trừ những hàng cĩ độ tin cậy kém đã thay và hàng cĩ độ tin cậy lớn nhất. B. Kết quả mơ phỏng + Kết quả mơ phỏng đánh giá chất lượng của thuật tốn giải mã BPA-EH cải tiến cho kênh AWGN: Hình 2 và Hình 3 trình bày kết quả đánh giá chất lượng mã BPA-EH cải tiến trên kênh AWGN với các ma trận 60 120× H và 120 240× H . Hình 2. So sánh chất lượng giải mã LDPC bằng thuật tốn BPA, BPA-EH, BPA-EH cải tiến với ma trận 60 120× H trên kênh AWGN. Từ Hình 2 cho thấy, đối với bộ mã 1 C sử dụng ma trận 60 120× H , khi thực hiện thuật tốn giải mã BPA-EH cải tiến (BPA-EH-erase 6 rows - xĩa 6 hàng từ ma trận e H của BPA-EH) và BPA-EH thì chất lượng giải mã tương đương nhau việc này mang lại độ lợi mã hĩa khoảng 0,75 dB ở tỷ lệ lỗi bít 410 e P −= so với BPA truyền thống, nhưng nếu tăng số hàng bị xĩa lên 7 và 12 thì chất lượng giải mã của BPA-EH cải tiến sẽ xấu đi so với BPA-EH. Hình 3. So sánh chất lượng giải mã LDPC bằng thuật tốn BPA, BPA-EH, BPA-EH cải tiến với ma trận 120 240× H trên kênh AWGN. Trên Hình 3 ta thấy, khi xĩa một số hàng của e H đồng nghĩa với việc ta phá vỡ 1 hoặc một số vịng kín ngắn trong nĩ nhưng khi số hàng bị xĩa quá lớn sẽ làm giảm khả năng kiểm tra với một số bít tin. Vì vậy, việc sử dụng ma trận H tương đương kết hợp xĩa một số hàng khơng những làm giảm sự phức tạp trong quá trình tính tốn cỡ (10%) đối với bộ mã cĩ ma trận kiểm tra 60 120× H và 20 % đối với bộ mã ma trận kiểm tra 120 240× H , mà cịn cĩ khả năng tăng chất lượng giải mã so với thuật tốn BPA-EH trình bày trong [1], thời gian và chất lượng giải mã sẽ được cải thiện hơn đối với các mã dài. Tuy nhiên để đảm bảo chất lượng giải mã thì phải tìm được số hàng bị xĩa phù hợp với từng mã, đặc biệt hơn là tìm được các hàng xĩa phù hợp. + Kết quả mơ phỏng đánh giá chất lượng của thuật tốn giải mã BPA-EH cải tiến cho kênh pha-đinh: Trên cơ sở kết quả mơ phỏng trên kênh AWGN, ta tiến hành thực hiện thuật tốn BPA-EH cải tiến trên kênh pha-đinh với bộ mã 1 C đã xĩa 3 hàng và bộ mã 2 C đã xĩa 20 hàng, các kết quả mơ phỏng được trình bày trên Hình 4 và Hình 5. Kết quả trên Hình 4 và Hình 5 cho thấy, đối với kênh pha-đinh đa đường, nếu dùng phương pháp giải mã BPA-EH và BPA-EH cải tiến cho tín hiệu đầu vào là tín hiệu tổng hợp của các tia thì chất lượng của 2 thuật tốn này tương đương nhau và tốt hơn so với chất lượng của thuật tốn BPA truyền thống khoảng 1,2 dB. Bên cạnh đĩ kết quả Hình 4 cũng cho thấy, chất lượng của thuật tốn giải mã BPA – EH cải tiến với việc ứng dụng đề xuất giải mã trên kênh pha-đinh đã trình bày ở Mục III.A (trên Hình 4 và Hình 5 được chú thích Hội thảo quốc gia 2014 về Điện tử, Truyền thơng và Cơng nghệ thơng tin (ECIT2014) ISBN: 978-604-67-0349-5 424 là BPA-EH cải tiến 1) tốt hơn đáng kể so với thuật tốn BPA ban đầu cỡ 13 dB và cỡ 9 dB so với thuật tốn BPA – EH ở tỷ lệ lỗi 10-4 . Hình 4. So sánh chất lượng giải mã LDPC bằng thuật tốn BPA, BPA-EH, BPA-EH cải tiến với ma trận 60 120× H trên kênh pha-đinh. Cũng tương tự, từ kết quả Hình 5 cho thấy, chất lượng của thuật tốn giải mã BPA – EH cải tiến 1 tốt hơn đáng kể so với thuật tốn BPA ban đầu cỡ 9 dB và cỡ 6 dB so với thuật tốn BPA – EH ở tỷ lệ lỗi 10-4. Sở dĩ cĩ được kết quả trên, là do trong quá trình giải mã đã thực hiện kết hợp được tính phân tập trong khơng gian trong truyền sĩng đa đường với tính phân tập theo thời gian khi sử dụng mã một cách tối đa làm cải thiện đáng kể chất lượng giải mã LDPC, điều này mở ra một hướng nghiên cứu mới trong việc ứng dụng mã kênh cho các hệ thống truyền tin bị ảnh hưởng bởi pha-đinh đa đường. V. KẾT LUẬN Từ kết quả mơ phỏng trình bày trong bài báo, cĩ thể khẳng định rằng: Các thuật tốn giải mã BPA-EH và BPA-EH cải tiến cho chất lượng mã LDPC được cải thiện cả trên kênh AWGN và trên kênh pha-đinh. ðộ lợi trên kênh AWGN khoảng 0,75dB, trên kênh pha-đinh khoảng 1 dB (ở 410 e P −= ). Khi chất lượng kênh tốt lên, thì sử dụng thuật tốn BPA-EH cải tiến cho chất lượng tốt hơn so với thuật tốn BPA-EH, nĩ cho độ lợi mã hĩa ≥ 6 dB so với thuật tốn BPA thuần túy. Thuật tốn BPA-EH cải tiến cho độ lợi về thời gian mã hĩa từ 10%-20% so với thuật tốn BPA-EH. ðộ lợi này tăng lên cùng với kích thước ma trận kiểm tra H . TÀI LIỆU THAM KHẢO [1] Nguyen Tung Hung, “A new decoding algorithm based on equivalent parity check matrix for LDPC codes,” REV Journall on Electronics and Communications, Vol.3, No. 1-2, Jannuary – June, 2013 [2] R,Gallager, “Low-density parity-check codes,” IRE Trans, Information Theory, pp. 21-28. January 1962. [3] William E. Ryan, “An introduction to LDPC codes,” Department of Electrical and Computer Engineering, the University of Arizona, August 19,2003. [4] Thomas J. Richardson, M. Amin Shokrollahi, Member, IEEE, and Rudiger L.Urbanker “Design of capacity-Approaching irregular low-density parity- check codes,”IEEE Transactions on Information Theory, Vol. 47, No. 2, February 2001. Hình 5. So sánh chất lượng giải mã LDPC bằng thuật tốn BPA, BPA-EH, BPA-EH cải tiến với ma trận 120 240× H trên kênh pha-đinh. Hội thảo quốc gia 2014 về Điện tử, Truyền thơng và Cơng nghệ thơng tin (ECIT2014) ISBN: 978-604-67-0349-5 425