устройство для обработки цифрового сигнала

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

1. УСТРОЙСТВО ДЛЯ ОБРАБОТКИ ЦИФРОВОГО СИГНАЛА, содержащее арифметические блоки, отличающееся тем, что арифметические блоки объединены в две группы вычислительных ячеек, входы арифметических блоков первых вычислительных ячеек первой и второй групп соединены с соответствующими входами устройства, выходы суммы арифметических блоков каждой предыдущей ячейки первой и второй групп соединены с входами арифметических блоков последующей ячейки первой группы, выходы разности арифметических блоков каждой предыдущей ячейки первой и второй групп соединены с входами арифметических блоков последующей ячейки второй группы, выходы суммы арифметических блоков последней ячейки первой и второй групп и выходы разности арифметических блоков последней ячейки первой и второй групп и соединены с соответствующими выходами устройства.

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

Описание изобретения к патенту

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

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

Однако данное устройство обладает значительной сложностью и невысоким быстродействием.

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

Однако данное устройство также имеет значительную сложность и невысокое быстродействие.

Наиболее близким по технической сущности к изобретению является блок преобразования, осуществляющий сжатое преобразование Уолша-Адамара, содержащий арифметические устройства двух уровней.

Недостатком известного устройства являются его узкие функциональные возможности, так как он выполняет только сжатое преобразование Уолша-Адамара.

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

Цель достигается тем, что в устройстве для обработки цифрового сигнала, содержащем арифметические устройства и соответствующие связи между ними, вход и выход содержит (N/2)log₂N арифметических устройств, объединенных в 2log₂N вычислительных ячеек по k(k N/4) арифметических устройств.

На фиг. 1 приведена функциональная схема устройства для обработки цифрового сигнала; на фиг. 2 функциональная схема вычислительной ячейки; на фиг. 3 показан граф вычислительной процедуры преобразования по Уолшу-Адамару для N 8; на фиг. 4 представлена функциональная схема устройства для N 8; на фиг. 5 функциональная схема вычислительной ячейки для N 8.

Устройство для обработки цифрового сигнала содержит вход 1, матрицу i x j вычислительных ячеек 2(i log₂N, j 2), связи между ними, выход 3. Вычислительная ячейка 2 содержит k арифметических устройств 4, входы 5 и 6, выходы 7 и 8. Арифметическое устройство имеет два входа операндов и два выхода суммы и разности этих операндов. Выходы суммы арифметических устройств соединены с выходом 7 вычислительной ячейки. Выходы разности арифметических устройств соединены с выходом 8 вычислительной ячейки. Выходы 7 (1, j)-х вычислительных ячеек соединены с входами 5 (1, j + 1)-х вычислительных ячеек матрицы. Выходы 7 (2, j)-х вычислительных ячеек соединены с входами 6 (1, j + 1)-х вычислительных ячеек матрицы. Выходы 8 (1, j)-х вычислительных ячеек соединены с входами 5 (2, j + 1)-х вычислительных ячеек матрицы. Выходы 8 (2, j)-х вычислительных ячеек соединены с входами 6 (2, j + 1)-х вычислительных ячеек. Выходы 7 и 8 вычислительных ячеек последнего столбца соединены с выходом 3 устройства так, что с выходов 7 этих ячеек снимаются четные отсчеты результата преобразования, а с выходов 8 снимаются нечетные отсчеты результата преобразования.

Принцип действия устройства основан на выполнении над вектором-столбцом исходных данных размерностью N следующего преобразования:

=H,(1) где вектор-столбец коэффициентов Уолша-Адамара;

H_N матрица Уолша-Адамара размерностью N x N;

N 2n, где n положительное целое число.

Преобразования Уолша-Адамара производятся итерационно за n итераций по формуле

=S_NH⁽_Nⁿ⁾.SH⁽_N²⁾(S_NH⁽_N¹⁾X), (2) где H_N⁽¹⁾ H_N⁽²⁾ H_N⁽ⁿ⁾ матрица размерностью N x N;

S_N мономиальная матрица перестановки;

H⁽_N¹⁾=1_N/2 H₂, i=1,n где 1_N/2 единичная матрица порядка N/2;

H₂ матрица Адамара порядка 2,

H₂

Вычислительная процедура (2) реализуется за n(n log₂N) итераций. Каждая i-я (i ) итерация сводится к сложению или вычитанию соответствующих элементов вектора и переупорядочению элементов результирующего вектора Х_i. Суть перестановки заключается в разделении элементов вектора на четные и нечетные. При этом массив нечетных элементов вектора располагается в первой половине результирующего массива.

Устройство работает следующим образом.

В статическом режиме исходные данные для преобразования на вход устройства не поступают. В динамическом режиме на вход 1 устройства (фиг. 1) подаются исходные данные для преобразования значения элементов вектора-столбца x₁(i=0,)в цифровом виде и поступают на входы 5 и 6 вычислительных ячеек первого столбца, причем первые N/2 отсчетов подаются на вычислительную ячейку 2₁₁, а вторые N/2 отсчетов на вычислительную ячейку 2₂₁. На входы 5 и 6 этих ячеек подается соответственно по k(k N/4) отсчетов. Вычислительная ячейка (фиг. 2), содержащая k арифметических устройств, формирует на их выходах "+" и "-" одновременно сумму и разность двух элементов вектора . Суммы подаются на выход 7 вычислительной ячейки, а разности на выход 8 вычислительной ячейки. Поскольку отсчеты поданы на вход 1 (1₁ 1_N) в естественном порядке, то за счет связей между вычислительными ячейками столбцов матрицы должна быть произведена перестановка элементов результирующего вектора путем разделения на четные и нечетные. Поэтому сумма с выхода 7 ячейки 2₂₁ подается на вход 5 ячейки 2₁₂, сумма с выхода 7 ячейки 2₂₁ подается на вход 6 ячейки 2₁₂, разность с выхода 8 ячейки 2₁₁ подается на вход 5 ячейки 2₂₂, разность с выхода 8 ячейки 2₂₁подается на вход 6 ячейки 2₂₂, разность с выхода 8 ячейки 2₂₁ подается на вход 6 ячейки 2₁₂. Тем самым осуществляется первая итерация. Аналогично осуществляются последующие итерации. Суммы с выходов 7 ячеек 2_ij подаются на вход 5 ячеек 2_1,j+1. Суммы с выходов 7 ячеек 2_2jподаются на вход 5 ячеек 2_j+1. Разности с выходов 8 ячеек 2_1j подаются на входы 5 ячеек 2_2,j+1. Разности с выходов 8 ячеек 2_2,j подаются на входы 6 ячеек 2_2,j+1. Через n итераций получают на выходе 3 устройства результат преобразования цифрового сигнала по Уолшу-Адамару в виде элементов вектора-столбца . Причем на выход 3 устройства результат подается следующим образом: на выходы 3₁ 3_k подаются суммы с выхода 7 ячейки 2_1,j, на выходы 3_k+1 3_2k суммы с выхода 7 ячейки 2_2,j, на выходы 3_2k+1 3_k разности с выхода 8 ячейки 2_i,j, на выходы 3_2k+1 3_N разности с выхода 8 ячейки 2_2,j. Таким образом, на выходе 3 устройства сформированы элементы вектора-столбца , расположенные в естественном порядке.

Рассмотрим работу устройства на примере для N 8. Функциональная схема устройства для N 8 приведена на фиг. 4. Устройство содержит шесть вычислительных ячеек 2_i,j (2log₂8 6). Схема вычислительной ячейки 2_i,j (i j ) приведена на фиг. 5. Она содержит два арифметических устройства 4₁ и 4₂, входы 5₁, 5₂, 6₁, 6₂, выходы 7₁, 7₂, 8₁, 8₂. Пусть на вход 1 устройства подаются элементы вектора-столбца х₀, х₁, х₂, х₃, х₄, х₅, х₆, х₇. Выполняемые в каждой итерации арифметические операции и функционирование устройства описываются таблицей.

Таким образом, рассмотренное устройство обладает более широкими возможностями, так как позволяет выполнять над цифровым сигналом полное преобразование Уолша-Адамара. Кроме того, оно обладает однородными связями между вычислительными ячейками, что определяет его высокую технологичность при реализации на основе СБИС. По сравнению с аналогами предлагаемое устройство обладает более высоким быстродействием, так как все элементы вектора-столбца исходных данных обрабатываются параллельно, а не последовательно, что увеличивает быстродействие, а также обладает меньшей конструктивной сложностью за счет однородности структуры устройства и вследствие этого более высокой технологичностью при реализации на СБИС и более высокой надежностью. Применение данного устройства в рассматриваемой области позволяет достичь следующих общественно-полезных преимуществ: повысить технологичность реализуемых устройств данного класса при реализации их на основе интегральной технологии и, следовательно, снизить их стоимость; расширить области применения, вследствие чего возможно снижение затрат на разработку аналогичных устройств в интересах других областей народного хозяйства.