CHƯƠNG 1: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU Nội dung của chương trình bày lý thuyết tổng quan về vành đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic. Các tiêu chuẩn đánh giá mã sửa lỗi cũng được giới thiệu trong chương này. Chương này cũng sẽ tập trung khảo sát các nghiên cứu liên quan đến mã cyclic để từ đó tìm ra các hạn chế của các nghiên cứu trước đây và đề xuất hướng nghiên cứu, phạm vi nghiên cứu và phương thức tiếp cận của luận án. GIỚI THIỆU CHUNG Lý thuyết mã hoá được bắt đầu nghiên cứu từ những năm 1940 và được phát triển theo ba hướng lớn đó là: mã nguồn [7], [17], mã kênh (có khả năng sửa lỗi [35], [74]) và mật mã [8], [63].
Đặt nền móng cho lý thuyết mã hoá là các nghiên cứu của Shannon trong hai năm 1948-1949 về độ tin cậy của truyền tin trên các kênh truyền có nhiễu [59]. Khởi đầu cho việc thiết kế các bộ mã tốt và các phương pháp giải mã hiệu quả đó là mã Hamming, mã Golay [59] và các mã khác vào cuối những năm 1940. Các nghiên cứu về mã hóa những năm 1950, 1960 tập trung vào việc phát triển lý thuyết về các mạch mã hóa và giải mã hiệu quả. Trên thực tế, các sơ đồ mã hoá và giải mã hiện nay đều không thoả mãn giới hạn của Shannon, nhưng bộ giải mã có độ phức tạp (giá thành) thấp hơn.
Vì lý do này, các hướng nghiên cứu tập trung vào việc thiết kế các sơ đồ mã hoá và giải mã với mục tiêu dễ dàng thực hiện về mặt kỹ thuật. Các nghiên cứu của Reed và Solomon (1960), Hocquenghem (1959), Bose và Chaudhuri (1960), Gorenstein và Zierler (1961) và Peterson (1961) đều tập trung theo hướng này [45], [59], [74]. Bằng cách kết hợp mỗi con số của mã với một phần tử trong trường Galois, có thể tìm được phương trình đại số mà các nghiệm của nó mô tả vị trí của các lỗi. Do đó, độ phức tạp tính toán khi giải mã cũng giảm đi bằng cách thiết lập các phương trình đại số và tìm nghiệm của chúng.
6 Trong những năm gần đây các nghiên cứu về lý thuyết mã tập trung vào việc xây dựng các phương pháp mã hóa đạt được giới hạn của Shannon bao gồm các hướng: điều chế mã lưới - TCM (Trellis Coded Modulation), mã Turbo [61], mã kiểm tra chẵn lẻ mật độ thấp - LDPC (Low-Density Parity Check) [32], mã khối không gian-thời gian – STBC (Space-Time Block Code) [47]. Các quan điểm xây dựng mã cũng rất phong phú: dựa trên các cấu trúc đại số, dựa trên lý thuyết dàn, dựa trên hình học – đại số, dựa trên hình học chiếu, dựa trên lý thuyết tổ hợp, dựa trên Graph. Các phương pháp giải mã chính được nghiên cứu bao gồm: giải mã ngưỡng của Messey [51], giải mã liên tiếp của Zigalgirov, giải mã Viterbi [7], giải mã hợp lý tối đa [54], giải mã lặp và giải mã có liên hệ ngược, giải mã đại số [7]. Các công trình nghiên cứu cho thấy, các mã sửa lỗi (ECC - Error Correcting Code) là hướng kiến thiết cho định lý tồn tại là định lý mã hoá thứ hai của CE.
Hướng nghiên cứu chủ đạo ở đây là xây dựng các mã trên các cấu trúc đại số khác nhau như nhóm, vành, trường, module, không gian tuyến tính [69], [74]. Một trong các lớp mã quan trọng của mã khối tuyến tính đó là các mã cylic, trong đó thành tựu nổi bật nhất và được ứng dụng rộng rãi nhất trong thực tế là các mã cyclic trên vành đa thức [17], [59]. Mã cyclic được Eugene Prange nghiên cứu đầu tiên năm 1957 [65]. Sau đó quá trình nghiên cứu về mã cyclic tập trung theo cả hai hướng sửa lỗi ngẫu nhiên và sửa lỗi cụm.
Nhiều lớp mã cyclic đã được xây dựng trong những năm này, bao gồm các mã BCH (Bose, Chaudhuri, and Hocquenghem), các mã Reed-Solomon, các mã hình học Euclid [74], [77]. Mã cyclic gồm các từ mã là bội của đa thức sinh g ( x) , với g ( x) | ( x n 1) [74]. Từ mã hay đa thức mã a( x) của mã cyclic là một phần tử của ideal g ( x) thoả mãn điều kiện a ( x) g ( x) [59]. Một tính chất quan trọng rất thuận lợi cho việc mã hoá và giải mã cho các mã cyclic là dịch vòng của một đa thức mã cũng là một đa thức mã 7 [59], [7].
Các mã cyclic được ứng dụng rất rộng rãi trong thực tế. Rất nhiều đa thức sinh cụ thể đã được sử dụng trong các chuẩn truyền tin [74]. Các thiết bị mã hoá và giải mã trong thực tế được thực hiện rất đơn giản bằng các bộ ghi dịch tuyến tính có liên hệ ngược [51]. Có thể đánh giá rằng các nghiên cứu về mã cyclic đã được hoàn thiện vào những năm 70 của thế kỷ 20 [77].
Mặc dù có nhiều ưu điểm nhưng có thể nhận thấy một số hạn chế của mã cyclic như sau: Mã cyclic (n, k ) chủ yếu được xây dựng cho các giá trị n lẻ, số các đa thức sinh có thể được lựa chọn để tạo các mã tốt không nhiều và phụ thuộc vào số ideal có thể xây dựng. Nếu phân tích nhị thức x n 1 thành tích của các đa thức bất khả qui thì khả năng lựa chọn rất thấp khi không có nhiều đa thức bất khả qui. Điều này đặc biệt thấy rõ đối với các vành đa thức có hai lớp kề cyclic (với n = 3, 5, 11, 13, 17, 19,…), các vành này không thể xây dựng được các mã cyclic tốt ngoài hai mã tầm thường duy nhất là mã (n, n 1) (mã kiểm tra chẵn) và mã (n,1) (mã lặp) [1]. Các hạn chế này có thể xem là do tính chặt chẽ về cấu trúc của mã cyclic.
Ngược lại, với mã ngẫu nhiên tuyến tính của Shannon ta thấy không có những hạn chế này. Shannon đã chứng minh rằng luôn tồn tại các mã tốt thỏa mãn định lý mã hóa thứ hai. Tuy nhiên do tính lỏng lẻo về mặt cấu trúc nên rất khó khăn cho việc thực hiện mã hóa và giải mã có hiệu quả cho các mã này. Cần chú ý thêm là việc nghiên cứu các ideal trên vành số đã xây dựng được các mã AN-cyclic [74] được sử dụng có hiệu quả trong kỹ thuật máy tính.
Phần tiếp theo luận án sẽ trình bày một số nội dung lý thuyết về mã tuyến tính, cơ sở lý thuyết về mã cyclic xây dựng trên vành đa thức. Một số khái niệm cơ bản Định nghĩa 1.1: R là một vành giao hoán, một đa thức của biến x trên vành R là một biểu thức có dạng [7]: n 1 f ( x) f i xi (1.1) i 0 8 Trong đó: f i – là hệ số, fi R. Trong trường GF (2) , f i nhận giá trị 0 hoặc 1. x – biến, ẩn hình thức.
Bậc của đa thức f ( x) là: deg f ( x) n 1 f ( x) được gọi là định chuẩn nếu hệ số cao nhất của nó f n 1 1. Nếu f i 0 với i 0 n 1 , thì f ( x) được gọi là đa thức 0.2: Cho R là một vành giao hoán, vành đa thức R[ x] là một vành được tạo bởi tập tất cả các đa thức của biến x có các hệ số trong R. Hai phép toán là phép cộng và phép nhân đa thức theo modulo ( x n 1) [7], [63]. Khi các hệ số của đa thức nằm trong trường nhị phân GF (2) , phép cộng và phép trừ là tương đương, vành đa thức được ký hiệu 2 [ x] / ( x n 1).
Trong trường nhị phân, vành đa thức ký hiệu: ( f ( x); , ) 2 [ x] / ( x n 1). ( f ( x), ) là một nhóm đối với phép cộng, thỏa mãn tiên đề của nhóm. n 1 n 1 * Phép cộng hai đa thức: Xét hai đa thức a( x) ai x i và b( x) bi xi , đa i 0 i 0 thức c( x) là tổng của hai đa thức này và được tính như sau: n 1 c( x) a( x) b( x) với c( x) ci xi và ci ai bi (1.2) i 0 Phép cộng các hệ số ai và bi được thực hiện trên trường (cộng theo modulo).3) i 0 j 0 * Đa thức bất khả quy: Định nghĩa 1. Như vậy đa thức bất khả quy là đa thức không thể phân tích được thành tích của các đa thức có bậc nhỏ hơn.1: Bất kỳ đa thức bất khả quy nào trên trường GF (2m ) đều là ước của x 2 1 1 [7].
* Đa thức đối xứng: Định nghĩa 1. Dựa vào tính chất của lũy đẳng nuốt, ta có: a x en x a x * Vành đa thức có hai lớp kề cyclic: Định nghĩa 1.6: Vành đa thức theo modulo x n 1 được gọi là vành đa thức có hai lớp kề cyclic nếu phân tích của x n 1 dưới dạng tích các đa thức bất khả quy trên trường GF(2) có dạng [1]: n 1 x n 1 ( x 1) xi (1.5) i 0 10 n 1 trong đó, ( x 1) và en ( x) xi là các đa thức bất khả quy. i 0 Nhận xét: - Vành đa thức 2 [ x] / ( x n 1) có hai lớp kề cyclic là vành đa thức mà trong đó chỉ có 2 chu trình (mục 1. - Vì en ( x) là một đa thức bất khả quy nên n phải là một số lẻ.1: Vành đa thức theo modulo x n 1 là một vành đa thức có hai lớp kề cyclic nếu n thoả mãn [1]: n phải là một số nguyên tố; phần tử 2 phải thoả mãn điều kiện 2 ( n)/ p 1mod n với mỗi ước nguyên tố p của (n) , với (n) là hàm phi Euler.
Căn cứ vào đặc điểm trên của vành đa thức có hai lớp kề cyclic, tác giả của [1] đề xuất một thuật toán xác định giá trị n thỏa mãn vành đa thức có hai lớp kề cyclic. Ví dụ, các số n nhỏ hơn 1000 thoả mãn điều kiện 2 [ x] / ( x n 1) là một vành đa thức có 2 lớp kề cyclic được liệt kê trong Bảng 1.