Tài liệu Các mã xyclic xây dựng trên các nhóm nhân xyclic theo mudulo

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- TÊN HỌC VIÊN: TRẦN ĐỨC QUYỀN TÊN LUẬN VĂN: CÁC MÃ XYXLIC XÂY DỰNG TRÊN CÁC NHÓM NHÂN XYCLIC THEO MODULO CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ MÃ SỐ: 60.52.70 LUẬN VĂN THẠC SỸ KỸ THUẬT Người hướng dẫn khoa học: GS.TS. Nguyễn Bình ĐÀ LẠT - Năm 2009 2 Luận văn được hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông Tập đoàn Bưu chính Viễn thông Việt Nam Người hướng dẫn khoa học: GS.TS. Nguyễn Bình Phản biện 1: …………………………………………………… …………………………………………………… Phản biện 2: …………………………………………………… …………………………………………………… Phản biện 3: …………………………………………………… …………………………………………………… Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... năm 2009 Có thể tìm hiểu luận văn tại: Thư viện Học viện Công nghệ Bưu chính Viễn thông 1 LỜI NÓI ĐẦU Theo nghĩa khái quát mã hóa là một ánh xạ 1-1 từ tập tin rời rạc lên tập các từ mã thuộc một tập hợp nào đó, tập hợp này không nhất thiết là một tập các phần tử có cấu trúc. Tuy nhiên để thuận tiện cho việc mã hóa và đặc biệt là việc giải mã người ta thường chọn tập hợp này là một cấu trúc đại số nào đó. ( nhóm, vành, trường, không gian tuyến tính….. ). Thành tựu lớn nhất trong lý thuyết mã hóa là việc xây dựng các mã xyclic truyền thống là các ideal trong vành đa thức. Về bản chất mã xyclic chính là phần tử đơn vị của phép cộng ( phần tử zero ) trên vành đồng dư được xây dựng trên vành đa thức. Tuy nhiên bằng cách lựa chọn các nhóm nhân xyclic ( hoặc các cấp số nhân xyclic trong phân họach của vành đa thức theo các nhóm nhân xyclic ) ta cũng có thể xay dựng được các mã xyclic khác với các mã truyền thống chỉ là một trường hợp lựa chọn đặc biệt khi chọn các nhóm nhân xyclic đơn vị theo modulo. Hiển nhiên là cách mã hóa này cho ta khả năng lựa chọn phong phú khi xây dựng các mã trên vành đa thức cụ thể. Cho dù khả năng lựa chọn này còn kém xa so với khả năng lựa chọn theo quan điểm mã hóa tuyến tính ngẫu nhiên của Shanmon nhưng bù lại nó lại có được đặc tính xyclic rất thuận lới cho việc mã hóa và 2 giải mã. Đây là đặc tíh ứng dụng đơn giản nổi trội của các mã xyclic truyền thống. Trên cơ sở các nghiêm cứu gần đây về các mã xyclic cục bộ xây dựng trên cán phân họach mã vành, theo quan điểm mới này luận văn mới chỉ chú trọng tới việc xây dựng mã từ các nhóm nhân xyclic có so sánh với các mã xyclic truyền thống. Bảng luận văn được chia làm 3 chương với các nội dung chủ yếu sau: - Chương I: Vành đa thức và các nhóm nhân xyclic. Chương này trình bày tổng quan lý thuyết nhóm nhân xyclic trên vành đa thức. - Chương II: Phân họach vành đa thức. Chương này trình bày các phương pháp phân họach vành đa thức theo các nhóm nhân xyclic khác nhau. Đây là cơ sở để xây dựng các mã xyclic cục bộ. - Chương III: Các mã xyclic xây dựng trên các nhóm nhân xyclic. Chương này mô tả cách xây dựng các mã xyclic xây dựng trên các nhóm nhân xyclic bao gồm thuật tóan mã hóa và thiết bị mã hóa, thuật tóan giải mã ngưỡng và thiết bị giải mã ngưỡng. Mối quan hệ giải mã xyclic truyền thống xây dựng trên các ideal và các mã xyclic xây dựng trên các nhóm nhân xyclic theo modulo cũng được xem xét. 3 Được sự giúp đỡ tận tình của thầy GS.TS Nguyễn Bình và sự nổ lực của bản thân luận văn đã được hòan thành. Tuy nhiên do thời gian hạn hẹp và trình độ hạn chế việc hiểu và trình bày các vấn đề được nêu không thể tránh khỏi còn nhiều thiếu sót. Rất mong được sự góp ý của các thầy và các bạn có quan tâm. CHƯƠNG I CÁC NHÓM NHÂN XYCLIC TRÊN VÀNH ĐA THỨC 1.1. Mã cyclic truyền thống và mã tuyến tính ngẫu nhiên của Shannon Mã cyclic gồm các từ mã là bội của đa thức sinh g(x) với g(x) là một ước nào đó của x n  1 . 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) [5, 6]. 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ã. Ký hiệu V _(n, k ) là mã cyclic (tuyến tính) có 4 độ dài từ mã n và số dấu thông tin k được sinh bởi đa thức sinh g(x) với deg g ( x)  r  n  k . Khi đó ta có: Nếu a( x ) V _(n, k ) thì a( x ) : g ( x) , Ta có: + Dịch vòng trái: xa( x) : g ( x) , + Dịch vòng phải: a( x) : g ( x) . x 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 [5]. 1.2. Các mã cyclic cục bộ (LCC: Local cyclic codes) Để khắc phục những hạn chế trên của mã cyclic vào năm 1987, GS Nguyễn Bình và giáo sư Nguyễn Xuân Quỳnh đã cùng nhau thảo luận đưa ra một quan điểm mã hoá mới dựa trên việc phân hoạch vành số Z 2k 1 thành các lớp kề của nhóm nhân cyclic đơn vị I  2k , i  0, k  1 (1-1) Mã được xây dựng trên phân hoạch (1-1) được gọi là mã cyclic cục bộ và được định nghĩa như sau : 5 Định nghĩa 1.1: Mã cyclic cục bộ hệ thống (n, k) là mã hệ thống tuyến tính trong đó: - k dấu thông tin là k phần tử của nhóm nhân cyclic đơn vị - n-k = r dấu kiểm tra là một tập con không trống tuỳ ý nào đó các lớp kề của nhóm nhân này + Mã cyclic truyền thống được xem là một lớp kề đặc biệt trong phân hoạch. + Mã tuyến tính ngẫu nhiên của Shannon được xem là mã LCC xây dựng trên phân hoạch của vành đa thức có hạt nhân phân hoạch là phần tử đơn vị e( x)  1 . Để xây dựng được mã tốt vấn đề quan trọng là phải có các tiêu chí để lựa chọn các lớp kề tạo mã. Các nghiên cứu tiếp theo là tìm các tiêu chí lựa chọn các lớp kề khác nhau để tạo mã. Quan hệ giữa các mã LCC với các mã cyclic truyền thống và các mã tuyến tính ngẫu nhiên được mô tả ở hình 1.1. 6 Phân hoạch của vành đa thức theo nhóm nhân xyclic Phân hoạch không suy biến Phân hoạch cực tiểu Phân hoạch cực đại Phần tử sinh n Phần tử sinh a(x) o r d a  x   m Phân hoạch suy biến Phân hoạch chuẩn a x o rd x 1 Mã tuyến tính ngẫu nhiên của Shannon x  b Phần tử sinh x Mã cyclic cục bộ Mã xyclic Hình 1.1: Quan hệ giữa các lớp mã khác nhau Với các vành chẵn, tác giả cũng đưa ra một phương pháp phân hoạch mới để tạo mã. Trong trường hợp này vành sẽ được phân hoạch thành các lớp chứa các phần tử liên hợp là các căn bậc 2 của các thặng dư bậc hai trong vành [8]. 7 Ta có thể xây dựng được các mã LCC trên các lớp đặc biệt là các căn bậc 2 của lũy đẳng nuốt và các căn bậc 2 của Zero.(Hình 1.2). Các phân hoạch của vành đa thức n tùy ý Theo nhóm nhân xyclic n = 2k + 1 Theo Ideal n = 2k Theo lớp các phần tử liên hợp Các mã xyclic Các mã cyclic cục bộ Hình 1.2: Các dạng phân hoạch khác nhau của vành đa thức 8 1.3. Các nhóm nhân cyclic trong vành đa thức 1.3.1. Nhóm nhân của vành đa thức theo modulo xn + 1 Theo lý thuyết mã cổ điển, mỗi Ideal tương ứng của một vành đa thức sẽ xây dựng được một bộ mã xyclic. Trong một vành đa thức, Ideal I gồm các đa thức là bội của một đa thức g(x), trong đó g(x) là ước của đa thức xn+ 1: (g(x)) | xn+1 hay x n  1: g  x  . Vành Z2[x]/ xn + 1 Đa thức sinh Ideal g(x) Hình 1.3: Phân hoạch vành theo Ideal. Theo phương pháp cổ điển này thì rõ ràng là số bộ mã bị hạn chế (do số đa thức sinh ít). Theo quan điểm xây dựng các mã cyclic mới là đi nghiên cứu các nhóm nhân trên vành đa thức. Dựa trên các nhóm nhân để đi xây dựng các bộ mã có đặc tính khác nhau. 9 Vành Z2[x]/ xn + 1 Nhóm nhân Nhóm nhân Hình 1. 4: Phân hoạch vành theo nhóm nhân. Định nghĩa 1.2: Nhóm nhân. Tập các đa thức f(x) trong vành đa thức Z2[x]/xn+1 với một phép toán nhân đa thức tạo nên một nhóm nhân G. = G Nếu g(x), f(x)  G thì g(x).f(x) = d(x)  G. Trong nhóm nhân tồn tại phần tử đơn vị e(x) với f(x).e(x) = f(x). Trọng số của đa thức: Trọng số của đa thức a(x) được ký hiệu là W(a(x)) là tổng các hệ số khác không trong biểu diễn đa thức đó: n 1 a( x)   ai x i i 0 Với a(x) = 1 + x ta có thể viết a(x) = 1.x0 + 1.x1  W(a(x)) = 2. 1.3.2. Nhóm nhân cyclic trong vành đa thức Z2[x] /xn +1 10 1.3.2.1. Nhóm nhân cyclic (CMG – Cyclic Multiplicative Groups) Nhóm nhân cyclic trong vành đa thức là tập hợp các phần tử đều bằng lũy thừa của một phần tử gọi là phần tử sinh. Trong vành đa thức có nhiều nhóm nhân xyclic, số nhóm nhân bằng số các lũy đẳng có thể có trong vành. A = {, 2, 3,…} (1-2) Trong đó: A là nhóm nhân xyclic  là phần tử sinh (đa thức sinh), cấp của phần tử sinh là cấp của nhóm (cấp của nhóm là tổng số các phần tử của nhóm). Phần tử đơn vị của nhóm chính là một lũy đẳng e(x). Định nghĩa 1.3: Cấp của một đa thức. Cấp của một đa thức, ký hiệu ord a(x), là số nguyên dương (m) nhỏ nhất sao cho: am(x) = e(x) mod (xn +1) Trong đó e(x) là một lũy đẳng nào đó. (1-3) 11 Như vậy, a(x) sẽ tạo nên một nhóm cyclic cấp m trong nhóm nhân của vành. Định nghĩa 1.4: Nếu a(x) là phần tử của nhóm nhân nào đó. Cấp cực đại của a(x) được xác định như sau: + Nếu n lẻ (n = 2k + 1) ; và xn +1 =  fi(x); trong đó fi(x) là các đa thức bất khả quy. Khi đó max ord(a(x)) = 2m – 1. Trong đó m = max deg fi(x). + Nếu n chẵn n = 2s(2k + 1); và x2k+1 +1 =  fi(x); trong đó fi(x) là các đa thức bất khả quy. Khi đó max ord(a(x)) = 2s(2m +1). Trong đó m = max deg fi(x). 1.3.2.2. Đa thức lũy đẳng Định nghĩa 1.5: Trong vành đa thức Z2[x] /xn + 1, nếu tồn tại một đa thức mà bình phương của nó lại cho giá trị như khi chưa bình phương thì được gọi là đa thức lũy đẳng và ký hiệu là e(x). e(x) = e2(x) = e(x2) (1-4) Các phần tử cấp 1 của vành Z2[x] /xn +1 chính là các lũy đẳng e(x) được xác định trên cơ sở phân tích chu trình Cs; 12 Định nghĩa 1.6: Lũy đẳng “nuốt” Trong mỗi vành đa thức Z2[x]/ xn + 1 đều tồn tại một lũy n 1 đẳng e0(x) =  xi , lũy đẳng này được gọi là lũy đẳng “nuốt” i0 (Swallowing Idempotent). Trong một vành bất kỳ, với n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy đẳng “nuốt” e0(x). 1.3.2.4. Nhóm nhân cyclic với phần tử sinh a(x) Định nghĩa 1.8: Nhóm nhân cyclic với phần tử sinh là đa thức a(x) bao gồm các phần tử là lũy thừa của phần tử sinh và có thể viết dưới dạng: A = {a(x), (a(x))2, (a(x))3,...} (1-8) Tương tự như với nhóm nhân cyclic đơn vị, ta thấy nhóm cyclic với phần tử sinh là đa thức a(x) cũng xây dựng dựa trên cấp số nhân có số hạng đầu là 1 và công bội là a(x). 1.3.2.5. Đa thức đối xứng và các nhóm nhân cyclic đối xứng Định nghĩa 1.9: Đa thức đối xứng 13 Đa thức a( x) được gọi là đa thức đối xứng với đa thức a( x ) nếu: a( x )   a i x i thì a( x)   a j x j iI jJ (1-9) Với: I  J = ; I  J  S  0,1,..., n  1 . Bổ đề 1.2: Nếu a(x) là một phần tử cấp k thì cấp của a ( x) cũng bằng k. Tức là, nếu A là một nhóm nhân cyclic cấp k có phần tử sinh là a(x) thì A cũng là nhóm nhân cyclic cấp k với phần tử sinh là a ( x) . Khi đó ta có: A = {a(x), a2(x), a3(x), ..., ak-1(x)} A = { a ( x) , ( a ( x) )2, ( a ( x) )3, ..., ( a ( x) )k-1} Như vậy, với mỗi phần tử a(x) của nhóm nhân cyclic A ta có tương ứng một phần tử a ( x) của nhóm nhân cyclic A . Từ nhóm nhân cyclic A ta dễ dàng thiết lập được nhóm nhân cyclic A . Hai nhóm nhân A và A được gọi là hai nhóm nhân cyclic đối xứng trong vành đa thức. 14 2.1.2. Cấp số nhân cyclic trên vành đa thức Xét vành đa thức Z2[x]/ xn + 1 với n lẻ, giả sử a(x) là số hạng đầu tiên của cấp số nhân cyclic và q(x) là công bội của cấp số nhân. Định nghĩa 2.1: Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions) Cấp số nhân cyclic trên vành đa thức là một tập hợp con có dạng sau: A(a,q) = {a(x), a(x).q(x), a(x).q2(x), ..., a(x).qm -1(x)} (2-1) Trong đó: m là số các số hạng của cấp số nhân. a(x) là số hạng đầu của cấp số nhân. q(x) là công bội. a(x).qm(x)  a(x) mod xn + 1 Giá trị của m được xác định bởi cấp của nhóm nhân xyclic. Định nghĩa 2.2: Phân hoạch vành đa thức được gọi là không suy biến nếu phân hoạch bao gồm tất cả các phần tử khác 0 trong vành đa thức. Ngược lại, phân hoạch là phân hoạch suy biến. 15 2.2.2. Phân hoạch cực đại Định nghĩa 2.3: Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh có phần tử sinh với cấp lớn nhất, ord(a(x)) = max ord(b(x)), b(x)  Zn. 2.2.3. Phân hoạch cực tiểu 2.2.4. Phân hoạch vành thành các cấp số nhân có cùng trọng số 2.2.5. Phân hoạch vành đa thức thành các cấp số nhân với các phần tử có cùng tính chẵn lẻ của trọng số 2.2.6. Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x) Vành đa thức Z2[x]/ xn + 1 có thể được phân hoạch thành các cấp số nhân theo modulo h(x) với h(x) | xn + 1. m Từ phân tích nhị thức xn+ 1 =  f i ( x)  f1 ( x). f 2 ( x )... f t ( x) i 1 Trong đó, fi(x) là các đa thức bất khả quy. Như vậy, h(x) là tổ hợp của các fi(x) sao cho deg h(x) = k < n, trong vành đa thức Z2[x]/ xn +1. Tuỳ theo giá trị n mà có số đa 16 thức bất khả quy khác nhau, nên sẽ có số h(x) khác nhau. Khi đó, trên vành sẽ có nhiều phân hoạch ứng với các h(x) khác nhau. 2.3. Các vành đa thức có hai lớp kề xyclic 2.3.1. Vành đa thức có hai lớp kề xyclic Định nghĩa 2.4: Vành đa thức theo modulo xn+1 được gọi là vành đa thức có hai lớp kề cyclic nếu phân tích của xn+1 thành tích của các đa thức bất khả quy trên trường GF(2) có dạng sau: xn + 1 = (x + 1) n 1 x i i 0 (2-9) n 1 Trong đó (1+x) và o(x) = x i 0 i là các đa thức bất khả quy. 17 CHƯƠNG III CÁC MÃ XYCLIC XÂY DỰNG TRÊN NHÓM NHÂN XYCLIC 3.1. Hai thủ tục giải mã: 3.1.1. Hai thủ tuc giải mã: Mọi phương pháp giải mã đều có thể tiến hành theo một trong hai thủ tục giải mã sau: - Phương pháp ( thủ tục) 1: Dẫn ra bản tin từ dấu nhận được - Thủ tục 2: Dẫn ra vec tơ sai dãy dấu nhận được 3.1.2. Hệ tổng kiểm tra trực giao và có khả năng trực giao: Định nghĩa 3.1: Hệ J tổng kiểm tra được gọi là trực giao với ui nếu: - Mỗi tổng kiểm tra trong hệ đều chứa uj . - Dấu mã uj (j≠ i) chỉ nằm tối đa trong một tổng kiểm tra. Định nghĩa 3.2: Hệ tổng kiểm tra được gọi là có khả năng trực giao nếu nó là hệ tổng kiểm tra trực giao với một tổ hợp tuyến tính nào đó các dấu mã. 3.2. 18 Các mã Xyclic xây dựng trên nhóm nhân xyclic. 3.2.1. Mô tả mã: Cho vành đa thức: Z2[x]/xn + 1 Xét a(x)  Z2[x]/xn + 1 Ta xây dựng nhóm nhân xyclic A = {ai(x), i = 1, 2, ……} Giả sử: Xn + 1 = ∏fi(x) m = max deg fi(x) Khi đó cấp của a(x) thỏa mãn điều kiện sau: max ord a(x) = 2m - 1 Xét a (x) là đa thức đối xứng của a(x) Bổ đề 3.1: Nếu A là 1 mã xyclic (n, k, d0) Thì A là 1 mã xyclic (n, k-1, d0+1) Ví dụ 17 : n = 5 ; X5 + 1 = (1 + x)(1 + x + x2 + x3 + x4)  A = {(024)i, i = 1, 2, ….}  A = {(13)i, i = 1, 2, …} A = {(024), (034), (1), (013), (014), (2), (124), (012), (3), (023), (123), (4), (134), (234), (0)} A = {(13), (12), (0234), (24), (23), (0134), (03), (34), (0124), (14), (04), (0123), (02), (01), (1234)}