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

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

 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├┐

   │ └┴─┴┘ └──┴─┘│                   │ └┴─┴┘ └──┴─┘│

   └─────────────┘                   └─────────────┘

     При таких структурных преобразованиях  проще  истолковы-

вать алгоритмы как процедурные.

               █                                 █

        █ p:=1; t:=0 █                       █ p:=1 █

               █                                 █

    ┌────────┐ │                      ┌────────┐ │

    │  ┌─────V─V───────┐              │  ┌─────V─V───────┐

    │  │t:=a;(p:,b)=t+p│              │  │ (p , b):= a+p │

    │  └───────┬───────┘              │  └───────┬───────┘

    └──────────┘                      └──────────┘

     БЛОК-ТЕКСТ. Способ описания автоматного алгоритма  после

некоторых дополнений может быть использован  и  для  описания

алгоритмов в процедурной форме:

     Блок-текст состоит из трех частей:

 1)- Описание переменных и начальных значений памяти.

 2)- Описания функций и связей. Записываются любые функции  и

функциональные связи (в том числе предикатные), не  использу-

ющие запоминания. Переменные из левой части операции  присва-

ивания таких функциональных описаний  используются  в  блоках

процедуры.

 3)- Процедура, состоящая из блоков (микроблоков) операторных

и блоков переходов:

- операторные - в скобках вида  {.....},

- перехода    - в скобках вида  <<...>>;

и те, и другие блоки могут снабжаться метками, стоящими перед

блоком. В блоках перехода используется  оператор  GO  в одной

из двух форм:

        GO m                 - безусловный переход,

        GO (P; m0,m1,m2,...) - условный переход.

здесь m0,m1,... - метки блоков,

      P - предикатное значение,интерпретируемое оператором GO

                                - 3 -

как неотрицательное целое число, являющееся порядковым  номе-

ром метки в списке меток оператора GO. С  этой  метки  должно

быть продолжено выполнение алгоритма. Блоки условных  перехо-

дов эквивалентны предикатным вершинам блок-схемы алгоритма.

     На следующем более сложном примере демонстрируется  пос-

ледовательность синтеза операционного устройства.

     Пример. Вычислитель наибольшего  общего  делителя  (НОД)

двух натуральных чисел (8-разрядных).

     1) Разработаем интерфейс вычислителя:

                 8  ┌──┬─────┬──┐

              ═══╪═>╡I1│ НОД │  │

                    │  │     │  │  8

                 8  │  │     │D ╞══╪══>

              ═══╪═>╡I2│     │  │

                    ├──┤     ├──┤

              ─────>┤rI│     │rO├─────>

                    ├──┤     │  │

              ─────>┤ C│     │  │

                    └──┴─────┴──┘

 I1[7..0], I2[7..0] -входные информационные шины.

 rI -входной сигнал готовности: если rI=1, то на  входах  I1,

I2 готовы операнды.

 D[7..0] -выходная информационная шина .

 rO -выходной сигнал готовности: если rO=1, то готов  резуль-

тат на шине D, который сохраняется до появления новых операн-

дов.

     2) Математическое обоснование алгоритма вычислений:

     Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-

ется в том, что НОД двух натуральных чисел А и В в случае ра-

венства этих чисел совпадает с любым из них, а  в  случае  их

неравенства совпадает с НОД двух  других  чисел:  меньшего  и

разности между большим и меньшим.  Последовательно,  уменьшая

числа, получим два равных числа -значение одного из них и бу-

дет НОД исходных чисел.

     3) Блок-схема алгоритма (микропрограмма в содержательном

виде):

                                - 4 -

                              █

                              │

                       ┌──────V──────┐

                     m1│  rO: = 0    │

                       └──────┬──────┘

                              │┌──────────────────┐

                              ││┌─────┐           │

                             ─VVV─    │           │

                             / \ 0    │           │

                            < rI>─────┘           │

                             \_/                  │

                              │1                  │

                       ┌──────V──────┐            │

                       │  rO: = 0    │            │

                       │             │            │

                     m2│   А: = I1   │            │

                       │             │            │

                       │   B: = I2   │            │

                       └──────┬──────┘            │

         ┌───────────────────┐│                   │

         │             ┌─────VV──────┐            │

         │           m3│ (p,S)=A - B │            │

         │             └──────┬──────┘            │

         │                   ─V─         m6       │

         │                   /  \ =0  ┌──────────┐│

         │                z <S==0>───>┤ rO:=1;D=A├┘

         │                   \__/     └──────────┘

         │                    │╪0

         │                    V

         │                 0 / \ 1

         │          ┌───────< p >────────┐

         │  ┌───────V──────┐ \_/ ┌───────V──────┐

         │m4│  (x,B:)=-A+B │   m5│ (x,A:)=A - B │

         │  └───────┬──────┘     └───────┬──────┘

         └──────────┴────────────────────┘

     Или в виде блок-текста:

I1[7..0], I2[7..0] --входные шины

D[7..0]            --выходная шина

rI, rO             --сигналы готовности

A[7..0]:, B[7..0]: --память текущих значений

S[7..0]            --разность

z, p               --предикатные переменные

z=┐(!/S) --сжатие(свертка) S[7..0] по ИЛИ-НЕ

         --можно записать иначе z=(S==0)

D=A

-------------------------------------------------------------------

     m1{rO:=0}

     g1<<GO(rI;g1,m2)>>

     m2{rO:=0; A:=I1; B:=I2}

     m3{(p,S)=A-B}

       <<GO(z;g2,m6)>>

     g2<<GO(p;m4,m5)>>

     m4{(x,B:)=-A+B}

       <<GO m3>>

     m5{(x,A:)= A-B}

       <<GO m3>>

     m6{rO:=1}

       <<GO g1>>

                                - 5 -

4) Разработка функциональной схемы операционного автомата.

     В ОА должны быть реализованы все переменные с памятью  и

без,а также вычислительные операции,используемые в алгоритме.

                      A     ╔══════════════════════════════>D

                  ─/┬┬──┬┐  ║    ┌────────────┐

                   C││RG││  ║    │   f1=(A-B) │

                    ││  ││  ║   A│            │

         I1═════>══>╡│  │╞══╝  ═>╡   f2=(-A+B)│      ┌─┐

                    ││  ││       │            │S    S│1│

                    ││  ││       │            ╞>   ═>┤ o───>z

                    ┴┴──┴┘       │            │      │ │

                      B          │            │      └─┘

                  ─/┬┬──┬┐       │            │

                   C││RG││       │            ├────────────>p

                    ││  ││B     B│            │

          I2═════>═>╡│  │╞>    ═>╡            │    ─/┬┬─┬┐

                    ││  ││       │            │     C││ │├>rO

                    ││  ││       │            │      ││ ││

            rI─────>┴┴──┴┘       └────────────┘      └┴─┴┘

     Кроме того, в ОА необходимо реализовать все информацион-

ные связи, соответствующие микрооперации коммутации, а  также

микрооперации запоминания (загрузки, записи) и обнуления.

    ╔══════════════════════════════════════════════╗

    ║                 A     ╔══════════════════════║═══════>D

    ║  ┌────┐     ─/┬┬──┬┐  ║   ┌────┐    ┌──────┐ ║

    ║  │ MUX│      C││RG││  ║   │M2*8│ 1─>┤cr  SM│ ║

    ╠═>┤0   │       ││  ││  ║   │    │    ├─     │ ║

I1══║═>┤1   ╞══════>╡│  │╞══╩══>╡    ╞═══>╡I1    │ ║ ┌─┐

    ║  ├    │       ││  ││  A   │    │    │      │ ║ │1│

    ║  │А   │      W││  ││      ├─   │    │     S╞═╩>╡ o───>z

    ║  └A───┘     ─A┴┴──┴┘      └A───┘    │      │   │ │

    ║   │          │             │        │      │   └─┘

    ║  umA         uA           uiA       │      │

    ║                  B                  │      │

    ║  ┌────┐     ─/┬┬──┬┐      ┌────┐    │      │

    ║  │ MUX│      C││RG││      │M2*8│    │     p├─────────>p

    ╚═>╡0   │       ││  ││ B    │    │    │      │

I2════>╡1   ╞══════>╡│  │╞═════>╡    ╞═══>╡I2    │  C

       ├    │       ││  ││      │    │    │      │ ─/┬┬─┬┐

       │А   │      W││  ││      ├─   │    │      │1─>┤│T│├>rO

       └A───┘     ─A┴┴──┴┘      └A───┘    └──────┘R W││ ││

        │          │             │               ─A─A┴┴─┴┘

      uMB          uB           uiB             urO uwO

     5) Формулировка требований к управляющему автомату.

     При формировании управляющих сигналов  следует  обратить

внимание не только на операции, которые необходимо  выполнить

на данном шаге, но и на те оперции, которые нельзя  выполнять

на этом шаге, это - как правило, операции изменения памяти.

     Будем считать, что операция активна, если  значение  уп-

равляющего сигнала равно 1.

                                - 6 -

Для управления вычислениями  на  каждом  шаге  алгоритма

потребуются следующие управляющие сигналы:

Страницы: 1, 2, 3