Khảo sát một số mã Xiclic vành đa thức X9+1

LÜnh vùc C«ng nghÖ th«ng tin

Kh¶o s¸t mét sè m· xiclic trªn vµnh ®a thøc x9 + 1

PGS.TS. NguyÔn B×nh, KS. Ng« §øc ThiÖn

Khoa Kü thuËt ®iÖn tö 1

Tãm t¾t: C¸c m· xyclic ®· cã nhiÒu øng dông rÊt hiÖu qu¶ trong thùc tiÔn.

Chóng ®îc x©y dùng trªn c¸c Ideal cña vµnh ®a thøc, tuy nhiªn sè Ideal trªn mét

vµnh ®a thøc Ýt nªn sè bé t¹o ra còng h¹n chÕ. §Ó më réng kh¶ n¨ng t¹o thªm c¸c

] [ 2Z x x

m· trªn mét vµnh ®a thøc, bµi b¸o ®Ò cËp ®Õn ph¬ng ph¸p ph©n ho¹ch vµnh ®a 9 1+ ), trªn c¬ së ®ã kh¶o s¸t mét sè bé m· thøc (cô thÓ trªn vµnh ®a thøc

xyclic kh«ng cã trªn vµnh X9+1 theo quan ®iÓm x©y dùng m· xyclic truyÒn

thèng.

1. Mét s« kh¸i niÖm

1.1. Vµnh ®a thøc

NÕu R lµ mét vµnh giao ho¸n th× 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 th«ng th êng víi sè häc c¸c hÖ sè ®îc thùc hiÖn

trong vµnh R.

Trong tr êng nhÞ ph©n, vµnh ®a thøc ®îc ký hiÖu: (f(x); f, •) = Z2[x]/ xn + 1

e(x) = 0 gäi lµ phÇn tö ®¬n vÞ, deg e(x) = 0 (bËc cña e(x) = 0)

(f(x), +) lµ mét nhãm ®èi víi phÐp céng, tháa m·n c¸c tiªn ®Ò cña nhãm.

(f(x), *) lµ nöa nhãm ®èi víi phÐp nh©n, kh«ng tån t¹i f(x), g(x) mµ f(x).g(x) = 0.

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.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.

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ö

Häc viÖn C«ng nghÖ BCVT

®¬n vÞ e(x) víi f(x).e(x) = f(x).

Héi nghÞ Khoa häc lÇn thø 5

C¸c phÇn tö ®¬n vÞ e(x) tháa m·n ®iÒu kiÖn: e(x) = e2(x) = e(x2) ®îc gäi lµ lòy

®¼ng. Trong mét vµnh Z2[x]/x n +1 cã thÓ tån t¹i nhiÒu lòy ®¼ng kh¸c nhau.

a) Nhãm nh©n xyclic (CMG - Cyclic Multiplicate Groups)

Nhãm nh©n xyclic 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 = {a , a 2, a 3,..}

Trong ®ã: A lµ nhãm nh©n xyclic; a 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).

b) Nhãm nh©n xyclic ®¬n vÞ

Nhãm nh©n xyclic ®¬n vÞ lµ mét nhãm bao gåm mäi ®¬n thøc vµ cã cÊp lµ n.

Ký hiÖu lµ I , hay nhãm nh©n xyclic ®¬n vÞ lµ nhãm nh©n xyclic víi phÇn tö

sinh lµ x.

I = {x, (x)2, (x)3, ..., (x)n-1, 1}

c) Nhãm nh©n xyclic víi phÇn tö sinh a(x)

Nhãm nh©n xyclic 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.3. CÊp sè nh©n xyclic (CGP - Cyclic Geometic Progressions) trªn vµnh

®a thøc

CÊp sè nh©n xyclic 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)}.

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

Trong ®ã: 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.

2. CÊu t róc c¸c nhãm nh©n xyclic t rong vµnh ®a thøc Z2[x] /x9 + 1

2.1. CÊu tróc c¸c nhãm nh©n

Víi vµnh Z2[x]/ x9 + 1, ta cã n = 9 (lµ sè lÎ).

+ Khai triÓn nhÞ thøc: x9 + 1 = (1 + x)(1 + x + x2)(1 + x3 + x6).

Vµnh ®a thøc nµy cã cã 29 - 1 = 511 phÇn tö kh¸c 0.

Häc viÖn C«ng nghÖ BCVT

Trong ®ã cã: 256 phÇn tö cã träng sè lÎ.

LÜnh vùc C«ng nghÖ th«ng tin

255 phÇn tö cã träng sè ch½n.

+ CÊp cùc ®¹i cña ®a thøc a(x) ®îc x¸c ®Þnh nh sau:

Max ord(a(x)) = 2m -1 = 26 - 1 = 63.

ë ®©y m còng chÝnh b»ng max ms = 6, hay cÊp lín nhÊt cña ®a thøc bÊt kh¶

quy trong khai triÓn nhÞ thøc x9 +1.

+ Ph©n tÝch max ord(a(x)) ra thõa sè nguyªn tè ®Ó x¸c ®Þnh c¸c íc cña nã:

Max ord(a(x)) = 63 = 3.3.7.

+ CÊp c¸c phÇn tö trong vµnh lµ c¸c íc sè cña max ord(a(x)), t ¬ng øng c¸c nhãm

nh©n trong vµnh cã c¸c cÊp lµ: 1, 3, 7, 9, 21, 63.

+ X¸c ®Þnh c¸c chu tr×nh Cs.

C¸c chu tr×nh Cs ®îc x¸c ®Þnh nh sau: - - =

{

}1

2 s .2 ,...,

” s s , .2, .2 sm s .2 sms trong ®ã s mod n

ﬁ |C 0| = m 0 = 1

C0 = {0} C1 = {1, 2, 4, 8, 7, 5} ﬁ |C 1| = m 1 = 6

ﬁ C3 = {3, 6} |C 3| = m 3 = 2

§a thøc e(x) lµ mét lòy ®¼ng khi vµ chØ khi tËp c¸c hÖ sè kh¸c kh«ng cña nã lµ

hîp mét sè c¸c chu tr×nh Cs nµo ®ã. C¸c lòy ®¼ng chÝnh lµ c¸c phÇn tö ®¬n vÞ

cña c¸c nhãm nh©n xyclic trong vµnh ®a thøc. Ta t×m ®îc c¸c lòy ®½ng nh sau:

B¶ng 1: C¸c lòy ®¼ng cña vµnh ®a thøc Z2[x]/ x9 + 1

D¹ng sè mò C¸c chu tr×nh C¸c lòy ®¼ng cña ®a thøc t ¬ng øng

(0124578) e1(x) = 1 + x + x2 + x4 + x5 + x7 + x8 C1

(036) e2(x) = 1 + x3 + x6 C0 ¨ C0 ¨ C3

e3(x) = e0(x) = 1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 (012345678) C0 ¨ C1 ¨ C3

(0) e4(x) = 1 C0

(36) e5(x) = x3 + x6 C3

(124578) e6(x) = x + x2 + x4 + x5 + x7 + x8 C1

(12345678) e7(x) = x + x2 + x3 + x4 + x5 + x6 + x7 + x8 C1 ¨ C3

Häc viÖn C«ng nghÖ BCVT

256 phÇn tö cã träng sè lÎ bao gåm:

Héi nghÞ Khoa häc lÇn thø 5

1 nhãm nh©n cÊp 63 víi phÇn tö sinh a1(x) = (012), víi lòy ®¼ng e1(x) =

(0124578).

1 nhãm nh©n cÊp 3 víi phÇn tö sinh a2(x) = (147), víi lòy ®¼ng e2(x) = (036).

1 nhãm nh©n cÊp 1 víi phÇn tö sinh a3(x) = e3(x) = (012345678).

3 nhãm nh©n cÊp 63 víi phÇn tö sinh a4(x) = (014), a5(x) = (016), a6(x) = (02357)

víi lòy ®¼ng e4(x) = (0).

1 nhãm nh©n cÊp 21 víi phÇn tö sinh b1(x) = (12345), víi lòy ®¼ng e4(x) = (0).

3 nhãm nh©n cÊp 21 víi phÇn tö sinh a7(x) = (124), a8(x) = (245), a9(x) = (128) víi

lòy ®¼ng e4(x) = (0).

Mét nhãm nh©n cÊp 7 víi phÇn tö sÝnh b2(x) = (12345) víi lòy ®¼ng e4(x) = (0).

2.2. Ph ¬ng ph¸p ph©n ho¹ch vµnh ®a thøc thµnh nhãm nh©n xyclic

C¸c bíc ph©n ho¹ch vµnh ®a thøc ®Ó x©y dùng c¸c nhãm nh©n xyclic cã thÓ kh¸i

qu¸t nh sau:

- T×m cÊp cùc ®¹i cña nhãm nh©n xyclic trong vµnh.

- T×m phÇn tö sinh cã cÊp lín nhÊt.

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 gåm c¸c phÇn tö cã träng sè ch½n. H¬n n÷a do vµnh ®èi

xøng nªn khi biÕt nöa vµnh cã thÓ suy ra nöa vµnh kia. V× vËy tr íc tiªn ta ®i

x¸c ®Þnh c¸c phÇn tö cã träng sè lÓ. Trong c¸c phÇn tö cã träng sè lÎ x¸c ®Þnh

c¸c phÇn tö sinh cã cÊp lín nhÊt.

Sau ®ã x©y dùng tÊt c¶ c¸c nhãm nh©n chøa c¸c phÇn tö cã träng sè lÎ. §Ó x©y

dùng ®îc tÊt c¶ c¸c nhãm nh©n ta ph¶i thùc hiÖn c¸c bíc:

o X¸c ®Þnh tÊt c¶ c¸c ®a thøc lòy ®¼ng trong vµnh, trªn c¬ së ph©n tÝch

c¸c chu tr×nh.

o Chän c¸c ®a thøc lòy ®¼ng cã träng sè lÎ ®Ó x©y dùng c¸c nhãm nh©n

chøa chóng.

- X©y dùng tÊt c¶ c¸c nhãm nh©n xyclic cã thÓ cã cña vµnh. Tïy theo tõng lòy

®¼ng mµ mçi lòy ®¼ng cã thÓ tham gia trong nhiÒu nhãm nh©n.

- LÊy ®èi xøng tÊt c¶ c¸c nhãm nh©n cã chøa c¸c phÇn tö cã träng sè lÎ sÏ t¹o

®îc tÊt c¶ c¸c nhãm nh©n cã chøa c¸c phÇn tö cã träng sè ch½n.

3. Kh ¶o s¸t mét sè m· xyclic vµ xyclic côc bé t rªn vµnh ®a thøc X 9 + 1

Häc viÖn C«ng nghÖ BCVT

3.1. Kh¸i niÖm m· xyclic côc bé (XCB)

LÜnh vùc C«ng nghÖ th«ng tin

M· xyclic côc bé lµ m· hÖ thèng tuyÕn tÝnh (n, k) trong ®ã:

( ix i

) 1

]

(

= - 0,1, 2,..., k k dÊu th«ng tin ®îc chän lµ k ®¬n thøc cã d¹ng vµ lµ nhãm

[ Z x 2

) x + . 1n

= -

n k

/ nh©n xyclic cÊp k cña vµnh

dÊu kiÓm tra ®îc chän lµ mét tËp con kh«ng trèng tïy ý nµo ®ã c¸c líp

kÒ cña nhãm nh©n nµy.

TËp c¸c tr ëng líp kÒ t¹o m· sÏ cho ta m« t¶ ®Çy ®ñ cña m· xyclic côc bé.

3.2. Mèi quan hÖ gi÷a m· xyclic vµ xyclic côc bé

Theo quan ®iÓm x©y dùng m· xyclic th«ng th êng: m· xyclic 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· XCB 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, ta hoµn toµn cã thÓ dïng lý thuyÕt x©y dùng c¸c ®a thøc sinh cña m·

xyclic ®Ó t¹o c¸c tr ëng líp kÒ cho c¸c m· XCB. 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· xyclic:

M· XCB ®îc x©y dùng tõ:

) ( g x x

+ - 1; x + Tr ëng líp kÒ lµ mét ®a thøc sinh g(x) tháa m·n: + . 1 §a thøc sinh lµ íc cña

- BËc cña ®a thøc sinh b»ng r víi 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:

1 x

= = x x = = ... x - = . 0

Trªn c¬ së ph©n tÝch nh vËy th× m· xyclic lµ mét líp kÒ ®Æc biÖt cña m· XCB.

Hay m· xyclic lµ mét d¹ng ®Æc biÖt cña m· XCB.

3.3. Kh¶o s¸t mét sè m· xyclic vµ xyclic côc bé trªn vµnh ®a thøc x9 + 1

a) Kh¶o s¸t m· xyclic (n, k) víi k = m.

Trong mét vµnh ®a thøc lu«n tån t¹i m· xyclic (m, m) cã d0 = 1, m· nµy ®îc x©y

= = -

{

i x i ,

I 1, m

} 1

dùng tõ nhãm nh©n ®¬n vÞ.

M· nµy kh«ng cã kh¶ n¨ng ph¸t hiÖn vµ söa sai. Do sè dÊu th«ng tin k = m, nªn ®Ó

t¹o c¸c m· cã kh¶ n¨ng ph¸t hiÖn vµ söa sai x©y dùng trªn c¸c nhãm nh©n xyclic th×

Häc viÖn C«ng nghÖ BCVT

yªu cÇu ph¶i tháa m·n ®iÒu kiÖn n > m . Hay nãi c¸ch kh¸c lµ cÊp cña nhãm nh©n

Héi nghÞ Khoa häc lÇn thø 5

xyclic t¹o m· ph¶i lín h¬n vµ b»ng béi cña m, nhãm nh©n ®¬n vÞ I ph¶i lµ nhãm

nh©n con cña nhãm nh©n xyclic t¹o m·.

)

Nhãm nh©n xyclic t¹o m· (n, m) ph¶i tháa m·n 2 ®iÒu kiÖn: - Nhãm nh©n xyclic ®¬n vÞ cã cÊp m ph¶i lµ mét nhãm con cña nhãm nh©n

(

- CÊp cña nhãm nh©n xyclic t¹o m· (n, m) ph¶i lµ íc nµo ®ã cña cÊp sè lín max ord a

M hoÆc n m m n xyclic cÊp n ( .

) x .

n nhÊt c¸c phÇn tö trong vµnh:

Trong vµnh Z2[x]/ x9 + 1, ta cã m = 9.

( + = +

) (

)

+ + x 1 1 x + + x 1 x 1 x x .

Ta cã max ord a(x) = 26 - 1 = 63 = 1.3.3.7.

Do ®ã, trong vµnh nµy tån t¹i c¸c nhãm nh©n cã cÊp: 1, 3, 7, 9, 21, 63. Nh ng

chØ cã c¸c nhãm nh©n cã cÊp 9 vµ 63 míi t¹o ®îc m· xyclic. M· xyclic ®îc x©y

dùng trªn c¸c nhãm nh©n cã cÊp 9 vµ 63 lµ 2 lo¹i m· xyclic (9, 9) vµ (63, 9).

= = = =

{

i x i ,

} 0,8

( ) a x i ,

} 0, 62

M· (9, 9) (cid:219) , m· (63, 9) (cid:219) .

* M· xyclic (63, 9) x©y dùng trªn nhãm nh©n cÊp 63

XÐt ®a thøc sinh a = (1 + x2 + x3 + x5 + x7), ®a thøc nµy cã cÊp 63. CÊu tróc cña

nhãm nh©n lµ A = {ai = (1 + x2 + x3 + x5 + x7); i = 0, 1, 2,…, 62}.

§¸nh gi¸:

Sè tæng kiÓm tra (TKT) tù trùc giao cña m· nµy: J = 17, do ®ã kho¶ng c¸ch tèi

0 j

thiÓu d0 = 18. - Ø ø ‡ n (cid:229) Œ œ Theo giíi h¹n díi cña ®é dµi tõ m· (giíi h¹n Griesmer): Œ œ d 0 2

Ø ø = + + + + + + + + = ‡ n 18 9 5 3 2 1 1 1 1 41 (cid:229) Œ œ ta cã: . Œ œ 18 2 j

Víi m· nµy cã ®é dµi tõ m· lµ n = 63 > 41 (cid:222) m· kh«ng tèi u.

b) Kh¶o s¸t c¸c m· xyclic (n, k) víi k < m.

* M· xyclic (63, 7).

)

= + + + + + 1 x x x x x víi phÇn tö sinh

( h x )

)

( a = + + 1

« Chän nhãm nh©n xyclic theo modulo ( x x 014 cña nhãm nh©n lµ: cã cÊp lµ 63, lµm m· xyclic (63,7).

Häc viÖn C«ng nghÖ BCVT

Nhãm nh©n nµy cã d¹ng nh sau:

LÜnh vùc C«ng nghÖ th«ng tin

(

{ a=

= = =

{

) ( h x i ,

} 0,1, 2,..., 62

) i 014 mod

) ( h x i ,

A mod

} 0,1, 2,..., 62

Do m· nµy lµ m· xyclic cã kh¶ n¨ng trùc giao, cho nªn ph¶i gi¶i m· 2 cÊp. ë cÊp

ngìng thø nhÊt gi¶i m· ra c¸c cÆp dÊu th«ng tin, sau ®ã qua bíc gi¶i m· cÊp ng-

ìng thø hai míi gi¶i m· ®îc toµn bé c¸c dÊu th«ng tin.

§¸nh gi¸:

Sè TKT tù trùc giao cña m· nµy lµ: J = 30, do ®ã kho¶ng c¸ch tèi thiÓu d 0 =

31.

Ø ø = = M 16 CÊp ngìng gi¶i m· lµ: . Œ œ Œ œ + 30 1 2

Theo giíi h¹n Griesmer: - Ø ø Ø ø = = + ‡ n + + + + + = 31 16 8 4 2 1 1 63 (cid:229) (cid:229) (cid:222) M· nµy lµ m· tèi u. Œ œ Œ œ Œ œ Œ œ d 0 i 2 31 i 2

c) Kh¶o s¸t m· xyclic côc bé.

]

* M· XCB (27, 9)

[ Z x 2

1 / M· XCB (27 9) ®îc x©y dùng tõ 3 cÊp sè nh©n (CGP) xyclic lÊy trong ph©n ho¹ch x + thµnh c¸c CGP cÊp 9. CGP1 chÝnh lµ nhãm nh©n vµnh ®a thøc

xyclic ®¬n vÞ (lµ ®a thøc th«ng tin). Chän CGP2 (tr ëng líp kÒ lµ (7)) vµ CGP3

(tr ëng líp lµ (11)) lµm c¸c dÊu kiÓm tra. Do CGP2 vµ CGP3 lµ 2 líp kÒ lÎ liªn

tiÕp, cho nªn m· nµy sÏ lµ m· XCB cã kh¶ n¨ng trùc giao.

CÊu tróc tõ m· XCB (27,9) nµy nh sau: (c¸c dÊu m· biÓu diÔn ë d¹ng thËp

ph©n).

1 2 4 8 16 32 64 12 25 7 14 28 56 11 22 44 38 25 11 22 44 88 17 35 19 38 26

8 6 2 4 8 5 9 6 2 3 6 1

NÕu biÓu diÓn m· XCB nµy theo tr ëng líp kÒ th× cã d¹ng {1, 7, 11}.

Sè TKT cã kh¶ n¨ng trùc giao J = 6 (cid:222) d0 = 7. Theo giíi h¹n Griesmer th× m·

nµy còng kh«ng tèi u:

3.4. Ph ¬ng ph¸p gi¶i m· ngìng

Cã c¸c phu¬ng ph¸p gi¶i m· nguìng sö dông cho viÖc gi¶i m· XCB:

+ Gi¶i m· nguìng theo ®a sè (GM§S). + Gi¶i m· nguìng ®¹i sè kh¸c: gi¶i m· nguìng trªn ®a sè 1 biÓu quyÕt (GM§S

+ 1), gi¶i m· nguìng trªn ®a sè 2 biÓu quyÕt (GM§S +2).

Häc viÖn C«ng nghÖ BCVT

* Ph ¬ng ph¸p gi¶i m· ngìng theo ®a sè (GM§S)

Héi nghÞ Khoa häc lÇn thø 5

®îc J tæng kiÓm tra trùc giao cho mét dÊu m· nµo ®ã.

{

}

mS m ,

J= 1,

= 1

+ Ø ø J 1 ‡ ø S (cid:229) Œ œ NÕu , trong ®ã xØ lµ sè nguyªn nhá nhÊt lín h¬n hoÆc b»ng x. Œ œ Œ œ 2

Th× coi ei = 1 cã sai ë dÊu thø i, ngîc l¹i ei = 0: dÊu thø i thu ®óng.

Mçi tæng kiÓm tra (TKT) trong hÖ J TKT nµy cho phÐp ®a ra c¸c dÊu ai ë d¹ng

tæ hîp tuyÕn tÝnh cña c¸c dÊu kh¸c mµ nã kh«ng n»m trong mét TKT. V× vËy

cã 2t TKT (2t = d0 –1 = J ) ®Ó gi¶i m· ®óng c¸c dÊu ai theo biÓu quyÕt ®a sè.

Do c¸c TKT ph¶i tháa m·n víi bÊt kú tõ m· nµo th× tÝnh chÊt tuÇn hoµn cña bé

m· míi cã hiÖu qu¶ ®Ó gi¶i m· c¸c dÊu tiÕp theo. Do vËy ta dÞch chuyÓn tuÇn

hoµn tõ m· vµ l¹i ¸p dông biÓu quyÕt theo ®a sè. Cø nh vËy sÏ thùc hiÖn gi¶i m·

cho tÊt c¶ c¸c dÊu m·.

Nh vËy víi m· xyclic tù trùc giao th× ph¬ng ph¸p gi¶i m· ngìng ®¬n gi¶n h¬n

nhiÒu so víi c¸c ph¬ng ph¸p gi¶i m· kh¸c vÒ thiÕt bÞ gi¶i m· víi bé m· cã cïng

chiÒu dµi. ThiÕt bÞ gi¶i m· chØ gåm bé ghi, bé céng vµ thiÕt bÞ ngìng theo ®a

sè. ChÝnh cã u ®iÓm nµy nªn viÖc thùc hiÖn kü thuËt sÏ ®¬n gi¶n.

§èi víi c¸c m· cã kh¶ n¨ng trùc giao, ta cã thÓ thiÕt lËp ®îc hÖ TKT cã kh¶ n¨ng

trùc giao. Mét hÖ TKT cã kh¶ n¨ng trùc giao nÕu tån t¹i mét tæ hîp tuyÕn tÝnh + + + ... = M x i 1 x i x im c¸c dÊu m·: tháa m·n ®iÒu kiÖn sau:

jx Mˇ

+ Tæ hîp tuyÕn tÝnh c¸c dÊu m· M cã mÆt trong mäi TKT.

C¸c dÊu cßn l¹i: chØ n»m ë nhiÒu nhÊt mét TKT.

Trªn c¬ së ®ã ta cã thÓ coi tËp M ®ãng vai trß nh mét dÊu m· x trong hÖ

TKT trùc giao. Theo nguyªn t¾c gi¶i m· theo ®a sè, ta cã thÓ gi¶i m· cho tËp M

cÆp dÊu m·.

4. Ch¬ng t r×nh m« pháng m· hãa vµ gi ¶ i m· mét sè m· xyclic vµ xyclic

côc bé trªn vµnh ®a thøc X 9 + 1

Ch¬ng tr×nh m« pháng ®îc viÕt trªn phÇn mÒm MATLAB, víi u ®iÓm: - Ch¬ng tr×nh ®¬n gi¶n, tèc ®é tÝnh to¸n nhanh. - Cã thÓ m« pháng thªm c¸c bé m· kh¸c dùa trªn c¸c hµm mµ ch¬ng tr×nh

Häc viÖn C«ng nghÖ BCVT

m« pháng ®· lËp.

LÜnh vùc C«ng nghÖ th«ng tin

Giao diÖn cña ch¬ng tr×nh m« pháng m· hãa vµ gi¶i m·.

4.1. M· cã ®é dµi 63

4.2. M· cã ®é dµi 27

KÕt luËn

M· xyclic lµ mét trong c¸c m· dÔ thùc hiÖn vµ ®· ®îc øng dông nhiÒu trong

thùc tÕ. ¦u ®iÓm cña m· xyclic ®ã lµ: lµ lo¹i m· cã cÊu tróc ®¹i sè t êng tËn, cã

chÊt lµ mét nhãm con cña nhãm céng trong vµnh. Tuy nhiªn, sè Ideal trong mét

vµnh ®a thøc Ýt nªn kh¶ n¨ng t¹o c¸c bé m· xyclic còng bÞ h¹n chÕ.

dùng c¸c m· xyclic vµ xyclic côc bé. Kh¸c víi c¸c m· xyclic th«ng th êng (mçi tõ m· lµ