Tài liệu Xây dựng phương pháp giải mã theo chuẩn syndrome trên cơ sở nhận dạng lỗi [tt]

Bé gi¸o dôc vµ ®µo t¹o Bé Quèc phßng ViÖn khoa häc vµ c«ng nghÖ qu©n sù -------------------------- VŨ SƠN HÀ XÂY DỰNG PHƢƠNG PHÁP GIẢI MÃ THEO CHUẨN SYNDROME TRÊN CƠ SỞ NHẬN DẠNG LỖI Chuyên ngành: Mã số: Kỹ thuật điện tử 62 52 02 03 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI - 2016 Công trình đƣợc hoàn thành tại: VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÒNG Ngƣời hƣớng dẫn khoa học: 1. TS PHẠM VIỆT TRUNG 2. TS PHẠM KHẮC HOAN Phản biện 1: PGS.TS Lê Mỹ Tú Học viện Kỹ thuật Mật mã Phản biện 2: PGS.TS Hoàng Mạnh Thắng Đại học Bách khoa Hà Nội Phản biện 3: TS Nguyễn Đông Hƣng Cục Cơ yếu – Bộ Tổng tham mưu Luận án đƣợc bảo vệ trƣớc Hội đồng chấm luận án Tiến sĩ cấp Viện, họp tại Viện Khoa học và Công nghệ quân sự vào hồi: ...... giờ ...... ngày ...... tháng ...... năm 2016. Có thể tìm hiểu luận án tại: - Thư viện Viện Khoa học và Công nghệ quân sự. - Thư viện Quốc gia Việt Nam. 1 MỞ ĐẦU 1. Tình hình nghiên cứu trong nƣớc và ngoài nƣớc Tại Việt Nam các giáo sư Nguyễn Xuân Quỳnh, Nguyễn Bình đã nghiên cứu về mã cyclic cục bộ từ những năm 80 của thế kỷ XX. Mã cyclic cục bộ tiếp tục phát triển và có nhiều thành tựu đáng kể. Tuy nhiên các công trình này chưa đi sâu vào việc nghiên cứu phương pháp giải mã, thiết kế bộ giải mã, đặc biệt khi khoảng cách mã lớn, hay mã có khả năng sửa đồng thời lỗi ngẫu nhiên và lỗi chùm. Các thiết bị giải mã mã BCH, Reed-Solomon hiện nay thường sử dụng các thuật toán Berlekamp-Massey, Euclid. Thuật toán BerlekampMassey (BMA) là một phương pháp tính để giải phương trình khóa rất hiệu quả về số lượng của phép tính trong trường hữu hạn và là lựa chọn phổ biến để mô phỏng hoặc thực hiện giải mã BCH và Reed-Solomon bằng phần mềm. Thuật toán Euclid (EA) là phương pháp để giải phương trình khóa dựa trên việc tìm ước số chung lớn nhất của hai đa thức. Đặc điểm cơ bản của các thuật toán này là chúng ở dạng lặp, dễ thực hiện ở dạng phần mềm, nhưng khó thực hiện khi thiết kế phần cứng, tốc độ giải mã không cao. 2. Tính cấp thiết Các phương pháp đại số giải mã BCH yêu cầu phải giải phương trình khóa bậc cao trên trường Galoa. Các thuật toán lặp BMA, EA và thủ tục tìm kiếm Chien có độ trễ xử lý lớn khi n và t tăng, điều đó hạn chế việc ứng dụng mã BCH vào các hệ thống thông tin thời gian thực. Mặt khác trong các hệ thống truyền tin, các hệ thống xử lý, lưu trữ thông tin thường xảy ra lỗi ở cả dạng lỗi ngẫu nhiên và lỗi chùm. Một số mã khối tuyến tính có khả năng đồng thời sửa được cả lỗi ngẫu nhiên và lỗi chùm như mã tầng, mã Fire biến thể, mã có xáo trộn… tuy nhiên việc giải mã chúng thường khá phức tạp, tốc độ mã hóa thấp hoặc khả năng sửa lỗi không lớn. Trên cơ sở nghiên cứu cấu trúc của mã BCH và các biến thể của nó, xây dựng một tham số mới là chuẩn syndrome. Chuẩn syndrome là bất biến với tác động của nhóm phép thế dịch vòng và chuẩn syndrome của các nhóm khác nhau thì khác nhau. Khi sử dụng chuẩn syndrome, các lỗi ngẫu nhiên và lỗi chùm có thể được sửa đồng thời do chuẩn syndrome của các vector lỗi ngẫu nhiên và một số cấu hình lỗi chùm độ dài nhỏ, lỗi chùm đồng pha không trùng nhau khi chọn đa thức sinh của trường một cách thích hợp. Trên cơ sở chuẩn syndrome, quá trình nhận 2 dạng lỗi có thể thực hiện khá thuận tiện làm giảm độ phức tạp xử lý lỗi đồng thời tăng hiệu quả giải mã. Do đó đề tài “Xây dựng phƣơng pháp giải mã theo chuẩn syndrome trên cơ sở nhận dạng lỗi’’ có tính cấp thiết và tính ứng dụng thực tiễn cao. 3. Đối tƣợng nghiên cứu: - Nhóm các phép thế dịch vòng, phép thế cyclotomic. - Các mã BCH, Reed-Solomon và các biến thể. 4. Mục đích nghiên cứu: - Nghiên cứu đặc điểm cấu trúc của mã BCH. - Nghiên cứu xây dựng thuật toán, thiết bị giải mã dựa trên chuẩn syndrome. - Nghiên cứu xây dựng phương pháp nhận dạng vector lỗi dựa trên chuẩn syndrome để nâng cao hiệu quả sửa lỗi của mã. 5. Nhiệm vụ nghiên cứu: - Nghiên cứu về mã BCH, Reed-Solomon. - Nghiên cứu nhóm các phép thế dịch vòng và tính chuẩn syndrome cho các mã BCH, Reed-Solomon và các biến thể. - Nghiên cứu phương pháp nhận dạng vector lỗi theo chuẩn syndrome. - Nghiên cứu thiết bị giải mã mã BCH và các biến thể, mã ReedSolomon trên cơ sở nhận dạng lỗi theo chuẩn syndrome. - Nghiên cứu phương pháp nén chuẩn syndrome và nhận dạng lỗi khi sửa lỗi bội cao. 6. Phƣơng pháp nghiên cứu: Phương pháp nghiên cứu cơ bản là kết hợp phương pháp giải tích và phương pháp mô phỏng Monte-Carlo trên Matlab có sử dụng các công cụ toán học của lý thuyết xác suất thống kê, lý thuyết nhóm... đồng thời sử dụng các công nghệ thiết kế, chế tạo phần cứng như công nghệ FPGA để thiết kế thiết bị giải mã. 7. Ý nghĩa khoa học và thực tiễn: Ý nghĩa khoa học: Xây dựng phương pháp thế giải mã mã BCH và các biến thể dựa trên chuẩn syndrome, phương pháp giải mã dựa trên việc kết hợp phép thế cyclotomic và phép thế dịch vòng khi sửa lỗi bội cao. Xây dựng phương pháp nhận dạng vector lỗi theo chuẩn syndrome với các dạng lỗi khác nhau, cho phép mở rộng khả năng sửa lỗi của mã. Ý nghĩa thực tiễn: Đề xuất sơ đồ cấu trúc thiết bị giải mã mã BCH và các biến thể, mã Reed-Solomon trên cơ sở nhận dạng lỗi theo chuẩn syndrome. Thiết bị mã hóa, giải mã thực hiện trên thiết bị logic lập trình 3 được có mức tác động nhanh cao và độ phức tạp thấp hơn các bộ giải mã đại số thông thường. 8. Bố cục luận án: Luận án chia thành 03 chương. Chương 1: Tổng quan về mã BCH. Chương 2: Phương pháp chuẩn syndrome giải mã mã BCH. Chương 3: Mở rộng khả năng sửa lỗi của mã BCH sử dụng phương pháp chuẩn syndrome. Ngoài ra luận án gồm có phần mở đầu, kết luận, danh mục các công trình nghiên cứu đã công bố của tác giả, tài liệu tham khảo và phụ lục. CHƢƠNG 1: TỔNG QUAN VỀ MÃ BCH 1.1. Tổng quan về mã khối tuyến tính Một mã khối có chiều dài n gồm qk từ mã được gọi là mã tuyến tính (n,k) khi và chỉ khi qk từ mã hình thành một không gian vector con k chiều của không gian vector gồm tất cả các vector n thành phần trên GF(q). Đối với xác suất lỗi bit có thể sử dụng giới hạn sau: n n Pb   i  t   p i 1  p ni (1.14) i t 1 n  i  Với mã tuyến tính nhị phân hệ thống truyền qua kênh AWGN, xác suất bit lỗi có giới hạn trên như sau: n   Pb   wAw Q 2wR Eb  (1.20)   n N wd o   1.2. Mã BCH 1.2.1. Một số khái niệm cơ bản 1.2.2. Mã BCH nhị phân Mã BCH nhị phân là mã vòng được xây dựng bởi các không điểm của đa thức sinh. Một mã BCH nhị phân có khoảng cách cấu trúc δ  2t + 1 là một mã vòng mà đa thức sinh g(x) có 2t lũy thừa liên tiếp của α là nghiệm  b ,  b1 , ...,  b 2t . 1.2.3. Mã BCH không nhị phân và mã Reed–Solomon Mã BCH nhị phân có thể được tổng quát thành mã không nhị phân. Đa thức sinh g(x) của mã BCH q - phân sửa t lỗi là một đa thức bậc thấp nhất với hệ số thuộc trường GF(q) và có các phần tử  b ,  b1 , ...,  b 2t là nghiệm. Nếu q  2 thì nhận được mã BCH nhị phân. Lớp con đặc biệt của mã BCH q phân với s  1 là lớp con quan trọng nhất. Mã của lớp con này được gọi là mã Reed–Solomon (mã RS). Mã RS sửa t lỗi dùng các ký hiệu thuộc trường Galoa GF(q) có những tham số sau: độ dài khối: n  q – 1; số symbol kiểm tra: n – k  2t; khoảng cách tối thiểu: d  2t + 1 4 1.3. Các phƣơng pháp giải mã mã BCH + Thuật toán Berlekamp–Massey (BMA); + Thuật toán Euclid (EA); + Phương pháp bẫy lỗi; + Phương pháp thế. 1.4. Đặt vấn đề nghiên cứu 1.4.1. Nghiên cứu xây dựng phƣơng pháp chuẩn syndrome giải mã mã BCH và các biến thể trên cơ sở nhận dạng lỗi Vấn đề nghiên cứu thứ nhất của luận án là xây dựng phương pháp giải mã mã BCH và biến thể dựa trên chuẩn syndrome cho phép xác định vector lỗi theo chuẩn syndrome, không cần giải phương trình khóa. Vấn đề nghiên cứu thứ hai của luận án là xây dựng phương pháp kết hợp phép thế cyclotomic và phép thế dịch vòng để giải mã mã BCH cho phép rút gọn các tập vector lỗi cần xử lý. 1.4.2. Nghiên cứu mở rộng khả năng sửa lỗi của mã BCH và các biến thể sử dụng phƣơng pháp chuẩn syndrome trên cơ sở nhận dạng lỗi Vấn đề nghiên cứu thứ ba của luận án là mở rộng khả năng sửa lỗi của mã BCH, Reed-Solomon và các biến thể, cho phép đồng thời sửa lỗi ngẫu nhiên và lỗi chùm trên cơ sở nhận dạng lỗi theo chuẩn syndrome. 1.5. Kết luận chƣơng 1 Các kết quả chương 1 bao gồm: (1) Nghiên cứu tổng quan mã khối tuyến tính, mã BCH và các phương pháp giải mã mã BCH nhị phân và không nhị phân, mã Reed-Solomon dựa trên thuật toán Berlekamp–Massey, thuật toán Euclid. (2) Nghiên cứu phương pháp bẫy lỗi và phương pháp thế giải mã mã BCH nhị phân. CHƢƠNG 2: PHƢƠNG PHÁP CHUẨN SYNDROME GIẢI MÃ MÃ BCH 2.1. Phân loại dịch vòng vector lỗi Ký hiệu σ là phép thế dịch vòng, vector lỗi e  (e1, e2, …, en) dịch vòng phải đi một vị trí σ(e)  (en, e1, e2, e3, …, en-1). Tập hợp tất cả các vector khác nhau đôi một σm(e) với 0 ≤ m ≤ n – 1 của vector lỗi e tùy ý gọi là σ-orbit của nó, mỗi σ-orbit có một vector sinh. Với một số λ tự nhiên nhỏ nhất nào đó, 1 < λ < n, σ-orbit chứa λ phần tử, với λ  n hoặc λ là ước của nó, σ-orbit có cấu trúc sau: 5  (e)  e  e, (e),...,  1 (e) (2.2) Tất cả các vector của σ-orbit có cùng đường kính, với hai vector lỗi tùy ý e và e’ thì các σ-orbit , hoặc là trùng nhau hoặc không giao nhau. Khi n  15, có 105 vector lỗi trọng số 2 chia thành 7 lớp với đường kính lỗi từ 2 đến 8 như minh họa trong bảng 2-1. Bảng 2-1. Các σ-orbit, đường kính, tọa độ vector lỗi bội 2 với chiều dài n=15 Các lớp σ-orbit I2 I3 I4 I5 I6 I7 I8 Đường kính lỗi D 2 3 4 5 6 7 8 Tọa độ vector sinh lỗi e 1,2 (110000000000000) 1,3 (101000000000000) 1,4 (100100000000000) 1,5 (100010000000000) 1,6 (100001000000000) 1,7 (100000100000000) 1,8 (100000010000000) 2.2. Xây dựng phƣơng pháp chuẩn syndrome cho mã BCH và các biến thể 2.2.1. Phƣơng pháp chuẩn syndrome giải mã mã BCH Ma trận kiểm tra của mã BCH với khoảng cách cấu trúc δ có dạng: 1  1 H  ...   1  H   bi , b  b1  2b  2( b1) ... ... ... ...  b 2  2 (b 2 ) ...  ( n1) b    ( n1)( b1)  ...  ( n 1)( b   2 )    ... 5 (2.3)  ( b1) i , ....  (b 2 ) i  T với 0 ≤ i ≤ n – 1,  là căn bậc n của 1. Cho mã BCH có ma trận kiểm tra như biểu thức (2.3), với syndrome S(e)  (s1, s2, …, sδ-1), khi đó: S ( (e))  ( b s1 ,  b1s2 ,...,  b 2 s 1 ). (2.4) Tổng quát khi sử dụng (2.4) λ lần ta có: S ( (e))  ( b s1 ,   (b1) s2 ,...,   (b 2) s 1 ),  0    n  1. (2.5) Đối với mã BCH có ma trận kiểm tra như biểu thức (2.3) 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: 6 ( b s1 ,   (b1) s2 ,...,   (b 2) s 1 ), 0    n  1. (2.6) Định nghĩa 2.1. Chuẩn syndrome của vector lỗi e với mã C (có ma trận kiểm tra (2.3)) là vector: N(S(e))  (N12, N13, …, N 1(δ-1), N23, ..., N Nij, 1≤ i < j ≤ δ - 1 tính theo công thức: (δ-2)(δ-1)) có C21 tọa độ Nij  s j (bi 1)/ hij / si (b j 1)/ hij , hij  USCLN (b  i  1, b  j  1) (2.7) Trong đó: Nij = ∞ nếu sj ≠ 0, si = 0. Nij = - (không xác định) khi sj = si = 0. Đối với mã nhị phân q  2, ma trận kiểm tra của mã BCH nhị phân theo nghĩa hẹp (b = 1) với δ  2t + 1 có dạng:  H  i,  3i , ....  ( 2t 1)i  , 0  i  n  1. T (2.8) 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). Đối với BCH mã nhị phân với ma trận kiểm tra (2.8) ta có; S ( (e))  ( s1 ,  3 s2 ,...,  2t 1st ). (2.9) Với mã BCH nhị phân nguyên thủy theo nghĩa hẹp, b  1, m     phần tử nguyên thủy của trường GF(2 ) và ma trận kiểm tra có dạng:   H   i ,  3i , ....  ( 2t 1)i , 0  i  n  1, n  2 m  1. T (2.10) Trường hợp mã BCH nhị phân nguyên thủy theo nghĩa hẹp có ma trận kiểm tra (2.10) đố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: ( i s1 , 3i s2 ,..., i ( 2t 1) st ), 0    2 m  2. (2.11) Định nghĩa 2.2. Gọi chuẩn (norm) của syndrome S(e)  (s1, s2, …, st) với mã nguyên thủy theo nghĩa hẹp là vector N(S) có Ct2 tọa độ Nij, 1≤ i < j ≤ t tính theo công thức: ( 2i 1) / hij N ij  s j ( 2 j 1) / hij / si , hij  USCLN (2i  1,2 j  1) . (2.12) Nij = ∞ nếu sj ≠ 0, si = 0; Nij = - (không xác định) khi sj = si = 0. Ví dụ với mã BCH nhị phân có d  7, chuẩn syndrome gồm 3 thành phần: 7 N1  s2 / s13 , N 2  s3 / s15 , N 3  s33 / s25 . Tính chất cơ bản của chuẩn syndrome là tính bất biến của nó với phép thế dịch vòng. N (S ( (e)))  N (S (e)) . (2.13) Định nghĩa 2.3. Norm của σ-orbit J là chuẩn syndrome của một vector tùy ý trong J và ký hiệu là N(J). Định lý 2.1. Cho K là tập σ-orbit tùy ý các vector lỗi nhị phân có phổ syndrome đầy đủ với mã BCH có khoảng cách mã 2t + 1 trên trường GF(2m) và có chuẩn syndrome khác nhau đôi một. Nếu biết rằng từ mã nhận được chứa vector lỗi thuộc tập K thì mã đã cho sửa được lỗi này. Để thực hiện giải mã dựa trên chuẩn syndrome cần ba bộ nhớ ROM lưu trữ các thông tin sau: - P1 = {N(I1), N(I2), ..., N(It)}– tập chuẩn syndrome của các σorbit I1, I2, ..., It của tập cần giải mã K (ROM 1). - P2 = {e01, e02, ..., e0t} – tập các vector sinh của các vector lỗi cho mỗi lớp I1, I2, ..., It (ROM 2). - P3 = {S11-1, S12-1, ..., S1t-1} – tập các phần tử của trường Galoa (ROM 3), trong đó s1j – thành phần syndrome đầu tiên của vector lỗi ei trong P2 (nếu s1(t) = 0, N(It) = ∞, thì thay cho s1t-1 ghi s2t-1 cho thành phần thứ 2 là s2t của S(et)). Thuật toán giải cho giải mã theo phương pháp chuẩn syndrome thực hiện tính toán qua các bước như sau: + Tính syndrome S(e)  (s1, s2, …, st) với si là phần tử của trường Galoa GF(2m). + Tính bậc của chuẩn syndrome N. Tính degsj, degsi là bậc thành phần si, sj của syndrome S(e)  (s1, s2, …, si, ..., sj, ..., st) với 1≤ i < j ≤ t. Chuẩn syndrome của syndrome S(e) tính theo công thức (2.12): ( 2i 1) / hij ( 2 j 1) / hij N ij  s j / si , hij  USCLN (2i  1,2 j  1) . DegNij  {degsj.(2i – 1)/hij – degsi.(2j – 1)/hij } mod n. + Theo degNij xác định vector sinh và bậc i0 của thành phần syndrome đầu tiên s10 ứng với vector sinh. + Tính số thứ tự bit lỗi đầu tiên bằng Li  (degsi – degs10) mod n. + Tìm vector lỗi e bằng cách dịch vòng vector sinh đi Li nhịp. + Sửa tín hiệu nhận được bằng cách tổng tín hiệu nhận được với vector lỗi tìm được. 8 2.2.2. Phƣơng pháp chuẩn syndrome giải mã mã thuận nghịch Cho mã thuận nghịch C5 có ma trận kiểm tra dạng T i j H   z ,   z  , chuẩn syndrome S  (s1, s2)  (  ,  ) là tích các m thành phần của syndrome trong trường GF(2 ). N  s1.s2 =   i+j    (2.15) Với   T  {–  , 0, 1, 2, …, n – 1}. Bậc  được gọi là bậc của chuẩn syndrome N và được ký hiệu degN: (2.16) deg N  (i  j ) mod n . Khi phân hoạch theo các σ-orbit, chuẩn syndrome tương ứng với các lỗi ngẫu nhiên và một số dạng lỗi phụ thuộc không trùng nhau. Ví dụ mã thuận nghịch có độ dài 31, d  5, với phần tử nguyên thủy α là nghiệm của đa thức x5 + x2 + 1 ngoài các lỗi bội 1, 2 còn sửa được các vector lỗi bội 3 với các vị trí lỗi thỏa mãn i2 – i1  i3 – i2. Chuẩn syndrome N với mã thuận nghịch C trên GF(2m) chỉ nhận các giá trị thuộc GF(2m), bậc chuẩn syndrome degN có giá trị tùy ý trong T. Gọi ID là lớp lỗi bội 2, đường kính D chứa lỗi tại vị trí 1 và D. Chuẩn syndrome của các lớp lỗi bội 2 và lỗi đơn không giao nhau, nên có thể giải mã mã thuận nghịch theo phương pháp chuẩn syndrome. Cho P1     1,  ,...,  1 tập các chuẩn syndrome của các lớp tương đương I1, I2, ..., Iv+1 với các lỗi bội 1, 2 (ROM 1) P2   21 , 31 ,..., v11, i  1   i 1 (ROM 2) Thành phần đầu tiên của syndrome của các lỗi bội 2 có vị trí thứ nhất tại i. Thuật toán giải mã mã thuận nghịch gồm các bước sau: + Tính syndrome S = (si, sj) = (αi, αj) + Tính chuẩn syndrome N(S) = αi . αj + So sánh N(S) với các phần tử của ROM 1, nếu N(S) = 1 xảy ra lỗi đơn tại vị trí i +1. Nếu N(S) thuộc P1 nghĩa là: N S      P1 với D >1 thì xảy ra lỗi bội 2 có đường kính D. + Với D tìm được và  D1  P2 tính s1.  D1    - bộ định vị, chỉ ra lỗi ở vị trí thứ   1 + Vị trí thứ 2 của lỗi   1 D mod n + Sửa lỗi bằng cách lấy tổng của vector lỗi e và vector nhận được r. 1 D 2 v 9 2.2.3. Phƣơng pháp chuẩn syndrome giải mã mã Reed-Solomon Mã RS có khoảng cách cấu trúc δ, ma trận kiểm tra H: I b  2b  3b  I  b1  2b1  3b1 H       b   2 2 b   2  3b   2     I   n1b    n1b1    n 1b  2         (2.17) Tương tự với mã BCH tổng quát, chuẩn syndrome Nij của các thành phần syndrome được tạo thành từ ma trận kiểm tra (2.17) sẽ được tính theo công thức: b i 1 / hij Sj (2.18) N ij  b j 1 / hij Si Trong đó hij là ước số chung lớn nhất của i và j 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ã RS sửa 1 lỗi modul, chuẩn syndrome có thể tính như sau: NM  S2 . S1 (2.26) 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 chuẩn syndrome NM theo công thức (2.26). - 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 giá trị S1 . - Sửa tín hiệu nhận được bằng cách lấy tổng tín hiệu nhận được với vector lỗi tìm được: v = r + e. Mã RS có thể ánh xạ sang mã nhị phân, ví dụ mã RS(7,3) với d = 5, với thành phần nguyên thủy  là nghiệm của đa thức x3  x  1, có khả năng sửa 2 lỗi modul ma trận kiểm tra dạng: I I  I  I I  I h1 h 2 h 3  h 6  i i i 1  i2  (2.27)  , h    H  2 4 6 12 I h h h  h   3 6 9 18  I h h h  h  10 Các thành phần chuẩn syndrome được xác định như sau: S S3 S4    ( N1 N 2 N3 ) N   2 S2 S3   S1 (2.28) 2.2.4. Sơ đồ cấu trúc thiết bị giải mã mã BCH theo phƣơng pháp chuẩn syndrome Sơ đồ cấu trúc bộ giải mã theo phương pháp chuẩn syndrome với d = 5 trên hình 2-2 gồm 6 khối: KTS – khối tính syndrome; khối tính chuẩn syndrome; khối tính số lượng của sự dịch vòng; khối tính toán vector sinh trong σ-orbit; khối tính vector lỗi hiện thời; mạch sửa. r KTS Khối tính N norm Khối tính vector sinh e0 Khối tính vector lỗi hiện thời e Mạch sửa v Khối tính lượng dịch vòng Hình 2-2 Sơ đồ cấu trúc bộ giải mã dựa trên chuẩn syndrome 2.2.5. Sơ đồ cấu trúc thiết bị giải mã mã RS theo chuẩn syndrome Xét mã RS nhị phân (21, 15) với ma trận kiểm tra có dạng: I3 I3 I3 I3 I3 I3  I H =  30 h1 h 2 h 3 h 4 h 5 h 6  h 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 H =                       0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 0 6 0 1                       Trên hình 2-6 trình bày sơ đồ cấu trúc của thiết bị giải mã mã RS theo phương pháp chuẩn syndrome. Thiết bị giải mã bao gồm khối tính syndrome (KTS), khối các mạch AND, khối mạch sửa (MS), khối xác định số hiệu modul lỗi (KXĐML). Các đầu vào của khối tính syndrome và các đầu vào thứ nhất của MS được nối với nhau và là đầu vào của 11 thiết bị giải mã. Các đầu ra thứ nhất của KTS được nối với đầu vào thứ nhất của khối các mạch AND và các đầu vào thứ nhất của KXĐML, các đầu vào thứ hai của khối được nối với các đầu ra thứ hai của KTS. Các đầu ra của KXĐML được nối với đầu vào thứ hai của khối các mạch AND, đầu ra của khối các mạch AND được nối với đầu vào thứ hai của MS, đầu ra MS là đầu ra của thiết bị giải mã. S2 Khối tính syndrome S1 Mạch “AND” r Mạch sửa М М 2 2М М 2 М 2 2М М 2 2 Hình 2-6 Sơ đồ cấu trúc thiết bị giải mã mã Reed-Solomon & & & & & & & Khối xác định số hiệu modul lỗi S1 DC 1 0 1 2 3 4 5 6 S2 DC 2 0 1 2 3 4 5 6 LA degN =0 degN = 1 degN = 2 degN = 3 degN = 4 degN = 5 degN = 6 Hình 2-7 Sơ đồ chức năng khối xác định modul lỗi v 12 Trên hình 2-7 trình bày một trong các phương án thực hiện khối xác định số hiệu modul lỗi thực hiện trên thiết bị logic lập trình được. Khối này bao gồm các bộ giải mã DC1, DC2 để xác định i, j và mảng logic (LA). Các đầu vào của khối được nối đến khối KTS, trên đầu ra của các bộ giải mã DC1, DC2 tạo ra tín hiệu tương ứng với các giá trị i, j, chúng được đưa đến mảng logic. Trên đầu ra của mảng logic tạo ra tín hiệu logic 1 phụ thuộc vào giá trị degN = (j-i) mod n, do đó tại đầu ra của khối sẽ có tín hiệu tương ứng với số hiệu modul lỗi. 2.3. Kết hợp phƣơng pháp chuẩn syndrome và phép thế cyclotomic 2.3.1. Tác động của phép thế cyclotomic lên không gian vector lỗi Phép thế cyclotomic theo modul n với trường GF(q) là tập hợp: (2.29) Cs  s, sq, sq2 , ..., sqm 1, sqm  s mod n Định nghĩa 2.4. Trên tập T = {1, 2, ..., n} biến đổi υ thỏa mãn υ(i) = 2i-1 mod n khi đánh số tọa độ vector lỗi từ 1 đến n. Với n lẻ, υ là song ánh trên tập T. Khi đánh số tọa độ của vector lỗi 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 Φ. s s 1 2 3 4 5 6 7 0 1 1 1 0 0 0 φ(e): 0 0 1 0 1 0 1 0 1 0 0 1 1 0 e =φ3(e): 0 1 1 1 0 0 0 e: φ2(e): Hình 2-8 Tác động của phép thế cyclotomic với vector e = 0111000 2.3.2. Giải mã theo chuẩn syndrome dựa trên phép thế cyclotomic Với n = 31 trong trường GF(2) tồn tại 6 lớp cyclotomic như sau: {1, 2, 4, 6, 8, 16}; {3, 6, 12, 24, 17}; {5, 10, 20, 9, 18}; {7, 14, 28, 25, 19}; {11, 22, 13, 26, 21}; {15, 30, 29, 27, 23}. Trên bảng 2-9 biểu diễn giá trị chuẩn syndrome của các lỗi bội 2 (15 lớp vector) với mã có chiều dài 31, với đa thức sinh của trường x5 + x3 + x2 + x + 1. 13 Bảng 2-9. Vector sinh lỗi bội 2 của các lớp dịch vòng và chuẩn syndrome STT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N 3 6 14 12 30 28 19 24 23 29 27 25 15 7 17 Vector sinh e0 1100000000000000000000000000000 1010000000000000000000000000000 1001000000000000000000000000000 1000100000000000000000000000000 1000010000000000000000000000000 1000001000000000000000000000000 1000000100000000000000000000000 1000000010000000000000000000000 1000000001000000000000000000000 1000000000100000000000000000000 1000000000010000000000000000000 1000000000001000000000000000000 1000000000000100000000000000000 1000000000000010000000000000000 1000000000000001000000000000000 Chuẩn syndrome của các vector lỗi bội 2 thuộc 3 lớp cyclotomic ({3, 6, 12, 24, 17}; {7, 14, 28, 25, 19}; {15, 30, 29, 27, 23}). Với các mã C5 có đa thức sinh khác cũng phân phối chuẩn syndrome của các lỗi bội 2 thành 3 lớp cyclotomic. Số lượng các tổ hợp chọn lọc có thể rút gọn 5 lần so với mã C5. Ký hiệu chuẩn syndrome của vector sinh của phần tử đầu tiên trong các lớp cyclotomic là Nao, Nbo, Nco (trong ví dụ trên Nao = 3, Nbo = 7, Nco = 15). Phương pháp giải mã dựa trên phép thế cyclotomic với mã C5 như sau: + Tính syndrome S và chuẩn syndrome N của tổ hợp nhận được. + So sánh giá trị N với mỗi giá trị Nao, Nbo, Nco, nếu N trùng với một trong các giá trị này sẽ xác định lớp cyclotomic mà N thuộc về lớp đó. + Nếu N không trùng với cả ba giá trị Nao, Nbo, Nco, thực hiện phép dịch cyclotomic và lặp lại bước 2. + Xác định lớp cyclotomic mà N thuộc về lớp đó, theo số lượng phép dịch cyclotomic, xác định giá trị N = Ndịch, vector sinh tương ứng e 0. + Theo giá trị S, N, e0 tính giá trị vector lỗi tức thời. 14 Lưu đồ thuật toán giải mã biểu diễn trên hình 2-9, trong đó N0 xác định phần tử đầu tiên của các lớp cyclotomic, F1 – hàm tính giá trị N, F2 – hàm tính vector sinh e0, F3 – hàm tính vector lỗi tức thời. Begin r Tính S No Nd= No? Yes Tính N SL phép dịch x=0 Dịch cyclotomic Nd N = F1(Nd,x) eo = F2(No) Nd = N x = x+1 e = F3(S,N,eo) e End Hình 2-9 Lưu đồ thuật toán giải mã C5, dựa trên phép thế cyclotomic. Để tiếp tục giảm độ phức tạp giải mã có thể sử dụng phương pháp xử lý từng bước các lớp cyclotomic. Xét mã C5, n = 31, biểu thức N co  ( N b0  ) mod n  ( N a0  2) mod n , xác định quy tắc chuyển từ một lớp cyclotomic này sang lớp khác. Vì vậy có thể chọn 1 trong 3 phần tử của một lớp cyclotomic và ký hiệu là N0. Quy tắc giải mã theo các bước sau: + Tính syndrome S và chuẩn syndrome N. + Chọn N 0  N a0 . + So sánh N và N0 (N trùng N0 chỉ ra lớp cyclotomic chứa giá trị N tính được). 15 + Nếu N không trùng với bất kỳ phần tử nào của lớp cyclotomic thì giá trị phần tử sinh của lớp cyclotomic N0 tăng lên ∆ và so sánh N với N0. + Xác định lớp cyclotomic chứa giá trị chuẩn syndrome N, theo số lượng phép dịch đã thực hiện xác định giá trị N0 = Ndịch theo bảng giá trị tìm vector sinh e0 tương ứng với chuẩn syndrome. + Theo giá trị S, N và e0 xác định vector lỗi hiện thời, giá trị ∆ được chọn phụ thuộc vào lớp cyclotomic được sử dụng. Lưu đồ thuật toán giải mã theo quy tắc giải mã nêu trên được minh họa trên hình 2-10. Begin r Tính S No No=Nd Yes Tính N Yes No x chứa n syndrome khác nhau đôi một |S(J)| = |J| = n, nghĩa là thành phần S1 nhận mỗi một giá trị khác 0 trong trường GF(2m) đúng 1 lần. Nếu với vector e nào đó thuộc σ-orbit J có S1 = 0 thì tất cả các vector của σ-orbit đó đều có thành phần syndrome thứ nhất bằng 0. 16 Mo,w là liên kết của các σ-orbit của các vector lỗi tạo thành G-orbit. Trong bảng 2-12 trình bày tập hợp M0,3, M0,4 liên kết thành các lớp dịch vòng trong không gian E15 tạo thành bởi các σ-orbit này, vector sinh, syndrome của chúng, thành phần N3 của chuẩn syndrome của mã C7 với đa thức sinh của trường x4 + x +1. 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 thành phần thứ 3 của chuẩn syndrome, khi bổ sung thêm các giá trị degs2 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ị degs2 sẽ được nhân đôi. Bảng 2-12. Vector sinh, syndrome S và chuẩn syndrome N3 của tập hợp hợp M0,3; M0,4 Lớp Số thứ tự Vector sinh Syndrome N3 cyclotomic σ-orbit 8 10 1 (1,12,13) (0, α , α ) α5 Ф1 2 (1,8,10) (0, α1, α5) α10 0 Ф2 3 (1,6,11) (0, α , 0) 0 4 (1,2,3,11) (0, α2, α5) α5 5 (1,3,5,6) (0, α4, α10) α10 Ф3 6 (1,5,9,11) (0, α8, α5) α5 1 10 7 (1,2,6,9) (0, α , α ) α10 11 5 8 (1,3,10,13) (0, α , α ) α5 Ф4 9 (1,4,5,10) (0, α7, α10) α10 12 Ф5 10 (1,2,4,8) (0, α , 0) 0 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. Vector g tạo thành tập M10,w trong M0,w. Trên hình 2-11 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. 17 (1,3) (8,13,5) (1,2) (4,14,10) (1,5) (1,11,10)  14 f (4,15) (0,8,5)  11 (13,12) (0,2,5) (1,4) (14,7,) (1,8) (9,13,10)  6 (1,12,13)  12 4 2 7 (7,14) (0,1,10) (2,5) (0,10,) (8,10) (0,4,10) 5 (6,11) (0,,0) (3,9) (0,5,) (1,8,10) 9 (1,6) (10,,5) (1,7) (13,14,) 8 (1,6,11) 5 (1,4,15)  14 (1,2,5) (1,7,14)  13 (1,3,9) Hình 2-11 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 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 M0,w chỉ có w vector thuộc tập M10,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. 18 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 giá trị 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)). Mã BCH (31, 16) số lượng vector lỗi bội 1, bội 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 M10,3, M10,4 do đó nếu tính đến cả phép dịch vòng thì 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, giảm 3 lần so với phương pháp chuẩn syndrome. 2.4. Kết luận chƣơng 2 Các kết quả chương 2 bao gồm: (1) Nghiên cứu phương pháp giải mã thế mã BCH và các biến thể dựa trên chuẩn syndrome: - Phân loại các vector lỗi theo chuẩn syndrome, tham số đặc trưng bởi cấu trúc của mã BCH. - Nghiên cứu các thuật toán giải mã mã BCH và biến thể dựa trên chuẩn syndrome. (2) Đề xuất sơ đồ cấu trúc thiết bị giải mã theo phương pháp chuẩn syndrome cho mã BCH và các biến thể: - Sơ đồ cấu trúc thiết bị giải mã mã BCH sử dụng các bộ cộng modul và các bộ nhớ ROM, thiết bị giải mã mã BCH, Reed-Solomon trên thiết bị logic khả trình có mức tác động nhanh cao, độ phức tạp thấp. (3) Đề xuất kết hợp phép thế cyclotomic và phương pháp chuẩn syndrome để giải mã mã BCH: - Phương pháp giải mã dựa trên phép thế cyclotomic cho phép rút gọn số tổ hợp cần chọn lọc đến 5, 7, 11 lần với mã C5 có độ dài n = 31, 127, 1047 tương ứng. - Nghiên cứu phương pháp nén chuẩn syndrome giải mã mã BCH. Với mã BCH (31,16) phương pháp đề xuất cho phép giảm độ phức tạp 3 lần so với phương pháp chuẩn syndrome thông thường. Nội dung của chương này đã được công bố trong các công trình CT1, CT2, CT5.