2.24. Линеен намотка на крайни секвенции

.. Да вземем два крайни последователности и дължина и броя, т.е. различни от нула при, а - в. Линеен или апериодична намотка на тези последователности е последователност, определена от отношението

където нула е подходящи интервали. Фиг. 2.30 примери на последователности и. Ясно е, че последователността е ограничен и има дължина на проби.

Преди е показано, че умножаването на DFT на две крайни последователности и намирането на обратен DFT на продукт, се получава същият резултат като кръгова намотка еквивалентни периодични последователности, получени от крайни последователности данни. Въз основа на това (вж. Също примера на фиг. 2.29), може да се получи сравнително просто линеен навиване на две крайни последователности. Конволюция периодична последователност е периодичен и има същия период като самите последователности. Тъй като намотка период (Фиг. 2,30) е равен брой, за да се получи такъв период в кръгова извивка е необходимо, съдържаща проби от тази, постигната допълнение всяка от двете последователности, съответстващи брой нула проби. След това се установи, точкова DFT увеличен последователности на размножават и изпълнява обратна DFT продукт.

Фиг. 2.30. Линейни (апериодична) намотка.

Фиг. 2.31. Изчисляване на линеен намотка с кръгови намотка средства.

Резултатът е необходимото свиване. Фиг. 2.31 илюстрираща тези операции са показани еквивалентни периодични последователности, използвани при изчисляването на кръгова извивка. Ясно е, че добавянето на родителските последователности на ограничен дължина и нула броят въвеждат период на желаната стойност и избягва кръгъл наслагване характеристика кръгова извивка. В резултат, всеки период на последователността (Фиг. 2,31) съвпада с (фиг. 2.30). Горният метод за изчисляване на навиване на две крайни последователности, използвайки DFT нарича бърз алгоритъм намотка в контраст с метода на изчисляване на размера (2,165), или бавно наречената директна намотка. Терминът "бързо" се използва, тъй като може да се изчисли DFT-бързо и ефективно, като се използва един от алгоритмите на БПФ (FFT). Може да бъде показано, че дори с умерени стойности (например, около 30) бързо намотка е ефективно права линия. Поради това, че този метод е важен инструмент за компютърната обработка на сигнали.

За практически приложения е важно да се отбележи, че в горния пример, DFT размер е не е задължително да се ограничи стойност. DFT могат да се извършват от всеки брой на пробите, които отговарят на условието. Ако това условие е изпълнено, за разлика от по-горе описаните методи за последователност и се допълват взаимно брой нула проби. Като еквивалент резултат ще има периодична последователност от нули в края на периода. Ясно е, че тези различия не нарушат желания резултат. Възможност произволен избор е от съществено значение, тъй като практически алгоритми за изчисляване на DFT с различна ефективност са неравноправни. Например, за някои алгоритми, необходими за да се изравни с мощност от 2. В този случай, тъй като ние трябва да изберете брой, равен на 2 градуса и не по-малко от.