Алгоритмический конечный автомат

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

метод АСМ

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

1 . Создайте алгоритм, используя псевдокод , для описания желаемой работы устройства.

2 . Преобразуйте псевдокод в диаграмму ASM .

3 . Спроектируйте путь данных на основе диаграммы ASM.

4 . Создайте подробную диаграмму ASM на основе пути к данным.

5 . Разработайте логику управления на основе подробной схемы ASM.

Диаграмма АСМ

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

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

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

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

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

Путь к данным

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

Подробная диаграмма ASM

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

См. также

Ссылки

^ Осборн, Томас «Том» Э. (11 ноября 2004 г.) [1994]. «История Тома Осборна его собственными словами» . Страница HP9825 Стива Лейбсона (письмо Барни Оливеру). Архивировано из оригинала 24 февраля 2021 г. Проверено 24 февраля 2021 г.
^ Клэр, Кристофер «Крис» Р. (февраль 1971 г.) [ноябрь 1970 г.]. Логическое проектирование алгоритмических автоматов . Лаборатории Hewlett-Packard, США: Hewlett-Packard . Каталожный номер CHM 102650285 . (110 страниц) [1] (Примечание. В 1970 и 1971 годах существовало несколько внутренних редакций. Позже они были опубликованы McGraw-Hill. ^[А])
^ Клэр, Кристофер «Крис» Р. (1973) [ноябрь 1972 г.]. Проектирование логических систем с использованием конечных автоматов . Осборн, Томас «Том» Э. (первоначальные взносы) (1-е изд.). Лаборатория исследований электроники, Hewlett-Packard Laboratories: McGraw-Hill, Inc. ISBN 0-07011120-0 . S2CID 60509061 . СБН 07-011120-0 . ISBN 978-0-07011120-2 . ковчег:/13960/t9383kw8n. 79876543 . Проверено 14 февраля 2021 г. (vii+114+3 страницы) [2] [3] (Примечание. Эта книга основана на внутреннем документе Hewlett-Packard 1970 года. ^[Б])
^ Хаус, Чарльз «Чак» Х. (24 декабря 2012 г.). «Смена парадигмы происходила вокруг нас» (PDF) . Журнал IEEE твердотельных схем . Том. 4, нет. 4. Стэнфордский университет: Институт инженеров по электротехнике и электронике . стр. 32–35. дои : 10.1109/MSSC.2012.2215759 . eISSN 1943-0590 . ISSN 1943-0582 . Архивировано (PDF) из оригинала 20 января 2013 г. Проверено 30 июня 2023 г. стр. 2–3: Второй ежегодный семинар IEEE по микропроцессорам (теперь называемый семинаром по микрокомпьютерам Asilomar , или AMW) проводился со среды по пятницу, 28–30 апреля 1976 года, недалеко от Монтерея, Калифорния […] В моем вечернем разговоре в среду были описаны инструменты. это позволило использовать совершенно другую методологию проектирования — алгоритмическое проектирование конечных автоматов (ASM) — с использованием Ляпунова математики переменных состояния и производных методов, впервые использованных в HP Крисом Клэром и Дэйвом Кокраном для чрезвычайно успешных портативных научных калькуляторов (например, HP 35 ) [… ] Моя точка зрения: проектирование схемы больше не было проблемой отдельных элементов, а представляло собой вопрос «потока состояний» во многих узлах — последовательных «слов» регистров, а не напряжений на выводах устройства. По сути, там утверждалось, что электронные напряжения, аналоговые или переключаемые, «проиграют» программным инструкциям и «состояниям данных». Системы будут проектироваться и анализироваться на правильную последовательность состояний, а не на искажение аналогового сигнала или время цифрового переключения. […] Я уже видел силу предизданные книги . Проницательный текст Клэра по методологии ASM « Проектирование логических систем с использованием конечных автоматов » пронесся по сообществу HPdesign […] Отдел электротехники Стэнфорда был не столь оптимистичен, однако отменил курс Клэр в 1974 году, заявив, что «это немного слишком нетрадиционно». «… Стэнфорд предпочитал методы минимизации Куайна–Маккласки . Соответственно, Мида из Калифорнийского технологического института коллега Иван Сазерленд подготовил статью в Scientific American (1977) […] о проблемах, которые микроэлектроника представляет для теории и практики вычислений, отметив, что, поскольку большая часть поверхности чипа занята «проводами» (проводящими путями), скорее чем «компоненты» (транзисторы), десятилетия теории минимизации в логическом проектировании стали неактуальными […] (4 страницы)

Дальнейшее чтение

Ли, Сунгу (2000) [1999]. Проектирование компьютеров и других сложных цифровых устройств (1-е изд.). Река Аппер-Сэддл, Нью-Джерси, США: Prentice-Hall, Inc. ISBN 0-13-040267-2 . ЛЦН 99-049967 . ISBN 978-0-13040267-7 . (xiv+418 страниц)
Ли, Сунгу (2000). Компьютерный дизайн: пример проектирования усовершенствованной цифровой логики . Прентис-Холл .
Ли, Сунгу (2006). Проектирование продвинутой цифровой логики: использование VHDL, конечных автоматов и синтеза для FPGA . Томсон. ISBN 0-534-46602-8 .
Браун, Стивен Д.; Вранешич, Звонко . Основы цифровой логики с использованием VHDL Design (1-е изд.).
- Браун, Стивен Д.; Вранешич, Звонко (2004). Основы цифровой логики с использованием VHDL Design (2-е изд.). МакГроу Хилл. ISBN 978-0-07-249938-4 .
- Браун, Стивен Д.; Вранешич, Звонко (2009). Основы цифровой логики с использованием VHDL Design (3-е изд.). МакГроу Хилл. ISBN 978-0-07-352953-0 .
Бьорнер, Дайнс (декабрь 1970 г.) [1970-05-04, 1970-04-07, 1970-02-04]. «Блок-схема машин» . БИТ Численная математика . 10 (4). Исследовательская лаборатория IBM, Сан-Хосе, Калифорния: 415–442. дои : 10.1007/BF01935563 . S2CID 189767592 . RJ-685 (№13346).
Ли, Сэмюэл К. (1976). Цифровые схемы и логическое проектирование . Энглвуд Клиффс, Нью-Джерси, США: Прентис-Холл .
Сантракул, Краим (1983). Проектирование логики многозначных LSI/VLSI (PDF) (кандидатская диссертация). Университет Оклахомы. Архивировано (PDF) из оригинала 17 августа 2016 г. Проверено 17 февраля 2021 г.
Шульц, GW (март 1969 г.). Написано в компании Central Data Systems, Inc., Саннивейл, Калифорния, США. «Алгоритм синтеза сложных последовательных сетей» . Компьютерный дизайн . Том. 8, нет. 3. Конкорд, Массачусетс, США: Издательская корпорация компьютерного дизайна. стр. 49–55. ISSN 0010-4566 . OCLC 828863003 . Проверено 22 февраля 2021 г. (7 страниц) (Примечание. Эта статья вызвала ряд писем в редакцию в последующих номерах журнала.)
Шульц, GW (1969). Написано в компании Central Data Systems, Inc., Саннивейл, Калифорния, США. «В редакцию» . Письма в редакцию. Компьютерный дизайн . Том. 8, нет. 5–12?. Конкорд, Массачусетс, США: Издательская корпорация компьютерного дизайна. п. 10. ISSN 0010-4566 . OCLC 828863003 . п. 10: […] В апрельском выпуске вы опубликовали письмо Р. Л. Динели, описывающее простой метод обработки логических выражений произведения сумм . […] Еще более простой метод преподает Д.А. Хаффман . Этот метод основан на признании того, что логическое выражение будет равно нулю, когда любой из факторов в форме произведения сумм равен нулю. Отобразить нули коэффициентов на диаграмме Вейча или карте Карно так же просто, как найти единицы в выражении суммы произведений . […] Для иллюстрации на примере Динели (A+BC)(A+C): […] Нули, полученные из A+BC, будут расположены там, где и A, и BC равны нулю. Поэтому находим на карте выражение A * BC (которое равно A * B + A * C ). Аналогичным образом нули A+C расположены и нанесены на график в точке А * С . Когда все нули расположены, остальная часть карты может быть заполнена единицами. Можно быть немного более формальным и алгебраически определить логическое дополнение рассматриваемого выражения, а затем построить нули для этого результирующего выражения. Однако в простом представлении произведения сумм дополнительные члены могут быть записаны путем проверки; или нули можно нанести путем проверки, не записывая полное выражение […] «Классическая редукция, включающая редко используемые переменные», 11 октября 1968 года. Университет Санта-Клары […] Работа г -на Осборна очень похожа на ту, которую я представил в и, таким образом, эта статья , безусловно, будет интересна тем читателям, которые ищут дополнительную информацию. Насколько я понимаю, он проделал работу по применению техники редких переменных для проектирования последовательных сетей, построенных из постоянной памяти . Поскольку он еще ничего не публиковал в этой области, если читатели захотят получить дополнительную информацию, они могут написать г-ну Осборну по адресу: […] Томас Э. Осборн […] Здание 1U […] 1501 Page Mill Road […] Пало-Альто , Калифорния […] Спасибо за возможность публиковаться вместе с вами. […] Г.В. Шульц […] Central Data Systems, Inc. […] Саннивейл, Калифорния. (1 страница) (Примечание. Метод Осборна был позже опубликован Клэр. ^[Б])
Лэнгдон-младший, Глен Г. (1974). «Глава 4. Взаимосвязи, D. Логическое проектирование и теория коммутации, 3. Таблица потоков как отправная точка проектирования» . Написано в корпорации IBM, Сан-Хосе, Калифорния, США. В Эшенхерсте, Роберт «Боб» Ловетт [в Викиданных] (ред.). Логический дизайн — обзор теории и практики . Серия монографий ACM (1-е изд.). Нью-Йорк, США: Academic Press, Inc. — дочерняя компания Harcourt Brace Jovanovich, Publishers . п. 149. ИСБН 0-12-436550-7 . ISSN 0572-4252 . LCCN 73-18988 . Архивировано из оригинала 17 апреля 2021 г. Проверено 17 апреля 2021 г. п. 149: […] Важный вклад в адаптацию теории к практике был сделан Шульцем [20] ; он опирается на базовое понимание проблемы дизайнером и требует от него идентифицировать « нечастые переменные ». В широком смысле эти переменные не относятся ко всем внутренним состояниям, т. е. они не нужны для определения каждого состояния. По сути, редкие переменные относятся только к нескольким (возможно, одному или двум) состояниям или переходам состояний. Шульц предлагает разработчику сначала перевести словесную задачу в уменьшенный граф переходов состояний. Внутренние состояния кодируются, а затем информация о редких переменных добавляется к соответствующим переходам состояний. «первое приближение» к входным уравнениям триггера Создается , основанное только на частых переменных. Шульц демонстрирует, как эти уравнения впоследствии можно изменить, включив в них переходы, контролируемые редкими переменными. В примерах Шульца все редкие переменные являются входными сигналами, но эта идея также применима к сигналам переменных внутреннего состояния, которые можно считать «редкими». В этом случае, например, нечастый триггер внутренней переменной состояния может быть установлен определенными обстоятельствами и сброшен когда-нибудь позже. Выход триггера теперь можно рассматривать как нечастую входную переменную. […] (ix+1+179+3 страницы)

Внешние ссылки

[Osborne_2004-1] Осборн, Томас «Том» Э. (11 ноября 2004 г.) [1994]. «История Тома Осборна его собственными словами» . Страница HP9825 Стива Лейбсона (письмо Барни Оливеру). Архивировано из оригинала 24 февраля 2021 г. Проверено 24 февраля 2021 г.

[Clare_1970-2] Клэр, Кристофер «Крис» Р. (февраль 1971 г.) [ноябрь 1970 г.]. Логическое проектирование алгоритмических автоматов . Лаборатории Hewlett-Packard, США: Hewlett-Packard . Каталожный номер CHM 102650285 . (110 страниц) [1] (Примечание. В 1970 и 1971 годах существовало несколько внутренних редакций. Позже они были опубликованы McGraw-Hill. ^[А])

[Clare_1973-3] Клэр, Кристофер «Крис» Р. (1973) [ноябрь 1972 г.]. Проектирование логических систем с использованием конечных автоматов . Осборн, Томас «Том» Э. (первоначальные взносы) (1-е изд.). Лаборатория исследований электроники, Hewlett-Packard Laboratories: McGraw-Hill, Inc. ISBN 0-07011120-0 . S2CID 60509061 . СБН 07-011120-0 . ISBN 978-0-07011120-2 . ковчег:/13960/t9383kw8n. 79876543 . Проверено 14 февраля 2021 г. (vii+114+3 страницы) [2] [3] (Примечание. Эта книга основана на внутреннем документе Hewlett-Packard 1970 года. ^[Б])

[House_2012-4] Хаус, Чарльз «Чак» Х. (24 декабря 2012 г.). «Смена парадигмы происходила вокруг нас» (PDF) . Журнал IEEE твердотельных схем . Том. 4, нет. 4. Стэнфордский университет: Институт инженеров по электротехнике и электронике . стр. 32–35. дои : 10.1109/MSSC.2012.2215759 . eISSN 1943-0590 . ISSN 1943-0582 . Архивировано (PDF) из оригинала 20 января 2013 г. Проверено 30 июня 2023 г. стр. 2–3: Второй ежегодный семинар IEEE по микропроцессорам (теперь называемый семинаром по микрокомпьютерам Asilomar , или AMW) проводился со среды по пятницу, 28–30 апреля 1976 года, недалеко от Монтерея, Калифорния […] В моем вечернем разговоре в среду были описаны инструменты. это позволило использовать совершенно другую методологию проектирования — алгоритмическое проектирование конечных автоматов (ASM) — с использованием Ляпунова математики переменных состояния и производных методов, впервые использованных в HP Крисом Клэром и Дэйвом Кокраном для чрезвычайно успешных портативных научных калькуляторов (например, HP 35 ) [… ] Моя точка зрения: проектирование схемы больше не было проблемой отдельных элементов, а представляло собой вопрос «потока состояний» во многих узлах — последовательных «слов» регистров, а не напряжений на выводах устройства. По сути, там утверждалось, что электронные напряжения, аналоговые или переключаемые, «проиграют» программным инструкциям и «состояниям данных». Системы будут проектироваться и анализироваться на правильную последовательность состояний, а не на искажение аналогового сигнала или время цифрового переключения. […] Я уже видел силу предизданные книги . Проницательный текст Клэра по методологии ASM « Проектирование логических систем с использованием конечных автоматов » пронесся по сообществу HPdesign […] Отдел электротехники Стэнфорда был не столь оптимистичен, однако отменил курс Клэр в 1974 году, заявив, что «это немного слишком нетрадиционно». «… Стэнфорд предпочитал методы минимизации Куайна–Маккласки . Соответственно, Мида из Калифорнийского технологического института коллега Иван Сазерленд подготовил статью в Scientific American (1977) […] о проблемах, которые микроэлектроника представляет для теории и практики вычислений, отметив, что, поскольку большая часть поверхности чипа занята «проводами» (проводящими путями), скорее чем «компоненты» (транзисторы), десятилетия теории минимизации в логическом проектировании стали неактуальными […] (4 страницы)

[1]

[2]

[3]

[4]