Nghiên cứu phương pháp giải mã golay bằng thuật toán Vetcan - Trần Thị Hường

Hóa học & Kỹ thuật môi trường T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp thuật toán vetcan.” 134 NGHIÊN CỨU PHƯƠNG PHÁP GIẢI MÃ GOLAY BẰNG THUẬT TOÁN VETCAN Trần Thị Hường*, Trần Đức Chuyển, Vũ Hữu Thích Tóm tắt: Trong bài báo này, các tác giả trình bày một thuật toán mới sử dụng mã Golay, nhằm nâng cao khả năng sửa lỗi với số lỗi lớn hơn nhiều so với mã thông thường, khả năng kiểm soát lỗi của thuật toán dựa vào tính chất của mã vòng, mã khối tuyến tính. Thuật toán vetcan có ý nghĩa là lấy toàn bộ các từ mã trong không gian của bộ mã đối ngẫu để quyết định từ mã nhận được với độ lợi giải mã lên tới 1,85 dB so với phương pháp giải mã cứng HDD tại BER = 10-4, tuy nhiên, độ phức tạp giải mã tăng theo hàm mũ với số mũ là số bit kiểm tra của mã đối ngẫu. Quá trình giải mã này có ưu điểm làm việc tin cậy, độ ổn định cao, xử lý nhiều dữ liệu của hệ thống một cách chính xác và nhanh chóng. Từ khóa: Mã Golay; Thuật toán vetcan; Giải mã dùng mã Golay. 1. ĐẶT VẤN ĐỀ Hiện nay, cùng với sự phát triển ngày càng cao của kỹ thuật vi xử lý; các onchip mới; các thuật toán thông minh và máy tính số, việc sửa lỗi trước (Forward Error Correction – FEC) có ý nghĩa thực tiễn, quan trọng để cải thiện tỉ lệ lỗi bít (BER) của các hệ thống tuyền dẫn và lưu trữ số. Mã nhị phân Golay (23,12,7) là mã nhị phân sửa được lỗi rất lớn, hoàn hảo được giới thiệu năm 1949, [1], với các tính chất toán học đặc biệt. Việc thêm vào một bít kiểm tra chẵn lẻ sẽ tạo ra mã nhị phân mở rộng tự đối ngẫu (24,12,8) tỉ lệ ½ và được ứng dụng nhiều trong thực tế (ví dụ trên tàu vũ trụ làm nhiệm vụ Voyager năm 1977) hay cũng được sử dụng như là một mã kiểm soát lỗi độc lập bên trong các hệ thống kết hợp để xử lý tín hiệu. Trong bài báo này, việc nghiên cứu các thuật toán nhằm áp dụng cho mã Golay để đạt được hiệu suất mong muốn với độ phức tạp chấp nhân được là điều mong mỏi của các nhà khoa học. Bài báo này giới thiệu về mã Golay và các thuật toán giải mã, từ đó đưa ra cải tiến mới. Kết quả mô phỏng trên kênh AWGN cho minh chứng về hiệu quả của thuật toán mới nâng cao chất lượng giải mã cho mã Golay. Các tác giả sử dụng phần mềm Matlab - Simulink để tiến hành mô phỏng đánh giá kết quả nhằm kiểm chứng thực nghiệm, đánh giá chất lượng của bộ thuật toán, [3, 4]. 2. XÂY DỰNG LÝ THUYẾT VỀ PHƯƠNG PHÁP GIẢI MÃ 2.1. Quá trình mã hóa Mã nhị phân tuyến tính C(n,k) được gọi là mã vòng nếu mọi từ mã c Є C, thì từ mã dịch vòng sang trái hay phải đều thuộc C, [2]. Giả sử từ mã c được biểu diễn dạng đa thức c(x): 2 n-1 0 1 2 n-1c(x) = c + c x + c x + ... + c .x (1) thì có thể chứng minh được mã nhị phân tuyến tính luôn tồn tại một đa thức sinh g(x) có bậc r: 2 n-1 0 1 2 n-1c(x) = c + c x + c x + ... + c .x (2) Từ mã c(x) được tạo ra ở đầu ra bộ mã hóa có đa thức sinh g(x) nên ta có: c(x) = m(x).g(x) (3) Các hệ số trong các đa thức c(x) và g(x) có thể nhận các giá trị nhị phân 0 hoặc 1; m(x) là đa thức bản tin với k là hệ số cũng nhận các giá trị nhị phân 0 hoặc 1. Lúc này, đa thức bản tin m(x) có dạng: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 135 2 k-1 0 1 2 k-1m(x) = m + m x + m x +.... + m x (4) trong đó, mi là các véc tơ mang tin. Với mã Golay ta có thể thực hiện mã hóa dựa vào tính chất của mã vòng, khi đó, với mã Golay (23,12,7) có đa thức sinh g(x) có bậc là 11 và được biểu diễn ở dạng: 5 6 7 9 11g(x) = 1 + x + x + x + x + x + x (5) đa thức g(x) có bậc 11 và được biểu diễn dạng ma trận G: Thực hiện chuyển đổi hàng trong ma trận G, ma trận sinh dạng hệ thống của mã được biểu thị như sau: 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 SG    0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 | kP I                                       (6) Trong đó, P là ma trận kiểm tra tính chẵn lẻ, Ik ma trận đơn vị với k = 12, từ mã dạng hệ thống thu được biểu diễn như sau: c = M.GS. Dựa vào tính chất của mã vòng ta có thể xác định được ma trận kiểm tra H từ các đa thức kiểm tra: h(x), h(x) = (x23 – 1)/g(x). Đa thức đối ngẫu h*(x) = h(x-1). Đa thức: h(x) = h0 + h1x + h2x 2 +hkx k, k = n – r. Từ đó, ta có ma trận kiểm tra H có dạng: 1 0 1 1 0 1 0 1 0 ...... 0 ..... 0 0 0 ..... 0 ..... 0 ..... ...... ...... ..... ..... ..... ...... ..... 0 ..... 0 ..... 0 0 ..... 0 0 ..... k k k h h h h h h H h h h h h h                (7) Đa thức kiểm tra h(x) của mã GOLAY (23,12) thì: h(x) = (x23 -1)/g(x) = x12+ x10 +x7 +x4 + x3 + x2 + x +1, bậc của h(x) là 12 nên ma trận kiểm tra H(12 x 23) được biểu diễn như biểu thức (8). Để truyền tín hiệu qua kênh, từ mã c được điều chế BPSK. Trong quá trình truyền tín hiệu điều chế cBPSK bị tác động bởi nhiễu Gauss trắng cộng tính (AWGN - Additive White GaussianNoise) w có kỳ vọng bằng không và phương sai 2/0 2 N với N0 mật độ phổ công suất tạp âm. Hóa học & Kỹ thuật môi trường T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp thuật toán vetcan.” 136 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 H  0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1                                      (8) Biến đổi hàng trong (8) biến đổi (P,Ik) thành [Ik,P T) trong (6) ta có: 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 9 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 , 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 T SH I P    1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1                                      (9) Phương pháp giải mã thông thường là giải mã cứng (Hard Decision Decoding – HDD) thì cho chất lượng giải mã rất thấp. Chuỗi tín hiệu đầu vào bộ giải mã c’(sau giải điều chế) bắt buộc phải nhận thông tin trực tiếp từ tin bị nhiễu Y. Bộ giải mã cứng HDD tính syndrome và véc tơ lỗi tương ứng: S = Y.HT = (cBPSK + e).H T = e.HT (10) với HT ma trận chuyển vị của ma trận kiểm tra H, e véc tơ lỗi. Từ mã quyết định tại đầu ra bộ giải mã HDD. 'lc c e  (11) Giải mã cứng HDD cho mã Golay với chiều dài từ mã khá lớn cho chất lượng thấp do lượng thông tin sử dụng cho giải mã hạn chế (từ tin bị nhiễu và ma trận kiểm tra H). Theo lý thuyết mã khối tuyến tính, bộ giải mã mã vòng C(n,k) đều tồn tại bộ mã C’(n,r) (r số lượng bit kiểm tra). Mã C’(n,r) được tạo ra từ đa tức kiểm tra h(x) của c(n,k), mà h(x) = (xn + 1)/g(x), đa thức đối ngẫu h*(x) = h(1/x) các bit trong mã C’(n,r) đều chứa thông tin giải mã. Từ phân tích trên, thay vì sử dụng ma trận kiểm tra H, thuật toán VETCAN sẽ tìm toàn bộ thông tin giải mã trong mã C’(n,r) (2r từ mã) và lấy thông tin mềm của các bit tin trong toàn bộ không gian bộ mã để quyết định từ mã đầu ra. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 137 Đa thức kiểm tra tính chẵn lẻ có dạng: h(x) = h0 + h1x + h2x 2 + + hk-1x k-1 với k = n – r là thừa số của đa thức: xn + 1= g(x).h(x). Nên c(x).h(x) = 0. 2.2. Giải mã GOLAY bằng thuật toán VETCAN Xét mã Golay (23,12,7) có khoảng cách Hamming tối thiểu dmin = 7, có thể xác định được các mẫu lỗi có trọng lượng ít hơn hoặc bằng t = [(dmin -1)/2] = [(7-1)/2] = 3 lỗi, như vậy, với phương pháp giải mã cứng HDD chỉ có thể sửa lỗi tối đa là 3. Để cải thiện khả năng sủa lỗi lớn hơn với mã GOLAY thì thuật toán vetcan được xây dựng để quét toàn bộ thông tin trong từ mã để quyết định từ mã đầu ra. Khi truyền từ mã bất kỳ C = (c1,c2,cn) của mã Golay qua kênh, dưới tác động của nhiễu AWGN tại đầu thu ta nhận được tin của mã Golay qua kênh, dưới tác động của nhiễu AWGN tại đầu thu ta nhận được tin y. Bộ giải điều chế tính tỷ lệ theo hàm Log tại các điểm tin nhận được c’ = (c’1 , c’2,c’n) để xác định sự ảnh hưởng của y đến c’ ta sử dụng biểu thức sau, [3]:   , , , Pr( | 1 ln Pr( | 0 i i i y c L c y c    (12) trong đó, Pr(x) là xác suất của x, Pr(x|y) là xác suất có điều kiện của x với điều kiện y đã cho. Từ mã c’ được đưa tới bộ giải mã, tập tin đầu vào mềm L(c’) sử dụng thông tin nhận được từ tất cả các bit trong không gian của từ mã C’(n,r) được tạo ra từ ma trận H để quyết định từ mã đầu ra c với độ tin cây cao nhất, [4]. Với khicl 0 : , 2 , 1 1 tan( ( / 2)) 0 r liki n c l i k i P L c      (13) Với 1lc thì Pl < 0, với δli = 1 khi l = i và δli = 0 khi l ≠ i, c’ki = 0 là bit thứ i của từ mã thứ k trong mã C’(n,r). Thuật toán vetcan được sử dụng để giải mã Golay được trình bày như hình 1. Bước 1: Sau khi nhận được tin đầu vào mềm L(c’) của bit tin từ bộ giải điều chế, bộ giải mã tính giá trị pi cho từng bít tin tương ứng với: 1))(exp( 1))(exp( ))2/(tanh(    i i ii cL cL cLp (14) Bước 2: Quyết định cứng từ mã đầu ra dựa vào tin nhận được từ tất cả các bit tin trong không gian mã: Với bit 0lc  khi đó giá trị pi là: 0))2/((tan 2 1 , 1 ,     r liki k c i n i l cLP  (15) Tăng giá trị l lên 1 cho tới khi l < n . Ngược lại với 1lc khi Pl < 0. Hóa học & Kỹ thuật môi trường T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp thuật toán vetcan.” 138 Hình 1. Lưu đồ thuật toán giải mã Golay. Bảng 1. Kích thước ma trận kiểm soát lỗi của thuật toán HDD, kích thước không gian kiểm tra theo VETCAN và độ lợi mã hóa của thuật toán VETCAN so với thuật toán HDD. Bộ mã Kích thước ma trận kiểm tra của HDD Kích thước không gian kiểm tra của VETCAN Độ lợi mã hóa của VETCAN so với HDD G(23,11) 11 x 23 (211 – 1) x 23 1,81dB G(24,12) 12 x 24 (212 – 1) x24 1,85dB 3. KẾT QUẢ MÔ PHỎNG VÀ THẢO LUẬN Sau khi nghiên cứu tuật toán và xây dựng chương trình mô phỏng trên phần mềm Matlab - Simulink để tiến hành mô phỏng đánh giá kết quả nhằm kiểm chứng tính đúng đắn của thuật toán, đánh giá chất lượng của bộ thuật toán. 0))2/((tan 2 1 , 1 ,     r liki k c i n i l cLP  Bắt đầu   0|Pr( 1|Pr( ln , , ,    i i i cy cy cL l = 1 Pi = tan(L(ci /2) Với i = 1n Cl’=0 S Đ Cl = 1 l < n l = l + 1 Đ S c’ = cl’ (l = 1n) Kết thúc Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 139 Kết quả mô phỏng được thực hiện trên phần mềm Matlab, với mã Golay (23,11) và mã Golay mở (24,12), giả sử tín hiệu được điều chế BPSK truyền trên kênh AWGN. Thực hiện mô phỏng đánh giá chất lượng giải mã của thuật toán vetcan và giải mã cứng HDD cho kết quả trên hình 2. 0 1 2 3 4 5 6 7 8 10 -7 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 EbNo[dB] B E R BER Golay tren kenh Gauss HDD Golay(23,11) HDD Golay(24,12) Vetcan Golay(23,11) Vetcan Golay(24,12) Hình 2. Kết quả mô phỏng của mã GOLAY bằng thuật toán VETCAN. Quan sát kết quả mô phỏng ta thấy chất lượng giải mã của thuật toán VETCAN tốt hơn rất nhiều so với giải mã cứng HDD. Đánh giá hiệu quả kiểm soát lỗi của thuật toán VETCAN tại BER = 10-4 thì VETCAN cho độ lợi đối với mã GOLAY và mã GOLAY mở rộng, độ lợi tương ứng là 1,81 dB và 1,85 dB so với giải mã cứng HDD. Tuy nhiên, thuật toán VETCAN này chỉ ra độ phức tạp giải mã được cho ở bảng 1, bảng chỉ ra độ phức tạp giải mã bằng cách so sánh số hàng của ma trận phải tính toán để kiểm soát lỗi trong thuật toán VETCAN, HDD ứng với BER = 10-4. Áp dụng thuật toán VETCAN cho mã Golay mở rộng có thể đạt được độ lợi 1,85dB so với thuật toán HDD. Như vậy, các mã tốc độ càng thấp thì cho độ lợi mã hóa càng cao và kích thước ma trận tham gia kiểm soát lỗi càng lớn. Đây là một trong những kết quả tốt được minh chứng cho thuật toán đã được thiết kế. 4. KẾT LUẬN Kết quả mô phỏng của bài báo trình bày phân tích đánh giá hiệu quả sử dụng thuật toán VETCAN cho mã GOLAY và mã GOLAY mở rộng về độ lợi mã hóa và phức tạp giải mã. So với thuật toán giải mã cứng HDD thì độ lợi của thuật toán VETCAN là 1,85dB với mã Golay. Tuy nhiên, để đạt được hiệu quả kiểm soát lỗi tốt hơn thì thuật toán giải mã VETCAN phải trả giá là tăng độ phức tạp của thuật toán theo hàm mũ 2r. Vậy thuật toán đề xuất phù hợp với các mã tuyến tính có độ dư nhỏ. Bên cạnh đó, thuật toán này thực hiện với dụng lượng bộ nhớ nhỏ hơn rất nhiều, và giảm đáng kể về thời gian (20%) giải mã so với thuật toán HDD. Các kết quả mô phỏng đã chứng tỏ rằng bộ thuật toán nghiên cứu được tính toán, xây dựng trong bài báo hoàn toàn có thể thực hiện trên thực tế, trong các lĩnh vực điện, điện tử và truyền thông; quốc phòng và an ninh hiện nay. Hóa học & Kỹ thuật môi trường T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp thuật toán vetcan.” 140 TÀI LIỆU THAM KHẢO [1]. M.J.E Golay, “Notes on digital coding” Proc, rd. 37, p.67, (1949). [2]. S. B. Wicher, “Error control Systems for Digital Communication and Storage”. Prentice Hall, (1995). [3]. H, Greenberger, “An iterative algorithm for decoding block codes transmitted over a memoryless channel”, DSN progress report 42 - 47 July anh August, (1978). [4]. Han, Yunghsiang S. Hartmann, Carlos R.P; Chih-Chieh Chen, “Efcient Maximum – likelihood Sof – Decision Decoding of Linear Block codes Using Algorithm A” (1991). Electrical Engineering and computer Science Technical Reports. Paper 134, 12-1991. [5]. Czeslaw Koscielny, “Extended (24, 12) Binary Golay Code: Encoding and Decoding Procedures”. Wroclaw University of Applied Informatics, Wroclaw, Poland, (2006). ABSTRACT THE RESEARCH METHOD OF GOLAY CODES BY VETCAN ALGORITHM In this paper, the authors present a new algorithm using the Golay code, to improve the error correction capability with a much larger number of errors than the conventional code, the ability to control the error of the algorithm is based on the nature of code loops, linear block codes. The vetcan algorithm is meant to take all the code words in the space of the dual-code set to determine the code word with a decoding gain of up to 1.85 dB compared to the hard disk decoding method at BER = 10-4, but the exponential complexity increases exponentially with the exponent being the number of double-checking codes. This decoding process has the advantage of being reliable, highly stable, and able to handle a lot of system data accurately and quickly. Keywords: The code Golay; Vetcan algorithm; Decode using Golay code. Nhận bài ngày 18 tháng 2 năm 2018 Hoàn thiện ngày 2 tháng 5 năm 2018 Chấp nhận đăng ngày 10 tháng 8 năm 2018 Địa chỉ: Khoa Điện tử, Trường Đại học Kinh tế Kỹ thuật Công nghiệp - Bộ Công thương. * Email: huongtt@uneti.edu.vn; tdchuyen@uneti.edu.vn.