Цю статтю треба для відповідності Вікіпедії. (січень 2014) |
Поліноміальна модель цифрового пристрою — це аналітичний вираз у вигляді поліному, який однозначно відображає алгоритм перетворення вхідних даних у вихідні.
Наприклад: Задана таблиця 1 цифрового пристрою, що реалізує функцію F(Xi)(вихідні дані). Вхідними даними є аргумент X, що визначає номер рядка таблиці, представлений у вигляді натурального числа у десятковій системі числення (X10 = 0, 1, 2, …, m). Для синтезу поліноміальної моделі цифрового пристрою використовують двозначну або тризначну систему числення (тризначна система числення використовувалась в ЭОМ «Сетунь»). В цьому випадку аргумент X замінюють кодом числа X в одній із вказаних систем числення зі змінними xi, які однозначно визначають X10 = де:
- 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 + + )(1+ + )(1 + + )…(1 + + ) = 1 + + + + + + + + + + + + + + + + + + + + + + + + + + … до тих пір, поки не виконається співвідношення 3i = m.
Апроксимуючий поліном прийме вигляд:
F(xi)=bt*P(X)=: + + …
Задача формування математичної моделі зводиться до визначення компонент bj (j= 0,1, …m) вектора b.
Двозначна система числення
Алгебраїчний поліном
Алгоритм визначення коефіцієнтів bj полінома F(xi). Вхідним виразом служить матриця C1: .
Подальші матриці будуються за рекурсивною процедурою: до тих пір, поки не виконається співвідношення 2i = m
Для знаходження вектора b, що складається з компонент шуканих коефіцієнтів bj, необхідно перемножити матрицю Ci на вектор, що складається з компонент правого стовпчика F(xi) таблиці 1:
b = Ci * F(xi)
Поліном Жегалкіна має той же вигляд, що і алгебраїчний поліном. Відмінність полягає в тому, що операції алгебраїчного множення та суми замінюються на логічні функції кон'юнкції та суми по mod.2 (виключної диз'юнкції).
Вхідним виразом служить матриця C1:
Подальші матриці будуються відповідно за рекурсивною процедурою:
до тих пір, поки не виконається співвідношення 2i=m .
Для знаходження вектора b, необхідно перемножити матрицю Ci на вектор, що складається з компонент правого стовпчика таблиці 1 з урахуванням підсумовування часткових добутків по mod.2: b = [(Ci)*F(xi)]mod2.
Тризначна система числення
Алгебраїчний поліном.
Тризначна симетрична система числення (-1,0,1)
Матриця C1 для симетричної системи числення має вигляд:
C1=
Наступні матриці будуються відповідно до рекурсивних співвідношень:
Ci=
Вектор b знаходять у відповідності з виразом: b=[(Ci)*F(xi)], а поліноміальну математичну модель згідно з виразом:
F(xi) = bt * P(X)
Тризначна несиметрична система числення (0,1,2)
Алгоритм той же, що і для симетричної системи числення, відмінність тільки в матрицях:
C1=
Ci=
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= .
Рекурсивне співвідношення для наступних матриць: Ci= .
Вектор b шукаємо у відповідності з виразом: b=[(Ci)*F(xi)]mod3, а поліноміальну математичну модель згідно з виразом: F(xi) = (bt * P(X))mod.3.
Тризначна несиметрична система числення (0,1,2)
Матриця C1 для несиметричною системи числення (0,1,2):
C1=
Рекурсивне співвідношення для наступних матриць: Ci=
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:
Шуканий вектор b = C3 * F(xi)=
Поліноміальна математична модель:
F(xi) = bt * P(X)= + 4* + 4** + 16* + 8** + 16**
Якщо коефіцієнти bj замінити кодами чисел у двозначній системі числення, то отримаємо вектор F(xi), який встановлює зв'язок між розрядами аргумента xi і функції f(k)(k=1,2,…,6):
F(k)=bt * P(X) =
Принципова схема пристрою для зведення чисел у квадрат, згідно отриманої поліноміальної моделі, зображена на мал.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:
Шуканий вектор b:
Поліноміальна математична модель: F(xi)=bt*P(X) = + * + * ]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:
Шуканий вектор b = C2 * F(xi)=
Поліноміальна математична модель: F(xi) = bt * P(X)= + — —
реалізує функцію F(xi)=( + )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 за рекурсивними співвідношеннями:
;
;
розраховується вектор b: b = [C3 * F(xi)]mod.3.
Визначивши компоненти вектора b отримаємо поліноміальну математичну модель модифікованого полінома Жегалкіна:
F(xi)= ( + * + * — * — * )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
Див. також
Література
- Пухов Г. Е., Евдокимов В. Ф., Синьков М. В. «Разрядно-аналоговые вычислительные системы». -М., «Сов. радио», 1978.
- Плющ Ю. А. Аппаратурная реализация функционального преобразования в специализированных вычислительных устройствах/ «Гибридные вычислительные машины». -К., «Наукова думка», 1979.
- 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.
- Автор. свид. СССР № 631918. МКИ3 G 06 f 15/32. БИ № 32, 30.08.79г.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti sichen 2014 Polinomialna model cifrovogo pristroyu ce analitichnij viraz u viglyadi polinomu yakij odnoznachno vidobrazhaye algoritm peretvorennya vhidnih danih u vihidni Napriklad Zadana tablicya 1 cifrovogo pristroyu sho realizuye funkciyu F Xi vihidni dani Vhidnimi danimi ye argument X sho viznachaye nomer ryadka tablici predstavlenij u viglyadi naturalnogo chisla u desyatkovij sistemi chislennya X10 0 1 2 m Dlya sintezu polinomialnoyi modeli cifrovogo pristroyu vikoristovuyut dvoznachnu abo triznachnu sistemu chislennya triznachna sistema chislennya vikoristovuvalas v EOM Setun V comu vipadku argument X zaminyuyut kodom chisla X v odnij iz vkazanih sistem chislennya zi zminnimi xi yaki odnoznachno viznachayut X10 x n x i x 1 2 k 0 n 1 x k 1 q k displaystyle x n dots x i dots x 1 2 sum k 0 n 1 x k 1 q k de q osnova sistemi chislennya xk 1 znachennya xk 1 rozryadu Tablicya 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 Zadacha stvorennya analitichnogo virazu matematichnoyi modeli u viglyadi polinoma F xi vid nezalezhnih zminnih xi zvoditsya do viznachennya viglyadu ta koeficiyentiv cogo polinoma sho v svoyu chergu zalezhit vid obranoyi sistemi chislennya Polinomialnu matematichnu model F xi shukayut u viglyadi skalyarnogo dobutku dvoh vektoriv bt ta P X de bt transponovanij vektor b Komponentami vektora bt ye koeficiyenti aproksimuyuchogo polinoma Nelinijna chastina aproksimuyuchogo polinoma P X zalezhit vid obranoyi sistemi chislennya Komponentami vektora P X dlya dvoznachnoyi sistemi chislennya ye odnochleni algebrayichnogo polinoma otrimanogo shlyahom peremnozhennya prostih linijnih funkcij dlya odnogo rozryadu P X 1 x1 1 x2 1 x3 1 xi 1 x1 x2 x1 x2 x3 x1 x3 x2 x3 x1 x2 x3 do tih pir poki ne vikonayetsya spivvidnoshennya 2i m m kilkist ryadkiv v tablici 1 Komponentami vektora P X dlya triznachnoyi sistemi chislennya ye odnochleni algebrayichnogo polinoma otrimanogo shlyahom dobutku prostih kvadratnih funkcij dlya odnogo rozryadu P X 1 x 1 displaystyle x 1 x 1 2 displaystyle x 1 2 1 x 2 displaystyle x 2 x 2 2 displaystyle x 2 2 1 x 3 displaystyle x 3 x 3 2 displaystyle x 3 2 1 x i displaystyle x i x i 2 displaystyle x i 2 1 x 1 displaystyle x 1 x 1 2 displaystyle x 1 2 x 2 displaystyle x 2 x 1 displaystyle x 1 x 2 displaystyle x 2 x 1 2 displaystyle x 1 2 x 2 displaystyle x 2 x 2 2 displaystyle x 2 2 x 1 displaystyle x 1 x 2 2 displaystyle x 2 2 x 1 2 displaystyle x 1 2 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 x 1 displaystyle x 1 x 3 displaystyle x 3 x 1 2 displaystyle x 1 2 x 3 displaystyle x 3 x 2 displaystyle x 2 x 3 displaystyle x 3 x 1 displaystyle x 1 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 x 1 2 displaystyle x 1 2 x 2 displaystyle x 2 x 3 displaystyle x 3 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 x 1 displaystyle x 1 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 x 1 2 displaystyle x 1 2 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 x 3 2 displaystyle x 3 2 x 1 displaystyle x 1 x 3 2 displaystyle x 3 2 x 1 2 displaystyle x 1 2 x 3 2 displaystyle x 3 2 x 2 displaystyle x 2 x 3 2 displaystyle x 3 2 x 1 displaystyle x 1 x 2 displaystyle x 2 x 3 2 displaystyle x 3 2 x 1 2 displaystyle x 1 2 x 2 displaystyle x 2 x 3 2 displaystyle x 3 2 x 2 2 displaystyle x 2 2 x 3 2 displaystyle x 3 2 x 1 displaystyle x 1 x 2 2 displaystyle x 2 2 x 3 2 displaystyle x 3 2 x 1 2 displaystyle x 1 2 x 2 2 displaystyle x 2 2 x 3 2 displaystyle x 3 2 do tih pir poki ne vikonayetsya spivvidnoshennya 3i m Aproksimuyuchij polinom prijme viglyad F xi bt P X b 0 b 1 b j b m p 0 1 p 1 x 1 p j p m displaystyle begin bmatrix b 0 amp b 1 amp amp b j amp amp b m end bmatrix times begin bmatrix p 0 1 p 1 x 1 p j p m end bmatrix b 0 displaystyle b 0 b 1 displaystyle b 1 x 1 displaystyle x 1 Zadacha formuvannya matematichnoyi modeli zvoditsya do viznachennya komponent bj j 0 1 m vektora b Dvoznachna sistema chislennyaAlgebrayichnij polinom Algoritm viznachennya koeficiyentiv bj polinoma F xi Vhidnim virazom sluzhit matricya C1 C 1 1 0 1 1 displaystyle C 1 begin bmatrix 1 amp 0 1 amp 1 end bmatrix Podalshi matrici buduyutsya za rekursivnoyu proceduroyu C i C i 1 0 C i 1 C i 1 displaystyle C i begin bmatrix C i 1 amp 0 C i 1 amp C i 1 end bmatrix do tih pir poki ne vikonayetsya spivvidnoshennya 2i m Dlya znahodzhennya vektora b sho skladayetsya z komponent shukanih koeficiyentiv bj neobhidno peremnozhiti matricyu Ci na vektor sho skladayetsya z komponent pravogo stovpchika F xi tablici 1 b Ci F xi Polinom Zhegalkina Polinom Zhegalkina maye toj zhe viglyad sho i algebrayichnij polinom Vidminnist polyagaye v tomu sho operaciyi algebrayichnogo mnozhennya ta sumi zaminyuyutsya na logichni funkciyi kon yunkciyi ta sumi po mod 2 viklyuchnoyi diz yunkciyi Vhidnim virazom sluzhit matricya C1 C 1 1 0 1 1 displaystyle C 1 begin bmatrix 1 amp 0 1 amp 1 end bmatrix Podalshi matrici buduyutsya vidpovidno za rekursivnoyu proceduroyu C i C i 1 0 C i 1 C i 1 displaystyle C i begin bmatrix C i 1 amp 0 C i 1 amp C i 1 end bmatrix do tih pir poki ne vikonayetsya spivvidnoshennya 2i m Dlya znahodzhennya vektora b neobhidno peremnozhiti matricyu Ci na vektor sho skladayetsya z komponent pravogo stovpchika tablici 1 z urahuvannyam pidsumovuvannya chastkovih dobutkiv po mod 2 b Ci F xi mod2 Triznachna sistema chislennyaAlgebrayichnij polinom Triznachna simetrichna sistema chislennya 1 0 1 Matricya C1 dlya simetrichnoyi sistemi chislennya maye viglyad C1 0 1 0 0 5 0 0 5 0 5 1 0 5 displaystyle begin bmatrix 0 amp 1 amp 0 0 5 amp 0 amp 0 5 0 5 amp 1 amp 0 5 end bmatrix Nastupni matrici buduyutsya vidpovidno do rekursivnih spivvidnoshen Ci 0 C i 1 0 0 5 C i 1 0 0 5 C i 1 0 5 C i 1 C i 1 0 5 C i 1 displaystyle begin bmatrix 0 amp C i 1 amp 0 0 5 C i 1 amp 0 amp 0 5 C i 1 0 5 C i 1 amp C i 1 amp 0 5 C i 1 end bmatrix Vektor b znahodyat u vidpovidnosti z virazom b Ci F xi a polinomialnu matematichnu model zgidno z virazom F xi bt P X Triznachna nesimetrichna sistema chislennya 0 1 2 Algoritm toj zhe sho i dlya simetrichnoyi sistemi chislennya vidminnist tilki v matricyah C1 1 0 0 1 5 2 0 5 0 5 1 0 5 displaystyle begin bmatrix 1 amp 0 amp 0 1 5 amp 2 amp 0 5 0 5 amp 1 amp 0 5 end bmatrix Ci C i 1 0 0 1 5 C i 1 2 C i 1 0 5 C i 1 0 5 C i 1 C i 1 0 5 C i 1 displaystyle begin bmatrix C i 1 amp 0 amp 0 1 5 C i 1 amp 2 C i 1 amp 0 5 C i 1 0 5 C i 1 amp C i 1 amp 0 5 C i 1 end bmatrix b Ci F xi F xi bt P X Modifikaciya polinoma Zhegalkina dlya triznachnoyi sistemi chislennyaModifikovanij polinom Zhegalkina maye toj zhe viglyad sho i algebrayichnij polinom dlya triznachnoyi sistemi chislennya Vidminnist polyagaye v tomu sho algebrayichna suma zaminyuyetsya na logichnu funkciyi sumi po mod 3 Operaciya mnozhennya i zvedennya v kvadrat argumentiv xi vidpovidayut algebrayichnomu mnozhennyu i zvedennyu argumentu v kvadrat Isnuvannya i yedinist predstavlennya modifikovanim polinomom Zhegalkina bud yakoyi funkciyi triznachnoyi logiki analogichno dokazu dlya dvoznachnoyi logiki Triznachna simetrichna sistema chislennya 1 0 1 Algoritm viznachennya koeficiyentiv bj j 0 1 m analogichnij viznachennyu cih koeficiyentiv dlya algebrayichnogo polinoma v simetrichnij sistemi chislennya 1 0 1 Vidminnist u vhidnih matricyah Matricya C1 dlya simetrichnoyi sistemi chislennya 1 0 1 maye viglyad C1 0 1 0 1 0 1 1 1 1 displaystyle begin bmatrix 0 amp 1 amp 0 1 amp 0 amp 1 1 amp 1 amp 1 end bmatrix Rekursivne spivvidnoshennya dlya nastupnih matric Ci 0 C i 1 0 C i 1 0 C i 1 C i 1 C i 1 C i 1 displaystyle begin bmatrix 0 amp C i 1 amp 0 C i 1 amp 0 amp C i 1 C i 1 amp C i 1 amp C i 1 end bmatrix Vektor b shukayemo u vidpovidnosti z virazom b Ci F xi mod3 a polinomialnu matematichnu model zgidno z virazom F xi bt P X mod 3 Triznachna nesimetrichna sistema chislennya 0 1 2 Matricya C1 dlya nesimetrichnoyu sistemi chislennya 0 1 2 C1 1 0 0 0 2 1 2 2 2 displaystyle begin bmatrix 1 amp 0 amp 0 0 amp 2 amp 1 2 amp 2 amp 2 end bmatrix Rekursivne spivvidnoshennya dlya nastupnih matric Ci C i 1 0 0 0 2 C i 1 C i 1 2 C i 1 2 C i 1 2 C i 1 displaystyle begin bmatrix C i 1 amp 0 amp 0 0 amp 2 C i 1 amp C i 1 2 C i 1 amp 2 C i 1 amp 2 C i 1 end bmatrix b Ci F xi mod3 F xi bt P X mod 3 PrikladiDvoznachna sistema chislennya Algebrayichnij polinom Zadana tablicya 2 Viznachiti komponenti bj j 0 1 7 vektora b polinomialnoyi matematichnoyi modeli F xi bt P X Tablicya 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 Buduyutsya matrici C2 ta C3 C 2 C 1 0 C 1 C 1 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 displaystyle C 2 begin bmatrix C 1 amp 0 C 1 amp C 1 end bmatrix begin bmatrix 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 end bmatrix C 3 C 2 0 C 2 C 2 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 displaystyle C 3 begin bmatrix C 2 amp 0 C 2 amp C 2 end bmatrix begin bmatrix 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 1 amp 1 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 end bmatrix Shukanij vektor b C3 F xi 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 4 9 16 25 36 49 0 1 4 4 16 8 16 0 displaystyle begin bmatrix 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 1 amp 1 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 end bmatrix times begin bmatrix 0 1 4 9 16 25 36 49 end bmatrix begin bmatrix 0 1 4 4 16 8 16 0 end bmatrix Polinomialna matematichna model F xi bt P X 0 1 4 4 16 8 16 0 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 displaystyle begin bmatrix 0 amp 1 amp 4 amp 4 amp 16 amp 8 amp 16 amp 0 end bmatrix times begin bmatrix 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 end bmatrix x 1 displaystyle x 1 4 x 2 displaystyle x 2 4 x 1 displaystyle x 1 x 2 displaystyle x 2 16 x 3 displaystyle x 3 8 x 1 displaystyle x 1 x 3 displaystyle x 3 16 x 2 displaystyle x 2 x 3 displaystyle x 3 Yaksho koeficiyenti bj zaminiti kodami chisel u dvoznachnij sistemi chislennya to otrimayemo vektor F xi yakij vstanovlyuye zv yazok mizh rozryadami argumenta xi i funkciyi f k k 1 2 6 F k bt P X 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 f 6 f 5 f 4 f 3 f 2 f 1 0 x 3 x 2 x 3 x 1 x 3 x 2 x 1 x 2 0 x 1 displaystyle begin bmatrix 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 1 amp 0 0 amp 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 0 amp 0 amp 1 amp 1 amp 0 amp 0 amp 0 amp 0 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 end bmatrix times begin bmatrix 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 end bmatrix begin bmatrix f 6 f 5 f 4 f 3 f 2 f 1 end bmatrix begin bmatrix 0 x 3 x 2 x 3 x 1 x 3 x 2 x 1 x 2 0 x 1 end bmatrix Principova shema pristroyu dlya zvedennya chisel u kvadrat zgidno otrimanoyi polinomialnoyi modeli zobrazhena na mal 1 Mal 1 Principova shema pristroyu dlya zvedennya chisel v kvadrat Dvoznachna sistema chislennya Algebra Zhegalkina Zadana tablicya 3 Viznachiti komponenti bj j 0 1 7 vektora b dlya polinoma Zhegalkina Tablicya 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 Buduyutsya matrici C2 ta C3 C 2 C 1 0 C 1 C 1 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 displaystyle C 2 begin bmatrix C 1 amp 0 C 1 amp C 1 end bmatrix begin bmatrix 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 end bmatrix C 3 C 2 0 C 2 C 2 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 displaystyle C 3 begin bmatrix C 2 amp 0 C 2 amp C 2 end bmatrix begin bmatrix 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 1 amp 1 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 end bmatrix Shukanij vektor b b 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 F 0 F 0 F 1 m o d 2 F 0 F 2 m o d 2 F 0 F 1 F 2 F 3 m o d 2 F 0 F 4 m o d 2 F 0 F 1 F 4 F 5 m o d 2 F 0 F 2 F 4 F 6 m o d 2 F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 m o d 2 0 1 0 0 0 1 1 0 displaystyle b begin bmatrix 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 1 amp 1 amp 1 amp 1 amp 0 amp 0 amp 0 amp 0 1 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 1 amp 1 amp 0 amp 0 amp 1 amp 1 amp 0 amp 0 1 amp 0 amp 1 amp 0 amp 1 amp 0 amp 1 amp 0 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 amp 1 end bmatrix times begin bmatrix 0 1 0 1 0 0 1 1 end bmatrix begin bmatrix F 0 F 0 F 1 mod 2 F 0 F 2 mod 2 F 0 F 1 F 2 F 3 mod 2 F 0 F 4 mod 2 F 0 F 1 F 4 F 5 mod 2 F 0 F 2 F 4 F 6 mod 2 F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 mod 2 end bmatrix begin bmatrix 0 1 0 0 0 1 1 0 end bmatrix Polinomialna matematichna model F xi bt P X 0 1 0 0 0 1 1 0 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 displaystyle begin bmatrix 0 amp 1 amp 0 amp 0 amp 0 amp 1 amp 1 amp 0 end bmatrix times begin bmatrix 1 x 1 x 2 x 1 x 2 x 3 x 1 x 3 x 2 x 3 x 1 x 2 x 3 end bmatrix x 1 displaystyle x 1 x 1 displaystyle x 1 x 3 displaystyle x 3 x 2 displaystyle x 2 x 3 displaystyle x 3 mod 2 Tablicya 3 realizuye funkciyu D trigera Zminnim xi vidpovidayut najmenuvannya vhodiv i vihodiv x1 Qt x2 D x3 C F xi Qt 1 Algoritm funkcionuvannya D trigera opisuyetsya formuloyu Qt 1 Qt C 1 D C mod 2 Dlya zmenshennya obsyagu obchislen zastosovuyut vlastivosti rekursivnoyi proceduri pobudovi matrici Cj U danomu vipadku znahodyat pershi znachennya koeficiyentiv bj1 j1 0 1 2 3 zastosovuyuchi spivvidnoshennya bj1 C2 F xi1 mod2 Ostanni koeficiyenti bj2 j2 4 5 6 7 obchislyuyutsya za formuloyu bj2 bj1 C2 F xi2 mod2 Znachennya funkciyi F k mozhe buti u viglyadi bagatorozryadnih desyatkovih chisel V comu vipadku neobhidno zapisati ci chisla u dvoznachnij sistemi chislennya i operaciyu sumi po mod 2 provoditi porozryadno Triznachna simetrichna sistema chislennya 1 0 1 Algebrayichnij polinom Zadana tablicya 4 Viznachiti komponenti bj j 0 1 8 vektora b dlya algebrayichnogo polinoma Tablicya 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 Buduyetsya matricya C2 C 2 0 C 1 0 0 5 C 1 0 0 5 C 1 0 5 C 1 C 1 0 5 C 1 0 0 0 0 1 0 0 0 0 0 0 0 0 5 0 0 5 0 0 0 0 0 0 0 5 1 0 5 0 0 0 0 0 5 0 0 0 0 0 0 5 0 0 25 0 0 25 0 0 0 0 25 0 0 25 0 25 0 5 0 25 0 0 0 0 25 0 5 0 25 0 0 5 0 0 1 0 0 0 5 0 0 25 0 0 25 0 5 0 0 5 0 25 0 0 25 0 25 0 5 0 25 0 5 1 0 5 0 25 0 5 0 25 displaystyle C 2 begin bmatrix 0 amp C 1 amp 0 0 5 C 1 amp 0 amp 0 5 C 1 0 5 C 1 amp C 1 amp 0 5 C 1 end bmatrix begin bmatrix 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 1 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 amp 0 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 25 amp 0 5 amp 0 25 amp 0 amp 0 amp 0 amp 0 25 amp 0 5 amp 0 25 amp 0 amp 0 5 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 5 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 5 amp 0 amp 0 5 amp 0 25 amp 0 amp 0 25 amp 0 25 amp 0 5 amp 0 25 amp 0 5 amp 1 amp 0 5 amp 0 25 amp 0 5 amp 0 25 amp end bmatrix Shukanij vektor b C2 F xi 0 0 0 0 1 0 0 0 0 0 0 0 0 5 0 0 5 0 0 0 0 0 0 0 5 1 0 5 0 0 0 0 0 5 0 0 0 0 0 0 5 0 0 25 0 0 25 0 0 0 0 25 0 0 25 0 25 0 5 0 25 0 0 0 0 25 0 5 0 25 0 0 5 0 0 1 0 0 0 5 0 0 25 0 0 25 0 5 0 0 5 0 25 0 0 25 0 25 0 5 0 25 0 5 1 0 5 0 25 0 5 0 25 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 5 0 1 5 0 displaystyle begin bmatrix 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 1 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 5 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 amp 0 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 25 amp 0 5 amp 0 25 amp 0 amp 0 amp 0 amp 0 25 amp 0 5 amp 0 25 amp 0 amp 0 5 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 5 amp 0 amp 0 25 amp 0 amp 0 25 amp 0 5 amp 0 amp 0 5 amp 0 25 amp 0 amp 0 25 amp 0 25 amp 0 5 amp 0 25 amp 0 5 amp 1 amp 0 5 amp 0 25 amp 0 5 amp 0 25 amp end bmatrix times begin bmatrix 1 1 0 1 0 1 0 1 1 end bmatrix begin bmatrix 0 1 0 1 0 1 5 0 1 5 0 end bmatrix Polinomialna matematichna model F xi bt P X 0 1 0 1 0 1 5 0 1 5 0 1 x 1 x 1 2 x 2 x 1 x 2 x 1 2 x 2 x 2 2 x 1 x 2 2 x 1 2 x 1 2 displaystyle begin bmatrix 0 amp 1 amp 0 amp 1 amp 0 amp 1 5 amp 0 amp 1 5 amp 0 end bmatrix times begin bmatrix 1 x 1 x 1 2 x 2 x 1 x 2 x 1 2 x 2 x 2 2 x 1 x 2 2 x 1 2 x 1 2 end bmatrix x 1 displaystyle x 1 x 2 displaystyle x 2 1 5 x 1 2 x 2 displaystyle 1 5 x 1 2 x 2 1 5 x 1 x 2 2 displaystyle 1 5 x 1 x 2 2 realizuye funkciyu F xi x 1 displaystyle x 1 x 2 displaystyle x 2 mod 3 Triznachna simetrichna sistema chislennya 1 0 1 Modifikovanij polinom Zhegalkina Zadana tablicya 5 Dlya sinteza matematichnoyi modeli neobhidno viznachiti komponenti bj j 0 1 26 vektora b dlya modifikovanogo polinomu Zhegalkina Polinomialna model F xi znahoditsya yak skalyarnij dobutok dvoh vektoriv bt ta P X Tablicya 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 Pobuduvavshi matricyu C3 za rekursivnimi spivvidnoshennyami C 1 0 1 0 1 0 1 1 1 1 displaystyle C 1 begin bmatrix 0 amp 1 amp 0 1 amp 0 amp 1 1 amp 1 amp 1 end bmatrix C 2 0 C 1 0 C 1 0 C 1 C 1 C 1 C 1 displaystyle C 2 begin bmatrix 0 amp C 1 amp 0 C 1 amp 0 amp C 1 C 1 amp C 1 amp C 1 end bmatrix C 3 0 C 2 0 C 2 0 C 2 C 2 C 2 C 2 displaystyle C 3 begin bmatrix 0 amp C 2 amp 0 C 2 amp 0 amp C 2 C 2 amp C 2 amp C 2 end bmatrix rozrahovuyetsya vektor b b C3 F xi mod 3 Viznachivshi komponenti vektora b otrimayemo polinomialnu matematichnu model modifikovanogo polinoma Zhegalkina F xi x 1 displaystyle x 1 x 1 displaystyle x 1 x 2 displaystyle x 2 x 1 displaystyle x 1 x 2 2 displaystyle x 2 2 x 2 displaystyle x 2 x 3 displaystyle x 3 x 2 2 displaystyle x 2 2 x 3 displaystyle x 3 mod 3 Tablicya 5 realizuye funkciyu D trigera Zminnim xi vidpovidayut najmenuvannya vhodiv i vihodiv x1 Qt x2 C x3 D F xi Qt 1 Algoritm funkcionuvannya D trigera opisuyetsya formuloyu Qt 1 Qt 1 C C2 D S C2 mod 3Div takozhPolinom Zhegalkina Model Matematichne modelyuvannya Polinomialna interpolyaciyaLiteraturaPuhov G E Evdokimov V F Sinkov M V Razryadno analogovye vychislitelnye sistemy M Sov radio 1978 Plyush Yu A Apparaturnaya realizaciya funkcionalnogo preobrazovaniya v specializirovannyh vychislitelnyh ustrojstvah Gibridnye vychislitelnye mashiny K Naukova dumka 1979 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 Avtor svid SSSR 631918 MKI3 G 06 f 15 32 BI 32 30 08 79g