Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

Реализация вычислительных операций и элементарных функций системами булевых функций

Власов Александр Александрович

кандидат технических наук

доцент, кафедра Проектирования и производства Электронно вычислительных средств, Поволжский Государственный Технологический Университет

424006, Россия, республика Марий Эл, г. Йошкар-Ола, пр.Гагарина, 24, кв. 26

Vlasov Aleksandr Aleksandrovich

PhD in Technical Science

Associate Professor of the Department of Design and Manufacture of Electronic Computing Means at the Volga State Technological University

424006, Russia, respublika Marii El, g. Ioshkar-Ola, pr.Gagarina, 24, kv. 26

a-vlasov2002@mail.ru
Другие публикации этого автора
 

 
Мамаев Евгений Игоревич

Программист, ИП "Богатырёв"

424036, Россия, Марий Эл, Йошкар-Ола, ул.К.Маркса, д.76, кв.17


Mamaev Evgenii Igorevich

programmer, individual entrepreneur "Bogaturev"

424036, Russia, Mari El, Yoshkar-Ola, ul. K.Marksa, d. 76, kv. 17

emamaew@gmail.com
Маслянский Владимир Михайлович

Программист, ООО "Первый бит"

424030, Россия, Марий Эл, Йошкар-Ола, ул.Мира, д.29, кв.3


Maslyanskii Vladimir Mikhailovich

programmer, "Pervii bit" L.t.d.

424036, Russia, Mari El, Yoshkar-Ola, ul. Mira, d. 29, kv. 3 

mavladm@nm.ru
Шестаков Алексей Сергеевич

студент, кафедра Проектирования и производства электронно вычислительных предств, Поволжский Государственный Технологический Университет

424000, Россия, Марий Эл, Йошкар-Ола, площадь Ленина, д.3

Shestakov Aleksei Sergeevich

student of the Volga State Technological University

424000, Russia, Yoshkar-Ola, pl. Lenina, d.3 

a1ex42@yandex.ru

DOI:

10.7256/2306-4196.2014.3.12119

Дата направления статьи в редакцию:

30-05-2014


Дата публикации:

13-06-2014


Аннотация: В статье рассматриваются существующие способы математического описания и представления в ЭВМ алгоритмов операций преобразования данных (арифметические операции, вычисления элементарных функций (ЭФ) и другие). Показано что основными способами их реализации в ЭВМ на различных уровнях организации вычислительного процесса являются- программный, микропрограммный и схемный. В качестве возможных способов математического представления рассматриваются: табличный, на основе СБФ, на основе машины Тьюринга Проводится краткий анализ известных форм представления систем булевых функций (СБФ) с учётом используемых средств реализации и оценка математической и технической сложности в зависимости от вида описания. Представление алгоритмов операций преобразования данных в виде СБФ позволяет максимально распараллеливать преобразование данных. Показано что вычислительная сложность операции определяется мощностью входных и выходных множеств и разрядностью входных данных и результатов.. Представление алгоритмов реализации СБФ в форме СДНФ весьма избыточно и что показано на основе некоторых арифметических операций и ЭФ. Делается вывод о необходимости минимизации сложности на основе минимальной и кратчайшей формы СБФ. В качестве реальных средств реализации СБФ в ПЛИС рассматривается применение универсальных логических модулей (УЛМ), в технических терминах это таблицы перекодировки (LUT). Приводятся способы построения СБФ на основе УЛМ от четырёх переменных и способы декомпозиции СБФ для их реализации схемами из УЛМ. Методы и методология исследований включают методы смешанного анализа, методы теории дискретной математики в частности аппарат анализа и синтеза булевых функций, теории алгоритмов, методы вычислительного эксперимента. В статье рассматривается сложность математического представления операций преобразования данных и их реализации в ЭВМ (арифметические вычисления элементарных функций и некоторые другие). Предлагаются алгоритмы реализации СБФ схемой из УЛМ от четырёх переменных и исследуются алгоритмы построения таких схем на основе разложения Шеннона и Рида. На основе анализа входных и выходных переменных операции преобразования данных, синтеза СБФ для формирования проблемно-ориентированных и специализированных команд в ЭВМ.


Ключевые слова:

Сложность операций, Системы булевых функций, Арифметико-логические формы, Декомпозиция СБФ, Разложение Шеннона, Разложение Рида, ПЛИС, Универсальный логический модуль, Таблицы перекодировки, СДНФ

УДК:

519.714

Abstract: The paper reviews existing methods of mathematical description and representation of algorithms for data conversion operations (arithmetic operations, calculation of elementary functions (EF) and others).  The article shows that their main realizations in the computer at the various levels of the organization of computational process are software, firmware and circuit realizations. As a possible way of mathematical representation the authors consider table representation, representation based on the systems of Boolean functions and Turing machine based representation. The article presents a brief analysis of the known forms of representation of systems of Boolean functions (SBF), taking into account the means of implementation and evaluation of mathematical and technical complexity depending on the type of description. The representation of the data transformation algorithms as SBF maximizes parallelization of data conversion. It is shown that the computational complexity of the operation is determined by the power of the input and output sets and number of bits in input and resulting data. The representation of the algorithms based on systems of Boolean functions in the form of the PDNF is highly redundant which is shown on the example of some arithmetic operations. The authors make a conclusion about the need of minimizing the complexity based on the minimum and shortest form of SBF. As a way of implementing SBF in the FPLD the authors considered use of the universal logic modules (ULM), in technical terms that a lookup table (LUT). The article present methods of constructing SBF based on the ULM of four variables and methods of SBF SBF decomposition for its implementation in ULM schemes. Methods and research methodology include mixed methods analysis methods, methods of the theory of discrete mathematics, apparatus for analysis and synthesis of Boolean functions in particular, the theory of algorithms, methods of computational experiment. The article reviews the complexity of the mathematical representation of the data conversion operations and their implementation in the computer (arithmetic computations, elementary functions and some others). The authors suggest algorithms for implementation of the SBF in form of ULM scheme of four variables, study the algorithms for constructing such schemes based on the Shannon and Reed expansions. Based on the analysis of the input and output variables of data conversion operations the  SBF synthesis for the formation of problem-oriented and specialized computer commands is carried out.


Keywords:

complexity of operations , Systems of Boolean functions , Arithmetic-logical forms, SBF decomposition, Shannon expansion, Reed expansion, FPLD, universal logic module , lookup tables, PDNF

Введение

Современная элементная база позволяет выполнить аппаратную реализацию операций и функций достаточно большой сложности в виде СБИС. При этом возникает вопрос наиболее эффективной реализации функций и операций, по каким либо критериям или их совокупностям.

Наиболее часто используется критерий времени реализации и схемной сложности (аппаратных затрат). Для оценки целесообразности выбора того или иного способа представления функций и операций и эффективности его реализации на СБИС требуется какой-то объективный критерий или показатель связанный только с фундаментальными свойствами операций. В качестве такого показателя можно было бы по аналогии с алгоритмами использовать показатель сложности операций. Известно, что на практике алгоритмы оцениваются временной и емкостной сложностью [1]. Непосредственное применение этих показателей малоинформативно, поскольку они скорее оценивают сложность метода выполнения операции или функции и существенно зависят от выбора базиса элементарных операций.

На наш взгляд сложность операции, так или иначе, связана со способом её реализации. Наиболее широко применяются следующие способы реализации: табличный, программный и микропрограммный (алгоритмический). Возможна также реализация операций непосредственно на основе построения схем, вычисляющих значения системы булевых функций (СБФ), описывающих эти операции или функции.

Для того, чтобы изложение материала статьи интерпретировалось однозначно, приведем основные определения, которые будут использоваться в дальнейшем.

Операция – это закон, по которому некоторым упорядоченным группам данного множества М ставятся в соответствие элементы из М, один или несколько.

Операция должна быть определена для любой группы элементов и должна быть однозначной.

Функцией называется функциональное соответствие. Функция fустанавливает соответствие между множествами А и В (функция fимеет вид f®В). Каждому элементу а из своей области определения функция fставит в соответствие единственный элемент b из обласи значений. Элемент а называется аргументом функции, b – значением функции на а.

n-местная (n-арная) операция w на множестве М (при n>0) есть однозначная функция из Мn в М; при этом не предполагается, что функция w определена для всякого элемента множества Мn. Если операция w не всюду определена на Мn, то она называется n-местной частичной операцией. Под нуль-местной операцией на М понимают выделение элемента из М.

Примеры:

1. Сложение действительных чисел есть двухместная операция на множестве R действительных чисел

2. Деление действительных чисел есть двухместная частичная операция на множестве R

3. Выделение элемента из R (например 1) есть нульместная операция в R.

Операцию можно рассматривать как отображение множества входных параметров на множество выходных.

Способы представления алгоритмов операций

В настоящее время реализация арифметических и логических операций и элементарных функций в ЭВМ может быть представлена на основе способов вычислений:

— на основе выполнения алгоритма операции в том или ином базисе машинных операций (микропрограммный, программный);

— на основе построения схемы алгоритма в том или ином элементарном базисе интегральных схем на кристалле.

Возможны так же комбинации этих способов особенно при реализации макрооперации. В качестве примера в таблице 1 представлена возможная реализация некоторых операций.

Таблица 1

Способ вычислений

Операция АЛУ

Алгоритмический

Умножение, деление, возведение в квадрат, извлечение корня, сканирование разрядов, вычисление элементарных функций (синус, экспонента и др.)

Схемный

Сложение, вычитание, сдвиг, инверсия, поразрядные логические операции, сравнение, установка, сброс, проверка отдельных разрядов.

Входные и выходные множества

Операцию или функцию можно рассматривать с точки зрения входных и выходных множеств. Входное множество – множество аргументов; выходное – множество результатов. Если разрядность входного множества n, а значений результатов m, то всевозможных значений аргументов - 2n, а значений результатов 2m. Различных способов отображения множества аргументов на множество результатов, как правило больше, чем всевозможных значений результата для конкретной операции или функции. Следовательно при оценке сложности операции или функции должны учитываться её особенности.

Табличное представление операций

Операция может быть представлена в виде таблицы и храниться, например, в ПЗУ вычислительной машины. Для представления операции в виде таблицы необходимо иметь рассчитанные значения операции при всех входных параметрах. В большинстве случаев это невозможно, поэтому используют некоторое ограниченное входное множество и для него рассчитывают таблицу.

Табличный метод характеризуется емкостной сложностью. Сложность табличного представления определяется объемом таблицы, который зависит от мощности входного и выходного множеств.

Алгоритмическое представление операций

Алгоритмическое преставление для получения результата операции или значения функции может быть описано несколькими способами. Известны [2] три типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм.

Первый тип – рекурсивные функции.

Второй тип основан на представлении об алгоритме, как о некотором детерминированном устройстве. Основной теоретической моделью этого типа является машина Тьюринга.

Третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки.

Машина Тьюринга

Операция может быть представлена в виде алгоритма и записана на одном из алгоритмических языков.

Можно выделить три типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм.

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики – вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа – рекурсивные функции – является исторически первой формализацией понятия алгоритма.

Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этих моделей близка к ЭВМ и, следовательно, к инженерной интуиции. Основной теоретической моделью этого типа является машина Тьюринга.

Наконец третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены фрагмента слова другим словом. Преимущества этого типа – в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (не обязательно числовой) природы.

Под алгоритмом понимается процесс последовательного вычисления величин, протекающий в дискретном времени так, что в каждый момент времени система величин получается по определенному закону из системы величин, имевшихся в предыдущий момент.

Трудоемкость алгоритма – число элементарных действий, выполняемых при его реализации.

Оценку алгоритма можно проводить сверху или снизу. Оценку сверху выполняют, указав конкретный алгоритм решения задачи, т.к. трудоемкость задачи не превышает трудоемкости любого из решающих её алгоритмов.

Оценку снизу получают из некоторых общих соображений (например, мощностных или информационных).

Сложность алгоритма можно рассматривать по следующим величинам:

  1. Время работы алгоритма
  2. Объем памяти, требуемый для работы алгоритма
  3. Размер программы (количество элементарных команд)

Различные формальные модели алгоритмов эквивалентны с точки зрения класса решаемых задач. Следовательно, теорию алгоритмов можно излагать на базе любой из них. Представляет определенный интерес оценка сложности на основе реализации операций машиной Тьюринга. Это обусловлено тем, что машина Тьюринга выполняет исключительно последовательно самые элементарные операции и алгоритмически универсальна.

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Машина работает в дискретные моменты времени t = 0, 1, 2, … В каждый момент времени во всякой ячейке ленты записана буква из конечного алфавита А={а01, … ,аk-1}, называемого внешним алфавитом машины, а головка находится в одном из конечного числа внутренних состояний Q={q0,q1, … ,qm-1}. Пусть а0 является пустым символом (обозначается также L). Наличие этого символа в ячейке означает, что она пуста.

В каждый момент времени головка обозревает одну ячейку ленты и, в зависимости от содержимого ячейки и своего внутреннего состояния, заменяет символ в ячейке на новый (Н), возможно прежний, переходит в новое состояние (возможно прежнее), и сдвигается на одну ячейку вправо (П), влево (Л), или остается на месте.

Работа машины подчиняется системе команд вида:

qiai®qiaiS

где SÎ{П,Л,Н}. Среди состояний машины особо выделяется одно (условимся, что это состояние q0), называемое заключительным.

Если машина в некоторый момент времени оказывается в состоянии q0, то машина прекращает свою работу. Для каждой пары qiai имеется одна команда с левой частью qiai , следовательно, всего имеется k(m-1) команд. Совокупность этих команд называется программой.

Оценить сложность функции или операции, для которой известна программа реализации на машине Тьюринга можно следующим образом:

  1. Объем программы
  2. Количество элементарных шагов до окончания работы алгоритма (время работы алгоритма)

В качестве примеров рассмотрим операцию сложения и вычисление значения булевой функции:

а) Сложность операции сложения:

Начальная конфигурация:

A + B

ΛΛΛΛ | |…|*| |…| ΛΛΛΛ

Λ

Программа вычисления суммы:

Λ

|

*

Q1

q2ΛП

q0ΛП

Q2

q2|П

q3|Л

Q3

q0ΛП

q3|Л

После обработки входных данных информация на ленте будет иметь вид:

ΛΛΛΛ | |…|ΛΛΛΛ

Λ

Количество внутренних состояний машины – 4

Количество букв внешнего алфавита машины – 3

Объём программы составляет – 6 команд

Количество шагов алгоритма – 2*А+1

б) Сложность вычисления значений булевой функции:

Начальная конфигурация:

ΛΛΛΛx1x2xn*k11k12k1n*…* km1km2kmn ΛΛΛΛ

Λ

где:

x1x2xn – входной набор переменных БФ

ki1ki2kin – единичные наборы БФ

Процесс вычисления БФ сводится к поиску единичного набора совпадающего со входным набором переменных. Если такой набор существует, то значение БФ – 1, иначе – 0.

Программа вычисления:

Λ

0

1

_

|

*

q1

q30П

q21П

q4*П

q2

q20П

q21П

q2_П

q2|П

q5*П

q3

q30П

q31П

q3_П

q3|П

q6*П

q4

q10ΛН

q4_П

q9|П

q10*П

q5

q7ΛН

q2|П

q2_П

q5_П

q5|П

q2*Н

q6

q7ΛН

q3_П

q3|П

q6_П

q6|П

q3*Н

q7

q8ΛП

q70Л

q71Л

q7_Л

q7|Л

q7*Л

q8

q1ΛП

q1ΛП

q1*Н

q9

q11*Н

q4*П

q10

q12*П

q100П

q101П

q10_П

q10|П

q10*П

q11

q00Н

q12

q01Н

После обработки входных данных информация на ленте будет иметь вид:

ΛΛΛΛx1x2xn*k11k12k1n*…* km1km2kmn *YΛΛΛ

Λ

где: Y – значение БФ.

Количество внутренних состояний машины – 13

Количество букв внешнего алфавита машины – 6

Объём программы составляет – 48 команд

Из полученных результатов видно, что оценка сложности операции на основе машины Тьюринга весьма трудоёмка и громоздка и не очень наглядна.

Представление операций системой булевых функций

Одним из наиболее формализованных и наглядных способов представления операций является представление в виде системы булевых функций (СБФ). Форма описания и основные параметры при представлении СБФ операций зависит от средств реализации операций (таблица 2). Следует отметить, что реализация в виде СБФ позволяет максимально распараллелить его выполнение и соответственно получить минимальное время её реализации.

Таблица 2

Форма описания

Средство реализации

Математическая сложность

Техническая сложность

СДНФ

ЗУ

Число переменных

Число ячеек ЗУ

ДНФ, факторизованная ДНФ

ПЛМ, ПМЛ

Число переменных, Число различных конъюнкций

Площадь ПЛМ, число ячеек ПМЛ.

И-НЕ, ИЛИ-НЕ

Базовые матричные кристаллы, заказные БИС

Число букв

Число логических элементов

Произвольная скобочная форма

Однородная среда, матрицы FPGA

Число букв

Число ячеек ОС, число ячеек ПЛИС

Полином Жегалкина

Специализированная СБИС

Число различных конъюнкций

Число логических элементов

Известные арифметико-логические формы.

Специализированная СБИС

Число членов формы

Число логических элементов

Пороговая логика

Нейронные сети

Число пороговых элементов

Число нейронов

Бинарные программы (decision diagrams)

Сеть из мультиплексоров

Число условных вершин

Число мультиплексоров

Операция может быть представлена в виде системы булевых функций.

Рассмотрим представление в виде ДНФ. ДНФ(дизъюнктивной нормальной формой) называется формула, имеющая вид дизъюнкции некоторых конъюнкций

Ф = К1ÚК2ÚÚКs , Кi = xi1si1xi2si2…xipsip , (i = 1,2, … , s )

Любая логическая функция (ЛФ) может быть реализована некоторой ДНФ( например СДНФ). ЛФ представленная в виде СДНФ обладает большой избыточностью.

Минимальной дизъюнктивной нормальной формой (МДНФ) функции f называется ДНФ, содержащая минимально возможное число вхождений символов переменных среди всех ДНФ реализующих f. Задача нахождения МДНФ называется задачей минимизации. Иногда решается задача нахождения ДНФ содержащей минимально возможное число конъюнкций, (такая ДНФ называется кратчайшей).

Во многих случаях количество переменных булевой функции оказывается велико, что затрудняет её прямую оценку и реализацию. В этом случае используют декомпозицию ЛФ (разложение Шеннона).

Любая функция f(x1,x2,…,xn) , не равная тождественно нулю, представима в виде разложения Шеннона

f(x1,x2,…,xk,xk+1 ,…,xn) =

k

= V & xisi f(s1, s2,…, sk,x k+1 ,…,xn),

"(s1, s2,…, sk) i=1

где si=0,1; i=1,…,k, xisi=xi, если si=1; xisi=xi, если si=0

Таким образом сложность операции представленной в форме СБФ (в виде СДНФ) может быть выражена как:

  1. Количество функций СБФ
  2. Количество коньюнкций в каждой функции (слов)
  3. Количество переменных в каждой функции (букв)

Для представления операции в виде СБФ может использоваться следующий подход:

Операция представляется как «черный ящик» на входы которого подаются параметры, а с выходов снимается реакция.

Параметры и реакции составляют таблицу, которую сводят к таблицам истинности СБФ. При таком подходе, в виде СБФ можно представить любую операцию преобразования данных.

В качестве примеров рассмотрим СБФ следующих операций:

1) Извлечения квадратного корня из шестиразрядных чисел в виде СБФ (двоичный код):

F0=(0111000001111111000000000111111111110000000000000111111111111111)

F1=(0000111111111111000000000000000000001111111111111111111111111111)

F2=(0000000000000000111111111111111111111111111111111111111111111111)

2) Возведения в квадрат трехразрядных чисел в виде СБФ (шестнадцатеричный код):

F0 = (01010101)

F1 = (00000000)

F2 = (00100010)

F3 = (00010100)

F4 = (00001101)

F5 = (00000011)

3) Извлечения квадратного корня из шестиразрядных чисел в виде СБФ (шестнадцатеричный код):

F0 = (E0EF00EFF000EFFF)

F1 = (0FFF00000FFFFFFF)

F2 = (0000FFFFFFFFFFFF)

4) Возведения в квадрат трехразрядных чисел в виде СБФ (шестнадцатеричный код):

F0 = (AA)

F1 = (00)

F2 = (44)

F3 = (82)

F4 = (0B)

F5 = (0C)

В таблице 3 приведены оценки сложности элементарных операций в СБФ:

Таблица 3

Функция/ Операция

Разрядность входных данных

Количество конъюнкций

Разряд №

Название

Операнды (разрядности)

0

1

2

3

4

5

Сложение

3 , 3

32

32

32

28

-

-

Умножение

3 , 3

16

24

28

22

15

6

Квадрат

3

4

0

2

2

3

2

Корень

6

36

38

44

-

-

-

В таблице 3 приведено количество единичных наборов для каждого разряда результата рассмотренных выше операций.

Оценки показывают, что реализация операций на основе СДНФ, характеризуется высокой сложностью и требует больших аппаратных затрат. С целью уменьшения аппаратных затрат необходимо провести минимизацию ДНФ. В этом случае существенно уменьшается число наборов и возможна реализация операций на ПЛИС.

Ниже приводятся графики зависимости числа единичных наборов СДНФ от разрядности результата.

10

Рисунок 1. Реализация экспоненты в виде СДНФ.

2

Рисунок 2. Реализация тангенса в виде СДНФ.

3

Рисунок 3. Реализация синуса в виде СДНФ.

4

Рисунок 4. Реализация гиперболического тангенса в виде СДНФ.

5

Рисунок 5. Реализация гиперболического синуса в виде СДНФ.

При построении диаграмм использовались 16 разрядные входные данные. Результат представлен в форме вещественного числа с фиксированной точкой. Разряды результата располагаются в порядке возрастания слева направо, сначала дробные разряды (16,15,…,1), затем целочисленные (0,1,…).

Один из способов повышения эффективности использования оборудования ЭВМ и в значительной степени реализации потенциального параллелизма является представление СБФ в виде арифметико-логических форм (АЛФ)[5]. В [6] рассмотрены способы повышения эффективности и реализации АЛФ и даны оценки сокращения представления ЛФ в этих формах.

Сложность реализации произвольной базовых функций в базисе 4-УЛМ

В современных программируемых логических интегральных схемах основным элементом преобразований данных являются универсальный логический модуль (УЛМ) другое название таблицы перекодировки Look Up Table (LUT). В существующих ПЛИС в большинстве случаев в качестве базисного элемента используются УЛМ выполняющие функции от четырёх переменных (4-УЛМ). В ПЛИС фирмы Altera 4-УЛМ могут быть представлены как две 3-УЛМ.

Реализация логических функций (ЛФ) в виде схемы на УЛМ при представлении СБФ в виде СДНФ существенно избыточно, поэтому для упрощения представления ЛФ используются различные способы минимизации и декомпозиции.

Произвольная БФ может быть реализована в базисе 4-УЛМ на основе разложений по одной переменной Шеннона [8]

13 (1)

и Рида [10]

12 (2)

Функция f в виде (1), (2) реализуется одним 4-УЛМ. Функции f (xi = 1) и f (xi = 0) называются остаточными и зависят от n 1 переменной. Рекурсивно применяя процедуру разложения n – 4 раза к обеим остаточным функциям получим схему, представляющую собой полное бинарное дерево (рисунок 6). Легко подсчитать, что число 4-УЛМ в этой схеме

L 4(n) = 2n 3 – 1, n > 2 (3)

2n 4 листовых УЛМ реализуют остаточные функции ровно от четырех переменных, остальные УЛМ реализуют функции разложения (1) и (2).

11

Рисунок 6. Схема полного бинарного дерева.

Схему можно упростить, если заметить, что группы из трех 4-УЛМ, выделенные на рисунок 6 реализуют следующую функцию от шести переменных (рисунок 7а)

9

В свою очередь эта функция может быть разложена следующим образом

8

Таким образом, выделенные группы из трех 4-УЛМ могут быть заменены двумя 4-УЛМ, соединенными по схеме рисунок 7в.

7

Рисунок 7. Варианты преобразования бинарного дерева.

Рассмотрим два случая.

1. n– четное.

В схеме рис. 1. нечетное число уровней на последнем уровне 2n 4 УЛМ, реализующих остаточные функции, УЛМ соседних уровней группируются по тройкам по схеме рисунок 7в, в итоге общее число УЛМ в схеме

L 4(n) = 2n 4 + (2n 3 + 2n 5 + 2n 7 + ¼ + 2) = 2n 4 + (2n 3 – 2) / 3

1. n– нечетное.

В схеме рис. 1. четное число уровней на последнем уровне 2n 4 УЛМ, реализующих остаточные функции, УЛМ соседних уровней группируются по тройкам по схеме рисунок 7в и еще остается один корневой УЛМ, в итоге общее число УЛМ в схеме

L 4(n) = 2n 4 + (2n 3 + 2n 5 + 2n 7 + ¼ + 1) = 2n 4 + (2n 3 – 1) / 3

В итоге сложность новой схемы

6

Выполняя несложные преобразования, получим, что выигрыш по сложности в первом случае составит (2n 3 – 2n 4 - 1) / 3, а во втором (2n 3 – 2n 4 - 2) / 3.

В [9] установлено, что не существует универсальных разделительных декомпозиций по одной переменной функции на две остаточных подфункции, отличных от разложений Шеннона и Рида и PN однотипных с ними. Этот факт дает возможность предполагать, что так же не существует других повторных декомпозиций заданной функции на две подфункции кроме указанных и PN однотипных с ними.

Исследованы системы булевых функций, описывающих типовые операции АЛУ, некоторые элементарные функции, некоторые функции по работе с полями данных типа “дата” в СУБД. В таблице 3 приведены результаты исследования.

Таблица 3.

Операция

n

m

Различных конъюнкций в ДНФ

Букв в ДНФ

Букв в факторизо-ванной ДНФ

4 УЛМ для реализа-ции

Памяти для реализации

Сравнение

8

2

38

95

76

20

160

Сложение

8

9

46

95

91

27

216

Умножение

4

8

128

334

298

69

Деление

8

8

180

531

482

95

760

Возведение в квадрат

8

16

194

526

486

105

840

Арифметическое выражение x2+y

16

16

870

4520

3980

443

3584

Квадратный корень

8

4

25

77

62

16

128

Синус

8

9

168

713

542

88

704

Косинус

8

9

174

720

566

91

728

DAYOFWEEK

24

3

22092

321607

321020

11058

176928

n – разрядность операнда (операндов);

m – разрядность результата;

Заключение

1.Сравнение способов представления операций и элементарных функций показывает, что наиболее наглядным и конструктивным является представление в форме СБФ. При таком способе реализации может быть получено минимальное время выполнения операций, т.к. возможно максимальное распараллеливание вычислений. По аппаратным затратам реализация СБФ занимает промежуточное место между табличным и алгоритмическим представлениями. Установлено, что порядок сложности операции определяется мощностью входного и выходного множеств. Для арифметических операций и элементарных функций это соответствует числу и разрядности входных данных и разрядности результата. Так, например, операции извлечения квадратного корня имеет первый порядок сложности, а операции умножения и деления второй порядок сложности.

Реализация основных арифметических операций в форме СБФ не всегда целесообразна, поскольку за время эволюции арифметических устройств сложились оптимальные способы их реализации, тем не менее представление в виде СБФ на ПЛИС представляет определенный интерес особенно при его реализации на основе перестраиваемых автоматов. Наибольший интерес представления в форме СБФ имеет место в случае введения новых операций и макроопераций преобразования данных, которые в традиционных АЛУ реализуются последовательным алгоритмом в виде фрагмента программы.

Для минимизации СБФ при её реализации схемы из УЛМ возможные способы её декомпозиции (Shannon, Reed).

2.Найдена универсальная повторная декомпозиция произвольной функции от n переменных на две подфункции от (n - 1) переменной.

3.Высказано предположение, что других универсальных повторных декомпозиций функции от n переменных на две подфункции от (n - 1) переменной не существует.

4.Найдена универсальная повторная декомпозиция произвольной функции от n переменных на две подфункции от (n - 1) переменной.

5.Высказано предположение, что других универсальных повторных декомпозиций функции от n переменных на две подфункции от (n - 1) переменной не существует.

Библиография
1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979
2. Кузнецов О.П., Андерсон-Вельский Г.М. Дискретная математика для инженера. – 2-е издание. М.: Энергоатомиздат, 1988 – 480 с.
3. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука. 1980.-400 с.
4. Фролов АБ., Андреев А.Е., Болотов А.А., Коляда К.В., Прикладные задачи дискретной математики и сложность алгоритмов. Под ред. Академика АТН РФ В. Б. Кудрявцева. – М.: Изд. МЭИ, 1997 – 312 с.
5. Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. ¬М.: Наука. Физматлит, 1997. – 192 с.
6. Власов А.А., Мамаев Е.И. Расширенные арифметико-логические формы для параллельных логических вычислений Параллельные вычисления и задачи управления: Труды Международной конференции (PACO'2001) Москва, 2-4 октября 2001 г. Институт проблем управления им. В. А. Трапезникова 1522c. ISBN 5-201-09559-3 с. 66-73.
7. http://www.achronix.com/
8. Shannon C.A. Symbolic analysis of relay and switching circuits // Trans. of American Inst. of Electrical engineers, 1938, № 57.
9. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. – СПб.: Наука, 2000. – 780 с.
10. Reed I.S. Class of multiple-error correcting codes and decoding scheme // IRE Trans. Inform. Theory, 1954, IT-4.
11. Лучинин З.С. Структура данных для документо-ориентированных баз данных // Программные системы и вычислительные методы. - 2013. - 3. - C. 230 - 232. DOI: 10.7256/2305-6061.2013.3.10772.
12. Н.А. Галанина, Д.Д. Дмитриев Синтез БПФ на ПЛИС с применением системы остаточных классов // Программные системы и вычислительные методы. - 2013. - 1. - C. 129 - 133. DOI: 10.7256/2305-6061.2013.01.11.
References
1. Akho A., Khopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nykh algoritmov. M.: Mir, 1979
2. Kuznetsov O.P., Anderson-Vel'skii G.M. Diskretnaya matematika dlya inzhenera. – 2-e izdanie. M.: Energoatomizdat, 1988 – 480 s.
3. Sholomov L.A. Osnovy teorii diskretnykh logicheskikh i vychislitel'nykh ustroistv. M.: Nauka. 1980.-400 s.
4. Frolov AB., Andreev A.E., Bolotov A.A., Kolyada K.V., Prikladnye zadachi diskretnoi matematiki i slozhnost' algoritmov. Pod red. Akademika ATN RF V. B. Kudryavtseva. – M.: Izd. MEI, 1997 – 312 s.
5. Malyugin V.D. Parallel'nye logicheskie vychisleniya posredstvom arifmeticheskikh polinomov. ¬M.: Nauka. Fizmatlit, 1997. – 192 s.
6. Vlasov A.A., Mamaev E.I. Rasshirennye arifmetiko-logicheskie formy dlya parallel'nykh logicheskikh vychislenii Parallel'nye vychisleniya i zadachi upravleniya: Trudy Mezhdunarodnoi konferentsii (PACO'2001) Moskva, 2-4 oktyabrya 2001 g. Institut problem upravleniya im. V. A. Trapeznikova 1522c. ISBN 5-201-09559-3 s. 66-73.
7. http://www.achronix.com/
8. Shannon C.A. Symbolic analysis of relay and switching circuits // Trans. of American Inst. of Electrical engineers, 1938, № 57.
9. Shalyto A.A. Logicheskoe upravlenie. Metody apparatnoi i programmnoi realizatsii algoritmov. – SPb.: Nauka, 2000. – 780 s.
10. Reed I.S. Class of multiple-error correcting codes and decoding scheme // IRE Trans. Inform. Theory, 1954, IT-4.
11. Luchinin Z.S. Struktura dannykh dlya dokumento-orientirovannykh baz dannykh // Programmnye sistemy i vychislitel'nye metody. - 2013. - 3. - C. 230 - 232. DOI: 10.7256/2305-6061.2013.3.10772.
12. N.A. Galanina, D.D. Dmitriev Sintez BPF na PLIS s primeneniem
sistemy ostatochnykh klassov // Programmnye sistemy i vychislitel'nye metody. - 2013. - 1. - C. 129 - 133. DOI: 10.7256/2305-6061.2013.01.11.