РОЗДІЛ 2
АНАЛІЗ ТЕОРЕТИКО-ЧИСЛОВИХ БАЗИСІВ ТА СИСТЕМ ЧИСЛЕННЯ, ЯКІ ВИКОРИСТОВУЮТЬСЯ ДЛЯ
ПОБУДОВИ ПРОЦЕСОРІВ
2.1. Базиси унітарних кусково-постійних функцій, Хаара та Крейга
Клас несинусоїдальних дискретних ортогональних функцій представляють функції:
унітарні, Радемахера, Хаара, Уолша, Крестенсона, Крейга, Галуа та інші [10, 13,
32, 115]. Теоретичною основою всіх кодів, що знайшли широке застосування в
обчислювальній техніці, є базиси ортогональних функцій.
Базис унітарних функцій можна представити [77, 115]:
Uni (n, q, i) =sign [sin ( (2n-1 i) Чp) ], (2.1)
де і = 0, 1, 2, ...,
n - порядковий номер функції; при цьому q=1/Т- параметр часу, час - формований
до інтервалу значення Т.
Даний базис широко використовується для проведення обчислень з високим рівнем
паралелізму операцій зокрема в матричних око процесорах, спецпроцесорах
кореляційної обробки даних, для процесорів швидкого перетворення Фур’є та в
аналого-цифрових перетворювачах [10, 43].
Функції Хаара Har (n, q, i) є набором вибіркових значень функцій Фур’є
(Радемахера) на і-му періоді і є теоретичною основою розряднопозиційних кодів
[23, 24, 92, 100]
Har (n, q, i) =sign [sin (2nЧiЧp) , q]. (2.2)
Даний базис широко використовується в обчислювальній техніці і реалізується
адресними дешифраторами та організації інтерактивної ітерфейсної взаємодії
оператора з комп’ютером на основі інформаційних вікон та «меню» [2].
Базис Крейга описується формулою [77, 115]:
Crg (n, q) =sign [sin ( (2n-1) ЧpЧq) ]. (2.3)
Базис Крейга породжує коди Лібова-Крейга, які мають більш компактну кодову
матрицю по відношенню до унітарного базису та базису Хаара і використовуються у
процесорах з двійковою арифметикою та засобах індикації цифрових даних [1, 2,
3]
2.2. Базиси Уолша та Радемахера
Повними ортогональними системами базисних кусково-постійних функцій є системи
Уолша. Функції Уолша утворюються шляхом перемноження функцій Радемахера [111,
118, 199]
, (2.4)
де .
По функціях Уолша можна здійснити розклад довільних сигналів в ряд Уолша-Фур’є,
і вони набуватимуть лише два значення (+1, -1) , тому зручні для обчислення.
Функції Уолша є періодичними з двійково-раціональним періодом, тому їх задають
на інтервалі N=2n, n=1, 2, …
Найбільше застосування знайшли системи функцій Уолша, відомі як системи Пелі,
Адамара і Хармута [103, 115].
Функція Уолша з номером n в системі Пелі задається добутком функцій Радемахера
з номерами k, різними розрядами у двійковому представленні n. При двійковому
представленні число n записується у вигляді
, nk=0 або 1,
де m – число розрядів.
Функції Уолша в системі Пелі визначаються як:
, (2.5)
де n – порядок функцій Уолша; rx – функція Радемахера.
Система Адамара отримується шляхом запису з системи Пелі розрядів двійкового
представлення номера функції Уолша n в зворотному порядку
. (2.6)
Комбінації nm-k+1 відповідають першим номерам функції Уолша.
Впорядкування функцій, представлених в системі Хармута, можна отримати
відповідні значення з системи Пелі шляхом представлення відповідного номера
функції Уолша в коді Грея. Даний код отримується послідовним сумуванням по
модулю двох сусідніх розрядів двійкового розкладу n, починаючи з молодшого
розряду.
Функції Радемахера є неповною системою ортонормованих функцій [87, 98]:
Rad (n, q) =sign [2npЧq]. (2.7)
За формулою (2.6) визначаються функції Радемахера для n=1, 2, 3...
Для n=0 функція Радемахера rad (0, t) =1 має вигляд одиничного імпульсу.
Формула (2.7) дозволяє порівняти функції Радемахера з синосуїдальними функціями
і дає наглядне представлення про процедуру їх одержання. Для практичних цілей
корисний рекурентний спосіб формування функцій Радемахера:
Rad (n, t) =rad (1, 2n-1Чt) , (2.8)
при вихідних значеннях rad (1, t) =1 для tО [0, 1/2], rad (1, t) =-1 для tО
[1/2, 1].
На відміну від повного набору синусоїд і косинусоїд, всі функції Радемахера
непарні. Це перешкоджає апроксимації їх за допомогою парних функцій, вони
утворюють неповний набір функцій, тому їх застосування обмежене.
2.3. Базис Крестенсона
Базис Крестенсона породжує систему залишкових класів (СЗК) згідно виразу [4-9]:
, (2.9)
де Р=; P1, P2, …Pi, …Pк – взаємопрості модулі,
bi –найменший невід'ємний залишок, bi=res Ni (mod Pi) ;
Bi-базисні вектори СЗК, які відповідають умові - де.
Базис Крестенсона породжує коди залишкових класів. Особливістю кодів системи
залишкових класів (СЗК) є наявність в кожному розряді числа іншого
взаємопростого модуля. Система залишкових класів відноситься до непозиційних
систем числення, що дозволяє проводити глибоке розпаралелення математичних
операцій шляхом виконання незалежних операцій по модулях Pi.
Елементарні арифметичні операції в базисі Крестенсона виконуються наступним
чином:
операнди X та Y в діапазоні [0, P-1] представлені відповідно залишками aі і bі
по модулю Рі при і=1, 2, ..., k [140-145].
Результати операцій додавання і множення X+Y та XЧY представляються
відповідними залишками gі і dі по модулях Рі,
X= (a1, a2, a3, …, ak) ,
Y= (b1, b2, b3, …, bk) ,
X+Y= (g1, g2, g3, …, gk) , (2.10)
XЧY= (d1, d2, d3, …, dk) , (2.11)
при цьому мають місце співвідношення:
X
При цьому в якості числа результату беруться відповідно
, (2.12)
. (2.13)
З цього можна визначити аналітику операції сумування
, (2.14)
для і=1, 2, 3, ...., k.
Для множення відповідно
Розглянемо виконання операції віднімання в СЗК коли операнди знаходяться в
діапазоні [0, P-1].
Операнди X та Y в діапазоні [0, P-1] представлені відповідно залишками aі і bі
по модулю Рі при і=1, 2, ..., k.
Результати