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

[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]

1 1 1

0000000 0" 0 110 0 0 0 1 0 10 10 0 10 10 0 110 0 0 10 10 0 10 0

"Mill"

0 10 0 0

0 10 0 1

0 10 0 1

0 110 0

-Vi.

0 10 10

0 М 1 1

0 1 М 1

<х"

0 1111

0 or.

.0 1 М 1.

Рис. 11.6. Малый пятиточечный алгоритм Винограда вычисления БПФ,

Здесь многочлен g (х) фиксирован, многочлен а (х) получается из многочлена v (х) перестановкой коэффициентов с отбрасыванием, а многочлен V (х) получается из многочлена b (х) без отбрасывания коэффициента.

Малый пятиточечный алгоритм Винограда вычисления БПФ получится, если для вычисления произведения g (х) а (х) воспользоваться алгоритмом Винограда вычисления короткой свертки. Обращаясь к таблице на рис. 11.2, находим алгоритм Винограда вычисления четырехточечной циклической свертки, содержащий девять умножений. Воспользуемся этим алгоритмом для построения алгоритма преобразования Фурье. Соединим операции переиндексации алгоритма Рейдера с матричными операциями алгоритма свертки, выполняя соответствующие перестановки строк и столбцов. Далее, так как коэффициенты многочлена g (х) являются фиксированными константами поля GF то произведение g на соответствующую матрицу можно вычислить заранее. Внеся все эти изменения в алгоритм четырехточечной свертки и присоединяя к нему компоненты Vq и v, получаем малый пятиточечный алгоритм Винограда БПФ. На рис. 11.6 приведена запись этого алгоритма в матричном виде:

V = BDAv.

Отметим, что матрица А предварительных сложений и матрица В последующих сложений не являются квадратными. Пятиточечный входной вектор перед выполнением покомпонентного умножения вытягивается в десятиточечный, задаваемый матрицей D. Первая строка матричного равенства связана с вычислением компоненты Vq и не содержит умножений. Остальные девять строк определяются алгоритмом четырехточечной циклической свертки. Одна из констант, на которую происходит умножение, равна еди-



1) Заметим, что для построения 5-точечного ДПФ с девятью умножениями достаточно воспользоваться только тем, что ядро а ДПФ длины 5 удовлетворяет тождеству 1 -j- сс -j- сс -j- сс + а* = 0. Это позволяет организовать вычисление величины vj = 2j?=o-4 полях характеристики 2 (последнее, впрочем, несущественно) следующим образом:

Vo = V(,+ Vj + Vz+ Vs + Vi,

= (fo + fi) + (f 1 + f4) аЯ + (t<2 -f v) -f {v -f v) a,

Vi = (fo + -4) + (Pi + v) a + (v + a? + {v + v) a?,

Vs = iPu + 2) + (Pi + a? + (t)2 + t;) a -f (Wg -f 4) cc*,

V, = t,o+ Vo+ У1+ У2+ 13-

Ha самом же деле использование алгоритма Рейдера сведения ДПФ простой длины к циклической свертке позволяет построить алгоритм 5-точечного БПФ, содержащий всего пять умножений. А именно для произвольных многочленов а (х) = flfl + aix -f ах -f- адл" и b {х) = f bx -f bx -f bifl алгоритм 4-точечной циклической свертки с {х) = Сд -f сх -f сх -f сх = а (х) b (х) (mod (х* - 1)) перепишем в виде

Со = (a, + ai) (60 + 2) + и йг +

+ {ao + a){bi + b.)+aibi,

Со f С2 = (bo + 62) и а; + (х + з) 2] г-

1=-0 1=0

Со + Cl + Сг = {bo Н- 62) (Оо + + il 2j +

+ iai + a){b2 + bs)+a, 6;.

Co + Cl -]- -b Сз -

/ 3 \ / 3 \

\t=0

\t=0 /

в рассматриваемом случае 6 (л:) = сс-f ссл:-f а*л;-f ccV, и, следовательно,

в силу тождества для ядра, 6 = 1, так что по существу эти умножения от-

сутствуют, и приходится выполнять только пять умнолсений. - Прим. перев.

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

Рассмотренный способ реализации малого БПФ-алгоритма Винограда можно использовать в случае, когда п является простым числом. Можно также построить малый БПФ-алгоритм Винограда, когда п является степенью малого простого числа. Вообще говоря, пользоваться малыми БПФ-алгоритмами Вино-



Града можно только при малых длинах. При больших длинах преобразований предпочтительнее алгоритмы с менее четкой структурой, хотя бы и за счет некоторого увеличения числа умножений. Этим требованиям удовлетворяет большой БПФ-алгоритм Винограда.

В общем случае БПФ-алгоритм Винограда строится для длины п, равной произведению простых чисел или степеней простых чисел. Рассмотрим случай двух множителей, когда п = пп". Воспользуемся алгоритмом Гуда-Томаса для преобразования п-точечного преобразования Фурье в двумерное [п X п")-точеч-ное преобразование Фурье. Отдельные компоненты этого двумерного преобразования Фурье могут быть вычислены с помощью соответственно «-точечного и п"-точечного алгоритмов Винограда. Сначала выполняется п-точечное преобразование Фурье каждой строки, а затем п"-точечное преобразование Фурье каждого столбца.

Перед БПФ-алгоритмом Винограда выполняется, однако, еще один шаг. Так как не существенно, применяется ли преобразование Фурье сначала к строкам или сначала к столбцам двумерного блока, то представляется возможным как-то их совместить. Именно это и делает БПФ-алгоритм Винограда. Он совмещает вычисления преобразований строк и столбцов, уменьшая при этом число умножений. Этот метод использует кронекеровское произведение матриц. Сделаем перерыв в изложении, чтобы ввести определение кронекеровского произведения матриц и доказать одну важную теорему. После этого мы сможем завершить построение БПФ-алгоритма Винограда.

Определение 11.5.1. Пусть А = (ац) и В = (Ьц) - матрицы соответственно размеров / X /С и J X L. Тогда кронекеровским произведением матриц А и В, обозначаемым А X В, называется матрица, содержащая строк и КБ столбцов, у которой на пересечении строки с номером (г - !)/-(-/ и столбца с номером {k - 1) L + / стоит элемент

Чтобы проще понять структуру кронекеровского произведения матриц, следует представить матрицу А X В в виде (/ X К)-таблицы, состоящей из (/ X L)-блoкoв, (i, к)-я из которых равен aftB. Непосредственно из определения вытекает, что кронекеровское произведение матриц некоммутативно, но ассоциативно:

А X В В X А, (А X В) X С = А (В X С).

Элементы матриц А X В и В X А одни и те же, но упорядочены по-разному. Очевидно также, что кронекеровское произведение дистрибутивно относительно обычного сложения матриц.




[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.0229