Giải mã tích bằng giải mã quyết định mềm dùng mã đối ngẫu đảm bảo tính khả dụng

Nghiên cứu khoa học công nghệ<br /> <br /> GIẢI MÃ TÍCH BẰNG GIẢI MÃ QUYẾT ĐỊNH MỀM<br /> DÙNG MÃ ĐỐI NGẪU ĐẢM BẢO TÍNH KHẢ DỤNG<br /> Phạm Xuân Nghĩa1, Nguyễn Thị Hồng Nhung2*<br /> Tóm tắt: Mã tích lần đầu tiên được giới thiệu bởi Elias vào năm 1954, gồm<br /> 2 mã khối nối tiếp với nhau, với khả năng sửa lỗi khá tốt. Tuy nhiên, nhược điểm<br /> cơ bản của mã tích là độ phức tạp trong quá trình giải mã quá lớn dẫn đến việc<br /> ứng dụng cũng như các nghiên cứu tiếp theo nhằm cải tiến chất lượng của mã<br /> này hầu như rất ít được đề cập. Đến nay, nhờ tiếp thu thành quả phát triển của<br /> kỹ thuật vi xử lý, nhược điểm trên đối với mã tích đã không còn là vấn đề khó<br /> khắc phục. Bài báo này trình bày việc ứng dụng thuật toán giải mã đối ngẫu và<br /> giải mã mềm cho các mã thành phần trong mã tích, điều này mang lại sự cải<br /> thiện độ phức tạp của thuật toán đáng kể so với các công bố trước, thúc đẩy khả<br /> năng ứng dụng mã tích trong hệ thống truyền tin số đảm bảo tính khả thi hơn so<br /> với các đề xuất trước đây với sự trả giá về chất lượng giải mã có thể chấp nhận<br /> được (từ 0,2 đến 0,5 dB).<br /> Từ khóa: Mã tích; Mã Hamming; Giải mã đối ngẫu, giải mã lặp; Giải mã quyết định mềm.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Mặc dù giải mã mềm có độ phức tạp tính toán cao hơn so với giải mã cứng nhưng với<br /> công nghệ hiện nay có thể chấp nhận trả giá cho độ lợi mã hóa cao hơn khoảng 2 ~ 3 dB<br /> [1]. Các thuật toán giải mã mềm tối ưu cho phép tối thiểu hóa xác suất lỗi từ mã cho kênh<br /> rời rạc không nhớ bất kỳ khi các từ mã là đồng xác suất. Giải mã Viterbi được dùng cho<br /> mã chập và giải mã tương quan dùng cho mã khối đều hoạt động theo kiểu vét cạn khi<br /> véc-tơ tín hiệu thu được so sánh với tất cả các từ mã có thể [2]. Do đó các kỹ thuật giải mã<br /> này thường ứng dụng hiệu quả đối với các mã có số lượng từ mã hạn chế, nghĩa là cho các<br /> mã có tỷ lệ mã hóa thấp hoặc các mã có tỷ lệ mã hóa trung bình-cao nhưng với chiều dài<br /> từ mã (khối) hoặc chiều dài ràng buộc máy mã (chập) ngắn. Bên cạnh đó, cũng như thuật<br /> toán MAP (Maximum Aposteriori Probability), thuật toán giải mã dùng mã đối ngẫu là<br /> giải mã tối ưu theo nghĩa tối thiểu hóa xác suất lỗi bít cho kênh rời rạc không nhớ khi các<br /> từ mã là đồng xác suất [3], [4]. Giải mã đối ngẫu cũng dựa trên kỹ thuật vét cạn, nhưng là<br /> so sánh với tất cả các từ mã đối ngẫu chứ không phải là các từ mã có thể có. Nghĩa là giải<br /> mã đối ngẫu phù hợp cho các mã có tỷ lệ mã hóa cao hoặc mã có tỷ lệ mã hóa trung bình-<br /> thấp nhưng với chiều dài từ mã (khối) hoặc chiều dài ràng buộc máy mã (chập) ngắn.<br /> Trong khi các thuật toán giải mã như BPA (Belief Propagation Algorithm) và MAP<br /> được ứng dụng rộng rãi cho mã FEC (Forward Error Correction) hiện đại, thuật toán giải<br /> mã đối ngẫu hầu như không được nhắc tới kể từ khi được đề xuất bởi Carlos R. P.<br /> Hartmann và Luther D. Rudolph từ Đại học Syracuse trong bài báo “An Optimum<br /> Symbol-by-Symbol decoding rule for linear codes” đăng tải trên Tập san Engineering and<br /> Computer Science Technical Reports, năm 1975. Một trong những lý do cơ bản là giải mã<br /> đối ngẫu, mặc dù tối ưu, nhưng chỉ thích hợp cho các mã có tỷ lệ mã hóa cao như đã nêu ở<br /> trên. Mà các mã khối tuyến tính có tỷ lệ mã hóa cao thì khó (hoặc không thể) đạt được<br /> khoảng cách Hamming tối thiểu đủ lớn cho các ứng dụng truyền tin hiện đại. Với mục<br /> đích tận dụng các ưu điểm của kỹ thuật giải mã đối ngẫu và mã tích, bài báo này đề xuất<br /> phương án ứng dụng kỹ thuật giải mã mềm và mã đối ngẫu cho các mã thành phần của mã<br /> tích. Hy vọng đề xuất này sẽ mở ra hướng mới về ứng dụng mã tích trong các hệ thống<br /> truyền tin số. Phần còn lại của bài báo có bố cục như sau: Mục 2 trình bày ý tưởng ứng<br /> dụng giải mã mềm và mã đối ngẫu cho mã tích. Mục 3 đề xuất thuật toán giải mã lặp cho<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 11<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> mã tích, ứng dụng phương pháp giải mã mềm và mã đối ngẫu. Mục 4 trình bày các kết quả<br /> mô phỏng đánh giá chất lượng của các mã tích vừa xây dựng trên kênh Gauss và cuối cùng<br /> là phần Kết luận.<br /> 2. ỨNG DỤNG GIẢI MÃ MỀM VÀ MÃ ĐỐI NGẪU CHO MÃ TÍCH<br /> Ý tưởng sử dụng mã tích gồm hai mã khối tuyến tính với tỷ lệ mã hóa trung bình- cao<br /> kết hợp với giải mã quyết định mềm sử dụng mã đối ngẫu dựa trên cơ sở:<br /> a) Tỷ lệ mã hóa của mã tích (bằng tích của tỷ lệ mã hóa của hai mã thành phần) sẽ đủ<br /> lớn khi các mã thành phần có tỷ lệ mã hóa trung bình- cao;<br /> b) Mặc dù mã thành phần với tỷ lệ mã hóa trung bình- cao có cự ly Hamming tối thiểu<br /> nhỏ, nhưng cự ly Hamming tối thiểu của mã tích (bằng tích của cự ly Hamming tối thiểu<br /> của hai mã thành phần) đủ lớn cho các ứng dụng đã nêu ở trên;<br /> c) Quan trọng nhất là các mã thành phần với tỷ lệ mã hóa trung bình – cao thì giải mã<br /> quyết định mềm sử dụng mã đối ngẫu cho phép cấu trúc thành giải mã lặp vừa đơn giản,<br /> vừa hiệu quả.<br /> Tuy nhiên, để tổ chức thành hệ thống giải mã lặp thì cần cải tiến thuật toán giải mã<br /> nguyên bản của Carlos R. P. Hartmann và Luther D. Rudolph sao cho giá trị đầu ra của<br /> giải mã hàng có thể dùng làm đầu vào cho giải mã cột và ngược lại. Cách tiếp cận của<br /> Hagenauer và các đồng tác giả trong bài báo kinh điển “Iterative decoding of binary and<br /> convolutional codes” là loại bỏ giả thiết các bít mã có xác suất như nhau, sau đó đưa ra<br /> công thức tính tỷ lệ hợp lẽ trong miền log để tính giá trị thông tin ngoài dùng trong giải mã<br /> lặp. Việc trực tiếp tính các giá trị tỷ lệ hợp lẽ làm đầu vào mềm, đầu ra mềm cho các bộ<br /> giải mã thành phần như là nối tiếp thuật toán của Hartmann và Rudolph. Cụ thể như sau:<br /> Cho là mã khối tuyến tính với ma trận sinh kích thước ( × ), ma trận kiểm tra<br /> kích thước (( − ) × ), và = ( , , … , ) là từ mã. Giả sử từ mã này được điều<br /> chế thành tín hiệu nhị phân ±1 theo qui tắc = 1 − 2 , và được truyền qua kênh rời rạc<br /> không nhớ tạp âm Gauss với mật độ phổ công suất 2 . Tín hiệu thu được là = + ,<br /> trong đó =( , … , ) là véc-tơ tạp âm và = + , 1 ≤ ≤ . Cho là<br /> mã đối ngẫu của , với = ( , , … , ) là từ mã đối ngẫu thứ j. Ký hiệu , ∈<br /> {0,1} là xác suất có điều kiện rằng thu được khi bít mã = được gửi đi. Ký hiệu<br /> = 1 / 0 là tỷ lệ hợp lẽ (Likelihood Ratio) của bít thứ q. Dễ dàng tính được<br /> = exp (−2 / ). Đặt<br /> ℓ<br /> (0) = ∑ ∑ ∏ℓ ∑ (−1) ℓ<br /> (1)<br /> <br /> <br /> = (−1) ℓ + (−1) ℓ ℓ<br /> ,<br /> ℓ ℓ<br /> ℓ<br /> (1) = ∑ (−1) ∑ ∏ℓ ∑ (−1) ℓ<br /> (2)<br /> <br /> ℓ<br /> = (−1) ℓ − (−1) ℓ<br /> .<br /> ℓ ℓ<br /> <br /> Trong [4] đã chứng minh rằng (0) = (0| ) và (1) = (1| ), với một hệ số<br /> xác định . Nói cách khác, máy giải mã sẽ quyết định rằng bít = 0 được gửi qua kênh<br /> khi và chỉ khi (0) > (1) hay (0)− (1) > 0. Bài báo cũng dẫn dắt cách tính<br /> (0)− (1) và chứng minh rằng:<br /> <br /> <br /> <br /> 12 P. X. Nghĩa, N. T. H. Nhung, “Giải mã tích bằng … mã đối ngẫu đảm bảo tính khả dụng.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> <br /> <br /> (0)+ (1) = 2 (−1) ℓ <br /> ℓ<br /> ℓ ℓ<br /> = ∑ ∏ℓ , (3)<br /> ℓ<br /> <br /> <br /> <br /> <br /> (0)− (1) = 2 (−1) ( ℓ ℓ)<br /> <br /> ℓ<br /> <br /> 1− ℓ⊕ ℓ<br /> ℓ<br /> = , (4) <br /> 1+ ℓ<br /> ℓ<br /> với = 1 khi = ℓ và ℓ = 0 khi ≠ ℓ.<br /> ℓ<br /> Vì đầu vào của phép tính cho giải mã là mà đầu ra của giải mã lại là hiệu<br /> (0)− (1) = (0| ) − (1| ) <br /> nên như đã nói ở trên, ta cần biến đổi để đầu ra của tính toán có thể làm đầu vào cho vòng<br /> lặp sau. Xét<br /> (1) (1| ) 1 ( | ) 1 (1) 1<br /> = = = = = (5)<br /> (0) (0| ) 0 ( | ) 0 (0) 0<br /> với giả định rằng các bít 0 và 1 được gửi đi với xác suất như nhau.<br /> Vậy, ý tưởng quan trọng của bài báo là đưa ra công thức tính lượng tin đầu vào vòng<br /> lặp tiếp theo:<br /> (1) −<br /> = = (6)<br /> (0) +<br /> với<br /> ′<br /> 1− ℓ<br /> ℓ<br /> = (7)<br /> 1+ ℓ<br /> ℓ<br /> <br /> 1− ℓ⊕ ℓ<br /> ℓ<br /> = . (8)<br /> 1+ ℓ<br /> ℓ<br /> Công thức (6) chính là cơ sở lý thuyết cho đề xuất thuật toán giải mã tích mới được<br /> trình bày dưới đây.<br /> 3. ĐỀ XUẤT THUẬT TOÁN GIẢI MÃ LẶP CHO MÃ TÍCH<br /> ỨNG DỤNG PHƯƠNG PHÁP GIẢI MÃ ĐỐI NGẪU<br /> Ở đây, thuật toán mới ứng dụng cho mã tích được xây dựng trên cơ sở thuật toán DCA<br /> ký hiệu là DCAPC (Dual codes Algorithm decoding of Product Codes) [4], [5]. Trong đó,<br /> ta xét mã tích của hai mã khối tuyến tính. Cho là mã khối tuyến tính với ma trận sinh<br /> kích thước ( × ), ma trận kiểm tra kích thước (( − ) × ) và là mã<br /> khối tuyến tính với ma trận sinh kích thước ( × ), ma trận kiểm tra kích thước<br /> (( − ) × ).<br /> Mỗi nhịp mã hóa, hàng, mỗi hàng bít thông tin, được mã hóa thành từ mã<br /> thuộc , mỗi từ mã gồm bít mã. Sau đó cột, mỗi cột bít, được mã hóa thành<br /> từ mã thuộc , mỗi từ mã gồm bít mã. Tổng thể bít thông tin được mã hóa thành<br /> bít mã, tỷ lệ mã hóa là ( / )( / ) và cự ly Hamming tối thiểu là ( ), với<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 13<br />  K<br /> Kỹỹ thuật điều khiển & Điện tử<br /> <br /> và lần<br /> ần lư<br /> lượt<br /> ợt là<br /> là ccự<br /> ự ly Hamming tối thiểu của m<br /> mãã và . Cấu<br /> ấu trúc của m<br /> mãã này được<br /> được<br /> trình bày trên Hình 1.<br /> <br /> <br /> <br /> × bit<br /> kiểm<br /> ểm tra<br /> × bit chẵn<br /> ẵn lẻ m<br /> mã<br /> thông tin hàng<br /> <br /> <br /> × bít kiểm<br /> ểm<br /> × bít ki<br /> kiểm<br /> ểm tra chẵn tra ch<br /> chẵn<br /> ẵn lẻ mãm<br /> lẻẻ m<br /> mãã ccột hóa các bít ki<br /> kiểm<br /> ểm<br /> tra chẵn<br /> chẵn lẻ<br /> <br /> <br /> Hình 1 1.. C<br /> Cấu<br /> ấu trúc của m mãã tích.<br /> Ta ký hihiệuu ma trtrậnn tín hi u thu là = [ , 1 ≤ ≤ , 1 ≤ ≤ ].. Tính ma tr<br /> hiệệu trậnn giá<br /> trịị tỷ lệ hợp ng bít mã = [<br /> p llẽẽ cho ttừng , 1 ≤ ≤ , 1 ≤ ≤ ]], = exp<br /> exp (− −2 /<br /> ).. Cho và lần<br /> ần llượt<br /> ợt llàà mã đối<br /> ối ngẫu của m mã và . Đ Đềề xuất<br /> xu t thuật<br /> thu t toán gi<br /> giảii mã llặpp<br /> cho mã tích nh như ư sau. V Vớii ttừng<br /> ng hàng củ củaa ma tr sử dụng (7) và (8) đđểể tính , với<br /> trậận , sử ới<br /> ∈ và sử<br /> s dụng<br /> d ng (6) đđể ccập p nhập<br /> nh p ma trậtrận . Sau đó vvớ ới từ<br /> ừng<br /> ng ccộột củ<br /> ủaa ma trận<br /> tr n , sử ử ddụng<br /> ụng<br /> (7) và (8) để để tính , ới ∈<br /> vvới và ssử ddụng<br /> ng (6) để<br /> đ cập<br /> c p nh<br /> nhậậtt ma trận<br /> tr n . Quá trình gi giải<br /> ải<br /> mã được<br /> được lặp lại nh nhưư trên, gi ải mã<br /> giải mã theo hàng ti tiếp<br /> ếp sau là<br /> là giải<br /> giải m<br /> mãã theo ccột.<br /> ột. Thuật toán giải m mãã<br /> cho ttừngừng hhàng,<br /> àng, hohoặc<br /> ặc từng cột đđược ợc trình<br /> trình bày trên hìnhình 2.<br /> <br /> Do giải<br /> giải mã<br /> mã quy<br /> quyết<br /> ết định mềm sử dụng m mãã đối<br /> ối ngẫu llàà gi<br /> giải<br /> ải m<br /> mã tối<br /> ối ưu cho ttừng<br /> ừng mã<br /> mã thành<br /> phần<br /> ph ần nnên<br /> ên ch<br /> chỉỉ cần hai lần lặp llàà đã<br /> đã đạt<br /> ạt đ<br /> được<br /> ợc chất llượng<br /> ợng giải mmãã ttốt<br /> ốt nhất của m<br /> mãã tích.<br /> <br /> <br /> <br /> <br /> Hình 22.. Lưu đđồ<br /> ồ giải mã<br /> mã cho m<br /> mỗi<br /> ỗi hhàng<br /> àng hoặc<br /> hoặc mỗi cột cho m<br /> mãã tích.<br /> <br /> <br /> 14 P. X. Nghĩa,<br /> Nghĩa, N. T. H. Nhung,<br /> Nhung “Gi<br /> Giải<br /> ải mã<br /> mã tích bbằng<br /> ằng … mã đối dụng.””<br /> ối ngẫu đảm bảo tính khả dụng<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 4. MÔ PHỎNG ĐÁNH GIÁ CHẤT LƯỢNG MÃ TÍCH VỚI PHƯƠNG PHÁP GIẢI<br /> MÃ LẶP KẾT HỢP VỚI MÃ ĐỐI NGẪU TRÊN KÊNH GAUSS<br /> <br /> Ở mục này, tiến hành mô phỏng đánh giá chất lượng mã tích gồm hai mã thành phần<br /> là các mã Hamming với các giá trị r= m= 3, 4, 5, 6 (là số bít kiểm tra chẵn lẻ, với quan hệ<br /> giữa các đại lượng = 2 − 1, = − ), cấu trúc của mã tương tự như cấu trúc tổng<br /> quát đã được mô tả trên hình 1 (ở đây lưu ý là thay tham số r bằng tham số m vì các mã<br /> thành phần của mã tích là mã Hamming). Kết quả thu được sau hai lần lặp chạy trên kênh<br /> Gauss được thể hiện trên hình 3.<br /> Từ kết quả hình 3 cho thấy, chất lượng của mã tích càng được cải thiện khi độ dài từ<br /> mã càng lớn mặc dù tỷ lệ mã hóa tăng đáng kể. Ví dụ, ở tỷ lệ lỗi bít là 10-5, nếu m= 3 (2<br /> mã thành phần như nhau), tức là độ dài từ mã tích là n= 49, tỷ lệ mã hóa ~ 0,33, cần tỷ số<br /> Eb/N0 là 6dB. Còn với mã có m= 6, độ dài từ mã tích là n= 3969, tỷ lệ mã hóa ~0,82, để đạt<br /> được chất lượng tương đương chỉ cần tỷ số Eb/N0 khoảng 4,2 dB có nghĩa là đạt được độ<br /> lợi về Eb/N0 khoảng 1,8dB và về tỷ lệ mã hóa khoảng 2,5 lần. Tuy nhiên, ta dễ nhận thấy<br /> sự trả giá cho độ lợi tăng ích mã đạt được chính là độ phức tạp của thuật toán giải mã vì<br /> tham số này tỷ lệ thuận với độ dài từ mã. Đây chính là nguyên nhân dẫn đến việc mã tích<br /> hầu như chỉ được dừng lại ở nghiên cứu lý thuyết. Tuy nhiên, điều này hoàn toàn có thể<br /> được khắc phục bởi thành quả của kỹ thuật vi xử lý ở giai đoạn hiện nay cũng như trong<br /> tương lai, đặc biệt là khi sử dụng thuật toán đề xuất (ở đây đã có sự cải tiến đáng kể so với<br /> các thuật toán giải mã nguyên bản).<br /> Để đánh giá khách quan thuật toán giải mã mới được đề xuất, thực hiện so sánh chất<br /> lượng cũng như độ phức tạp của thuật toán giải mã này với thuật thuật được đánh giá cao<br /> đã từng được công bố như là giải mã MAP cho mã tích sử dụng thông tin giải mã trên mã<br /> đối ngẫu (MAP Decoder Using the Dual Code: MDUDC) của Hagenauer [6]. Hình 4 thể<br /> hiện kết quả mô phỏng khả năng giải mã của hai giải thuật DCAPC và MDUDC cho các<br /> mã tích với mã thành phần là mã Hamming.<br /> Chat luong cua giai ma doi ngau ma tich cua cac ma Hamming So sanh chat luong hai thuat toan giai ma doi ngau ma tich<br /> -1 -1<br /> 10 10<br /> <br /> -2<br /> -2 10<br /> 10<br /> <br /> -3<br /> -3 10<br /> 10<br /> -4<br /> 10<br /> -4<br /> 10<br /> BER<br /> <br /> <br /> <br /> <br /> BER<br /> <br /> <br /> <br /> <br /> -5<br /> 10<br /> -5<br /> 10 DCAPC(7,4)x(7,4)<br /> -6<br /> 10 DCAPC(15,11)x(15,11)<br /> -6<br /> DCAPC: m1=3, m2=3 DCAPC(31,26)x(31,26)<br /> 10 DCAPC: m1=4, m2=4 -7 DCAPC(63,57)x(63,57)<br /> DCAPC: m1=5, m2=5 10<br /> MDUDC(7,4)(7,4)<br /> -7 DCAPC: m1=6, m2=6<br /> 10 -8 MDUDC(15,11)(15,11)<br /> DCAPC: m1=3, m2=4 10<br /> MDUDC(31,26)(31,26)<br /> DCAPC: m1=4, m2=5<br /> -8 MDUDC(63,57)(63,57)<br /> 10 -9<br /> 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 10<br /> 1 1.5 2 2.5 3 3.5 4 4.5 5<br /> EbNo[dB] EbNo[dB]<br /> <br /> <br /> Hình 3. Chất lượng của mã tích gồm các Hình 4. So sánh chất lượng các thuật toán<br /> thành phần là mã Hamming. giải mã tích.<br /> Nhận xét, đánh giá kết quả mô phỏng. So với kết quả mô phỏng của Hagenauer [6],<br /> phẩm chất giải mã của hệ thống đang đề xuất kém hơn khoảng từ 0,2 dB (với = =<br /> = 4) đến 0,5 dB (với = = = 5, 6) ở xác suất lỗi bit 10 . Điều này có thể<br /> giải thích như sau, với thuật toán giải mã của Hagenauer loại bỏ giả thiết đồng xác suất<br /> của bít từ mã, dùng giá trị xác suất tiền nghiệm cho đầu vào giải mã nên cho phẩm chất<br /> giải mã tốt hơn. Tuy nhiên, điều này sẽ dẫn đến khối lượng tính toán trong thuật toán do<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 15<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> Hagenauer đề xuất quá lớn. Bên cạnh đó, thuật toán này sử dụng các hàm phi tuyến, đây<br /> cũng là lý do dẫn đến độ phức tạp rất cao của thuật toán này và vì vậy theo các công trình<br /> đã công bố [3], [6], thuật toán này chỉ dừng lại ở mức nghiên cứu lý thuyết, rất khó có thể<br /> áp dụng vào thực tế ngay cả khi chúng ta có những bộ vi xử lý có khả năng tính toán mạnh<br /> [7]. Đây cũng chính là điểm mạnh của thuật toán giải mã mới được đề xuất DCAPC. Với<br /> thuật toán này ta hoàn toàn có thể tính được độ phức tạp giải mã, kết quả tính toán này mở<br /> ra tính khả thi khi hiện thực hóa thuật toán bằng các thiết bị phần cứng. Bên cạnh đó, thuật<br /> toán đề xuất đưa ra được cơ sở lý thuyết là nền tảng cho việc nghiên cứu, đề xuất các thuật<br /> toán giải mã cải tiến có độ phức tạp thấp hơn, có tỷ lệ mã hóa cao hơn và rất có thể cho<br /> chất lượng giải mã tốt hơn.<br /> Để khẳng định cho khả năng giảm độ phức tạp của thuật toán mới đề xuất, chúng tôi<br /> thực hiện đánh giá chi tiết tham số này. Từ (5) dễ dàng xác định được, thuật toán DCAPC<br /> cần × × (2 × × 2 + 2) phép tính cộng và nhân cho giải mã các hàng và<br /> × × (2 × × 2 + 2) phép tính cộng và nhân cho giải mã các cột mã tích. Hay để<br /> giải mã một bít mã, thuật toán mới cần tổng cộng 2 × ( × 2 + × 2 + 2) phép tính<br /> với 2 × (( − 1) × 2 + ( − 1) × 2 ) phép nhân và 2 × (2 + 2 + 2) phép cộng.<br /> Nếu sử dụng cùng một mã khối để kiểm soát lỗi, với 2 lần lặp nên có số lượng tính toán<br /> cho một bít đầu ra xấp xỉ 8 lần DCA. Bảng 1 trình bày số lượng phép tính cần thiết cho<br /> mỗi lần giải mã lặp của thuật toán DACPC đề xuất.<br /> <br /> Bảng 1. Độ phức tạp của giải thuật đề xuất.<br /> Số phép tính nhân Số phép tính cộng<br /> Mã<br /> 2 (( − 1)2 + ( − 1)2 ) 2 (2 + 2 + 2)<br /> (7,4) × (7,4) 9408 1764<br /> (15, 11)(15, 11) 201600 15300<br /> (31, 26)(31, 26) 3690240 126852<br /> (63, 57)(63, 57) 62995968 1031940<br /> <br /> 5. KẾT LUẬN<br /> Trong nội dung bài báo đã đề xuất thuật toán giải mã mới cho mã tích DCAPC, dựa<br /> trên cơ sở sử dụng kỹ thuật giải mã mềm và giải mã đối ngẫu. Thuật toán này cho phép<br /> giảm độ phức tạp giải mã một cách đáng kể so với thuật toán giải mã tích nguyên bản, với<br /> sự trả giá về chất lượng cho phép (từ 0,2 dB đến 0,5 dB). Thuật toán mới đề xuất cho phép<br /> mở ra hướng mới về việc ứng dụng mã tích vào các hệ thống truyền tin số cũng như là cơ<br /> sở để đề xuất các cải tiến mới cho phép tăng chất lượng, tỷ lệ mã cũng như giảm độ phức<br /> tạp trong quá trình giải mã.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Todd K.Moon, Erros correction coding, John Wiley and Sons Inc., publication, 2005.<br /> [2]. LAndrew J. Viterbi, “Convolutional codes and their performance in communication<br /> systems,” IEEE Transactions on Communication Technology, COM- 19: 751- 772,<br /> 1971.<br /> [3]. L.R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for<br /> minimizing symbol error rate,” IEEE Transactions on Information Theory, vol. 20, pp.<br /> 284- 287, Mar. 1974<br /> [4]. Carlos R. P. Hartmann, Luther D . Rudolph, “An optimum symbol-by-symbol decoding<br /> rule for linear codes,” IEEE Transactions on Information Theory, vol. 22, pp. 514-<br /> 517, Sept. 1976.<br /> <br /> <br /> 16 P. X. Nghĩa, N. T. H. Nhung, “Giải mã tích bằng … mã đối ngẫu đảm bảo tính khả dụng.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> [5]. Nguyen Thi Hong Nhung, Pham Khac Hoan, Pham Xuan Nghia, Bui Huy Hai, “Dual<br /> Codes decoding Algorithm for high density parity check codes,” Asian Academic<br /> Research Journal of Multidisciplinary, vol. 5, pp. 114-124, May 2018.<br /> [6]. J. Hagenauer, E. Offer, and Lutz Papke, “Iterative decoding of binary block and<br /> convolutional codes,” IEEE Transactions on Information Theory, vol. 42, pp. 429-<br /> 445, 1996.<br /> [7]. P. Robertson, E. Villebrun, P. Hoeher, “A comparison of optimal and sub-optimal<br /> MAP decoding algorithms operating in the log domain,” Proceedings IEEE<br /> International Conference on Communications ICC '95, 2002.<br /> ABSTRACT<br /> PRODUCT CODES DECODER BY SOFT DECISION DECODING<br /> USING DUAL CODES TO ENSURE THE POSSIBILITY<br /> The product codes were first presented by Elias in 1954, consisting of two serial<br /> concatenated block codes with good error correction capability. However, the<br /> application as well as studies in order to improve the performance of product codes<br /> is rarely mentioned due to its fundamental disadvantage of serious complexity<br /> during decoding process. So far, thanks to the development of microprocessor<br /> technology, the above-mentioned disadvantage of the product code does not remain<br /> as a problem any more. With this article, the application of dual codes decoding<br /> algorithm and soft decision decoding for the component codes of product codes will<br /> be presented. This shoud help to significantly improve the complexity of the<br /> algorithm in comparison with previous publications, hence enhancing the<br /> application of product codes in digital communication systems, ensuring the<br /> possibility in comparison with previous suggestions with the acceptable loss in term<br /> of decoding performance (from 0.2 to 0.5dB).<br /> Keywords: Product codes; Hamming code; Dual codes decoding; Soft- decision decoding.<br /> <br /> Nhận bài ngày 11 tháng 8 năm 2018<br /> Hoàn thiện ngày 28 tháng 8 năm 2018<br /> Chấp nhận đăng ngày 11 tháng 10 năm 2018<br /> 1<br /> Địa chỉ: Học viện Kỹ thuật quân sự;<br /> 2<br /> Đại học Kinh tế kỹ thuật công nghiệp.<br /> *<br /> Email: nhungnh13@gmail.com.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 17<br />