Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 129
Текст из файла (страница 129)
Однако внутри АЛУ микропроцессора эта операция должна выполняться быстрее. В идеале мы бы хотели, чтобы подсчет числа единиц происходил так же быстро, как любое другое арифметическое действие типа сложения двух чисел. Поэтому требуется комбинационная схема.
Предположим в этом примере, что нам требуется создать счетчик числа единиц в 32-разрядном слове как часть более крупной системы. Очевидно, что необходимое число входов и выходов не позволяет нам разьгестить счетчик в одном ПЛУ типа 22Ч10, но мы могли бы разбить устройство на отдельные компоненты для размещения в относительно небольшом числе ПЛУ.
На рис. 6.10 показано такое разбиение. С помощью двух первых идентичных ИС 22Ч10 О[чЕЗС[ЧТ1 осуществляется счет числа единиц в двух 15-разрядных отрезках 32-разрядного входного слова 0[31:О[ с выдачей каждой нз них результата в виде 4-разрядного числа. Следующая ИС 22Ч!0 01»ЕЗС[чТ2 используется для сложения двух полученных 4-разрядных чисел и числа единиц в оставшихся 2-х разрядах входного слова. 0[31:01 811м[4:01 Рис. 6.10. Возможное разбиение схемы счетчика единиц на отдельные компоненты Программа для 01ч ЕВС[чТ1, приведенная в табл. 6.12, обманчиво проста. Операнд "0 Сйкну 1" включен для ОГРаничения цепочки переносов одним разрядом; как объяснялось в разделе 5.10 8, это уменьшает число термов-произведений за счет появления вспомогательных выходов и увеличения задержки.
б 2. Примеры проектирования схем с использованием языка АВЕЬ 579 табл. 5.12. Программа на языке АВЕ1. для подсчета числа разРядов, содер- ;«ащих 1, в 15-разрядном слове яобп1в опввспс1 с1с1е 'Сопле спе опав зп а 15-п11 яокп' ОМЕЯСНТ1 сГет1св 'Р22т'10'; " 1прпс апб опсрпе р1па 014..00 рзп 1..11, 13..16, 23; ЯОМЗ..ЯОМО ркп 17 20 1аеуре 'сое' еопас1опз ЕСАННТ 1; 1ЯОМЯ .ЯОМП1 = 00 + 01 + 02 + 03 + 04 + 05 + 05 + 07 + 08 + 09 + 010 + 011 + 012 + 013 + 0141 епц опввспз1 К сожалению, при компиляции этой программы мой компьютер из-за ограниченных возможностей процессора в течение часа не выдавал никаких результатов. Это дало мне время воспользоваться своей головой — хорошее упражнение для тех из нас, кто стал слишком зависимым от автоматизированных средств проектирования.
Тогда я понял, что для выхода ЯОМС могу записать логическую функцию вручную всего лишь за несколько секунд: 811МО= ПО Э 01 9 02® 03 от 04®05® 06 ЭП7® ... Ю 013®014. Карта Карно для этой функции выглядит как шахматная доска, и минимальное выражение в виде суммы произведений содержит 2'4 термов-цроизведений. Очевидно, что это невозможно реализовать за один или несколько проходов через ИС 22Ч!0! Так или иначе, я прекратил процесс компиляции и перезагрузил 1Ч1пдозтз на тот случай, если компилятор что-то испортил.
Понятно, что для создания схемы, подсчитывающей число единиц, требуется разделение на небольшие блоки. Хотя мы могли бы и дальше продолжить пользоваться языком АВЕЬ в расчете на реализацию в нескольких ПЛУ, но интереснее выполнить структурное проектирование такого устройства, пользуясь средствами ЧНПЬ, как это и будет сделано в разделе 6.Ь.6, а вариант с языком АВЕЬ и микросхемами ПЛУ пусть останется в качестве задачи 6.6. 6.2.7. Игра в крестики и нолики В этом примере мы построим комбинационную схему, которая выбирает очеРедной ход в игре в крестики и нолики. Прежде всею нужно решить, какой будет стратегия выбора очередного хода.
давайте попробуем подражать типичной стратегии человека, который принимает решения по шагам: Ищем строку, столбец или диагональ, где имеются две наши метки (Х или 0 в зависимости от того, на чьей мы стороне) и одна пустая клетка. Если такая ситуация обнаруживается, то помещаем свою метку в эту пустую клетку.
Мы победили! б80 Глава б. Примеры проектирования комбинационных схем ПРАВИЛА ИГРЫ В КРЕСТИКИ И НОЛИКИ (НА СЛУЧАЙ, ЕСЛИ ВЫ НЕ ЗНАЕТЕ) Игра в крестики и нолики ведется двумя игроками на поле, разбитом на клетки, по 3 клетки в каждой строке и в каждом столбце. Первоначально клетки пустые. Один игрок выбирает себе в качестве метки крестик Х, а другой — нолик О. Игроки поочередно ставят свои метки в одной из пустых клеток; игрок Х всегда начинает первым. Победителем считается тот, кто первым заполнит своими метками три клетки подряд в строке, в столбце или по диагонали.
Хотя у игрока Х, начинающего игру, есть небольшое преимущество, можно показать, что игра между двумя сообразительными игроками всегда заканчивается вничью: ни один игрок не поставит три метки подряд к моменту, когда поле заполнится. 2. Ищем строку, столбец или диагональ, где имеются две метки противника и одна пустая клетка. Если такая ситуация обнаруживается,'то помещаем свою метку в эту пустую клетку, чтобы блокировать возможный выигрыш противника.
3. Выбираем клетку, руководствуясь своим опытом. Например, если центральная клетка пустая, то обычно стоит заполнить ее. В противном случае полезно заполнять угловые клетки. Умный игрок может заметить также и блокировать развитие конфигурации противником или выбрать хороший ход благодаря «предвиденитот>.
1 3 стоааач Рис. 6.11. Поле для игры в крестики и нолики и имена сигналов в программе на языке АВЕЕ строка Заранее предвидя путаницу между символом О и нулем 0 в наших программах, мы, во избежание неприятностей, назовем второго игрока буквой у. далее, нужно подумать о том, как следует кодировать входные и выходные сигналы в разрабатываемой схеме. У каждого игрока существует только девять возможных ходов, поэтому для представления выходных сигналов достаточно четырех двоичных разрядов.
Входными сигналами схемы служит текущее состояние игрового поля. Каждая из девяти клеток, может находиться в одном из трех со- стояний (пустая, заполненная меткой Х, заполненная меткой у), Можно различными способами отобразить состояние одной клетки. Поскольку игра симметрична, выберем симметричное представление, которое поможет нам в дальнейшем: б 2.
Примеры проектирования схем с использованием языка АВН. 581 КОМПАКТНОЕ КОДИРОВАНИЕ Так как каждая клетка в этой игре может находиться только в одном нз трех состояний, а не из четырех, общее число игровых конфигураций составляет 3 = 19683. Это число меньше, чем 2, поэтому состояние' поля можно и кодировать всего 15-ю разрядами. Однако в этом случае схема, выбирающая очередной ход, была бы слишком сложной, если только функции такой схемы не поручить ПЗУ (см. задачу 10.26). 00 — клетка пуста; 10 — клетка занята меткой Х; 01- клетка занята меткой у.
Рис. б.12. Предварительное разбиение на блоки схемы для реализации игры в крестики и нолики моче!3 О! твом пав х1!.хзз тн-тзз Таким образом, состояние поля размером ЗхЗ можно кодировать 18-ю битами. Будем обозначать клетки двумя числами, указывая номер строки и номер столбца, как это сделано на рис.
6.11, а в программе на языке АВЬЬ будем использовать символы Хз 3 и уз 3 при наличии метки Х или у в клетке з, 3. Кодирование выходных сигналов давайте рассмотрим позже. Схема с! 8 входами и 4 выходами, играющая в крестики и нолики, могла бы, в принципе, разместиться в одной ИС 22Ч ! О. Однако опыт показывает, что этого сделать нельзя.
Поэтому функцию, реализуемую схемой в целом, необходимо разбить на части. Сделать это можно в соответствии с тем, как игрок принимает решение по шагам, и мысль эта выглядит неплохой идеей. Иа самом деле, шаги 1 и 2 очень похожи; они отличаются только тем, что игроки меняются ролями. Именно поэтому может оказаться полезным симметричное кодирование.
ПЛУ, которое находит две мои метки подряд и пустую клетку для победного хода (шаг 1), может найти также две метки моего противника подряд и пустую клетку для выполнения блокирующего хода (шаг 2). Все, что нам надо сделать, — это переставить коды меток Х и У, При выбранном нами способе кодирования, не требующем никакой логики, достаточно во всех клетках физически поменять местами сигналы Хз3 и уз3. С учетом этого для выполнения шагов 1 и 2 можно воспользоваться двумя одинаковыми ПЛУ ТтЧО!!!!!Отт', как показано парис.
6.12. Обратите внимание, что сигналы хауз-х3 3 поданы на верхние входы первого ПЛу ТтЧОйч!ЗО)Л/ и на нижние входы второго ПЛУ. 582 Глава 6. Примеры проектирования комбинационных схем Сигналы с выходов двух ПЛУ ТЧЧЮМЧРОЧЧ пусть поступают на входы еще одного ПЛУ Р! СК. Если хотя бы одним нх двух первых ПЛУ найден ход, то блоком Р!СК он передается на выход; в противном случае этим устройством выполняется шаг Э. Похоже, что у блока Р!СК слишком много входов и выходов и его нельзя реализовать в ИС 22Ч!0, но мы вернемся к этому позже.
В табл. 6. ! 3 представлена программа для ПЛУ ТИЮ!МРОЧЧ. В ней анализируется состояние игрового поля с точки зрения игрока Х; другими словами, ищется ход, при котором метка Х будет занимать трн идущие подряд клетки. В этой программе активно используются промежуточные равенства для определения всех возможных ходов по строкам, столбцам и диагоналям. В выражении для С[з объединяются все условия, при которых ход в клетку 1, з (ее заполнение меткой Х) будет правильным ходом. Наконец, в разделе ес!оагзопз с помо!цью оператора МНЕМ выбирается нужный ход. Табл.
б.1З. Программа иа языке АВЕ( дяя нзхохщпиия двух меток подряд при игре п креовпки и нолеги еоаи1е Сяо1пгоя Т1с1е 'Р1пй Тяо Хв апй аи еврсу се11 Хп а гоя, со1иши, ог п1абоиа1' Т701МДОЧ аетйсе 'Р22710'; 1приив епа Патриса Х11, Х12, Х13, Х21, Х22, Х23, ХЭ1, Х32, ХЭЗ рйп 1,.9; 711, 712, 713, 721, 722, 723, 731, 732, ЧЗЗ р1п 10,11,13..16,20..23; МОЧЕЗ..МОЧЕО рйп 16..19 1вяуре 'сов'; " М07Е еигрие епсой1ибв МОЧЕ [МОЧЕЗ..МПЧЕ02! МОЧЕ11 [1,0,0,03! МОЧЕ12 [0,1 0 0)! М07Е21 [0.0.0,13; МПЧЕ22 [1,1,0,03; МП7ЕЗ1 [1,0.1,1]; МОЧЕ32 [1,1,0,11; МПМЕ = [0,0,0,02; МОЧЕ13 [0,0,1.02; МОЧЕ23 [0,1,1,11; МП7ЕЗЗ [1, 1, 1,03 ! " Рйид потев Хи Р11 Х12 й Х13 312 = Х!1 й Х13 Р13 Х11 й Х12 Е21 = Х22 й Х23 322 Х21 й Х23 323 Х21 й Х22 ЕЭ1 ХЗ2 й ХЭЗ Е32 ХЗ1 й ХЗЭ ЕЗЭ Х31 й Х32 Еху => а ноте ех1егв 1п се11 ху й !711! й !712; й !713! й !721; й !722! й !723; й !731; й !732! й !733; со1иепв.
й !Х11 й й !Х12 й й !Х13 й й !Х21 й й !Х22 й й !Х23 й й !Х31 й " Р1по потев Хп С11 Х21 й Х31 С12 = Х22 й ХЗ2 С13 Х23 й ХЗЭ С21 Х11 й Х31 С22 = Х12 й Х32 С2Э Х13 й ХЭЗ С31 = Х11 й Х21 гоев. й !Х11 й !Х12 й !Х13 й !Х21 й !Х22 й !Х2Э й !ХЗ1 й !Х32 й !ХЗЭ Сху > а поте ех1асв 1п се11 ху !711; !712; !713; !721; !722; !723; !731; б 2.
Примеры проектирования схем с использованием языка АВЕь 583 Табл. 6.13. Программа на языке АВЕК для нахождения двух меток подряд при игре в крестики и нолики (продолжение) СЗ2 Х12 й Х22 й !Х32 й !У32; СЗЗ - Х1З й Х2З й !ХЗЗ й !УЗЗ; Ч1па потев тп 011 = Х22 й ХЗЗ 022 = Х11 й ХЗЗ 033 Х11 й Х22 Е13 = Х22 й Х31 Е22 = Х13 й Х31 ЕЗ1 = Х13 й Х22 Сху ==> а аотв еххвск 1п се11 ху ес)па11опа МНЕМ С22 ТНЕМ МОЧЕ-" МРЧЕ22; ЕЬЯЕ МНЕМ С11 ТНЕМ МОЧЕ МОЧЕ11; ЕЬЯЕ МНЕМ С13 ТНЕМ МОЧЕ МОЧЕ13; ЕЕЯЕ МНЕМ С31 ТНЕМ МОЧЕ " МОЧЕЗ1!' ЕьБЕ МНЕМ СЗЗ ТНЕМ МОЧЕ МОЧЕЗЗ; ЕЕЯЕ МНЕМ С12 ТНЕМ МОЧЕ МОЧЕ12; Е1.БЕ МНЕМ С21 ТНЕМ МОЧЕ = МОЧЕ21; НАБЕ МНЕМ С23 ТНЕМ МОЧЕ = МОЧЕ23„ Е)-БЕ МНЕМ СЗ2 ТНЕМ МОЧЕ МОЧЕ32; Е1.ЯЕ МОЧЕ МОНЕ; еп4 Сяойпгоя Обратите внимание, что необходимо использовать еложеннь!й оператор МНЕМ, а не девять параллельных операторов НН ЕМ или присваиваний, поскольку выбрать нужно только один ход, даже если имеется несколько возможностей. Заметьте также, что первой проверяется центральная клетка 622, а потом — угловые клетки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
