Luận án Nhóm nhân cyclic và mã cyclic trên vành đa thức

h xạ tuyến tính. Mặt khác các phần tử trên dòng thứ i của ma trận A lần lượt sẽ là các tọa độ thứ i của các vector  0, , 1k k n    , đó là    1 mod 1 mod, , ,i i n i n na a a   và đây chính là tọa độ của vector ix và điều này đã chứng minh đẳng thức (2.8). Như vậy, định lý đã được chứng minh. 60 Hệ quả: Nếu A là ma trận của  thì với mọi i ta có iA là ma trận của ' . 2.3.1.2. Một tính chất của tích vô hướng Tính chất 2.1: Với mọi    0 1 1 0 1 1, , , , , , ,n n na a a b b b R       và mọi ma trận vuông ,i jD d    cấp n , ta có: , , TD D    (2.12) Chứng minh: Ký hiệu j là vector cột thứ  , 0,1, , 1j j n   của ma trận D , ta có  0, 1, 1,, , ,j j j n jd d d   .  0 1 1, , , , , , nD               Do đó 1 1 1 1 1 , , 0 0 0 0 0 , , n n n n n j j i i j j i j i j j j i i j D b a d b a b d                              (2.13) Tương tự, kí hiệu * i là vector cột thứ i của ma trận TD và do đó là vector dòng thứ i của ma trận D , ta có:  * ,0 ,1 , 1, , ,i i i i nd d d    * * *0 1 0, , , , , , ,TD              Do đó: 1 1 1 1 1 * , , 0 0 0 0 0 , , n n n n n T i i i j i j i j i j i i j i j D a a d a db b                              (2.14) Từ đẳng thức (2.13) và (2.14) suy ra (2.12), tính chất được chứng minh. 2.3.2. Sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống 61 Trong mục 2.3.1 các kết quả được trình bày cho một trường F tổng quát, còn tại mục này ta quay lại với trường  2GF vì khái niệm về mã cyclic cục bộ được phát biểu trên     2 / 1nGF x x  với n lẻ và do đó, cần đến một số tính chất mà vành này có được. Dễ thấy, trong   2GF x các phép toán cộng và trừ là như nhau nên có thể sử dụng  1nx  thay cho  1nx  . Nhóm nhân cyclic và mã cyclic cục bộ trên     2 / 1nGF x x  với n lẻ, có tính chất sau: Tính chất 2.2: Với mọi     , 2 / 1nGF x x    với n lẻ thì  #m     là ước của #m    [25]. Hơn thế nữa, ta có: 1m   (2.15) Trên cơ sở đó, ta có bổ đề về tính cyclic của mã cyclic cục bộ được tạo từ một cấp số nhân cyclic (hay lớp kề cyclic) như sau. Bổ đề 2.4: Mã cyclic cục bộ xây dựng từ một cấp số nhân cyclic cũng là một mã cyclic truyền thống. Mã cyclic này được xây dựng trên vành đa thức có bậc là cấp của cấp số nhân cyclic trong phân hoạch của vành đa thức xây dựng cấp số nhân cyclic [J4]. Chứng minh: Theo định nghĩa của mã cyclic cục bộ xây dựng từ cấp số nhân cyclic với nhóm nhân cyclic   và đa thức 1 0 1 1 t tb b x b x     là không gian tuyến tính con của     2 / 1mGF x x  với  #m     sinh bởi n vector dòng của ma trận cấp n m dưới đây:      1 2, , , T T T mG         (2.16) Ký hiệu các vector dòng của G lần lượt là 0 1 1, , , n    . 62 Vậy mỗi từ của mã này là một tổ hợp tuyến tính của n vector nói trên. Giả sử  là một từ mã với 1 0 n i i i c     (  2ic GF ) nếu kí hiệu  0 1 1, , , nc c c   , ta có:  1 2, , , , , , mG                (2.17) Chọn:  1 T mD A  (2.18) Với A là ma trận của phép nhân với  trong    / 1nF x x  Xét từ mã  * D G  , ta có:  * 1 2 1, , , , , , , ,                 m mD D D D Áp dụng (2.12), ta có:  * 1 2 1, , , , , , , ,                 T T m T m TD D D D Áp dụng (2.18), ta có:     * 1 1 2 1 1 1 1 1 2 1 , , , , , , , , , , , , , , , ,                                                m m m m m m m m m m m m A A A A Áp dụng (2.15), ta có:  * 1 2 1, , , , , , , ,                 m m m (2.19) Từ (2.17) và (2.19) cho thấy * chính là  dịch vòng đi một vị trí. Điều này có nghĩa là mã cyclic cục bộ xây dựng trên chính là mã cyclic và đây là điều cần chứng minh. Chứng minh này đưa đến khẳng định rằng mã cyclic cục bộ xây dựng từ cấp số nhân cyclic là một mã cyclic, từ đây có thể mở ra một phương án mới để xây dựng các lớp mã cyclic. Với phương án tiếp cận này, việc xây dựng các mã cyclic (nhất là với các mã cyclic ở trên các vành lớn) trở nên đơn giản hơn, ta chỉ cần khảo sát các cấp số nhân cyclic trên các vành nhỏ cũng có thể xây dựng được các mã 63 cyclic ở trên các vành lớn, trong khi đối với các vành lớn (số mũ n lớn), việc phân tích giá trị ( 1) nx  ra thành các đa thức bất khả quy cũng là một trở ngại cho việc xây dựng mã cyclic. 2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyền thống Một số nghiên cứu bước đầu về mã cyclic cục bộ đã chỉ ra rằng giữa nhóm nhân cyclic và mã cyclic truyền thống có mối quan hệ với nhau [6]. Từ kết quả bổ đề 2.4, khi 1  thì cấp số nhân cyclic tương đương nhóm nhân cyclic, do đó có thể nhận định rằng mã LCC xây dựng trên nhóm nhân cyclic cũng tương đương với mã cyclic truyền thống. Phần này sẽ trình bày kết quả khảo sát và đánh giá về sự tương đương giữa mã LCC xây dựng trên nhóm nhân cyclic và mã cyclic truyền thống. Do vành đa thức có cấu trúc đối xứng, một nửa vành gồm các phần tử có trọng số lẻ, một nửa vành có trọng số chẵn nên khi phân hoạch chỉ cần tìm các phần tử có trọng số lẻ và suy ra các phần tử có trọng số chẵn với cấu trúc tương tự. Để xây dựng được tất cả các nhóm nhân của vành, ta thực hiện các bước như trình bày trong mục 1.4.3.1. Đối với mã cyclic, việc khảo sát và lựa chọn để tìm ra một bộ mã tối ưu trên các vành đa thức có giá trị n lớn là rất phức tạp và khó khăn, bằng việc chứng minh được sự tương đương giữa các mã cyclic cục bộ được xây dựng trên các vành có giá trị n nhỏ tương đương với các mã cyclic truyền thống được xây dựng trên các vành có giá trị n lớn là một kết quả quan trọng giúp cho việc khảo sát và tìm kiếm các bộ mã cyclic tối ưu được dễ dàng hơn. Để chứng minh cho sự tương đương này, ta xét một số ví dụ. Ví dụ 2.6: Trong vành   72 / 1Z x x  , đa thức 7 1x  được phân tích dưới dạng tích của ba đa thức bất khả quy:    7 3 321 1 1 1x x x x x x       . 64 Xét    2 0121 ~a x x x   trên vành   72 / 1Z x x  , xây dựng nhóm nhân:               012 024 01356 014 034, , , , ,56 02 , 0356A  Lập ma trận mã từ các phần tử của nhóm nhân A , ta được ma trận mã: 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 G                        (2.20) Sử dụng phương pháp Gauss-Jordan biến đổi ma trận mã trên về ma trận hệ thống [38], [40], ta được ma trận: 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 G                        (2.21) Loại bỏ các hàng bằng 0 của ma trận ta được ma trận hệ thống tương đương:         1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 ~ 0 1 2 3 0 0 1 0 1 1 0 0 0 0 1 0 1 1 012 123 013G             (2.22) Dễ dàng nhận thấy 1G là nhóm nhân được xây dựng trên phân hoạch vành đa thức theo modulo    0124h x  hay     2 4 2 31 1 1h x x x x x x x       trên vành   72 / 1Z x x  . 65 Theo tính chất của mã cyclic cục bộ được xây dựng theo modulo  h x , ta luôn tìm được mã cyclic truyền thống với đa thức sinh     * 1nx g x h x         tương đương với mã cyclic cục bộ xây dựng theo modulo  h x . Ta có:     * 7 * 3 3 2 3 2 4 3 1 1 1 1 1 1 1 x g x x x x x x x x x x x                        (2.23) Trên vành 7 1x  , xét mã cyclic truyền thống được xây dựng theo đa thức sinh   2 31g x x x   Theo định nghĩa ma trận sinh 2G của mã cyclic truyền thống được thiết lập:         2 3 3 4 2 2 2 4 5 3 3 5 6 1 0 1 1 0 0 01 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 g x x x xg x x x x G x g x x x x x g x x x x                                            (2.24) Sử dụng phương pháp Gauss-Jordan biến đổi về ma trận hệ thống [38], [40], ta được: 2 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 G             (2.25) Từ (2.22) và (2.25) suy ra 1 2G G hay hai phương pháp thực hiện cùng đi đến kết quả là ma trận mã hệ thống bằng nhau. Ví dụ 2.7: Trong vành   92 / 1Z x x  , đa thức 9 1x  được phân tích dưới dạng tích của ba đa thức bất khả quy:    9 2 3 61 1 1 1x x x x x x       . 66 Xét    2 4 124~a x x x x   trên vành 9 1x  , xây dựng nhóm nhân:                                           , 248 , 01458 , 478 , 12356 , 01278 , 23568 , 578 , 0123678 , 12346 , 125 , 02457 , 13567 , 13467 , 0134568 , 157 , 35678 , 0234567 , 34678 , 23468 , 4 0 12 A            (2.26) Tiến hành tương tự, lập ma trận và chuyển ma trận lập được về ma trận hệ thống, loại bỏ các hàng có kết quả bằng 0 ta được ma trận mã hệ thống:                                           3 0 , 1 , 2 , 3 , 4 , 5 , 014 , 125 , 01234 , 12345 , 01235 , 023 , 134 , 245 , 01345 , 025 , 034 , 145 , 01245 , 02345 , 035 G            (2.27) Biểu thức (2.27) là ma trận mã cyclic cục bộ được xây dựng theo CMG   , 1,2,...iA a x i  trên vành   92 / 1Z x x  . Có thể nhận thấy 3G là ma trận sinh đối với mã cyclic cục bộ được sinh bởi CMG xây dựng theo modulo      4 6 2 31 1 1 1h x x x x x xx x x         trên vành   22 1/ 1Z x x  . Xét vành đa thức   212 / 1Z x x  , phân tích đa thức 21 1x  dưới dạng tích của các đa thức bất khả quy:       21 2 3 2 3 2 4 6 2 4 5 61 1 1 1 1 1 1x x x x x x x x x x x x x x x x                 Xét   * 21 4 6 1 1 x g x x x x         , biến đổi ta có:       * 2 3 2 4 6 2 4 5 6 15 2 3 5 6 7 10 11 13 15 2 4 5 8 9 10 12 13 14 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 g x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x                                         (2.28) Theo định nghĩa ma trận sinh 4G của mã cyclic truyền thống được thiết lập: 67             2 4 5 8 9 10 12 13 14 15 3 5 6 9 10 11 13 14 15 16 2 4 6 7 10 11 12 34 4 2 14 15 16 17 3 5 7 8 11 12 13 15 16 17 5 18 4 1 x x x x x x x x x x x x x x x x x x x x g x xg x x g x G x g x x g x x x x x x x x x x x x x x x x x x x x x x g x x x x x x                                                               6 8 9 12 13 14 16 17 18 19 5 7 9 10 13 14 15 17 18 19 20 x x x x x x x x x x x x x x x x x x x x                                        (2.29) 4 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 G                     (2.30) Dùng công thức Gauss-Jordan biến đổi về ma trận hệ thống, ta có ma trận tương đương:                             4 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 , 1 , 2 , 3 , 4 , 5 , 014 , 125 , 01234 , 12345 , 01235 , ~ 023 , 134 , 245 , G                                  01345 , 025 , 034 , 145 , 01245 , 02345 , 035         2.31) Biểu thức (2.31) là ma trận mã cyclic truyền thống xây dựng theo đa thức sinh  g x trên vành   22 1/ 1Z x x  . Từ (2.27) và (2.31) suy ra 3 4G G , hay mã cyclic cục bộ xây dựng theo nhóm nhân cyclic   , 1,2,...iA a x i  trên vành   92 / 1Z x x  và mã cyclic truyền thống xây dựng theo đa thức sinh  g x trên vành   22 1/ 1Z x x  cùng đi đến kết quả là ma trận mã hệ thống bằng nhau. 68 Nhận xét: Qua hai ví dụ trên, có thể nhận thấy rằng hai phương pháp xây dựng mã khác nhau là xây dựng mã cyclic cục bộ theo nhóm nhân cyclic trên phân hoạch vành đa thức và xây dựng mã cyclic truyền thống theo đa thức sinh đều dẫn đến một ma trận mã hệ thống như nhau. Tiếp tục quá trình khảo sát và đánh giá ta xây dựng được thuật toán 2.4 để xác định mã cyclic truyền thống tương đương với các nhóm nhân cyclic trên phân hoạch vành đa thức. Kết quả khảo sát với các toàn bộ nhóm nhân khác nhau trên các vành đa thức khác nhau (các giá trị n lẻ  19n  ) cũng cho kết quả tương tự, có nghĩa là có mã cyclic cục bộ được xây dựng theo nhóm nhân trên phân hoạch vành đa thức sẽ tương đương với một mã cyclic truyền thống được xây dựng trên vành là cấp của nhóm nhân trên vành đa thức đã xét. Kết quả nghiên cứu được công bố trong [C3]. Thuật toán xác định mã cyclic truyền thống tương đương (Thuật toán 2.4) VÀO:    2[ ] / 1nxa Z xx   RA: Mã cyclic truyền thống tương đương với CMG { ( ), 1,2,..., } iA a x i m  Bước 1: - Xây dựng { ( ), 1,2,..., } iA a x i m  . - Đặt   n ord a x - Lập ma trận mã LCC từ các phần tử của CMG A . - Sử dụng thuật toán Gauss-Jordan để chuyển ma trận lập được ở trên về dạng ma trận hệ thống. - Loại bỏ các hàng bằng 0 (nếu có) của ma trận mã, được ma trận sinh  ,G n k . Bước 2: - Chuyển đổi ma trận sinh  ,G n k về dạng các phần tử trong nhóm - Đặt       2& ; / ( 1) nh x A k k h x Z x   69 - Tính     * 1nx g x h x         - Từ đa thức sinh  g x , được ma trận mã tương đương với mã cyclic truyền thống. Một số kết quả khảo sát trên các vành đa thức với các giá trị n khác nhau được trình bày trong Phụ lục 3. 2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI Từ quan điểm xây dựng mã cyclic và LCC, ta thấy có thể thực hiện việc mô tả mã cyclic theo quan điểm xây dựng các mã LCC dựa trên phân hoạch vành đa thức [6], [18].  Theo quan điểm xây dựng mã cyclic: mã cyclic là một Ideal của vành đa thức; trong đó mỗi từ mã là một phần tử của Ideal đó trên vành đa thức.  Theo quan điểm xây dựng mã LCC mỗi dấu mã là một phần tử của Ideal; toàn bộ từ mã là một bộ phận của vành gồm n phần tử xác định của Ideal. Như vậy, có thể dùng lý thuyết xây dựng các đa thức sinh của mã cyclic để tạo các trưởng lớp kề cho các mã LCC. Với quan điểm đó, lớp kề được xây dựng theo cách sau đây sẽ tạo nên một mã cyclic [6], [7]: - Đa thức sinh là ước của 1; ( ) ( 1) n nx g x x  . - Bậc của đa thức sinh bằng r n k  . - Sử dụng r dấu thông tin giả khi tạo lớp kề này; tức là cho trước: 0 1 2 1... 0nx x x x      . Như vậy, có thể nói rằng mã cyclic là một lớp kề đặc biệt của mã LCC. 70 a(x) b(x) c(x) a(x) LCC đa nhịp a(x) a(x) a(x) LCC đơn nhịp Mã cyclic xây dựng từ CMG (Mã cyclic xây dựng từ LCC) x Mã cyclic truyền thống (Mã cyclic ideal) Hình 2.2. So sánh các mã cyclic và mã cyclic cục bộ Có thể hình dung mã cyclic như một chuỗi hạt có tốc độ xử lý khác nhau như trong Hình 2.2. Mã cyclic truyền thống có nhịp dịch của từ mã là x , mã cyclic xây dựng từ mã LCC (hay CMG) có nhịp dịch khác x , còn mã LCC chứa các từ mã khác nhau, mỗi từ mã có thể có nhịp dịch khác nhau. Theo quan điểm trên thì các mã cyclic xây dựng trên các Ideal là một trường hợp đặc biệt của mã LCC. Có thể xem xét: Nhóm nhân cyclic: { mod ( ); 0,1,2,...} iI x h x i  ; ( ) | ( 1) nh x x  và deg ( )h x k Nhóm nhân I là một mã cyclic (n,k) có đa thức sinh *( )g x với: ( 1) ( ) ( ) nx g x h x   và * deg ( ) 1( ) ( )g xg x x g x là đa thức đối ngẫu của ( )g x . Nhận xét:  Với mã cyclic truyền thống, ma trận sinh G của mã được xây dựng từ phương trình đồng dư sau: ( ). mod ( 1) i ng x x x  (2.32)  Với mã cyclic xây dựng từ mã LCC, ma trận sinh G của mã được xây dựng từ phương trình đồng dư sau: ( ). mod ( 1) i i ka x x x  (2.33) 71 Chú ý: (1.29) là phương trình tạo các hàng của G (1.30) là phương trình tạo các cột của G Một ưu điểm của mã LCC đó là có thể xây dựng được mã trên mọi vành đa thức (n bất kỳ), với các vành chẵn ta có thể xây dựng mã LCC trên các lớp các phần tử liên hợp [23], trong khi mã cyclic thì chỉ có thể xây dựng trên các vành lẻ. Có những vành không thể xây dựng được mã cyclic tốt (ví dụ với các vành có hai lớp kề cyclic thì khó tìm được mã cyclic tốt), nhưng ngược lại ta có thể tìm được nhiều mã LCC trên các vành này [1]. Việc xây dựng mã LCC trên phân hoạch vành đa thức sẽ cho nhiều bộ mã hơn và trên cơ sở đó cũng có nhiều bộ mã tốt hơn với các độ dài từ mã khác nhau. Mặc dù đã có một số cách phân loại mã tuyến tính nhưng chỉ dựa vào cấu trúc đại số mà không đề cập tới mã LCC, vì vậy các kiểu phân loại đã có là chưa toàn diện. Nghiên cứu các mã cyclic cục bộ trong mối quan hệ với mã cyclic nói riêng và trong hệ thống mã tuyến tính xây dựng trên các cấu trúc đại số nói chung, với các dạng phân hoạch khác nhau có thể cho ra các loại mã sửa lỗi khác nhau, hệ thống phân loại các mã tuyến tính xây dựng trên các cấu trúc đại số được trình bày trong Hình 2.3. 72 Mã tuyến tính Không có cấu trúc Có cấu trúc Vành số Mã cyclic AN Vành đa thức Z2[x]/x n+1 Phân hoạch vành theo CMG Vành các lớp liên hợp Vành đồng dư Trên một vành Trên hai vành Vành và vành ước của vành Hai vành bất kỳ LCC hỗn hợp Phân hoạch cực tiểu Phân hoạch chuẩn Phân hoạch cực đại LCC đa nhịp LCC đơn nhịp LCC Mã cyclic nhịp x   modi xxI h Vành ma trận Ma trận Cauchy Ma trận Vandermon Mã cyclic theo Ideal I= Mã Goppa Mã tuyến tính ngẫu nhiên Mã BCH Mã tựa LCC n lẻ Mã cyclic với nhịp đa thức n chẵn n bất kỳ Hình 2.3. Sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã LCC [C4] Trước hết, về mặt cấu trúc thì mã tuyến tính được chia thành hai loại là có cấu trúc và không có cấu trúc. Trong đó mã không có cấu trúc là cơ sở xây dựng mã tuyến tính ngẫu nhiên có khả năng đạt được được giới hạn của Shanon nhưng việc thực hiện mạch mã hoá và giải mã gặp nhiều khó khăn chính vì tính không có cấu trúc nên ít được nghiên cứu. Các loại mã tuyến tính có cấu trúc được tập trung nghiên cứu chủ yếu dựa trên cấu trúc vành số (tiêu biểu như mã cyclic AN [74]), vành ma trận (tiêu biểu như mã Goppa, mã BCH [74], [77]) và vành đa thức (tiêu biểu là các loại mã cyclic). Hướng xây dựng mã tuyến tính có cấu trúc dựa trên vành đa thức    2 / 1nZ x x  lại gồm các loại như: vành chẵn ( n chẵn) hướng đến xây dựng 73 các mã cyclic dựa trên vành các lớp liên hợp (trong số này tiêu biểu là LCC), vành lẻ ( n lẻ) thường tập trung nghiên cứu các mã cyclic truyền thống, đối với vành bất kỳ (hay n bất kỳ) thì một hướng nghiên cứu được đề xuất đó là thực hiện phân hoạch vành theo nhóm nhân cyclic với một số kết quả được công bố trong [6], [12], [13], [30]. Trên cơ sở tham khảo và đánh giá kết quả nghiên cứu về mã cyclic cục bộ, một số mã khối tuyến tính đề cập ở trên và cấu trúc đại số, nghiên cứu sinh đề xuất sơ đồ thể hiện mối quan hệ như Hình 2.3 với trọng tâm tập trung vào mã cyclic và cyclic cục bộ. Các nội dung đã nghiên cứu trong hai mục trên bao gồm: phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại (liên quan trực tiếp đến phân hoạch cực đại, nội dung được đánh giá là quan trọng nhất trong phân hoạch vành đa thức theo CMG); mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống (liên quan đến mối quan hệ giữa mã cyclic nhịp đa thức, nhịp x và mã cyclic truyền thống), ngoài ra có thể chỉ ra được những mối quan hệ khác mà chưa thể hiện trong sơ đồ. Hai kết quả chính đó góp phần hoàn thiện lý thuyết và thực nghiệm về các nội dung được tô sẫm trong Hình 2.3. 2.5. KẾT LUẬN CHƯƠNG Chương 2 của luận án đã trình bày các nội dung liên quan đến nhóm nhân và cấp số nhân cyclic trên vành đa thức. Trên cơ sở đó, Luận án cũng đã trình bày kết quả nghiên cứu mới đóng góp vào việc bổ sung, hoàn thiện lý thuyết về mã cyclic. Các kết quả nghiên cứu này được công bố trong các công trình [J2], [J3], [J4], [J5], [C3], [C5] và tập trung vào hai nội dung chính: 1) Kiến thiết các nhóm nhân cyclic trên vành đa thức thông qua việc đề xuất phương pháp xác định cấp của đa thức và đa thức đạt cấp cực đại, đồng thời chứng minh hoàn chỉnh một số bổ đề quan trọng, cụ thể: (a) Đề xuất phương pháp xác định cấp của đa thức là tích các đa thức trên vành đa thức với đóng góp quan trọng nhất là đề xuất và chứng minh hoàn chỉnh bổ đề 2.2 cùng các hệ quả của bổ đề góp phần khẳng định một hướng tiếp cận mới để xây dựng đa thức có cấp cực đại trên 74 vành đa thức [J5]; (b) Đề xuất phương pháp xác định cấp của nhị thức trên vành đa thức với đóng góp là đề xuất và chứng minh hoàn chỉnh bổ đề 2.3 cùng với bảng 2.3 khảo sát cấp của  1 x dẫn tới một hướng xây dựng đa thức có cấp cực đại trên vành đa thức bằng việc chọn nhị thức  1 x hoặc đa thức là tích của đa thức có cấp nguyên tố với cấp của nhị thức  1 x [J3], [J5]; (c) Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành đa thức, thuật toán 2.3 được đề xuất giúp giảm độ phức tạp và thời gian tính toán, cũng như giúp thu được các kết quả về cấp của đa thức trên các vành lớn [C5]; (d) Đánh giá xác suất tìm phần tử có cấp cực đại trên vành đa thức có hai lớp kề cyclic cho thấy xác suất lựa chọn phần tử sinh là khá cao (hầu hết là trên 50%) [J2]. 2) Chứng minh sự tương đương giữa các nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, với việc trình bày một chứng minh về lý thuyết (bổ đề 2.4), xây dựng thuật toán (thuật toán 2.4), sau đó tiến hành khảo sát, đánh giá và xây dựng được một phụ lục minh chứng cho tính tương đương này [J4], [C3]. Kết quả này góp phần mở ra một hướng tiếp cận mới là xây dựng mã cyclic truyền thống từ các nhóm nhân, cấp số nhân cyclic trên vành đa thức có bậc bằng cấp của nhóm nhân/cấp số nhân cyclic, điều này đặc biệt có ý nghĩa khi các nhóm nhân cyclic trên các vành nhỏ có thể được dùng để kiến thiết nên mã cyclic truyền thống trên các vành lớn hơn và bằng cấp của nhóm nhân cyclic. Ở cuối chương, Luận án đã trình bày và thảo luận một sơ đồ phân loại các mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ, góp phần khẳng định mối quan hệ giữa mã cyclic với mã cyclic cục bộ và đánh giá vai trò của mã cyclic cục bộ trong hệ thống mã tuyến tính, mã sửa lỗi [C4]. 75 CHƯƠNG 3: ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC Các kết quả đạt được trong chương 2 về việc kiến thiết nhóm nhân cyclic, mối quan hệ tương đương của mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống là cơ sở để tiếp tục nghiên cứu ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi và mật mã. Một đặc điểm nổi bật của các bộ mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic là có độ dài thay đổi được có khả năng ứng dụng trong LTE, mã mạng [62], [64], [73]. Trong số các nhóm nhân trên một vành đa thức thì nhóm nhân có cấp cực đại có độ ngẫu nhiên của các phần tử cao nhất do đó có thể sử dụng các phần tử có cấp cao nhất trong nhóm nhân cấp cực đại trên vành đa thức làm khóa cho một số hệ mật. Trong chương này, luận án sẽ trình bày phương pháp xây dựng mã cyclic với các nội dung liên quan đến việc xây dựng khối mã hoá và giải mã, tiếp đến luận án trình bày đề xuất một số mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic gồm phương pháp tìm mã cyclic tốt, danh sách một số mã cyclic tốt được đề xuất, mô phỏng đánh giá bộ mã, đồng thời đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần cứng FPGA. Nội dung cuối, luận án trình bày ứng dụng của nhóm nhân cyclic và cấp số nhân cyclic trong việc làm khóa một số hệ mật. 3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC 3.1.1. Phương pháp xây dựng mạch mã hóa Bước đầu tiên để xây dựng mã LCC là xác định tất cả các nhóm nhân cyclic có thể có trên một vành đa thức, các nhóm nhân này có cấp khác nhau. Sau đó cần xác định nhóm nhân sinh (hay lớp kề sinh của vành) để xây dựng các cấp số nhân. Nó tương ứng với việc xác định đa thức sinh ( )g x trong mã cyclic cổ điển. Trên cơ sở đã xác định được các nhóm nhân sinh, ta chọn phần