ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² написании студСнчСских Ρ€Π°Π±ΠΎΡ‚
АнтистрСссовый сСрвис

ΠšΠΎΡ€Ρ€Π΅ΠΊΡ‚ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠ΅ ΠΊΠΎΠ΄Ρ‹. 
Π›ΠΈΠ½Π΅ΠΉΠ½Ρ‹Π΅ Π³Ρ€ΡƒΠΏΠΏΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹. 
Код Π₯эмминга

ΠšΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°ΡΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

1, 5}, {3, 4, 5}, {2, 6, 7}} — эта ΡΠΎΠ²ΠΎΠΊΡƒΠΏΠ½ΠΎΡΡ‚ΡŒ элСмСнтов Π½Π΅ ΡΠ²Π». Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ΠΌ А, Ρ‚.ΠΊ. Π½Π΅ ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚воряСт ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ нСпСрСсСкаСмости. Π‘. БистСма мноТСств {x1, x2, …, xn} Π½Π°Π·. Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ΠΌ мноТСства А, Ссли ΠΎΠ½Π° удовлСтворяСт слСд. условиям: Π‘ МинимальноС расстояниС Π₯эмминга (ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ расстояниС) ΠΊΠΎΠ΄Π°, ΠΏΠΎΡ€ΠΎΠΆΠ΄Π°Π΅ΠΌΠΎΠ³ΠΎ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ΠΉ Адамара. Π”Π°Π»Π΅Π΅ остатки слСдуСт ΠΏΠΎΠ΄Π΅Π»ΠΈΡ‚ΡŒ Π½Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‰ΠΈΠ΅ части… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠšΠΎΡ€Ρ€Π΅ΠΊΡ‚ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠ΅ ΠΊΠΎΠ΄Ρ‹. Π›ΠΈΠ½Π΅ΠΉΠ½Ρ‹Π΅ Π³Ρ€ΡƒΠΏΠΏΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠ΄Ρ‹. Код Π₯эмминга (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

Π’Π°Ρ€ΠΈΠ°Π½Ρ‚ 24

1Π°

??

??

??

И

И

И

И

И

И

Π›

Π›

И

Π›

И

И

И

Π›

Π›

И

Π›

И

И

Π›

Π›

И

Π›

Π›

Π›

Π›

И

И

Π›

Π›

Π›

Π›

Π’ Π΄ΠΈΠ·ΡŠΡŽΠ½ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΉ Π½ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΠ΅:

1Π±. БистСма мноТСств {x1, x2, …, xn} Π½Π°Π·. Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ΠΌ мноТСства А, Ссли ΠΎΠ½Π° удовлСтворяСт слСд. условиям:

1) Π›ΡŽΠ±ΠΎΠ΅ мноТСство X{x1, x2, …, xn} явл. помноТСством ΠΌΠ½-Π²Π° А.

2) Π›ΡŽΠ±Ρ‹Π΅ Π΄Π²Π° ΠΌΠ½-Π²Π° Xi, Xj{x1, x2, …, xn}явл. Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΠΌΠΈΡΡ.

3) ОбъСдинСниС всСх ΠΌΠ½-Π², входящих Π² Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅, Π΄Π°Π΅Ρ‚ ΠΌΠ½-Π²ΠΎ А.

Π—Π°Π΄Π°Π½ΠΎ ΠΌΠ½-Π²ΠΎ ?? = {1, 2, 3, 4, 5, 6, 7}:

Π°) {{1, 2}, {3, 4, 5}, {6, 7}} - эта ΡΠΎΠ²ΠΎΠΊΡƒΠΏΠ½ΠΎΡΡ‚ΡŒ элСмСнтов составляСт Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ ΠΌΠ½-Π²Π° А, Ρ‚.ΠΊ. удовлСтворяСт всСм условиям, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Ρ‹ΠΌ Π²Ρ‹ΡˆΠ΅.

Π±) {{1, 5}, {3, 4, 5}, {2, 6, 7}} - эта ΡΠΎΠ²ΠΎΠΊΡƒΠΏΠ½ΠΎΡΡ‚ΡŒ элСмСнтов Π½Π΅ ΡΠ²Π». Ρ€Π°Π·Π±ΠΈΠ΅Π½ΠΈΠ΅ΠΌ А, Ρ‚.ΠΊ. Π½Π΅ ΡƒΠ΄ΠΎΠ²Π»Π΅Ρ‚воряСт ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ нСпСрСсСкаСмости.

2Π°. ΠžΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ ΠΏΡƒΡ‚ΠΈ Π³Ρ€Π°Ρ„Π° (с ΡƒΠΊΠ°Π·Π°Π½ΠΈΠ΅ΠΌ Π΄Π»ΠΈΠ½Ρ‹ ΠΏΡƒΡ‚ΠΈ):

v1v2(1), v1v4(1), v1v2v3(2), v1v2v4(2), v1v2v3v4(3), v2v3(1), v2v4(1), v2v3v4(2),

v3v4(1), v5v1(1), v5v3(1), v5v3v4(2), v5v2(1), v5 v1v2(2), v5v1v4(2), v5

v1v2v3(3), v5 v1v2v4(3), v5 v1v2v3v4(4), v5 v2v3(2), v5 v2v4(2), v5v2v3v4(3).

Для Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π³Ρ€Π°Ρ„Π° Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Ρ†ΠΈΠΊΠ»

2Π± ИдСя Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π£ΠΎΡ€ΡˆΠ΅Π»Π»Π° состоит Π² Ρ€Π°ΡΡˆΠΈΡ€Π΅Π½ΠΈΠΈ мноТСства ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΡ‡Π½Ρ‹Ρ… Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΏΠΎ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌΡƒ ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ: Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС Π² Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Π½ΠΈΠ΅ добавляСтся ΠΎΠ΄Π½Π° новая Π²Π΅Ρ€ΡˆΠΈΠ½Π°, послС Ρ‡Π΅Π³ΠΎ достиТимости Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΏΠ΅Ρ€Π΅ΡΡ‡ΠΈΡ‚Ρ‹Π²Π°ΡŽΡ‚ΡΡ «Ρ‡Π΅Ρ€Π΅Π· Π½Π΅Π΅». Если w — промСТуточная Π²Π΅Ρ€ΡˆΠΈΠ½Π°, Ρ‚ΠΎ Π΄ΠΎΡΡ‚ΠΈΠΆΠΈΠΌΠΎΡΡ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ v ΠΈΠ· Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ u Ρ‡Π΅Ρ€Π΅Π· w ΠΏΠ΅Ρ€Π΅ΡΡ‡ΠΈΡ‚ываСтся ΠΏΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ: D[u;v] = D[u;v] Π˜Π›Π˜ (D[u;w] И D[w;v]). Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρƒ достиТимости:

ΠŸΡƒΡ‚ΠΈ ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³Ρ€Π°Ρ„Π°:

v1v2v3v1, v1v2, v1v2v3, v1v2v3v4, v2v3v1, v2v3v1v2, v2v3, v2v3v4, v3v1, v3v1v2,

v3v1v2v3, v3v4, v5v1, v5v1v2, v5v3, v5v3v4.

?? =, ?? =

U =? =

?? =? =

= =

???(4) = GF (22)? p = 2, q = 4 (p — Ρ…Π°Ρ€-ΠΊΠ° поля, q — ΠΊΠΎΠ»-Π²ΠΎ эл-Ρ‚ΠΎΠ² Π² ΠΏΠΎΠ»Π΅)

2? +

?? + 2? = 3

y = 1, x = 1.

.

Π±3 = Π±2 + 1.

Π±0 = 1;

Π±1 = Π±;

Π±2 = Π±2;

Π±3 = Π±2 + 1;

Π±4 = Π±3 + Π± = Π±2 + Π± + 1;

Π±5 = Π±3 + Π±2 + Π± = Π± + 1;

Π±6 = Π±2 + Π±;

Π±7 = Π±3 + Π±2 = 1;

ΠœΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡ‡Π»Π΅Π½ элСмСнта Π² ΠΏΠΎΠ»Ρ GF (qm) опрСдСляСтся ΠΏΠΎ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅:

НайдСм l: условиС выполняСтся ΠΏΡ€ΠΈ l = 3: Π±48 = Π±6.

НайдСм ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ ΠΌΠ½ΠΎΠ³ΠΎΡ‡Π»Π΅Π½ элСмСнта Π±6:

ΠŸΡ€ΠΎΠ΄Π΅Π»Π°Π² прСобразования, ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ:

M6(x) = x3 + x + 1.

6a

Π›ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ Π³Ρ€ΡƒΠΏΠΏΠΎΠ²ΠΎΠΉ ΠΊΠΎΠ΄ с ΠΏΠΎΠ²Ρ‚ΠΎΡ€Π΅Π½ΠΈΠ΅ΠΌ с ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π°ΠΌΠΈ [??; 1; ??], ?? = 6.

Π”Π»ΠΈΠ½Π° ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ слова n = 6, ΠΊΠΎΠ»-Π²ΠΎ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½Ρ‹Ρ… символов k = 1, ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ расстояниС dmin = 6, ΠΊΠΎΠ»-Π²ΠΎ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΎΡ‡Π½Ρ‹Ρ… символов r = n — k = 5.

ΠŸΠΎΡ€ΠΎΠΆΠ΄Π°ΡŽΡ‰Π°Ρ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π°:

ΠŸΡ€ΠΎΠ²Π΅Ρ€ΠΎΡ‡Π½Π°Ρ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π°:

6Π± МинимальноС расстояниС Π₯эмминга (ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ расстояниС) ΠΊΠΎΠ΄Π°, ΠΏΠΎΡ€ΠΎΠΆΠ΄Π°Π΅ΠΌΠΎΠ³ΠΎ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π΅ΠΉ Адамара

dmin = 2.

7Π° Π’Π°Π±Π»ΠΈΡ†Π° смСТных классов:

Для ΠΊΠΎΠ΄Π° Адамара: 0 = 1, 1 = -1.

ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½ΠΎ сообщСниС

Ρ‚. Π΅.

— ΡΡ‚ΠΎ Ρ€Π°Π·Ρ€Π΅ΡˆΠ΅Π½Π½Π°Ρ кодовая комбинация, Ρ‚. Π΅. ошибок Π½Π΅Ρ‚.

ΠŸΠΎΠ»ΡƒΡ‡Π΅Π½ΠΎ сообщСниС

Ρ‚. Π΅.

— ΠΎΡˆΠΈΠ±ΠΊΠ° ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ»Π° Π² ΠΏΠ΅Ρ€Π²ΠΎΠΌ разрядС, ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ слово Π±Π΅Π· ошибки: (1 -1 -1 1).

7Π±

— ΠΎΡˆΠΈΠ±ΠΎΠΊ Π½Π΅Ρ‚.

— Π΅ΡΡ‚ΡŒ однократная ошибка.

Π’.ΠΊ. ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ расстояниС для Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π° dmin = 2, Ρ‚ΠΎ ΠΏΠΎ ΡΠΈΠ½Π΄Ρ€ΠΎΠΌΡƒ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ ΠΈΠ»ΠΈ отсутствиС ΠΎΠ΄Π½ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎΠΉ ошибки (to + 1? dmin, 2tΠΈ + 1? dmin).

символ

Π°

Π±

с

Π΄

Π΅

ΠΈ

ΠΊ

Ρ€

Ρ‚

частота

, ,

, ,

, .

Π±

0,2353

0,2353

0,2353

0,2353

0,2549*

0,3333*

0,4118*

0,5882*

1*

Π΅

0,1765

0,1765

0,1765

0,1765

0,2353

0,2549

0,3333

0,4118

Ρ€

0,1569

0,1569

0,1569

0,1764*

0,1765

0,2353

0,2549

Π°

0,1373

0,1373

0,1373

0,1569

0,1764

0,1765

ΠΊ

0,098

0,098

0,1176*

0,1373

0,1569

ΠΈ

0,0784

0,0784

0,098

0,1176

с

0,0588

0,0588

0,0784

Π΄

0,0392

0,0588*

Ρ‚

0,0196

8Π±. Код Π₯Π°Ρ„Ρ„ΠΌΠ°Π½Π°:

Π‘ΠΈΠΌΠ²ΠΎΠ»

Π°

Π±

с

Π΄

Π΅

ΠΈ

ΠΊ

Ρ€

Ρ‚

Π’Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ

0,1373

0,2353

0,0588

0,0392

0,1765

0,0784

0,098

0,1569

0,0196

Код

9. Π”Π°Π½Ρ‹ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π΄Π»ΠΈΠ½ L = 4 ΠΈ M = 3, соотвСтствСнно. АпСриодичСская (линСйная) взаимная коррСляция опрСдСляСтся ΠΏΠΎ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅:

. Π’ ΠΌΠ°Ρ‚Ρ€ΠΈΡ‡Π½ΠΎΠΌ Π²ΠΈΠ΄Π΅:

Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ ΠΊΠΎΠ΄ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½Ρ‹ΠΉ сигнал

10. Алгоритм Π“ΠΎΡ€Π½Π΅Ρ€Π°:

ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ стСпСни N:

.

ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΠΌ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ p (z) Π² Π²ΠΈΠ΄Π΅

.

ВычислСниС Π½Π°Ρ‡Π½Π΅ΠΌ с ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ, Π·Π°Ρ‚Π΅ΠΌ суммы, Π΄Π°Π»Π΅Π΅ произвСдСния ΠΈ Ρ‚. Π΄. ΠœΠ΅Ρ‚ΠΎΠ΄ Π“ΠΎΡ€Π½Π΅Ρ€Π° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ N ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ умноТСния ΠΈ N ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ слоТСния.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€: ΠΏΡƒΡΡ‚ΡŒ Π΄Π°Π½ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ p (z) стСпСни

N = 4: p (z) = 4z4 — 2z3 + 3z2 + z — 5.

P (z) = (4z3 — 2z2 + 3z + 1) z — 5 = ((4z2 — 2z + 3) z + 1) z — 5 = (((4z — 2) z +

+ 3) z + 1) z — 5.

ΠŸΡƒΡΡ‚ΡŒ

z = -1: 4Β· z = 4Β· (-1) = -4, -4 — 2 = -6, -6Β· z = -6Β· (-1) = 6, 6 + 3 = 9, 9Β· z = 9Β· (-1)

= -9, -9 + 1 = -8, -8Β· z= = -8Β· (-1) = 8, 8 — 5 = 3.

ΠœΡƒΠ»ΡŒΡ‚ΠΈΠΏΠ»ΠΈΠΊΠ°Ρ‚ΠΈΠ²Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ = 4, аддитивная = 4. Если Π±Ρ‹ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ считался прямо, Ρ‚ΠΎ ΠΌΡƒΠ»ΡŒΡ‚ипликативная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ составила Π±Ρ‹ 6 ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ.

ВычислСниС ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π² Ρ‚ΠΎΡ‡ΠΊΠ°Ρ… с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° «Ρ€Π°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡ‚Π²ΡƒΠΉ»:

ΠŸΡƒΡΡ‚ΡŒ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Π² Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Ρ‚ΠΎΡ‡ΠΊΠ°Ρ… Π°1, Π°2, …, Π°k, k? N. ПолоТим сначала

z = a1. Π’ΠΎΠ³Π΄Π° ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ

p (z) = (z — a1) q (z) + r (z),

Π³Π΄Π΅ q (z) ΠΈ r (z) — частноС ΠΈ ΠΎΡΡ‚Π°Ρ‚ΠΎΠΊ ΠΎΡ‚ Π΄Π΅Π»Π΅Π½ΠΈΡ p (z) Π½Π° (z — a1). Π­Ρ‚ΠΎΡ‚ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°ΡΠΏΡ€ΠΎΡΡ‚Ρ€Π°Π½ΠΈΡ‚ΡŒ Π½Π° Π±ΠΎΠ»ΡŒΡˆΠ΅Π΅ число Ρ‚ΠΎΡ‡Π΅ΠΊ. Рассмотрим ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΈ Π·Π°ΠΏΠΈΡˆΠ΅ΠΌ p (z) = m (z) q (z) + r (z). Π’ Ρ‚ΠΎΡ‡ΠΊΠ΅ z = ai ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ m (z) Ρ€Π°Π²Π΅Π½ Π½ΡƒΠ»ΡŽ, поэтому p (ai) = r (ai). Π’Π΅ΠΏΠ΅Ρ€ΡŒ вычислСниС ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° p (z) свСлось ΠΊ Π²Ρ‹Ρ‡ΠΈΡΠ»Π΅Π½ΠΈΡŽ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° r (z), ΡΡ‚Π΅ΠΏΠ΅Π½ΡŒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ мСньшС.

Π­Ρ‚ΠΎΡ‚ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ для построСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° вычислСния ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° стСпСни N — 1 Π² N Ρ‚ΠΎΡ‡ΠΊΠ°Ρ…. ПолоТим N = 2l. Π Π°Π·Π΄Π΅Π»ΠΈΠΌ N Ρ‚ΠΎΡ‡Π΅ΠΊ Π½Π° Π΄Π²Π΅ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ‹ ΠΈ ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅ΠΌ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΡ‹ ΠΈ.

Π Π°Π·Π΄Π΅Π»ΠΈΠΌ p (z) Π½Π° m1(z) ΠΈ m2(z). ΠŸΡ€ΠΈ этом ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ остатки r1(z) ΠΈ r2(z) стСпСни N/2. Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΎΡΡ‚Π°Π»ΠΎΡΡŒ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ эти остатки Π² N/2 Ρ‚ΠΎΡ‡ΠΊΠ°Ρ…. Для вычислСния остатков ΠΌΠΎΠΆΠ½ΠΎ Π²ΠΎΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Ρ‹ΠΌ ΠΏΡ€ΠΈΠ΅ΠΌΠΎΠΌ, повторяя Π΅Π³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎ.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€: ΠŸΡƒΡΡ‚ΡŒ трСбуСтся Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ

p (z) = 4z3 — 2z2 — 2z + 1 Π² Ρ‚ΠΎΡ‡ΠΊΠ°Ρ… z, Ρ€Π°Π²Π½Ρ‹Ρ… -2, 2, 1, -1.

ΠžΠ±Ρ€Π°Π·ΡƒΠ΅ΠΌ

m1(z) = (z + 2)(z — 2) = z2 — 4, m2(z) = (z — 1)(z + 1) = z2 — 1

ПослС дСлСния p (z) Π½Π° m1(z) ΠΈ m2(z) ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ остатки

r1(z) = 14z — 7, r2(z) = 2z — 1

Π”Π°Π»Π΅Π΅ остатки слСдуСт ΠΏΠΎΠ΄Π΅Π»ΠΈΡ‚ΡŒ Π½Π° ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‰ΠΈΠ΅ части ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠ² m1(z) ΠΈ m2(z):

r1(z)/(z + 2) = -35? p (-2) = -35

Аналогично ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ

p (2) = 21, p (-1) = -3, p (1) = 1

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ