Реализуйте эффективное оборудованием разложение QR Используя CORDIC в систолическом массиве

В этом примере показано, как вычислить разложение QR матриц с помощью эффективного оборудованием кода MATLAB® в Simulink®.

Чтобы решить систему уравнений или вычислить решение методом наименьших квадратов к матричному уравнению AX = B использование разложения QR, вычислите R и Q'B, где QR = A, и RX = Q'B. R является верхней треугольной матрицей, и Q является ортогональной матрицей. Если вы только хотите, чтобы Q и R, то установленный B были единичной матрицей.

В этом примере R вычисляется из матрицы А путем применения преобразований Givens с помощью алгоритма CORDIC. C = Q'B вычисляется из матрицы B путем применения тех же преобразований Givens. Алгоритм использует только итеративные сдвиги и сложения, чтобы выполнить эти расчеты.

Для получения дополнительной информации об алгоритме, используемом в этом примере, смотрите, Выполняют QR-факторизацию Используя CORDIC

Обзор

Модель Simulink, используемая в этом примере:

fxpdemo_real_4x4_systolic_array_QR_model

Чтобы ввести ваши собственные входные матрицы, A и B, открывают параметры блоков соответствующих активированных блоков подсистемы налево. После симуляции модель возвращает вычисленные выходные матрицы, C = Q'B и R к рабочей области. Можно задать количество итераций CORDIC в параметрах блоков транспонирования (Q) *B, R 4x4 Действительная Систолическая подсистема Массивов CORDIC. Если входные параметры являются фиксированной точкой, то количество итераций CORDIC должно быть меньше размера слова. Точность расчета улучшается на один бит для каждой итерации до размера слова входных параметров.

Эта модель будет работать с фиксированной точкой и одним типами данных.

Чтобы видеть, как алгоритм выполняет факторизацию, посмотрите под маской транспонирования (Q) *B, R 4x4 Действительная Систолическая подсистема Массивов CORDIC. Аннотации указывают, какие строки матрицы управляются, чтобы обнулить поддиагональные элементы. Систолический массив настраивается для матрицы А 4 на 4, но может быть расширен к любому размеру следующим тот же шаблон. Эта реализация работает только с действительными входными матрицами.

Чтобы видеть код MATLAB в блоке MATLAB function, который выполняет преобразования Givens с помощью CORDIC, продолжите смотреть под масками блока.

В этом примере, количестве строк и столбцов быть 4. Матрица B должна иметь 4 строки и любое количество столбцов.

Используйте QR, чтобы решить матричное уравнение Ax = B

Первый шаг в решении матричного уравнения AX = B должен вычислить RX = Q'B, где R является верхне-треугольным, Q является ортогональным и Q*R = A.

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

format
NumberOfCORDICIterations = 52;
A = 2*rand(4,4)-1;
B = 2*rand(4,4)-1;

Симулируйте модель, чтобы вычислить R и C = Q'B.

sim fxpdemo_real_4x4_systolic_array_QR_model
R
C
R =

    1.5149   -0.0519    1.7292   -0.3224
         0    0.9593   -0.0259   -0.0879
         0         0    0.2565    1.0888
         0         0         0   -0.6429


C =

    0.5942   -0.2382    0.0676   -0.9370
   -0.8887    0.6146   -0.5758    0.3051
    0.1725    0.7339    0.5409    0.5374
    0.8540    1.1078   -0.2183   -0.5620

Проверьте, что замена спины с R и C = Q'B дает те же результаты как MATLAB.

X = R\C
X_should_be = A\B
X =

   -7.1245  -12.1131   -0.6637    1.4236
   -0.8779    0.7572   -0.5511    0.3545
    6.3113   10.1759    0.6673   -1.6155
   -1.3283   -1.7231    0.3396    0.8741


X_should_be =

   -7.1245  -12.1131   -0.6637    1.4236
   -0.8779    0.7572   -0.5511    0.3545
    6.3113   10.1759    0.6673   -1.6155
   -1.3283   -1.7231    0.3396    0.8741

Норма различия между встроенным MATLAB и решением CORDIC QR должна быть малой.

norm(X - X_should_be)
ans =

   3.6171e-14

Вычислите Q и R

Чтобы вычислить Q и R, установите B, равный единичной матрице. Когда B равняется единичной матрице, затем Q = C'.

NumberOfCORDICIterations = 52;
A = 2*rand(4,4)-1;
B = eye(size(A,1),'like',A);
sim fxpdemo_real_4x4_systolic_array_QR_model

Q = C';

Теоретическое разложение QR является QR == A, таким образом, различие между вычисленным QR и A должно быть малым.

norm(Q*R - A)
ans =

   2.2861e-15

QR не уникален

Разложение QR только уникально до знаков строк R и столбцов Q. Можно сделать уникальное разложение QR путем создания диагональных элементов R всеми положительный.

D = diag(sign(diag(R)));
Qunique = Q*D
Runique = D*R
Qunique =

   -0.3086    0.1224   -0.1033   -0.9376
   -0.6277   -0.7636   -0.0952    0.1174
   -0.5573    0.3930    0.7146    0.1559
    0.4474   -0.4975    0.6852   -0.2877


Runique =

    1.4459   -0.8090    0.1547    0.3977
         0    1.1441    0.0809   -0.2494
         0         0    0.8193    0.1894
         0         0         0    0.4836

Затем можно сравнить вычисленный QR от модели до встроенного MATLAB qr функция.

[Q0,R0] = qr(A);
D0 = diag(sign(diag(R0)));
Q0 = Q0*D0
R0 = D0*R0
Q0 =

   -0.3086    0.1224   -0.1033   -0.9376
   -0.6277   -0.7636   -0.0952    0.1174
   -0.5573    0.3930    0.7146    0.1559
    0.4474   -0.4975    0.6852   -0.2877


R0 =

    1.4459   -0.8090    0.1547    0.3977
         0    1.1441    0.0809   -0.2494
         0         0    0.8193    0.1894
         0         0         0    0.4836

Используйте фиксированную точку для аппаратного эффективного внедрения

Используйте типы входных данных фиксированной точки, чтобы произвести эффективный HDL-код для устройств FPGA и ASIC.

Для получения дополнительной информации о том, как выбрать типы данных с фиксированной точкой, которые не переполнятся, относиться к примеру, Выполняют QR-факторизацию Используя CORDIC.

Можно запустить много тестовых воздействий через модель путем создания A и 3-мерные массивы B.

n_test_inputs=100;

Следующий раздел задает случайные входные параметры для матриц A и B, которые масштабируются между-1 и 1, таким образом, устанавливает размер слова фиксированной точки на 18 битов и дробную длину к 14 битам допускать рост в QR-факторизации и промежуточных расчетах в алгоритме CORDIC.

word_length = 18;
fraction_length = 14;

Количество лучшей точности итераций CORDIC является размером слова минус один. Если номер итераций CORDIC будет определен к меньшему, чем word_length - 1, то задержка и такты системных часов к следующему готовому сигналу будут короче, но это будет менее точно. Номер итераций CORDIC не должен быть определен немного больше, потому что сгенерированный код не поддерживает сдвиги, больше, чем размер слова фиксированной точки.

NumberOfCORDICIterations = word_length - 1
NumberOfCORDICIterations =

    17

Случайные тестовые воздействия конкатенированы так, чтобы во время k, входные параметры были (:: k) и B (:: K. Каждый элемент массива и B являются универсальной случайной переменной между-1 и +1.

A = 2*rand(4,4,n_test_inputs)-1;

Выберите B, чтобы быть единичной матрицей так Q=C'.

B = eye(4);
B = repmat(B,1,1,n_test_inputs);

Бросьте к фиксированной точке и бросьте B как A.

A = fi(A,1,word_length,fraction_length);
B = cast(B,'like',A);

Симулируйте модель

sim fxpdemo_real_4x4_systolic_array_QR_model

Вычислите и постройте ошибки

norm_error = zeros(1,size(R,3));
for k = 1:size(R,3)
    Q_times_R_minus_A = double(C(:,:,k))'*double(R(:,:,k)) - double(A(:,:,k));
    norm_error(k) = norm(Q_times_R_minus_A);
end

Ошибки должны быть порядка 10^-3.

clf
plot(norm_error,'o-')
grid on
title('norm(QR - A)')

%#ok<*NASGU,*NOPTS>
Для просмотра документации необходимо авторизоваться на сайте