. , , ,

,,,

( ) —

.. 11_03_91

.

. , -

, , -

, , -

( )

( ).

- -

().

- :

, -

, -

, ,

. -

.

-

,

(), -

().

, -

. , -

.

; , -

, -

.

, -

e .

,

() -

.

┌──────┐ │

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

│ │ B=FO(S,A) │

│ │ │

│ │ S:=FS(S,A)│

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

└─────────┘

.

,

, -

.

, -

-

:

█ p:=1 █

┌────────┐ │

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

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

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

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


, , :

┌──┬─┐

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

, -

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) - (

):


┌──────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 ───>┤ 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<>

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

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

<>

g2<>

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

<>

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

<>

m6{rO:=1}

<>

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.


:

║umA│umB│uwA│uwB│uiA│uiB│urO│uwO│

══╬═══╪═══╪═══╪═══╪═══╪═══╪═══╪═══╡

m1║ │ │ │ │ │ │ 1 │ 0 │

──╫───┼───┼───┼───┼───┼───┼───┼───┤

m2║ 1 │ 1 │ 1 │ 1 │ │ │ 1 │ 0 │

──╫───┼───┼───┼───┼───┼───┼───┼───┤

m3║ │ │ 0 │ 0 │ 0 │ 1 │ │ 0 │

──╫───┼───┼───┼───┼───┼───┼───┼───┤

m4║ │ 0 │ 0 │ 1 │ 1 │ 0 │ │ 0 │

──╫───┼───┼───┼───┼───┼───┼───┼───┤

m5║ 0 │ │ 1 │ 0 │ 0 │ 1 │ │ 0 │

──╫───┼───┼───┼───┼───┼───┼───┼───┤

m6║ │ │ 0 │ │ │ │ 0 │ 1 │

──╨───┴───┴───┴───┴───┴───┴───┴───┘

.

, umA = umB , uiB = ┐uiA , -

:

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

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

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

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

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

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

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

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

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

║ └────┐ ┌─┘ B ┌────┘ ├─ │ └─┘

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

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

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

I2════>╡1 ╞│═══│═>┤│ │╞══│══>┤ ╞═══>╡I2 │

├ ││ │ ││ ││ │ │ │ │ │

│ ││ │ W││ ││ │ ├─ │ │ │ C

└A───┘│ │─A┴┴──┴┘ │ └A───┘ └──────┘ ─/┬┬─┬┐

│ │ │ └─┐ │ ┌─┐│ 1─>┤│T│├>rO

│ │ │ │ ├>┤ o┘ R W││ ││

├────┘ │ │ │ └─┘ ─A─A┴┴─┴┘

umB uwA uwB uiA urO uwO

---│--------│----│-----│----------------------│-│-----

y1 y2 y3 y4 y5 y6

║y1│y2│y3│y4│y5│y6│

══╬══╪══╪══╪══╪══╪══╡

m1║ │ │ │ │ 1│ 0│

──╫──┼──┼──┼──┼──┼──┤

m2║ 1│ 1│ 1│ │ 1│ 0│

──╫──┼──┼──┼──┼──┼──┤

m3║ │ 0│ 0│ 0│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m4║ 0│ 0│ 1│ 1│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m5║ 0│ 1│ 0│ 0│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m6║ │ 0│ │ │ 0│ 1│

──╨──┴──┴──┴──┴──┴──┘


:

┌────────────────────────────────┐

══>╡I1 │

│ │

══>╡I2 D╞══>

│ │

┌──/C rO├──>

│ │ │

│ │z p umB uwA uwB uiA urO uwO │

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

│ │ │ │ │ │ │ │ │

│ │ │ │ │ │ │ │ │

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

│ │z p y1 y2 y3 y4 y5 y6 │

│ │ │

┴──/C │

│ │

──>┤rI │

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

,

-:

m1{xxxx10}

g1<>

m2{111x10}

m3{x000x0}

<>

g2<>

m4{0011x0}

<>

m5{0100x0}

<>

m6{x0xx01}

<>

. .

- () , -

()

.

= ,

.

-

. ,

, .

-

(). :

([7],x,B[6..0]) = (A[7..0],x)

8--

. , -

,

(B[7..0],d) = (A[7],A[7..0])

.

(p,S[3..0]) = A[3..0] + B[3..0] + q

, 4- -

, ( ,,q ) -

, ( ,S ) - .

( : ) - -

( ) . -

-


.

.

- (

),

. :

( e,D:) = R1 + R2 + c

, ,

, , :

┌───┐

c │MUX│

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

││T │├───>┤0 │ ┌────┐ │MUX│ D

└┴──┴┘ ──>┤1 │ │ SM│ │ │ ┌┬──┬┐

──>┤ ├───>┤cr │ ═══>╡0 ╞═══>╡│RG│╞══>

├───┤ │ S╞═════>╡1 │ └┴──┴┘

R1 │MUX│ │ │ ═══>╡ │

┌┬──┬┐ │ │ │ │ └───┘

││RG│╞═══>╡0 ╞═══>╡I1 │ ┌───┐

└┴──┴┘ ══>╡1 │ │ │ │MUX│

══>╡ │ │ │ │ ├────────────>e

├───┤ │ p├─────>┤0 │

R2 │MUX╞═══>╡I2 │ ───>┤1 │

┌┬──┬┐ │ │ └────┘ ───>┤ │

││RG│╞═══>╡0 │ └───┘

└┴──┴┘ ══>╡1 │

══>╡ │

└───┘

, ,

( -

). ,

- .

- , -

( ) . -

.

, -

"" .

:

{ (p,A):= A + B

(C,r):= A + D }

- ,

.

:

{ (C,x):= A + D

(x,A)= C + B }

,

- . , -

o .

{ A:= B ; B:= 0 }

:=0 (

, ).

: :=0 ,

.

,

( ) ,

. , ,

, , -

.

. :


█ █

█ CT:=(╪0)█ █ CT:=(╪0)█

█ █

│ │

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

m1│ CT:=3 │ m1│ CT:=3 │

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

┌──────>│ ┌──────>│

│ ─V─ │ ─V─

│ / =0 │ / =0

─> │ ─>

│ ___/ │ ___/

│ │╪0 │ │╪0

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

│m2│........│ │m2│........│

│ │ │ │ │ │

│ │CT:=CT-1│ │ │CT:=CT-1│

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

└───────┘ │ ┌────V───┐

│m3│........│

│ └────┬───┘

└───────┘

4 ; -

m3 , , - 3 -

. ( !)

- ,

,.. -

. ,

,

.

( ), .

-

.

- ,

, , - -.

- -

,

.

ߠ Π

-

:

███████████████████████████████████████████████████████████

█ █

█ ┌──────────┐ ┌┬──────┬┐ ┌──────────┐ ┌───────┐ █

██>╡│ ││││ ││ │▐███

│ ▐███>╡│ │▐██>╡ ▐██>╡ │

██>╡ │ ││ ││ │ │ │ ▐███>

└─A────────┘ ─/─┴┴───A──┴┘ └──A───────┘ └──A────┘

█ ┌─┐│CC █ █ █

█ SYN─>┤&├┘ █ █ █

█ ┌┤ │ █ █ █

█ yC│└─┘ █ █ █

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

(, -

, ) . , -

, .


젠 蠠 ࠠ

( ).

y, -

. ,

,

- . , (-

) , ,

. (-

) , . (

.)

:

1)- ;

2)- , ;

3)- .

-

(

), ,, Ѡ

.

:

- ;

-

:

, " -

" ;

(.,,

).

,

,

.

"" -

"" -

, ..

, .

(

), .

, -

, - -

, .

, ,

-

- .

, ,

-

"" -

.

-

, -

. ,

,

. ,

- . (

). ,

.

, -

, -

, -

.


,

,

(.. -

). , -

, ,

.  

,

.

: , -

.

"" .

:

1)- "" ()

, ,

;

2)- ,

-

;

3)- , ..

;

-

, , -

. -

, 1 - 3

.

- - -

, ,

-

.

.

, :

─┬─

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

│ J:=0 │ ┌┬──┬─┐ │ MUX│ ┌────┐

└───────┬───────┘ ││RG│0├───>┤0 │ │ f │

┌──────┐ │ ││ │.│ . │. │A[J] │ │

│ ┌────V──V───────┐ ││ │.│ . │. ├────>┤ │

│ │ ..... │ ││ │.│ . │. │ │ │ B

│ │ │ ││ │ │ │ │ │ ╞══>

│ │ B= f(...,A[J])│ ││ │K├───>┤K │ │ │

│ │ │ ││ │.│ │. │ ══>╡ │

│ │ J:=J+1 │ ││ │.│ │. │ │ │

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

│ ─V─ └┴──┴─┘ ├─ │ └────┘

╡ │

└───────────> └────┘

__/

( J a).

,

D. :


───┬── A D

│ ┌┬──┬┐ ┌┬──┬─┐ A[J] ┌─────┐

┌───────V───────┐ ││RG││ ││RG│0├─────>┤ f │

│ J:=0 │ ││ ││ ││ │.│ │ │

│ │ ││ ││ ││->│.│ │ │ B

│ D:=A │ ││ │╞══════>╡│ │.│ │ ╞══>

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

┌──────┐ │ ││ ││ ││ │K├ │ │

│ ┌────V──V───────┐ ││ ││ x ──>┤Dn │.│ │ │

│ │ ..... │ ││ ││ ││ │.│ ══>╡ │

│ │ │ ││ ││ S W││ │.│ │ │

│ │ B= f(...,D[0])│ └┴──┴┘ ─v─v┴┴──┴─┘ └─────┘

│ │ │

│ │ (D,x):=(x,D) │

│ │ │

│ │ J:=J+1 │

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

│ ─V─

└───────────>

__/

A ,

( ).

: , -

:

───┬── ┌┬─┬┐B[0]

│ a ────────────┬─────>┤│T│├────>

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

│ J:=0 │ ┌───┐ │ ─A┴┴─┴┘

└───────┬───────┘ │DC │ ┌──┼─────┘| |

┌──────┐ │ │ 0├─┘ │ | |

│ ┌────V──V───────┐ │ .│. │ ┌┬─┬┐B[K]

│ │ ..... │ │ .│. └─────>┤│T│├────>

│ │ │ │ .│. W││ ││

│ │ a=f(...) │ J ══>╡ │ ─A┴┴─┴┘

│ │ │ │ K├──────────┘

│ │ B[J]:=a │ │ .│

│ │ │ │ .│

│ │ J:=J+1 │ │ .│

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

│ ─V─

└───────────>

__/

,

.

-

D[K..0], -

:


───┬──

│ D B

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

│ J:=0 │ │ │RG││ ││RG││

└───────┬───────┘ │ │->││ ││ ││

┌──────┐ │ a │ │ │╞═════>╡│ ││

│ ┌────V──V───────┐ ──>┤Dk│ ││ ││ ││

│ │ ..... │ S│ │ ││ W││ ││

│ │ │ ─v┴──┴──┴┘ ─v┴┴──┴┘

│ │ a=f(...) │

│ │ │

│ │ (D,x):=(a,D) │

│ │ │

│ │ J:=J+1 │

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

│ ─V─

└────────>┤B:=D├>

__/ └────┘

, , , -

().

ɠ

-

, -

. -

582, 583, 584, 588, 589, 1800, 1804 .., -

, , --

.

:

╔══════════════════╦═══════════════════════════╗

║ ║ ║

║ ║ SYN┐ ACC ║

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

║ │ │ RGF ││ ║ C││RG││ │ ALU │ ║

║ │ │ ││ ║ ││ ││ │ │ ║

║ │ │ ││ ╚════>╡│ │╞═════>╡ │ ║

║ │ │ ││ ││ ││ │ ╞═══╩═>DO

╚═══>╡D│ ││ └┴──┴┘ │ │

│ │ ││ T │ │

│ │ ││ ┌┬──┬┐ │ ╞═════>P

│ │ ││ ││RG││ │ │

│ │ │╞═════════>╡│ │╞═════>╡ │

│ │ ││ ││ ││ │ │

C W││ ││ C││ ││ ╔═>╡ │

─o─A┴A┴─────┴┘ ─┬┴┴──┴┘ ║ └──A──┘

SYN┘ │ ║ SYN┘ ║ ║

│ ║ ║ ║

yW YA DI═════╝ YF

ALU - - -

,

.

RGF - - RAM -

.

RG'T' - - .

RG'CC' - - -

.


DI,DO - .

- ().

YF - .

YA - / RGF.

yW - RGF.

, RGF,

. -

, -

,

RG'T' -

. -

RG'ACC', -

SYN=1 RGF; RG'T'

. SYN=0 -

RG'T', .. ,

( ) RGF. -

RGF RG'ACC' , .. -

.

Š

.

:

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

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

╚╡ CS │ ││RG││ │CS ╞<╝

│ ╞<═╦═╡│ │╞<══╡ │

┌───┤ b │ ║ ││ ││ │ c ├<────┐

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

│ ┌────┐ ║ └───────────┐ │

│ │CS ╞<═╝ │ │

│┌──┤ a ├<───────────────────┐ │ │

││ └────┘ │ │ │

----││----------------------------│-│-│--

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

│└─>┤ CS│ ││RG││ │ CS ├┘ │ ││

└──>┤ ╞════>╡│ │╞═>╡ ├──┘ ││Y

│ │ ││ ││ │ ├────┘│

╔>╡ p │ ││ ││ │ y ╞═╗ ┘

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

╚════════════════════════════╝

, (t)=f(Y(t))

,

PB(t+1)=F(Y(t))

,

- .

-

. , -

,

( ),

(CSy,CSa,CSp,RG).

:

> ty + ta + tp + trg,

tj- .

, -

- :


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

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

╚╡ CS │ ││RG││ │CS ╞<╝

│ ╞<═╦═╡│ │╞<══╡ │

┌───────────┤ b │ ║ ││ ││ │ c ├<────┐

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

│ ┌┬──┬┐ ┌────┐ ║ └───────────┐ │

│┌─┤│RG│╞<══╡ CS ╞<═╝ │ │

││ ││ ││ │ a ├<───────────────────┐ │ │

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

││ └──────────────────────────┐ │ │ │

---││----------------------------------│-│-│-│--

││ MK │ │ │ │

││ PA ┌────┬────┐ ┌┬──┬┐│ │ │ │┐

│└────>┤ CS│ CS │ ││RG│├┘ │ │ ││

│ │ │ │ ││ │├──┘ │ ││Y

└─────>┤ │ ╞═══════════>╡│ │├────┘ ││

│ │ │ ││ │├──────┘│

╔>╡ p │ y │ ││ │╞═╗ ┘

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

╚═══════════════════════════════╝

,

, . -

RG'FF' ( ) RG'MK' ( -

) .

:

T > max( ta,(tp + ty) )+ trg ,

PA(t+1)=f(Y(t)), ..

.

mS{...;pA=f(...)}

<< GO(pA;mi,mj)>>,

, -

-

:

mS{...,pA=f(...)}

mS'{ }

<< GO(pA;mi,mj)>>

,

, -

. -

( , )

.

, SYN,

, -

. =0 - - -

. -

0 1

(),

. "" ͠

:

┌──────────┐ ┌────────┐

V 0H/CONST│ V 1H/SYN│

█▀▀▀█────────┘ █▀▀▀█──────┘

>▌ 0 ▐──────────────>▌ 1 ▐──────┐

█▄▄▄█ 1H/CONST █▄▄▄█ 0H/X │

렠 │

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

,


D-.

( ):

)- , )- :

┌──┐ ┌──┐

SYN ──┬──────────┤ 1├── CC SYN ──┬──────────┤ &├── CC

│ ┌─┬─┐ ┌─┤ │ │ ┌─┬─┐ ┌─┤ │

└─/C│T│ │ └──┘ └─C│T│ │ └──┘

│ │ ├ │ │ │ ├──┘

┌─┤D│ │ │ ┌─┤D│ │

│ ├─┤ o──┘ │ ├─┤ o─

├─oR│ │ ├─oR│ │

H │ └─┴─┘. . . H │ └─┴─┘. . .

──┴─────────────────── ──┴───────────────────

, -

, ,

.


.. 11_03_91

.

,

(), ..

.

.

, .

, -

(

):

- -

-

(.. );

- .

-

.

-

, -

() -

(,

, ). -

- -

: .

, -

( )

. -

-

, , , -

.

, , -

, :

- ,

- ,

- ,

- .

, -

, :


███

┌───┐│

│ ┌VV─┐

n1│ │m1 │ n1 { m1 }

│ └─┬─┘

│ ┌─V─┐ n2 { m2 }

n2│ │m2 │

│ └─┬─┘ g1 <>

│ │<──┐

│ ┌V┐ 0│ n3 { m3 }

g1│ < a >─┘

│ └┬┘ n4 { m4 }

│ 1│<────┐

│ │┌───┐│ g2 <>

│ ┌─VV┐ ││

n3│ │m3 │ ││ n5 { m5 }

│ └─┬─┘ ││

│ ┌─V─┐ ││ g3 <>

n4│ │m4 │ ││

│ └─┬─┘ ││

│10 ┌V┐ 01││

g2└──< ab>──┘│

11 └┬┘ │

00│┌───┐│

┌─VV┐ ││

n5 │m5 │ ││

└─┬─┘ ││

┌V┐ 0 ││

g3 < a >──┘│

└┬┘ 1 │

└─────┘

: -

( ), g1,

. , g2,

4- , e -

.

,

.

, -

. -

-

, , , -

- " ".

- .-

""; ,

"" "" - . " ".

( ,

, -

, .)

,

.

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

│MUX│ q │ROM│ ││RG││ │ROM│

a─>┤0 ├──>┤ │ S' ││ ││ S │ │ Y

b─>┤1 │ │ ╞═══>╡│ │╞═╦>╡ ╞══>

│ │ ╔>╡ │ ││ ││ ║ │ ├─┐

│ │ ║ │ 2 │ C││ ││ ║ │ 1 │ │

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

│ H ╚═════════════════╝ │

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


.

, -

, -

.

(ROM_1), , -

; -

,

, -

.

(ROM_2), ,

.

, . Ӡ -

, -

.

n1 { m1 } S│ Y H│ S q│S'│

─┼────┤ ───┼──┤

n2 { m2 } 0│m1 x│ 0 0│ 1│

│ │ 0 1│ 1│

<> │ │ │ │

1│m2 0│ 1 0│ 2│

d1 { m0 } │ │ 1 1│ 3│

│ │ │ │

<> 2│m0 0│ 2 0│ 2│

│ │ 2 1│ 3│

n3 { m3 } │ │ │ │

3│m3 x│ 3 0│ 4│

n4 { m4 } │ │ 3 1│ 4│

│ │ │ │

<> 4│m4 0│ 4 0│ 5│

│ │ 4 1│ 0│

d2 { m0 } │ │ │ │

5│m0 1│ 5 0│ 6│

<> │ │ 5 1│ 4│

│ │ │ │

n5 { m5 } 6│m6 0│ 6 0│ 6│

│ │ 6 1│ 4│

<> ─┴────┘ ───┴──┘

, -

" ". ,

ROM_1 :

0- ROM_1 , -

.

┌───┐ q ┌───┐ ┌───┐ ┌┬──┬┐

│MUX├──────────>┤ROM│ │ROM│Y ││RG││ Y'

a─>┤0 │ C │ │ S │ ╞══>╡│ │╞══>

b─>┤1 │ ─/┬┬──┬┐ │ ╞═╦>╡ │H ││ ││

│ │ ╔>╡│RG│╞═>╡ │ ║ │ ├──>┤│ │├┐

│ │ ║ ││ ││S'│ 2 │ ║ │ 1 │ C││ │││

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

│H' ╚═══════════════╝ │

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


̠

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

║╔═════════════════════════╗║

║║ ┌───┐ ┌┬──┬┐ ┌───┐A0║║

║║ │MUX│ ││RG││ │ROM╞══╝║

║╚>╡0 │ ││ ││A │ │A1 ║

┌───┐╚═>╡1 ╞═══>╡│ │╞═>╡ ╞═══╝

│MUX│ │ │ ││ ││ │ ╞══>Y

a─>┤0 │ │ │ C││ ││ │ ├┐

b─>┤1 │ └A──┘ ─/┴┴──┴┘ └───┘│H

│ ├────┘ │

└A──┘ │

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

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

║╔══════════════════════════╗║

║║ ┌───┐ ┌────┐A0 ┌┬──┬┐A0'║║

║║ │MUX│ │ROM ╞══>╡│RG│╞═══╝║

║║ │ │ │ │A1 ││ ││A1' ║

║╚>╡0 │A │ ╞══>╡│ │╞════╝

┌───┐╚═>╡1 ╞═>╡ │ Y ││ ││ Y'

│MUX│ │ │ │ ╞══>╡│ │╞══>

│ │ │ │ │ │ H ││ ││

a─>┤0 │ │ │ │ ├──>┤│ │├┐H'

b─>┤1 │ └A──┘ └────┘ ─/┴┴──┴┘│

│ ├────┘ C │

└A──┘ │

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

, , -

,

. -

, .

n1 { m1 } A│ Y H A0 A1│

─┼──────────┤

n2 { m2 } 0│m1 x 1 1│

│ │

<> 1│m2 0 2 3│

│ │

d1 { m0 } 2│m0 0 2 3│

│ │

<> 3│m3 x 4 4│

│ │

n3 { m3 } 4│m4 0 5 0│

│ │

n4 { m4 } 5│m0 1 6 4│

│ │

<> 6│m5 0 6 4│

─┴──────────┘

d2 { m0 }

<>

n5 { m5 }

<>


򠠠

┌────────────────────────┐ ┌─────────────────────────┐

│ ┌───┐ ┌┬──┬┐ ┌───┐│e │ ┌───┐ ┌───┐ e ┌┬──┬┐│

│ │MUX│ q ││RG││q'│ROM├┘ │ │MUX│ q'│ROM├────>┤│RG│├┘

└>┤0 ├────>┤│ │├─>┤ │ Y └>┤0 ├──>┤ │ Y ││ ││Y'

a─>┤1 │ S ││ ││S'│ ╞══> a─>┤1 │ S'│ ╞════>╡│ │╞═>

b─>┤2 │ ╔══>╡│ │╞═>╡ ╞══╗ b─>┤2 │ ╔>╡ │ H ││ ││

│ │ ║ C││ ││ │ ╞╗ ║ │ │ ║ │ ├────>┤│ │╞═╗

└A──┘ ║ ─/┴┴──┴┘ └───┘║ ║ │ │ ║ │ │ S ││ ││ ║

║ H ╚════════════════╝ ║ │ │ ║ │ ╞════>╡│ │╞╗║

╚═══════════════════════╝ └A──┘ ║ └───┘ ─/┴┴──┴┘║║

║ H' ║ C ║║

║ ╚═════════════════╝║

╚═══════════════════════╝

-

( - ),

. -

-

.

.

.  

-

. -

, -

.

n1 { m1 } --(0,0),(2,1) S'q'│ Y H S e│

────┼────────┤

n2 { m2 } --(4,0) 0 0 │m1 0 4 0│

│ │

<>-- 1,x 0 1 │m4 1 2 x│

│ │

d1 { m0 } --(1,0) 1 0 │m0 1 1 x│

│ │

<>-- 1,x 1 1 │m3 0 0 1│

│ │

n3 { m3 } --(1,1),(3,1) 2 0 │m0 2 3 x│

│ │

n4 { m4 } --(0,1) 2 1 │m1 0 4 0│

│ │

<>-- 2,x 3 0 │m5 1 3 x│

│ │

d2 { m0 } --(2,0) 3 1 │m3 0 0 1│

│ │

<>-- 3,x 4 0 │m2 1 1 x│

│ │

n5 { m5 } --(3,0) ────┴────────┘

<>-- 3,x

:

- , -

, -

;


- -

;

- -

.

-

, , -

.

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

│ ╔══════════════════════════╗│ ROM_0 A'│ Y H A e│

│ ║ ┌────┐ ║│ ──┼──────────┼

│ ║ │ROM ╞═╬A ║│ 0 │m1 0 4 0│

│ ║ │ ├─╫e ║│ 1 │m0 1 1 x│

│ ╠>╡ ╞═╬Y ┌───┐ ┌┬──┬┐║│ 2 │m0 2 3 x│

│ ║ │ ╞═╬H │MUX│ ││RG│╞╝│ 3 │m5 1 3 x│

│ ║ │ 0 │ ╚══>╡0 │ ││ │├─┘e' 4 │m2 1 1 x│

│ A'║ ├────┤ │ │ ││ ││ ──┴──────────┘

│ ║ │ROM ╞═╬A │ ╞══>╡│ │╞══>Y' ──┬──────────┬

│ ┌───┐║ │ │ ╠══>╡1 │ ││ ││ ROM_1 A'│ Y H A e│

│ │MUX│╚>╡ ├─╫e │ │ C││ │╞╗H' ──┼──────────┼

└>┤0 │ │ ╞═╬Y └A──┘ ─/┴┴──┴┘║ 0 │m4 1 2 x│

a>┤1 │ │ 1 ╞═╬H │ ║ 1 │m3 0 0 1│

b>┤2 │ └────┘ │ ║ 2 │m1 0 4 0│

│ ├──────────────┘ ║ 3 │m3 0 0 1│

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

╚══════════════════════════════╝

, , , -

.

( -

).

┌───┐ ┌──┐ 0W- +1

│MUX├─>┤M2├──┐ 1W-

0─>┤0 │┌>┤ │ ─V┬┬──┬┐ ┌───┐ Y

a─>┤1 ││ └──┘ W││CT││ │ROM╞══>

b─>┤2 ││ ││ ││ │ │H

│ ││ ││ ││A │ ╞════╗

│ ││ ╔══>╡│ │╞═>╡ │e ║

└A──┘│ ║ ││ ││ │ ├──┐ ║

║ │ ║ C││ ││ │ ╞═╗│ ║

║ │ ║ ─/┴┴──┴┘ └───┘S║│ ║

║ │ ╚═════════════════╝│ ║

║ └───────────────────────┘ ║

╚═════════════════════════════╝

: -

, ( ..

"" ), - -

.

, "" , , -

, .


: -

, -

, -

.

2,

, -

.

n1 { m1 } -- 0 A │ Y H e S│

──┼───────────┤

n2 { m2 } -- 1 0 │m1 x x 1│

│ │

<> 1 │m2 1 0 3│

│ │

d1 { m0 } -- 2 2 │m0 1 1 2│

│ │

<> 3 │m3 x x 4│

│ │

n3 { m3 } -- 3 4 │m4 1 0 0│

│ │

n4 { m4 } -- 4 5 │m0 2 0 3│

│ │

<> 6 │m5 1 1 6│

│ │

d2 { m0 } -- 5 7 │m0 0 1 3│

──┴───────────┘

<>

n5 { m5 } -- 6

<>

-

,

.

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

║╔═════════════════════╗ ║

║║ ┌┬──┬┐ ┌───┐║ ┌───┐S║

║║ ┌───┐ ││RG││ │MUX│║ │ROM╞═╝

║╚═>╡INC╞═>╡│ │╞>╡0 │║ │ │Y ┌┬──┬┐Y'

║ └───┘ C││ ││ │ │║ │ ╞══>╡│RG│╞══>

║ ─/┴┴──┴┘ │ ╞╩>╡ │ ││ ││

║ ─/┬┬──┬┐ │ │A │ │H ││ ││H'

║ C││RG││ │ │ │ ╞══>╡│ │╞══╗

╚═════════>╡│ │╞>╡1 │ │ │e ││ ││e'║

││ ││ │ │ │ ├──>┤│ │├┐ ║

┌───┐ └┴──┴┘ └A──┘ └───┘ ─/┴┴──┴┘│ ║

│MUX│ ┌──┐ │ C │ ║

0─>┤0 ├─>┤M2├────┘ │ ║

a─>┤1 │┌>┤ │ │ ║

b─>┤2 ││ └──┘ │ ║

│ ││ │ ║

└A──┘└─────────────────────────────┘ ║

╚═══════════════════════════════════╝


╔════════════════════════════╗ C

║╔═══════════════════╗ ║ ─/┬┬──┬┐H'

║║ ┌┬──┬┐ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗

║║ ┌───┐ ││RG││ │MUX│║ │ROM│ ║ ║ ┌>┤│ │├─┐║

║╚>╡INC╞>╡│ │╞>╡0 │║ │ │S║H║e│ └┴──┴┘ │║

║ └───┘C││ ││ │ │║ │ │ ║ ║ │ ┌┬──┬┐Y│║ RG"Y"

║ ─/┴┴──┴┘ │ ╞╩>╡ ▐██████>╡│RG│╞>│║

║ ─/┬┬──┬┐ │ │A │ │ w c││ ││ │║ 0w-

║ C││RG││ │ │ │ │ ─A─/┴┴──┴┘ │║

╚═══════>╡│ │╞>╡1 │ │ │k │ ┌┬─┬┐k'│║ 1w-

││ ││ │ │ │ ├────┴─>┤│T│├┐ │║

┌───┐ └┴──┴┘ └─A─┘ └───┘ ─/┴┴─┴┘│ │║ k ┌───┐

│MUX│ ┌──┐ ┌─┐│ C │ │║ └────┤ 1 ├─ CC

0>┤0 ├─>┤M2├─>┤&├┘ │ │║ ┌────┤ │

a>┤1 │┌>┤ │┌>┤ │ │ │║ SYN └───┘

b>┤2 ││ └──┘│ └─┘ │ │║

│ ││e' └──────────────────────────┘ │║ CC -

└A──┘└──────────────────────────────────┘║

╚═══════════════════════════════════════╝

.

, . ( -

-"" -

.) , ,

(

)

. -

:

- ,

- ().

-

"k". k=0 -

.

. .

k=1 .

-

. ,

, -

, -

.

񠠠 A ▌k│ Y │

n1 { m1 } -- 0 ▌ │ H│ e│ S│

──▌─┼──┴──┴──┤

n2 { m2 } -- 1 0 ▌0│ m1 │

1 ▌0│ m2 │

g1 <>-- 2 ──▌─┼──┬──┬──┤

2 ▌1│ 1│ 1│ 2│

n3 { m3 } -- 3 ──▌─┼──┴──┴──┤

3 ▌0│ m3 │

n4 { m4 } -- 4 4 ▌0│ m4 │

──▌─┼──┬──┬──┤

g2 <>-- 5 5 ▌1│ 1│ 0│ 0│

6 ▌1│ 2│ 0│ 3│

g3 <>-- 6 ──▌─┼──┴──┴──┤

7 ▌0│ m5 │

n5 { m5 } -- 7 ──▌─┼──┬──┬──┤

8 ▌1│ 1│ 1│ 7│

g4 <>-- 8 9 ▌1│ 0│ 1│ 3│


-

, -

.

SYN ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌────

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

| | | | |

k 0 ▄▄▄▄▄▄▄▄ 0 ▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄ 0 ▄▄▄

──────▀▀▀▀▀▀▀▀─────▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀─────▀▀▀

| | | | |

CC┐ ┌──────────┐ ┌────────────────────────────────────┐ ┌────

└─┘ └─┘ └─┘

| | | | |

Y────▄────────────▄──────────────────────────────────────▄───

─────▀────────────▀──────────────────────────────────────▀───

.

, -

,

.

,

, .

, -

.

. ( -

, ,

.)

╔══════════════════════╗ C

╔══════║══════════════╗ ║ ─/ ┬┬──┬┐H'

║ ║ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗

║ ║ │MUX│║ │ROM│ ║ ║ ┌>┤│ │├─┐║

F ═║══════║════════>╡0 │║ │ │ ║ ║ │ └┴──┴┘ │║

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

║ ║ ││RG││ │ │║ │ │ ║ ║ │ │║

║ ╚>╡│ │╞═>╡1 │║ │ │S║H║e│ │║

║ C││ ││ │ │║ │ │ ║ ║ │ ┌┬──┬┐Y│║ RG"Y"

║ ─/┴┴──┴┘ │ ╞╩>╡ ▐██████>╡│RG│╞>│║

║ ┌┬──┬┐ │ │A │ │ ││ ││ │║ 0w-

║ ┌───┐ ││RG││ │ │ │ │ w c││ ││ │║

╚>╡INC╞═>╡│ │╞╦>╡2 │ │ │ ─A─/┴┴──┴┘ │║ 1w- .

└───┘ C││ ││║ │ │ │ │ │ │║

─/┴┴──┴┘║ │ │ │ │ │ │║

╔══════════╝ │ │ │ │ │ │║

║ ┌┬─────┬┐ │ │ │ │ ┌┘k │║

╚>╡│STACK│╞═>╡3 │ │ │K │ ┌┬──┬┐K' │║

└┴────A┴┘ │ │ │ ╞═══╧>╡│RG│╞╗ │║

║ │ │ │ │ ││ ││║ │║

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

┌───┐ ║ ║ C ║ │║

│MUX│ ┌──┐ ┌╨──────╨┐ ║ │║

0>┤0 ├─>┤M2├>┤ CS ╞<══════════════════╝ │║

a>┤1 │┌>┤ │ │ │ │║

b>┤2 ││ └──┘ └────────┘ │║ k ┌───┐

│ ││e' │║ └─┤ 1 ├─CC

└A──┘└──────────────────────────────────────┘║ ──┤ │

╚═══════════════════════════════════════════╝ SYN └───┘


-

.

.

, ,

.

-

, - (stack).

()

" - " (Last In - First Out, LIFO).

, , -

, -

1,2,...,N.

.

:

-"" ,

-"" () -

,

-"" -

.

"-

" . -

"" , -

"" .

"" "" -

.

"" -

. , 4

, 4 -

, ,

.

CS

"" -

.

-

, ,

, ""

, , -

.

, -

:

,

. , -

. -

,

, -

, , , ..

RG'.

, :

F = { 1, ; 0, },

P - .

,

:


──────────────┐ │ │W

┌┬──┬┐ │ ─V┬───┐ q ┌A───┐ f

t ││RG││ └──>┤MUX├───>┤ SS ├<──────────────────────┐

──┬───>┤│ │├────>┤ │┌──>┤ ├<─────────────────────┐│

│ ││ ││ │ ││t │ │ p ││

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

│ │ │ │ │j ││

└───┼────────────────┘ │─V┬───┐ ┌─────┐ P ┌┬──┬┐p││

│ │ │MUX│ │ ROM ├───>┤│RG│├─┘│

│ │ │ │ │ │ F ││ ││f │

│ │ │ ├───>┤│ │├──┘

│ │ │ │ ││ ││

│ │ │ ▐███>││ │▐██>

│ │ │ │ ││ ││

C │ │ └─────┘ ─A┴┴──┴┘

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

c=1 .

SS ,

s0 s1,

s0, 0f, w=1, j=q

s0, 1f, 0c, w=0, j=p

s0, 1f, 1c, p==t, w=1, j=p

s0, 1f, 1c, p=/=t, w=0, j=x, s1

s1, w=1, j=q, s0

.. 11_03_91 . . ,

 

 

 

! , , , .
. , :