Ефективне обчислення косинуса і синуса. Використання навантаженої суми розряду продукції.
Резюме-кутове обертання базується на підході до одночасного обчислення представлених синуса і косинуса. Цей підхід приводить навантажену суму розряду (бітової) продукції двійкових шматків(розрядів), що представляють кут х. Ми обговорюємо необхідне число термінів в многочленні також як і необхідний коефіцієнт довжини рядка, як функцію точності. Підхід приводить комбінаторну реалізацію з малою складністю. Ми також пропонуємо відповідність швидкої і простої архітектури. Комбінаторний цикл містить малий час очікування і легко може бути системою постачання (джерелом інформації) для високої продуктивності.
І.Вступ
Тригонометричні функції синуса і косинуса відіграють важливу роль у різних процесах сигналів систем, як графіки: швидке перетворення Фур`є (ШПФ), модуляція/демодуляція, прямі цифрові частотні синтезатори, і т.д. Синус і косинус можна обчислювати використовуючи велику різноманітність цифрових методів. Ми направляємо читача до недавніх коротких оглядів [1]. Робота видана після короткого огляду в [1] включає приклад [2]-[4].У цьому документі ми пропонуємо новий підхід, заснований на кутовому обертанні, розкладі і одночасному додаванні синуса і косинуса. Виражаючи окремий кут обертань як навантажену суму шматкової продукції і нехтуючи найменшою вагою, ефективністю, незначною складністю, досягаємо реалізації. У параграфі 2 ми представляємо основний підхід і обговорюємо числові властивості, в той час, як в параграфі 3 ми обговорюємо відповідну архітектуру. Далі в параграфі 4 представлений приклад для застосування (ШПФ) в процесорі. Наостанок, деякі висновки.
ІІ. Запропонований підхід
Щоб оцінити однаковою мірою проміжку точок N,на одиничному колі, необхідно спочатку оцінити перші N/8+1 точок. Це тому, що на кожен октант може проектуватись перший октант через обертання або обертання з операцією відображення. Тепер нам необхідно лише додавати косинус і синус в першому октанті. Це повинно часто використовуватись у… наприклад, квадратурах DDFS [1][5]. Ми виражаємо кут х в термінах кутового розкладу, ?, і, е.

де ?=2?/N. Завдяки, заздалегідь обговореної, симетрії октанта ми надалі обговорюватимемо тільки випадок . Використовуючи три найбільш важливі біти х, ми можемо перетворити будь-який кут на ряд відповідний куту з ряду , який вказано в таблиці 1. Термін х’ означає зображення (образ), використовуючи W-2 молодших бітів. Заперечення бітів у х’ повинно трактуватись як два доповнення, тобто перевертаючи і додаючи один до позиції LSB. Відзначте, що використання стандартних тригонометричних функцій як, наприклад, sin(-x`)=-sin(x`) не можливе в таблиці 1, так як результат х’ був би за межами ряду .

Таблиця 1.Картографія октанта.
Вартість виконання може бути потім зменшеною, умовно заперечуючи найменшу істотну частину входу і, умовно обмінюючи і заперечуючи, sin(x) i cos(x), як це показано на рис 1.
Тут ми розглянемо проблему додавання sin(x) i cos(x), використовуючи кутове обертання. Використовуючи (1) ми маємо:

і у матричній формі ми маємо:

Цей вираз представляє W подвійне навантаження кута обертань одиничного вектора . Відтепер кожна матриця означає, що кут одиничного вектора є також незмінним або зростає з коефіцієнтом Ці обертання можуть легко здійснюватись безпосередньо використовуючи будь-який дійсний комплекс або поширювати арифметику [6].У алгоритмі CORDIC [7], (3) переписаний відповідно до (4) таким чином, що матричне множення стає послідовністю простих додавань або віднімань.

Рис.1.Реалізація використанням симетрії октанта.

де і

Це дає:

Проте, ми визнаємо, що маємо:

і

Виконуючи матричні множення (3) і використовуючи (7) і (8) ми отримаємо:

Це є сума М=2 EMBED Equation.3 термінів, кожен складається з константи часів продукту двійкових змінних. Продукти можуть бути сформованими відбором всіх можливих двійкових продуктів від шматків в кутовому уявленні без повторення будь-яких двійкових змінних. Також дозволяється виділення без змінних. Наприклад для 3-розрядного кута де є 2 EMBED Equation.3 =8 продуктів:
і , де продукт 1 відповідає випадку, де не вибрані бінарні змінні. Відзначте: це для випадку:
Поки що ми не отримали ніякого суттєвого скорочення у вартості представлення, починаючи з числа термінів у (9) що є такою ж самою, якби ми запам’ятали sin(x) i cos(x) безпосередньо в двох списках(таблицях).Проте величина більшості коефіцієнтів s EMBED Equation.3 i c EMBED Equation.3 -незначна і нею можна знехтувати.
Рис.2 показує розміщення величини коефіцієнтів для синуса. Число розрядів для одного октанта=1, тобто повне число вхідних розрядів-більше двох. З Рис.2 зрозуміло, що максимальні і мінімальні величини для коефіцієнтів змінюються в деякій послідовності. Відтепер, розумно припустити, що істотна частина найменших коефіцієнтів може бути знехтувана. Розміщення(розподіл) для коефіцієнтів косинуса є подібним. Щоб узяти(розвинути) це міркування далі, число правильного входу розрядів отриманих, нехтуванням найменшими розрядами продукту показане в Рис.3.Суцільні лінії відповідають справжнім коефіцієнтам s EMBED Equation.3 з (9), штрих пунктир - доки лінії відповідають безперервній вазі, мінімізуючи максимальну помилку як описано в [8].Видно, що висока точність може бути отримана не дивлячись не нехтування більш ніж половини розрядів продукції. Для прикладу, використання 10-розрядного входу (N=4096), точність майже 14 розрядів отримана, використанням 100 розрядів продукції поза 512 в обчисленні, використовуючи коефіцієнти, обчислені в (9).Застосування підходу лінійної оптимізації запропонованого в (8) збільшує точність близько до 17 розрядів. У випадку високої потреби кутового рішення число розряду продукції може ставати надмірним, як М=2 EMBED Equation.3 у (9).Проте, як видно з Рис.2, співвідношення між найбільшою і найменшою вагою зростає з W.Відтепер, необхідне число розрядів продукції не зростає вдвічі.
На Рис.4 необхідна кількість розрядів продукції показана для 12 і 16 – розрядної точності, що приймає на себе різні кутові рішення (відповідність довжини ШПФ).Ці номери отримані використанням оптимізації з безперервних змінних для n ваг з найбільшою початковою величиною, відповідно до (9).Тут можна побачити, що необхідне число розрядів продукції зростає приблизно лінійно до числа вхідних розрядів.
Точність функції обмеженого коефіцієнта довжини рядка показано в Рис.5.Коефіцієнти, основані на (9) округлюються до певної довжини рядка. З Рис.5 зрозуміло, що використовуючи округлення в обсязі двох додаткових розрядів є необхідним для ваги. Використовуючи оптимізацію, число додаткових розрядів може бути зменшене [8].

Рис.2:Розміщення коефіцієнтів s EMBED Equation.3 для синуса на проміжку

Рис.3:Точність проти числа термінів за синус на проміжку .Коефіцієнти, узяті з (9) (суцільна) і оптимізовані (штрихпунктир).
З обмеженою довжиною слова для ваги, не вся вага залишається ненулевою, як показано на Рис.6.Відтепер, фактичне число не мулевих коефіцієнтів зменшується із зменшенням коефіцієнтів довжини слова. Для збільшення кількості вхідних розрядів відносне число ненулевої ваги зменшується. Це також можна побачити на Рис.2.
ІІІ. Запропонована архітектура.
Сума навантажених розрядів продукції або для синуса або косинуса в (9) може бути реалізована як показано в Рис.7.Andstage-невідоме слово проводить необхідні розряди продукції. Ці розряди продукції потім переміщаються відповідно до коефіцієнтів у стадіє покоління часткового продукту і додаються, використанням дерева сумування, наприклад, дерево Уолеса.
Коефіцієнти представлені, використовуючи канонічні позначені цифри (КПЦ) представлені в [6].Для позицій розрядів відповідність позитивній цифрі в уявленні (КПЦ) розряд додається в ту колонку

Рис.4:Число розрядів продукції, необхідної проти (ШПФ) розмір (кутове рішення),N,для різної точності

Рис.5:Точність проти коефіцієнтів довжини слова для розряду продуктів для синуса на проміжку



Рис.6:Відносне число ненулевої ваги після округлення до певної довжини рядка.

Рис.7:Запропонована архітектура для виконання генерації синуса або косинуса в інтервалі
. Для заперечення цифри в уявленні КПЦ, одного розряду іншим, використовується додаткове представлення. Щоб уникнути поширення знаку, використовується вектор компенсації. Розглянемо віднімання цифри х. Розширення знаку більше двох позицій дає ххх. Це може бути переписане як 111+00х, де частина 111-вектор компенсації. Відтепер перевернутий розряд продукції доданий дереву. Вся компенсація векторів і ваги, відповідно до 1 розряду продукції може, бути зібрана в одному коефіцієнті, що додається в дереві.
Для підрахунку всіх можливих кутів використано підхід, ілюстрований у Рис.1 і таблиця 1.Відзначте, що Andstage-невідоме слово з генерації косинуса і синуса, також частини додавання дерев можуть зливатись(поглинатись).
Час очікування цієї архітектури –низький, що є важливим в багатьох застосуваннях. До того ж, це може бути легко системою постачання (джерелом інформації) для отримання високої продуктивності.
ІV.Приклад
Як приклад, ми вибираємо крутильний фактор генератора для 4096 точок процесора ШПФ. Точність складає 16 розрядів що краще як для синуса, так і косинуса. Коефіцієнти, оптимізовані для малої кількості ненулевих розрядів в уявленні КПЦ, використовуючи 20 розрядів коефіцієнтів.
Число термінів в (9) складає 111 в підсумку.69-ті,що використовуються як для синуса, так і косинуса, з 20 унікальними для синуса і 22 унікальних для косинуса. Тому, синус має 89, а косинус 91 розрядів продукції, що є збільшенням близько десяти шматкових продуктів порівняно з Рис.4, завдяки обмеженню ваги довжини слова.
Дерево сумування для синуса складається з 241 ФА, 67 ХА, в той час як, для косинуса необхідно 261 ФА, 71 ХА. Кожне дерево сумування приблизно відповідає 16х16-розрядів множника.
Повне число входів для простого синтезу VHDL складає 2630 (стандартних чарунків) з областю 0.231 мм EMBED Equation.3 , використовуючи 0.35 ??m чарунків стандартної бібліотеки CMOS. Критичний шлях без обробки складає 27(не уточнено), відповідаючи продуктивності 32.2 Msample/s.Звичайно, продуктивність може збільшити обробка, цикл оптимізації і використання швидкого поширення.
Для порівняння використаємо пряме представлення CORDIC. Довжина слова складає 22 розряди для акумуляторів даних і 21 розряд для кута акумулятора. Алгоритм CORDIC розгорнутий 18 разів. Це дає найгіршу точність 16.15 розряду, використовуючи усікання для квантування. Виконання складається з 3876 стандартних чарунків з повною областю 0.406 мм EMBED Equation.3 .Критична межа складає 185 (не уточнено), відповідаючи продуктивності 5.4 Msample/s.
Хоча можна збільшити архітектуру CORDIC декількома способами, цей приклад показує життєздатність запропонованого підходу. Для цього запропонованого випадку результати в області чіпа, на 43% менші, в той час, як продуктивність на 85% більша, порівняно з прямим розгортанням CORDIC.
V.Висновки
Було запропоновано підхід для обчислення навантаженої суми розрядів продукції як косинуса, так і синуса, що заснований на кутових обертаннях і розкладанні. Довільний кут в інтервалі від 0 до 2? рад. перше(спочатку) проектується на перший октант. Кутові обертання, необхідні в цьому октанті, виражені в термінах вхідних розрядів, що представлені х. Результатом виразів для синуса і косинуса є дві навантажені суми розряду продукції, які використовують ці розряди. Багато з цих термінів можуть бути знехтувані, оскільки вони значно менші, ніж дозволена похибка. До того ж швидке передавання запропонованої апаратної архітектури має низький час очікування і легко може бути джерелом інформації для максимальної продуктивності.