Giải mã mềm mã hamming dựa trên các mã đối ngẫu - Nguyễn Thị Hồng Nhung

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