Лупал А.М. Теория автоматов (часть 2)
Подождите немного. Документ загружается.
104
Òàáëèöà 10.2 Òàáëèöà 10.3 Òàáëèöà 10.4
Èç òàáë.10.3 âèäíî, ÷òî ïàðà (a
1
, a
2
), (a
6
, a
6
) ðàçâÿçàíà (÷åòâåðêà
(0011)). Òî÷íî òàê æå ðàçâÿçàíû ïàðû, îáðàçîâàííûå ïåðåõîäîì
(a
2
, a
2
) è âñåìè ïîñëåäóþùèìè ïåðåõîäàìè â M
1
. Îáðàòèìñÿ ê
ïàðå (a
3
, a
4
), (a
5
, a
6
). Èç òàáë. 10.3 ïîëó÷àåì ñîîòâåòñòâóþùóþ ÷åò-
âåðêó (1111) ïàðà íå ðàçâÿçàíà. Ââîäèì ïåðåìåííóþ t
2
è ïîëàãà-
åì äëÿ a
3
è a
4
çíà÷åíèå τ
2
=0, à äëÿ a
5
è a
6
τ
2
= 1 (òàáë. 10.4).
Ïîñëå ÷åãî îñòàëüíûå ïåðåõîäû â M
1
òîæå ðàçâÿçàíû. Àíàëîãè÷íî
äëÿ M
2
è M
3
ïîëó÷èì òàáë.10.5 è 10.6.
Òàáëèöà 10.5 Òàáëèöà 10.6
Ïåðåõîäèì ê ìèíèìèçàöèè. Èñêëþ÷àåì ïåðåìåííóþ τ
1
(òàáë. 10.7)
è ïîâòîðÿåì ïðîöåññ ðàçâÿçûâàíèÿ ïàð ïåðåõîäîâ.
Îêàçûâàåòñÿ, ÷òî ïàðà (a
1
, a
2
), (a
5
, a
6
) íå ðàçâÿçàíà, â ñâÿçè ñ ÷åì
äîáàâëÿåì ïåðåìåííóþ τ
5
è ðàçâÿçûâàåì ýòó ïàðó (òàáë. 10.8).
Âñå îñòàëüíûå ïàðû ðàçâÿçàíû. Äàëåå èñêëþ÷àåì ïåðåìåííóþ τ
2
è
ïîëó÷àåì òàáë.10.9 ñ òðåìÿ ïåðåìåííûìè τ
3
,τ
4
, τ
5
, â êîòîðîé ïîñëå ïðî-
âåðêè îêàçûâàþòñÿ ðàçâÿçàííûìè âñå ïàðû.
τ
τ
=
`
=
`
=
!
=
"
=
#
=
$
=
%
``
τ
=
=
=
!
=
"
=
#
=
$
=
%
`
τ
=
=
=
!
=
"
=
#
`
=
$
`
=
%
`
τ
τ
τ
!
τ
"
=
`
=
=
!
=
"
`
=
#
=
$
``
=
%
``
τ
τ
τ
!
=
=
=
!
=
"
=
#
=
$
`
=
%
```
105
Òàáëèöà 10.7 Òàáëèöà 10.8
Òàáëèöà 10.9 Òàáëèöà 10.10
Äàëüíåéøàÿ ìèíèìèçàöèÿ íåâîçìîæíà, òàê êàê äëÿ êîäèðîâàíèÿ ñåìè
ñîñòîÿíèé íóæíî íå ìåíåå òðåõ ïåðåìåííûõ. Ïîñëå äîîïðåäåëåíèÿ ïðî-
÷åðêîâ â òàáë. 10.1 ïîëó÷àåì òàáë. 10.10 ïðîòèâîãîíî÷íîãî êîäèðîâà-
íèÿ ñîñòîÿíèé èñõîäíîãî àâòîìàòà.
10.2. Ïðîòèâîãîíî÷íîå ñîñåäíåå êîäèðîâàíèå
Âòîðîé ñïîñîá êîäèðîâàíèÿ, ïîçâîëÿþùèé èçáàâèòüñÿ îò ãîíîê,
ýòî êîäèðîâàíèå ñîñåäíèõ ñîñòîÿíèé àâòîìàòà ñîñåäíèìè êîäàìè (ñî-
ñåäíåå êîäèðîâàíèå). Ñîñåäíèå ñîñòîÿíèÿ ýòî ñîñòîÿíèÿ, ñâÿçàííûå
äóãîé íà ãðàôå àâòîìàòà, à ñîñåäíèå êîäû ýòî äâîè÷íûå íàáîðû, îòëè-
÷àþùèåñÿ òîëüêî îäíèì ðàçðÿäîì. Ðàññòîÿíèå ïî Õýììèíãó ó òàêèõ
êîäîâ ðàâíî 1. Ïðè ñîñåäíåì êîäèðîâàíèè ïðè ïåðåõîäå àâòîìàòà èç
îäíîãî ñîñòîÿíèÿ â äðóãîå ìåíÿåòñÿ ñîñòîÿíèå òîëüêî ó îäíîãî ýëåìåí-
òà ïàìÿòè è ñîñòÿçàíèÿ ñòàíîâÿòñÿ íåâîçìîæíûìè. Ñîñåäíåå êîäèðî-
âàíèå íå âñåãäà îêàçûâàåòñÿ âîçìîæíûì [4] è â ýòîì ñëó÷àå ïðèõîäèò-
τ
!
τ
"
τ
#
=
=
=
!
`
=
"
`
=
#
=
$
`
=
%
``
τ
τ
!
τ
"
τ
#
=
=
=
!
`
=
"
`
=
#
=
$
` `
=
%
` `
τ
τ
!
τ
"
=
`
=
=
!
=
"
`
=
#
=
$
` `
=
%
`
τ
!
τ
"
τ
#
=
=
=
!
=
"
=
#
=
$
=
%
106
ñÿ íà ãðàôå ìåæäó ñîñåäíèìè ñîñòîÿíèÿìè àâòîìàòà âñòàâëÿòü äîïîë-
íèòåëüíûå, òàê íàçûâàåìûå íåóñòîé÷èâûå ñîñòîÿíèÿ. Íåóñòîé÷èâîå ñî-
ñòîÿíèå àâòîìàòà (ñîñòîÿíèå a
k
, íà ðèñ. 10.1) îòëè÷àåòñÿ òåì, ÷òî ïîä
äåéñòâèåì íåêîòîðîãî âõîäíîãî ñèãíàëà Z
k
, ïî äëèòåëüíîñòè ïðåâûøà-
þùåãî âðåìÿ ïåðåõîäà â ýòî ñîñòîÿíèå a
k
, àâòîìàò ìîæåò åãî ïðîñêî-
÷èòü, ïåðåéäÿ ñðàçó â ñëåäóþùåå ñîñòîÿíèå a
s
.
 ïðîöåññå äîáàâëåíèÿ íåóñòîé÷èâûõ ñîñòîÿíèé íåîáõîäèìî ñëåäèòü
çà òåì, ÷òîáû çíà÷åíèå âûõîäíîãî ñèãíàëà ïðè ýòîì íå ìåíÿëîñü. Äëÿ
òîãî ÷òîáû óäîáíåå áûëî íàõîäèòü êîäû ñîñåäíèõ ñîñòîÿíèé, öåëåñî-
îáðàçíî âîñïîëüçîâàòüñÿ äèàãðàììîé Âåé÷à. ×èñëî êëåòîê íåîáõîäè-
ìîé äèàãðàììû îïðåäåëÿåòñÿ êàê 2
k
, ãäå k ÷èñëî ñîñåäåé ó òîãî ñî-
ñòîÿíèÿ àâòîìàòà, êîòîðîå èìååò èõ áîëüøå âñåõ îñòàëüíûõ ñîñòîÿíèé.
Ðàññìîòðèì ïðèìåð êîäèðîâàíèÿ ñîñåäíèìè êîäàìè ñîñòîÿíèé ôðàã-
ìåíòà ãðàôà íåêîòîðîãî àâòîìàòà, ïðèâåäåííîãî íà ðèñ. 10.2.
Ñîñòîÿíèåì ñ ìàêñèìàëüíûì ÷èñëîì ñîñåäåé (k = 6) ÿâëÿåòñÿ ñî-
ñòîÿíèå a
0
. Ñëåäîâàòåëüíî, äëÿ êîäèðîâàíèÿ óäîáíî âîñïîëüçîâàòüñÿ
äèàãðàììîé Âåé÷à ðàçìåðîì 8×8=64=42 êëåòîê (ðèñ. 10.3). Ïîìåñòèì
ñîñòîÿíèå a
0
â ïðîèçâîëüíóþ êëåòêó äèàãðàììû, íàïðèìåð ñîîòâåòñòâó-
þùóþ êîäó 110110 (Q
1
Q
2
Q
3
Q
4
Q
5
Q
6
). Ýòà êëåòêà èìååò 6 ñîñåäíèõ
êëåòîê, êóäà öåëåñîîáðàçíî ïîìåùàòü âñå ñîñòîÿíèÿ, ñîñåäíèå a
0
. Òîã-
äà ïîëó÷èì ñëåäóþùèå êîäû ñîñòîÿíèé:
a
m
Z
k
Z
k
a
k
a
s
Ðèñ. 10.1
a
"
a
!
Z
Z
Z
W
W
W
W
W
W
W
W
W
Z
Z
Z
Z
Z
"
Z
!
a
a
$
a
%
a
#
a
a
Ðèñ. 10.2
107
k(a
0
) 110110, k(a
1
) 110100, k(a
2
) 110010, k(a
3
) 100110
Î÷åâèäíî, êîäû ñîñòîÿíèé a
1
, a
2
,
a
3
îòëè÷àþòñÿ îò êîäà ñîñòîÿíèÿ a
0
òîëüêî îäíèì ðàçðÿäîì. Ïîñêîëüêó ñîñòîÿíèå a
5
ÿâëÿåòñÿ îäíîâðåìåí-
íî ñîñåäíèì è äëÿ a
0
, è äëÿ a
1
, íåîáõîäèìî ïîìåñòèòü åãî â òàêóþ êëåò-
êó, êîòîðàÿ èìåëà áû ìèíèìàëüíûå ðàññòîÿíèÿ îò îáîèõ ýòèõ ñîñòîÿ-
íèé. Òàêèìè êëåòêàìè ÿâëÿþòñÿ êëåòêè ñ êîäàìè 010100 è 010110. Âû-
áåðåì îäíó èç íèõ (íàïðèìåð, 010110). Òîãäà, ÷òîáû îáåñïå÷èòü ñîñåä-
íåå êîäèðîâàíèå, ïðèäåòñÿ ââåñòè äîïîëíèòåëüíîå íåóñòîé÷èâîå ñîñòî-
ÿíèå b
1
, èñïîëüçóÿ äëÿ íåãî âòîðîé èç ýòèõ êîäîâ, à èìåííî êîä 010100.
Ïîñëå ýòîãî îñòàâøèåñÿ ñîñòîÿíèÿ a
4
è a
6
ìîæíî ïîìåñòèòü â êëåò-
êè ñ êîäàìè 110111 è 111110 ñîîòâåòñòâåííî. Ñîñòîÿíèå a
7
, ñîñåäíåå
ñîñòîÿíèÿì a
3
è a
2
, óäà÷íî ïîìåùàåòñÿ â êëåòêó 100010, íî ïðè ýòîì íå
ïîëó÷àåòñÿ òðåáóåìûõ ñîñåäíèõ êîäîâ ó ñîñòîÿíèé a
7
è a
1
. Ïîýòîìó íà
ïåðåõîäå a
7
→ a
1
íåîáõîäèìî ââåñòè äîïîëíèòåëüíûå ñîñòîÿíèÿ (ìåíü-
øå äâóõ ïðè âûáðàííîì êîäèðîâàíèè íå ïîëó÷àåòñÿ) b
2
è b
3
, ðàñïîëî-
æåííûå ñîîòâåòñòâåííî â ñîñåäíèõ êëåòêàõ (a
7
ñ b
2
, b
2
ñ b
3
, b
3
ñ a
1
).
 ðåçóëüòàòå êîäèðîâàíèÿ ÷èñëî ñîñòîÿíèé ãðàôà óâåëè÷èëîñü íà 4
(ðèñ. 10.4), ÷òî, åñòåñòâåííî, óìåíüøàåò áûñòðîäåéñòâèå àâòîìàòà.
Ðèñ. 10.3
3
!
3
3
>
>
!
=
>
=
!
=
=
#
=
$
=
%
=
=
"
3
$
3
#
3
108
Êîäû ñîñòîÿíèé, ïîëó÷åííûõ â ðåçóëüòàòå ñîñåäíåãî êîäèðîâàíèÿ,
ïðèâåäåíû â òàáë. 10.11.
Òàáëèöà 10.11
Ñëåäóåò îòìåòèòü, ÷òî â ãðàôå ïåðåõîäîâ ìîæíî íàéòè òàêèå ïàðû
ñîñåäíèõ ñîñòîÿíèé (a
m
z
k
→ a
s
), êîòîðûå íå òðåáóþò ñîñåäíåãî êîäèðî-
âàíèÿ.  ýòîì ñëó÷àå êîäû, ïîÿâëÿþùèåñÿ â ðåçóëüòàòå ñîñòÿçàíèé (ëîæ-
íûå êîäû), ìîãóò áûòü èñïîëüçîâàíû äëÿ êîäèðîâàíèÿ ñîñòÿçàíèé àâòî-
ìàòà, óäîâëåòâîðÿþùèõ îäíîìó èç ñëåäóþùèõ óñëîâèé:
1) êîäèðóåìîå ëîæíûì êîäîì ñîñòîÿíèå (a
i
) äîëæíî áûòü óñòîé÷è-
âûì ïî îòíîøåíèþ ê âõîäíîìó ñèãíàëó z
k
, (ðèñ. 10.5); ïîñêîëüêó ïîä
a
"
a
!
Z
Z
W
W
W
W
W
W
W
W
W
Z
Z
Z
Z
Z
Z
"
Z
!
a
a
$
a
%
a
#
a
a
b
b
!
W
Z
W
Z
b
îãîíòêàðòñáàåèíÿîòñîÑ
àòàìîòâà
äîêéûí÷èîâÄ
ÿèíÿîòñîñåèùþóâòñòåâòîîÑ
èòÿìàïâîòíåìåëý
=
0
011011 3
1
3
2
3
3
3
4
3
5
3
6
=
1
001011 3
1
3
2
3
3
3
4
3
5
3
6
=
2
010011 3
1
3
2
3
3
3
4
3
5
3
6
=
3
011001 3
1
3 3
3
3
4
3
5
3
6
=
4
111011 3
1
3
2
3
3
3
4
3
5
3
6
=
5
011010 3
1
3
2
3
3
3
4
3
5
3
6
=
6
011111 3
1
3
2
3
3
3
4
3
5
3
6
=
7
010001 3
1
3
2
3
3
3
4
3
5
3
6
>
1
001010 3
1
3
2
3
3
3
4
3
5
3
6
>
2
000001 3
1
3
2
3
3
3
4
3
5
3
6
>
3
000011 3
1
3
2
3
3
3
4
3
5
3
6
Ðèñ. 10.4
109
äåéñòâèåì z
k
àâòîìàò èç a
i
íèêóäà ïåðåéòè íå ìîæåò, ñîñòÿçàíèÿ, åñëè
îíè è âîçíèêíóò, ÿâëÿþòñÿ íåêðèòè÷åñêèìè;
2) èç ñîñòîÿíèÿ a
i
îòñóòñòâóåò ïåðåõîä ïî ñèãíàëó z
k
;
3) èç êîäèðóåìîãî ëîæíûì êîäîì ñîñòîÿíèÿ a
i
ïîä äåéñòâèåì ñèãíà-
ëà z
k
àâòîìàò ïåðåõîäèò â íóæíîå ñîñòîÿíèå a
s
(ðèñ.10.6).
Êîäèðîâàíèå ñîñåäíèõ ñîñòîÿíèé êîäàìè ñ ðàññòîÿíèåì ïî Õýììèí-
ãó, áîëüøèì 1, ìîæíî èñïîëüçîâàòü òàêæå â òåõ ñëó÷àÿõ, êîãäà ëîæíûå
êîäû, âîçíèêàþùèå ïðè ñîñòÿçàíèÿõ, íå èñïîëüçóþòñÿ â ïðîöåññå êîäè-
ðîâàíèÿ.
10.3. Êîäèðîâàíèå ñîñòîÿíèé àâòîìàòà, áëèçêîå ê ñîñåäíåìó
Àíàëèç êàíîíè÷åñêîãî ìåòîäà ñòðóêòóðíîãî ñèíòåçà àâòîìàòîâ ïî-
êàçûâàåò, ÷òî ðàçëè÷íûå âàðèàíòû êîäèðîâàíèÿ ñîñòîÿíèé àâòîìàòà
ïðèâîäÿò ê ðàçëè÷íûì âûðàæåíèÿì ôóíêöèé âîçáóæäåíèÿ ïàìÿòè è ôóí-
êöèé âûõîäîâ. Ýòè âûðàæåíèÿ îáëàäàþò ðàçëè÷íûìè ðàíãàìè êàíîíè-
÷åñêèõ ôîðì çàïèñè, â ðåçóëüòàòå ÷åãî ðåàëèçîâàííûå ïî íèì êîìáèíà-
öèîííûå ñõåìû îáëàäàþò ðàçëè÷íîé ñëîæíîñòüþ, êîòîðàÿ â èòîãå çàâè-
ñèò îò ñïîñîáà êîäèðîâàíèÿ.
Ðàññìîòðèì ýâðèñòè÷åñêèé àëãîðèòì êîäèðîâàíèÿ ñîñòîÿíèé [4] è
ìèíèìèçèðóþùèé ñóììàðíîå ÷èñëî èçìåíåíèé ýëåìåíòîâ ïàìÿòè íà âñåõ
ïåðåõîäàõ àâòîìàòà.
Ââåäåì âåñîâóþ ôóíêöèþ W = ∑t
ms
, ãäå t
ms
= |K
m
K
s
|
2
ðàññòîÿíèå
ìåæäó êîäàìè ñîñòîÿíèé a
m
è a
s
, ðàâíîå ÷èñëó ýëåìåíòîâ ïàìÿòè, èçìå-
íÿþùèõ ñâîå ñîñòîÿíèå íà ïåðåõîäå (a
m
, a
s
); ñóììèðîâàíèå ïðîèçâî-
äèòñÿ ïî âñåì ïåðåõîäàì àâòîìàòà. Ââåäåííàÿ ôóíêöèÿ W ìîæåò ñëó-
æèòü îäíîé èç îöåíîê ñëîæíîñòè êîìáèíàöèîííîé ñõåìû àâòîìàòà S,
ïðè ýòîì óïðîùåíèå êîìáèíàöèîííîé ñõåìû áóäåò òåì áîëüøå, ÷åì
ìåíüøå W.
a
m
Z
k
Z
k
a
s
a
j
a
i
Z
k
ëîæíûå
êîäû
a
m
Z
k
Z
k
Z
k
a
s
a
i
Ðèñ. 10.5
Ðèñ. 10.6
110
Àëãîðèòì ñîñòîèò èç íåñêîëüêèõ øàãîâ.
1. Ïîñòðîèì ìàòðèöó
11
..
.
,
..
.
rr
RR
αβ
=
αβ
αβ
M
ñîñòîÿùóþ èç âñåõ ðàçëè÷íûõ ïàð íîìåðîâ (a
r
, b
r
), òàêèõ, ÷òî â àâòî-
ìàòå S åñòü ïåðåõîä èç a
αr
â a
βr
.
2. Ïåðåñòàâèì ñòðîêè â ìàòðèöå òàê, ÷òîáû âûïîëíÿëîñü óñëîâèå
{α
r
, β
r
}∩{α
1
, β
1
, ..., α
r1
, β
r1
}≠∅, r=2, ..., R. (10.1)
Óñëîâèå (10.1) îçíà÷àåò, ÷òî õîòÿ áû îäèí èç ýëåìåíòîâ r-é ñòðîêè
ñîäåðæèòñÿ â êàêîé-íèáóäü èç ïðåäûäóùèõ ñòðîê. Èìåþòñÿ â âèäó òîëü-
êî ñâÿçíûå àâòîìàòû S, äëÿ êîòîðûõ òàêàÿ ïåðåñòàíîâêà âñåãäà âîç-
ìîæíà.
3. Çàêîäèðóåì ñîñòîÿíèÿ èç ïåðâîé ñòðîêè ìàòðèöû M ñëåäóþùèì
îáðàçîì:
K
α1
= (00 ... 00); K
β1
= (00 ... 01).
4. Âû÷åðêíåì èç ìàòðèöû M ïåðâóþ ñòðî÷êó, ñîîòâåòñòâóþùóþ çà-
êîäèðîâàííûì ñîñòîÿíèÿì a
α1
, è a
β1
. Ïîëó÷èì ìàòðèöó M.
5.  ñèëó óñëîâèÿ (1) â íà÷àëüíîé ñòðîêå ìàòðèöû M çàêîäèðîâàí
îäèí ýëåìåíò. Âûáåðåì èç ïåðâîé ñòðî÷êè ìàòðèöû M íåçàêîäèðîâàí-
íûé ýëåìåíò è îáîçíà÷èì åãî ÷åðåç γ.
6. Ïîñòðîèì ìàòðèöó M
γ
, âûáðàâ èç M ñòðî÷êè, ñîäåðæàùèå γ. Ïóñòü
Â
γ
= {γ
1
, ..., γ
f
, ..., γ
F
} ìíîæåñòâî ýëåìåíòîâ èç ìàòðèöû M
γ
, êîòîðûå
óæå çàêîäèðîâàíû. Èõ êîäû îáîçíà÷èì K
γ1
, ..., K
γf
, ..., K
γF
ñîîòâåòñòâåí-
íî.
7. Äëÿ êàæäîãî K
γf
(f = 1, ..., F) íàéäåì
1
f
C
γ
ìíîæåñòâî êîäîâ,
ñîñåäíèõ ñ K
gf
è åùå íå çàíÿòûõ äëÿ êîäèðîâàíèÿ ñîñòîÿíèé àâòîìàòà.
Ïîñòðîèì ìíîæåñòâî
11
1
f
F
f
DC
γγ
=
=
U
. Åñëè
1
D
γ
= ∅ , òî ñòðîèì íîâîå ìíî-
æåñòâî
22
1
f
F
f
DC
γγ
=
=
U
, ãäå
2
f
C
γ
ìíîæåñòâî êîäîâ, ó êîòîðûõ êîäîâîå
111
ðàññòîÿíèå ñ êîäîì K
γf
ðàâíî äâóì. Åñëè
2
D
γ
= ∅, ñòðîèì àíàëîãè÷íî
3
,...,
n
DD
γγ
, äî òåõ ïîð ïîêà íå íàéäåòñÿ
n
D
γ
≠ ∅ (n = 1, 2, 3, ...). Ïóñòü
n
D
γ
= { K
δ1
, ..., K
δg
, ..., K
δG
}.
8. Äëÿ êàæäîãî K
δg
íàõîäèì W
gf
= | K
δg
K
gf
|2 êîäîâûå ðàññòîÿíèÿ
ìåæäó K
δg
è âñåìè èñïîëüçîâàííûìè êîäàìè K
gf
(f = 1, ..., F). Åñëè â
àâòîìàòå èìååòñÿ ïåðåõîä èç a
γf
â a
γ
è èç a
γ
â a
γf
òî W
gf
, âõîäèò äâàæäû
â W
g
(ñì. íèæå ïðèìåðû ïåðåõîäîâ (a
4
, a
5
) è (a
5
, a
4
)).
9. Íàõîäèì W
g
=
f
F
=
∑
1
W
gf
, g = 1, ..., G.
10. Èç
n
D
γ
âûáèðàåì K
γ
, ó êîòîðîãî W
g
= min W
g
. Ýëåìåíò γ (ñîñòîÿ-
íèå a
γ
) êîäèðóåì êîäîì K
γ
.
11. Èç ìàòðèöû M âû÷åðêíåì ñòðî÷êè, â êîòîðûõ îáà ýëåìåíòà çà-
êîäèðîâàíû, â ðåçóëüòàòå ÷åãî ïîëó÷èì íîâóþ ìàòðèöó, êîòîðóþ òàêèå
îáîçíà÷èì ÷åðåç M. Åñëè â ìàòðèöå M íå îñòàëîñü íè îäíîé ñòðî÷êè,
ïåðåõîäèì ê ï.12, èíà÷å ê ï. 5.
12. Âû÷èñëÿåì ôóíêöèþ W = ∑t
ms
, ãäå t
ms
= |K
m
K
s
|
2
.
13. Êîíåö.
Îöåíêîé êà÷åñòâà êîäèðîâàíèÿ ïî ðàññìîòðåííîìó àëãîðèòìó ìî-
æåò ñëóæèòü ÷èñëî k = W/p, ãäå p ÷èñëî ïåðåõîäîâ â àâòîìàòå. Î÷å-
âèäíî, ÷òî k ≥ 1, ïðè÷åì ÷åì ìåíüøå çíà÷åíèå k, òåì áëèæå êîäèðîâà-
íèå ê ñîñåäíåìó , ïðè êîòîðîì k = 1.
Áåç ïîäðîáíûõ îáúÿñíåíèé ïðèâåäåì ïðèìåð êîäèðîâàíèÿ ñîñòîÿ-
íèé àâòîìàòà, ãðàô êîòîðîãî èçîáðàæåí íà ðèñ. 10.7.
12
12
24
25
32
000, 001.
43
45
54
51
KK
===
M
a
a
#
a
a
"
a
!
Ðèñ. 10.7
112
Êîäèðîâàíèå áóäåì èëëþñòðèðîâàòü äèàãðàììîé Âåé÷à.
3
3
3
!
{}
44
24
25
24
32
43
4; 2 .
43
45
45
54
54
51
B
′
=γ== =
MM
C
2
1
={101, 011};
D
4
1
=
C
2
1
={101, 011}. W
101
=|101001|
2
=1; W
011
=|011-001|
2
=1.
Âûáèðàåì K
4
=101.
"
3
3
3
!
{}
55
25
32 25
43 45
5; 2, 4,1 .
45 54
54 51
51
B
′
=γ== =
MM
113
C
2
1
={011};
C
4
1
={100, 111};
C
1
1
={100, 010};
D
5
1
=
C
2
1
∪
C
4
1
∪
C
1
1
={011, 100, 111, 010}.
W
011
=|011001|
2
+|011101|
2
+|011101|
2
+|011000|
2
=1+2+2+2=7;
W
100
=|100001|
2
+|100101|
2
+|100101|
2
+|100000|
2
=2+1+1+1=5;
W
111
=|111001|
2
+|111101|
2
+|111101|
2
+|111000|
2
=2+1+1+3=6;
W
010
=|010001|
2
+|010101|
2
+|010101|
2
+|010000|
2
=2+3+3+1=9.
W
100
=min{W
001
, W
100
, W
111
, W
010
}. Ñëåäîâàòåëüíî âûáèðàåì K
5
=100.
#"
3
3
3
!
{}
33
32 32
3; 2, 4 .
43 43
B
′
=γ== =
MM
C
2
1
={011};
C
4
1
={111};
D
3
1
=
C
2
1
È
C
4
1
={011, 111}.
W
011
=|011001|
2
+|011101|
2
=1+2=3;
W
111
=|111001|
2
+|111101|
2
=2+1=3.
W
011
=W
111
. Ñëåäîâàòåëüíî âûáèðàåì K
3
= 011.
!
#"
3
3
3
!
k = W/p = 10:8 = 1,25.