(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation дует обратиться к документации, чтобы узнать, что запрещено, что разрещено и что рекомендуется в вашем конкретном случае. В предвидимом будущем проектировщикам, использующим программные средства синтеза, для получения хороших результатов придется обратить довольно пристальное внимание на стиль написания своих программ. А в настоящее время критерий хорошего стиля программирования в определенной степени зависит как от средств синтеза, так и от технологии микросхем, в которых нужно разместить результат синтеза. Хотя примеры, которые будут приведены в оставшейся части этой книги, будут синтаксически и семантически корректными, они дадут лишь поверхностное представление о методах написания программ на языках описания схем, которые применяются в больших проектах. Искусство и практика проектирования больших устройств с использованием языков описания схем все еще находятся в состоянии интенсивного развития. Обзор литературы Историческое описание того, как Буль развивал науку Логику , появилось в 1972 году в книге Голдстайна Компьютер от Паскаля до фон Неймана (Herman Н. Goldstine. The Computer from Pascal to von Neumann. Princeton University Press, 1972). Шеннон показал, как можно было бы применить работы Буля к логическим схемам ( А Symbolic Analysis of Relay and Switching Circuits . Trans. AIEE, Vol. 57, 1938, pp. 713-723; рус. пер. в книге: К. Шеннон. Труды по теории информации и кибернетике.-М.: ИЛ, 1963). Хотя основой алгебры переключений стала двузначная булева алгебра, возможна логика и с большим числом значений. Существуют булевы алгебры с 2 значениями для любого целого я; см., например, Дискретные математические структуры и их приложения Стоуна (Harold S. Stone. Discrete Mathematical Structures and Their Applications. SRA, 1973). Формально такие алгебры могут быть определены с помощью так называемых постулатов Хантингтона, введенных Хантингтоном (Е. V. Huntington) в 1907 году; см., например. Цифровое проектирование Мано (М. Morris Мало. Digital Design. Prentice Hail, 1984). Математическое развитие булевой алгебры на основе современного набора постулатов появилось в 1970 году в книге Биркгофа и Барти Современная прикладная алгебра (G. Birldioff and Т. С. Bartee. Modern Applied Algebra. McGraw-Hill, 1970; рус. пер.: Г. Биркгоф, Т. Барти. Современная прикладная алгебра. - М.: Мир, 1976). В нашем прямом развитии алгебры переключений в инженерном стиле мы следуем книгам Мак-Класки Введение в теорию переключательных схем и Принципы логического проектирования (Edward J. McCluskey. Introduction to the Theory of Switching Circuits.McGra\N-H\l\, 1965; Logic Design Principles.VrenticeUaW, 1986). Теорему о простых импликантах доказал Куин (W. V. Quine. The Problem of Simplifying Truth Functions . Am. Math. Monthly, Vol. 59, No. 8,1952, pp. 521-531). Ha самом деле можно доказать более общую теорему о простых импликантах, согласно которой существует по меньшей мере одна минимальная сумма, то есть сумма простых импликант, даже в случае, когда ограничение на число литералов в определении минимальный снято.
На данном этапе аргументы в пользу карт Карно против диафамм Вейча, конечно, неуместны, поскольку никто больше не вычерчивает никаких карт для минимизации логических схем. Вместо этого мы пользуемся компьютерными про-фаммами, реализующими алгоритмы логической минимизации. Первый такой алгоритм описан Куином (W. V. Quine. 4 Way to Simplify Truth Functions . Am. Math. Monthly, Vol. 62, No. 9,1955, pp. 627-631) и усовершенствован Мак-1Сласки (E. J. McCluskey. Minimization of Boolean Functions . Bell Sys. Tech. J., Vol. 35, No. 5, November 1956, pp. 1417-1444). Алгоритм Куина-Мак-Класки исчерпывающим образом описан в упомянутых выше книгах Мак-Класки. В своей книге 1965 года Мак-Класки привел также итеративно-консенсусный алгоритм нахождения простых импликант и доказал, что он работает. Отправным моментом в этом алгоритме является логическое выражение вида сумма произведений или, что эквивалентно, список кубов. Термы-произведения не обязательно должны быть минтермами или простыми импликантами, помогут быть чем-то средним между ними. Другими словами, в случае функции п переменных, кубы в списке могут быть любой размерности, или всех размерностей, от О до п. Начиная с этого списка кубов, алгоритм генерирует список всех кубов, являющихся простыми импликантами функции, не прибегая к составлению полного списка минтермов. Итеративно-консенсусный алгоритм впервые был опубликован Моттом (Т.Н. МОТТ, Jr. Determination of the Irredundant Normal Forms of a Truth Function by Графический метод упрощения булевых функщ1й был предложен Вейчем (Е. W. Veitch. А Chart Method for Simplifying Boolean Functions . Proc. ACM, May 1952, pp. 127-133). Его диаграмма Вейча, приведенная на рис. 4.53, фактически представляет собой заново изобретенную карту, придуманную английским археологом Маркандом (А. Marquand. Оя Logical Diagrams for п Terms . Philosophical Magazine ХП, 1881, pp. 266-270). В диафамме Вейча и карте Марканда используется естественный порядок двоичной нумерации строк и столбцов, в результате чего некоторые смежные строки и столбцы отличаются более чем в одном значении и термы-произведения не всегда покрывают смежные клетки. Карно показал, как решить эту задачу (М. Karnaugh. 4 Map Methodfor Synthesis of Combinational Logic Circuits . Trans. AIEE, Comm. and Electron., Vol. 72, Part I, November 1953, pp. 593-599). С другой стороны. Клир в своей книге Введение в .методологию переключательных схем (Geoige i. Klir. Methodology of Switching Circuits. Van Nostrand, 1972) утверждает, что для минимизации логических функций двоичный порядок счета так же хорош, как и порядок в карте Карно, а может быть даже и лучше. Рис. 4.53. Диаграмма Вейча или карта Марканда для 4-х переменных Iterated Consensus of the Prime Implicants . IRE Trans. Electron. Computers, Vol. EC-9, No. 2, I960, pp. 245-252). Затем Тизоном был предложен обобщенный консен-сусный алгоритм (Pierre Tison. Generalization ofConsensus Theory and Application to the Minimization of Boolean Functions . IEEE Trans. Electron. Computers, Vol. EC-16, No. 4,1967, pp. 446-456). Bee эти алгоритмы описаны в книге ДаунсаЛогмчес-кое проектирование на Паскале (Thomas Downs. Logic Design with Pascal. Van Nostrand Reinhold, 1988). Как мы уже объясняли в разделе 4.4.4, у некоторых логических функций число простых импликант бывает огромным, поэтому найти их все или выбрать минимальное покрытие на регулярной основе оказывается трудно выполнимым или невозможным. Существуют, однако, эффективные эвристические методы решения, дающие результаты, близкие к оптимальным. Один из таких методов -Espresso II - описан в книге Брайтона и др. Алгоритмы логической минимизации для синтеза СБИС (R. К. Brayton, С. McMullen, G. D. Hachtel, and А. Sangiovanni-Vincentelli. Logic Minimtation Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984). Более поздние алгоритмы Espresso-MV и Espresso-EXACT описаны Руделлом и Санджованни-Винчентелли (R. L, Rudell and А. Sangiovanni-Vincentelli. Multiple-Valued Minimization for PLA Optimization . IEEE Trans. CAD, Vol. CAD-6,No. 5,1987, pp. 727-750). В этой главе мы рассмотрели метод нахождения статических источников опасности в двухуровневых схемах И-ИЛИ и ИЛИ-И по картам Карно. Задача поиска источников опасности может возникнуть в отношении любой комбинационной схемы. В своих книгах 1965 года и 1986 года Мак-Класки вводит понятия О- и 1-совокупностей литералов (0-sets, 1-sets) для конкретной схемы и показывает, как с их помощью можно находить статические источники опасности; там же вводятся P-KS-совокупности (P-sets, S-sets), позволяющие находить динамические источники опасности. Существует много более глубоких и разнообразных аспектов теории переключений, которые в этой книге опущены, но в деталях разбираются в других книгах и публикациях. Хорошим началом в изучении классической теории переключений может служить книга Кохави Теория переключательных схем и конечных автоматов (Zvi Kohavi. Switching and Finite Automata Theory, second edition. McGraw-Hill, 1978), которая включает теорию множеств, симметричные цепи, функциональную декомпозицию, пороговую логику, обнаружение неисправностей и активизацию тракта проверки логической схемы. Другой областью, представляющей большой академический (но незначительный коммерческий) интерес, является m}xвoшнaямнoгoзнaчнaялoгuкa(multiple-valuedlogic), в которой каждый сигнал может принимать более двух значений. Хорошее введение в многозначную логику содержится в книге Мак-Класки 1986 года, где приводятся все за и против и объясняется, почему она с трудом находит коммерческое применение. Годами я бился в поисках доступного и надежного источника сведений о языке ABEL и, наконец, нашел: приложение А в книге Пеллерина и Холли Цифровое проектирование на языке ABEL (David Pellerin and Michael Holley. Digital Design Using ABEL. Prentice Hall, 1994). Данный источник следует считать, по-видимому, самым авторитетным: именно Пеллерин и Холли придумали этот язык и напи- ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |
||||||||||||||||||||||||||