Nghiên cứu phương pháp giải mã Golay bằng thuật toán vetcan

Hóa học & Kỹ thuật môi trường<br /> <br /> NGHIÊN CỨU PHƯƠNG PHÁP GIẢI MÃ GOLAY<br /> BẰNG THUẬT TOÁN VETCAN<br /> Trần Thị Hường*, Trần Đức Chuyển, Vũ Hữu Thích<br /> 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<br /> 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ã<br /> 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,<br /> 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<br /> 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ã<br /> 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, độ<br /> 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.<br /> 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ữ<br /> liệu của hệ thống một cách chính xác và nhanh chóng.<br /> Từ khóa: Mã Golay; Thuật toán vetcan; Giải mã dùng mã Golay.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> 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;<br /> 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 –<br /> 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<br /> 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,<br /> 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<br /> 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à<br /> đượ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)<br /> 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<br /> hợp để xử lý tín hiệu.<br /> 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<br /> đượ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à<br /> 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<br /> 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<br /> 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 -<br /> Simulink để tiến hành mô phỏng đánh giá kết quả nhằm kiểm chứng thực nghiệm, đánh<br /> giá chất lượng của bộ thuật toán, [3, 4].<br /> 2. XÂY DỰNG LÝ THUYẾT VỀ PHƯƠNG PHÁP GIẢI MÃ<br /> 2.1. Quá trình mã hóa<br /> 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ã<br /> dịch vòng sang trái hay phải đều thuộc C, [2].<br /> Giả sử từ mã c được biểu diễn dạng đa thức c(x):<br /> c(x) = c0 + c1x + c 2 x 2 + ... + c n-1.x n-1 (1)<br /> 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ó<br /> bậc r:<br /> c(x) = c0 + c1x + c 2 x 2 + ... + c n-1.x n-1 (2)<br /> 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ó:<br /> c(x) = m(x).g(x) (3)<br /> 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)<br /> 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<br /> bản tin m(x) có dạng:<br /> <br /> <br /> 134 T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp … thuật toán vetcan.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> m(x) = m 0 + m1x + m 2 x 2 +.... + m k-1x k-1 (4)<br /> trong đó, mi là các véc tơ mang tin.<br /> 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<br /> 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:<br /> g(x) = 1 + x + x 5 + x 6 + x 7 + x 9 + x11 (5)<br /> đ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<br /> trong ma trận G, ma trận sinh dạng hệ thống của mã được biểu thị như sau:<br /> <br /> 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0<br /> 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 <br /> <br /> 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0<br />  <br /> 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0<br /> 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0<br />  <br /> 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0<br /> GS  <br /> 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 (6)<br />  <br /> 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0<br /> 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0<br />  <br /> 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0<br />  <br /> 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0<br /> 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 <br />   P | Ik <br /> <br /> <br /> 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<br /> hệ thống thu được biểu diễn như sau: c = M.GS.<br /> 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<br /> thức kiểm tra: h(x), h(x) = (x23 – 1)/g(x). Đa thức đối ngẫu h*(x) = h(x-1).<br /> Đa thức: h(x) = h0 + h1x + h2x2 +…hkxk, k = n – r. Từ đó, ta có ma trận kiểm tra H có<br /> dạng:<br /> <br />  hk ...... h1 h0 0 ..... 0 0<br /> 0 h1 ..... h1 h0 0 ..... 0 <br /> <br /> H  ..... ...... ...... ..... ..... ..... ...... ..... (7)<br />  <br /> 0 ..... 0 hk ..... h1 h0 0<br />  0 ..... 0 0 hk ..... h1 h0 <br /> <br /> Đa thức kiểm tra h(x) của mã GOLAY (23,12) thì:<br /> 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<br /> kiểm tra H(12 x 23) được biểu diễn như biểu thức (8).<br /> Để 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<br /> hiệu điều chế cBPSK bị tác động bởi nhiễu Gauss trắng cộng tính (AWGN - Additive White<br /> GaussianNoise) w có kỳ vọng bằng không và phương sai  2  N 0 / 2 với N0 mật độ phổ<br /> công suất tạp âm.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 135<br />  Hóa học & Kỹ thuật môi trường<br /> <br /> 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0<br /> 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0<br /> <br /> 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0<br />  <br /> 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0<br /> 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0<br />  <br /> 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0<br /> H   (8)<br /> 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0<br />  <br /> 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0<br /> 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0<br />  <br /> 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0<br />  <br /> 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1<br />  <br /> Biến đổi hàng trong (8) biến đổi (P,Ik) thành [Ik,PT) trong (6) ta có:<br /> <br />  1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 <br />  0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 <br />  <br />  0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 <br />  <br />  0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 <br />  0 0 0 0 1 0 0 0 0 0 0 1 1 0 9 1 0 0 0 1 1 1 1 <br />  <br /> 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 <br /> H S   I , PT   0 1 (9)<br /> 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0<br />  <br />  0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 <br />  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 <br />  <br />  0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 <br />  <br />  0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 <br />  <br /> <br /> <br /> Phương pháp giải mã thông thường là giải mã cứng (Hard Decision Decoding – HDD)<br /> 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ế)<br /> bắt buộc phải nhận thông tin trực tiếp từ tin bị nhiễu Y.<br /> Bộ giải mã cứng HDD tính syndrome và véc tơ lỗi tương ứng:<br /> S = Y.HT = (cBPSK + e).HT = e.HT (10)<br /> T<br /> với H ma trận chuyển vị của ma trận kiểm tra H, e véc tơ lỗi.<br /> Từ mã quyết định tại đầu ra bộ giải mã HDD.<br /> cl  c '  e (11)<br /> 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<br /> 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).<br /> 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)<br /> (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)<br /> = (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<br /> giải mã.<br /> 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<br /> 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<br /> toàn bộ không gian bộ mã để quyết định từ mã đầu ra.<br /> <br /> <br /> <br /> 136 T. T. Hường, T. Đ. Chuyển, V. H. Thích, “Nghiên cứu phương pháp … thuật toán vetcan.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Đa thức kiểm tra tính chẵn lẻ có dạng: h(x) = h0 + h1x + h2x2 + …+ hk-1xk-1 với k = n – r<br /> là thừa số của đa thức: xn + 1= g(x).h(x). Nên c(x).h(x) = 0.<br /> 2.2. Giải mã GOLAY bằng thuật toán VETCAN<br /> Xét mã Golay (23,12,7) có khoảng cách Hamming tối thiểu dmin = 7, có thể xác định<br /> đượ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ư<br /> 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ả<br /> 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ộ<br /> thông tin trong từ mã để quyết định từ mã đầu ra.<br /> 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<br /> 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<br /> 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<br /> 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ử<br /> dụng biểu thức sau, [3]:<br /> Pr( y | ci,  1<br /> L  ci,   ln (12)<br /> Pr( y | ci,  0<br /> 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 đã<br /> cho.<br /> 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<br /> đượ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<br /> định từ mã đầu ra c với độ tin cây cao nhất, [4].<br /> Với cl  0 khi :<br /> 2r n ,<br /> Pl   tan( L(ci, / 2))cki li  0 (13)<br /> k 1 i 1<br /> <br /> Với cl 1 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ừ<br /> mã thứ k trong mã C’(n,r). Thuật toán vetcan được sử dụng để giải mã Golay được trình<br /> bày như hình 1.<br /> 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<br /> mã tính giá trị pi cho từng bít tin tương ứng với:<br /> exp( L(ci )) 1<br /> pi  tanh( L(ci / 2))  (14)<br /> exp( L(ci ))  1<br /> 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<br /> không gian mã:<br /> Với bit cl  0 khi đó giá trị pi là:<br /> 2r n ,<br /> Pl   tan ( L(ci, / 2)) cki  li  0 (15)<br /> k 1 i 1<br /> <br /> Tăng giá trị l lên 1 cho tới khi l < n .<br /> Ngược lại với cl 1 khi Pl < 0.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 137<br />  Hóa học & Kỹ thuật môi trường<br /> <br /> <br /> Pr( y | ci,  1<br /> Bắt đầu  <br /> L ci,  ln<br /> Pr( y | ci,  0<br /> <br /> <br /> <br /> <br /> Pi = tan(L(ci /2)<br /> Với i = 1…n<br /> <br /> <br /> <br /> l=1<br /> <br /> <br /> Đ<br /> 2r n<br /> , c ki,   li<br /> Pl   tan ( L(c / 2))<br /> i 0 Cl’=0<br /> k 1 i 1<br /> <br /> <br /> <br /> <br /> S<br /> Cl = 1<br /> <br /> <br /> l=l+1<br /> <br /> <br /> Đ<br /> l