|
Библиотека
|
ваш профиль |
Статья опубликована с лицензией Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0) – Лицензия «С указанием авторства – Некоммерческая».|
Кибернетика и программирование
Правильная ссылка на статью:
Власов А.А., Мамаев Е.И., Маслянский В.М., Шестаков А.С.
Реализация вычислительных операций и элементарных функций системами булевых функций
// Кибернетика и программирование.
2014. № 3.
С. 1-35.
DOI: 10.7256/2306-4196.2014.3.12119 URL: https://nbpublish.com/library_read_article.php?id=12119
Реализация вычислительных операций и элементарных функций системами булевых функций
DOI: 10.7256/2306-4196.2014.3.12119Дата направления статьи в редакцию: 30-05-2014Дата публикации: 13-06-2014Аннотация: В статье рассматриваются существующие способы математического описания и представления в ЭВМ алгоритмов операций преобразования данных (арифметические операции, вычисления элементарных функций (ЭФ) и другие). Показано что основными способами их реализации в ЭВМ на различных уровнях организации вычислительного процесса являются- программный, микропрограммный и схемный. В качестве возможных способов математического представления рассматриваются: табличный, на основе СБФ, на основе машины Тьюринга Проводится краткий анализ известных форм представления систем булевых функций (СБФ) с учётом используемых средств реализации и оценка математической и технической сложности в зависимости от вида описания. Представление алгоритмов операций преобразования данных в виде СБФ позволяет максимально распараллеливать преобразование данных. Показано что вычислительная сложность операции определяется мощностью входных и выходных множеств и разрядностью входных данных и результатов.. Представление алгоритмов реализации СБФ в форме СДНФ весьма избыточно и что показано на основе некоторых арифметических операций и ЭФ. Делается вывод о необходимости минимизации сложности на основе минимальной и кратчайшей формы СБФ. В качестве реальных средств реализации СБФ в ПЛИС рассматривается применение универсальных логических модулей (УЛМ), в технических терминах это таблицы перекодировки (LUT). Приводятся способы построения СБФ на основе УЛМ от четырёх переменных и способы декомпозиции СБФ для их реализации схемами из УЛМ. Методы и методология исследований включают методы смешанного анализа, методы теории дискретной математики в частности аппарат анализа и синтеза булевых функций, теории алгоритмов, методы вычислительного эксперимента. В статье рассматривается сложность математического представления операций преобразования данных и их реализации в ЭВМ (арифметические вычисления элементарных функций и некоторые другие). Предлагаются алгоритмы реализации СБФ схемой из УЛМ от четырёх переменных и исследуются алгоритмы построения таких схем на основе разложения Шеннона и Рида. На основе анализа входных и выходных переменных операции преобразования данных, синтеза СБФ для формирования проблемно-ориентированных и специализированных команд в ЭВМ. Ключевые слова: Сложность операций, Системы булевых функций, Арифметико-логические формы, Декомпозиция СБФ, Разложение Шеннона, Разложение Рида, ПЛИС, Универсальный логический модуль, Таблицы перекодировки, СДНФУДК: 519.714Abstract: 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] три типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм. Первый тип – рекурсивные функции. Второй тип основан на представлении об алгоритме, как о некотором детерминированном устройстве. Основной теоретической моделью этого типа является машина Тьюринга. Третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки.
Машина ТьюрингаОперация может быть представлена в виде алгоритма и записана на одном из алгоритмических языков. Можно выделить три типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм. Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики – вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа – рекурсивные функции – является исторически первой формализацией понятия алгоритма. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этих моделей близка к ЭВМ и, следовательно, к инженерной интуиции. Основной теоретической моделью этого типа является машина Тьюринга. Наконец третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены фрагмента слова другим словом. Преимущества этого типа – в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (не обязательно числовой) природы. Под алгоритмом понимается процесс последовательного вычисления величин, протекающий в дискретном времени так, что в каждый момент времени система величин получается по определенному закону из системы величин, имевшихся в предыдущий момент. Трудоемкость алгоритма – число элементарных действий, выполняемых при его реализации. Оценку алгоритма можно проводить сверху или снизу. Оценку сверху выполняют, указав конкретный алгоритм решения задачи, т.к. трудоемкость задачи не превышает трудоемкости любого из решающих её алгоритмов. Оценку снизу получают из некоторых общих соображений (например, мощностных или информационных). Сложность алгоритма можно рассматривать по следующим величинам:
Различные формальные модели алгоритмов эквивалентны с точки зрения класса решаемых задач. Следовательно, теорию алгоритмов можно излагать на базе любой из них. Представляет определенный интерес оценка сложности на основе реализации операций машиной Тьюринга. Это обусловлено тем, что машина Тьюринга выполняет исключительно последовательно самые элементарные операции и алгоритмически универсальна. Машина Тьюринга состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Машина работает в дискретные моменты времени t = 0, 1, 2, … В каждый момент времени во всякой ячейке ленты записана буква из конечного алфавита А={а0,а1, … ,аk-1}, называемого внешним алфавитом машины, а головка находится в одном из конечного числа внутренних состояний Q={q0,q1, … ,qm-1}. Пусть а0 является пустым символом (обозначается также L). Наличие этого символа в ячейке означает, что она пуста. В каждый момент времени головка обозревает одну ячейку ленты и, в зависимости от содержимого ячейки и своего внутреннего состояния, заменяет символ в ячейке на новый (Н), возможно прежний, переходит в новое состояние (возможно прежнее), и сдвигается на одну ячейку вправо (П), влево (Л), или остается на месте. Работа машины подчиняется системе команд вида: qiai®qi’ai’S где SÎ{П,Л,Н}. Среди состояний машины особо выделяется одно (условимся, что это состояние q0), называемое заключительным. Если машина в некоторый момент времени оказывается в состоянии q0, то машина прекращает свою работу. Для каждой пары qiai имеется одна команда с левой частью qiai , следовательно, всего имеется k(m-1) команд. Совокупность этих команд называется программой. Оценить сложность функции или операции, для которой известна программа реализации на машине Тьюринга можно следующим образом:
В качестве примеров рассмотрим операцию сложения и вычисление значения булевой функции: а) Сложность операции сложения: Начальная конфигурация: A + B ΛΛΛΛ | |…|*| |…| ΛΛΛΛ Λ Программа вычисления суммы:
После обработки входных данных информация на ленте будет иметь вид: ΛΛΛΛ | |…|ΛΛΛΛ Λ Количество внутренних состояний машины – 4 Количество букв внешнего алфавита машины – 3 Объём программы составляет – 6 команд Количество шагов алгоритма – 2*А+1 б) Сложность вычисления значений булевой функции: Начальная конфигурация:
ΛΛΛΛx1x2…xn*k11k12…k1n*…* km1km2…kmn ΛΛΛΛ Λ где: x1x2…xn – входной набор переменных БФ ki1ki2…kin – единичные наборы БФ Процесс вычисления БФ сводится к поиску единичного набора совпадающего со входным набором переменных. Если такой набор существует, то значение БФ – 1, иначе – 0. Программа вычисления:
 Авторам
Услуги
Наши сайты
 © 1998 – 2024 Nota Bene. Publishing Technologies. NB-Media Ltd.
|
Рус
