Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 136
Текст из файла (страница 136)
В этом примере предполагается, что нам надо построить комбинационную схему, считающую число единиц в 32-разрядном двоичном слове, которая могла бы быть частью арифметическо-логического устройства микропроцессора. Подсчет числа единиц совсем нетрудно описать в поведенческой ЧН0).-программе, как это видно из табл. 6.33.
Эта программа вполне синтезируема, но результатом синтеза может оказаться очень медленная и неэффективная реализация, состоящая из 32 последовательно включенных 5-разрядных сумматоров. Чтобы синтезировать счетчик числа единиц с лучшими параметрами, необходимо приду мать экономичную струк)у ру и затем описать ее в виде архитектуры. Такой структурой является дерево сумматоров, показанное на рис. 6.15. Полный сумматор (ЕА) выполняет сложение трех входных битов, вырабатывая 2-разрядную сумму.
Пары 2-разрядных чисел складываются с помощью 2-разрядных сумматоров А00ЕВ2, у каждого нз которых имеется вход переноса, позволяющий добавить к сумме значение еще одного бита. Полученные 3-разрядные суммы объединяются 3-разрядными сумматорами А00ЕВЗ„а последняя пара 4-разрядных сумм складывается в 4-разрядном сумматоре А00ЕВ4. С учетом сигналов, подаваемых на входы переноса, эта древовидная структура обеспечивает подсчет числа единица 31 Разряде При наличии единицы в оставшемся входном разряде это обстоятельство учитывается с помощью отдельного 5-разрядного устройства 1МСЙБ увеличения числа на единицу 6 3.
Примеры проектирования с использованием языка ЧНОЬ 607 1хЬтвту 1ЕЕЕ; пзе 1ЕЕЕ.зкг[ 1о31с 1134.а11; пзе ТЕБЕ.зхй 1обхс ппз13пес.а11; епкхЬУ 7слс18 хз роте ( О: 1п ЯТО 10010 7ЕСТОК (31 Лозпко О); ЯОН: опк ЯТО ЬОИС 7ЕСТОК (4 совпсо О) ); епа 7спе1з) атсьхсессите 7спс1в ексь ог 7спв1з 1з ЬеЕзп ргосезз (О) тат1аЬ)е Я'. ЯТО 1001С 7ЕСТОК(4 4[скоко О); Ьеяхп Я : "00000"; Хот х хп 0 «о 31 1оор 11 О(1) = '1' ЬЬеп Я := 3 + "00001"; епс 11) епа 1оор; ЯОИ <= Я; епс ртосезз; епо 7спк1з агсЬ; О(24) — ) о[г:о) ==Ь~:д ~д-Т ДЙР Аооенг О[ге)-) О(з:з[ =О ЕА , о(28) О[8:61 =ф~П,:А Д[=-~ з г АООЕН2 О[":8) =>[)гкфу~ , О(281- о[14пг) ==ОБА..Д~Ь АООЕЯ2 орт 18[=Ф[рс, ~сФ О[27) — ) ороп8) — ~Яд-) АООЕН2 О(гз:21) -ф~: Е фГО имена 2(84[ко) О(о:81(г:о) [зо).
о[зй- 4 6 Аооекв гнснз ЗОМ[5:О) з[4:81 (з:о) и[оп сигналов рис. 6.15. Структура 32-разрядного счетчика числа единиц Устройство, изображенное на рнс. 6.15, отлично создается структурной ЧН()(-архитекгурой, приведенной в табл. 6.34. Программа начинается с объявления всех компонентов, которые будут использованы в проекте, соотзетстзукхших блокам на рисунке.
Табл„6.33. Поведенческая ЧНОЬ-программа для счетчика числа единиц в 32-разрядном слове 608 Глава 6. Примеры проектирования комбинационных схем Табл. 6.34. Структурная ЧН0(.-архитектура для 32-Разрядного счетчика чис- ла единиц пгсвксессиге чспс1есг агск ох чспс1асг (в сошропепС РА ротс ( А„ В, С1: 1п ЯТР 00010; Я, СО: опс ЯТР 10010 ); епа сошропепс; сошропепс АРРЕВ2 рогС ( А, В: Ап ЯТР 10010 ЧЕСТОК(1 аоепго О); С1: Ап БТР 00010; Б: опс БТР СОС1С ЧЕСТОВ(2 Сокпсо О) ); епа сокропепс; сошропепс АРРЕКЗ ротс ( А, В: 1п ЯТРЛОС1С ЧЕСТОК(2 аоъпго 0); С1: Ап ЯТ0„10010; опС ЯТОЛОС1С„ЧЕСТОВ(3 аояпго 0) ); епд сошропвпс; сошропепс АРОЕК4 рогС ( А, В: Ап ЯТРЛОС10 ЧЕСТОК(З Совпсо О); С1: 1п БТР 1001С; Я: опС ЯТРЛОС1С„ЧЕСТОК(4 Сового О) ); епо сопропепс; сошропепс 1БСВВ роге ( А: 1п БТО 1.001С ЧЕСТОВ(4 аоъпсо 0); С1: 1п БТО 10010; Я: опс БТО ЬОСХС ЧЕСТОК(В ооъпго О) )) епе соаропепс; суре Рсуре 1в аггау (О со ?) о1 БТР 10010 ЧЕСТОВ(1 оокпсо О); суре Цсуре 1в астау (О со 3) о1 ЯТО 1001С ЧЕСТОВ(2 ооепсо О); суре Муре 1в актау (О со 1) от БТР 00010 ЧВСТОК(3 дояпсо О); взепа1 Р: Рсуре; е13па1 Ц: Цсуре; е13па1 к: муре; е1Бпа1 Я: ЯТР 10010 ЧЕСТОК(4 аояМо О); Ье31п 01: Хог 1 Ап 0 со 7 Бепегасе 01С: РА ротс шар (0(зь1), 0(Зе1+1), Р(Зь1+2), Р(1) (О), Р(1) (1) ) ' епд Бепегасе; 02: тот 1 1п 0 Со 3 Еепегаге 02С: АРРЕК2зРогс шар (Р(2е1), Р(2е1+1), Р(24+1), Ц(1)); епа Еепегазе; 03: (ог 1 Ап с со 1 Бепегасе ОЗС: АРРЕВЗ рогС шар (Ц(2ь1), Ц(2ь1+1), 0(23 1), В(1)); епо Бепегасе; 04: АРРЕК4 рогС шар (В(О), В(1), 0(ЗО), Б); 03: 1ЪСВЯ рогС шар (Я, 0(31), БРЕ); епа ЧсоС1есг агсп; Под каждым столбцом сигналов в схеме на рис.
6,15 указано имя, присвоенное этой совокупности сигналов в пРогРамме. Каждый из сигналов Р, О и  — это массив, позволяющий представить все соединения в соответствующем столбце в виде одного вектора типа Ят0 1001с честОВ. Объявлению этих сигналов в программе предшествует определение соответствующих типов. 6 6. Примеры проектирования о использованием языка ЧНОЕ 609 В этой программе создание однотипных сумматоров — восьми полных сума,оров РА, четырех сумматоров Ас()ЕВ2 и двух сумматоров АОРЕВЗ вЂ” успешно осуществляется операторами депегасе, а затем происходит обращение к компонентам АРРЕН4 и 1НСЕ5.
Определение компонентов счетчика числа единиц в виде отдельных обьектов и архитектур, начиная с полногО СуММатОра ГА и кончая устройством 1НСН увеличения числа на 1, можно сделать в отдельных структурных или поведенческих программах. Например, в табл. 6.35 приведена структурная программа для полного сумматора ЕА. Описание остальных блоков оставлено в качестве задач 6.20 — 6.22. Табл. 6.36. Структурная 1/НВЕ-программа для полного сумматора 116гагу 1ЕЕЕ „ пее 1ЕЕЕ.асс 1ойзс 1164.а11; епсяху РА 1в ротЕ ( А, В, С1: зп ЯТ0 1001С; Я, С0: опс ЯТ0 1.001С ); епп ГА; агспзсесхиге ГА ахсй оХ ГА за ЬеЕ1п 3 < А хоп В хох СХ; СС <= (А апп В) ох (А апп С1) ог (В апа С1); епй РА агсп; 6.3.7. Игра в крестики и нолики Наш последний пример состоит в проектировании комбинационной схемы, которая выбирает очередной ход игрока в игре в крестики и нолики.
Те, кто не знаком с этой игрой, могут прочитать правила, приведенные в разделе 6.2.7. Здесь мы повторим нашу стратегию игры с целью достижения победы: 1. Ищем строку, столбец нли диагональ, в которых имеется две наших метки (Х или О в зависимости от того, за кого мы играем) и одна пустая клетка. Если такая комбинация существует, то помещаем свою метку в пустую клетку. Мы выиграли! 2. В противном случае ищем строку, столбец или диагональ, в которых имеется лве метки противника и одна пустая клетка. Если такая комбинация обнаруживается, то помещаем свою метку в пустую клетку, чтобы блокировать возможную победу противника. Если не найдены две предыдущие комбинации, то выбираем клетку «на основании опыта».
Например, если свободна центральная клетка, то обычно хорошим ходом является ее занятие. Другими хорошими ходами считается занятие Угловых клеток. При выборе хода умные игроки могут также принять во внимание развитиее конфигурации противником и заблокировать его, воспользовавшись «предаидением».
еюе ~нее» е. ззримеры проектировании компинационных схем Чтобы избежать путаницы в наших программах между символами "0*' и "0", присвоим второму игроку имя ' ~". Теперь можно подумать о том, как кодировать входные и выходные сигналы схемы. Входные си~палы — это текущее состояние игрового поля. Всего в игровом поле девять клеток и каждая клетка находится в одном из трех возможных состояний (пустая, заполненная меткой Х, заполненная меткой У).
Выходной сигнал — это ход, который надо сделать; предполагается, что очередной ход за игроком Х. Игроку предстоит сделать только один из девяти возможных ходов, так что для представления выходного сигнала достаточно четырех битов. Можно несколькими способами кодировать состояние одной клетки. Поскольку игра симметрична, выберем симметричное кодирование: 00- клетка пуста; 10 — клетка занята меткой Х; 01- клетка занята меткой У. Такое представление поможет нам позднее. Итак, состояние игрового поля размером ЗхЗ можно представить 18-ю битами.
Поскольку язык ЧНР1. поддерживает массивы, полезно определить тип массива ТТТог1с), элементы которого соответствуют клеткам игрового поля, Так как мы повсюду в нашем проекте будем использовать этот тип, удобно включить его определение, наряду с несколькими другими, о которых будет сказано позднее, в ЧНРЬ-пакет, как показано в табл. 6.36. Табл. 6.36.
ЧНР1.-пакет с определениями для устройства, играющего в крес- тики и нолики 1зЬгагу ТЕЕЕ; цвв ТЕЕЕ.вса 1обьс 1164.а111' раснаяе ТТТЗе1е зв суре тттегьа Тв аггау 11 со 3) от ят0 10010 честОЕ11 со 3); ваЬсуре ТТТшоче зв ЯТО ЕОСХС ЧЕСТОЕ 13 с)оявсо О); вос) ТТЫв1в; соовааас сопвсалс совааелс соавселс соавсапС соввсааС солвсапс солвсапс соласаас соавсалс ИОЧЕг1: ИОЧЕ12.' ИОЧЕ13: ИОЧЕ21: ИОЧЕ22.' ИОЧЕ23: ИОЧЕЗ1: ИОЧЕЗ2: ИОЧЕЗЗ: ИОНЕ: ТТТоочв ТТТшоче ТТТшо че ТТТлочв ТТТшочв ТТТшоче ТТТшочв ТТТшочв ТТТшоче ТТТшочв "1000"; "0100"; "0010"; "0001", "1100"; ;= "0111"; "1011"; "1101"; "1110"; := "0000*'; 6 6. Примеры проектирования с использованием языка ЧНОЬ 611 Было бы естественно определить тип ТТТдгйс1 как двумерный массив эле„ов типа ЯТ0 ЬОСТС, но не все ЧНПЬ-средства полдерживают двумерные массивы.
Поэтому введем массив 3-разрядных векторов типа РТС гОСТС ЧЕСТОК, что является почти тем же самым. Для представления и~ рового поля игры в крестики н нолики воспользуемся двумя сигналами этого нпа Х и Т, где элемент переменной равен 1, когда у игрока с соответствующим именем стоит метка в данной клетке. На рис. 6.16 показано соответствие между именами сигналов и клетками на игровом поле. 1 2 3 столбец Рис. 6.16.
Поле для игры в кре- стики и нолики и именасигнапав в ЧНВЬ-программе строка 1 В пакете в табл. 6.36 определен также 4-разрядный тип ТТТг«оче для представления ходов. У игрока есть девять возможных ходов, и нужно еще одно кодовое слово для случая, когда никакой ход не возможен. Выбор именно такого способа кодирования и его включение в пакет обусловлено только тем, что точно так же мы поступили в примере проектирования нашего устройства средствами языка АВЕЬ в разделе 6.2.7.
Благодаря тому, что способ кодирования определен в пакете, можно позднее изменить это определение без необходимости вносить изменения в использующие это определение обьекты (см., например, задачу 623). Имеет смысл не пытаться разработать устройство, выбирающее ход в игре в лрестики и нолики, как единое целое, а попробовать разбить его на меньшие блоки. Действительно, представляется разумным разбиение устройства на блоки в соответствии с тремя шагами стратегии игры, указанными в начале этого раздела. Отметим, что 1-й и 2-й шаги в нашей стратегии очень похожи: они отличаются только тем, что игроки иеняются ролями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
