пЮЯОЮПЮККЕКХБЮМХЕ ЯУЕЛШ цНПМЕПЮ

дНЙСЛЕМР БГЪР ХГ ЙЩЬЮ ОНХЯЙНБНИ ЛЮЬХМШ. юДПЕЯ НПХЦХМЮКЭМНЦН ДНЙСЛЕМРЮ : http://fpga.parallel.ru/Colamo/Gorner.htm
дЮРЮ ХГЛЕМЕМХЪ: Sun May 31 14:33:27 2009
дЮРЮ ХМДЕЙЯХПНБЮМХЪ: Mon Oct 1 19:58:47 2012
йНДХПНБЙЮ: koi8-r

оНЯРЮМНБЙЮ ГЮДЮВХ Х ЯСРЭ ОПНАКЕЛШ
яУЕЛЮ ЯДБЮХБЮМХЪ
пЮЯОЮПЮККЕКХБЮМХЕ ЯУЕЛШ цНПМЕПЮ

оНЯРЮМНБЙЮ ГЮДЮВХ Х ЯСРЭ ОПНАКЕЛШ

йКЮЯЯХВЕЯЙХИ ОПХЛЕП ПЕЙСПЯХХ Б ЮКЦНПХРЛЕ - ЯУЕЛЮ цНПМЕПЮ ДКЪ БШВХЯКЕМХЪ ВЮЯРМНЦН НР ДЕКЕМХЪ ЛМНЦНВКЕМЮ n-И ЯРЕОЕМХ НДМНИ ОЕПЕЛЕММНИ P_n(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a МЮ ДБСВКЕМ x - c, Я ОНКСВЕМХЕЛ ЛМНЦНВКЕМЮ n-1-И ЯРЕОЕМХ Q_n-1(x) = b₀x^n-1 + b₁x^n-2 + ... + b_n-2x + b_n-1 Х НЯРЮРЙЮ НР ДЕКЕМХЪ b_n (ПЮБМНЦН P_n(Я)). оПХ ЩРНЛ С МЮЯ ХЯЙНЛШЕ ЙНЩТТХЖХЕМРШ Х НЯРЮРНЙ БШВХЯКЪЧРЯЪ ОН ПЕЙСППЕМРМНИ ТНПЛСКЕ: b_i = c b_i-1 + a_i.

йЮГЮКНЯЭ АШ, МЮЛ МХВЕЦН МЕ ОНДЕКЮРЭ Я ОНЯКЕДНБЮРЕКЭМШЛ УЮПЮЙРЕПНЛ ЮКЦНПХРЛЮ. нДМЮЙН Б РНЛ ЯКСВЮЕ, ЕЯКХ МЮЛ ЛНФМН БНЯОНКЭГНБЮРЭЯЪ ЮЯЯНЖХЮРХБМНЯРЭЧ Х ДХЯРПХАСРХБМНЯРЭЧ ЯКНФЕМХЪ Х СЛМНФЕМХЪ, РН ЛШ ЛНФЕЛ ПЮЯОЮПЮККЕКХРЭ ЯУЕЛС цНПМЕПЮ, БНЯОНКЭГНБЮБЬХЯЭ НАШВМНИ ЯУЕЛНИ ЯДБЮХБЮМХЪ.

яУЕЛЮ ЯДБЮХБЮМХЪ

оСЯРЭ МЮЛ МСФМН БШВХЯКХРЭ БЯЕ ВЮЯРХВМШЕ ЯСЛЛШ ЩКЕЛЕМРНБ y_i НР 1 ДН k, ЦДЕ 1 ≤ k ≤ n. нЙЮГШБЮЕРЯЪ, ВРН ЩРН БНГЛНФМН ЯДЕКЮРЭ ОН ЯУЕЛЕ ЯДБЮХБЮМХЪ ОПХЛЕПМН ГЮ log₂n ЬЮЦНБ, БШОНКМЪЪ МЮ ЙЮФДНЛ ЬЮЦЕ ОПХЛЕПМН ОН n/2 ЯКНФЕМХИ. оПХБЕД╦Л ОПХЛЕП БШВХЯКЕМХЪ БЯЕУ ВЮЯРМШУ ЯСЛЛ ДКЪ n=8 ГЮ 3 ЬЮЦЮ.

1-И ЬЮЦ: БШВХЯКЪЕЛ y₁ + y₂, y₃ + y₄, y₅ + y₆, y₇ + y₈.
2-И ЬЮЦ: БШВХЯКЪЕЛ (y₁ + y₂) + y₃, (y₁ + y₂) + (y₃ + y₄), (y₅ + y₆) + y₇, (y₅ + y₆) + (y₇ + y₈).
3-И ЬЮЦ: БШВХЯКЪЕЛ (y₁ + y₂ + y₃ + y₄) + y₅, (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆), (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆ + y₇), (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆ + y₇ + y₈)

йЮЙ БХДХЛ, БЯЕ ВЮЯРМШЕ ЯСЛЛШ БШВХЯКЕМШ. нРЛЕВЮЕЛ ОПН ЯЕАЪ РН, ВРН

ЛШ БНЯОНКЭГНБЮКХЯЭ ЮЯЯНЖХЮРХБМНЯРЭЧ ЯКНФЕМХЪ Х ВРН
НАЫЕЕ ЙНКХВЕЯРБН НОЕПЮЖХИ БНГПНЯКН (ВЕЦН МЕ АШКН АШ, ЕЯКХ А МЮЛ АШКЮ МСФМЮ РНКЭЙН ОНКМЮЪ ЯСЛЛЮ, МН МЕ МСФМШ ВЮЯРХВМШЕ).

рЕОЕПЭ ПЮЯЯЛНРПХЛ, ЙЮЙ ОПХЛЕМХРЭ ЯУЕЛС ЯДБЮХБЮМХЪ Й ЯУЕЛЕ цНПМЕПЮ.

пЮЯОЮПЮККЕКХБЮМХЕ ЯУЕЛШ цНПМЕПЮ

оЕПЕОХЬЕЛ ЯУЕЛС цНПМЕПЮ Б БЕЙРНПМНИ ТНПЛСКХПНБЙЕ. бБЕД╦Л ОНЯКЕДНБЮРЕКЭМНЯРЭ БЕЙРНПНБ z_i = ( b_i, 1)^T. рНЦДЮ ПЕЙСППЕМРМШЕ ТНПЛСКШ ЯУЕЛШ цНПМЕПЮ ОПХЛСР БХД: z_i = A_iz_i-1, ЦДЕ A_i - РПЕСЦНКЭМЮЪ ЛЮРПХЖЮ БХДЮ ( (c, 0)^T, (a_i, 1)^T). оНЯКЕ ОНДЯРЮМНБЙХ БЯЕУ ТНПЛСК ЛШ БХДХЛ, ВРН z_i = A_iA_i-1...A₁z₀, РН ЕЯРЭ МЮЛ МСФМН БШВХЯКХРЭ БЯЕ ВЮЯРМШЕ ЛЮРПХВМШЕ ОПНХГБЕДЕМХЪ A_iA_i-1...A₁, ОНЯКЕ ВЕЦН СЛМНФХРЭ ХУ МЮ БЕЙРНП z₀. мН ЛЮРПХВМНЕ СЛМНФЕМХЕ ЮЯЯНЖХЮРХБМН, Х Й БШВХЯКЕМХЪЛ ВЮЯРМШУ ОПНХГБЕДЕМХИ ЛШ ЛНФЕЛ ОПХЛЕМХРЭ ЯУЕЛС ЯДБЮХБЮМХЪ, ОПХВ╦Л Я СОПНЫЕМХЪЛХ - БЕДЭ

МХФМХЕ ЯРПНЙХ ЛЮРПХЖ МЮЛ БШВХЯКЪРЭ МЕ МСФМН - НМХ БЯЕ ПЮБМШ (0, 1);
Б БЕПУМЕИ ЯРПНЙЕ ЛЮРПХЖШ ОЕПБШИ ЩКЕЛЕМР БШВХЯКЪЕРЯЪ ГЮ 1 СЛМНФЕМХЕ (БРНПНЕ ЯКЮЦЮЕЛНЕ ПЮБМН 0);
БРНПНИ ЩКЕЛЕМР ОЕПБНИ ЯРПНЙХ БШВХЯКЪЕРЯЪ ГЮ 1 СЛМНФЕМХЕ Х 1 ЯКНФЕМХЕ (БРНПНЕ СЛМНФЕМХЕ - МЮ 1 - БШОНКМЪРЭ МЕ МСФМН).

бШВХЯКЕМХЪ БЕЙРНПНБ z_i МЮ ОНЯКЕДМЕЛ ЩРЮОЕ РНФЕ ЛНФМН БШОНКМЪРЭ МЕ ОНКМНЯРЭЧ (ОНРНЛС ВРН 1 МЕ МСФМН БШВХЯКЪРЭ), Х, ЙПНЛЕ ЩРНЦН, МЕГЮБХЯХЛН ДПСЦ НР ДПСЦЮ. нМХ РНФЕ ГЮИЛСР БЯЕЦН ОН 1 СЛМНФЕМХЧ Х 1 ЯКНФЕМХЧ. оПХ ДНЯРЮРНВМН АНКЭЬНЛ n ЯУЕЛНИ цНПМЕПЮ ЛНФМН ГЮЦПСГХРЭ БЯ╦ ХЛЕЧЫЕЕЯЪ С МЮЯ НАНПСДНБЮМХЕ окхя Б ЩТТЕЙРХБМНЛ ПЕФХЛЕ, АЕГ ОПНЯРНЕБ.