Giải mã mềm mã Hamming dựa trên các mã đối ngẫu

Nghiên cứu khoa học công nghệ<br /> <br /> GIẢI MÃ MỀM MÃ HAMMING DỰA TRÊN CÁC MÃ ĐỐI NGẪU<br /> Nguyễn Thị Hồng Nhung1*, Phạm Xuân Nghĩa2, Vũ Thị Thắng3, Lê Tiến Cường4 <br /> Tóm tắt: Trong bài báo này, chúng tôi đề xuất thuật toán giải mã BPA (Belief<br /> Propagation Algorithm) cải tiến dựa trên tính chất đối ngẫu của mã khối tuyến tính.<br /> Thuật toán mới đề xuất thực hiện giải mã mềm với các ma trận kiểm tra tương<br /> đương ứng dụng cho mã Hamming, trong đó, các ma trận kiểm tra tương đương<br /> được xây dựng trên cơ sở sử dụng các từ mã đối ngẫu. Kết quả khảo sát cho thấy độ<br /> lợi của thuật toán giải mới tốt hơn từ 0.45 dB đến 0.5 dB so với thuật toán BPA<br /> truyền thống mà thời gian và độ phức tạp giải mã tăng không đáng kể.<br /> Từ khóa: Mã kênh, Giải mã mềm, Mã Hamming. <br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Mã hóa kênh đóng vai trò vô cùng quan trọng trong kỹ thuật truyền dẫn thông <br /> tin số, trong đó, mã khối là loại mã có khả năng sửa và phát hiện lỗi khá tốt đảm <br /> bảo  độ  chính  xác  cho  hệ  thống  truyền  tin.  Tuy  nhiên,  phần  lớn  các  họ  mã  khối <br /> trước đây còn tồn tại những mặt hạn chế đáng kể như đánh đổi chất lượng giải mã <br /> để giảm lượng tính toán và tăng tỷ lệ mã hóa hoặc để đạt chất lượng mong muốn <br /> lại phải tăng độ phức tạp tính toán cũng như giảm tỷ lệ mã hóa. <br /> Mã Hamming do Richard Hamming lần đầu tiên giới thiệu tại [1] là một loại mã  <br /> thuộc họ mã khối có thể sửa được 1 lỗi đơn hoặc phát hiện được các lỗi kép (bội <br /> 2). Với tính chất đơn giản của thuật toán mã hóa và giải mã, mã Hamming đã được <br /> ứng dụng khá rộng rãi trong các hệ thống truyền tin số với vai trò là mã phát hiện <br /> lỗi. Với mục đích sử dụng mã Hamming vừa có khả năng sửa lỗi, vừa có khả năng <br /> phát hiện lỗi, trong bài báo đề xuất thuật toán giải mã mềm cải tiến ứng dụng cho  <br /> loại mã này. <br /> Từ việc nghiên cứu thuật toán giải mã BPA [4] và tính chất đối ngẫu của mã sửa <br /> sai [2], [3], chúng tôi đưa ra ý tưởng xây dựng thuật toán giải mã mới cho mã khối <br /> tuyến tính trong đó có mã Hamming. Phần còn lại của bài báo được trình bày như <br /> sau: Mục 2 trình bày các cơ sở lý luận để xây dựng thuật toán giải mã mới, mục 3 <br /> của bài báo trình bày các bước của việc xây dựng thuật toán giải mã mới, mục 4 thực <br /> hiện khảo sát đánh giá chất lượng của thuật toán giải mã mới thông qua các kết quả <br /> mô phỏng trên kênh AWGN với các mã Hamming, cuối cùng là phần kết luận.   <br /> 2. CƠ SỞ LÝ LUẬN XÂY DỰNG THUẬT TOÁN GIẢI MÃ MỀM<br /> CẢI TIẾN CHO CÁC MÃ HAMMING<br /> 2.1. Phương pháp giải mã khối dựa trên các mã đối ngẫu<br /> Như  ta  đã  biết,  tính  chất  của  ma  trận  kiểm  tra  G   và  ma  trận  sinh  H   của  mã <br /> khối tuyến tính thể hiện như sau: <br /> G.HT  0. (1) <br /> Bên cạnh đó, tính chất đối ngẫu của mã khối tuyến tính được hiểu như sau: ma <br /> trận kiểm tra của mã gốc đóng vai trò là ma trận sinh của mã khối tuyến tính khác. <br /> Từ các tính chất nêu trên cho thấy có thể xây dựng các ma trận kiểm tra của một <br /> mã khối tuyến tính dựa trên các từ mã trong bộ mã đối ngẫu. Trên cơ sở này hình <br /> thành nên phương pháp giải mã khối sử dụng mã đối ngẫu trình bày trong [2] và <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016                               27<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> [3].  Phương  pháp  giải  mã  này  được  mô  tả  như  sau:  khi  truyền  từ  mã  bất  kỳ <br /> c  (c1, c2 ,...., cn )  của mã tuyến tính  C(n, k ) qua kênh, dưới tác động của nhiễu và <br /> tạp âm ta nhận được từ mã  ˆc'  (cˆ '1, cˆ '2 ,...., cˆ 'n ) , quá trình giải mã ở phía thu với <br /> từ mã đầu vào mềm  ˆc' , sử dụng các từ mã đối ngẫu của  mã đối ngẫu  C '(n, r )  ta <br /> tính ra các bit nhận  c (   1  n ) với xác suất cao nhất (trong đó,  n  là chiều dài <br />  <br /> từ mã,  k  là chiều dài từ tin,  r   n  k     2r  1   k  là số lượng các bít kiểm tra). <br /> Ký hiệu    exp[2 / p ]  là biểu diễn phức của nghiệm nguyên thủy  p ;  i  1  <br /> nếu    i  và  i  0  với các trường hợp khác;    là đơn vị ảo;  Pr(x ) là xác suất <br /> của  x  và  Pr(x | y )  là xác suất có điều kiện của  x  cho bởi  y;   c 't '' i  là bít thứ  i  của <br /> từ mã thứ  t ''  trong mã đối ngẫu;  t, t '  là số phần tử trong trường  GF (p)  và có giá <br /> trị  là  các  số  nguyên  0,1,..., p  1.   Nếu  s   thuộc  trường  GF (p) ta  có  c  s   khi <br /> A (s ) đạt cực đại với: <br />  <br /> r<br /> p 1 p<br />  n p 1 <br /> A ( s )     st     t '( c 't '' i t i ) Pr(cˆ 'i | t ')  . (2)<br /> t 0 t ''1  i 1 t ' 0 <br /> Kết  quả  chứng  minh  trong  [2]  khẳng  định  đối  với  mã  nhị  phân  ( p  2 ),  điều <br /> kiện quyết định cứng (ở lần lặp cuối cùng), bít  c  0  khi:  <br /> c 't '' i  i<br /> 2r n<br />  1  i <br />   <br /> t ''1 i 1  1  i <br /> 0 (3) <br /> <br /> Pr(cˆ 'i |1)<br /> và  c  1   nếu  (3)  xảy  ra  theo  chiều  ngược  lại,  ở  đây:  i  ;   là  phép <br /> Pr(cˆ 'i | 0)<br /> cộng modulo 2.    <br /> Để làm rõ tính chất trên ta xét mã Hamming (7,4) với mã nhận được ký hiệu là <br /> ˆc'  (cˆ '1, cˆ '2 ,...., cˆ '7 ) , theo (3) điều kiện quyết định bit mã  c1  là: <br /> ct' '' i 1i<br /> 8 7<br />  1  i <br /> c1  0 khi     0. (4) <br /> t ''1 i 1  1  i <br /> <br /> Ta có ma trận kiểm tra  H  của mã Hamming (7, 4) cũng là ma trận sinh của mã <br /> đối ngẫu: <br />  <br /> 1 1 1 0 1 0 0  (a )<br /> H = 0 1 1 1 0 1 0  (b) .  <br /> 0 0 1 1 1 0 1 (c)<br /> Như vậy, các từ mã của bộ mã đối ngẫu  C '  (ở đây ký hiệu a, b, c là các từ mã <br /> đối ngẫu) là: <br /> <br />  <br /> <br /> 28     N. T. H. Nhung, P. X. Nghĩa, …, “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> c1  c 2  c3  c 4  c5  c 6  c 7<br /> 0  0  0  0  0  0  0<br /> 1  1  1  0  1  0  0   (a)<br /> 0  1  1  1  0  1  0   (b)<br /> C'  : 1  0  0  1  1  1  0   (a  b) . (5)<br /> 0  0  1  1  1  0  1   (c)<br /> 1  1  0  1  0  0  1   (a  c)<br /> 0  1  0  0  1  1  1   (b  c)<br /> 1  0  1  0  0  1  1   (a  b  c)<br /> Đặt  i  (1  i ) / (1  i )  điều kiện quyết định đối với bít  c1  là: <br /> c1  0 khi 1   2 3 5  1 2 3  4 6   4 5 6  13  4 5 7 <br /> (6)<br />  2  4 7   1 2 5 6 7  3 6 7  0;<br /> c1  1  khi (6) xảy ra theo chiều ngược lại. <br />  <br /> Như vậy, đến đây ta có thể nhận xét rằng: Đối với mã khối tuyến tính, mỗi bít <br /> mã trong các từ mã đối ngẫu đều chứa các thông tin về các bít mã trong các từ mã <br /> gốc [2]. Bên cạnh đó, từ các từ mã đối ngẫu ta có thể thành lập các ma trận kiểm <br /> tra khác nhau. Những nhận định trên đây là cơ sở để xây dựng thuật toán giải mã <br /> mới được trình bày ở nội dung tiếp theo của bài báo.  <br /> 2.2. Thuật toán giải mã BPA<br /> 2.2.1. Quan hệ giữa ma trận kiểm tra và đồ hình Tanner<br />   0 0 0 1 1 1 1  <br /> H = 0 1 1 0 0 1 1  <br /> 1 0 1 0 1 0 1<br /> <br /> c1 c2   c3   c4 c5 C c6   c7<br /> 1 <br /> <br /> (n =7)<br /> <br /> <br /> <br /> <br />    f1   f2         f3   (r =3)<br />  <br /> Hình 1. Ma trận kiểm tra H  và đồ thị Tanner tương ứng<br /> của mã Hamming (7, 4).  <br /> Mã khối tuyến tính nói chung, mã Hamming nói riêng được giải mã nhờ việc sử <br /> dụng  ma  trận  kiểm  tra  H   có  kích  thước  r  n .  Hiện  nay,  một  trong  những  cách <br /> được coi là hiệu quả nhất biểu diễn mã khối chính là thông qua đồ hình song biên <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016                               29<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> Tanner [5], đồ hình này có quan hệ chặt chẽ với ma trận kiểm tra của bộ mã, điều <br /> này được minh chứng qua ví dụ thể hiện trên hình 1. <br /> Trên đồ hình này có hai hàng nút gồm các nút mã  c  c1 , c2 ,... cn  và các nút kiểm <br /> tra  f  f1 , f 2 ,... f r .  Nút  kiểm  tra  f j   nối  với  nút  ci   khi  và  chỉ  khi  H ( j , i )  1  <br /> ( H ( j , i )  là phần tử ở vị trí hàng  j ,  cột  i  của ma trận kiểm tra  H ). Bộ giải mã sử <br /> dụng thuật toán giải mã lặp như thuật toán lan truyền niềm tin BPA. Khi đó, thông <br /> tin sẽ được truyền qua lại giữa các nút bít và các nút kiểm tra khi có kết nối trên đồ <br /> thị Tanner. Nội dung tiếp theo của bài báo đi sâu phân tích bản chất của thuật toán <br /> giải mã này. <br /> 2.2.2. Thuật toán giải mã BPA cho mã Hamming<br /> Xét mã Hamming  ( n, k ) , đầu vào bộ giải mã BPA là tỷ lệ ước lượng theo hàm <br /> log (Log Likelihood Ratio – LLR): <br /> ˆ)<br /> Pr(cˆ 'i 0|c'<br /> L ( qij )  L (cˆ 'i )  log . (7) <br /> ˆ)<br /> Pr(cˆ 'i 1|c'<br />  <br /> Ở đây,  cˆ '  là tập các symbol nhận từ kênh.  Pr(cˆ 'i  b | c' ˆ )  là xác suất điều kiện <br /> với  b  0,1;  Trước khi đi sâu vào phân tích các thuật toán chúng ta cùng định nghĩa <br /> một số ký hiệu: <br /> ci  : bit thứ  i của từ mã  n  bit. <br /> R j : tập hợp các cột ở đó  H (i, j )  1  với  j  là thứ tự hàng. <br /> Ci  : tập hợp các hàng ở đó  H ( j , i )  1  với  i  là thứ tự cột. <br /> R j ~  i : tập  R j  trừ cột thứ  i . <br /> Ci ~  j : tập  Ci  trừ hàng thứ  j . <br /> p ji  b   : Pr [nút kiểm tra  f j  thỏa mãn |  cˆ 'i  b & qij (b)  R j ~  i ].  <br /> <br /> qij  b  :  Pr[ cˆ 'i  b | p ji (b)  Ci ~  j , ci ].  <br /> Thuật toán BPA là thuật toán giải mã lặp có hai bước chính:<br /> Bước 1: Cập nhật bản tin cho tất cả các nút kiểm tra  j   1, 2, ,  r và gửi bản <br /> tin  L( p ji )  từ nút kiểm tra tới các nút bit nối với nó. <br /> Bước 2:  Cập  nhật  bản  tin  cho  tất  cả  các  nút  bit  i   1, 2, ,  n   và  gửi  bản  tin <br /> L (qij )  từ các nút bit tới nút các kiểm tra nối với nó.  <br /> <br /> Đầu ra của bộ giải mã là giá trị LLR của các bit mã được sử dụng để quyết định <br /> thành từ mã thăm dò  c  c1 , c2 ,..., cn . Nếu syndrome  s  thỏa mãn điều kiện: <br /> T<br /> s  c.H  [0, 0, ..., 0] (8)<br /> thì dừng lặp và đưa ra từ mã hợp lệ  c . Nếu điều kiện (8) không thỏa mãn thì quá <br /> trình được thực hiện lại cho đến khi đạt số lần lặp cực đại   max   thì dừng và đưa ra <br /> từ mã tại lần lặp cuối. <br />  <br /> <br /> 30     N. T. H. Nhung, P. X. Nghĩa, …, “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> Thuật toán BPA và các phiên bản cải tiến của thuật toán này được ứng dụng cho <br /> mã mật độ kiểm tra thấp LDPC (là mã khối tuyến tính có ma trận H là một ma trận <br /> thưa với  số lượng các phần tử "1" trên mỗi hàng và mỗi cột rất ít) mang lại chất <br /> lượng giải mã rất tốt. Với mục đích ứng dụng thuật toán giải mã BPA cho các mã <br /> khối tuyến tính khác, trong đó có mã Hamming với ma trận kiểm  tra H không đảm <br /> bảo tính thưa, khi đó tồn tại nhiều chu kỳ ngắn trong nó, điều này làm ảnh hưởng <br /> lớn tới chất lượng giải mã (các chu kỳ ngắn tạo ra những tập bẫy (trapping sets) là <br /> nguyên nhân chính dẫn đến hiệu ứng sàn “error floor”), vì vậy, để ứng dụng thuật <br /> toán BPA cho mã Hamming đòi hỏi phải có những cải tiến nhất định mới đạt được <br /> mục đích đặt ra. Đây cũng là nội dung sẽ được trình bày trong nội dung tiếp theo <br /> của bài báo.  <br /> 3. ĐỀ XUẤT THUẬT TOÁN GIẢI MÃ BPA CẢI TIẾN<br /> DỰA TRÊN MÃ ĐỐI NGẪU<br /> Ở  mục  này  trình  bày  thuật  toán  BPA  cải  tiến  bằng  việc  sử  dụng  các  ma  trận <br /> kiểm tra tương đương, các ma trận này được xây dựng trên cơ sở sử dụng các từ <br /> mã  đối  ngẫu  BPA  –  DCS  (Belief  Propagation  Algorithm  base  on  dual  codes).  Ở <br /> đây, thay vì sử dụng một ma trận kiểm tra với số lần lặp tối đa   max  sau đó mới sử <br /> dụng ma trận kiểm tra tương đương mới [6], thuật toán cải tiến sẽ sử dụng tại mỗi <br /> vòng lặp một ma trận kiểm tra tương đương khác nhau để giải mã, bằng cách thực <br /> hiện như trên sẽ làm cho thông tin ngoại lai ở vòng lặp trước đưa tới vòng lặp sau  <br /> trong  quá  trình  giải  mã  luôn  được  cải  thiện,  điều  này  đã  khắc  phục  được  vấn  đề <br /> “vòng kín ngắn” đã nêu ở trên.  <br /> 3.1. Xây dựng các ma trận kiểm tra tương đương<br /> Một cách tổng quát, với mã  (n, k )   sẽ tồn tại  2r   từ mã đối ngẫu, tương ứng  C 2rr  <br /> ma trận kiểm tra tương đương  H e  để sử dụng cho quá trình giải mã. Các ma trận <br /> kiểm tra tương đương  H e  được xây dựng dựa trên các từ mã đối ngẫu. Ví dụ với <br /> mã Hamming (7,4), các ma trận kiểm tra tương đương sẽ được xây dựng như sau: <br /> a   ab <br /> H =  b           →             H e =  b  c  .<br />  <br />  c   a  b  c <br />  <br /> Với cách thực hiện như trên, ma trận kiểm tra tương đương He được hình thành <br /> từ các từ mã đối ngẫu khác so với ma trận H, bằng cách đó ta có thể xây dựng số <br /> lượng ma trận kiểm tra tương đương khá lớn (phụ thuộc vào số từ mã đối ngẫu  2r ) <br /> phục vụ cho mỗi vòng giải mã lặp. <br /> 3.2. Xây dựng thuật toán giải mã mềm dựa trên các ma trận kiểm tra tương<br /> đương<br /> Khởi tạo: Tính LLR  L(ci )  cho tất cả các nút bit  i  1,2 ,...,n  và đặt: <br /> ˆ)<br /> Pr(cˆ 'i 0|c'<br /> L ( qij )  L(cˆ 'i )  log<br /> (1)<br />  (9)<br /> ˆ)<br /> Pr(cˆ 'i 1|c'<br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016                               31<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> tại vị trí  ( j , i )  thỏa mãn  H ji  1  cho lần lặp thứ nhất. <br /> Giai đoạn 1:<br /> Bước 1:  Đối  với  tất  cả  các  nút  kiểm  tra  f j ( j  1, 2,..., m) ,  tính  toán  L( γ ) ( p ji )  <br /> ứng với các vị trí  ( j , i )  có  H ji  1  tại lần lặp thứ    1  theo phương trình sau:<br />    <br />  i'R ~ i <br /> L(γ ) (p ji )    sign L(γ ) (qi'j )   .φ   φ  L (γ )<br /> <br /> (qi'j )  ,<br />  (10)<br />  j   i'R j ~ i <br />  ex  1<br /> với  φ(x)   logtanh (x/ 2 )  log x  .<br />  e 1<br /> Sau đó gửi bản tin  L( p ji )  từ nút kiểm tra tới các nút bit nối với nó. <br /> Bước 2: Tính toán  L(qij )  đối với tất cả các nút tin  cˆ 'i (i  1, 2,..., n)  tại các vị trí <br /> ( j , i )  có  H ji  1  theo phương trình sau: <br /> L(qij )  L(cˆ 'i )   L(γ ) (p j'i ). (11)<br /> j'Ci ~ j<br /> <br /> Tiếp đó gửi bản tin  L(qij )   từ các nút bit tới nút các kiểm tra nối với nó. Đầu ra <br /> bộ giải mã là giá trị LLR của các bit mã  ci (i  1, 2,..., n)  tại lần lặp thứ nhất: <br /> <br /> Li(γ )  L(cˆ 'i )   L(γ ) (p ji ). (12)<br /> jCi<br /> <br /> Khi đó từ mã thăm dò  c ( ) = (c1( ) , c2( ) ,..., cn( ) )  tại lần lặp thứ nhất được quyết <br /> định là: <br /> <br /> ( )<br /> 0, sign(Li (γ ) )  1<br /> ci 1,2,...,n<br />  (γ ) (13)<br /> 1, sign(Li )  1<br /> và kiểm tra điều kiện:  <br /> c .H T  [0, 0,..., 0], (14)<br /> nếu thỏa mãn thì đưa ra từ mã  c , nếu không thỏa mãn (14) thì chuyển sang giai <br /> đoạn 2. <br /> Giai đoạn 2: Ở giai đoạn 1, nếu (14) không thỏa mãn, thực hiện thay thế các <br /> hàng của ma trận kiểm tra bằng cách lấy hàng đó cộng với hàng tiếp theo ta nhận <br /> được  ma  trận  kiểm  tra  tương  đương  H e và  thực  hiện  lại  giai  đoạn  1  với  lần  lặp <br />   2  sử dụng ma trận kiểm tra tương đương  H e . Nếu thấy (14) thỏa mãn thì dừng <br /> và đưa ra từ mã. Nếu không, thực hiện lại giai đoạn 2, xây dựng ma trận kiểm tra <br /> tương đương mới và tiếp tục giải mã ứng với  H e  mới đó, … Tại mỗi lần lặp luôn <br /> kiểm  tra  điều  kiện  (14),  nếu  thỏa  mãn  thì  đưa  ra  từ  mã,  nếu  không  tiếp  tục  thực <br /> hiện giải mã đến khi tìm được từ mã hợp lệ hoặc hết   max lần lặp. <br />  <br /> <br /> 32     N. T. H. Nhung, P. X. Nghĩa, …, “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> 4. KẾT QUẢ MÔ PHỎNG VÀ THẢO LUẬN<br /> 4.1. Sơ đồ hệ thống<br /> Để đánh giá chất lượng của thuật toán giải mã mới được xây dựng ta sử dụng sơ <br /> đồ mô phỏng thể hiện trên hình 2. <br /> Xét  mô  hình  hệ  thống  sử  dụng  mã  Hamming  mô  tả  trên  hình  2.  Các  bít  tin <br /> u  u1 , u2 ,... uk  được mã hóa Hamming  ( n, k )  với tỷ lệ  R  k / n (trong đó,  n  là độ <br /> dài từ mã,  k  là chiều dài thông tin) thành từ mã  c  c1 , c2 ,... cn , sau đó được điều <br /> chế và truyền qua kênh. Tại đầu thu, khi nhận được từ mã  cˆ ' , tiến hành giải mã và <br /> đưa ra từ mã  c . <br />   c      <br /> <br /> <br /> cˆ '    c  <br /> u  Mã hóa <br /> Điều chế <br /> Kênh  Giải điều  Giải mã <br />     Hamming <br />   truyền  chế  Hamming <br /> u (1, 2...k ) c(1,2,...n )   cˆ '(1,2...n )  <br />  <br />  <br /> Hình 2. Mô hình hệ thống sử dụng mã Hamming. <br /> 4.2. Kết quả mô phỏng<br /> Xét các mã Hamming (7, 4), (15, 11), (31, 26), (63, 57) giả thiết điều chế BPSK <br /> lý tưởng và kênh truyền AWGN. Thực hiện mô phỏng đánh giá chất lượng giải mã <br /> của thuật toán giải mã mới BPA – DCS với các thuật toán giải mã cứng, thuật toán <br /> BPA, cho kết quả trên hình 3, hình 4, hình 5 và hình 6. <br /> 0<br /> BER Hamming (7,4) tren kenh Gauss BER Hamming (15,11) tren kenh Gauss<br /> 0<br /> 10 10<br /> giai ma cung giai ma cung<br /> BPA BPA<br /> -1<br /> -1 BPA-DCS 10 BPA-DCS<br /> 10<br /> <br /> -2<br /> 10<br /> -2<br /> 10<br /> BER<br /> <br /> <br /> <br /> <br /> BER<br /> <br /> <br /> <br /> <br /> -3<br /> 10<br /> -3<br /> 10<br /> -4<br /> 10<br /> <br /> -4<br /> 10 -5<br /> 10<br /> <br /> <br /> -5 -6<br /> 10 10<br /> 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8<br /> EbN0[dB] EbN0[dB]<br /> <br /> <br /> Hình 3. So sánh chất lượng của mã Hình 4. So sánh chất lượng của mã<br /> Hamming (7, 4) giữa các thuật toán. Hamming (15, 11) giữa các thuật toán.<br /> <br /> Từ kết quả mô phỏng ta thấy thuật toán giải mã Hamming dựa vào các ma trận <br /> kiểm tra tương đương mới ứng dụng cho các mã Hamming có độ dài từ mã  n  7,  <br /> tại tỷ lệ lỗi bít  BER   105  cho phép nâng cao chất lượng khoảng 0.9 dB đến 1.05 <br /> dB so với thuật toán giải mã cứng, 0.45 dB đến 0.5 dB so với thuật toán BPA khi <br /> thực  hiện  cùng  số  vòng  lặp.  Độ  phức  tạp  thuật  toán  tăng  không  đáng  kể  so  với <br /> thuật toán BPA. Để đạt được kết quả này, dù cải tiến rồi nhưng thuật toán BPA-<br /> DCS vẫn phải trả giá về mặt thời gian. Tuy nhiên, khi chiều dài từ mã tăng, thời <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016                               33<br />  Kỹ thuật điều khiển & Điện tử<br /> <br /> gian  giải  mã  của  thuật  toán  BPA  –  DCS  rút  ngắn  khoảng  cách  so  với  thuật  toán <br /> BPA. Điều này có thể giải thích như sau: <br /> BER Hamming (31,26) tren kenh Gauss BER Hamming (63, 57) tren kenh Gauss<br /> 0 0<br /> 10 10<br /> giai ma cung giai ma cung<br /> -1 BPA -1 BPA<br /> 10 10<br /> BPA-DCS BPA-DCS<br /> <br /> -2 -2<br /> 10 10<br /> <br /> <br /> -3 -3<br /> 10 10<br /> <br /> <br /> <br /> <br /> BER<br /> BER<br /> <br /> <br /> <br /> <br /> -4 -4<br /> 10 10<br /> <br /> <br /> -5 -5<br /> 10 10<br /> <br /> <br /> -6 -6<br /> 10 10<br /> <br /> <br /> -7 -7<br /> 10 10<br /> 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8<br /> EbN0[dB] EbN0[dB]<br /> <br /> <br /> Hình 5. So sánh chất lượng của mã Hình 6. So sánh chất lượng của mã<br /> Hamming (31, 26) giữa các thuật toán. Hamming (63, 57) giữa các thuật toán.<br />  <br /> Bảng 1. So sánh thời gian trung bình xử lý một từ mã giữa hai thuật toán giải mã<br /> BPA và BPA - DCS với các bộ mã Hamming (7, 4), (15, 11), (31, 26), (63, 57).<br /> <br /> Bộ mã BPA BPA - DCS Tỷ lệ thời gian của thuật<br /> toán BPA –DCS so với BPA<br /> Hamming (7, 4)  0,4453 ms  1,1297 ms  253,69 % <br /> Hamming (15, 11)  0,8540 ms  2,0961 ms  245,445 % <br /> Hamming (31, 26)  2,8901 ms  6,8318 ms  236,386 % <br /> Hamming (63, 57)  15,4322 ms  33,101 ms  214,493 % <br /> Tại mỗi vòng lặp thuật toán BPA – DCS chỉ thêm phép tính cộng modulo giữa <br /> các hàng. Mặt khác, thuật toán mới sử dụng nhiều ma trận kiểm tra tương đương <br /> nên thông tin kiểm tra các bit tin tích lũy được nhiều hơn, thời gian hội tụ thông tin <br /> kiểm  tra  theo  điều  kiện  (14)  nhanh  hơn  khi  chiều  dài  từ  mã  tăng  nên  chất  lượng <br /> giải mã tốt hơn, và thời gian giải mã với các mã càng dài càng rút ngắn về tỷ lệ <br /> thời gian so với BPA. Bảng 1 là kết quả so sánh thời gian giải mã trung bình cho <br /> một từ mã giữa thuật toán giải mã BPA và thuật toán giải mã  BPA - DCS của các <br /> mã Hamming (7, 4), (15, 11), (31, 26), (63, 57) được thực hiện trên cùng một máy <br /> tính cũng cho kết quả phù hợp với phân tích. <br /> 5. KẾT LUẬN<br /> Từ  đặc điểm của thuật toán  giải mã  mềm  BPA và  tính chất  đối ngẫu  của  mã <br /> sửa  sai,  bài  báo  đã  đưa  ra  thuật  toán  cải  tiến  mới  dựa  vào  các  ma  trận  kiểm  tra <br /> tương đương nhằm cải thiện BER đối với các mã Hamming có chiều dài lớn hơn 7. <br /> Chất lượng thuật toán giải mã mới tăng 0.9 dB đến 1.05 dB so với thuật toán giải <br /> mã cứng, so với thuật toán BPA cải thiện 0.45 dB đến 0.5 dB. Độ chênh lệch về <br /> thời gian giải mã so với BPA giảm dần khi chiều dài từ mã tăng trong khi độ phức <br /> tạp và mức độ tính toán không tăng đáng kể. <br />  <br /> <br /> 34     N. T. H. Nhung, P. X. Nghĩa, …, “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> TÀI LIỆU THAM KHẢO<br /> [1]. Hamming,R.W.,” Error detecting and error correcting codes”, Bell System Tech. <br /> J. 29 (1950) 147–160. <br /> [2].  Carlos R .P . Hartmann, Luther D . Rudolph, " An Optimum Symbol-by Symbol<br /> decoding rule for linear codes", Electrical Engineering and Computer Science <br /> Technical Reports, Paper 8, September 1975. <br /> [3].  H, Greenberger, " An iterative algorithm for decoding block codes transmitted<br /> over a memoryless channel",  DSN  progress  report  42-47,  July  and  August <br /> 1978. <br /> [4].  M. P. C. Fossorier, M.Mihaljevic, and H. Imai, “Reduced complexity iterative<br /> decoding of low density parity check codes based on belief propagation”, <br /> IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May 1999. <br /> [5].  R.  Tanner.  "A recursive approach to low complexity codes",  IEEE <br /> Transactions on Information Theory, IT-27(5):533--547, September 1981. <br /> [6].  Nguyen  Tung  Hung,  “A new decoding algorithm based on equivalent parity<br /> check matrix for LDPC codes”,  REV  Journall  on  Electronics  and <br /> Communications, Vol.3, No. 1-2, Jannuary – June 2013, pp.73-76. <br /> ABSTRACT<br /> SOFT- DECISION DECODING OF HAMMING CODE  <br /> BASED ON DUAL CODES <br /> In this article, the BPA which is improved based on the duality of linear<br /> block codes is proposed. The new algorithm proposed soft decision decoding<br /> with equivalent parity check matrixs applied for Hamming codes, in which<br /> the equivalent parity check matrixs are developed using dual codes. It is<br /> shown that the gain of the new algorithm is 0,45 dB to 0,5 dB better<br /> compared to the traditional BPA whereas the decoding time and complexity<br /> faces a negligible increase.<br /> Keywords: Channel codes, Soft- decision decoding, Hamming code.<br /> <br /> Nhận bài ngày 29 tháng 6 năm 2016<br /> Hoàn thiện ngày 03 tháng 11 năm 2016<br /> Chấp nhận đăng ngày 14 tháng 12 năm 2016<br /> <br /> Địa chỉ: 1 Đại học Kinh tế Kỹ thuật Công nghiệp; <br />                   2 Học viện Kỹ thuật quân sự; <br />     3 Đại học Sư phạm Kỹ thuật Nam Định; <br />       4<br />  Trung tâm di động, Tổng Công ty mạng lưới Viettel. <br /> *<br />                     Email: nhungnh13@gmail.com  <br />  <br /> <br /> <br /> <br /> <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016                               35<br />