Поліноміальні моделі цифрових пристроїв

Матеріал з testwiki
Версія від 14:03, 9 жовтня 2022, створена imported>Ата (оформлення)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку

Шаблон:Вікіфікувати Поліноміальна модель цифрового пристрою — це аналітичний вираз у вигляді поліному, який однозначно відображає алгоритм перетворення вхідних даних у вихідні.

Наприклад: Задана таблиця 1 цифрового пристрою, що реалізує функцію F(Xi)(вихідні дані). Вхідними даними є аргумент X, що визначає номер рядка таблиці, представлений у вигляді натурального числа у десятковій системі числення (X10 = 0, 1, 2, …, m). Для синтезу поліноміальної моделі цифрового пристрою використовують двозначну або тризначну систему числення (тризначна система числення використовувалась в ЭОМ «Сетунь»). В цьому випадку аргумент X замінюють кодом числа X в одній із вказаних систем числення зі змінними xi, які однозначно визначають X10 =(xnxix1)2=k=0n1xk+1qk, де:

  • q — основа системи числення,
  • xk+1 — значення xk+1 розряду,

Таблиця 1.

X xn . xi . x1 F(xi)
0 0 . 0 . 0 F(0)
1 0 . 0 . 1 F(1)
. . . . . . .
k xkn . xki . xk1 F(k)
. . . . . . .
m xmn . xmi . xm1 F(m)

Задача створення аналітичного виразу (математичної моделі) у вигляді полінома F(xi) від незалежних змінних xi), зводиться до визначення вигляду та коефіцієнтів цього полінома, що в свою чергу, залежить від обраної системи числення.

Поліноміальну математичну модель F(xi) шукають у вигляді скалярного добутку двох векторів — bt та P(X) (де: bt — транспонований вектор b).

Компонентами вектора bt є коефіцієнти апроксимуючого полінома.

Нелінійна частина апроксимуючого полінома P(X) залежить від обраної системи числення. Компонентами вектора P(X) для двозначної системи числення є одночлени алгебраїчного полінома, отриманого шляхом перемноження простих лінійних функцій для одного розряду: P(X)=(1+x1)(1+x2)(1+x3)…(1+xi)=1 + x1 + x2 + x1 x2 + x3 + x1 x3 + x2 x3 + x1 x2 x3… до тих пір, поки не виконається співвідношення 2i = m (m — кількість рядків в таблиці 1).

Компонентами вектора P(X) для тризначної системи числення є одночлени алгебраїчного полінома, отриманого шляхом добутку простих квадратних функцій для одного розряду: P(X)=(1 + x1 + x12)(1+ x2 + x22)(1 + x3 + x32)…(1 + xi + xi2) = 1 + x1 + x12 + x2 + x1 x2 + x12 x2 + x22 + x1 x22 + x12 x22 + x3 + x1 x3 + x12 x3 + x2 x3 + x1 x22 x3 + x12 x2 x3 + x22 x3 + x1 x22 x3 + x12 x22 x3 + x32 + x1 x32 + x12 x32 + x2 x32 + x1 x2 x32 + x12 x2 x32 + x22 x32 + x1 x22 x32 + x12 x22 x32… до тих пір, поки не виконається співвідношення 3i = m.

Апроксимуючий поліном прийме вигляд:

F(xi)=bt*P(X)=:[b0b1...bj...bm]×[p0=1p1=x1...pj...pm]= b0 + b1 x1 + …

Задача формування математичної моделі зводиться до визначення компонент bj (j= 0,1, …m) вектора b.

Двозначна система числення

Алгебраїчний поліном

Алгоритм визначення коефіцієнтів bj полінома F(xi). Вхідним виразом служить матриця C1: C1=[1011].

Подальші матриці будуються за рекурсивною процедурою: Ci=[Ci10Ci1Ci1] до тих пір, поки не виконається співвідношення 2i = m

Для знаходження вектора b, що складається з компонент шуканих коефіцієнтів bj, необхідно перемножити матрицю Ci на вектор, що складається з компонент правого стовпчика F(xi) таблиці 1:

b = Ci * F(xi)

Поліном Жегалкіна має той же вигляд, що і алгебраїчний поліном. Відмінність полягає в тому, що операції алгебраїчного множення та суми замінюються на логічні функції кон'юнкції та суми по mod.2 (виключної диз'юнкції).

Вхідним виразом служить матриця C1:

C1=[1011]

Подальші матриці будуються відповідно за рекурсивною процедурою:

Ci=[Ci10Ci1Ci1]

до тих пір, поки не виконається співвідношення 2i=m .

Для знаходження вектора b, необхідно перемножити матрицю Ci на вектор, що складається з компонент правого стовпчика таблиці 1 з урахуванням підсумовування часткових добутків по mod.2: b = [(Ci)*F(xi)]mod2.

Тризначна система числення

Алгебраїчний поліном.

Тризначна симетрична система числення (-1,0,1)

Матриця C1 для симетричної системи числення має вигляд:

C1= [0100,500,50,510,5]    

Наступні матриці будуються відповідно до рекурсивних співвідношень:

Ci= [0Ci100,5*Ci100,5*Ci10,5*Ci1Ci10,5*Ci1]    

Вектор b знаходять у відповідності з виразом: b=[(Ci)*F(xi)], а поліноміальну математичну модель згідно з виразом:

F(xi) = bt * P(X)

Тризначна несиметрична система числення (0,1,2)

Алгоритм той же, що і для симетричної системи числення, відмінність тільки в матрицях:

C1= [1001,520,50,510,5]    

Ci= [Ci1001,5*Ci12*Ci10,5*Ci10,5*Ci1Ci10,5*Ci1]    

b=[(Ci)*F(xi)];

F(xi) = bt * P(X).

Модифікація полінома Жегалкіна для тризначної системи числення

Модифікований поліном Жегалкіна має той же вигляд, що і алгебраїчний поліном для тризначної системи числення. Відмінність полягає в тому, що алгебраїчна сума замінюється на логічну функції суми по mod.3. Операція множення і зведення в квадрат аргументів xi відповідають алгебраїчному множенню і зведенню аргументу в квадрат:

Існування і єдиність представлення модифікованим поліномом Жегалкіна будь-якої функції тризначної логіки аналогічно доказу для двозначної логіки.

Тризначна симетрична система числення (-1,0,1)

Алгоритм визначення коефіцієнтів bj (j= 0,1, …m) аналогічний визначенню цих коефіцієнтів для алгебраїчного полінома в симетричній системі числення (-1,0,1). Відмінність у вхідних матрицях. Матриця C1 для симетричної системи числення (-1,0.1) має вигляд:

C1= [010101111]    .

Рекурсивне співвідношення для наступних матриць: Ci= [0Ci10Ci10Ci1Ci1Ci1Ci1]    .

Вектор b шукаємо у відповідності з виразом: b=[(Ci)*F(xi)]mod3, а поліноміальну математичну модель згідно з виразом: F(xi) = (bt * P(X))mod.3.

Тризначна несиметрична система числення (0,1,2)

Матриця C1 для несиметричною системи числення (0,1,2):

C1= [100021222]    

Рекурсивне співвідношення для наступних матриць: Ci= [Ci10002*Ci1Ci12*Ci12*Ci12*Ci1]    

b=[(Ci)*F(xi)]mod3;

F(xi) = (bt * P(X))mod.3.

Приклади

Двозначна система числення. Алгебраїчний поліном

Задана таблиця 2. Визначити компоненти bj (j= 0,1, …7) вектора b поліноміальної математичної моделі F(xi)=bt * P(X):

Таблиця 2.

x3 x2 x1 F(xi)
0 0 0 F(0)=0
0 0 1 F(1)=1
0 1 0 F(2)=4
0 1 1 F(3)=9
1 0 0 F(4)=16
1 0 1 F(5)=25
1 1 0 F(6)=36
1 1 1 F(7)=49

Шаблон:- Будуються матриці C2 та C3:

C2=[C10C1C1]=[1000110010101111]
C3=[C20C2C2]=[1000000011000000101000001111000010001000110011001010101011111111]

Шуканий вектор b = C3 * F(xi)=

[1000000011000000101000001111000010001000110011001010101011111111]×[014916253649]=[0144168160]

Поліноміальна математична модель:

F(xi) = bt * P(X)= [0144168160]×[1x1x2x1*x2x3x1*x3x2*x3x1*x2*x3]= x1 + 4*x2 + 4*x1*x2 + 16*x3 + 8*x1*x3 + 16*x2*x3

Якщо коефіцієнти bj замінити кодами чисел у двозначній системі числення, то отримаємо вектор F(xi), який встановлює зв'язок між розрядами аргумента xi і функції f(k)(k=1,2,…,6):

F(k)=bt * P(X) =

[0000101000000100001100000000000001000000]×[1x1x2x1*x2x3x1*x3x2*x3x1*x2*x3]=[f6f5f4f3f2f1]=[0x3+x2*x3x1*x3x2+x1*x20x1]

Принципова схема пристрою для зведення чисел у квадрат, згідно отриманої поліноміальної моделі, зображена на мал.1:

Мал. 1. Принципова схема пристрою для зведення чисел в квадрат

Шаблон:-

Двозначна система числення. Алгебра Жегалкіна

Задана таблиця 3. Визначити компоненти bj (j= 0,1, …7) вектора b для полінома Жегалкіна:

Таблиця 3.

x3 x2 x1 F(xi)
0 0 0 F0=0
0 0 1 F1=1
0 1 0 F2=0
0 1 1 F3=1
1 0 0 F4=0
1 0 1 F5=0
1 1 0 F6=1
1 1 1 F7=1

Шаблон:- Будуються матриці C2 та C3:

C2=[C10C1C1]=[1000110010101111]


C3=[C20C2C2]=[1000000011000000101000001111000010001000110011001010101011111111]

Шуканий вектор b: b=[1000000011000000101000001111000010001000110011001010101011111111]×[01010011]=[F0(F0+F1)mod.2(F0+F2)mod.2(F0+F1+F2+F3)mod.2(F0+F4)mod.2(F0+F1+F4+F5)mod.2(F0+F2+F4+F6)mod.2(F0+F1+F2+F3+F4+F5+F6+F7)mod.2]=[01000110]

Поліноміальна математична модель: F(xi)=bt*P(X) =[01000110]×[1x1x2x1*x2x3x1*x3x2*x3x1*x2*x3]=[ x1 + x1 * x3 + x2 * x3]mod.2.

Таблиця 3 реалізує функцію D-тригера. Змінним xi відповідають найменування входів і виходів: x1 = Qt; x2 = D; x3 = C; F(xi) = Qt+1.

Алгоритм функціонування D-тригера описується формулою:Qt+1 = [Qt * (C + 1) + D * C)]mod.2.

Для зменшення обсягу обчислень застосовують властивості рекурсивної процедури побудови матриці Cj. У даному випадку знаходять перші значення коефіцієнтів bj1 (j1 = 0,1, 2, 3) застосовуючи співвідношення: bj1 = [(C2)*F(xi1)]mod2. . Останні коефіцієнти bj2 (j2= 4,5, 6, 7) обчислюються за формулою: bj2=[bj1 + (C2)*F(xi2)]mod2.

Значення функції F(k) може бути у вигляді багаторозрядних десяткових чисел. В цьому випадку необхідно записати ці числа у двозначній системі числення і операцію суми по mod.2 проводити порозрядно.

Тризначна симетрична система числення (-1;0;1). Алгебраїчний поліном

Задана таблиця 4. Визначити компоненти bj (j= 0,1, …8) вектора b для алгебраїчного полінома:

Таблиця 4.

x2 x1 F(xi)
-1 -1 1
-1 0 -1
-1 1 0
0 -1 -1
0 0 0
0 1 1
1 -1 0
1 0 1
1 1 -1

Шаблон:- Будується матриця C2:

C2=[0C100,5*C100,5*C10,5*C1C10,5*C1]=[0000100000000,500,50000000,510,500000,5000000,500,2500,250000,2500,250,250,50,250000,250,50,2500,5001000,500,2500,250,500,50,2500,250,250,50,250,510,50,250,50,25]

Шуканий вектор b = C2 * F(xi)= =[0000100000000,500,50000000,510,500000,5000000,500,2500,250000,2500,250,250,50,250000,250,50,2500,5001000,500,2500,250,500,50,2500,250,250,50,250,510,50,250,50,25]×[110101011]=[010101,501,50]

Поліноміальна математична модель: F(xi) = bt * P(X)= [010101,501,50]×[1x1x12x2x1*x2x12*x2x22x1*x22x12*x12]= x1 + x2 — 1,5*x12*x2 — 1,5*x1*x22

реалізує функцію F(xi)=(x1 + x2)mod.3.

Тризначна симетрична система числення (-1;0;1). Модифікований поліном Жегалкіна

Задана таблиця 5. Для синтеза математичної моделі необхідно визначити компоненти bj (j= 0, 1, …, 26) вектора b для модифікованого поліному Жегалкіна. Поліноміальна модель F(xi) знаходиться як скалярний добуток двох векторів — bt та P(X).

Таблиця 5.

F(xi) -1 0 1 -1 0 1 -1 -1 -1 -1 0 1 -1 0 1 0 0 0 -1 0 1 -1 0 1 1 1 1
x3 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
x2 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1
x1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1

Шаблон:- Побудувавши матрицю C3 за рекурсивними співвідношеннями:

C1=[010101111];

C2=[0C10C10C1C1C1C1];

C3=[0C20C20C2C2C2C2]

розраховується вектор b: b = [C3 * F(xi)]mod.3.

Визначивши компоненти вектора b отримаємо поліноміальну математичну модель модифікованого полінома Жегалкіна:

F(xi)= (x1 + x1 * x2 + x1 * x22 — x2 * x3 — x22 * x3)mod.3.

Таблиця 5 реалізує функцію D-тригера. Змінним xi відповідають найменування входів і виходів: x1= Qt; x2= C; x3= D; F(xi)= Qt+1.

Алгоритм функціонування D-тригера описується формулою:

Qt+1 = [Qt * (1 + C + C2) — D * (С + C2)]mod.3

Див. також

Література

  1. Пухов Г. Е., Евдокимов В. Ф., Синьков М. В. «Разрядно-аналоговые вычислительные системы». -М., «Сов. радио», 1978.
  2. Плющ Ю. А. Аппаратурная реализация функционального преобразования в специализированных вычислительных устройствах/ «Гибридные вычислительные машины». -К., «Наукова думка», 1979.
  3. V. Evdokimov, Y. Plushch, A. Chemeris «SYNTHESIS OF DISCRETE DEVICES ON BASIS OF BIT TRANSFORMATIONS»/ ROCZNIKI INFORMATYKI STOSOWANEJ WYDZIALU INFORMATYKI POLITECHNIKI SZCZECINSKIEJ NR 3. Szczecin, 2002.
  4. Автор. свид. СССР № 631918. МКИ3 G 06 f 15/32. БИ № 32, 30.08.79г.