9.3.2. Роль свойств декодеров высоких порядков

Полная таблица истинности для двоичной системы с входами содержит строк, по одной на каждую возможную комбинацию входных сигналов. Обозначая номер строки получим, что полное число возможных функций выходного сигнала по оценкам составляет ошеломляющую величину — Степень сложности этих функций различается весьма значительно. Один из способов определения степени сложности функций заключается в проведении для этих функций процедуры логической минимизации и сравнения числа полученных вариантов. Это число также позволяет определить требуемый коэффициент разветвления по выходу. Термин «функциональная сложность» уместен лишь для двузначных ПЛМ, т. е. для ПЛМ с -разрядным декодером, и он не подходит для используемых декодеров высших порядков. Для случая декодеров высших порядков необходимо дать определение дополнительной величине, получившей название «сложности вычислений». Это понятие будет применяться для обозначения минимизированного числа логических функций, получаемых в случае использования -разрядных декодеров. Представленные ниже данные позволят продемонстрировать тот факт, что для определенного уровня функциональной сложности сложность вычислений также может значительно различаться (в том случае, если используются декодеры высших порядков).

Чтобы оценить целесообразность применения декодеров высших порядков с точки зрения вычислительной сложности, удобно работать с набором функций, имеющих предсказуемый рост сложности по мере увеличения числа входных переменных. Одним из примеров таких наборов функций являются пороговые функции. Эти функции представляют интерес и по той причине, что они могут быть использованы для реализации обычной логики. Математический аппарат пороговой логики принципиально отличается от булевой алгебры, тем не менее теоретически возможно получить любую булеву функцию в рамках подхода пороговой логики. Данный метод является привлекательным, так как он может привести к значительной экономии числа логических вентилей и снижению требований к числу межэлементных соединений. К сожалению, недостаточный уровень развития универсальных методик получения пороговых функций ограничил степень практической полезности этого подхода [30];

тем не менее с его помощью может быть оптически реализован ряд булевых функций [31]. И наоборот, возможно получить любую пороговую функцию с помощью методов минимизации в стандартной булевой логике. Указанный процесс логической минимизации представляет собой универсальную методику синтеза, обычно называемую синтезом в исследовании операций. Недавно на основе ОПЛМ был разработан и реализован полностью программируемый генератор пороговых функций (называемый также программируемым вентилем) [13].

Пороговая функция может быть получена при вычислении внутреннего произведения весового вектора и вектора входного сигнала, а также порогового кодирования результата. Эту функцию удается получить путем ограничения входных сигналов двоичными числами и полагая все весовые множители равными единице; в этом случае она равна сумме входных сигналов, подвергнутых пороговому кодированию. Для любого произвольного числа переменных входного сигнала данная функция может быть получена с помощью методов минимизации обычной булевой логики, что дает определенное число комбинаций или термов произведения. Одним из забавных свойств пороговых функций, как было замечено автором данной главы, является то, что один или большее число термов произведения, полученных за счет приравнивания всех весовых коэффициентов единице, представляет собой не что иное, как одну из возможных пороговых подфункций. При этом пороговые подфункции могут быть получены в предположении, что любая комбинация весовых коэффициентов принимает значения либо 0, либо 1. Тогда случай единичных весовых коэффициентов представляет максимально возможную функциональную сложность для случая -разрядных весовых коэффициентов. В табл. 9.1 представлен ряд значений минимизированных термов произведения для случая -разрядных входных сигналов с единичными весовыми коэффициентами, являющимися функциями полного числа переменных входного сигнала, значений порога и степени сложности декодера.

Данные, представленные в табл. 9.1, вполне заслуживают внимания, поскольку представляют собой первую попытку строгого исследования процесса синтеза ряда пороговых функций в рамках булевой логики, применительно к декодерам с увеличивающейся степенью сложности. Эти данные были получены в результате длительных расчетов по алгоритму ESPRESSO. При проверке данных видно, что для определенного числа входных переменных и -разрядных декодеров необходимое число минимизированных термов произведения, связанных с каждым из возможных значений порога, может быть получено с помощью биномиальных коэффициентов. Это соответствует числу возможных комбинаций из М переменных,

(кликните для просмотра скана)

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

Для каждой группы переменных входного сигнала возможные пороговые значения могут рассматриваться как дополнительные входы в большую таблицу истинности, образующую макрофункцию. Эта макрофункция является в значительной мере программируемой униполярной пороговой функцией [13]. Данная макрофункция, связанная с каждой группой переменных входного сигнала, представляет определенный уровень функциональной сложности. Сложность вычислений, требуемая для синтеза данной функции, может быть определена путем суммирования всех произведений вдоль определенной строки в табл. 9.1. Результаты указаны в столбце, именуемом «коэффициент разветвления по выходу». Из представленных в данном столбце данных становится очевидным, что сложность вычислений коэффициента разветвления по выходу, связанная с каждым значением переменных входного сигнала, уменьшается монотонно с ростом сложности декодера. Как отмечалось ранее, не является удивительным тот факт, что число термов произведения должно в конечном счете равняться одному терму на один выходной канал в том случае, когда входной сигнал полностью декодируется. Один из негативных моментов, связанный с использованием декодеров высших порядков, заключается в сопутствующем увеличении коэффициента объединения по входу. В следующей части раздела будет показано, что существует оптимальный уровень сложности декодера, связанный с достижением компромисса между коэффициентами объединения по входу и разветвления по выходу. Этот оптимальный уровень сложности декодера задает минимум требований в отношении сложности вычислений, сводя к минимуму затраты мощности и энергии на проведение конкретных вычислений.