Đánh giá chất lượng mã LDPC sử dụng thuật toán BPA - EHR cho kênh pha - đinh đa đường

Kỹ thuật điện tử N. A. Tuấn, P. X. Nghĩa, “Đánh giá chất lượng mã LDPCkênh pha-đinh đa đường.” 242 ĐÁNH GIÁ CHẤT LƯỢNG MÃ LDPC SỬ DỤNG THUẬT TOÁN BPA- EHR CHO KÊNH PHA - ĐINH ĐA ĐƯỜNG Nguyễn Anh Tuấn1*, Phạm Xuân Nghĩa2 Tóm tắt: Bài báo trình bày phương pháp giải mã LDPC sử dụng thuật toán BPA-EHR (Là thuật toán BPA-EH được cải tiến bằng cách thay thế một số hàng của ma trận kiểm tra tương đương khi thực hiện giải mã). Phương pháp này cho phép giảm bớt số phép tính khi giải mã. Việc thay thế một số hàng trong ma trận kiểm tra cũng phá vỡ các vòng kín ngắn là nguyên nhân chính dẫn đến hiện tượng sàn lỗi. Các kết quả mô phỏng thực hiện trên mô hình kênh pha đinh đa đường cho kết quả cải thiện rõ rệt về độ lợi giải mã và rút ngắn được thời gian giải mã. Từ khóa: Mã LDPC, Thuật toán giải mã BPA-EH, Ma trận kiểm tra tương đương, Kênh pha - đinh đa đường. 1. ĐẶT VẤN ĐỀ Mã kiểm tra chẵn lẻ mật độ thấp LDPC (Low Density Parity Check) hiện nay vẫn là một trong những họ mã kênh mạnh nhất và được khuyến nghị sử dụng trong các hệ thống thông tin thế hệ mới. Việc nghiên cứu nâng cao chất lượng bộ giải mã LDPC là vấn đề thường được đặt ra cho những hệ thống truyền tin yêu cầu chất lượng cao. Mã LDPC về bản chất là một mã khối tuyến tính, cơ chế phát hiện và sửa sai của mã 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. Thuật toán lan truyền niềm tin BPA (Belief Propagation Algorithm) là thuật toán giải mã lặp do Gallager đề xuất đã được ứng dụng từ lâu và cho kết quả khá tốt [1], [2]. Tuy nhiên cũng như các loại mã sửa lỗi sử dụng thuật toán giải mã lặp, mã LDPC cũng phải chịu sự có mặt của sàn lỗi khi tỉ lệ năng lượng bit trên mật độ phổ công suất nhiễu (Eb/ N0) tăng cao [3], [4], đồng thời chất lượng giải mã còn chưa đạt được chất lượng giải mã hợp lẽ cực đại ML (Maximum Likelihood). Đã có rất nhiều công trình nghiên cứu nhằm cải thiện hiệu quả bộ giải mã LDPC. Thuật toán BPA-EH sử dụng các ma trận kiểm tra tương đương trong quá trình giải mã lặp [5] cho độ lợi giải mã khá tốt so với thuật toán giải mã BPA truyền thống, tuy nhiên thời gian thực hiện giải mã bị kéo dài do số lượng các phép tính trên các ma trận kiểm tra tương đương tăng theo và việc khắc phục hiệu ứng sàn lỗi là chưa rõ nét. Từ các 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 đối với mã LDPC và cải tiến trong khâu xử lý tính toán trên các ma trận kiểm tra tương đương nhằm tăng độ lợi giải mã, đặc biệt trong môi trường pha - đinh đa đường. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 243 2. THUẬT TOÁN GIẢI MÃ BPA, BPA-EH VỚI QUYẾT ĐỊNH LỰA CHỌN TỪ MÃ THEO TRỌNG SỐ SYNDROM 2.1. Thuật toán giải mã BPA (Belief Propagation Algorithm) 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) [1], [6]: 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 | )iy r   . Thuật toán BPA [1], [6] là thuật toán giải mã lặp có hai công đoạn chính: - Cập nhật bản tin cho tất cả các nút kiểm tra và gửi bản tin rji(b) từ nút kiểm tra tới các nút bít nối với nó. - Cập nhật bản tin cho tất cả các nút bít và gửi bản tin qji(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 và đư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ã. 2.2. Thuật toán giải mã BPA-EH Như ta đã biết thuật toán BPA-EH (Belief Propagation Algorithm - based on Equivalent parity check matrix H) là thuật toán sử dụng các ma trận kiểm tra tương đương e H [5]. 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ỉ xét trường hợp thành lập e H 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 [5]. 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 [5]: ( ) ( ( )) min | ( ) | i i i j j j V j V L s sign L y L y      (4) min 1,2... 1,2... | ( ) | min | ( ) | min | ( ) |i j i m j n L s L s L y      (5) Kỹ thuật điện tử N. A. Tuấn, P. X. Nghĩa, “Đánh giá chất lượng mã LDPCkênh pha-đinh đa đường.” 244 Ở đây smin là nút có giá trị tuyệt đối của syndrome là 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 ( )h a là hàng ứng với L(smin) 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 ( )h b ứng với L(smax) có giá trị lớn nhất mang dấu âm, còn hàng ( )h c ứng với L(si) có giá trị tăng dần với a b c  . 2.3. Phương pháp giải mã BPA-EHR với mục đích rút ngắn thời gian giải mã Khi thực hiện thuật toán BPA – EH ta đã sử dụng các ma trận H tương đương được tạo ra bằng việc thay thế mỗi hàng (tương ứng với nút kiểm tra kém tin cậy) bằng tổng của hai hàng khác. Điều này dẫn đến khối lượng tính toán lớn gấp m – 1 lần (m là số lượng hàng của ma trận). Ở đây chúng tôi đề xuất phương án xây dựng các ma trận kiểm tra mới như sau: Ngoài việc thay thế hàng có độ tin cậy kém của ma trận H gốc, chúng ta cũng có thể thay thế một số hàng có độ tin cậy kém bằng hàng toàn “0”. Điều này sẽ làm giảm khối lượng tính toán và do đó dẫn đến giảm thời gian giải mã đáng kể. Với mã LDPC, mỗi một nút bít đượ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 thì vẫn đảm bảo là nút bít tin cậy dựa vào các bản tin từ các nút kiểm tra khác. Mặt khác, khi thực hiện thay thế một hàng của ma trận H bằng toàn các bít “0”, ta đã phá bỏ được các vòng kín ngắn là nguyên nhân chủ yếu gây ra hiệu ứng sàn lỗi làm giảm chất lượng mã LDPC. Thuật toán giải mã sử dụng các ma trận tương đương e H kết hợp với thay thế một số hàng của ma trận kiểm tra bằng các hàng toàn “0” được gọi là thuật toán BPA-EHR (Belief Propagation Algorithm - based on Equivalent parity check matrix H with Replace rows). Trong bài báo này, nhóm nghiên cứu sử dụng hai phương án khi thực hiện khâu thay thế một số hàng của ma trận e H : - Phương án thay thế ngẫu nhiên các hàng của ma trận e H . Phương án này đơn giản nhưng hiệu quả không thật cao và chưa chặt chẽ về mặt toán học. - Phương án chọn ra tất cả các hàng có chứa vòng kín chu kỳ “4” trong các ma trận kiểm tra tương đương e H để thay thế bằng các hàng toàn “0”. Phương án này chỉ ra việc xóa triệt để các vòng kín có chu kỳ “4”, là nguyên nhân chủ yếu gây ra hiệu ứng sàn lỗi. 3. GIẢI MÃ LDPC SỬ DỤNG THUẬT TOÁN BPA-EHR TRÊN MÔ HÌNH KÊNH PHA – ĐINH ĐA ĐƯỜNG Như ta đã biết, đặc trưng của kênh pha – đinh đa đường là các tia sóng cùng xuất phát từ một máy phát, nhưng sẽ đi theo các tia khác nhau với độ trễ khác nhau (do độ dài đường đi khác nhau) đến một máy thu. Trong khuôn khổ bài báo, nhóm tác giả chỉ giới hạn khảo sát đối với mô hình kênh pha đinh phẳng (không chọn Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 245 lọc). Khi đó, có thể coi độ trễ giữa các tia ∆τ ≈ 0. Trong bài toán đang xét, để tạo ra tính độc lập thống kê giữa các tia sóng, nhóm nghiên cứu đề xuất ý tưởng sử dụng thuật toán giải mã BPA – EHR 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 tương đương eH , và kết quả là trên mỗi tia nhận được một từ mã 1 2, ,...,i i i iny y y y     . - Kết hợp lựa chọn từ mã để đưa ra từ mã chính xác nhất. Điều này chắc chắn sẽ tốt hơn việc gộp tất cả các tia lại trước khi thực hiện giải mã. Hình 1. Sơ đồ mô tả quá trình giải mã của thuật toán BPA – EHR trên mô hình kênh Pha - đinh đa đường. 3.1. Kết quả khảo sát trên kênh pha – đinh phẳng đơn đường 0 5 10 15 20 25 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 Eb/N0[dB] B E R BPA BPA-EH BPA-EH Replaced cycle 4 Hình 2. So sánh chất lượng giải mã LDPC bằng thuật toán BPA, BPA – EH, BPA – EHR (thay thế các hàng có chu kỳ 4) với ma trận H60x120 bất quy tắc trên kênh pha – đinh. Giải mã với He Giải mã với He Giải mã với He Quyết định từ mã hợp lý Từ mã C1 Từ mã C2 Từ mã CL Tia 1 Tia 2 Tia L Tia 2 Tia L Tia 1 Copt Kỹ thuật điện tử N. A. Tuấn, P. X. Nghĩa, “Đánh giá chất lượng mã LDPCkênh pha-đinh đa đường.” 246 Từ kết quả ở Hình 2 cho thấy, chất lượng mã LDPC với ma trận H60x120 ở hai thuật toán giải mã BPA – EH và BPA – EHR (BPA – EH replace cycle 4) trên kênh pha – đinh tương đương nhau, chúng cho độ lợi mã khoảng 3dB ở tỷ lệ lỗi 10-4 so với BPA thuần túy. Từ Hình 3 cho thấy, đối với mã LDPC sử dụng ma trận H60x120, khi thực hiện thuật toán giải mã BPA – EH cải tiến (BPA – EHR 4) từ ma trận He của BPA – EH và BPA – EHR 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 3,8 [dB] ở tỷ lệ lỗi bít Pe = 10 -4 so với BPA truyền thống, nhưng nếu tăng số hàng bị thay thế lên 8 và 12 hàng thì chất lượng giải mã của BPA – EHR sẽ xấu đi so với BPA – EH. 0 5 10 15 20 25 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 Eb/N0[dB] B E R BPA BPA-EH BPA-EH replaced 4 rows BPA-EH replaced 8 rows BPA-EH replaced 12 rows Hình 3. So sánh chất lượng giải mã LDPC bằng thuật toán BPA, BPA – EH, BPA – EHR thay thế 4, 8 và 12 hàng với ma trận H60x120 trên kênh pha – đinh phẳng đơn đường. 3.2. Kết quả khảo sát trên kênh pha – đinh phẳng đa đường Thực hiện khảo sát trên mô hình kênh pha – đinh như Hình.1 với các tham số của kênh pha – đinh như sau: - Số tia đến L = 5 tia; - Tần số Doppler chuẩn hóa fD_norm = 0.01. Thuật toán BPA –EHR thực hiện với ma trận kiểm tra H60x120 bất quy tắc. Như vậy, số lượng ma trận kiểm tra tương đương He được sử dụng tương ứng với số tia đến L = 5 trong mô hình kênh pha – đinh. Các kết quả mô phỏng được trình bày trên hình 4. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 247 0 5 10 15 20 25 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 Eb/N0[dB] B E R BPA BPA-EH BPA-EHR 4 BPA-EHR 4 RAKE Hình 4. So sánh chất lượng giải mã LDPC bằng thuật toán BPA, BPA- EH, BPA- EHR 4 (thay thế các hàng có chu kỳ 4) và BPA – EHR 4 RAKE (thay thế các hàng có chu kỳ 4 xử lý trên từng tia) với ma trận H60x120 trên kênh pha – đinh phẳng. Từ kết quả Hình 4 cho thấy, chất lượng của thuật toán giải mã BPA – EHR thay thế các hàng chu kỳ 4 được xử lý trên từng tia (BPA – EHR 4 RAKE) tốt hơn đáng kể so với thuật toán BPA ban đầu cỡ 15 [dB] và cỡ 11 [dB] so với thuật toán BPA – EH ở vị trí sàn lỗi Pe = 10 -4 . Việc 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ể quá trình giải mã LDPC. Tuy nhiên, điều này phải trả giá do làm tăng tính phức tạp của hệ thống, nhưng điều này có thể chấp nhận được so với việc cải thiện đáng kể quá trình giải mã trên kênh pha – đinh. Từ kết quả hình 5 cho thấy, chất lượng của thuật toán giải mã BPA – EHR thay thế các hàng chứa chu kỳ 4 được xử lý với 3 tia (BPA – EHR 3TIA) tốt hơn đáng kể so với thuật toán BPA ban đầu cỡ 17 [dB] và cỡ 3 [dB] so với thuật toán BPA – EHR được xử lý với 9 tia (BPA – EHE 9TIA) ở sàn lỗi Pe = 10 -4 . Điều này có thể được giải thích như sau khi số lượng tia ít thì năng lượng trên từng tia cao hơn khi bị phân tán trên 9 tia, do vậy mà số lượng từ mã khi có 3 tia đến ít hơn để lựa chọn nhưng có chất lượng (độ chính xác) cao hơn so với 9 tia mặc dù có nhiều sự lựa chọn từ mã nhưng hầu hết lại có chất lượng kém. Kỹ thuật điện tử N. A. Tuấn, P. X. Nghĩa, “Đánh giá chất lượng mã LDPCkênh pha-đinh đa đường.” 248 Hình 5. So sánh chất lượng giải mã LDPC bằng thuật toán BPA, BPA – EHR 4 (thay thế các hàng chu kỳ 4) ứng với số lượng tia tới khác nhau khi sử dụng ma trận H60x120 trên kênh pha – đinh phẳng đa đường. 4. KẾT LUẬN Từ các kết quả mô phỏng, ta có thể khẳng định rằng: Các thuật toán giải mã BPA-EH và BPA-EHR được cải tiến cho chất lượng mã LDPC được cải thiện tốt trên kênh pha-đinh, độ lợi trên kênh pha – đinh khoảng 1 dB(ở Pe = 10 -4). Khi chất lượng kênh tốt lên, thì sử dụng thuật toán BPA-EHR cải tiến cho chất lượng tốt hơn so với thuật toán BPA-EH, nó cho độ lợi mã hóa ≥1,2 dB so với thuật toán BPA thuần túy. Thuật toán BPA-EHR được cải tiến cho độ lợi về thời gian mã hóa từ 10%-20% so với thuật toá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. Với đề xuất thay thế các hàng có chứa chu kỳ 4 của các ma trận tương đương e H , kết quả độ lợi mã hóa còn tốt hơn, đặc biệt được cải thiện ở vùng sàn lỗi. Kết quả mô phỏng cũng cho thấy, với phương án xử lý độc lập các tia tới máy thu trong mô hình kênh pha - đinh phẳng đa đường trước khi đưa tới quyết định từ mã cho hiệu quả rõ rệt về độ lợi giải mã. Phương án này tuy làm tăng độ phức tạp của hệ thống nhưng lại kết hợp được tính phân tập về không gian với phân tập thời gian khi giải mã. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 249 TÀI LIỆU THAM KHẢO [1]. R.Gallager, “Low-density parity-check codes,” IRE Trans, Information Theory, pp. 21-28. January 1962. [2]. 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. [3]. T. Richardson, “Error floors of ldpc codes,” in Proceedings of the annual Allerton conference on communication control and computing, vol. 41, no. 3. The University; 1998, 2003, pp. 1426–1435. [4]. Y. Han and W. Ryan, “Low-floor decoders for ldpc codes,” Communications, IEEE Transactions on, vol. 57, no. 6, pp. 1663–1673, 2009. [5]. 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. [6]. Y. Han and W. Ryan, “Low-floor decoders for ldpc codes,” Communications, [7]. IEEE Transactions on, vol. 57, no. 6, pp. 1663–1673, 2009. ABSTRACT EVALUATION QUALITY OF LDPC DECODING USING BPA-EHR ALGORITHM FOR MULTIPATH FADING CHANNEL This article presents a method of LDPC decoding algorithm using BPA- EHR (BPA-EH algorithm is improved by removing some rows of check matrix equivalent when decoding). This method allows reducing the number of operations when decoding. Deleting a row in the matrix of checks and break the short cycle is the main cause leading to the error floor. The simulation results performed on the multi-path fading channels for significantly improved results for the gain decoding and shorten the time decoding. Keywords: LDPC codes, BPA-EH decoding algorithm, Equivalence checking matrix, Multi-path fading channel. Nhận bài ngày 21 tháng 07 năm 2015 Hoàn thiện ngày 10 tháng 08 năm 2015 Chấp nhận đăng ngày 07 tháng 09 năm 2015 Địa chỉ: 1Đại học Công nghệ thông tin & Truyền thông, Đại học Thái Nguyên; *Email: natuan@ictu.edu.vn; 2Học viện Kỹ thuật quân sự.