Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Ділення комплексних чисел методом Волдера
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра захисту інформації
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
„ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
Кафедра захисту інформації
Курсова робота
з курсу:
„ Комп’ютерні методи дослідження
інформаційних процесів та систем ”
на тему:
„Ділення комплексних чисел методом Волдера”
В даній роботі розглянено застосування методу CORDIC для ділення комплексних чисел. Він побудований в середовищі С# і платформі Visual Studio 2008. Графіки уточненнь побудовані в Microsoft Excel
Зміст
Вступ……………...............................................................................................4
Основна частина……………………………………………………..………..6
Ділення комплексних чисел…………….…………………......................6
Ділення комплексних чисел алгебраїчним методом…………......6
Ділення комплексних чисел в тригонометричній формі…...........7
Ділення комплексних чисел в тригонометричній формі………..8
Метод Волдера…………………………………………………………..9
Ділення комплексних чисел методом Волдера…………….………....17
Висновок…………………………………………………………….……….18
Список літератури…………………………………………………………..19
1.Вступ
Ко́мпле́ксні чи́сла— об'єкти, що утворюють поле, яке є розширенням поля дійсних чисел і позначається C.
Найбільш поширеним є запис комплексних чисел у вигляді виразів
, (1)
Де а, b — дійсні числа, причому a називається дійсною, а b - уявною частиною числа z; ці частини позначаються відповідно та .
Символом і позначається уявна одиниця для якої виконується рівність
. (2)
Комплексне число можна зобразити точкою площини з координатами (a,b). Кожне комплексне число виду a+0i ототожнюється з дійсним числом a.
Кожному комплексному числу відповідає деякий вектор на площині, а будь-який вектор задається довжиною і напрямком. Наприклад вектор z можна задати кутом який цей вектор утворює з додатним напрямком осі . Домомвимось, що всі кути відраховуються від осі проти годинникової стрілки.
/
Нехай `відповідає комплексному числу позначимо через довжину вектора , а через кут, який утворює цей вектор з додатним напрямком осі , тоді
(3)
(4)
(5)
(6)
- тригонометрична форма комплексного числа.
Назвемо - модулем комплексного числа , а - аргумент комплексного числа (, якщо , то аргумент не визначається).
2.Основна частина
2.1. Ділення комплексних чисел
Ділення двох комплексних чисел потребує складних обчислювальних операцій. В ході побудови алгоритму ділення, а особливо комплексних чисел, намагаються уникати або замінювати елементарними функціями.
Однак, зі зростаючим числом продуктів, що вимагають високої точності обчислень, в багатьох випадках таке ухилення або заміна призведе до серйозної деформації числової точності.
В останні роки велику увагу приділяють розвитку і впровадженню ефективних алгоритмів поділу. Проте, більшість із запропонованих методів є реалізаціями цілочисельного поділу, і дуже мало хто вивчав справу з комплексними числами.
Ділення комплексних чисел за стандартною формулою часто реалізується в програмному забезпеченні. Програмне забезпечення реалізації поділу комплексних чисел часто призводить до низької швидкості розрахунку, що робить їх непридатними для використання в сучасних високопродуктивних продуктах. Таким чином, все більшого значення для отримання апаратних методів виконання суперечливих вимог, що стосуються чисельної точність, швидкості розрахунків а також затримки і області споживання.
2.1.1. Ділення комплексних чисел алгебраїчним методом
Визначимо ділення як операцію обернену до множення
(1.1)
Частку комплексних чисел , де , визначимо як таке комплексне число , що задовольняє рівність
(1.2)
Розпишемо (2) (1.3)
Зауважимо, що операція множення комплексних чисел виконується так само, як з біномами(двочленами) із зауваженням на те, що
Отже з (3) будемо мати
(1.4)
З (4) (1.5)
Ми отримали систему лінійних алгебраїчних рівнянь для визначення x та y
Випишимо визначник цієї системи:
.
Система має єдиний розв’язок якщо
Проте, насправді ділення виконується за формулою (1.6)
2.1.2 Ділення комплексних чисел у тригонометричній формі
Задамо два числа в тригонометричній формі
(1.7)
Домножимо чисельник і знаменник на число комплексно спряжене до знаменника:
Отже, (1.8)
Тобто, щоб поділити два комплексних числа в тригонометричній формі потрібно поділити модулі, а аргументи відняти.
2.1.3 Ділення комплексних чисел методом трансформації
Під час ділення за допомогою трансформації, обидва комплексні числа перетворюють за формулою а також в тригонометричну форму . Дійсні значення змінних можуть бути розміщені між комплексними числами і а кут можна легко отримати шляхом віднімання двох аргументів, і , як показано в наступному рівнянні:
(1.9)
Ці перетворення можуть бути застосовані і в зворотньому напрямку. 2.2 Метод Волдера
Як було сказано в пункті 1, ділення комплексних чисел алгебраїчним методом намагаються уникати, оскільки воно споживає надто багато ресурсів.
Інший спосіб реалізації ділення комплексних чисел – за допомогою перетворень (1.9). Комплексні числа може бути перетворені з лінійної в полярну систему координат. Після ділення за формулою (1.8) результат повинен бути переведений назад в Декартові систему. Проте це обійдеться великими затратами апаратних ресурсів.
Ще один метод трансформації, який набув значної популярності через простоту і ефективність є COordinate Rotation DIgital Computer (CORDIC метод ) – цифровий комп’ютер для обертання координат – абревіатура назви методу. Він був описаний Джеком Волдером (J.Volder) ще у 1959 році. Це простий метод для програмної та апаратної реалізації . Адже класичний CORDIC вимагає для свого втілення лише невеликий об’єм пам’яті та деякі елементарні операції типу зчитування з пам’яті, додавання, віднімання та зсуву.
Будемо розглядати метод о з опису кола одиничного радіуса.
З можливих форм математичного представлення неявної та параметричної, оберемо параметричну.
У випадку параметричного представлення положення будь – якої точки на колі, що має координати (x,y)Т , описується такими рівняннями
(2.1)
Тут φ – це кут, який утворив вектор початкового положення (xo,yo)T = (1,0)T, рухаючись по колу, з віссю абсцис, кінець якого досяг точки (x,y)T
Зв'язок між координатами двох точок, що лежать на колі можна описати з допомогою повороту вектора навколо початку декартової системи координат. Точка, що знаходиться на кінці вектора і має початкові координати (x,y)T, завдяки повороту вектора на кут φ займе нове положення з координатами (x,y)T. Якщо рух відбувається проти годинникової стрілки, то зв'язок описується такими рівняннями :
(2.2)
/
Якщо зобразити рух точки по колу як сумарний результат мікрообертань вектора навколо початку системи координат на мікрокути , які є частиною загального вхідного кута , зв'язок між двома сусідніми точками з координатами (xі,yі)T та (xі+1,yі+1)T для колового обертання вектора буде такий :
(2.3)
Як бачимо, для здійснення одного мікрообертання необхідно мати обчислені значення синуса та косинуса кута та провести чотири операції множення. Перетворимо систему (2.3) з метою зменшення кількості необхідних операцій та спрощення апаратної реалізації такого пристрою. Для цього зобразимо її у наступному вигляді:
(2.4)
Тепер спробуємо замінити множення зсувами.
Проведемо заміну в системі (2.4) – будемо вибирати елементарні кути
виходячи з умови
. (2.5)
В цьому випадку , a даний кут повороту наближається сумою знакозмінних кутів :
, (2.6)
де -оператор вибору (decision operator) напрямку обертання.
Наприклад
/
Отже (7) можна замінити на
(2.7)
В розгорнутому вигляді ця система зобразиться так:
Отже, для здійснення одного мікрообертання необхідно мати наперед обчислене значення косинуса кута та провести лише дві операції множення. Дві інші операції множення замінені операціями зсуву.
Враховуючи (2.2),(2.5)-(2.7), можемо записати:
=
==, (2.8)
де . (2.9)
Зауважимо, що при цьому
(2.10)
(2.11)
(2.12)
Таким чином (11) перепишеться як:
, (2.13)
де .
В свою чергу можна записати, що добуток матриць, який знаходиться в дужках, можна зобразити однією результуючою матрицею повороту
=, (2.14)
де
Звідси (2.13) перепишеться у вигляді
= (2.15)
Як випливає з (2,8) , (2,13) множення замінені зсувами, що значно спрощує апаратну реалізацію обчислювачів.
Якщо відкинути з (2.7) масштабуючий коефіцієнт, то отримаємо спрощений ітераційний CORDIC. Ротаціії в такому випадку називають псевдоротаціями, а рівняння приймають вигляд
(2.16)
aбо в розгорнутому вигляді
(2.17)
Якщо провести всі ітерації за алгоритмом (2.17), то отримаємо:
== , (2.18)
, (2.19)
або
(2.20)
(2.21)
Тут - коефіцієнт деформації вектора.
Зв'язок між векторами (xm+1,ym+1)T та (x,y)T такий:
. (2.22)
Наступні рівняння (2.23)-(2.26) описують традиційний ітераційний CORDIC в режимі обертання (Rotation mode) для колової системи координат
(2.23)
(2.24)
Де , (2.25)
, (2.26)
Причому , ,.
Тут введена ще одна змінна для зрівноваження значення вхідного кута . При значення залишкового кута прямує до 0.
Для компенсації деформації вектора використовують початкове значення , як це випливає з (2.19) та (2.22).
Якщо прийняти , , то в результаті виконання (2.23)-(2.26) буде реалізовано функції синуса та косинуса за системою рівнянь (2.1).
Якщо ж початковий вектор задається координатами , , і при цьому зрівноважується значення змінної , тобто при значення прямує до 0, то це так званий векторний режим роботи (Vectoring mode).
Для колової системи координат рівняння тоді будуть мати вигляд
(2.27)
(2.28)
Де , (2.29)
(2.30)
У такому випадку обчислюються функції
(2.31)
Для уніфікації методу CORDIC пропонуємо використати такий варіант узагальнення для колової системи координат:
(2.32)
(2,33)
в режимі обертання (Rotation) R=1, V=0 та у векторному режимі (Vectoring) –навпаки R=0, V=1;
- оператор вибору напрямку обертання (вибирається з умови = для режиму обертання (Rotation) або = для векторного режиму (Vectoring) і приймає значення ) ;
;
Таблиця 1
Rotation
()
Vectoring ()
, ,
, ,
2.3. Ділення комплексних чисел методом Волдера
Як уже згадувалося в пункті 2.2, ділення комплексних чисел може бути обчислене за допомогою перетворення комплексних чисел з прямокутної системи координат у полярну, виконанні операцій, зазначених рівнянням (1.9), Потім провести перетворення результату назад в прямокутну систему координат. Для досягнення цього можна використовувати оператори ротації, що працюють в різних режимах.
Порівняльна діаграма операційного методу і методу Волдера
/ /
3.Висновок
В даній роботі було розглянено метод Волдера. І застосування його до ділення комплексних чисел. Даний метод є ефективним навіть при незначній кількості ітерацій, дуже швидкодійним і простим в реалізації. Єдиним недоліком є те, що даний метод працює в межах від до . Тому він не є універсальним. Для обчислення ділення комплексних чисел методом трансформації, це є один з найоптимальніших методів.
4.Список літератури
1. Fredric Edman Digital Hardware Aspects of Multiantenna Algorithms Lund 2006;
2. Volder J.E. The CORDIC trigonometric computing technique, IRE Trans. Electron. Comput 1959;
3.Walther, J.S. A unified algorithm for elementary functions. In Proceedings of AFIPS 1971 Spring Joint Computer Conference1971;
4. Аристов В.В. Функциональные макрооперации. Основы итерационных алгоритмов. –Киев: “Наукова думка”, 1992.-280с.;
5. Вікіпедія – вільна енциклопедія. http://uk.wikipedia.org/wiki/
6. F. Edman and V. Оwall, “Hardware Implementation of two Complex Divider
Architectures," Proceedings of RVK’05, Linkцping, Sweden, June 2005.
7. F. Edman and V. Оwall, “Fixed-point Implementation of a Robust Complex
Valued Divider Architecture,” Proceedings of ECCTD’05, Cork, Ireland, August 2005.
8. J. Volder, “Binary Computaion Algorithms for Coordinate Rotation and Function Generation,” Convair Report IAR 148 Aeroelectric Group, June 1956
9. Математика для школи http://formula.co.ua/complex.php
Додаток 1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Volder
{
class Komplex_Value_Division //Клас, в якому викликається метод
ділення комплексних чисел
{
static void Main(string[] args)
{
Cordic Prog = new Cordic();
Prog.Dilennja_K_Ch();
}
}
class Cordic
{
int M = 1, R, V;
double x_new, x_old, y_new, y_old, z_new, z_old;
double sign,X,Y,Z,a,b,c,d,Rez_X,Rez_Y;
int i, m;
public void Tup(double S) //Визначення типу ітераційного
процесу
{
if (S == 1) { R = 1; V = 0; pocatkovi_umovu(m); }
else if (S == 2) { R = 0; V = 1; pocatkovi_umovu(); }
}
public int Sigma(double ch) //Визначення сигма
{
if (ch < 0) return -1; else return 1;
}
public double K() //Обчислення K
{
double s = 1;
for (int I = 0; I < m; I++)
{
double k = Math.Sqrt(1 + Math.Pow(2, -2 * I));
s *= k;
}
return s;
}
public double Epsilon() // Обчислення 2^-i
{
return Math.Pow(2, -i);
}
public double Alfa(int I) //Обчислення арктангенсу від
Epsilon()
{
return Math.Atan(Epsilon());
}
public void pocatkovi_umovu(int n) //Початкову умови режиму
ротації
{
x_old = 1 / K();
y_old = 0;
z_old = Z;
}
public void pocatkovi_umovu() //Початкові умови векторного
режиму
{
z_old = 0;
}
public void Volder(int s) //Метод Волдера
{
m = 16;
Tup(s);
for (i = 0; i <= m; i++)
{
if (s == 1) sign = z_old;
else if (s == 2) sign = y_old;
x_new = x_old - M * (R - V) * Sigma(sign) * y_old * Epsilon(); //Ітераційний процес
y_new = y_old + (R - V) * Sigma(sign) * x_old * Epsilon();
z_new = z_old + (V - R) * Sigma(sign) * Alfa(i);
x_old = x_new;
y_old = y_new;
z_old = z_new;
if (s == 1) Console.WriteLine("sigma={0}\tX={1}\tY={2}", Sigma(sign) * Alfa(i), x_new, y_new);
else Console.WriteLine("sigma={0}\tRo={1}\tFi={2}",Sigma(sign) * Alfa(i), x_new, z_new);
}
double Kk = K();
X = x_new; Y = y_new; Z = z_new;
Console.ReadKey();
}
public void Dilennja_K_Ch() //Метод для ділення комплексних чисел
{
double X1,Y1,Z1,X2,Y2,Z2;
X1 = X2 = Y1 = Y2 = Z1 = Z2 = 0;
Console.WriteLine("Zadaj X"); //Зчитування комплексного
числа
x_old=a = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Zadaj Y");
y_old=b= Convert.ToDouble(Console.ReadLine());
Volder(2); //Виклик методу Волдера в векторному режимі
Z1 = Z; X1 = X;
Console.WriteLine("Zadaj X"); //Зчитування 2 комплексного
числа
x_old = c = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("Zadaj Y");
y_old = d = Convert.ToDouble(Console.ReadLine());
Volder(2); //Виклик методу волдера для 2 числа в
векторному режимі
Z2 = Z; X2 =X;
double Ro = X1 / X2;
Z = Z1 - Z2; //Діленя аргументів і віднімання кутів
X1 *= K(); Z1 *= 180 / Math.PI;
X2 *= K(); Z2 *= 180 / Math.PI;
Console.WriteLine("\nRo1={0}\tFi1={1}",X1 , Z1);
Console.WriteLine("Ro1={0}\tFi2={1}\n", X2, Z2);
Console.ReadKey();
Volder(1); //Виклик методу Волдера в режимі ротації
Rez_X = Ro * X;
Rez_Y = Ro * Y;
Console.WriteLine("\n X(Cordic)= {0}\t Y(cordic)= {1}", Rez_X, Rez_Y);
Console.ReadKey();
Pohubka(); //Виклик методу обчислення рохибки
}
public void Pohubka() //Метод обчислення похибки
{
double Re=0, Im=0;
double r1 = Math.Sqrt(a * a + b * b);
double r2 = Math.Sqrt(c*c+d*d);
Re = (a * c + b * d) / ((c * c) + (d * d));
Im = (b * c - a * d) / (c * c + d * d);
Console.WriteLine("Re(linijnuj)={0}\t Im(linijnuj)={1}", Re, Im);
Console.WriteLine("Poxubka Re={0}\t Poxubka Im={1}", Rez_X - Re, Rez_Y - Im);
Console.ReadKey();
}
}
}
Додаток 2
Приклад 1
Zadaj X
10
Zadaj Y
5
sigma=0,785398163397448 Ro=15 Fi=0,785398163397448
sigma=-0,463647609000806 Ro=17,5 Fi=0,321750554396642
sigma=0,244978663126864 Ro=18,125 Fi=0,566729217523506
sigma=-0,124354994546761 Ro=18,359375 Fi=0,442374222976745
sigma=0,0624188099959574 Ro=18,3837890625 Fi=0,504793032972702
sigma=-0,0312398334302683 Ro=18,4074401855469 Fi=0,473553199542434
sigma=-0,0156237286204768 Ro=18,4102892875671 Fi=0,457929470921957
sigma=0,00781234106010111 Ro=18,4111117385328 Fi=0,465741811982058
sigma=-0,00390623013196697 Ro=18,4112623504916 Fi=0,461835581850091
sigma=0,00195312251647882 Ro=18,4113275101474 Fi=0,46378870436657
sigma=-0,000976562189559319 Ro=18,4113300470156 Fi=0,462812142177011
sigma=0,000488281211194898 Ro=18,4113375577866 Fi=0,463300423388206
sigma=0,000244140620149362 Ro=18,4113391183705 Fi=0,463544564008355
sigma=0,00012207031189367 Ro=18,4113393499619 Fi=0,463666634320249
sigma=-6,10351561742088E-05 Ro=18,4113393713413 Fi=0,463605599164075
sigma=3,05175781155261E-05 Ro=18,4113393949454 Fi=0,46363611674219
sigma=1,52587890613158E-05 Ro=18,411339398174 Fi=0,463651375531251
Zadaj X
2
Zadaj Y
1
sigma=0,785398163397448 Ro=3 Fi=0,785398163397448
sigma=-0,463647609000806 Ro=3,5 Fi=0,321750554396642
sigma=0,244978663126864 Ro=3,625 Fi=0,566729217523506
sigma=-0,124354994546761 Ro=3,671875 Fi=0,442374222976745
sigma=0,0624188099959574 Ro=3,6767578125 Fi=0,504793032972702
sigma=-0,0312398334302683 Ro=3,68148803710938 Fi=0,473553199542434
sigma=-0,0156237286204768 Ro=3,68205785751343 Fi=0,457929470921957
sigma=0,00781234106010111 Ro=3,68222234770656 Fi=0,465741811982058
sigma=-0,00390623013196697 Ro=3,68225247009832 Fi=0,461835581850091
sigma=0,00195312251647882 Ro=3,68226550202948 Fi=0,46378870436657
sigma=-0,000976562189559319 Ro=3,68226600940311 Fi=0,462812142177011
sigma=0,000488281211194898 Ro=3,68226751155732 Fi=0,463300423388206
sigma=0,000244140620149362 Ro=3,6822678236741 Fi=0,463544564008355
sigma=0,00012207031189367 Ro=3,68226786999237 Fi=0,463666634320249
sigma=-6,10351561742088E-05 Ro=3,68226787426827 Fi=0,463605599164075
sigma=3,05175781155261E-05 Ro=3,68226787898908 Fi=0,46363611674219
sigma=1,52587890613158E-05 Ro=3,68226787963479 Fi=0,463651375531251
Ro1=30,3190620149854 Fi1=26,5652669833759
Ro1=6,06381240299707 Fi2=26,5652669833759
sigma=0,785398163397448 X=0,607252935103139 Y=0,607252935103139
sigma=-0,463647609000806 X=0,910879402654709 Y=0,30362646755157
sigma=-0,244978663126864 X=0,986786019542602 Y=0,0759066168878924
sigma=-0,124354994546761 X=0,996274346653588 Y=-0,0474416355549328
sigma=0,0624188099959574 X=0,999239448875771 Y=0,0148255111109165
sigma=-0,0312398334302683 X=0,999702746097988 Y=-0,0164007216664514
sigma=0,0156237286204768 X=0,999959007374026 Y=-0,000780366258670331
sigma=0,00781234106010111 X=0,999965103985422 Y=0,00703181348643925
sigma=-0,00390623013196697 X=0,999992572006853 Y=0,00312569979899619
sigma=-0,00195312251647882 X=0,999998676889273 Y=0,00117258930679531
sigma=-0,000976562189559319 X=0,999999821996018 Y=0,000196028098895627
sigma=-0,000488281211194898 X=0,999999917712863 Y=-0,000292253064188366
sigma=0,000244140620149362 X=0,999999989063709 Y=-4,81124592779992E-05
sigma=0,00012207031189367 X=0,999999994936812 Y=7,39578518870043E-05
sigma=-6,10351561742088E-05 X=0,999999999450841 Y=1,29226959460368E-05
sigma=-3,05175781155261E-05 X=0,99999999984521 Y=-1,75948821622042E-05
sigma=1,52587890613158E-05 X=1,00000000011369 Y=-2,33609310206612E-06
X(Cordic)= 5,00000000056843 Y(cordic)= -1,16804655103306E-05
Re(linijnuj)=5 Im(linijnuj)=0
Poxubka Re=5,6843418860808E-10 Poxubka Im=-1,16804655103306E-05
08.03.2012 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора