Устройство для вычисления преобразования фурье-галуа

союз советснихсОцИАлистичеснихРЕСПУБЛИН 1) 5 С 06 Р 15/33 ЕН ТЕЛЬСТ 3,2 ГОСУДАРСТВЕННЫЙ КОМИТЕТпо изоБРетениям и омытиямпРи Гннт сссР ОПИСАНИЕ ИЗО К АВТОРСКОМУ С(46) 28.02.91. Бюл. Р 8 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры(56) Авторское свидетельство СССР В 1218396, кл, С 06 Е 15/332, 1984Авторское свидетельство СССР У 1295415, кл. С 06 Р 15/332, 1-985 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПРЕ ОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА(57) Изобретение относится к вычислительной технике и может быть ис" пользовано в устройствах для цифровой обработки сигналов. Цель изобретения - расширение области приме-, нения за счет обработки последовательностей длиной больше Р (Р - размер преобразования). Поставленная цель достигается за счет того, что в состав устройства входит Р блоков вычисления коэффициентов, кажцый из которых содержит регистр 5, сумматор 6, регистр 7, умножитель 8 на 2, узел инверсии кода 9, регистр 10 и сумматор 11. 4 ил.-011 = 100 = 4,Изобретение относится к вычислительной технике и может быть использовано в устройствах для цифровойобработки сигналов.Цель изобретения - расширение области применения за счет обработкипоследовательностей длиной, большейР (Р - размер преобразования),На Фиг. 1 приведена Функциональная схема устройства для вычисленияпреобразования Фурье-Галуа, на фиг.2 функциональная схема блока вычисления коэффициента на фиг. 3 - Функциональная схема узла инверсии кодана фиг.4 - временные диаграммы работы устройства.Функциональная схема устройствасодержит Р блоков 1 вычисления коэф-,Фициентов (Фурье-Галуа), информацион-. 20ный вход 2, информационные выходы 3и (многоразрядный) чправляюший вход 4.Блок 1 вычисления 1-го коэффициента (Фиг.2) содержит входной Р-разрядный) регистр 5, двухвходовыйР-разрядный сумматор 6, (Р-разрядный) регистр 7 хранения промежут,(точных данных, умножнтель 8 на 2узел 9 инверсии кода,Р-разрядный:регистр 10, Р-разрядный двухвходо 30вый сумматор 11,Узел 9 инверсии кода содержитпервую 12 группу из Р элементов И,вторую 13 группу иэ Р элементов И синверсными выходами, группу 14 из Рэлементов ИЛИ, вход 15, выход 16 и 35управляющие входы 17 и 18,Преобразование Фурье-Галуа задается выражением:М-Я(06) =.х(п) х, (п)Ь:О(Ьгде х (п) - матрица преобразованияфурье-Галуа,хО(п) =Е ", С; = 7 - корень М-йЖистепени из единицы при 45надлежащей полю Галуа,Я СР(М), М = 2 Р.Если в таком поле принять Я = 2,то максимальный размер матрицы х(п)равен Р, т,е. Н = Р,. При этом умноже-ния на коэффициенты сводятся к умножениям на 2 . Недостаток таких преобразований - небольшой размер матрицы х (п), а значит и длина цифрово. го сигнала, равный РаР. Арифметиче 55ские операции в выражении (1) выполняются по модулю М.Увеличить размер матрицы х(п) до,2 Р2 Р можно выбрав Й = -2. Однако вэтом случае умножения на -2 сложнее и не являются циклическими сдвигами, как умнсяения на 2 . В (1) умножение на -2реализуются по модулю М = 2 + 1 с последующйм приведе) нием результата по модулю М = 2 и вычислением специальных коэффициентов, на основе которых получают спектральные коэффициенты Б(Ж). Это упрощает умножение на -2" , но полностью проблему не решает,Пусть а, Ь Е СР(М), причем а и Ь представляются в двоичной системе исчисления. Пусть а и Ь получаются из а и Ъ инверсией разрядов. Тогда -а=а и, следовательно-а Ь=а Ь = авЬ = а.Ь(2) т.е. умножение на отрицательное, число сводится к инверсии одного из сомножителей и вычислению произведения, или вычислению произведения и,инверсии результата,В поле Галуа СР(М) справедливо следующее равенство:-а = М-а (3)Ра так как М = 2 -1, то двоичное его представление соответствует Р-разрядному числу, значение каждого разряда которого равно единице. Следовательно выражение (3) задает операцию инвертирования разрядов -а. Например пустьЭ М = 7 = 2 -1. С элементами поля СР (7) можно сопоставить целые числа от 0 до 6, т.е. принять в качестве эле,ментов этого поля множество Е 7 = ГОЭ ,1,26). В этом случае отрицательные числа оказываются закодированными целыми числами, большими М/2.Можно записать соответствие: 0- О, 1- 1, 2-2, 3 -е 3, 4-з -3,В двоичной системе исчисленияэти числа можно представить трехразрядными двоичными числами -001 = 110 = 6 -010 = 101 = 5; где четко просматривается свойство (2), Это свойство можно использовать при вычислениях по (1) при Е,= -2(5) 50 55 5 16315Иат 1 ииуху(п)тР с ", с(, пд 0,2 Г- можно получить исходя из матрицы хф(п)р = Я у 0 и = О РпуФ)1тем перестановки отсчетови и в ,соответствии с выражнниями: А п(Р+1)шо(12 Р, п(Р, п(Р+1)+Р 1 чос 2 Р, п Р(. (Р+1)шоЮР Ы с Р2)СР+1)+Р) юпй 2 Р, С( Ъ Р,Тогда матрицу хо(п) можно записать в виде блочной матрицы:15Ъ(п) (п)р р Ях (п)р -х (п)Процес вычисления разбивается на следующие этапы:1) вычисляется Р-точечное преобразование Фурье-Галуа согласно (1) для четных отсчетов сигнала х(п). Результат (коэффициенты Я 0), Я(2) БР(2 Р) запоминаются в блоках 12) вычисляется Р-точечное преобразование Фурье-Галуа согласно (1) для нечетных отсчетов сигнала х(п). Результаты (коэффициенты Б (1), Я(3),/Я (2 Р) запоминаются в блоках 1. Коэффициенты в блоках 1 переставлены в соответствии с выражением (5),"3) вычисляются суммы ЯГ(0) + + Б (1) = Б(0), Я (2) + Б (3) = Б(2),у Я (2 Р 2) + Я (2 Р 1) = Я(2 Р 2), 35 В результате получаем Р/2 четных коэффициентов преобразования Фурье- Галуа длины Н = 2 Р;4) спектральные коэффициенты Б (1), Б (3) Я (2 Р) подвергаются дво/ 40 ично-разрядной инверсии,5) вычисляется сумма, в результате чего получаются остальные Р/2 коээффициентов. Б(0) + Я(1) = Я(1), Я (2) + Я (3) = Я(3) Ру Я (2 Р 2) + + БУ(2 Р) = Б(2 Р).Устройство для вычисления преобразования Фурье-Галуа работает следующим образом,Отсчеты цифрового сигнала х(п)(и = О, М), И = 2 Р, х(п) ЕЕ Рк = (01Г .1-11 ) поступаютна вход 2 устройства и в соответствии с (4) последовательно записываются в регистр 5 (фиг.4) .Перед началом работы все регистры обнуляются подачей сигнала на входы 4, 4, 4 й. Входные данныесопровождаются стробом СС выхода регистра 5 отсчет сигнала поступает на один из входов сумматора 6.Этот сумматор реализует сумму помодулю М. Для этого его выход переноса соединен с собственным входом переноса. Выход сумматора 6 соединен с входом регистра 7В каждом последующем такте в регистр 7записывается значение суммы сумматора 6 на предыдущем такте, Это осуществляется соответствующей подачейуправляющих сигналов на входы 4(фиг.4). Выход регистра 7 соединенс входом умножителя 8 на 2 . Умножение на 2" в поле СР(М) соответствует циклический сдвиг, поэтомублок 6 представляет собой простоесоединение проводов. Вычислитель-го коэффициента 1 содержит умножитель 8 на 2, В результате регистр 5, сумматор 6, регистр 7 иумножитель 8 образуют схему, реализующую функцию умножения на 2 инакапливающей суммы. Таким образомвычисляются коэффициенты Бпреобразования длины Р. Алгоритм вычислений следующий. Коэффициент Б(0) вычисляется путем суммирования х(0) + х(2) + х(2 Р), т,е. умножитель 8 осуществляет умножение отсчетов на 2 =1. Для удобства дальнейшего изложения выполняют перенумерацию х(0)-ьх(0), х(2)2 х(1), х(4) ьх(2), у х(2 Р)- -ех(Р), т.е. рассматриваем преобразование фурье-Галуа размерности Р (четверть матрицы х (п) ). Коэффициент Б , 1 = О, 1Рвычисляется согласно выражению:кБ(1) = ( х(0)2 + х(1 2 ++ х(2 2 + + х(Р2 . (6) Результат вычисления преобразования Фурье-Галуа для четных значений х(п) (спектральные коэффициенты Я(0), Я (2),. "., Б)(2 Рзапоминается в регистрах 10 блоков 1 вычисления коэффициентов, Для этого на вход 44, подается управляющий сигнал (фиг.4). На узел 9 подаются сигналы управления, обеспечивающие прямую передачу кодовых слов без инвертирования (на вход 17 подается значение сигнала, соответствующее "1", 1631554на вход 18 - значениесоответствующее,иО 1).Далее, точно так же вычисляются)успектральные коэффициенты Б (1),Б (3) 8(2 Р).Значения этих коэффициентов после последнего такта вычислений при,сутствуют на выходе сумматора 6 (запись в регистр 7 не производится,; т,е, сигнал на вход 4 в этом случаене подается). С выхода сумматора 6через узел 9 без инвертирования зна"чение спектрального коэффициентаБ (1),- нечетное, подается на входсумматора 11, на другой вход которого с выхода регистра 10 подается значение коэффициента Я (1), 1 - четное(1 = 1 после перенумерации). Сумматор 11 реализует сумму по модулю М.С этой целью выход переноса этогосумматора соединен с .собственным вхо"дом переноса. После суммирования получают первые Р коэФФициентов 8(О),Я(2)Я(2 Р) преобразования сматрицей размерности 2 Р Ж 2 Р, Значения этих коэффициентов считываютсяс выходов 3блоков 1. После считывания коэфициентов 8(0), 8(2)8(2 Р) в общую вычислительную систему на вход сумматора 11 каждого . З 0блока 1 подаются инвертированныес помощью узлов 9 значения коэффицициентов Я (1), Б(3)8(2 Р),После вычисления суммы получают вторые Р коэффициентов 8(1), "Я(3) 358(2 Р). Коэффициенты навыходах 3переставляют в соответствии с (5).При подаче на вход 17 управляющегои исигнала, соответствующего 1 , а навход 18 - соответствующего О , входи и 40ные данные без изменений передаютсяна выход 16. Если же на вход 17 подать управляющий сигнал соответствую-,щий уровню иО", а на вход .18 - сиги и45нал соответствующий уровню 1 , то,слова входных данных подвергаютсяпоразрядному инвертированию и подаются на выход 16.Формула и з о б р е т е н и я. 50Устройство для вычисления преобразования Фурье-Галуа, содержащее Р (Р - размер преобразования) блоковвычисления коэфйииентов, причем выход -го ( = 1, Р) блока вычисления коэффициента является выходомх-го коэффициента устройства, информационным входом которого являютсясоединенные между собой информационные входы всех блоков вычисления коэффициента, управляющие входы группы которых соответственно соединенымежду собой и являются входами кодаоперации группы устройства, при этом-й блок вычисления коэффициента содержит три регистра, первый сумматори умножитель на 2, выход первого регистра подключен к первому информационному входу первого аумматора, выход переноса которого подключен квходу переноса первого сумматора, информационный вход первого регистраявляется информационным входом блока вычисления коэффициента, управляющие входы группы которого образуюттактовые и установочные входы первого, второго и третьего регистров,о т л и ч а ю щ е е с я тем, что, сцелью расширения области примененияза счет обработки последовательностей длиной большей Р, в -й блок вычисления коэффициента введены второйсумматор и узел инверсии кода, выходкоторого подключен к первому информационному входу второго сумматораинформационному входу второго регистра, выход которого подключен к второму информационному входу второгосумматора, выход переноса которогоподключен к входу переноса второгосумматора, информационный выход которого является выходом блока вычисления коэффициента, выход третьегорегистра подключен к входу умножителя на 2 , выход которого подключен к второму информационному входупервого сумматора, информационныйвыход которого подключен к информационному входу третьего регистра иинформационному входу узла инверсиикода, управляющий вход которого подключен к соответствующему управляющему входу группы блока вычислениякоэффициента.1631554 ФЪг УСоставитель А.Баранов Техред Л.Сердюкова Корректор Т.Патай Редактор Л,Пчолинск зводствеино-издательский комбинат "Патентф, г. Ужгород, ул. Гагарина, 10 Заказ 547ВНИИПИ Госуда Тираж 401венного комитета по изобретениям 113035, Иосква, Ж, Раушская на дписноеоткрытиям при ГКНТ СССР