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ệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 103 MỞ RỘNG KHẢ NĂNG SỬA LỖI CỦA MÃ REED-SOLOMON SỬ DỤNG CHUẨN SYNDROME PHẠM KHẮC HOAN*, VŨ SƠN HÀ**, NGUYỄN THỊ THU NGA*** 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 loại dịch vòng vector lỗi theo chuẩn syndrome, tham số đặc trưng cho cấu trúc đại số của mã. Với mã Reed-Solomon (RS), các vector lỗi sẽ được chia thành các A-orbit. Nhờ phân hoạch các modul lỗi thành các tập con tương đương không giao nhau nên mã RS có thể đồng thời sửa được lỗi modul và lỗi chùm. Từ khóa: Syndrome, Mã Reed-Solomon, Giải mã thế, Chuẩn syndrome. 1. ĐẶT VẤN ĐỀ 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ý 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 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ã 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 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 trình bậc cao trong trường Galoa [1, 2, 3]. Phương pháp chuẩn syndrome được V. K. 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 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 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 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 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 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 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 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 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- 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 của mã Reed-Solomon và phần 4 trình bày các đánh giá, phân tích. 2. PHƯƠNG PHÁP VÀ THIẾT BỊ GIẢI MÃ RS DỰA TRÊN CHUẨN SYNDROME Với mã RS có khoảng cách mã δ, ma trận kiểm tra có dạng:                   )2)(1()2(3)2(22 )1)(1()1(3)1(21 )1(32 ... I ... ... I ... 1     bnbbb bnbbb bnbbb H Khi đó syndrome của vector lỗi e có 1  thành phần trong trường GF(qm), 1 2 1( ) ( , ,..., )S e s s s  . Chuẩn syndrome (norm) Nij chứa 2 1C   thành phần được tính theo công thức sau [4, 5]: (2) ij ij hjb i hib j ij S S N /)1( /)1(    (1) Kỹ thuật điện tử & Khoa học máy tính P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng sử dụng chuẩn Syndrome.” 104 Trong đó hij là ước số chung lớn nhất của i và j Nij = ∞ nếu Si = 0 và Sj ≠ 0 Nij không xác định nếu Si = Sj = 0 Ví dụ, với mã RS có khoảng cách cấu trúc δ = 5, b = 1 chuẩn (norm) syndrome có 6 thành phần: (3) Các tính chất cơ bản của chuẩn syndrome đối với mã BCH và mã Reed-Solomon tương tự nhau, với mã Reed-Solomon cần chú ý một số khác biệt sau: 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 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 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 trong trường GF(23), (trường hợp riêng  = α). Hình 1. Các A-orbit của mã Reed-Solomon dài 7. Với mã RS có b = 1, syndrome S(e) = (s1, s2, , sδ-1) ta có 1 2 3 1( ( )) ( , , , .. ., ) ( ) .S f e s s s s S e       Định lý: Cho mã RS có ma trận kiểm tra (1), với chuẩn syndrome: 1 2 1 3 ( 2 )( 1)( ( )) ( , , . .., ).N S e N N N    Khi đó [5]: 1 2 1 3 ( 2 )( 1 )( ( )) ( , , .. ., ) ,N S e N N N        với ( ) / / , 1 1 .ij j i h ij i jN N i j          (4) 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 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 pháp chuẩn syndrome được thực hiện thông qua các A-orbit. Trong bộ nhớ sẽ lưu vector 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ã 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 4 3 3 4 342 2 4 243 2 3 23 4 1 4 143 1 3 132 1 2 12 ,, ,, S S N S S N S S N S S N S S N S S N   f f )(6 e )( e )(2 e )(e)(6 e )(2 e e e e6 )( 6e )( 62 e )( 66 e f Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 105 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 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ụ 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 thông qua δ-2 thành phần norm đầu tiên. 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 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 là ma trận  1 2 i m 1 ... .i i i ih        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, ma trận kiểm tra có dạng: 2 n 1 2 t-1 2t-1 2 2t-1 n 1 1 1 1 ... 1 1 ... ... 1 ( ) ... ( ) H                      (5) Bằng cách ánh xạ sang mã nhị phân nhận được ma trận kiểm tra có dạng: 1 2 3 1 2 2( 2) 3( 2) ( 1)( 2) I I I I ... I I ... ... I ... n d d d n d h h h h H h h h h                    ,  1 mi21 ...   iiiih trong đó, I là các ma trân đơn vị cấp m, d là khoảng cách Hamming nhỏ nhất. 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 của phương pháp chuẩn syndrome vẫn giữ nguyên. Với mã RS sửa 1 lỗi modul, norm có thể tính như sau : 2 1 .M S N S  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ẽ xác định được vị trí modul lỗi. Thuật toán giải mã như sau : - Tính syndrome S = (S1, S2) ; - Tính norm syndrome NM; - Theo NM xác định số hiệu modul bị lỗi k; - Vector lỗi e trong modul k được xác định theo S1 ; - Sửa lỗi v = r + e. Để minh họa xét mã RS nhị phân (21, 15) với ma trận kiểm tra có dạng : 3 3 3 3 3 3 3 0 1 2 3 4 5 6 I I I I I I I H h h h h h h h        (6) (7) Kỹ thuật điện tử & Khoa học máy tính P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng sử dụng chuẩn Syndrome.” 106 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 0 6 0 1 H                                                   1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 0 H                    (8) 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 định số hiệu modul lỗi được thực hiện trên thiết bị logic lập trình được. Hình 2. Sơ đồ cấu trúc bộ giải mã. 3. MỞ RỘNG KHẢ NĂNG SỬA LỖI CỦA MÃ REED-SOLOMON SỬ DỤNG PHƯƠNG PHÁP CHUẨN SYNDROME 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 có dạng: (9) 1 2 3 n 1 2 4 6 2(n 1) I I I I ... I I ... I ... H h h h h h h h h              Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 107 Hình 3. Sơ đồ chức năng khối xác định modul lỗi. Với ma trận kiểm tra (9) chuẩn syndrome được tính theo công thức: 2 3 1 2 1 2 ( , ) , S S N N N S S         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 S1 sẽ thể hiện giá trị lỗi trong modul. 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. 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 chùm dài 5, 6. 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 dạng:              28642 14321 ... I ... I I ... I I I I hhhh hhhhH ,  3i21   iiiih            313029289876765454320000 171615146543543243210000 00000000000000000000 ... ... ...    H Biểu diễn các thành phần syndrome ở dạng: S = (S1, S2, S3) =( i , j , k ). Tính bậc của norm: deg N1=(j-i) mod 15, deg N2=(k-j) mod 15. 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 vector lỗi e như sau: 10001, 11001, 10101, 10011, 11101, 10111, 11011, 11111. 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, S3) = ( 0 , ,j k  ) = ( 4 80, ,  ), N = ( 4, ). Khi dịch đi 1 modul ta luôn thu được S = (S1, S2, S3) = ( 1 2( 1), ,j j   ), do đó chuẩn syndrome N = (N1,N2) = ( 1, j  ), j = (10) Kỹ thuật điện tử & Khoa học máy tính P.K.Hoan, V.S.Hà, N.T.T.Nga, “Mở rộng khả năng sử dụng chuẩn Syndrome.” 108 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 dịch vòng theo modul của nó tạo thành một A-orbit.                                        11001111..........1101001101100001 10001110..........1010011010010010 00011100..........0101110000110100 11100111..........0110100100101000 10001100..........1001010000100001 00011000..........0011100101000010 00100001..........0110001110010100 11001110..........0100001000011000 00010001..........0001000100010001 00100010.........0010001000100010 01000100.........0100010001000100 10001000..........1000100010001000 H 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 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 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 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 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 modul bội 1 và lỗi chùm dài 5. 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 sinh như sau: 100001, 110001, 101001, 100101, 100011, 111001, 110101, 110011, 101101, 101011, 100111, 111101, 111011, 110111, 101111, 11111. Trường hợp cấu hình vector lỗi e = 110011 tại modul 0 và 1, giá trị syndrome S = (S1, S2, S3) = ( 8 120, ,  ), chuẩn syndrome N = (N1,N2) = ( 4, ). Khi dịch vector lỗi đi 1 modul thì S = (S1, S2, S3) = ( 9 140, ,  ), N = (N1,N2) = ( 5, ). Tổng quát với syndrome, chuẩn syndrome: S = (S1,S2,S3) = (0, , j k  ), N = ( , k j  ), dịch vector lỗi đi 1 modul nhận được S = (S1, S2, S3) = ( 1 2)0, ,j k   ), N = ( 1, k j   ), với k, j = 0, 1, ...14, các syndrome và chuẩn syndrome khác nhau đôi một. 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ì 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ó chuẩn syndrome phân biệt hoặc chuẩn syndrome trùng nhau nhưng giá trị S1 khác nhau nên có thể giải mã đơn trị. Quy tắc giải mã như sau: - Tính syndrome: S = r . HT = (S1, S2, S3) - Tính norm syndrome: N = (N1 N2) =       2 3 1 2 S S S S (11) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04 - 2015 109 - 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 = deg N1 - deg N2); - Nếu N1 = N2 = N, xảy ra lỗi trong modul thứ N, vector giá trị lỗi bằng S1; - Nếu N1 ≠ N2, tính giá trị K = deg N1 - deg N2 và so sánh giá trị trong bộ nhớ để xác đị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 lượng dịch vòng x (dịch vòng theo modul); - Vector lỗi nhận được e ta cộng modul với từ mã thu được r sẽ đưa ra ở đầu ra từ mã đúng v: v = r + e. Ví dụ: S = (S1, S2, S3) = ( 2 14, ,   ), (N1, N2) = ( 12,  ), K = 4. 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 = 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 vector sinh e0 = 11001, (N1, N2) = ( 14 10,  ), vì vậy số lượng dịch vòng modul x = 1-14 = 2 (mod 15), kết quả là vector lỗi e = 00000001100100...00. 4. KẾT LUẬN Phương pháp chuẩn syndrome cho mã BCH có thể áp dụng cho mã Reed-Solomon với 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 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ố 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à 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ễ 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. TÀI LIỆU THAM KHẢO [1]. Lin Shu. “Error control coding: Fuldamentals and applications”, Pre., Inc, 1983. [2]. G. Sharma, A.A. Hassan and A. Dholakia, “Performance evaluation of burst-error- correcting codes on a Gilbert–Elliott channel,” IEEE Trans. On Commun. 46 (1998). [3]. Todd K. Moon. “Wiley Error Correction Coding Mathematical Methods and Algorithms,” John Wiley & Sons Ltd, 2005. [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ả mã BCH,” Nghiên cứu khoa học và công nghệ quân sự (05-2012). [5]. В.А. Липницкий, В.К. Конопелько, “Норменное декодирование помехоустойчивых кодов и алгебраические уравнения,” Минск : Изд. центр БГУ, 2007. ABSTRACT EXTENSION ERROR-CORRECTION CAPABILITY OF REED-SOLOMON CODES USING NORM OF SYNDROME In this paper a permuted decoding of RS codes based on norm syndrome, a new parameter that is characterized by code’s structure is investigated. For RS codes error vectors are classcified by A-orbit. By partition error vectors into disjoint equivalent, the module errors and some of burst errors can be corrected simultaneously using RS codes. Keywords: Syndrome, RS codes, Permuted decoding, Norm of syndrome, Burst error. Nhận bài ngày 01 tháng 02 năm 2015 Hoàn thiện ngày 10 tháng 4 năm 2015 Chấp nhận đăng ngày 15 tháng 4 năm 2015 §Þa chØ: * Khoa Vô tuyến điện tử, Học viện KTQS; ** Viện CNTT, Viện KHCNQS; *** Sở Giáo dục và đào tạo Bắc Ninh.