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

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах для цифровой обработки сигналов. Цель изобретения - расширение области применения за счет обработки последовательностей длиной больше Р (Р - размер преобразования). Поставленная цель достигается за счет того, что в состав устройства входит Р блоков вычисления коэффициентов, каждый из которых содержит регистр 5., сумматор 6, регистр 7, умножитель 8 на , узел инверсии кода 9, ре- .гистр 10 и сумматор 11. 4 ил.

союз советсних сОцИАлистичесних

РЕСПУВЛИН

{,51)5 G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ по изои етениям и ощгнтиям пРи Гннт сссР (21) 4660800/24 (22) 10.03.89 (46) 28.02.91. Бюл. № - 8 (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) Л.В.Вариченко (53) 681.32(088.8) (56) Авторское свидетельство СССР

¹ 1218396, кл. С 06 F. 15/332, 1984.

Авторское свидетельство СССР № 1295415, кл. G 06 F 15/332, 1-985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ФУРЬЕ-ГАЛУА

„.SU„„1631554 А 1

2 (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах для цифровой обработки сигналов. Цель изобретения — расширение области приме-, нения за счет обработки последовательностей длиной больше Р (Р— размер преобразования). Поставленная цель достигается за счет того, что в состав устройства входит P блоков вычисления коэффициентов, кажцый из которых содержит регистр 5, сумматор 6, регистр 7, умножитель 8 на 2, узел инверсии кода 9, ре,гистр 10 и сумматор 11. 4 ил. 1631554 (1) 40 (4,5) -011 = 100 = 4, Изобретение относится к вычислительной технике и может быть использовано в устройствах для цифровой обработки сигналов.

Цель изобретения — расширение области применения за счет обработки последовательностей длиной, большей

P (P — размер преобразования).

На фиг. 1 приведена функциональная схема устройства для вычисления преобразования Фурье-Галуа, на фиг.2функциональная схема блока вычисления коэффициента, на фиг. 3 — функциональная схема узла инверсии кода на фиг.4 — временные диаграммы работы устройства.

Функциональная схема устройства содержит P блоков 1 вычисления коэф-, фициентов (Фурье-Галуа), информацион-. 20 ный вход 2, информационные выходы 3 и (многоразрядный) управляюший вход 4.

Блок 1 вычисления i-го коэффициента (фиг.2) содержит входной Р-разрядный) регистр 5, двухвходовьп

Р-разрядный сумматор 6, (Р-разрядный) регистр 7 хранения промежу-„ ( точных данных, умножнтель 8 на 2 узел 9 инверсии кода, P-разрядный: регистр 10, P-разрядный двухвходо30 вый сумматор 11.

Узел 9 инверсии кода содержит первую 12 группу из Р элементов И, вторую 13 группу иэ Р элементов И с,, инверсными выходами, группу 14 из P элементов ИЛИ, вход 15, выход 16 и 35 управляющие входы 17 и 18.

Преобра ование Фурье-Галуа задается выражением:

М-(Я (06) = x(n) х, (n)

И=О (Ь

-1 где x (n) — матрица преобразования

Фурье-Галуа, х (п) =К ", Я = (1 — корень М-й

Жи степени из единицы при 45 надлежащей полю Галуа, Я (=GF(M), N = 2Р-1.

Если в таком поле принять Я = 2, то максимальный размер матрицы x (n) равен Р, т.е. N = Р При этом умноже- ния на коэффициенты сводятся к умножениям на 2 . Недостаток таких преобразований — небольшой размер матрицы х (п), а значит и длина цифрово. го сигнала, равный Р Р. Арифметиче55 ские операции в выражении (1) выполняются по модулю N.

Увеличить размер матрицы х (п) до .2P> 2Р можно выбрав Я = -2. Однако в

I этом случае умножения на -2 сложнее и не являются циклическими сдвигами, как умнсяения на 2 . В (1) умножение на -2 реализуются по модулю М = 2 + 1 с последующйм приведе1 нием результата по модулю М = 2 и вычислением специальных коэффициентов, на основе которых получают спектральные коэффициенты Б(Ж). Это упрощает умножение на -2", но полностью проблему не решает.

Пусть а, Ь Е GF(N), причем а и Ь представляются в двоичной системе исчисления. Пусть а и Ь получаются из а и Ъ инверсией разрядов. Тогда -а=а и, следовательно

-a b=a-Ь = а Ь = а.Ь (2)

У т.е. умножение на отрицательное, число сводится к инверсии одного из сомножителей и вычислению произведения, или вычислению произведения и,инверсии результата.

В поле Галуа СР(М) справедливо следующее равенство:

-а = М-а (3)

P а так как М = 2 -1, то двоичное его представление соответствует P-разрядному числу, значение каждого разряда которого равно единице. Следовательно

1 выражение (3) задает операцию инвертирования разрядов -а. Например пусть

Э

М = 7 = 2 -1. С элементами поля GF ..(7) можно сопоставить целые числа от 0 до 6, т.е. принять в качестве эле,ментов этого поля множество Е = 0

7 1 9 .1,2,...,б . В этом случае отрицательные числа оказываются закодированными целыми числами, большими М/2.

Можно записать соответствие:

0-0, 1-1, 2- 2, 3 3, 4- --3, В двоичной системе исчисления эти числа можно представить трехразрядными двоичными числами

-001 = 110 = 6;, -010 = 101 = 5; где четко просматривается свойство (2). Это свойство можно использовать при вычислениях по (1) при

Я,= -2

54 6 (4) (5) 50

5 16216

ИатЬииу x16(n )тР = f"", 6(, и =0,2Р-! можно получить исходя из матрицы х ((п) =Я, g,, n = О, Р-1 пу()(n тем перестановки отсчетов g и и в ,соответствии с выражнниями: п(Р+1)mod2P, n (P, п(Р+1) +PJmod2P, и-» P !

М (P+1) mod2P, g a P ) С((Рт1) тР) юс62Р, C(Ъ P.

Тогда матрицу хо (п) можно запи.сать в виде блочной матрицы:

15 х (n) g()P x@(n)1) р Я

x g(n)p -x pC(n) L)

Процес вычисления разбивается на следующие этапы:

1) вычисляется Р-точечное преобразование Фурье-Галуа согласно (1) для четных отсчетов сигнала x(n). Результат (коэффициенты S (0),,S (2),..., SР(2Р-2) запоминаются в блоках 1

2) вычисляется P-точечное преобразование Фурье-Галуа согласно (1) для нечетных отсчетов сигнала x(n). Результаты (коэффициенты S (1), S(3), / I

S (2P-1) запоминаются в блоках 1.

Коэффициенты в блоках 1 переставлены в соответствии с выражением (5);

3) вычисляются суммы S (0) +

+ S (1) = $(0), S (2)-- + S (3) = S(2), S (2Р-2) + S (2Р-1) = S(2P-2) 35

В результате получаем Р/2 четных коэффициентов преобразования ФурьеГалуа длины N = 2Р;

4) спектральные коэффициенты S (1), S (3),..., S (2Р-1) подвергаются дво! « 40 ично-разрядной инверсии, 5) вычисляется сумма, в результате чего получаются остальные Р/2 коээффициентов . S (0) + S (1) = S(1), S (2) + S" (3) = S (3),..., S (2P-2) +

+ S (2Р-1) = S(2P-1) .

Устройство для вычисления преобразования Фурье-Галуа работает следующим образом.

: Отсчеты цифрового сигнала x(n) (n = О, N-1), N = 2Р, х(п) 6 Е((, Е а = (0,1,..., k-1 ) ) поступают на вход 2 устройства и в соответствии с (4) последовательно записываются в регистр 5 (фиг.4) .

Перед началом работы все регистры обнуляются подачей сигнала на входы 4 i 4, 4 . Входные данные сопровождаются стробом С ., С выхода регистра 5 отсчет сигнала поступает на один из входов сумматора 6.

Этот сумматор реализует сумму по модулю N. Для этого его выход переноса соединен с собственным входом переноса. Выход сумматора 6 соединен с входом регистра 7 ° В каждом последующем такте в регистр 7 записывается значение суммы сумматора 6 на предыдущем такте. Это осуществляется соответствующей подачей управляющих сигналов на входы 4 (фиг.4). Выход регистра 7 соединен с входом умножителя 8 на 2 . Умножение на 2" в поле GP(M) соответствует циклический сдвиг, поэтому блок 6 представляет собой простое соединение проводов. Вычислитель

i-го коэффициента 1 содержит умножитель 8 на 2 . В результате регистр 5, сумматор 6, регистр 7 и умножитель 8 образуют схему, реализующую функцию умножения на 2 и накапливающей суммы. Таким образом вычисляются коэффициенты S (i) преобразования длины P. Алгоритм вычислений следующий.

Коэффициент S (О) вычисляется путем суммирования х(О) + х(2)+. ° .+

+ х(2Р-2), т.е. умножитель 8 осуО ществляет умножение отсчетов на 2 =1.

Для удобства дальнейшего изложения выполняют перенумерацию х(0)-ьх(0), х(2)-2 х(1), x(4) x(2),..., х(2Р-2)- x(P-1), т.е. рассматриваем преобразование Фурье †Гал размерности

Р (четверть матрицы х <(п) zp) . Коэффициент S (з.), i = О, 1,...,P-1 вычисляется согласно выражению:

Я (1) = (... ((х(0) ° 2 + х(1)) 2 +

1 1

+ х(2)) 2 + ...+ х(Р-1))» 2 . (6) Результат вычисления преобразования Фурье-Галуа для четных значений x(n) (спектральные коэффициенты S (О), S (2),. "., S)(2Р-2)) запоминается в регистрах 10 блоков 1 вычисления коэффициентов. Для этого на вход 44, подается управляющий сигнал (фиг.4). На узел 9 подаются сигналы управления, обеспечивающие прямую передачу кодовых слов без инвертирования (на вход 17 подается значение сигнала, соответствующее "1", 1631554 на вход 18 — значение„соответствующее, "0 1).Далее, точно так же вычисляются

11 II спектральные коэффициенты Б (1), S (3),..., S (2P-1).

Значения этих коэффициентов после последнего такта вычислений при,сутствуют на выходе сумматора 6 (запись в регистр 7 не производится, :;т.е. сигнал на вход 4 в этом случае не подается). С выхода сумматора 6 через узел 9 без инвертирования зна:чение спектрального коэффициента

S (i), i — нечетное, подается на вход сумматора 11, на другой вход которого с выхода регистра 10 подается значение коэффициента S (1), 1 — четное

I ° ° (i = j после перенумерации). Сумматор 11 реализует сумму по модулю М.

С этой целью выход переноса этого сумматора соединен с .собственным входом переноса. После суммирования получают первые Р коэффициентов S(0), Б(2),...,$(2Р-2) преобразования с матрицей размерности 2Р Ж 2Р. Значе- 25 ния этих коэффициентов считываются с выходов 3 блоков 1. После считывания коэфициентов Б(0), Б(2),. °

S(2P-2) в общую вычислительную систему на вход сумматора 11 каждого, 30 блока 1 подаются инвертированные

1 с помощью узлов 9 значения коэффицициентов S (1), S (3),...,S (2Р-1).

После вычисления суммы получают вторые Р коэффициентов Б(1), -Б(3),..., 35

S(2Р-1). Коэффициенты на выходах 3 переставляют в соответствии с (5).

При подаче на вход 17 управляющего

11 И сигнала, соответствующего 1, а на вход 18 — соответствующего 0, входИ 11 - 40 ные данные без изменений передаются на выход 16. Если же на вход 17 подать управляющий сигнал соответствую-, щий уровню "0", а на вход 18 — сиг11 45 нал соответствующий уровню 1, то, слова входных данных подвергаются поразрядному инвертированию и подаются на выход 16.

Формула изобретения.50

Устройство для вычисления преобразования Фурье-Галуа, содержащее

Р (P — размер преобразования) блоков вычисления коэфйит иентов, причем выход i ro (i = 1, P) блока вычисления коэффициента является выходом х-го коэффициента устройства, инфор-. мационным входом которого являются соединенные между собой информационные входы всех блоков вычисления коэффициента, управляющие входы группы которых соответственно соединены между собой и являются входами кода операции группы устройства, при этом

i-й блок вычисления коэффициента содержит три регистра, первый сумматор и умножитель на 2, выход первого регистра подключен к первому информационному входу первого аумматора, выход переноса которого подключен к входу переноса первого сумматора, информационный вход первого регистра является информационным входом блока вычисления коэффициента, управляющие входы группы которого образуют тактовые и установочные входы первого, второго и третьего регистров, отличающееся тем, что, с целью расширения области применения за счет обработки последовательностей длиной большей P в i-й блок вычисления коэффициента введены второй сумматор и узел инверсии кода, выход которого подключен к первому информационному входу второго сумматора информационному входу второго регистра, выход которого подключен к второму информационному входу второго сумматора, выход переноса которого подключен к входу переноса второго сумматора, информационный выход которого является выходом блока вычисления коэффициента, выход третьего регистра подключен к входу умножителя на 2, выход которого подключен к второму информационному входу первого сумматора, информационный выход которого подключен к информационному входу третьего регистра и информационному входу узла инверсии кода, управляющий вход которого подключен к соответствующему управляющему входу группы блока вычисления коэффициента.

1631554

Составитель А.Баранов

Техред Л.Сердюкова Корректор Т.Патай

Редактор Л.Пчолинская

Заказ 547 Тираж 401 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР.

113035, Иосква, R-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101