- Trang Chủ
- Điện - Điện tử
- Một số phương pháp mới xác định cấp của đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng
Xem mẫu
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Một số phương pháp mới xác định cấp của đa thức
trên vành đa thức sử dụng tính chất của nhóm nhân
cyclic đối xứng
Nguyễn Trung Hiếu
Khoa Kỹ thuật Điện tử 1, Học viện Công nghệ Bưu chính Viễn thông, Hà Nội, Việt Nam
Email: hieunt@ptit.edu.vn
Tóm tắt– Mã cyclic cục bộ (LCC) là một mã khối được tạo giảm độ phức tạp tính toán, rút ngắn thời gian tính toán tới
thành dựa trên các phân hoạch của vành đa thức. Phương pháp mức tối đa và đặc biệt là có thể xác định được cấp của toàn bộ
điển hình xây dựng mã LCC là dựa trên nhóm nhân cyclic với ưu các đa thức trên các vành lớn mà các nghiên cứu trước đây
điểm nổi bật là số lượng mã có thể tạo ra bởi phương pháp này chưa đề cập.
nhiều hơn phương pháp tạo mã cyclic dựa trên Ideal. Việc tìm
được nhóm nhân đạt cấp cực đại trong vành đa thức có ý nghĩa Nội dung bài báo được chia làm năm phần. Phần II, trình
và vai trò quan trọng nhất trong việc cấu trúc lên mã cyclic cục bày sự phân bố đa thức dựa trên cấp của đa thức trên nhóm
bộ. Bài báo này sẽ đề xuất một số phương pháp mới xác định các nhân cyclic. Trong phần III, đề xuất một phương pháp chứng
cấp của các đa thức trên vành đa thức sử dụng tính chất của minh tính chất của nhóm nhân cyclic đối xứng, trong khi phần
nhóm nhân cyclic đối xứng. IV đề xuất hai thuật toán mới xác định cấp của đa thức trên
vành và thảo luận về sự cần thiết của chúng. Cuối cùng, kết
Từ khóa– Mã cyclic cục bộ (LCC-Local Cyclic Code), Nhóm luận bài báo được trình bày trong phần V.
nhân cyclic (CMG- Cyclic Multiplicative Group), Vành đa thức,
phân hoạch. II. PHÂN BỐ ĐA THỨC DỰA TRÊN CẤP CỦA ĐA THỨC
TRÊN NHÓM NHÂN CYCLIC
I. GIỚI THIỆU
Lý thuyết mã hóa đã được nghiên cứu và ứng dụng trong
Định nghĩa 1: [10] CMG trên 2 > x@ / xn 1 là tập hợp
rất nhiều lĩnh vực của cuộc sống, đặc biệt là trong lĩnh vực
truyền thông. Lý thuyết về mã hóa phát triển theo ba hướng A ^a x
- , i
i
1, 2,....` , với a x
- 2 > x@ / xn 1\ ^0`
lớn đó là: mã nguồn, mã kênh (có khả năng phát hiện và sửa
lỗi) và mật mã [1], [2]. Mã cyclic là một lớp mã quan trọng ord a x
- A
-
trong các mã khối tuyến tính, có khả năng phát hiện và sửa lỗi
tốt, được ứng dụng trong điện tử dân dụng, các hệ thống lưu
trữ, các hệ thống truyền thông vì có nhiều phương pháp mã a x
- - phần tử sinh của CMG A .
hóa và giải mã hiệu quả.
Định nghĩa 2: Cấp của đa thức [9].
Mã cyclic được Eugene Prange nghiên cứu đầu tiên năm
1957 [1] . Ngày nay, mã cyclic vẫn nhận được sự quan tâm từ Cấp của đa thức a( x) 2 [ x] / ( xn 1) (ký hiệu ord a( x) )
các nhà nghiên cứu trên toàn thế giới [3]-[8]. Một hướng là số nguyên dương m nhỏ nhất thỏa mãn:
nghiên cứu mới về mã cyclic được biết đến là mã cyclic cục
bộ (LCC-Local Cyclic Code) được đưa ra bởi tác giả Nguyễn
a m1 ( x) a( x) mod ( x n 1) hoặc
Bình vào những năm 1980 [10]. LCC thu hút được nhiều nhà
nghiên cứu và một số kết quả nghiên cứu về LCC đã được
công bố trên các tạp chí chuyên ngành và hội nghị khoa học a m ( x) e( x) mod ( x n 1)
-
quốc tế [9]-[14].
Các nghiên cứu trước đây chủ yếu tập trung vào cấu trúc Trong đó e( x) là lũy đẳng trong vành, e( x) e2 ( x) .
mã [9], [10], [11], [13], [14], thực hiện cứng hóa bộ mã LCCs
[12]. Nhìn chung, LCC được xây dựng dựa trên cấu trúc và Như vậy, a( x) tạo nên một nhóm cyclic cấp m vành.
phân hoạch CMG của vành đa thức [9], [11].
Định lý 1: [9] Xét a( x) là phần tử của nhóm nhân nào đó,
Tuy nhiên, thuật toán xác định cấp của đa thức trên vành cấp cực đại của a( x) được xác định như sau:
đa thức đến nay mới chỉ sử dụng phương pháp vét cạn có độ
phức tạp lớn, bị hạn chế về năng lực và thời gian tính toán. Bài
báo này nghiên cứu một phương pháp chứng minh tính chất
- Nếu n lẻ ( n 2k 1 ) và x n 1 f ( x) ;
i trong đó
của nhóm nhân cyclic đối xứng, đề xuất hai bổ đề phân bổ đa f i ( x) là các đa thức bất khả quy. Khi đó
thức trong nhóm nhân cyclic theo cấp và đề xuất các thuật max ord (a( x)) m
2 1 . Trong đó m max deg fi ( x) .
toán cải tiến xác định cấp của đa thức trên vành nhằm làm
ISBN: 978-604-67-0635-9 248
- Hội+ӝL7KҧR4XӕF*LDYӅĈLӋQ7ӱ7UX\ӅQ7K{QJYj&{QJ1JKӋ7K{QJ7LQ (&,7
-
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
- Nếu n chẵn ( n 2s (2k 1) ) và x 2k 1 1 f ( x) ;
i Như vậy, ta có: bmk ( x) a( x)mk k e( x)
trong đó fi ( x) là các đa thức bất khả quy. Khi đó Bổ đề được chứng minh.
max ord (a( x)) 2s (2m 1) . Trong đó m max deg fi ( x) .
Bổ đề 2: Số các đa thức đạt cấp cực đại trên vành được
Bổ đề 2.1: Trong một nhóm nhân cyclic cấp m , cấp của đa tính bằng N .M (m) , với m là cấp cực đại và N là số nhóm
thức thứ k bằng: nhân cyclic đạt cấp cực đại độc lập (nghĩa là không có nhóm
nhân nào là hoán vị của nhóm nhân khác).
m Chứng minh:
mk
-
gcd m, k
- Theo hệ quả của bổ đề 1, số đa thức đạt cấp cực đại trong
một nhóm nhân cyclic được tính bởi hàm Phi-Euler ( M (m) ).
Hệ quả: Trong một nhóm nhân cyclic cấp m thì:
Bổ đề hiển nhiên đúng.
+ Các đa thức tại vị trí thứ k nguyên tố cùng nhau với m
thì có cấp bằng m , nghĩa là GCD m, k
- 1 thì mk m . Ví dụ 1: Xét vành đa thức 2 [ x] / ( x5 1) , không xét lũy
đẳng nuốt en ( x) 1 x x x x 4 , có 2 nhóm nhân như
2 3
+ Số đa thức đạt cấp m là M (m) . Trong đó: sau:
1· §
M m
- m ¨1 e e ek
¸ là hàm Phi-Euler, với m p11 . p22 ... pk ; ° 012
- , 024
- , 3
- , 034
- , 023
- , 1
- , 123
nguon tai.lieu . vn
