Імовірнісний паралельний суматор

Реферат: Імовірнісний паралельний суматор належить до галузі автоматики і вимірювальної техніки і може бути використаний в пристроях обробки дискретної інформації. Cуматор містить nрозрядний лічильник результату, n-розрядний регістр результату, K-розрядний лічильник кількості випробувань, генератор псевдовипадкових рівномірно розподілених чисел і мультиплексор на Log2Q керуючих входів. На керуючі входи мультиплексора надходить випадковий рівномірно розподілений сигнал з генератора псевдовипадкових рівномірних чисел, а на його інформаційні входи подаються Q імовірнісно наданих відображень підсумованих аргументів, вихід якого навантажений на вхід лічильника результату, що містить n = [log2K] розрядів, де K - кількість статистичних випробувань, паралельні виходи якого підключені до входів регістра результату аналогічної розрядності, на дозвільний вхід якого навантажений вихід лічильника кількості випробувань. На вхід "зсув вліво" регістра результату подається Log2Q імпульсів зсуву, а на синхронізуючий вхід лічильника кількості випробувань і генератора псевдовипадкових рівномірно розподілених чисел - синхронізуючий сигнал з генератора тактових імпульсів, при цьому вихід регістра результату є виходом пристрою. Технічним результатом є підвищення подальшої обробки отриманих результатів та зменшення апаратного об'єму пристрою. UA 103342 C2 (12) UA 103342 C2 UA 103342 C2 5 10 15 Винахід належить до галузі автоматики і вимірювальної техніки і може бути використаний в пристроях обробки дискретної інформації. Для виконання операції додавання двійкових чисел відомі двійкові суматори аналогічного призначення - послідовні [Угрюмов Е.П. Цифровая схемотехника: Учеб. пособие для вузов.-2-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2004. - С. 82-83 ил. 2.27-2.28] і паралельні [Угрюмов Е.П. Цифровая схемотехника: Учеб. пособие для вузов.-2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2004. - С. 85-86: ил. 2.29-2.30]. Основним недоліком першого прототипу є мала швидкодія, оскільки результат виконування операції підсумовування n-розрядних двійкових чисел буде отриманий тільки через n тактів. Недолік другого полягає в тому, що при високій швидкодії він має значний апаратний розмір. Так, для паралельного комбінаційного шістнадцятирозрядного суматора ця величина складає 181 логічний елемент Булєвого базису. Загалом, суть стохастичного або імовірнісного перетворення полягає в тому, що будь-якому значенню параметра перетворюваної величини можна привести відповідну ймовірність.      1 при xi  R tij yij   , 0 при xi  R tij  де xi - і-e значення перетворюваного сигналу X(t); R(tij) - j-e значення допоміжного випадкового сигналу R(t), змінного в інтервалі зміни X(t); i  1, N - число циклів перетворення сигналу Xt  ; 20 j  1, K - кількість статистичних випробувань кожного значення xi всередині тимчасового інтервалу ti  ti1  ti ; y ij 25 30 - значення ймовірнісного зображення сигналу xi з ряду Yi t   yi1; yi2;K yij;K yiK . При послідовному перетворенні аналогової або цифрової інформації в імовірнісну форму подання виникають методичні похибки, тим більші, чим менше інтервал імовірнісного перетворення. При роботі інформаційно-вимірювальних систем у реальному масштабі часу це приводить до помітного звуження їх частотного діапазону і, як наслідок, до обмеження сфер застосування ймовірнісних вимірювальних процесорів. Розв'язанням може слугувати використання паралельного ймовірнісного перетворення вимірюваного сигналу. Якщо значення логічної функції на виході логічного елемента, що реалізовує операцію диз'юнкції, в j-й момент часу позначити через Sj, то для Q доданків, наданих у вигляді ймовірнісних зображень, можна записати   Q S j  y1j  y2 j  K  yqj  K  yQj   yqj q1 Q, і диз'юнкція ймовірнісних зображень доданків набере вигляду Q 35 Q K  Yq t     y qj q1 q1 j1 . Проте виконувати додавання відповідно до останнього виразу не можна, оскільки   P Sj  1  40 45  Py q Q q1 j  1 1 . Вихід полягає в поперемінній подачі значень Yq(t) на відповідні входи схеми "АБО" через час t j  Q , t j де - період проходження тактових імпульсів; Q - кількість доданків. Тоді суму ймовірнісних відображень можна розглядати як частинне ймовірнісне відображення суми, що є послідовністю уj, на періоді Т, розділених σ. Групуючи члени ймовірнісного відображення за однаковою позицією на періоді Т, отримаємо ймовірнісне відображення диз'юнкції у вигляді St   y 01; y 02 ;K ; y 0k ; y t1;K ; y tk ;K ; y Q1 t1 ;K ; y Q1 tk .   1 UA 103342 C2 Математичне очікування (МО) випадкової функції S(t) можна розглядати як суму математичних очікувань ймовірнісних відображень незалежних і несумісних логічних змінних, тобто MSt   MY1t   MY2 t   K  MYQ t     y qjlPql   Py ql  1   PRq t   r  x q    Fx R . Q 2 Q Q q1l1 5 Q q1 q1 q1 q Для випадкових допоміжних рівномірно розподілених сигналів R(t) маємо   2   M Yq t    y qjlPl  P y qj  1  x q l1 і далі отримаємо MSt   Q  x q. q1 З іншого боку, оскільки при будь-якому, у тому числі і скільки завгодно малому ε 10 1 Q K    P   y qj  MSt     0 lim K k   q1j1    як оцінку для суми вхідних доданків отримаємо  15 20 25 30 35 40 45 Q K Q   x   1 y q qj  q1 K q1j1   , звідки випливає, що ймовірнісний суматор для підсумовування Q доданків є Q-вхідною логічною схемою "АБО" і (Q-1) пристроїв тимчасової затримки тривалістю т кожний. Таким чином, для двох доданків апаратний розмір імовірнісного суматора порівняно з детермінованим буде менший, орієнтовно в 90 разів. Основний недолік розглянутого імовірнісного суматора полягає в тому, що імовірнісне зображення суми утворюється зі стиском у часі. Суть пропонованого винаходу полягає у виконанні паралельної операції арифметичного додавання імовірнісне наданих операндів, що дозволяє значно прискорити отримання результатів у порівнянні з першим прототипом, або значно зменшити апаратний розмір пристрою у порівнянні з другим прототипом. Розв'язання технічної задачі досягається шляхом використання імовірнісної форми надання даних, у зв'язку з чим змінюється схема суматора. Технічний результат досягається шляхом заміни схеми комбінаційного суматора послідовного або паралельного типу на мультиплексор, що має Q інформаційних і Log 2Q керувальних входів, лічильник результату, регістр результату, лічильник кількості випробувань та генератор псевдовипадкових чисел. Функціональна схема імовірнісного паралельного суматора представлена на кресленні, де: MUX - мультиплексор; ЛР - лічильник результату; РгР - регістр результату; ЛКВ - лічильник кількості випробувань; ГПВЧ - генератор псевдовипадкових чисел. Апаратно, як імовірнісний суматор, може бути використаний мультиплексор (МПК), навантажений на вхід двійкового накопичувального лічильника результату (ЛР) з числом розрядів n = [log2K] паралельні виходи якого підключені на входи регістра результату (РгР) аналогічної розрядності, на дозвільний запис вхід якого подається сигнал переповнення з лічильника кількості випробувань (ЛКВ), який сигналізує про закінчення виконання K випробувань. Інформаційні входи мультиплексора є входами пристрою, на який подається Q імовірнісне наданих доданків, а керувальні входи підімкнені до виходів генератора псевдовипадкових чисел (ГПВЧ), значення на які подані у паралельному позиційному коді. Синхронізація всієї схеми здійснюється синхроімпульсами з генератора тактових імпульсів (ГТІ). При цьому ЛР, РгР, ГПВЧ на схемі виконують допоміжну роль. Пропонований імовірнісний паралельний суматор працює наступним чином. На інформаційні входи мультиплексора у паралельному коді побітно подаються імовірнісно представлені доданки. В свою чергу, адресні входи мультиплексора підключені до ГПВЧ, завдяки чому на кожному такті з виходу мультиплексора на ЛР буде подаватися одне з K 2 UA 103342 C2 5 значень вірогідного відображення доданку, номер якого в позиційному коді згенеровано ГПВЧ. ЛКВ підраховує кількість статистичних випробувань та при досягненні K випробувань видає дозвільний сигнал для запису значення з ЛР у РгР. Після цього, одержання результату виконання операції додавання в двійковому позиційному коді необхідно подати до РгР Log 2Q сигнал "зсуву вліво". Тоді значення логічної функції на виході мультиплексора в j-й момент часу буде рівне S j  y1j1j  y2 j2 j  K  yqjqj  K  yQjQj ,  qj де - значення логічної змінної (біта унітарного коду) на виході дешифратора. Визначимо вірогідність того, що Sj набуде одиничного значення:             P S j  1  P y1j  1 P 1j  1  K  P y qj  1 P  qj  1  10 Q q1 . У випадку, коли випадковий сигнал на керівних входах мультиплексора рівномірний, маємо 1 P qj  1  Q, і попередній вираз перепишеться у вигляді P Sj  1  15  Py qj  1Pqj  1   1 Q 1 Q  P y qj  1  Q  Fx q Rq Q q1 q1   . При лінійному ймовірнісному перетворенні вираз спроститься:  xq  Q  PS j  1 Q q1 Визначимо МО випадкової величини Sj, здатної набувати тільки двох можливих значень - 0 або 1    2  M S j   s jlPl P S j1  1 20 l1 . Як оцінку МО, з урахуванням висновку з теореми Чебишева, приймемо 1 MS j   K  S j K j1 , звідки отримаємо остаточний вираз для обчислення суми імовірнісних зображень   25 30 35 40  K K Q Q    x S   Q S  Q   y  q j  j qj qj  q1 K j1 K j1q1   . Таким чином, для відновлення результату в цифрову форму необхідно після проходження K випробувань переписати уміст ЛР в РгР і виконати в ньому операцію зсуву вліво на Log 2Q розрядів. Синтезована таким чином структура має значно менший, приблизно в 30 разів, апаратний розмір, ніж цифровий багаторозрядний суматор. ФОРМУЛА ВИНАХОДУ Імовірнісний паралельний суматор, що містить n-розрядний лічильник результату, n-розрядний регістр результату, K-розрядний лічильник кількості випробувань, який відрізняється тим, що додатково містить генератор псевдовипадкових рівномірно розподілених чисел і мультиплексор на Log2Q керуючих входів, на які надходить випадковий рівномірно розподілений сигнал з генератора псевдовипадкових рівномірних чисел, а на інформаційні входи мультиплексора подаються Q імовірнісно наданих відображень підсумованих аргументів, вихід якого навантажений на вхід лічильника результату, що містить n = [log2K] розрядів, де K - кількість статистичних випробувань, паралельні виходи якого підключені до входів регістра результату аналогічної розрядності, на дозвільний вхід якого навантажений вихід лічильника кількості випробувань, на вхід "зсув вліво" регістра результату подається Log2Q імпульсів зсуву, а на синхронізуючий вхід лічильника кількості випробувань і генератора псевдовипадкових рівномірно розподілених чисел - синхронізуючий сигнал з генератора тактових імпульсів, при цьому вихід регістра результату є виходом пристрою. 3 UA 103342 C2 Комп’ютерна верстка Л. Бурлак Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4