Рефераты Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

Вернуться в Аппаратное обеспечение и компьютерные сети

Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
 2Антик М.И. 11_03_91 МИРЭА  _АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА Алгоритмы этого типа являются следующим этапом обобщенияописаний вычислительных процессов. Теперь, по сравнению с ал-горитмами автоматного типа, на каждом шаге, помимо модифика-ции памяти, идентифицирующей шаг алгоритма, разрешается изме-нять любую другую память устройства локально (по частям) илиглобально (всю сразу). Устройство-исполнитель алгоритма этого типа будем назы-вать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат сосложно структурированной памятью - состоянием: часть памятииспользуется для идентификации шага алгоритма, остальная па-мять используется для запоминания промежуточных данных, вы-числяемых в процессе последовательного, по шагам, выполненияалгоритма. Такая модель вычислителя особенно удобна для рас-чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп-ность взаимодействующих синхронных автоматов, один из которыхназывается управляющим автоматом (УА), а объединение всех ос-тальных автоматов называется операционным автоматом (ОА). УА является исполнителем алгоритма автоматного типа, ко-торый входит составной частью в любой алгоритм процедурноготипа. Кроме того, УА инициирует действия отдельных шагов ал-горитма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритмапод управлением УА; кроме того, к ОА удобно отнести все вы-числения предикатных функций, оставив УА только анализ вычис-ленных предикатных значений. Прежде чем переходить к точным терминам, рассмотрим сле-дующиe примеры алгоритмов процедурного типа. Например, каноническое описание синхронного конечногоавтомата может быть интерпретировано (истолковано) как одно-шаговый алгоритм процедурного типа. ? ???????? ? ? ???V??V?????? ? ? B=FO(S,A) ? ? ? ? ? ? S:=FS(S,A)? ? ????????????? ??????????? Исполнитель этого алгоритма состоит только из ОА. Накаждом шаге этого алгоритма изменяется вся память устройства,поэтому управление памятью не требуется, идентифицировать ша-ги этого алгоритма не надо. Например, инкрементор с одноразрядным входом и однораз-рядным выходом может быть реализацией следующих преобразова-ний: ? ? p:=1 ? ? ?????????? ? ? ??????V?V???????? ? ? (p:, b) = a+p ? ? ????????????????? ???????????? - 2 -ОА, реализующий инкрементор в целом, будет следующим: ?????? a ???????????????????HS?S?????b ?????p ? ? ?начальное значен.??S?T???? ?P???? ??? ? ?????? ? SYN ?????????/C? ? ? ??D? ? ? ?????? ? ?????????????????Конечно, эта реализация совпадает с реализацией алгоритма ав-томатного типа, если состояние р1 кодируется 1, а состояниер0 - 0. Этот пример показывает,что до начала вычислений можетпотребоваться начальная установка памяти. На самом деле этонеобходимо было уже в алгоритмах автоматного типа, так каккод начального состояния требует предварительной установ-ки. Ограничимся здесь обозначением этой проблемы, а решениеее, связанное прежде всего с корректной синхронизацией ус-тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк-вивалентного автомату Мили , не обсуждалась простая возмож-ность ее реализации и на структурном уровне. Например, толькочто рассмотренный автомат Мили может быть преобразован в эк-вивалентный автомат Мура по одному из следующих вариантов: ?????t?????? ?????? ?????a ????T???HS?S??b a ??????HS?S????T???b ?/????? ? ? ? ? ? ??/????? C ? ? ? C ? ? ? C ?/?????p? ? ? ?/?????p? ? ? ???T??? ?P?? ???T??? ?P?? ? ????? ??????? ? ????? ??????? ??????????????? ??????????????? При таких структурных преобразованиях проще истолковы-вать алгоритмы как процедурные
10 11 12 13 14 15 16 
Добавить в Одноклассники    

 

Rambler's Top100