Кириш диссертация мавзусининг долзарблиги ва зарурати

Узунликлар кетма-кетлиги 4	Кўпҳад	Даража
Логарифм
1	2	3	4
0000	0	0	–
1000	1	1	0
0100			1
0010	^2	^2	2
0001	^3	^3	3
1100	1+	^4	4
0110	+^2	^5	5
0011	^2+^3	^6	6
1101	1++^3	^7	7
1010	1+^2	^8	8
0101	+^3	^9	9
1110	1++^2	^10	10
0111	+^2+^3	^11	11
1111	1+ +^2+^3	^12	12
1011	1+^2+^3	^13	13
1001	1+^3	^14	14

2.1-жадвалда келтирилган GF(2⁴) майдонининг х⁴+х+1 модули қурилган. Майдоннинг примитив α элементи бу кўпҳаднинг илдизидир. Илдизи примитив элемент бўлган кўпҳадга примитив кўпҳад дейилади. Агар Π(х) учун GF(2) майдонга нисбатан m нинг бошланғич келтириб бўлмайдиган кўпҳадни танласак, у ҳолда m узунлигининг барча 2^m иккилик кетма-кетлигидан GF(2^m) майдонни оламиз.

Иккилик кетма-кетликни сиқишнинг учта усулини кўриб чиқамиз.
1. Бирликларни ҳисоблаш усули. Ушбу усулдан фойдаланган ҳолда синаш жараёнида ҳисобга олиш маълум белгилар сонининг маълум бир модули, одатда “1” ёрдамида амалга оширилади. Масалан, 20 белгидан иборат бошқариладиган иккилик кетма-кетлик Х га тенг бўлсин:
Х= 0011 1100 0111 1100 0110.
Ушбу кетма-кетликдаги бирликлар сони 11 (ўнлик). Бирликларни 3 битли иккилик ҳисоблагич билан ҳисобланади (модул 8 сони). Кейин ушбу усул билан олинган сигнатура 3 га тенг.
Шуни таъкидлаш керак-ки, бир хил миқдордаги бирликларни ўз ичига олган бир хил узунликдаги (аммо Х тартибидан фарқли) ҳар қандай навбат бир хил сигнатурани беради. Масалан, бу кетма-кетлик:
Z: = 0010 1100 0111 1101 0110. (Z ≠ Х).
Агар биз Х кетма-кетликни мос ёзувлар деб ҳисобласак ва Z тартибини битта объект учун бошқариш керак деб ҳисобласак, у ҳолда Z кетма-кетлиги ва Х кетма-кетликнинг сигнатураси бир-бирига тўғри келиши аниқ. Сигнатураларни таққослаш натижаларига кўра хатолар аниқланмайди. Бу маълумотларнинг сиқилишининг натижасидир - 20 та белгининг ўрнига фақат 3 дан фойдаланамиз.
Агар хатоларни аниқламаслик эҳтимоли мақбул бўлганидан кўпроқ бўлса, сигнатуралардан фойдаланиш мақбул деб ҳисобланади.
2. Ўтишларни ҳисоблаш усули (улаш). Ушбу усул иккилик кетма-кетликда белгилар ўзгаришини ҳисоблаб чиқади. Х кетма-кетликнинг юқорида келтирилган намунаси учун сигнатура 6 га тенг. Маълумотлар тўпламидан фарқ қиладиган кетма-кетлик намуналарини топиш қийин эмас, аммо ушбу усул учун бир хил сигнатурани беради.
3. Полиномлар бўлинишининг қолдиқларини ҳисоблаш усули. Олдинги иккита усулда бўлгани каби, бу ерда ҳам маълумот сиқилган, аммо агар ҳисоб (модул ёки ўтиш даври) модулининг қолган қисми ишлатилган бўлса, унда бу ерда бўлинманинг қолган қисми бўлади. Сигнатура олишнинг ушбу усули, шунингдек, 1-эҳтимоллик билан барча хатоларни аниқлашни кафолатламайди, аммо бир қатор афзалликларга эга. Биринчидан, МПҚларни иккилик кетма-кетликнинг сиқилган характеристикаларига нисбатан тестдан ўтказиш назоратнинг мақбул ишончлилигини таъминлашига ишонч ҳосил қилишимиз керак.
Сигнатураларни кўпайтиришни ҳисоблашда энг кўп ишлатиладиган усулдан фойдаланган ҳолда сигнатураларни таҳлил қилиш самарадорлигини исботлайди.
Полином бўлиниш усули билан сигнатура ҳосил қилиш
N узунликдаги иккилик кетма-кетлик Х расмий ўзгарувчида N-1 даражали кўпайтма билан ифодаланиши мумкин:
P(x) = a_N-1x^N-1 + a_N-2x^N-2+…+ a₂x²+ a₁x¹+ a₀x⁰ (2.21)
Бу ерда a_i = {0,1}; 0≤ i ≤ N-1
Иккилик полиномлар тўплами алгебраик майдон ҳосил қилади, унда қуйидагилар аниқланади:

• 
  2-модул бўйича таркибий қисмларга асосланган қўшимча операция;
  
• 
  полиномни кўпайтириш операцияси;
  
• 
  полиномиал бўлиниш операцияси.
  

N узунликнинг ҳар қандай иккилик кетма-кетлигини Х расмий даражадаги ўзгарувчида N -1 даражали кўпайтма билан ифодалаш мумкин.
Шундай қилиб, илгари кўриб чиқилган Х = 0011 1100 0111 1100 0110 кетма-кетликни кўпхадни тасвирлаш мумкин:
P(X) = x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x² + x¹. (2.22)
Z=0010 1100 0111 1101 0110 - полином
P(Z) = х¹⁷ + х¹⁵ + х¹⁴ + х¹⁰ + х⁹ + х⁸ + х⁷ + х⁶ + х⁴ + х² + х¹. (2.23)
Сигнатурани ҳисоблаш учун m тартибининг қайтариб бўлмайдиган полиноми P(S) дан фойдаланилади.
Агар бошқариладиган объект тўғри ишламаса, у ҳолда Х мос ёзувлар кетма-кетлиги ўрнига Z ≠ X кетма-кетлиги ҳосил бўлади, уларнинг баъзи белгилари мос ёзувлар кетма-кетлигининг белгиларидан фарқ қилади. Буни қуйидагича ифодалаш мумкин: объект Х кетма-кетликни, Y хато кетма-кетлигини ҳосил қилади, Z = X Y унга устун қўйилади, Y эса нолга тенг бўлмаган кетма-кетликни ҳосил қилади. Яъни Y кетма-кетликдаги белгилар Y тартибидаги белгилар Y кетма-кетликдаги белгилардан фарқ қиладиган у 1 га тенг. Қўшиш операциясининг комутатив операцияси туфайли иккита модул Y = X Z. Юқоридаги мисоллар қуйида келтирилган.


(2.24)


P(Y) = x¹⁶ + x⁴.
Яъни, Z тартибидаги мисолда иккита хато мавжуд - 4 ва 16 ўлчовларда (тактларни нолдан ҳисоблаш).
Аммо, кетма-кетликларнинг ўзи билан ишламаймиз, уларни сигнатуралари билан, бунда мос эталон Х ва назорат қилувчи Y тартибларини тавсифловчи P(X) ва P(Z) полиномларини m тартибли P(S) полином бўлинувчига бўлиш орқали ҳисоблаб чиқилади.
Полином-бўлинувчи сифатида полином - бу шундай полиномки бунда ўз-ўзига ва 1 га бўлинади.