Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 83
Текст из файла (страница 83)
Однако представленные в этом параграфе сокращенные версии языка и стили написания программ в общем случае обеспечивают синтезирование большинством программных средств. Но все же от того, как вы напишете программу, сильно зависит качество схемы, которую вы получите в результате синтеза. Приведем несколько примеров. ° Конструкции с «последовательиым» управлением типа 1Г-е1вдй-е1еьбе1ве могут приводить к цепочке последовательно включенных логических схем, проверяющих соответствующие условия.
Если условия являются взаимно исключающими, то лучше использовать операторы саве или ве1есс. Цикл в процессе обычно «разворачивается» в множество копий той или иной комбинационной логической схемы, чтобы обеспечить исполнение этого оператора. Если вы хотите, чтобы эта комбинационная логическая схема была только в одном экземпляре и использовалась последовательно шаг за шагом, то вы должны спроектировать последовательностиую схему; о таких схемах речь пойдет в последующих главах. ° Если вы ошибетесь в условном операторе в процессе, не указав выход для какой-либо комбинации входных сигналов, то это приведет к созданию компилятором «защелки» для удержания старого значения сигнала, который в противном случае мог бы измениться.
В общем случае образование таких защелок нежелательно. Кроме того, в зависимости от реализации программных средств могут оказатьс~ несиитезируемыми и другие элементы и структуры языка. Вам, безусловно„сле- Обзор литературы Збб дует обратиться к документации, чтобы узнать, что запрещено, что разрешено и что рекомендуется в вашем конкретном случае.
В предвидимом будущем проектировщикам, использующим программные средства синтеза, для получения хороших результатов прилете я обратить довольно пристальное внимание на стиль написания своих программ. А в настоящее время критерий «хорошего стиля программирования» в определенной степени зависит как от средств синтеза, так и от технологии микросхем, в которых нужно разместить результат синтеза. Хотя примеры, которые будут приведены в оставшейся части этой книги, будут синтаксически и семантически корректными, они дадуг лишь поверхностное представление о методах написания программ на языках описания схем, которые применяются в больших проектах.
Искусство и практика проектирования больших устройств с использованием языков описания схем все еще находятся в состоянии интенсивного развития. Обзор литературы Историческое описание того, как Буль развивал «науку Логику», появилось в 1972 году в книге Голдстайна Компьютер от Паскаля до фон Неймана (Неппап Н. Счо!дзг!пе. ТЬ« Сотрипт Рот Раз«а! чо «оп Хеитапп. Рппсечоп ()и!иегз!ту Ртезз, ! 972). Шеннон показал, как можно было бы применить работы Буля к логическим схемам ("А ВутЬо!ь«А па!ул!л оТВ«!ау апч! Яч«йсйчпй С!гси!гз".
Тгапз. А1ЕЕ, Чо!. 57, ! 938, рр. 713 — 723; рус. пер. в книге: К. Шеннон. Труды по теории информации и кибернетике. -Мл ИЛ, 1963). Хотя основой алгебры переключений стала двузначная булева алгебра, возможна логика и с бдльшим числом значений. Существуют булевы алгебры с 2" значениями для любого целого и; см., например, Дискретные математическчче структуры и их приложения Стоуна (Наго!д Б. Бгопе. О!«снеге Ма!А«та!!са! Виги«юге« апч! ТЬеа Арр!игабопл. БКА, 1973). Формально такие алгебры могут быть определены с помощью так называемых постулато«Хантингтона, введенных Хантинггоном (Е.Ч. Нппбпй!оп) в 1907 голу; см., например, Цифровое про«кт про«ание Мапо (М. Мопбз Мапо. 0ч8!га! 0«л!8п. Ргепбсе На!1, ! 984), Математическое развитие булевой алгебры на основе современного набора постулатов появилось в 1970 году в книге Бирк тофа и Барти Соврем «иная прикладная алгебра (О.
В!6г)чей апд Т, С. Вштее. Мог!егп АррбеачА!8«Ьга. Мората«ч-Н!П, 1970; рус, перл Г Биркгоф, Т. Барти. Современная прикладная алгебра. — Мл Мир, 1976). В нашем «прямом» развитии алгебры переключений в инженерном стиле мы следуем книгам Мак-Класки Введение в теорию пер«ключ«тельных схем и Принципы логи««ского проектирования (Едч«агд Х. М«С!пз1сеу.
!пггог!исг!оп го гйе ТЬ«огу о7 Зч«!чсЫп8 Счг анук М«Счга» -Н!11, 1965; Ьо8ю Оез!8п Рппсчр!ел. Ргеппсе На)1, 1986). Теорему о простых импликантах доказал Куин (!Ч. Ч. ()пве. "ТЬ« РгоЫ«т оТ Вчтр!!04п8 Тигй Рина!!оп«". Аш. Майч. Моп!!ч1у, Чо!. 59, Ыо. 8, 1952, рр. 521-531). На самом деле можно доказать более обшую теорему о простых импликантах, согласно которой сушествует по меньшей мере одна минимальная сумма, то есть сумма простых и мил икант, даже в случае, когда ограничение на число литералов в определении «минимальный» снято. 356 Глава 4.
Принципы проектыроввнив комбинационных попьческих схем Графический метод упрощения булевых функций был предложен Вейчем (Е, %. Уейсй. "А СЬаг! Ме!Вод (Ьг В!тр!Я!п8 Вою!«ап гипс!1опл". Ргос. АСМ, Мау 1952, рр. 127 — 133). Его диаграмма Вейча, приведенная на рис. 4.53, фактически представляет собой заново изобретенную карту, придуманную английским ар хеоло гам Маркандом (А. Мащцапд. "Оп 1 а8!са! Огайгатл аког п Тегтл".
РЬ йозорЬ! са! Майалпе ХП, 1881, рр. 266 — 270). В диаграмме Вейча и карте Марканда используется «естественный» порядок двоичной нумерации строк и столбцов, в результате чего некоторые смежные строки и столбцы отличаются более чем в одном значе нни и термы-произведения не всегда покрывают смежные клетки.
Карно показал, как решить эту задачу (М. КагпацйЬ. "А Мар Ме!Ьодрог ЯупгЬелм о7 СотЬ!пайопа! !.о8!с Соси!!Р'. Тгапз. А1ЕЕ, Соппп. апд Е!ес!топ., Уо!. 72, Рагт 1, ХочешЬег 1953, рр. 593 — 599). С другой стороны, Клир в своей книге Введение в методологию пер«- ключ атель иых схем (Оеогйе К К! и.
Ме!подо!ойу о~Бич!сЫп8 Спси!!ж Чап Ыозйапд, 1972) утверждает, что для минимизации логических функций двоичный порядок счета так же хорош, как и порядок в карте Карно, а может быть даже и лучше. Рис.4.63.ДиаграммаВейчанпнкартаМаркандадля ччх 4-х переменных чу~ оо о! !о О! 1О На данном этапе аргументы в пользу карт Карно против диаграмм Вейча, конечно, неуместны, поскольку никто больше не вычерчивает никаких карт для минимизации логических схем. Вместо этого мы пользуемся компьютерными программами, реализующими алгоритмы логической минимизации. Первый такой алгоритм описан Куином (%.
Ч. Оц!пе, "А йау !о ЯтрЩ Тги!Ь гипс!!оп«'". Апь МагЬ. Мопй!у, Уо!. 62, Хо. 9, 1955, рр. 627 — 63! ) и усовершенспюван Мак-Кваски (Е. !. МсС1цзйеу."М!и!т(ла!!оп аТВоо1еап гипс!!опз". Вей Буз. ТесЬ. 3., Уо!. 35,Ыо. 5, ХочешЬег 1956, рр. 1417-1444). Алгоритм Кунца — Мак-Кваски нсчерпываюшим образом описан в упомянутых выше книгах Мак-Кваски. В своей книге ! 965 года Мак-Кяаски привел также итеративно-консенсусный алгоритм нахождения простых импликаит н доказал, что он работает.
Отправным моментом в этом алгоритме является логическое выражение вида «сумма произведений» нли, что эквивалентно, список кубов. Термы-произведения не обязательно должны быть минтермами или простыми импликантами, помогут быть чем-то средним между ними. другими словами, в случае функции п переменных кубы в списке могут быть любой размерности, илн всех размерностей, от 0 до п. Начиная с этого списка кубов, авгоритм генерирует список всех кубов, являю шихся простыми имплнкантами функции, не прибегая к составлению полного списка минтермов. Итеративно-консенсусный алгоритм впервые был опубликован Моттом (Т.Н.
МОТТ, 3г. "!Зе!егтта!!ап о(!Ье 1ггег!ипг1ап! фогта! гогтл о~а Тгигд гипс!!оп Ьу Обзор литературы 367 7гегагвд Сапяепяия оТгйе Рпте!тр1!сапгя", 1КЕ Тгаля. Е!есггоп. Сошрп1егз, уо1. ЕС- 9, Но. 2, 1960, рр, 245-252). Затем Тизоном был предложен обобщенный консенсусный алгоритм (Р(егге Тйоп. "бепега1!гаг!ап о7"Сопяепяия Т!явагу апдАррйсапап и гйе М!п1та а!!оп о! Вас!еап рина!гоня". 1ЕЕЕ Тгапз. Е)ее!гоп. Сот рп1егз, Чо1. ЕС- 16, Хо. 4, 1967, рр. 446-456). Все эти алгоритмы описаны в книге ДаунсаЛагичвскав проектирование на 17аскале (Т!зотаз Реваз.
Бой(с Рея!дп ичгй раяса1. Уап 1Чозягапд Кеш(зо! д, 1988). Как мы уже объясняли в разделе 4.4.4, у некоторых логических функций число простых имплнкант бывает огромным, поэтому найти нх все нли выбрать минимальное покрытие на регулярной основе оказывается трудно выполнимым или невозможным. Существуют, однако, эффективные эвристические методы решения, дающие результаты, близкие к оптимальным.
Один из таких методов— Езргеззо 11 — описан в книге Брайтона и др. Алгоритмы логической минимизаиии длл синтеза СВИС (К. К. Вгау1оп, С. МсМп!1еп, О. Р. Нас1пе1, апд А. Бапй!очапш-Ч)псеп1е1!Ь Боя!с М!п1тггаг1ап А!йаНуйтя !аг !ьБТБЗтг!мя(я. К1пячег Асадеш!с РпЬйзйегз, 1984). Более поздние алгоритмы Езргеззо-МУ и ЕзргезяоЕХАСТ описаны Руделлом и Санджованни-Винчентелли (К. Ь. Киде!! впд А, Запй)очапп(-Ч!псепзе1!1. "Ми!г!р!в-'га1ие<3М!п1тааг1оп(ог РЕА 0рг1т!яаг!оп". 1ЕЕЕ Тггпз. САР, Чо!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
