Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [ 119 ] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

однако, что промежуточные частичные суммы можно вычислять так, чтобы уменьшить число сложений.

Если продолжать процесс, то можно попытаться уменьшить число умножений при вычислении сз> (х):

с(3) (х) = g(3) (X) (х) = {ах + ах f 1) {dx + dx f do). Выберем

b (x) =x(x + 1)(х + x + I);

тогда

c(3) (X) = (a3d2) b (X) f Rb (.) [сЗ) (x)].

Для вычислени,р аЫ необходимо только одно умножение. Вычеты даются равенствами

g(3) (3) (х = а

d<3) С) (X) = do,

d3) (2) (Х) = do + di + d„

d(3) (3) = + dj X + (do + d,).

Тогда

(0 (x) = d(3) (1) (x), (2) (x) = d<3) (2) (x), c(3) (3) (x) = ad<3) (3) (x).

Для вычисления c) (з) (л;) необходимо два умножения. Мы уже использовали одно умножение для вычисления аМа, так что всего для вычисления с-) (х) с помощью выписанной выше процедуры требуются три умножения. Так как непосредственное вычисление сз> (х) также включает три умножения, то предпочтение надо отдать ему.

11.3. БЫСТРЫЕ ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Дискретное преобразование Фурье (ДПФ) в той форме, как оно задается:

Vj = I o.4Vi, »=о

требует порядка умножений и сложений. Для составного п имеется несколько способов превратить такое преобразование



Vj = I] aVl

Число умножений

БПФ-алгоритм Кули-Тьюки [1965]

п = пп",

i = i+ni", г о, ...,п -\, /" = 0, ...,п"-1 j = n"j + r, j=.0.....n-l, r = 0, ...,n"-l.

/7"-1

i"=0

Число умножений » n (n Ч- n") -f n

БПФ-алгоритм Гуда-Томаса ([I960], [1963])

n = nn", n и n" взаимно просты Перестановка входных символов

i - iN"tr + i"Nn {mod п).

., ., , ,, , f I - iN"n +

\<-\ причем f(modn") J ,,, , , ,,„ „

Nn + N"n" - 1

Перестановка выходных символов / = /V"/ (mod n) y" = yV/(modn")

i = n"j -fn/"(modn)

rn"-1

1 ,/"= I P--

i-=0

i"=0

Число умножений л; n (n -f n")

Рис. 1J.3. Некоторые алгоритмы БПФ.

Фурье В двумерное преобразование или в нечто ему подобное. С вычислительной точки зрения это приводит к существенно более эффективной форме, хотя понять ее структуру труднее. Алгоритмы подобного рода известны под общим названием быстрого преобразования Фурье (БПФ). Некоторые рассматриваемые в этом параграфе алгоритмы, а именно алгоритм Кули-Тьюки и алгоритм Гуда-Томаса, приведены на рис. 11.3.



Уг.г = 1Г>

п"-1 ("=0

Хотя эта формула сложнее исходной, число сложений и умножений при вычислении по ней гораздо меньше, а именно требуется не более п {п -Ь п" + 1) умножений по сравнению с п, необходимых в исходном варианте. Заметим, что при каждом значении i внутренняя сумма представляет собой -точечное преобразование Фурье и при каждом значении i" внешняя сумма представляет собой п-точечное преобразование Фурье. Если соответствующая длина является составным числом, то каждое из этих преобразований в свою очередь можно упростить с помощью быстрого преобразования Фурье. Преобразование длины п с делителями щ таким образом представляется в форме, требующей около niUt умножений.

БПФ-алгоритм Кули-Тьюки можно наглядно представить в виде отображения двумерной таблицы в двумерную таблицу, пример которого для п = 15 и п = 21 приведен на рис. 11.4. Преобразование Фурье сначала применяется к каждой строке, а затем к каждому столбцу. Перед применением преобразования Фурье к столбцам производится поэлементное умножение. Отметим, что компоненты спектра упорядочены иначе, чем компоненты

Начнем с БПФ-алгоритма Кули-Тьюки. Предположим, что п = пп". В выражении для преобразования Фурье сделаем следующую перестановку входных и выходных символов:

1 = i + пЧ", i = О, п - 1, Г = 0, п"-и

j = п"Г + /", / = о, /г - 1, /•" = 0, п"-\.

Тогда

Уп-г+г = "l асч-"-") ("Г+Г)г;,. „,,„.

Раскроем скобки в показателе степени и положим а" = у и а"" = р. Так как порядок элемента а равен пп", то член а""""-" = = 1 можно опустить. Определим теперь двумерные переменные, которые также обозначим через v и V, задавая их равенствами

Vi, i" = Viini", i" = О,.. ., n - 1,

i" = 0.....

Vj-. Г=Уп"Г+Г /=0,..., -1,

i" = Q,...,n"-\.

Это задает отображение входного и выходного векторов данных в двумерные таблицы, причем




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [ 119 ] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.0208