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

и мощность класса бинарных карт N(Fn) не превосхо­ дит величины

	X
Х(2?)2п>2 _2^'112.22ар^ •2£2"	Э271 (7.11)

Если теперь перейти к энтропии класса бинарных карт

Н {Fn) = logN(Fn)*\ то

	Я (Fn) < log 18 (2 j - - 1				у	ip24"’ }+ -§-/* +
+	2"/2 log 2? +		«2,i/2 +	[2ap +	p +	plog ( 2	-j- — 1 2пЪ
^	2aP [ 1 + 2		( a / P ) p +	2 ( a / ? ) p	l 0 §	( 2 1	(7.12)
							1
Ранее через		/	обозначалось		отношение		/ = S /(v + l) =
— а/(^ + 2~п),		предел которого			равен a/Р;		чтобы не вво­

дить новых обозначений, будем этот предел обозначать прежней буквой 1 = a/Р; по смыслу I равно средней длине постоянства средней линии.

С учетом сказанного **)
Я (Fn) < 2ар [1 +	+ - щ - log (21 — 1)] 2п. (7.13)

Определим нижнюю границу для мощности и энтропии класса бинарных карт.

Лемма 7.2. Существует п0 такое, что для любого п>п0 внутри квадрата размером 2п^ х 2 п>г можно прове­ сти ломаную полосу с длиной средней линии S = a-2п и

шириной		2р,	содержащую не меньше 2pS клеток.
*>	З десь	и в	дальнейш ем		п од lo g с поним ается		логариф м .числа
с по основанию			2.
**)	З десь и		в дальнейш ем		использую тся	следую щ и е расп р остр а ­
ненные	обозначения:			сим вол ап ~ Ь п означает, что Н т ( а ( п )/Д (/г )]= 1 ;
	ап ^ Ь п, —					«->00
сим вол				что Н т [ а ( п ) /6 ( п ) ] ^ 1 ;		сим вол	ап ^ Ь п, — что
				«->00

lim [а(п) /Ь( п)]^ 1.

П-*00

210

Д о к а з а т е л ь с т в о . Выберем nQ— ]] 2 log^ ^ — £ *>

(напомним, что 2а/?<М, см. (7.3)) и зафиксируем не­ которое п ^ > п 0. Разобьем квадрат 2"/2Х 2 ,!/2 снизу вверх

и слева направо на полосы и столбцы шириной 2р, кото­ рые разделят квадрат 2"/2х 2 п/2 на меньшие квадраты размером 2рХ2р, причем верхняя полоса и крайний пра­ вый столбец могут иметь ширину меньше 2р.

Число полных полос и столбцов равно ] 2"/2/2/? [— 1.

Проведем некоторую вспомогательную ломаную линию, начинающуюся в средней точке А нижней грани ниж-

Рис. 7.2.

него левого квадрата 2рх2р. Она пройдет снизу вверх по всем полным квадратам первого столбца, затем пе­ рейдет во второй столбец и спустится по нему вниз, да­ лее перейдет в третий столбец и поднимется вверх и т. д. (рис. 7.2). Длина этой вспомогательной ломаной линии при условии, что она пройдет все целые квадраты

*) ]а[ означает наименьшее целое число, не меньшее а.

14

211

2рХ2р, будет не меньше, чем

+ 2 p ( ^ Z - 2 )	+ 2p.
а поскольку M>]21og(4p/l—2ар)[,	эта длина превосхо­
дит величину 5 = ia2n.

Требуемую ломаную полосу можно построить сле­ дующим образом: в качестве ее средней линии взять

участок	вспомогательной ломаной	линии длины S =
= « 2 П,	начиная от точки А . (на рис.	7.2 средняя линия

кончается в точке В), и выделить р-окрестность этого участка; в результате получится ломаная полоса шири­ ной 2р с длиной средней линии S = a2n. Так как постро­ енная указанным способом ломаная полоса не имеет точек самопересечения, то она содержит не менее 2pS точек. Лемма 7.2 доказана.

Если внутри квадрата размером 2п/2х 2 п/2 выделена ломаная полоса шириной 2р с длиной средней линии S = =ia2n, содержащая не менее 2pS точек, то каждому но­ вому заполнению этой ломаной полосы нулями и едини­ цами (или черными и белыми клетками) соответствует

новая булева функция F(xu х2, ..., хп)	(новая бинар­
ная карта рассматриваемого типа) *\
Поскольку число различных возможных заполнений
этой ломаной полосы, очевидно, не менее	22pS= 2 2ap2 , то

и число различных бинарных карт рассматриваемого типа

N(Fn) ^ 22ap2".

На основании всего вышеизложенного в этом параграфе доказана следующая теорема.

Теорема 7.1. Энтропия H(Fn) класса бинарных карт Fn заключена в следующих границах:

2ар2п < Н (Fn) « 2ар [ 1 +

log (21- 1)] 2* (7.14)

*> При этом клетки, не попавшие в ломаную полосу, можно условиться, для определенности, заполнять нулями.

212

Насколько точными являются полученные границы? От­ ношение верхней границы

M(F„) = 2 a p [l + -2 ^ - + -2 ^ - lo g (2 /~ 1)] 2ft (7.15)

к нижней

H(Fn)= 2aP2n

(7.16)

равно

E ( F n)lH(Fn) = 1 + (1/2р/) + (1/2/7/)logС2/ — 1). (7.17)

Это отношение принимает наибольшее значение, равное

1,67, при р = 1 и /=1,57; если же / ^ 2,5 и р ^ З , то это отношение меньше 1,2. Таким образом, найденные гра­ ницы являются достаточно точными.

7.2.Локальное кодирование бинарных карт

Зафиксируем некоторое четное число п > 2 и рас­ смотрим класс бинарных карт Fn, соответствующий это­

му числу. Выберем другое четное число k<n и разобьем поле бинарных карт на «большие» квадраты размером 2Щх2к!2 так, как показано на рис. 7.3 (для п = 8, &=4). Всего получится 2n~h больших квадратов. Положение

213

больших квадратов определяется исключительно стар­ шими разрядами

^ л / 2 ' ^ л / 2 - 1 >

^ / 2 + 1 ' ^п/2’ \ l 2 - - l ’ " • ’ \ / 2 + 1

чисел £ и т), т. е. величинами

X k /2+l ’ X kl2 + 2 > •••> Х	п/2 - 1 ’ X n l 2'
X nl2 +k/2 + l’ X nl2 +kl2 + 2	> •••> Х п - и х п*'-

Большие квадраты можно перенумеровать, если считать номером число

1 — Хк!2+\ -20 + ^*/2+2 ’2*+ ••• + Хп/2'2"12 к‘2 ' +

I у	пЛ/2—*/2 |		о«/2—ft/2+ I |
"Г л'п/2 +*/2+1	' z	" Г Ал/2 + */2 + 2	“Г
	+	. .. + х п.2'!“*-'.	(7.20(

В предлагаемом методе кодирования бинарных карг код оператора содержит информацию о прохождении средней линии и заполнении покрывающей ломаной полосы последовательно в нулевом, первом, втором и т. д. больших квадратах. Стороны больших квадратов «разрезают» единую среднюю линию на множество от­ резков. В процессе кодирования потребуется установить однозначное распределение отрезков и изломов средней линии по большим квадратам. На поле бинарной карты будем рассматривать различные квадраты (в том числе и большие квадраты), состоящие из клеток бинарной карты.

Условимся к данному квадрату Q относить те точки плоскости бинарной карты, которые лежат внутри этого квадрата, а также два интервала, образованных левой и нижней сторонами, и нижнюю левую вершину. Усло­ вимся дополнительно к квадратам, верхняя сторона ко­

торых совпадает	с верхним		краем	карты, относить ин-
*> Для сокращения записи набор старших разрядов будем обо­
значать хс:
Х с = Х / г / 2 + l ,	x k/2 + 2 ............. х п.‘2 ’ х л / 2			+	й / 2	+ 1 ............... х п ) . ( 7 - ' 8 )
а набор младших разрядов		— хм:
Х м ~ ( * 1 , * 2 .........	х л/2	; х п/2 + 1’	ХП12 + 2'	'	• ’	x ;i/2 + fc/2)-

214

тервал,

образованный

верхней '

^

шину. Договоримся также кквад-

-

г,

у

у ‘7\~

ратам,

правая

сторона

которых

совпадает с правым краем кар-

^

2 /

а7

'Л/Ъ

у г

/

2 2

/

/у

б

ты

относить

интервал

обрати-

УГ,

7

УГ

ванный правой гранью, и пра-

2 2 /

Г,/Х ■*, 7Г

Z

z

2 'лг,,

2Г

вую

нижнюю

вершину.

Кроме

а

а,

2

того, к

правому верхнему

квад-

У

{ ,2 V

it

Гп

рату

будем

относить

верхнюю

г

правую вершину.

i

г,

гН

При принятых условиях каж­

дая

точка плоскости

бипарной

карты

будет

входить в

какой-то

квадрате

□

один квадрат

(рис. 7.3). Будем в некотором

учитывать длину только тех участков

средней линии,

ко­

торые принадлежат этому квадрату.

Изломы

средней ли­

нии распределим по квадратам следующим образом. Точ­ ку излома средней линии а отнесем к квадрату □, если существует участок средней линии, начинающийся в точ­ ке а, который принадлежит □ . Распределение точек излома по квадратам поясняется на рис. 7.4, где изоб­ ражен внутренний квадрат □ ; этому квадрату прина­ длежат все внутренние точки излома: аь щ, аь, Яб, й|з, а также точки аз, аи, пщ, лежащие на сторонах квадрата. Из введенных определений вытекает следую­ щее свойство.

Свойство 7.1. Для любого отрезка средней линии, принадлежащего некоторому квадрату, число точек из­ лома этого отрезка, принадлежащих данному квадрату, меньше длины отрезка.

Действительно, каждой точке этого отрезка, принад­ лежащей к рассматриваемому квадрату, соответствует по определению некоторый участок средней линии дли­ ной не менее 1, принадлежащий этому же квадрату.

Точку средней линии а назовем входом в квадрат □, если существуют два участка средней линии, один из

которых	(предшествующий) заканчивается в	точке а,
а другой	(последующий) начинается в точке	а, таких,

что предшествующий участок не принадлежит квадрату □ , а последующий — принадлежит этому квадрату. Если же предшествующий участок принадлежит квадра­ ту, а последующий — не принадлежит, то точка а назы­ вается выходом из квадрата □ . Дополнительно усло­

215

вимся входом в данный квадрат считать начало средней

линии в том случае, когда оно е П , и выходом	из дан­
ного квадрата считать конец средней линии,	если он

£=□.

Рис. 7.5 поясняет понятие входа и выхода для вну­

треннего		квадрата			бинарной		карты.		В	соответствии
с	принятым		определением			точки аь		аз,		яю являются
										-
								с	777777Г
								7Г		А
							-	А		АГ
										/Р
										УГ
								а	27*?7 7V- -
										2л
	Рис. 7.5.									Рис. 7.6.
входами,		точки		а%	ав, Яи	являются		выходами, точки
я4,	аь,	аз,	ад,	хотя и лежат			на сторонах квадрата, не

являются ни входами, ни выходами. Из определения входа вытекает следующее свойство.

Свойство 7.2. Суммарная длина всех отрезков сред­ ней линии, расположенных в граничном кольце шириной

1 некоторого квадрата, не	меньше,	чем	число входов
в этот квадрат.			квадрата □
Под граничным кольцом шириной 1
в свойстве 7.2 понимается	множество	точек,

. 0 = П ?\

где EHi — множество точек, принадлежащих исходному квадрату; — множество точек, принадлежащих ква­ драту, сторона которого на две единицы меньше стороны исходного квадрата (рис. 7.6).

Свойство 7.2 является очевидным, так как по опреде­ лению каждому входу в квадрат Di соответствует неко­ торый участок средней линии, принадлежащий этому квадрату. Следовательно, каждому входу в квадрат Di соответствует некоторый участок средней линии, при-

216

надлежащий граничному кольцу, и дли'на этого участка не меньше 1.

Средняя линия может иметь несколько входов и вы­ ходов в некотором квадрате □ . Среди них всегда можно выделить главный вход и главный выход. Для этого на­ до, передвигаясь вдоль средней линии от ее начала, от­ метить первое вхождение средней линии в рассматри­ ваемый квадрат — это будет главный вход; продолжая передвигаться вдоль средней линии, отметим последний выход средней линии из квадрата — таким образом опре­ деляется главный выход. Остальные входы и выходы (будем называть их дополнительными) возникают вслед­ ствие сечения средней линии сторонами квадрата. Если средняя линия начинается или кончается в данном квад­ рате, то эти точки также будем считать соответственно главным входом или главным выходом.

Рассмотрим некоторый t-й большой квадрат. Пусть средняя линия имеет т г- входов в этом квадрате с дли­

ной отрезков S*, S ^ ,.... St ‘ и числом точек излома у каждого отрезка, принадлежащих рассматриваемому большому квадрату, v', .... vt*.

Обозначим суммарную длину отрезков средней линии, принадлежащих t-му большому квадрату, через Su а суммарное число точек излома средней линии, прина­ длежащих t-му большому квадрату, — через \\:

(7.21)

(7.22)

/=1

При введенном нами распределении отрезков и точек излома средней линии по квадратам полная длина S средней линии покрывающей ломаной полосы и число точек излома v этой средней линии равны соответственно

s =	2	sit	(7.23)
	i- О
V =	£	Vi,	(7.24)

217

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

Новое покрытие должно обладать следующими свой­ ствами: каждая граничная точка бинарной карты, рас­ положенная внутри большого квадрата, должна быть вновь покрыта таким участком ломаной полосы, что

средняя линия этого участка принадлежит данному боль­
шому квадрату; новое покрытие внутри «большого» ква­
драта должно содержать одну ломаную покрывающую
полосу и одну среднюю линию; увеличение суммарной
длины Si	и числа изломов v,- средней линии при переходе
к новому	покрытию должно быть несущественным.

Метод перехода к новому покрытию будет	изложен
в приложении 2, где будет также показано [см.	формулы

(44), (45)], что длина S*,- п число изломов средней ли­ нии v*j нового покрытия отличаются от S; и v; на при­

ращения A Si= S*i—Si,		Avi = v*j—v;,	не	превосходящие
величин
Д S i < 6	+ 2	2 k/2 - f 18 •2 т +		10,	(7 .2 5 )
0 < ДV i< 8S i ! г + 3 (г— 1) i p			-Ь 32,		(7.26)
где г — некоторое число, заключенное в пределах
	1 < ^ < 4 ~ -2*/2-				(7.27)

Перейдем к кодированию бинарных карт. В коде опе­ ратора F записывается информация о типе средней ли­ нии и о заполнении ломаной покрывающей полосы по­ следовательно в нулевом, первом, втором и т. д. больших квадратах.

Понятие покрывающей ломаной полосы Р, по отно­ шению к некоторому г-му большому квадрату вводится так же, как в § 7.1 было введено понятие покрывающей ломаной полосы Р всей бинарной карты. Если Кг — мно­ жество клеток г'-го большого квадрата, а Пг-—p-окрест­ ность средней линии нового покрытия этого большого

218

квадрата (с параметрами К*,-, v:\ ) , то ломаной покры­ вающей полосой г-го большого квадрата называется мно­ жество клеток

Рг = Кг П Г1г-.

(7.28)

Поясним подробно, как составляется участок кода для некоторого г-го большого квадрата. Пусть новое покрытие этого большого квадрата одной ломаной по­ крывающей полосой имеет длину средней линии S*i и

число изломов средней линии v*,. s*.

Число N 2*1-2, v*t всех возможных типов различных

средних линий с параметрами S*1 , v*,-, исходящих из одной точки, равно согласно (7.7)

,. + 2

(7.29)

5*

где, в соответствии с приложением 1, Q ‘2 v. — коэф-

фициент при степени г6 * в разложении

?(2) = (г + 22 + . . . + ^ /2) ^ +1 .

Для фиксированных 5*г-, v*z- производится нумерация этих типов. С этой целью произвольным способом нуме­

руются все возможные векторы длин отрезков * (для

S*

чего требуются ]log Q t [ двоичных разрядов), а дво­

ичная запись номера типа средней линии получается как последовательная запись вектора формы средней линии

sи двоичной записи] номера вектора длин отрезков.

Вкачестве примера рассмотрим большой квадрат, показанный на рис. 7.7,а, со стороной 2к12= 8 и параме­

трами S*i = 7, v*i =				2. Для этих S*i и v*i				возможны 15
различных векторов длин отрезков.							11.	* =	(3,2,2),
1.	* =		(1,1,5),	6.	* =	(2,1,4),
2.	*	=	(1,2,4),	7. * =		(2,2,3),	12.	г =	(3,3,1),
3.	*	=	(1,3,3),	8.		* = (2,3,2),13.		* =	(4, 1,2),
4.	* =		(1,4,2),	9.	* =	(2,4, 1),	14.	5 =	(4,2, 1),
5.	*	=	(1,5, 1),	10.	* =	(3, 1,3),	15.	* =	(5, 1, 1).

Кусок кода 7ц оператора F, содержащий информацию о

г'-ом большом квадрате, состоит из двух участков и' и

it2 ; первый характеризует тип средней линии, а второй—

219