Устройство для вычисления преобразования Фурье-Галуа Советский патент 1991 года по МПК G06F15/332 

со ел

ЈП

Ј

10

f5

25

Изобретение относится к вычислительной технике и может быть использовано в устройствах для цифровой обработки сигналов.

Цель изобретения - расширение области применения за счет обработки последовательностей длиной, большей Р (Р - размер преобразования).

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

Функциональная схема устройства содержит Р блоков 1 вычисления коэф- . фициентов (Фурье-Галуа), информацией- 2Q ный вход 2, информационные выходы 3

(многоразрядный) управляющий вход 4 .

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

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

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

S(06) 2-.x(n)-x

где х (п) - матрица преобразования

Фурье-Галуа J x(n) ЈWr, 6 - корень Ы-й

степени из единицы, при- 45 надлежащей полю Галуа gCGF(M), М 2Р-1. Если в таком поле принять Ј 2, то максимальный размер матрицы х(п) равен Р, т.е. N - Р. При этом умноже- ния на коэффициента сводятся к умножениям на 2. Недостаток таких преобразований - небольшой размер матрицы х(п), а значит и длина цифрового сигнала, равный . Арифметические операции в выражении (1) выполняются по модулю М.

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

30

35

kOO

(п),

(1)

40

50

55

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

Пусть a, b € GF(M), причем а и b представляются в двоичной системе исчисления . Пусть а и b получаются из а и b инверсией разрядов. Тогда и, следовательно

a b

(2)

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

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

5

0

5

0

0

5

-а М-г 2Р-1.

(3)

а так как М 2 -1, то двоичное его представление соответствует Р-разряд- ному числу, значение каждого разряда которого равно единице. Следовательно выражение (3) задает операцию инвертирования разрядов -а. Например, пусть М 7 23-1. С элементами поля GF (7) можно сопоставить целые числа от О до 6, т.е. принять в качестве эле- ,ментов этого поля множество Е- JO, .1 ,2,... ,6 у. В этом случае отрицательные числа оказываются закодированными целыми числами, большими М/2. Можно записать соответствие:

0-М, , , , , , (4,5)

В двоичной системе исчисления эти числа можно представить трехразрядными двоичными числами

-001 110 6; , -010 101 5, -011 100 4,

где четко просматривается свойство (2). Это свойство можно использовать при вычислениях по (1) при .

Матрицу )гр Ј, tf, п 0,2F-1 можно получить исходя из XtfCrOp Р

цы XtfUJp fc4, Od, п О, Р-1 тем перестановки отсчетов &Ј и п чсоответствии с выражениями:

матри- пу- в

n(P+1)mod2P, Јn(P+1)+p mod2P, n5:P

((P+1)inod2P, tf P; jV(P+1)+p mod2P, ct Ь Р.

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

хЫ(п)р

V(n)p

х/п)р

Xj/n)p -Хр((п)р

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

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

2)вычисляется Р-точечное преобразование Фурье-Галуа согласно (1)

для нечетных отсчетов сигнала х(п). зультаты (коэффициенты S (1), S(3), ..., s (2P-1) запоминаются в блоках 1 Коэффициенты в блоках 1 переставлены в соответствии с выражением (5) ,

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

+ S (D S(0), S ( S (3) S(2) ..., s (2P-2) + s (2P-1) S(2P-2). В результате получаем Р/2 четных коэффициентов преобразования Фуръе- Галуа длины N 2Р;

4)спектральные коэффициенты s (1 s (3),..., S (2P-1) подвергаются дво ично-разрядной инверсии/

5)вычисляется сумма, в результате чего получаются остальные Р/2 коэ эффициентов; S (0) + S (1) S(1),

s (2) + S (3) S(3),..., S (2P-2) +

+ s (2P-1) S(2P-1).

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

Отсчеты цифрового сигнала х(п)

(п О, N-1), N 2, х(п) €ЕК, Ек ,1,..., k-1) поступают на вход 2 устройства и в соответ- ствии с (4) последовательно записываются в регистр 5 (фиг.4).

Перед началом работы все регистры обнуляются подачей сигнала на

F-1

и- пу- в

4)

(5)

10

и15

20

25

30

35

на

брадляуль.., j

б1)

). Ре), ах 1 ены

(2), ). ко-

s (1), дво- 40

ьтакоэ-),

) +

бе

- $5

т45

50

входы 45, 4f. Входные данные сопровождаются стробом С.. С выхода регистра 5 отсчет сигнала поступает на один из входов сумматора 6. Этот сумматор реализует сумму по модулю М. Для этого его выход переноса соединен с собственным входом переноса. Выход сумматора 6 соединен с входом регистра 7. В каждом последующем такте в регистр 7 записывается значение суммы сумматора 6 на предыдущем такте. Это осуществляется соответствующей подачей управляющих сигналов на входы 4 (фиг.4) о Выход регистра 7 .соединен с входом умножителя 8 на 2 . Умножение на 21 в поле GF(M) соответствует циклический сдвиг, поэтому блок 6 представляет собой простое соединение проводов. Вычислитель 1-го коэффициента 1 содержит умножитель 8 на 2. В результате регистр 5, сумматор 6, регистр 7 и умножитель 8 образуют схему, реализующую функцию умножения на 2 и накапливающей суммы. Таким образом вычисляются коэффициенты s (i) преобразования длины Р. Алгоритм вычислений следующий.

Коэффициент S (0) вычисляется путем суммирования х(0) + х(2)+...+ + х(2Р-2), т.е. умножитель 8 осуществляет умножение отсчетов на 2 1 Для удобства дальнейшего изложения выполняют перенумерацию х(0)(0), х((1), х(4)х(2),..., х(2Р-2)- -9х(Г-1), т.е. рассматриваем преобразование Фурье-Галуа размерности Р (четверть матрицы х(Х.(п)гр). Коэффициент s (i), i О, 1,...,Р-1 вычисляется согласно выражению:

S(i) (...((х(0)2 + х(О)-21 + + х(2))-2 + ...+ х(Р-1))-2 1,. (6)

Результат вычисления преобразования Фурье-Галуа для четных значений х(п) (спектоальные коэффициенты S (0), Sr(2),..:, )) запоминается в регистрах 10 блоков 1 вычисления коэффициентов. Для этого на вход 4. подается управляющий сигнал (фиг.4). На узел 9 подаются сигналы управления, обеспечивающие прямую передачу кодовых слов без инвер- т,ирования (на вход 17 подается значение сигнала, соответствующее 1й,

10

на вход 18- значение,,соответствующее О).Далее,точно так же вычисляются спектральные коэффициенты S (1), ; S (3),..., S(2P-1).

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

,т.е. сигнал на вход 4g в этом случае не подается). С выхода сумматора 6 через узел 9 без инвертирования значение спектрального коэффициента S (i), i - нечетное, подается на вход сумматора 11 , на другой вход которо- го с выхода регистра 10 подается значение коэффициента S (j), j - четное (i j после перенумерации). Сумматор 11 реализует сумму по модулю М, С этой целью выход переноса этого 20 сумматора соединен с собственным входом переноса. После суммирования получают первые Р коэффициентов S(0)j S(2)s...,S(2P-2) преобразования с матрицей размерности 2Р&2Р. Значения этих коэффициентов считываются с выходов блоков 1. После считывания коэффициентов 3(0), 8(2),..., S(2P-2) в общую вычислительную систему на вход сумматора 11 каждого блока 1| подаются инвертированные с помощью узлов 9 значения коэффици1631554 8

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

25

30

35

циентов S (1), S (3),...,S (2P-1). После вычисления суммы получают вторые Р коэффициентов S(1), -SO) ,.., S(2P-1). Коэффициенты на выходах 3 переставляют в соответствии с (5). При подаче на вход 17 управляющего сигнала, соответствующего 1, а на вход 18 - соответствующего О, вход-40 сумматора, информационный выход котоные данные без изменений передаются на выход 16. Если же на вход 17 подать управляющий сигнал соответствуют щий уровню О, а на вход 18 - сигнал соответствующий уровню 1, то , 45 слова входных данных подвергаются поразрядному инвертированию и пода- ются на выход 16.

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

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

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

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

Фаг.1

Фиг.З

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

/1

Ст,

г

il

i

a

n

П

n

П

n

x

П

Ј. 6

п

П

П

4

t t

г ь