Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
