Implementation of computational operations and elementary functions by systems of Boolean functions.

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 Other publications by this author     Mamaev Evgenii Igorevich programmer, individual entrepreneur "Bogaturev" 424036, Russia, Mari El, Yoshkar-Ola, ul. K.Marksa, d. 76, kv. 17 emamaew@gmail.com Maslyanskii Vladimir Mikhailovich programmer, "Pervii bit" L.t.d. 424036, Russia, Mari El, Yoshkar-Ola, ul. Mira, d. 29, kv. 3  mavladm@nm.ru

Shestakov Aleksei Sergeevich student of the Volga State Technological University 424000, Russia, Yoshkar-Ola, pl. Lenina, d.3  a1ex42@yandex.ru

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

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

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

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

Таблица 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

q_ia_i®q_i’a_i’S

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

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

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

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

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

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

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

A + B

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

Λ

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

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

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

Λ

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

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

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

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

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

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

ΛΛΛΛx₁x₂…x_n*k₁₁k₁₂…k_1n*…* k_m1k_m2…k_mn ΛΛΛΛ

Λ

где:

x₁x₂…x_n – входной набор переменных БФ

k_i1k_i2…k_in – единичные наборы БФ

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

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

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

ΛΛΛΛx₁x₂…x_n*k₁₁k₁₂…k_1n*…* k_m1k_m2…k_mn *YΛΛΛ

Λ

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

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

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

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

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

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

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

Таблица 2

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

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

Ф = К₁ÚК₂Ú…ÚК_s , К_i = x_i1^si1x_i2^si2…x_ip^{sip ,} (i = 1,2, … , s )

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

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

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

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

f(x₁,x₂,…,x_k,x_k+1 ,…,x_n) =

_k

= V & x_i^si f(s₁, s₂,…, s_k,x _k+1 ,…,x_n),

^{"(s1, s2,…, sk) i=1}

где s_i=0,1; i=1,…,k, x_i^si=x_i, если s_i=1; x_i^si=xi, если s_i=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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

и Рида ^[10]

(2)

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

L ₄(n) = 2^{n – 3} – 1, n > 2 (3)

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

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

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

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

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

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

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

1. n– четное.

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

L ₄(n) = 2^{n – 4} + (2^{n – 3} + 2^{n – 5} + 2^{n – 7} + ¼ + 2) = 2^{n – 4} + (2^{n – 3} – 2) / 3

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

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

L ₄(n) = 2^{n – 4} + (2^{n – 3} + 2^{n – 5} + 2^{n – 7} + ¼ + 1) = 2^{n – 4} + (2^{n – 3} – 1) / 3

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

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

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

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

Таблица 3.

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

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

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

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

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

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

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

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

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