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

тогда			S’ (Fn) ~ pi (Fn),	(7.45)
где	p — наименьший из приведенных			весов всех элемен
тов,	входящих	в	схему*); <2(А),	££ {Fn) — сложность
реализации операторов A , Fn-
Рассматриваемая нами ситуация отличается от по­
становки задачи		О.	Б. Лупанова. Эти отличия сводятся

кследующему:

1.Исходный оператор F(x) связан с операторами ко­ дирования Л, декодирования и другими вспомогатель­ ными операторами А зависимостью, отличающейся от

(7.40).

2.В процессе декодирования нам понадобится выде­

лить не один, а два куска кода яА и я,2.

3. Нам неизвестно точное значение энтропии класса бинарных карт H(Fn), а известны лишь нижняя Н и

верхняя Н оценки энтропии.

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

более простым.	(рис. 7.10), что оператор F (х)
Ниже будет показано
можно представить в виде
F (х) =Aw(Ag(x, A (A (A i(# ), А (Ли(*))),
Л4(Л2(х))), Ат(х),	Л8(х)), А6(А3(Ац{х),
Л(Л12(х))), Л2(*)))•		(7.46)

Здесь Л — оператор кодирования; Л1— оператор, опре­

деляющий координаты начала куска кода Я{; Л2 — опе­ ратор, определяющий длину первого участка я ,1 куска

кода я^; Л3, Л4, Л5, Л6— некоторые вспомогательные опе­

раторы, выделяющие куски кода я ,1	и я,2; Л7, Л8, Л9,
Лю — операторы декодирования. Запись	(7.46) является

одной из разновидностей неравномерного кодирования и отличается от (7.40). Согласно (7.46) схема для реали­

зации F(x) имеет вид, показанный на рис. 7.10.

'■‘••"в.**»

*) Далее всюду будет полагаться р=1.

231

h разрядов

rf-p разрядов

J f(Z)

Рис. 7.10,

Операторы А\, А2, Аъ А8 зависят только от старших разрядов координат | и т|, определяющих положение большого квадрата, соответствующего входному набору

х ~	Х2,	, хп), т. е.
	^*/2+1	X k/2+V	\j2-V2	X k/2+2’ • • ’ Ki/2 ~ Х п12 >
		%/2+\ —	X nj2+ kl2+ \ ’ •" > \ / 2 = = Х П’

т

По определению величии v*, и 5*, и в соответствий с не­ равенством (7.39)

v * i < S * i ^ 2 k .

(7.47)

Найдем теперь верхние границы для длин hi1, ht2 участ­

ков кода	Л12:
	/г, =	шах /г1^	тах	+	2 + v*z- -j- 2 -(-
		г 1	i
		+ ]lo g < 3 ^ ,.			[+ 2 -}.	(7.48)
			’	г
Определим		максимально		возмолшое значение		числа

S* .

Q2k;2 t при ограничении (7.39). Если перенумеровать все

стороны клеток, образующие среднюю линию, номерами от 1 до 5*i, то каждой конкретной средней линии длины

S*i с числом изломов v*j можно поставить в соответст­ вие v*i чисел—номеров тех сторон, в конце которых

S*	* Раз'
средняя линия терпит излом. Поэтому число Q

личных векторов длин отрезков не превосходит величины

V*	которая	(при	фиксированном			S*j)	достигает ма-
C<J ,
^ i			Is*.
ксимума при v*i = ]				т,	е.
			[ ,
			s*.		] S * J 2 [
			®2к12, »*	< С S*			(7.49)
r ) S\/2 [ — возрастающая функция S*u						поэтому
			qs*‘	<	. 2*—1
			^ 2fe/2' v.t ^		2*
		(2 2	- 1) ... (2 2		+ 2)(2 J		+ 1)
			1- 2 . . .		0fc-l		<
					2 2
<	22* (22h -	1)... (22h_1 +		2)(22* " +		1) < (2 2* )2* " =
			o2ft.—1		02h
			= 2		< 22
							(7-50'

233

Подставляя (7.50) в (7.48)		и учитывая		(7.47),	приходим
к неравенству
/г, = шах /г' < 22ft+\					(7.51)
Из (7.32) можно получить
h2= шах		(2/7 + 1) 2ft.			(7.52)
i
Максимально возможная	длина Q куска			кода	[не прево­
сходит суммы /г,-(-/г2, поэтому
Q < (2 /? -f 4)22fe.					(7.53)
Введем обозначения:	пусть а =		(з0, ... ,aft_,) — набор из
нулей и единиц длиной	k.	Через	| з | обозначим число
k—\

XI 31'2г. Это число, двоичной записью которого является i=0

набор о, только здесь старшие разряды пишутся справа, а младшие — слева.

Пусть 0^<7<2й; через o(k, q) будем обозначать на­

бор о= (сто, <7i,. . . , Oh-1), такой что |сг|=<7. Рассмотрим некоторые вспомогательные операторы, которые потре­ буются для реализации операторов A i,i —1 ,..., 10.

1.Оператор Кп («дешифратор»). Это (п, 2П)-опера

тор.	Этот	оператор	преобразует			набор	a=(cto, a i,. . . ,
. . . .	a„-i)	в набор р= (ро, Рь . . . ,				Р2»_,);	такой,	что
		р__ f 1,		если	i =	| a |,
			[ 0,	если	i ф | а |.
Известно		(см. [85]),	что
где	Ск — константа.		££(Кп) < С к2",						(7.54)
								систему
Для реализации Кп необходимо реализовать
всех	конъюнкций		а”0 & а"1&...			,	так как		р,-=
= «?&«?& -				f =	0,	1.........	2rt — 1,		где

з — ■( з 0, з , , . . . , з „ _ ,) ■ = з (/£, i) .

234

2.Оператор выделения разряда Вн. Это'(к -}-] log/гf ,

1)—оператор. Он по набору ж длиной h и набору (3 дли­

ной] log h [выдает разряд набора ж с номером |р|:

о>	®i) • •• I	_ к	Ро, P i’ •” Р|	log ft Г— l) = = а	'
■	._________ _		-_________ i	в 1 -	I ВI

			“			li
Из определения				оператора		Bh следует,		что его можно
задать		так:
			B h К	, •••	, ® f t _ i ,	Ро> ••• » Р ]	l o g ft i - i )	—
				ft-i		I l o g ft [ - 1 a ~
				=v	£
						P'1 l o g ft [ - I	| „ |
				I О1=0
где	o =	(a0.......a,
Известно (см. [85]), что									(7.55)
					££(Bh) = CBh,
где Св — константа.
3.	Оператор Dk. Это (h, /г)-оператор.							Он	по набору
			i
a —(0,			0 ,..., 0, 1,		0...... 0) (единица стоит на				г-м месте)
вычисляет			набор р = (1 , 1...... 1, 0, 0,... ,0)(единица стоит

на 0-м, 1-м,..., i-м местах); на других наборах а опера­ тор Dh определен произвольно. Схема для реализации оператора Dh показана па рис. 7.11. Его сложность удо­ влетворяет неравенству:

£ ( D h)<h.

(7.56)

Рис. 7.11.

235

4. Оператор поразрядного логического умножения Mh.

Это (h + h, h) -оператор. По наборам			< x = ( c t o , аь-1) и
Р = !(Ро, •••, P/i-i) он	выдает набор		y==(Yo. Yi........\ h - i )
такой, что Yi=«j&p,,	t = 0 ,l,. .. ,	h—1;
	2 ( M h) =	h.	(7.57)

5. Оператор сдвига Sd’1. Это (Л-f-l, /г)-оператор.

Предполагается, что 2i+d<=h — 1. Оператор Sd' ‘ по на­

бору а = ( а 0, а1г..., ah_1) и по значению переменной у,

вычисляет на выходе набор {3=ф„, Рп-.-.Рл-О такой, что

Ро = а0, Рх== ®1»• • • >рл- 1~		-1	при уj — О,
Ро — a2j+d> Pi =	a2i+ d + ] ’	*Pft-2j+ d-l = afl- 1*
=	=	П Р И	У > = 1 -

Схема для реализации оператора сдвига Sil1 показана на рис. 7.12, из рассмотрения которого вытекает, что

££{SdhJ )<3h.		(7.58)
Опишем операторы А, Аи i= 1, ... ,		10.
Оператор А\. Рассмотрим целочисленную функцию
g(x) такую, что
0	при	Xi = 0,
1	при Яг- > 0 ,
1=0

где Xi — номер большого квадрата, соответствующего набору х, определяемый равенством (7.20); g ( x ) — це­ лое число, так как все hi имеют длину, кратную 2d.

Смысл g(x) таков: если набору х соответствует i-й большой квадрат, то §(х) равно числу отрезков длины

2d, содержащихся в куске кода я, предшествующем уча­

стку я,-.

236

Обозначим

t =	]log I	2	hil2d \ \= \\o g	S hi\—d=\lo%h\—d.
	V	»=o	У	i=0
				(7.59)
Л1— это		(n—подоператор, который по старшим разря­
дам	набора х		(набору х с) выдает набор у=(уо, Уи ■• ■

..., yt-i), являющийся /-разрядной двоичной записью числа g(x). А 1— монотонный оператор. Оценим его

сложность. В (85] доказана теорема: если	— монотон­
ный (п, п) -оператор, то
<£{Шп) ^ 2 «+1/п.	(7.60)

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

Лемма 7.3. Если W — монотонный (п, т) -оператор, то

££(W)<2a+1/a, \

(7.61)

а= max (п, т). /

До к а з а т е л ь с т в о . Рассмотрим два случая:

1.n<gtn.

Любому монотонному оператору W, перерабатываю­

щему	входной набор а=(ао, сц,. . . , ctn-i)	в выходной
набор	р = ( р 0, . . . , pTO-i), можно поставить	в соответст-

237

вие оператор $8?, перерабатывающий входной набор

	е	а
7	(ео> •••> em - n - и	®о» ••• >a n - i ) == ( е > а )

в выходной набор р и обладающий следующими свойст­ вами:- - переменные е0> е ,,..., em_n_, являются фиктив­

ными для оператора ЗУ?; на любом наборе у — (s, а)

3»(7);= ^(«).

(7.62)

Определенный таким образом оператор является моно­ тонным и в соответствии с (7.60) существует схема 2gj|

со сложностью

^ ( 2 ал) < 2 - +1/т,	(7.63)
реализующая оператор 5R.	соединить
Если первые т — п + 1 входов схемы 2 ^

между собой и подать на них переменную а0 (рис. 7.13,а), то согласно (7.62) получится схема, реализующая опера­

тор W. Значит,	существует	схема	2^, со	сложностью
i£ (2ll7)< 2 m+1//n,	реализующая	оператор W.		Отсюда вы­
текает неравенство				(7.64)
	St(W)<2m+1lm.
2. п>т.

Исходному монотонному (п, т) -оператору W поста­ вим в соответствие (п, п) -оператор 3R, перерабатыва­

ющий входной набор а =			(ао, сн........	ctn-i)	в выходной
набор
®	(Ро» " . f	Pm- 1 *	®о» ... » ® n - m - i ) — ’ (р»		®)
по такому правилу:		для любого набора		a
			п— т
	Р =	Н7 (a), 7 = (0, 0 ,..., 0).			(7.65)
Оператор	является монотонным и согласно (7.60)
		£ б ( Щ ъ 2 п+11п.			(7.66)

238

		7
		п<т
< 1	<| <	<
т-п <	>с
Ет-п-',		&о ■• ■

тс:
Вв В , - - Вт-1
~Y~
В		В
ы		<л
п>т	с£о	) П
		*4-п-1
		----Т

						И
						- 1“*
						ЕU)
				В о	‘ • ■В т -1
			5		В
			Рис. 7.13.
Из схемы			реализующей оператор 9ft,			элементарно
просто получается			схема £ w.,	реализующая		оператор	W.
Достаточно	из	п	выходов	взять	лишь первые		т
выходов, как	в	соответствии		с (7.65)	получится схема
Е117 (рис. 7.13,5). Поэтому
			% { W ) ^ 2 n+4n.			(7.67)

Зависимости (7.64), (7.67) доказывают лемму 7.3. На основании леммы 7.3 получаем оценку для сложности

339

реализации оператора Ар.	а = max(/z — к, t).	(7.68)
££(А1) < 2 а+1/а,

Оператор А2■Этот оператор по старшим п-~k разря­

дам набора х (т. е. по набору х с) выдает набор е, пред­ ставляющий собой двоичную запись длины hА первого

участка кода я,1 t-го большого квадрата, соответствую­

щего х с■ Поскольку шах hA<22h+2, то набор е может

Рис. 7.14.

иметь не более	(2к + 2) разрядов. Оператор А2 является
(п—к, 2^ + 2)-оператором,		его сложность	равна
2	(Л ) < (2 * + 2) 2 » -* /(« -£ ).		(7.69)
Оператор кодирования А. Преобразуем код оператора
~~~ ....	1^	\ , о, V 0+l...... ^ho-V
n = ( n 0,	It,, ...,

” V	7CA o+ I ’ " • ’ 1tAo + A ' i - l ’ 1CA 0 + A ' i ' • " ’ ’ ' f t o + A i - l . • • • > ^ h - i )

Введем некоторый новый параметр l(2l «гораздо боль­

ше», чем Q) и разобъем набор я на «большие» куски

240