Пристрій для обчислення коефіцієнтів фур’є

Изобретение относится к вычислительной технике и может быть использовано в устройствах вычисления спектров, сверток и, корреляционных функций на основе использования алгоритма быстрого преобразования Фурье. Известно устройство для быстрого преобразования Фурье, содержащее шесть регистров, умножитель, сумматор, регистр произведений, два регистра сумм, два коммутатора и блок микропрограммного управления, причем, выходы первого и второго входных регистров через первый коммутатор подключены к входам умножителя, выходы третьего и четвертого входных регистров и выход регистра произведений через второй коммутатор подключены к входам сумматора, выход которого является выходом устройства, выходы блока микропрограммного управления подключены к управляющим входам коммутаторов, выходы пятого и шестого входных регистров подключены к дополнительным информационным входам первого коммутатора, а выходы регистров, сумм - к дополнительным информационным входам второго коммутатора [Авт.св. СССР №995096, кл. G 06 F 15/332]. Известно также устройство для быстрого преобразования Фурье, содержащее сумматор, два сумматоравычислителя, четыре регистра, два управляющих инвертора знака, первый и второй блоки умножения, первые входы которых являются соответственно первым и вторым входами коэффициентов устройства, а суммирующий и вычитающий выходы первого сумматора-вычитателя подключены по входам соответственно первого и второго регистров, входы первого и второго управляемых инверторов, знака соединены соответственно с первым и вторым входами второго сумматора-вычитателя, третий и четвертый входы которого являются соответственно входами вещественной и мнимой частей первого числа устройства, суммирующий и вычитающий выходы первого сумматора-вычитателя соединены со вторыми входами соответственно первого и второго блоков умножения, выходы которых соединены соответственно со входами сумматора, выход которого подключен к первому входу первого сумматора-вычислителя, второй вход которого является входом второго числа устройства, а управляющий вход сумматора является входом задания режима устройства, при этом вход третьего регистра соединен со входом второго регистра, причем тактовые входы регистров являются входами синхронизации устройства [Авт. св. СССР №794637, кл. G 06 F 15/332]. Недостатком известных устройств является малое быстродействие, так как в них отсутствуют средства конвейерной организации выполнения арифметических и логических операций. Наиболее близким к изобретению является устройство для вычисления коэффициентов Фурье, содержащее четыре блока умножения и шесть суммирующих блоков, два входных регистра действительной и мнимой частей операндов, регистры действительной и мнимой частей весового коэффициента, блоки сдвигов, блок управления сдвигами и промежуточные регистры, причем выходы регистров первого операнда и весового коэффициента подключены ко входам блоков умножения, выходы первого и второго блоков умножения через промежуточные регистры соединены со входами первого суммирующего блока, выходы третьего и четвертого блоков умножения через промежуточные регистры соединены со входами второго суммирующего блока, выходы первого и второго и регистров второго операнда соединены со входами с третьего по шестой суммирующих блоков; выходы которых соединены со входами промежуточных регистров и со входами блока управления, сдвигами, выход которого подключен к первым входам блоков сдвига, вторые входы которых соединены с шинами операндов, а выходы соединены со входами регистров операндов [Авт.св. СССР №736112, кл. G 06 F 15/332, 1980 (прототип)]. Недостатком данного устройства является малая точность вычисления коэффициентов Фурье при использовании его в процессорах, реализующих алгоритм быстрого преобразования Фурье и обрабатывающих массивы двоичных чисел с фиксированной запятой из-за быстрого накопления систематических ошибок округления промежуточных результатов и неполного использования разрядности функциональных узлов устройства. Технической задачей предлагаемого изобретения является повышение точности вычисления коэффициентов Фурье при реализации алгоритма быстрого преобразования Фурье. Для решения этой задачи в устройство для вычисления коэффициентов Фурье, содержащее четыре блока умножения, шесть суммирующих блоков, два входных регистра, четыре блока сдвига, два промежуточных регистра и блок управления сдвигами, первый выход которого подключен ко вторым входам с первого по четвертый блоков сдвига, выход первого входного регистра соединен с первыми информационными входами третьего и пятого суммирующих блоков, выход второго входного регистра соединен с первыми информационными входами четвертого и шестого суммирующих блоков, дополнительно введены четыре блока округления, выходы которых подключены к выходным шинам первого и второго операндов устройства и ко входам блока управления сдвигами, второй выход которого является выходом значения коэффициента масштабирования операндов устройства, информационные входы первого и второго регистров входных подключены к входным шинам соответственно действительной и мнимой частей второго операнда, первые информационные входы первого и четвертого блоков умножения подключены к входной шине действительной части первого операнда, первые информационные входы второго и третьего блоков умножения подключены к входной шине мнимой части первого операнда, вторые информационные входы первого и третьего блоков умножения подключены к входной шине действительной части весового коэффициента, вторые информационные входы второго и четвертого блоков умножения подключены к входной шине мнимой части весового коэффициента, выходы первого и второго блоков умножения соединены со входами первого суммирующего блока, выход которого соединен со входом первого промежуточного регистра, выход которого соединен со вторым информационным входами третьего и пятого суммирующего блоков, выходы третьего и четвертого блоков умножения соединены со входами второго суммирующего блока, выход которого соединен со входом второго промежуточного регистра, выход которого соединен со вторыми информационными входами четвертого и шестого суммирующих блоков, выходы третьего, четвертого, пятого и шестого суммирующих блоков соединены с первыми входами соответственно первого, второго, третьего и четвертого блоков сдвига, выходы которых соединены со входами соответственно первого, второго, третьего и четвертого блоков округления, управляющие входы третьего, четвертого, пятого и шестого суммирующих блоков, входных регистров и блоков умножения подключены к шине тактовых импульсов. Сопоставительный анализ с прототипом показывает, что заявляемое устройство для вычисления коэффициентов Фурье отличается тем, что преобразованные операнды по базовой операции быстрого преобразования Фурье масштабируются и округляются таким образом, что разрядность чисел используется более рационально, а систематические ошибки исключаются. Таким образом, заявляемое устройство соответствует критерию изобретения "новизна", сравнение заявляемого решения не только с прототипом, но и с другими техническими решениями в данной области техники, не позволило выявить в них признаки, отличающие заявляемое решение от прототипа, что позволяет сделать вывод о соответствии критерию "существенные отличия". На фиг.1 представлена функциональная схема устройства для вычисления коэффициентов Фурье; на фиг.2 приведены графики экспериментальной оценки точности реализации алгоритма быстрого преобразования Фурье в формате чисел с фиксированной запятой. Устройство (фиг.1) содержит: 1,2,3,4 - первый, второй, третий и четвертый блоки умножения; 5,6 - первый и второй входные регистры; 9,10 - первый и второй промежуточные регистры; 7,8,11,12,13,14 - первый, второй, третий, четвертый, пятый и шестой суммирующие блоки; 15,16,17,18 - первый, второй, третий и четвертый блоки сдвига; 19,20,21,22 - первый, второй, третий и четвертый блоки округления; 23 - блок управления сдвигами. Входом действительной части первого операнда устройства является первые информационные входы первого и четвертого блоков 1,4 умножения, входом мнимой части первого операнда - первые информационные входы второго и третьего блоков 2,3 умножения, входом действительной части весового коэффициента - вторые информационные входы первого и третьего блоков 1,3 умножения, входом мнимой части весового коэффициента - вторые информационные входы второго и четвертого блоков 2,4 умножения, входами второго операнда - информационные входы первого и второго входных регистров 5,6 входом тактовых импульсов устройства являются управляющие входы блоков 1,2,3,4 умножения, входных регистров 5,6, третьего, четвертого, пятого и шестого суммирующих блоков 11,12,13,14. Выходы первого и второго блоков 1,2 умножения соединены со входами первого суммирующего блока 7, выход которого через первый промежуточный регистр 9 соединен с первыми информационными входами третьего и четвертого суммирующих блоков 11,13, вторые информационные входы которых подключены к выходу первого входного регистра 5. Выходы третьего и четвертого блоков 3,4 умножения соединены со входами второго суммирующего блока 8, выход которого через второй промежуточный регистр 10 соединен с первыми информационными входами пятого и шестого суммирующих блоков 12,14, вторые информационные входы которых подключены к выходу второго входного регистра 6. Выходы с третьего по шестой суммирующих блоков 11,12,13,14 соединены с первыми входами соответственно с первого по четвертый блоки сдвига 15,16,17,18, выходы которых соответственно через первый, второй, третий и четвертый блоки 19,20,21,22 округления подключены к выходным шинам первого и второго операндов устройства, а также к входам блока управления сдвигами 23, второй выход которого подключен к выходной шине коэффициента масштабирования операндов, а первый выход соединен со вторыми входами первого, второго, третьего и четвертого блока 15,16,17,18 сдвига. Предлагаемое устройство для вычисления коэффициентов Фурье реализует в формате двоичных чисел с фиксированной запятой базовую операцию алгоритма быстрого преобразования Фурье по формуле где і - порядковый номер цикла преобразований массива операндов; Аi-1(k); Аi-1(I) - комплексные значения первого и второго входных операндов; Аi(k); Ai(l) - комплексные значения первого и второго выходных операндов; W - комплексное значение весового коэффициента. Введем обозначения для комплексных чисел: В этом случае соотношения (1) преобразуются к виду Значения действительной и мнимой частей входных и выходных операндов и весового коэффициента (2) представляются двоичными числами с фиксированной запятой. Будем считать, что эти числа представлены в дополнительном коде и выравнены слева, т.е. изменяются в пределах (-1,0 -+1,0). В устройстве-прототипе применяется масштабирование входных операндов сдвигом вправо (в сторону младших разрядов) на 0,1,2 разряда, что равносильно делению действительной и мнимой частей первого и второго входных операндов Аi-1(К); Аi-1(I) на 0,2,4 соответственно, при этом сдвинутые разряды теряются (округление методом усечения). Как показано в книге: А.Рабинер, Б.Гоулд. Теория и практика цифровой обработки сигналов. Мир, 1978 г., стр. 650, максимальные значения модулей операндов при реализации базовой операции (1) алгоритма БПФ увеличивается примерно в 2 раза, Однако из соотношений (3) видно, что сами действительные и мнимые части выходных операндов ai(к); аi(I); bi(k); bi(I) могут увеличиваться по абсолютному значению более, чем в два раза по сравнению с максимальными значениями действительной и мнимой частей входных операндов аi-1(к); аi-1 (I); bi-1 (к); bi-1(I). Для этого в устройстве-прототипе предусмотрено увеличение разрядности выходных данных на единицу, что позволяет учитывать крайне редкие случаи, когда выходные числа ai(k); ai(l); bi(k); bi(l) по абсолютной величине становятся больше 1,0. Масштабирование в устройстве по авт.св. №736112 производится сдвигом вправо на 2,1,0 разряда соответственно при Mi-1 ³ 1,0; 0,5 £ Mi-1 < 1,0 и Mi-1 < 0,5, где Mi-1 =мах{lаi-1(к)l;lb i-1(к)l} к = 0,1.....(N-1) для всех входных операндов А i-1(К). Максимальное увеличение абсолютного значения в базовой операции (3) возможно только в 2,4 раза, поэтому необходимо выполнять масштабирование сдвигом входных операндов на 2,1,0 разряда соответственно при значениях 0,84 £ Мi-1< 1,0; 0,42 £ Мi-1< 0,84; Мi-1 < 0,42. В устройстве-прототипе производится округление входных операндов после сдвига, двоичных чисел, а также произведений (3) ai-1 (k) U; аi-1(к) V; bi-1(к) U; bi-1(к) V перед записью их в промежуточные регистры. В предлагаемом устройстве для вычисления коэффициентов Фурье входные операнды, которые представляют двоичные числа аi-1(к); аi-1(І); bi-1(к); bi-1(I) фиксированной запятой, не масштабируются, а сразу поступают для реализации базовой операции (3). Преобразованные в результате базовой операции (3) действительные и мнимые части выходных операндов аi(к); аi(І); bi(к); bi(I) масштабируются путем сдвига в блоках сдвига 15,16,17,18: после чего они округляются в блоках 19,20,21,22 таким образом, что исключаются условия возникновения систематических ошибок, которые накапливаются быстрее, чем чисто случайные ошибки. Систематические ошибки при округлении возникают потому, что при усечении двоичных чисел в дополнительном коде после сдвига одинаковые по абсолютному значению положительные неотрицательные числа становятся различными после округления. Эта разница составляет всего цену младшего разряда, однако эта систематическая ошибка при многократном преобразовании операндов по базовой операции (1) по алгоритму БПФ быстро накапливается, что является основной причиной низкой точности вычисления преобразования Фурье. Известно, что спектр действительных сигналов и корреляционных функций содержат действительную и мнимую части, которые являются соответственно четной и нечетной функцией. При округлении методом усечения, когда одинаковые по абсолютному значению числа разных знаков принимают различные значения после мастабирования, приводят к нарушению соответственно четности и нечетности действительной и мнимой частей спектров. В вышеупомянутой книге: Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов предлагается округление производить по методу: D - цена младшего разряда; при ошибке; d 0,5 D -добавляется "1" в младший разряд округляемого числа; при ошибке d = 0,5D добавляется "1" случайным образом, а фактически через раз (авт.св. СССР №771667,1043636). Однако этот метод округления также нельзя применять в базовой операции (3), так как он также приводит к систематическим ошибкам. Для исключения систематических ошибок в предлагаемом устройстве для вычисления коэффициентов Фурье округление операндов после сдвига производится по М-методу, суть которого заключается в следующем: при ошибке delta > 0,5 D - в младший разряд округляемого числа добавляется "1"; при ошибке d= 0,5 D в младший разряд округляемого числа "1" добавляется, если младший разряд округляемого числа находится в состоянии "0", т.е. при ошибке d= 0,5D младший разряд всегда устанавливается в состояние " 1". Этот метод реализует устройство для округления по авт.св. СССР №995088. Известно, что при вычислении преобразования Фурье по алгоритму БПФ в формате целых чисел для массивов длиной N = 1024-4096 отсчетов из-за ошибок округления операндов в базовой операции (3) теряется 6-8 разрядов [Рабинер Р., Гоулд Б. Теория и применение цифровой обработки сигналов; Бовбель Е.И. и др. Ошибки цифровых систем, основанных на вычислении дискретного преобразования Фурье; Журнал: Зарубежная радиоэлектроника, 1981, №5,с. 3-24; книга: Цифровые фильтры и устройства обработки сигналов на интегральных микросхемах. Под ред. Б.Высоцкого, 1984]. Использование предлагаемого метода округления позволяет вычислять преобразование Фурье в формате целых чисел по алгоритму БПФ для массивов операндов длиной N = 1024¸4096 отсчетов, при этом теряется всего 1¸2, крайне редко до 3-х разрядов. Оценка точности вычисления преобразования Фурье по алгоритму БПФ в формате целых числе 16-разрядных произведена на ЭВМ СМ-1420 последующей методике. Реальные и модельные сигналы вводились в ЭВМ с помощью АЦП. Вычисление преобразования Фурье производилось в формате целых чисел и чисел с плавающей запятой. За эталон точности принимались выходные результаты, полученные при обработке массивов в формате плавающей запятой, при этом получается относительная ошибка d< 10-6, т.е. на два порядка меньше, чем цена минимальная целого 16разрядного числа. После вычисления преобразования Фурье в формате целых чисел все составляющие спектра сравнивались с аналогичными составляющими результата, полученного после реализации алгоритма БПФ в формате плавающей запятой. Ошибка вычислялась по соотношениям: где ak’; bk’ - выходные действительная и мнимая части преобразования Фурье; вычисленные в формате плавающей запятой; ak’’, bk’’ - результаты при вычислениях в формате целых чисел; d ош , dсигн - среднеквадратичные значения соответственно ошибок и массивов выходных данных. Для различных условий выполнялось 25-30 экспериментов, статистические данные обрабатывались методами интервальных оценок с надежностью 95%. Вычислялись и предельные относительные ошибки по соотношениям где dэф; d пр - относительные эффективная и предельная ошибки. Выполнялось три способа обработки точности целочисленной реализации алгоритма БПФ для массивов длиной N = 256¸4096 отсчетов приведены на фиг.2. Способы округления операндов: 1. Операнды масштабировались на входе базовой операции, как это предусмотрено в устройствепрототипе. Округление производилось методом усечения. Область оценки эффективной относительной ошибки d эф на фиг.2 показана кривыми №1. Эта ошибка достигает d эф = 0,45% при N = 4096 отсчетов. Предельная ошибка d пр»4 dэф (Правило 3-х сигма, известное из теории вероятности). 2. Операнды машстабировались в конце операции (3), как это предусмотрено в предлагаемом устройстве. Округление операндов производилось также методом усечения. Точность вычисления преобразования Фурье в формате целых числе (кривые №2) повысилась примерно в 2 раза, так как разрядность обрабатываемых операндов увеличилась на единицу. 3. Масштабирование операндов также производилось в конце базовой операции (3) с округлением промежуточных результатов после сдвига по М-методу, как предусмотрено в предлагаемом устройстве для вычисления коэффициентов Фурье. Точность вычисления преобразования Фурье в формате целых 16разрядных чисел показана кривыми №3 (фиг.3). Из графиков видно, что реализацию алгоритма БПФ в формате фиксированной запятой можно осуществлять с точностью при разрядности чисел n = 16, при которой d эф < 0.05%, а d пр - 4 d эф 0,4%. При вычислении преобразования Фурье разрядность операндов составляет n = 20. Предлагаемое устройство для вычисления преобразования Фурье позволит вычислять спектры и корреляционные функции в формате 16-разрядных целых чисел с относительной ошибкой d эф < 0,05%, что на порядок меньше ошибок оцифрования сигналов на входе. Снижение разрядности операндов приведет к сокращению аппаратурных затрат в спектроанализаторе на 20-25%. Предлагаемое устройство для вычисления коэффициентов Фурье работает следующим образом. Подлежащие обработке на 1-м цикле преобразования массива операндов по соотношениям (1) и в развернутой форме (3) n-разрядные числа с фиксированной запятой аi-1(к); bi-1(к) поступают в блоки умножения 1,2,3,4, куда также поступают числа U,V весового коэффициента W = U + j ×V. Числа ai-1 (I); bi-1(l) поступают во входные регистры 5.6. Произведения аi-1(к)×U; bi-1(k)×V; bi-1(k)×U; ai-1(k)×V с выходов блоков умножения 1,2,3,4 поступают на информационные входы первого и второго суммирующих блоков 7,8, с выходов которых суммы соответственно поступают через промежуточные регистры 9,10 на вторые информационные входы третьего, четвертого, пятого и шестого суммирующих блоков 11,12,13,14, на первые входы которых поступает второй операнд Аi-1(І). На выходах третьего, четвертого, пятого и шестого суммирующих блоков вырабатываются выходные значения операндов по формуле (3) соответственно aiк); bi(к); ai(I); bi(I). Действительные и мнимые части операндов Аi(к) = аi(к) + j×bi(k); Ai(l) – ai(l) + j×bi(I) поступают через первые входы соответственно первого, второго, третьего и четвертого блоков 15,16,17,18 сдвига. Сдвинутые на r = 0,1,2 разрядов числа ai(k); bi(k); ai(l); b i(l) округляются в блоках 19,20,21,22, с выходов которых первый и второй операнды Ai(k); Ai(l) поступают на выходные шины устройства. Блок управления сдвигами 23 функционируют аналогично блоку 25 устройства-прототипа и на своем первом выходе вырабатывает коды (00,01,10), соответствующие сдвигу в блоках 15,16,17,18 соответственно 0,1 или 2 разряда вправо. Выходные числа ai(k); bi(k); ai(l); bi(l) поступают в блок управления сдвигами 23, по этим числам для всего массива операндов в і-м цикле их преобразования вырабатывается максимальное абсолютное значение Mi = max{lai(k)l; lbi(k)l}, при к = 0,1,2,...(N-1), N - длина массива в отсчетах. Аналогичная величина Mi-1 была выработана на предыдущем (i-1) цикле преобразования операндов по базовой операции БПФ (1). На основе анализа числа Mi-1 было выработано: код "10" при 0,84 £ Mi-1 < 1,0 (сдвиг на 2 разряда); "01" при 0,42 £ Mi-1 < 0,84 (сдвиг на 1 разряд); "00" при Mi-1 < 0,42 (сдвиг на 0 разрядов, т.е. отсутствует). Вырабатываемое число Mi послужит для выработки признака, на сколько разрядов сдвигать числа в следующем (i+1) цикле преобразования операндов. Управление ходом преобразования операндов по базовой операции БПФ (1) производится тактовыми импульсами, поступающими в устройство через управляющие входы блоков умножения 1,2,3,4, входных регистров 5,6, а также с третьего по шестой суммирующие блоки 11,12,13,14. Устройство для вычисления коэффициентов Фурье одновременно обрабатывает две пары операндов. Поступающая пара операндов Ai-1(k); Ai-1(l) и весовой коэффициент W 1 проходят этап умножения, а ранее поступившая пара операндов Аi-1(r); Ai-1(q) c весовым коэффициентом W 2 проходят этап суммирования, масштабирования и округления. По каждому тактовому импульсу операнды Аi-1(к); Аi-1(I) и весовой коэффициент поступают в блоки умножения и входные регистры. На первом этапе вырабатываются соответственно которые поступают в промежуточные регистры 9,10, а числа аi-1(І); bi-1(І) остаются во входных регистрах, откуда по тактовому импульсу числа ai-1(q); bi-1(q) поступают соответственно вместе с ранее вычисленными произведениями [аi-1(r)×U2 – bi-1(r)×V2]; [bi-1 )×U2 + аi-1(r)×V2] на входы третьего, четвертого, пятого и шестого суммирующих блоков. Входные регистры 5,6 с поступлением тактового импульса сначала выдают в блоки 15,16,17,18 числа ai1(q); b i-1(q), а затем записывают второй входной операнд Ai-1(I) = ai-1(l)+ j×b i-1(І). Быстродействие устройства, как и в устройстве-прототипе, определяется быстродействием блоков умножения. Положительный эффект от использования предлагаемого устройства для вычисления коэффициентов Фурье заключается в том, что при обработке операндов в формате фиксированной запятой повышается точность вычисления по базовой операции БПФ без изменения разрядности входных и выходных чисел за счет увеличения их разрядности на единицу. Это стало возможным благодаря переносу масштабирования операндов в конец базовой операции. Кроме того, введение блоков округления исключает возникновение систематических ошибок, которые в ходе реализации алгоритма БПФ накапливаются значительно быстрее, чем чисто случайные ошибки. Использование предлагаемого устройства для вычисления коэффициентов Фурье позволит в процессорах БПФ и спектроанализаторах при разрядности операндов и весовых коэффициентов n = 16 обрабатывать массивы длиной до N = 16384 отсчета с точностью, при которой накопленные ошибки округления ниже ошибок на входе при оцифровании сигналов с помощью 12-разрядных АЦП. Таким образом, введение четырех блоков округления и перенос блоков сдвига от входных шин к выходным шинам операндов устройства повышают точность преобразования операндов по базовой операции быстрого преобразования Фурье в два раза и исключает систематические ошибки при округлении двоичных чисел с фиксированной запятой.