книги из ГПНТБ / Белоглазов, И. Н. Корреляционно-экстремальные системы

заполнение ломаной покрывающей полосы. В участок я/ сначала записываются младшие разряды

=	Х 1г = Х 2,	ЕА/ 2 = = Xk/2’ ^ /2 + 1 = X k/2+l >
71> =	Л'«/2+1	= X n/2 +kj2' \ j 2 + \ == X n/2 +kl2+l

координат главного входа средней линии в рассматри­ ваемый большой квадрат, определяющие положение это-

							п п m
								в
	Длина кратна 2i~8
7Г[=0 0 1 0 0 0 0 1 0 0 1 1					1110			Двоичная
v * „ - *		tj'—г—' '— у—'
5	V ” " 4		Г		у	'	запись номера
V"	1? >?*	>?-■-------					вектора длин
	Хм/---------	'	Двоичная				отрезков		'
			запись Xi
1-я строка		2-я отрока 3-я строка						Ч-я строка	/
Sr?= 'ооооооo'		T ito но		v	'oi 1 0 0 0 0 '			TiotTiojso o
v								^
	Длина 2pS*=2-2-7=28							(,

___________ Длина кратна 2d=8____________

Рис. 7.7.

го входа внутри данного большого квадрата*) (обозначим

этот набор х*М(), а затем номер типа средней линии Яг-

в двоичной		системе.	На это потребуется не более
k + 2 -f- v*i +			s*	Qдвоичных разрядов.
		2 + Ц log Q г*/2 ^
*)	В участок кода л4		надо записывать не k координат главного
входа,	a (k+'2)	координаты, включая		сюда величины lfe/2+1 == jca/2+i

и rjft/2+i = лгп/2+й./2-ы, чтобы охватить тот случай, когда главный вход

расположен на правой или верхней сторонах большого квадрата, Поэтому набор

х ы = (*i- х г- > Xk/2 ’ x kl2 +l ’ Хп/2+1 ■••• • Xnl2 +k/2’ Xn/2+kl2+1)

содержит (k+2) компонент и отличается в этом отношении от вве­ денного ранее [см. (7.19)] обозначения набора младших разрядов, имеющего k составляющих.

220

В дальнейшем, чтобы некоторые вспомогательные опе­ раторы декодирования оказались монотонными, нам пот­

ребуется	длину	измерять	с точностью до 2d, где
й — некоторое положительное			целое число, меньшее k.
При этом,	если	величина k	5*
			v** -f- 4 -f- ] log Q J /2 v. £

окажется не кратной 2d, то последние разряды участка

я* заполняются нулями. Это может привести к удлинению

участка	кода	не более, чем на 2d; с учетом			сделан­
ных замечаний длина			участка я1 не	превышает ве­
личины
^	< k + 2 + v*i + 2 + JlogQS) /2^			С + 2«<
	< k +	v*.+	5 + logQS;%_ >#t +	2d.	(7.30)

Участок кода я^ для большого квадрата, представлен­

ного	на рис.	7.7,а, в	случае, когда d = 3,	показан на
рис.	7.7,6. За	участком	я 1* следует участок	я2*, в кото­

ром записывается информация о заполнении покрываю­ щей ломаной полосы в i-ом большом квадрате. Чтобы

составить участок кода я2», надо предварительно распря­ мить покрывающую ломаную полосу Pi, принадлежащую г-му большому квадрату. Поскольку Рг-сП,-, то достаточ­ но распрямить ломаную полосу Пг-; при этом будет рас­ прямлена и покрывающая ломаная полоса Pi. При рас­ прямлении в некоторой точке а производится отображе­ ние клеток ломаной полосы n i на новую плоскость giOiT}i. Пусть точка излома а ломаной покрывающей по­ лосы Р,- шириной 2р находится на пересечении нижних сторон клеток q-й строки и левых сторон клеток /-го столбца. В точке излома а средняя линия Li делится на

два участка: предыдущий L{ от главного входа средней

линии до точки спрямления а, и последующий L^ — от

точки а до главного выхода.

221

Обозначим через II		множество клеток, принадлежа­
щих /7-окрестности	,	за	исключением клеток
(q + p— 1, у),			(q + p— 1, /+1),
. . (	q + p—1, j + P—1),
(q + p—2, j),		(q + p—2 , j + l ) , . . „
	(q + p—2, i + p— 1),
(7—p,	/),	(q—p> Ж ) , • • •>
	(q—p, j + p— 1),
а через IT обозначим		множество клеток,		принадлежа
щих /7-окрестности	L.t ,	за исключением клеток
( q +p — U j —p),			( q + p —1, j —p+i),...,
.... (q + p— 1, /—I),
(q + p—2, j—p),		(q + p—2, /—/7+1),		...,
..., (7 + P—2, /—1),
(</—p. i—p)>			(q—p, /—p + i ) , ....
	• •	(7—p, /—1) •

Распрямление ломаной полосы ГГ в точке а осуществля­ ется тремя последовательными преобразованиями Т{, Тг Т3.

Преобразованием	Т,	множество	без	искажений
отображается в П'.	на	плоскость	(на рис. 7.8 по­
казано распрямление	покрывающей		ломаной полосы ши­
риной 2/7 = 4). Г2 переводит клетки			внешнего	(по отно­

шению к спрямляемому излому) квадрата +1

(Я— 1, /), (7—1, / И ) ........

• • ( 7	—1, i + p— 1),
(7—2, /),	(7—2, / 41) , ...,

222

Рис. 7.8.

..., (<7—2, j + p— l),

(q—p. /), (q—p, j + i), ....

•••, {q—p, i+P— 1).

вклетки внутреннего квадрата 6д, причем каждая клетка внешнего квадрата Л переходит на место симметричной

относительно точки излома клетки внутреннего квадрата

223

63 (рис. 7.8); при этом n f>— IY(V Преобразование 7\ по­

ворачивает множество клеток IP. вокруг точки излома так, чтобы начало линии Lh стало продолжением конца линии Lt , при этом П'.а—

Преобразования Т и Т2, Т3 спрямляют								ломаную полосу
(и среднюю	линию)		в	точке		излома		а. В	результате
спрямления Пг- — П’ =			П'г1У П” .а, а				средняя		линия Ц
переходит в L l; L', имеет ту же						длину,		что и Ц,		но чис­
ло изломов у	L 1.	на единицу			меньше,			чем у L,-.		Можно
показать, что П*		является /7-окрестностью L \
Все клетки ломаной				покрывающей				полосы Ргоказы­
ваются отображенными				на плоскость			^О,^, в некоторое
множество Р', причем Р ^ с П ’.						Если произвести распрям­
ление последовательно				во всех		точках		аи а2......ука­
занным способом,		то получается два ряда преобразований
Для каждой	пары Р|, IP, К				/ <	v**
			P j c n j .							(7.31)
		v*	< закрашиваются так же, как и их
Клетки множества Р

прообразы из множества Pi. остальные клетки полосы Пг-,

принадлежащие множеству ГТ’< \р ,\ закрашиваются в бе- 1 N t

лый цвет (или заполняются нулями). На рис. 7.9 пока­ зано, как осуществляется распрямление ломаной полосы в случае трех изломов. Клетки исходной полосы прону­ мерованы, и по рис. 7.9,а можно проследить, как пере­ мещаются клетки при каждом из преобразований.

Преобразования 7\, Т2, Т3 осуществляют распрямле­

ние в точке а,у, при этом происходит отображение
П Т'ГгТз_^П1; преобразования Т \ ,		Т \	, Т \	производят			рас-
					у!	у»1
прямление в точке а2 и	отображение			П1	1 2	3, ГР,	и,
наконец, преобразования Т \ , Т \ ,		Г2	осуществляют				рас-
прямление в точке ”а„	переводя	IP	•р2 *р2 *р2
			1 2		3, ГР.

224

На рис. 7.9,6 показано, как распрямляется ломаная покрывающая полоса некоторого большого квадрата, которой соответствует та же ломаная полоса, что и по­ лоса, преобразуемая на рис. 7.9,а. После распрямления ломаной покрывающей полосы рассматриваемого г'-го

большого квадрата в участок кода яД заносится инфор­ мация о заполнении распрямленной ломаной полосы.

Сначала в я,2 записывается (по направлению средней линии) нижняя строка, причем черным клеткам в коде соответствуют единицы, а белым клеткам — нули; затем записывается вторая снизу строка и т. д. вплоть до по­ следней 2/7-й строки. Тем самым образуется последова­ тельность из нулей и единиц длиной 2pS*i.

Длина hi2 участка яД так же как и длина /г,1 участ­

ка я,1, должна быть кратной 2d. Если 2pS*i не кратно 2d, то длина этого участка кода искусственно увеличивается до наименьшего числа, кратного 2d и большего 2p S *it поэтому

ki2^2 p S * i + 2d.

(7.32)

Длина полного участка кода, соответствующего /-му большому квадрату hi = hil + hi2, определяется неравен­ ством

	hi < k -f-	+ logQ 2l/2 ^ -f- 2pS*i -{- 2 • 2d. (7.33)
В	рассмотренном	ранее	примере,	приведенном	на
рис.	7.7,а, распрямленная		ломаная	полоса имеет	вид,

показанный на рис. 7.7,б; участок кода я,2 для 2й= 8 изображен на рис. 7.7,г. Полный участок кода, соответ­ ствующий большому квадрату, представленному на рис. 7.7,а, такой:

^ • = 001000010011 1110

00000001010110011000010001000000

15— 527

225

■71	ч?\ п W\39\0O	л
р	Of02\03100
\	г jb Is.
в\?\8)9 Ь\ Щ/20

io\i5\i6\i7,ic mzt-rT 22\23\20!#|a> WUffi

щз1\зг$з$о shbV-f]

О

к!"

h

n't

Tf б 7 8 9 10 1015161718

гг23го25гй so3i;зг3330

Of

ft

//’	«г	т;	a?							Ы383900
f 7
	е 9\Ш Ж.ч		\6ТГ\8 9 \10\28\	n’	Г/		n’z		»Г 01020300
Ю15	1C17\18 27352' 0137	L1
26\2320\25\26 19WУ 0238			‘10\15\l6 1718 27}	ft ■35\2 0137	аг			0137*.			3 0 5
ЗО\ЗГ\32\33\30\2:Ш4 4559			?г\гз\2о 26III	1f * 0238	2 35113 02м						111213
/			30\31\32	120 0339	1 36		0		т,	^ 353621
	\29\21\135 0000		ЗЗ'ЗО 20\			12		03391J
п1				\29\21135 00оо\					7j ^	ог	2 1 29
					29\21135 9400}

h

L-f

2	37383900
	01020300		212901‘37
	29 1 0 5
	21361213		561 ог'зз
	«3	>4'	12\0 03\39
			из\13\5Woo'

		I
		l
		„ большой“
5	7 8 9 10283 21290137	квадрат
		L3
1015161718271136 1 0238		1-
гг2320252в1935120 0339
3031323330202 135 0000		Главный.
	&1 0-2 &3	вход

Рис. 7.9.

Из изложенного выше				следует, что	длина		всего	кода
	2	n-h	1		n-fc	,
		— 1			2	— 1
Л =		Ц /гг- < ( 6 + 5 ) 2 « - й +			s	v * i +
		i=0			i= 0
	__j		2П ~ ^ __1
+ 2/^	S	S V f		£ logQSJ /2>V. +2.2«'.2»-*.(7.34)
	i=0			i=o	‘
Требует	специальногопояснения				вариант,		когда	для
рассматриваемого			большогоквадрата		5 д = 0 (т. е. дан­

ный большой квадрат не содержит граничных клеток).

В этом случае участок иД отсутствует, а участок Я г 2 со- "* стоит сплошь из 2d нулей или единиц в зависимости от того, заполнен ли данный большой квадрат только бе­ лыми или только черными клетками. Неравенство (7.34)

и в этом случае остается справедливым. Рассмотрим подробнее сумму

n - h	,	rt - ft. .
2	— 1	2	— 1

2	l° s Q % v* = b g		П	•
;=o	-	1	i= o	1

Если положить		с =	2k/2 ,		b =	2n/2,
n -h		,		2	П- ft,	t
2	—l				—1
£		5*j =	S*,		2	v*i = v*,
i= 0					/=0

то на основе свойства 1 (см. приложение 1) можно полу­ чить следующее неравенство:

п	Q S*i		<	0 s *
	^	2*/2, v* г		^ 2 " / 2 ',	v* + 2 " - 1 1 — 1
Из (7.23) — (7.26)		вытекает, что
5 * < S -f-6 -^ - +	2		2п~к12-j- 18-2”~*/2 + 10-2п_й,
v < v * < v + 8 ™			+	3 ^	2"“й -|- 32-2К~к.

Далее параметры к, г, d в зависимости от п будут выби­ раться так, что

2*/2 2*

k —>oo, г —►оо, й —*о о , ------- >-оо, "27 ~ "00 ПРИ

(7.35)

228

В этом случае
			S*<S = a2”,			v*'v,v =			p2w.	(7.36)
Поскольку,		кроме		того, всегда S*>v*, то по отношению
к Q2"/2, v . +	2"	- * _ i	справедлива			оценка			(34)
S*				, 2«/2-1				2it (v* +		2" ft)X
Q 2л /2	v* + 2				v«+2n_h—1+2«/2/
X ехр{-й12 (v* +							S*			v * + 2 "
				2n ~ h) ■ } ( s V * +
							2 n ~ h —		1	2" -k) }x
v*+2		-1	r	4	1	'	F	[ J 2 (v* +
:C 2		«-и	, ]/2 n (v * -j- 2"~ft) exp 1						,
		X 2 v* + 2n-*— 1 - 1						v * + 2 "
И					s
s*							~ p -2 rtlog(2Z - 1). (7.37)
logQ 2"/2, v*+2«-h_i ^					log Q2«/2,

Совместное рассмотрение (7.341, (7.36) и (7.37) показы­ вает, что при выполнении условий (7.35)

		h<2ap	1 Ч— 2^7“ log2 (2/ — 1)			(7.38)
При избранном способе				кодирования бинарных карт
длина	кода	h асимптотически не			иревосходит	верхней
оценки	Н энтропии		Н (Fn) класса		бинарных	карт [ср.
(7.15)	и (7.38)].
Не снижая общности рассуждений, можно полагать,
что длина		средней	линии	нового	покрытия	в любом
большом квадрате			S * i< 2 \			(7.30)

так как в противном случае (при S*,->2h) всегда можно, не увеличивая длины кода, перейти к улучшенному но­ вому покрытию с длиной средней линии S * * j< 2h.

7.3. Оценка сложности схем из функциональных элементов, реализующих бинарные карты

О. Б. Лупанов сформулировал принцип локального кодирования, который можно с успехом использовать для синтеза управляющих систем, и рассмотрел несколь­ ко разновидностей этого принципа: варианты равномер­ ного и неравномерного кодирования и случай парамет­ ризации [85].

229

В настоящем параграфе пас будет интересовать лишь вариант неравномерного кодирования. Суть принципа локального кодирования применительно к этому вари­ анту сводится к следующему.

Пусть F есть {п, т) -оператор, и пусть ему можно поставить в соответствие:

1) последовательность я=(ло, ял,. . . , ял- i) из нулей и единиц длины, скажем, h — код оператора F — разби­

тую на куски (куски			могут пересекаться;	пусть	макси­
мальная длина куска равна Q);
	2)	вспомогательные операторы:
и	— операторы выбора куска кода A i и А% (это п, р)-
	(п,	q) -операторы	соответственно; здесь p=]\ogh[,
<7=] log QL
	— оператор декодирования Аз,				А з , ,
	— быть может еще некоторые операторы Аь
..	,А^	такие, что
		F (х) = А3 (х,	Bh- ч(я, Л, (х), Л2 (Зс)),	Л, (х),
		А2({х), Л4 (л ),. ., Л, (■*)),			(7.40)

где Bh,q— оператор выделения части набора (см. [85]); тогда говорят, что оператор F допускает неравномерное кодирование.

Пусть F = {F1, F2, . . . , Fn, ...} — последовательность классов операторов, причем Fn состоит из (п, тп) -опе­ раторов (не обязательно всех). Введем обозначение: H(Fn) — двоичный логарифм числа операторов из Fn (энтропия класса операторов Fn)\

7 (Fn) = Н (Fn)/\ogH(Fn).

Теорема *). Пусть

(n + m)II(Fn)— Ю

(7.41)

и операторы из Fn допускают неравномерное кодирова­ ние с соблюдением условий

h ~ H ( F n),		(7.42)
Q log2 h jh — v0,		(7.43)
2(Л,-) =	0 ( I ( F n)),	(7.44)
i — 1,	2 ,..., v,
*> Эта теорема доказана О.	Б. Лупановым	в [85].

230