Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Метод алгоритмического конечного автомата ( ASM ) - это метод проектирования конечных автоматов (FSM), первоначально разработанный Томасом Осборном в Калифорнийском университете в Беркли (UCB) с 1960 года [1], представленный и реализованный в Hewlett-Packard. в 1968 году, формализована и расширена с 1967 года и написана Кристофером Р. Клэром с 1970 года. [2] [3] Используется для представления диаграмм цифровых интегральных схем . Диаграмма ASM похожа на диаграмму состоянийно более структурированный и, следовательно, более понятный. Схема ASM - это метод описания последовательных операций цифровой системы.

Метод ASM [ править ]

Метод ASM состоит из следующих шагов:

1 . Создайте алгоритм, используя псевдокод , для описания желаемой работы устройства.
2 . Преобразуйте псевдокод в диаграмму ASM .
3 . Спроектируйте путь данных на основе диаграммы ASM.
4 . Создайте подробную диаграмму ASM на основе пути данных.
5 . Разработайте логику управления на основе подробной диаграммы ASM.

Диаграмма ASM [ править ]

Схема ASM состоит из взаимосвязи четырех типов базовых элементов: имени состояния, блока состояния, проверки условий и условных выходов. Состояние ASM, представленное в виде прямоугольника, соответствует одному состоянию регулярной диаграммы состояний или конечного автомата. В Moore выходы типа перечислены внутри коробки.

Название штата

Название штата: название штата указывается внутри круга, и кружок помещается в левый верхний угол, или название помещается без кружка.

Государственная коробка

Поле состояния: вывод состояния указывается внутри прямоугольного поля.

Блок решения, используемый в диаграмме ASM

Блок решения: ромбик указывает на то, что указанное условие / выражение должно быть проверено и путь выхода должен быть выбран соответственно. Выражение условия содержит один или несколько входов для конечного автомата. Проверка условия ASM, обозначенная ромбом с одним входом и двумя выходами (для истинного и ложного), используется для условного перехода между двумя блоками состояний, в другой блок принятия решений или в блок условного вывода. Поле решения содержит указанное выражение условия, которое необходимо проверить, выражение содержит один или несколько входов конечного автомата.

Поле условного вывода

Поле условного вывода: овал обозначает выходные сигналы типа Мили . Эти выходы зависят не только от состояния, но и от входов конечного автомата.

Datapath [ править ]

После того, как желаемая операция схемы была описана с использованием операций RTL , можно получить компоненты канала данных. Каждая уникальная переменная, которой присвоено значение в программе RTL, может быть реализована как регистр. В зависимости от функциональной операции, выполняемой при присвоении значения переменной, регистр для этой переменной может быть реализован как простой регистр, регистр сдвига, счетчик или регистр, которому предшествует блок комбинационной логики. Блок комбинационной логики, связанный с регистром, может реализовывать сумматор, вычитатель, мультиплексор или какой-либо другой тип функции комбинационной логики.

Подробная диаграмма ASM [ править ]

После проектирования пути данных диаграмма ASM преобразуется в подробную диаграмму ASM. РТЛ обозначения заменяется сигналов , определенных в магистрали данных.

См. Также [ править ]

Ссылки [ править ]

  1. ^ Осборн, Томас «Том» Э. (2004-11-11) [1994]. «История Тома Осборна его собственными словами» . Страница HP9825 Стива Лейбсона (Письмо Барни Оливеру). Архивировано 24 февраля 2021 года . Проверено 24 февраля 2021 .
  2. ^ Клэр, Кристофер «Крис» Р. (февраль 1971 г.) [ноябрь 1970 г.]. Логический дизайн алгоритмических конечных автоматов . Лаборатории Hewlett-Packard, США: Hewlett-Packard . Каталожный номер CHM 102650285.(110 страниц) [1] (NB. В 1970 и 1971 годах существовало несколько внутренних исправлений. Позднее это было опубликовано McGraw-Hill. [A] )
  3. ^ Клэр, Кристофер "Крис" Р. (1973) [ноябрь 1972]. Проектирование логических систем с использованием конечных автоматов (PDF) . Осборн, Томас «Том» Э. (первоначальные взносы) (1-е изд.). Лаборатория исследований электроники, Hewlett-Packard Laboratories: McGraw-Hill, Inc. ISBN  0-07011120-0. S2CID  60509061 . SBN 07-011120-0. ISBN 978-0-07011120-2 . ark: / 13960 / t9383kw8n. 79876543 . Источник 2021-02-14 . (vii + 114 + 3 страницы) [2] (NB. Эта книга основана на внутреннем документе Hewlett-Packard 1970 г. [B] )
  • Сунгу Ли : Компьютерный дизайн: пример усовершенствованного дизайна цифровой логики , Prentice-Hall 2000, ISBN 0-13-040267-2 . 
  • Сунгу Ли : Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs , Thomson 2006, ISBN 0-534-46602-8 . 
  • Стивен Д. Браун , Звонко Вранешич : Основы цифровой логики с VHDL-дизайном .
    • 2-е место, Макгроу Хилл, 2004 г .; ISBN 978-0-07-249938-4 . 
    • 3-е место, Макгроу Хилл, 2009 г .; ISBN 978-0-07-352953-0 . 
  • Бьёрнер, Дайнс (декабрь 1970 г.) [1970-05-04, 1970-04-07, 1970-02-04]. «Блок-схема машин» . BIT Численная математика . Исследовательская лаборатория IBM, Сан-Хосе, Калифорния. 10 : 415–442. DOI : 10.1007 / BF01935563 . S2CID  189767592 . RJ-685 (№ 13346).
  • Ли, Сэмюэл С. (1976). Цифровые схемы и логический дизайн . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл .
  • Сантракул, Крайим (1983). Многозначный логический дизайн БИС / СБИС (PDF) . Университет Оклахомы. Архивировано (PDF) из оригинала 17 августа 2016 года . Проверено 17 февраля 2021 .

Дальнейшее чтение [ править ]

  • Шульц, GW (март 1969 г.). Написано в Central Data Systems, Inc., Саннивейл, Калифорния, США. «Алгоритм синтеза сложных последовательных сетей» . Компьютерный дизайн . Vol. 8 нет. 3. Конкорд, Массачусетс, США: Корпорация компьютерного дизайна. С. 49–55. ISSN  0010-4566 . OCLC  828863003 . CODEN CMPDA . Проверено 22 февраля 2021 года . (7 страниц) (NB. Эта статья вызвала ряд писем в редакцию в последующих выпусках журнала.)
  • Шульц, GW (1969). Написано в Central Data Systems, Inc., Саннивейл, Калифорния, США. «В редакцию» . Письма в редакцию. Компьютерный дизайн . Vol. 8 нет. 5–12 ?. Конкорд, Массачусетс, США: Computer Design Publishing Corporation. п. 10. ISSN  0010-4566 . OCLC  828863003 . CODEN CMPDA . п. 10: […] В своем апрельском выпуске вы опубликовали письмо Р.Л. Динли, описывающее простой метод обработки логических выражений произведения сумм . […] Еще более простой метод преподает Д.А. Хаффман . Этот метод основан на признании того, что логическое выражение будет равен нулю, когда любой из множителей в форме произведения сумм равен нулю. Нанести нули факторов на диаграмму Вейча или карту Карно так же просто, как найти их для выражения суммы произведений . […] Чтобы проиллюстрировать, используя пример Динли (A + BC) (A + C): […] Нули, полученные в результате A + BC, будут располагаться там, где и A, и BC равны нулю. Поэтому мы размещаем на карте выражение A * BC (которое равно A * B + A * C ). Точно так же нули A + C расположены и нанесены на A * C.. Когда все нули расположены, остальная часть карты может быть заполнена единицами. Можно быть немного более формальным и вычислить алгебраически логическое дополнение рассматриваемого выражения, а затем построить нули для этого результирующего выражения. Однако в простом представлении произведения сумм дополнительные термины могут быть записаны путем проверки; или нули могут быть построены путем осмотра без написания полного выражения […] «Классическая редукция с использованием редко используемых переменных» 11 октября 1968 года. Университет Санта-Клары […] Работа г-на Осборна очень похожа на ту, что я представил в эта статьяи поэтому, безусловно, будет интересен тем читателям, которые ищут дополнительную информацию. Насколько я понимаю, он проделал работу по применению техники нечастых переменных к проектированию последовательных сетей, построенных из постоянной памяти . Поскольку он еще ничего не опубликовал в этой области, если читатели захотят получить дополнительную информацию, они могут написать мистеру Осборну по адресу: […] Thomas E. Osborne […] Building 1U […] 1501 Page Mill Road […] Пало-Альто , Калифорния […] Спасибо за возможность публиковаться вместе с вами. […] GW Schultz […] Central Data Systems, Inc. […] Саннивейл, Калифорния.(1 страница) (NB. Метод Осборна был позже опубликован Клэр. [B] )
  • Лэнгдон младший, Глен Г. (1974). «Глава 4. Взаимосвязи, D. Логический дизайн и теория переключения, 3. Таблица потоков как отправная точка для проектирования». Написано в IBM Corporation, Сан-Хосе, Калифорния, США. В Эшенхерсте, Роберт «Боб» Ловетт (ред.). Логический дизайн - обзор теории и практики . Серия монографий ACM (1-е изд.). Нью-Йорк, США: Academic Press, Inc. - дочерняя компания Harcourt Brace Jovanovich, Publishers . п. 149. ISBN. 0-12-436550-7. ISSN  0572-4252 . LCCN  73-18988 . ISBN 978-0-12-436550-6 . Архивировано 17 апреля 2021 года . Проверено 17 апреля 2021 . п. 149: […] Важный вклад в адаптацию теории к практике был сделан Шульцем [20] ; он опирается на базовое понимание проблемы проектировщиком и требует, чтобы он определил « редко встречающиеся переменные. . "Вольно определенные, эти переменные не относятся ко всем внутренним состояниям, т. Е. Они не нужны для определения каждого состояния. По сути, нечастые переменные относятся только к нескольким (возможно, одному или двум) состояниям или переходам между состояниями. Шульц предлагает, чтобы разработчик сначала преобразовал словесную задачу в сокращенный граф переходов состояний. Внутренние состояния кодируются, а затем информация о нечастых переменных добавляется к соответствующим переходам состояний. «Первое приближение» к триггерувходные уравнения составляются на основе только частых переменных. Шульц демонстрирует, как эти уравнения могут быть впоследствии изменены, чтобы включить переходы, контролируемые нечастыми переменными. В примерах Шульца все нечастые переменные являются входными сигналами, но эта идея также применима к сигналам переменных внутреннего состояния, которые можно считать «нечастыми». В этом случае, например, нечастый триггер переменной внутреннего состояния может быть установлен в определенных обстоятельствах и сброшен через некоторое время. Выход триггера теперь можно рассматривать как нечастую входную переменную. […] (ix + 1 + 179 + 3 стр.)

Внешние ссылки [ править ]

  • Краткое введение в диаграммы ASM
  • ASM ++: современная методология алгоритмического конечного автомата для проектов RTL