Mở rộng khả năng sửa lỗi của mã Reed-Solomon sử dụng chuẩn syndrome

Nghiên cứu khoa học công nghệ<br /> <br /> MỞ RỘNG KHẢ NĂNG SỬA LỖI CỦA MÃ<br /> REED-SOLOMON SỬ DỤNG CHUẨN SYNDROME<br /> PHẠM KHẮC HOAN*, VŨ SƠN HÀ**, NGUYỄN THỊ THU NGA***<br /> Tóm tắt: Bài báo nghiên cứu giải mã thế mã Reed-Solomon trên cơ sở phân<br /> loại dịch vòng vector lỗi theo chuẩn syndrome, tham số đặc trưng cho cấu trúc<br /> đại số của mã. Với mã Reed-Solomon (RS), các vector lỗi sẽ được chia thành các<br /> A-orbit. Nhờ phân hoạch các modul lỗi thành các tập con tương đương không<br /> giao nhau nên mã RS có thể đồng thời sửa được lỗi modul và lỗi chùm.<br /> Từ khóa: Syndrome, Mã Reed-Solomon, Giải mã thế, Chuẩn syndrome.<br /> 1. ĐẶT VẤN ĐỀ<br /> Hiện nay mã kênh được ứng dụng rộng rãi trong các hệ thống truyền, lưu trữ và xử lý<br /> thông tin để phát hiện và sửa lỗi. Trong đó, một ứng dụng điển hình khi mã hóa thông tin<br /> có chiều dài lớn là mã Reed-Solomon. Tuy nhiên, các phương pháp đại số giải mã mã<br /> Reed-Solomon rất phức tạp. Khi tăng chiều dài mã và khoảng cách mã thì độ phức tạp giải<br /> mã tăng lên theo hàm mũ đồng thời thiếu phương pháp toán học tổng quát để giải phương<br /> trình bậc cao trong trường Galoa [1, 2, 3]. Phương pháp chuẩn syndrome được V. K.<br /> Konopelko đề xuất trên cơ sở phân loại dịch vòng vector lỗi theo tham số mới được tính<br /> dựa trên cấu trúc đại số của mã - chuẩn syndrome. Dựa trên chuẩn syndrome có thể phân<br /> chia các vector lỗi thành các lớp con không giao nhau, vì vậy có thể tìm được vector lỗi<br /> dựa trên các phép thế mà không yêu cầu giải phương trình khóa và cho phép giảm độ phức<br /> tạp của các thiết bị giải mã. Đặc biệt khi sử dụng phương pháp thế dựa trên chuẩn<br /> syndrome có thể sửa được đồng thời lỗi modul và lỗi chùm vì chuẩn syndrome của các lớp<br /> lỗi này khác nhau. Đây là điểm khác biệt căn bản với các phương pháp giải mã truyền<br /> thống, vì nếu chỉ dựa trên syndrome không thể phân biệt được các dạng lỗi này. Phần còn<br /> lại của bài báo được tổ chức như sau. Trong phần 2 trình bày phương pháp giải mã Reed-<br /> Solomon dựa trên chuẩn syndrome, phần 3 nghiên cứu vấn đề mở rộng khả năng sửa lỗi<br /> của mã Reed-Solomon và phần 4 trình bày các đánh giá, phân tích.<br /> 2. PHƯƠNG PHÁP VÀ THIẾT BỊ GIẢI MÃ RS DỰA TRÊN CHUẨN SYNDROME<br /> <br /> Với mã RS có khoảng cách mã δ, ma trận kiểm tra có dạng:<br /> 1  b  2b  3b ...  ( n1)b <br />  <br /> I  b 1  2( b1)  3( b 1)<br /> ...  ( n 1)( b 1)<br />  (1)<br /> H  <br /> ... <br /> I  b   2  2 ( b  2 )  3 ( b   2 )<br /> ...  ( n 1)( b   2 ) <br /> <br /> <br /> Khi đó syndrome của vector lỗi e có   1 thành phần trong trường GF(qm),<br /> S (e )  ( s1 , s2 ,..., s 1 ) . Chuẩn syndrome (norm) Nij chứa C 2  1 thành phần được tính<br /> theo công thức sau [4, 5]:<br /> ( b  i  1 ) / h ij<br /> S j<br /> N ij  ( b  j  1 ) / h ij<br /> S (2)<br /> i<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 103<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> Trong đó hij là ước số chung lớn nhất của i và j<br /> Nij = ∞ nếu Si = 0 và Sj ≠ 0<br /> Nij không xác định nếu Si = Sj = 0<br /> Ví dụ, với mã RS có khoảng cách cấu trúc δ = 5, b = 1 chuẩn (norm) syndrome có 6<br /> thành phần:<br /> S2 S3 S4<br /> N 12  , N 13  , N 14 <br /> S 12 S 13 S 14 (3)<br /> 3<br /> S3 S S<br /> N 23  3<br /> , N 24  42 , N 34  4<br /> 4<br /> S2 S2 S 3<br /> <br /> Các tính chất cơ bản của chuẩn syndrome đối với mã BCH và mã Reed-Solomon<br /> tương tự nhau, với mã Reed-Solomon cần chú ý một số khác biệt sau:<br /> Số lượng vector lỗi lớn hơn nhiều, vì vậy cần phân chia chúng một cách hiệu quả hơn<br /> thành các A-orbit, tập hợp các vector bao gồm phép thế dịch vòng và phép nhân f  với<br /> phần tử  tùy ý của trường Galoa. Trên hình 1 tminh họa các A-orbit của mã RS dài 7<br /> trong trường GF(23), (trường hợp riêng  = α).<br /> <br /> f<br /> e<br /> f<br /> 6<br />  (e )  (e )<br /> <br /> e  6e<br />  2 (e )<br />  6 (e )  (e )  6 ( 6e )<br />  ( 6e )<br /> <br /> <br />  2 (e ) f  2 ( 6e )<br /> Hình 1. Các A-orbit của mã Reed-Solomon dài 7.<br /> Với mã RS có b = 1, syndrome S(e) = (s1, s2, …, sδ-1) ta có<br /> S ( f  ( e ))  (  s 1 ,  s 2 ,  s 3 , ...,  s   1 )   S ( e ).<br /> Định lý: Cho mã RS có ma trận kiểm tra (1), với chuẩn syndrome:<br /> N ( S ( e ))  ( N 1 2 , N 1 3 , ..., N (   2 )(   1 ) ). Khi đó [5]:<br /> N ( S (  e ))  ( N 12 , N 13 , ..., N (  2 )(   1 ) ),<br /> ( j  i ) / h ij (4)<br /> với N ij  N ij /  , 1  i  j    1.<br /> <br /> Vì vậy, biến đổi của các σ-orbit bên trong A-orbit dưới tác động của tự đồng cấu f <br /> dẫn đến biến đổi norm của các σ-orbit theo công thức (4). Quá trình giải mã theo phương<br /> pháp chuẩn syndrome được thực hiện thông qua các A-orbit. Trong bộ nhớ sẽ lưu vector<br /> sinh của mỗi một σ-orbit bên trong một A-orbit, syndrome và norm của nó. Khi giải mã<br /> thực hiện so sánh norm với giá trị trong bộ nhớ, nếu chúng không trùng nhau, thực hiện<br /> <br /> <br /> 104 P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng …sử dụng chuẩn Syndrome.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> biến đổi norm theo công thức (4) (nhân vector lỗi với γ) và thực hiện lặp lại cho đến khi<br /> norm trùng với giá trị trong bộ nhớ. Chú ý rằng, các thành phần của chuẩn syndrome phụ<br /> thuộc nhau vì vậy khi s1 ≠ 0 để giảm độ phức tạp có thể xác định các thành phần norm<br /> thông qua δ-2 thành phần norm đầu tiên.<br /> Mã Reed-Solomon trên trường GF(2m) có thể ánh xạ thành mã nhị phân, biểu diễn mỗi<br /> tọa độ của từ mã bằng một vector m bit. Khi đó ma trận biến đổi tuyến tính f  với γ = αi<br /> <br />  <br /> là ma trận hi   i  i 1  i 2 ...  i  m 1 .<br /> <br /> Xét mã RS gốc sửa t lỗi trong trường GF(2m) với chiều dài n = 2m-1 có thể sửa t lỗi,<br /> ma trận kiểm tra có dạng:<br /> 1 1 1 ... 1 <br />  <br />  1   2 ...  n 1  (5)<br /> H<br /> ... <br />  <br /> 1  2 t-1 ( 2t-1 )2 ... ( 2t-1 ) n 1 <br /> Bằng cách ánh xạ sang mã nhị phân nhận được ma trận kiểm tra có dạng:<br /> I I I I ... I <br />  1 2 3 n 1 <br /> I h h h ... h<br /> H , (6)<br /> ... <br />  d 2 2( d  2) 3( d  2) ( n  1)(d  2 )<br /> <br />  I h h h ... h <br /> hi   i  i 1  i 2 ...  im 1 <br /> trong đó, I là các ma trân đơn vị cấp m, d là khoảng cách Hamming nhỏ nhất.<br /> Với cấu trúc ma trận kiểm tra (6), công thức tính norm có thay đổi nhưng các đặc điểm<br /> của phương pháp chuẩn syndrome vẫn giữ nguyên.<br /> Với mã RS sửa 1 lỗi modul, norm có thể tính như sau :<br /> S2<br /> NM  . (7)<br /> S1<br /> Chuẩn syndrome là bất biến với mọi vector lỗi trong modul, dựa vào tham số này sẽ<br /> xác định được vị trí modul lỗi. Thuật toán giải mã như sau :<br /> - Tính syndrome S = (S1, S2) ;<br /> - Tính norm syndrome NM;<br /> - Theo NM xác định số hiệu modul bị lỗi k;<br /> - Vector lỗi e trong modul k được xác định theo S1 ;<br /> - Sửa lỗi v = r + e.<br /> Để minh họa xét mã RS nhị phân (21, 15) với ma trận kiểm tra có dạng :<br />  I3 I3 I3 I3 I3 I3 I3 <br /> H 0 <br /> h h1 h2 h3 h4 h5 h6 <br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 105<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> <br />  0 1  2  0 1  2  0 1  2  0 1  2  0 1  2  0 1  2  0 1  2 <br /> H <br />  0 1  2 1  2  3  2  3  4  3  4  5  4  5  6  5  6  0  6  0 1 <br /> 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0<br /> 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0<br />  <br /> 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1  (8)<br /> H <br /> 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0<br /> 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1<br />  <br /> 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0<br /> Trên hình 2, hình 3 trình bày sơ đồ cấu trúc bộ giải mã, sơ đồ chức năng của khối xác<br /> định số hiệu modul lỗi được thực hiện trên thiết bị logic lập trình được.<br /> <br /> <br /> <br /> <br /> Hình 2. Sơ đồ cấu trúc bộ giải mã.<br /> <br /> <br /> 3. MỞ RỘNG KHẢ NĂNG SỬA LỖI CỦA MÃ REED-SOLOMON<br /> SỬ DỤNG PHƯƠNG PHÁP CHUẨN SYNDROME<br /> Xét mã Reed-Solomon (n, k) có d = 4, khi ánh xạ sang dạng nhị phân, ma trận kiểm tra<br /> có dạng:<br /> <br /> I I I I ... I <br />   (9)<br /> H   I h1 h2 h3 ... h n 1 <br />  I h2 h4 h6 ... h 2(n 1) <br />  <br /> <br /> <br /> <br /> <br /> 106 P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng …sử dụng chuẩn Syndrome.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> <br /> <br /> <br /> Hình 3. Sơ đồ chức năng khối xác định modul lỗi.<br /> Với ma trận kiểm tra (9) chuẩn syndrome được tính theo công thức:<br /> S S3 <br /> N  ( N1 , N2 )   2 ,  (10)<br />  S1 S2 <br /> Khi N1 = N2 = N, xảy ra lỗi trong 1 modul với N là số hiệu modul bị lỗi và tương ứng<br /> S1 sẽ thể hiện giá trị lỗi trong modul.<br /> Khi N1 ≠ N2 : nhận dạng đây là lỗi xảy ra ngoài phạm vi 1 modul và xử lý đặc biệt.<br /> Trong ví dụ dưới đây chỉ ra rằng ngoài lỗi trong 1 modul mã trên còn cho phép sửa lỗi<br /> chùm dài 5, 6.<br /> Xét mã RS(15,12) với d = 4, với đa thức sinh của trường x4  x  1 ma trận kiểm tra<br /> dạng:<br /> I I I I ... I <br />  <br /> H  I h1 h2 h3 <br /> ... h 14  , h i   i  i 1  i  2  i  3 <br /> I h2 h4 h6 ... h 28 <br /> <br />  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 ...  0  0  0  0 <br />  <br /> H   0  0  0  0  1  2  3  4  2  3  4  5  3  4  5  6 ...  14 15 16 17 <br />  0  0  0  0  2  3  4  5  4  5  6  7  6  7  8  9 ...  28 29 30 31 <br />  <br /> j k<br /> Biểu diễn các thành phần syndrome ở dạng: S = (S1, S2, S3) =( i ,  ,  ). Tính bậc<br /> của norm: deg N1=(j-i) mod 15, deg N2=(k-j) mod 15.<br /> Xét lỗi chùm dài 5 tại 2 modul, ví dụ lỗi tại 2 modul liền kề nhau gồm 8 dạng cấu hình<br /> vector lỗi e như sau: 10001, 11001, 10101, 10011, 11101, 10111, 11011, 11111.<br /> Trường hợp cấu hình vector lỗi e = 10001 tại modul 0 và 1, ta được kết quả: S = (S1, S2,<br /> S3) = ( 0 ,  j ,  k ) = ( 0,  4 ,  8 ), N = ( ,  4 ). Khi dịch đi 1 modul ta luôn thu được S<br /> = (S1 , S2 , S3 ) = ( , j 1 , 2( j 1) ), do đó chuẩn syndrome N = (N1 ,N 2 ) = ( , j 1 ), j =<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 107<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> 0, 1, ...14 và không trùng nhau. Tập hợp vec tor lỗi e = 10001 tại modul 0 và 1 và các<br /> dịch vòng theo modul của nó tạo thành một A-orbit.<br /> <br /> 1000 1000 1000 1000 .......... 1000 1000 <br />  0100 0100 0100 0100 ......... 0100 0100 <br />  <br />  0010 0010 0010 0010 ......... 0010 0010 <br />  <br />  0001 0001 0001 0001 .......... 0001 0001 <br /> 1000 0001 0010 0100 .......... 1110 1100 <br />  <br /> 0100 1001 0011 0110 .......... 0001 0010 <br /> H  <br /> 0010 0100 1001 0011 .......... 1000 0001 <br />   (11)<br />  0001 0010 0100 1001 .......... 1100 1000 <br /> 1000 0010 1001 0110 .......... 0111 1110 <br />  <br />  0100 0011 1100 0101 .......... 1100 0001 <br />  <br />  0010 1001 0110 1010 .......... 1110 1000 <br />  0001 0110 0011 1101 .......... 1111 1100 <br /> <br /> Với 07 cấu hình lỗi còn lại cho kết quả: khi dịch di 1 modul thì deg N1, deg N2 đều tăng<br /> 1 giá trị. Vì vậy, khoảng cách giữa bậc của N1 và N2 luôn không đổi với cùng 1 cấu hình<br /> vector lỗi e khi dịch vòng theo modul, khi giá trị khoảng cách đó trùng nhau với cấu hình<br /> vector e khác nhau thì S1 luôn khác nhau. Như vậy, tập hợp các lỗi chùm dài 5 tạo thành<br /> các A-orbit và có thể phân biệt với nhau, nghĩa là mã RS (15, 12) có thể sửa đồng thời lỗi<br /> modul bội 1 và lỗi chùm dài 5.<br /> Xét lỗi chùm độ dài 6 tại 2 modul liền kề nhau chứa 16 cấu hình vector lỗi có vector<br /> sinh như sau: 100001, 110001, 101001, 100101, 100011, 111001, 110101, 110011,<br /> 101101, 101011, 100111, 111101, 111011, 110111, 101111, 11111.<br /> Trường hợp cấu hình vector lỗi e = 110011 tại modul 0 và 1, giá trị syndrome S = (S1,<br /> 4<br /> S2, S3) = ( 0,8,12 ), chuẩn syndrome N = (N1,N2) = ( , ). Khi dịch vector lỗi đi 1<br /> 5<br /> modul thì S = (S1, S2, S3) = ( 0,9,14), N = (N1,N2) = ( , ). Tổng quát với syndrome,<br /> j<br /> chuẩn syndrome: S = (S1,S2,S3) = ( 0, ,k ), N = ( ,kj ), dịch vector lỗi đi 1 modul<br /> kj1<br /> nhận được S = (S1, S2, S3) = ( 0,j1,k2) ), N = ( , ), với k, j = 0, 1, ...14, các<br /> syndrome và chuẩn syndrome khác nhau đôi một.<br /> Với mỗi một trong 15 cấu hình lỗi độ dài 6 còn lại cho kết quả: khi dịch di 1 modul thì<br /> giá trị deg N1, deg N2 đều tăng 1. Các lỗi chùm dài 6 cũng tạo thành các A-orbit và có<br /> chuẩn syndrome phân biệt hoặc chuẩn syndrome trùng nhau nhưng giá trị S1 khác nhau<br /> nên có thể giải mã đơn trị.<br /> Quy tắc giải mã như sau:<br /> - Tính syndrome: S = r . HT = (S1, S2, S3)<br /> - Tính norm syndrome:<br />  S2 S3 <br /> N = (N1 N2) =  <br />  S1 S 2 <br /> <br /> <br /> <br /> 108 P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng …sử dụng chuẩn Syndrome.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> - Xây dựng bảng norm với các cấu hình vector sinh khác nhau (bổ sung giá trị K =<br /> deg N1 - deg N2);<br /> - Nếu N1 = N2 = N, xảy ra lỗi trong modul thứ N, vector giá trị lỗi bằng S1;<br /> - Nếu N1 ≠ N2, tính giá trị K = deg N1 - deg N2 và so sánh giá trị trong bộ nhớ để xác<br /> định vector sinh (dạng cấu hình lỗi), kết hợp với giá trị S1 hoặc S2 (khi S1 = 0) để tìm<br /> lượng dịch vòng x (dịch vòng theo modul);<br /> - Vector lỗi nhận được e ta cộng modul với từ mã thu được r sẽ đưa ra ở đầu ra từ<br /> 12<br /> mã đúng v: v = r + e. Ví dụ: S = (S1, S2, S3) = ( ,  2 ,  14 ), (N1, N2) = ( ,  ), K = 4.<br /> Tra bảng giá trị với K = 4 có thể xác định vector lỗi dạng e1 =11001 hoặc e2 = 10111; e3 =<br /> 100101; tuy nhiên chỉ có vector e1 thỏa mãn S1 = α, vì vậy cấu hình lỗi dạng 11001. Với<br /> 14 10<br /> vector sinh e0 = 11001, (N1 , N2 ) = (  ,  ), vì vậy số lượng dịch vòng modul x =<br /> 1-14 = 2 (mod 15), kết quả là vector lỗi e = 00000001100100...00.<br /> 4. KẾT LUẬN<br /> Phương pháp chuẩn syndrome cho mã BCH có thể áp dụng cho mã Reed-Solomon với<br /> việc phân chia vector lỗi thành các A-orbit. Dựa trên phương pháp chuẩn syndrome, ngoài<br /> lỗi modul trong khả năng sửa của mã RS, có thể nhận dạng và sửa được đồng thời một số<br /> lỗi chùm. Mã RS(15,12) trên trường GF(24) cho phép đồng thời sửa 1 lỗi modul dài 4 và<br /> các lỗi chùm dài 5, 6. Cấu trúc của thiết bị giải mã dựa trên phương pháp đã đề xuất dễ<br /> thực hiện trên các phần tử logic lập trình được, có tốc độ cao do xử lý song song.<br /> <br /> TÀI LIỆU THAM KHẢO<br /> [1]. Lin Shu. “Error control coding: Fuldamentals and applications”, Pre., Inc, 1983.<br /> [2]. G. Sharma, A.A. Hassan and A. Dholakia, “Performance evaluation of burst-error-<br /> correcting codes on a Gilbert–Elliott channel,” IEEE Trans. On Commun. 46 (1998).<br /> [3]. Todd K. Moon. “Wiley Error Correction Coding Mathematical Methods and<br /> Algorithms,” John Wiley & Sons Ltd, 2005.<br /> [4]. Phạm Khắc Hoan, Vũ Sơn Hà, Phạm Việt Trung. “Phương pháp thế giải mã hiệu quả<br /> mã BCH,” Nghiên cứu khoa học và công nghệ quân sự (05-2012).<br /> [5]. В.А. Липницкий, В.К. Конопелько, “Норменное декодирование помехоустойчивых<br /> кодов и алгебраические уравнения,” Минск : Изд. центр БГУ, 2007.<br /> ABSTRACT<br /> EXTENSION ERROR-CORRECTION CAPABILITY OF<br /> REED-SOLOMON CODES USING NORM OF SYNDROME<br /> In this paper a permuted decoding of RS codes based on norm syndrome, a new<br /> parameter that is characterized by code’s structure is investigated. For RS codes<br /> error vectors are classcified by A-orbit. By partition error vectors into disjoint<br /> equivalent, the module errors and some of burst errors can be corrected<br /> simultaneously using RS codes.<br /> Keywords: Syndrome, RS codes, Permuted decoding, Norm of syndrome, Burst error.<br /> <br /> Nhận bài ngày 01 tháng 02 năm 2015<br /> Hoàn thiện ngày 10 tháng 4 năm 2015<br /> Chấp nhận đăng ngày 15 tháng 4 năm 2015<br /> §Þa chØ: * Khoa Vô tuyến điện tử, Học viện KTQS;<br /> ** Viện CNTT, Viện KHCNQS;<br /> *** Sở Giáo dục và đào tạo Bắc Ninh.<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 109<br />