Phương pháp nén chuẩn syndrome giải mã mã BCH

Nghiờn cứu khoa học cụng nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, số 32, 08 - 2014 91 Phương pháp nén CHUẩN SYNDROME giải mã mã BCH Phạm Khắc Hoan*, Vũ sơn hà**, BùI NGọC Mỹ*** Tóm tắt: Phương pháp giải mã thế mã BCH được trình bày trong bài báo cho phép giảm độ phức tạp khi sửa lỗi bội cao. Dựa trên phép thế cyclotomic và phép thế dịch vòng có thể phân loại các vector lỗi thành các lớp cyclotomic. Mặt khác, khi thực hiện phép biến đổi syndrome sao cho thành phần thứ nhất của syndrome bằng 0 có thể giảm đáng kể số lượng chuẩn syndrome cần xử lý. Từ khóa: Syndrome, Mã BCH, Giải mã thế, Chuẩn syndrome, Phép thế cyclotomic. 1. Dẫn nhập Các phương pháp đại số truyền thống để giải mã mã BCH thường yêu cầu giải phương trình khóa trên trường Galoa. Biện pháp thường được sử dụng là nhân tử hóa trong trường hữu hạn theo thuật toán Berlerkamp và thủ tục Chien để tìm nghiệm phương trình bằng cách thử lần lượt. Vì vậy độ phức tạp giải mã tăng hàm mũ theo bội lỗi cần sửa và độ dài từ mã [1]. Một biện pháp hiệu quả để giảm độ phức tạp của giải mã syndrome là phương pháp giải mã dựa trên nhóm tự đồng cấu, còn gọi là phương pháp thế. Thành tựu đáng kể và có triển vọng to lớn trong giải mã thế (permuted decoding) là phương pháp chuẩn syndrome được V. K. Konopelko đề xuất và các học trò của ông tiếp tục phát triển 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ác thành phần syndrome - chuẩn syndrome [2, 3]. Tuy nhiên khi tăng bội lỗi cần sửa sẽ tăng số lượng thành phần syndrome, tăng số lượng chuẩn syndrome, do đó tăng độ phức tạp giải mã. Các mã BCH có cấu trúc đại số chặt chẽ trên trường hữu hạn, vì vậy có thể sử dụng các phép thế cyclotomic, phép thế dịch vòng cho phép phân hoạch, xử lý hiệu quả các lớp vector lỗi và syndrome. Dưới tác động của phép thế cyclotomic, bậc của phần tử bất kỳ trong trường Galoa sẽ được nhân đôi. 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 chuẩn syndrome cho mã BCH, phần 3 nghiên cứu phép thế cyclotomic và quan hệ của nó với phép thế dịch vòng, phần 4 nghiên cứu vấn đề nén chuẩn syndrome để giảm độ phức tạp giải mã. 2. Phương pháp chuẩn syndrome giải mã mã bch Ma trận kiểm tra của mã BCH nhị phân với khoảng cách cấu trúc δ  2t+1 có dạng:   .10,....,, )12(3   niH Titii  (1) Khi đó syndrome của vector lỗi tùy ý gồm t thành phần thuộc trường GF(2m) S(e)  (s1, s2, ..., st). Với mã BCH nhị phân nguyên thủy theo nghĩa hẹp,  phần tử nguyên thủy của trường GF(2m) và ma trận kiểm tra có dạng:   .12,10,....,, )12(3   mTitii nniH  (2) Cho e là vector lỗi tùy ý khi sử dụng mã BCH nhị phân ta có: ).,...,,())(( 122 3 1 t t ssseS   (3) Gọi phổ syndrome của σ-orbit J là tập hợp các syndrome của tất cả các vector lỗi của J với mã C và ký hiệu là S(J). Đối với mã BCH nhị phân phổ syndrome của σ-orbit J = bao gồm các vector khác nhau đôi một của không gian S(En) dạng: .10),,...,,( 1 )2( 2 )1( 1   nsss bbb    (4) Kỹ thuật điện tử & Khoa học máy tính P. K. Hoan, V. S. Hà, B. N. Mỹ, “Phương phỏp nộn chuẩn syndrome mó BCH.” 92 Trong trường hợp mã BCH nhị phân nguyên thủy đối với vector lỗi e, syndrome S(e) = (s1, s2, ..., st) phổ syndrome S() gồm tất cả các vector khác nhau đôi một dạng .220),,...,,( )12(2 3 1   m t t sss   (5) Định nghĩa norm syndrome (chuẩn syndrome) là vector N(S) có 2 1C tọa độ Nij, 1≤ i<j≤ t tính theo công thức: .0;0;0 );1,1(,0/ /)1(/)1(    jiijijij iji hjb i hib jij sskhiNsskhiN jbibUSCLNhskhissN ijij (6) Với mã BCH nhị phân gốc (b = 1) chuẩn syndrome là vector N(S) có 2tC tọa độ: (2 1)/ (2 1)/ / , (2 1, 2 1), 0; 0; 0. ij ij ij i h j h j i ij ij j i ij i j N s s h USCLN i j N khi s s N khi s s               . (7) Tính chất cơ bản của chuẩn syndrome là tính bất biến của nó với nhóm các dịch vòng. Từ công thức (6) suy ra đối với mọi mã vector lỗi e của mã BCH thỏa mãn đẳng thức sau: ))(()))((( eSNeSN  . (8) Vì vậy, phương pháp chuẩn syndrome giải mã BCH dựa trên xác định vector sinh của mỗi lớp vector lỗi tương ứng với các giá trị chuẩn syndrome, sau đó dựa vào một thành phần syndrome sẽ xác định lượng dịch vòng cần thiết để biến đổi vector sinh thành vector lỗi [2, 3]. 3. Phép thế cyclotomic và các lớp cyclotomic Các tập cyclotomic theo modul n với trường GF(q) chứa bậc (số mũ) của n lũy thừa khác nhau của căn nguyên thủy bậc n của 1 trên trường GF(q), mỗi tập hợp tương ứng với một lớp liên hợp. Các tập cyclotomic cho phép biểu diễn hiệu quả các lớp này. Ví dụ các tập cyclotomic modul 15 trong trường GF(7) bao gồm {0}; {1, 7, 4, 13}; {2, 14, 8, 11}; {3, 6, 12, 19}; {5}; {10} [4]. Định nghĩa trên tập T = {0, 1, 2, ..., n} biến đổi φ thỏa mãn φ (i) = 2i-1 mod n. Với n lẻ, φ là song ánh trên tập T. Khi đánh số tọa độ của vector lỗi không phải từ 1 mà từ 0 đến (n- 1), ta có, φ (i) = 2i mod n. Tương tự khi áp dụng biến đổi này k lần ta có: φk (i) = i2k mod n. Khi đó các số i, 2i, 22i, ...2m-1i tạo thành một lớp cyclotomic theo modul n. Các phép thế φ, φ2, .. φm =1 gọi là nhóm cyclotomic Φ. 1 2 3 4 5 6 7 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 φ(e): φ2(e): e : e =φ3(e): Hình 1. Tác động của phép thế cyclotomic với vector e = (0111000). Nghiờn cứu khoa học cụng nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, số 32, 08 - 2014 93 Phép thế cyclotomic φ là một phép thế dựa trên tự đồng cấu Frobenius trên trường Galoa GF (2m). Dưới tác động của tự đồng cấu này bậc của các phần tử trong trường Galoa sẽ nhân đôi. Do đó tọa độ i của một vector dưới tác động của phép thế φ sẽ trở thành tọa độ 2i (tính theo modul n). Trong các phần dưới đây sử dụng đánh số tọa độ đầu tiên bắt đầu bởi 1 chứ không phải 0. Trên hình 1 minh họa tác động của phép thế cyclotomic φ và bậc của nó trong không gian nhị phân 7 chiều. Các phép thế dịch vòng và cyclotomic σ, φ sinh ra nhóm không giao hoán các phép thế với các tọa độ trong không gian En (n lẻ), nó bao gồm các phép thế φ j σi, 0 ≤ i ≤ n-1, 0 ≤ j ≤ m-1. Hai vector f, g trong En gọi là G-tương đương nếu tồn tại phép thế φ j σi sao cho φj σi (f) = g. Gọi G-orbit là tập hợp tất cả các vector thuộc En thỏa mãn G-tương đương từng đôi một: G = {, φ,..., φà-1 }, à-số tự nhiên nhỏ nhất thỏa mãn φà= 1. Nhóm G và các orbit của nó có các tính chất sau. 1) Nhóm dịch vòng sinh bởi phép thế φ bao gồm m phần tử, m là số tự nhiên nhỏ nhất thỏa mãn 2m -1 chia hết cho n. 2) Phép thế cyclotomic biến đổi σ–orbit thành σ–orbit. 3) φ σ (e)= σ2φ(e). 4) Bậc của nhóm G bằng mn. 5) G-orbit sinh bởi vector bao gồm tất cả σ-orbit nhận được dưới tác động của phép thế cyclotomic lên σ-orbit . 6) Phần lớn G-orbit là các G-orbit đầy đủ chứa mn phần tử. Ví dụ 9 σ-orbit của các vector lỗi bội 1, 2, 3 trong không gian E7 chia thành 5 G-orbit bao gồm: J1 G =- tập hợp các vector lỗi đơn; J1 G = G = {; ; }, G-orbit của tất cả lỗi bội 2; J31 G = G = {; ; }; J32 G = G = ; J33 G = G = ; 3 G-orbit của lỗi bội 3. Tương tự, 39 σ-orbit của các vector lỗi bội 1, 2, 3 trong không gian E15 chia thành 14 G- orbit. Như vậy các phép thế cyclotomic biến đổi lẫn nhau các σ-orbit của các vector lỗi trọng lượng giống nhau. Việc phân loại các vector lỗi thành các G-orbit cho phép xử lý hiệu quả chúng, và tiến hành giải mã dựa trên phương pháp thế theo chuẩn syndrome. 4. Giải mã BCH theo phương pháp nén chuẩn syndrome Trước hết xem xét vai trò của thành phần syndrome đầu tiên s1. Với s1 ≠ 0, đối với mã nhị phân nguyên thủy và USCLN (b, n) =1 (để đơn giản dưới đây coi rằng b = 1), phổ syndrome S(J) chứa n syndrome phân biệt, thành phần s1 sẽ nhận mỗi một giá trị khác 0 trong GF(2m) đúng một lần. Nếu với một vector e nào đó thuộc σ-orbit J có s1 = 0, tất cả các vector của σ-orbit đều có thành phần đầu tiên bằng 0 (theo công thức 5). Các vector này có liên hệ với các vector lỗi có trọng lượng nhỏ hơn. Giả sử với vector lỗi e tùy ý, syndrome S(e) = (s1, s2, ..., st) có thành phần đầu tiên s1 = α h ≠ 0, sau khi dịch vòng n – h nhịp sẽ nhận được s1 * = 1. Xét vector g là tổng của vector f nhận được sau khi dịch vòng vector e và vector (1, 0, ...,0), g = τ(f) = f + 1, rõ ràng syndrome của g có thành phần thứ nhất bằng 0. Ký hiệu M0,w là tập hợp các vector lỗi bội w có thành phần syndrome đầu tiên bằng 0. Vector g tạo thành tập M10,w trong M0,w. Trên hình 2 biểu diễn tác động của biến đổi τσn-h với các vector lỗi bội 2 trong không gian E15, khi đó 105 vector lỗi bội 2 (7 σ-orbit) được nén thành 7 vector bội 3 thuộc 3 σ-orbit có thành phần s1 = 0. Trên hình này, với mỗi σ-orbit vector sinh được mô tả ở hàng đầu tiên, bậc của các thành phần syndrome được mô tả ở hàng thứ hai. Kỹ thuật điện tử & Khoa học máy tính P. K. Hoan, V. S. Hà, B. N. Mỹ, “Phương phỏp nộn chuẩn syndrome mó BCH.” 94 Như vậy nếu xác định được vector g sẽ tìm được vector e = σh(τ(g)). Việc xác định g đơn giản hơn việc xác định e bởi vì số lượng vector g ít hơn số lượng vector e đúng n lần; số lượng σ-orbit của g ít hơn của e khoảng w + 1 lần; số lượng thành phần chuẩn syndrome cũng giảm đi. Tuy nhiên cần tính đến khả năng các vector g có trọng số khác nhau có cùng chuẩn syndrome và syndrome. Khi đó cần đánh giá trọng số của g theo syndrome và trước tiên xác định các vector có trọng số w ≤ t, sau đó mới xét vector trọng số t+1. Chú ý rằng trong mỗi σ-orbit của các vector thuộc tập M 0,w chỉ có w vector thuộc tập M 1 0,w, vì vậy có thể xác định đơn trị vector g. Quy tắc giải mã theo phương pháp nén chuẩn syndrome như sau. 1. Tính syndrome S = (s1, s2, ..., st), nếu S = 0, không xảy ra lỗi, với S ≠ 0, giải mã theo các bước sau. 2. Nếu s1 = 0, tính chuẩn syndrome, xác định vector lỗi theo phương pháp chuẩn syndrome. 3. Nếu s1 = α h ≠ 0, sử dụng biến đổi g = τσn-h(e), khảo sát S(g) = (0, N12 + 1, ..., N1t +1), nếu S(g) = 0, xảy ra lỗi đơn tại vị trí h. 4. Với S(g) ≠ 0, chuyển về bước 2 và giải mã theo phương pháp chuẩn syndrome để xác định g. 5. Biến đổi vector g để xác định vector lỗi e = σh(τ(g)). Hình 2. Tác động của các phép thế τσn-h với các vector lỗi bội 2 trong không gian E15 Trong bảng 1 biểu diễn các σ-orbit của tập hợp M0,3; M0,4 liên kết thành các lớp cyclotomic, vector sinh, syndrome và thành phần thứ 3 của chuẩn syndrome của mã C7 (15, 3) với đa thức sinh của trường x4 + x + 1. Trong bảng trên, tập hợp 35 vector M0, 3 chia thành 3 σ-orbit, lớp cyclotomic Φ1 có các vector sinh (1, 12, 13) và (1, 8, 10) (mỗi vector này sẽ có thêm 14 vector dịch vòng), lớp Φ2 có vector sinh (1, 6, 11) (và 4 dịch vòng của nó). Thành phần chuẩn syndrome thứ 3 của các vector thuộc M0,3 trùng với chuẩn syndrome của các lỗi bội 4 thuộc tập M0,4. Các σ-orbit của tập hợp M0,3; M0,4 có chuẩn syndrome N = (∞, ∞, α 5) (gồm một σ-orbit của lỗi bội 3 và 3 σ-orbit lỗi bội 4) có phổ syndrome như nhau. Ngoài Nghiờn cứu khoa học cụng nghệ Tạp chớ Nghiờn cứu KH&CN quõn sự, số 32, 08 - 2014 95 thành phần thứ 3 của chuẩn syndrome, khi bổ sung thêm các giá trị deg s2 có thể xác định đơn trị vector sinh của các σ-orbit này. Chú ý rằng dưới tác động của phép thế cyclotomic giá trị deg s2 sẽ được nhân đôi. Bảng 1. Vector sinh của tập hợp hợp M0,3; M0,4 syndrome và thành phần N3 Lớp cyclotomic Số thứ tự σ-orbit Vector sinh syndrome N3 Ф1 1 (1,12,13) (0, α8, α10) α5 2 (1,8,10) (0, α1, α5) α10 Ф2 3 (1,6,11) (0, α 0, 0) 0 Ф3 4 (1,2,3,11) (0, α2, α5) α5 5 (1,3,5,6) (0, α4, α10) α10 6 (1,5,9,11) (0, α8, α5) α5 7 (1,2,6,9) (0, α1, α10) α10 Ф4 8 (1,3,10,13) (0, α11, α5) α5 9 (1,4,5,10) (0, α7, α10) α10 Ф5 10 (1,2,4,8) (0, α 12, 0) 0 Xét độ phức tạp của phương pháp trên. Xét mã BCH (31, 16) số lượng vector lỗi bội 1 - 3 cần phân tích là 4991. Khi sử dụng phương pháp chuẩn syndrome yêu cầu phân tích 161 chuẩn syndrome. Với phương pháp nén chuẩn syndrome yêu cầu phân tích 5 σ-orbit của tập M0,3 (gồm một G-orbit) hoặc phân tích 31 vector thuộc tập M 1 0,3, M 1 0,4 do đó nếu tính đến cả phép dịch vòng chỉ cần 5 + 31 + 1 + 31 = 68 phép phân tích. Độ phức tạp giải mã giảm khoảng 73 lần so với phương pháp syndrome thông thường. 4. Kết luận Dựa trên phép thế cyclotomic có thể phân hoạch tập các vector lỗi thành các lớp cyclotomic, xác định vector sinh của chúng theo chuẩn syndrome cho phép xác định vector lỗi. Nhờ biến đổi syndrome thành syndrome có thành phần thứ nhất bằng 0 có thể giảm số lượng thành phần chuẩn syndrome cần xử lý. Khi sửa các lỗi bội 3 nhờ mã BCH (31, 16) phương pháp đã đề xuất cho phép giảm độ phức tạp khoảng 3 lần so với phương pháp chuẩn syndrome, giảm 73 lần so với phương pháp syndrome. Tài liệu tham khảo [1]. Lin Shu. Error control coding: Fuldamentals and applications, Prentice-Hall, 1983. [2]. 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”, Tạp chớ NCKH và cụng nghệ quõn sự (05-2012). [3]. В.А. Липницкий, В.К. Конопелько, “Норменное декодирование помехоустойчивых кодов и алгебраические уравнения”, Минск : Изд. центр БГУ, 2007. [4]. Todd K. Moon, “Wiley Error Correction Coding Mathematical Methods and Algorithms”, John Wiley & Sons Ltd, 2005. [5]. M. Maheswari, G. Seetharaman, “Multi bit random and burst error correction code with crosstalk avoidance for reliable on chip interconnection links”, Microprocessors and Microsystems, 37(2013). Kỹ thuật điện tử & Khoa học máy tính P. K. Hoan, V. S. Hà, B. N. Mỹ, “Phương phỏp nộn chuẩn syndrome mó BCH.” 96 [6]. R. H. Morelos-Zaragoza, “The Art of Error Correcting Coding”, John Wiley &, 2002. [7]. Муттер, В.М, “Основы помехоустойчивой телепередачи информации”, В.М. Муттер – Л.: Энергоатомиздат, Ленинградское отделение, 1990. [8]. Madhu Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity, 13(1):180-193, 1997. Abstract A method of compressing norm of syndrome for decoding bch codes In this paper a permuted decoding of BCH codes is proposed, that allows decreasing complexity of correcting the multiple errors. Based on cyclotomic and cyclic permutations can divide the error vectors into cyclotomic cosets. Moreover, the transformation of syndrome to syndrome, which the first component is zero, can significantly decrease the number of processing norm of syndrome. Keywords: BCH codes, Permuted decoding, Norm syndrome, Decoding beyond the error-correction bound. Nhận bài ngày 20 thỏng 05 năm 2014 Hoàn thiện ngày 25 thỏng 06 năm 2014 Chấp nhận đăng ngày 01 thỏng 8 năm 2014 Địa chỉ: * Khoa VTĐT, Học viên Kỹ thuật Quân sự. ** Viện CNTT, VKHCNQS. *** Phòng Đào tạo, VKHCNQS.