Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сибирский Государственный Университет Телекоммуникаций и Информатики

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

681_Trofimov_V.K._Teoremy_kodirovanija_neravnoznachnymi_

.pdf

Скачиваний:

Добавлен:

12.11.2022

Размер:

2.19 Mб

Скачать

☆

<<< < Предыдущая 1 2 34 / 84 5 6 7 8 > Следующая >>>

1Y a;b I1 I2 , I1	0;0,81 ,	I2 0,81;1 .
Для построения разбиения Y2 a;b	вычислим	границы интервалов 1Y Ii ,
i=1,2. Согласно определению,

I11 I1 I1 I1 0;0,81 0 0,81 0;0 0,81 0,81 0;0,659 , I12 I2 I1 I2 0;0,81 0 0,81 0,81;0 0,81 1 0,659;0,81 ,

I21 I1 I2 I1 0,81;1 0,81 0,19 0;0,81 0,19 0,81 0,81;0,8767 ,

I22 I2 I2 I2 0,81;1 0,81 0,19 0,81;0,81 0,19 1 0,8767;1 .

Продолжая строить разбиения разбиений получим своеобразную сеть на заданном интервале (см. рис. 8).

Иллюстрация разбиения приведена на рис. 9.

Рис. 8. Разбиения единичного интервала глубины 1 и 2.

Рис. 9. Схема разбиений интервала различной глубины.

Сформулируем и докажем ряд утверждений о свойствах определенных выше разбиений.

Лемма 3.1.1 (о свойствах Yn a;b -разбиения).

Пусть на интервале a;b задано разбиение

a;b

... j

a;b

ji 1,m;i 1,n

Тогда:

1) границы a

j1 j2 ... jn 1

a j

... j

интервала I j

... j

a;b

j1 j2 ...

jn 1

; a j

j ... j

вычис-

ляются по формулам:

a j

t j

j2 1

t j

... j

1 a (b a)

i 0

... 0

1 0

... 0

n 1 0

i 1

a j j

... j

1 2

j2 1

jn 1 1

(b a)

t j

;

0 i

0 1 0

... 0

n 2

... 0

n 1

i 1

a;b

t ji

2) длина интервала I j

... j

равна

I j

... j

(b a) 0

i 1

Доказательство. Индукция по n.

База индукции: при n 1

I j1 a,b

a j1 1;a j1 ;

тогда по определению разбиения:

, a j

a j 1 a b a 0

a (b a) 0

i 1

a,b

(b a) t j1 .

Допустим, что утверждение имеет место для

I j

j ... j

a;b a

j j

...

;a j j ... j

1 2

По определению разбиения

I j

j ... j

a;b I j

... j

;a j

... j

;a j

j ... j

j j

n 1

и верны следующие соотношения:

a;b

jn 1 1

I j

...

j j

... j

ji ,

n 1

i 1

a j

I j j

a;b

jn 1

... j

n 1

...

... j

ji .

i 1

Из этого следует первое утверждение леммы. Действительно,

j2 1

...

jn 1

j1 j2 ... jn 1

a (b a)

jn 1

i 1

t ji

jn 1

(b a) 0 i 1

i 1

j1 1

j2 1

n 1

jn 1

t ji

jn 1

a (b a)

... 0 i 1

0 i 1

i 1

...

jn 1

j1 j2 ... jn 1

a (b a)

jn 1

i 1

t ji

jn 1

(b a) 0 i 1

i 1

j1 1

n 1

j2 1

t ji

jn 1

a (b a)

... 0 i 1

0 i 1

i 1

Далее, по определению Y a;b получаем второе утверждение леммы:

n 1

a;b

a j1 j2

t ji

I j1 j2

... jn 1

a j

... j

n 1

1 (b a) 0 i 1

Лемма доказана.

Рис. 10. Зависимость длин интервалов от глубины разбиения.

На рис. 10 наглядно продемонстрирована зависимость длин интервалов разбиений единичного отрезка от глубины разбиения и положения на разбива-

емом отрезке.

3.2.Схема кодирования неравнозначными символами

Рассмотрим произвольный источник информации, генерирующий блоки длины N над алфавитом X. В работе [72] Г. Катоной предложена схема кодиро-

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

тельности. Данную процедуру кодирования далее предлагается использовать и для универсального кодирования, опираясь на КТ-распределение [26]. Ниже

доказана оптимальность предлагаемой модификации.

Идея кодирования заключается в следующем.

Пусть		на X N задан закон	распределения вероятностей	p(w ) p ,
				i	i
w X N ,
w X N ,	p	0 i 1, k N . Рассмотрим порожденное данным законом отноше-
i	i
ние нестрогого порядка, а именно,			положим wi wi ' , если p(wi ) p(wi ' ) .		Не

уменьшая общности, можно считать, что

pi 1 pi

p2N 0. В со-

ответствие каждой последовательности wi

поставим величину

i 1

wi p(wn ) , i 2, k N

и w1 0 .

(3.6)

n 1

Определение 3.2.1. Кодирование

, p

определим как функцию

...y

(3.7)

o , p

которая ставит в соответствие кодовой последовательности wi

сло-

во из букв кодового алфавита

y j

y j ...y j

, где

j1 j2... jn

– набор индексов интер-

вала I j j

... j

0;1

Yn 0;1 ,

удовлетворяющего следующим условиям:

1 2

1) wi I j

... j

0;1 ,

wi 1 I j

... j

0;1

(3.8)

... j

0;1

i 1

wi 1 I j

... j

0;1

n 1

j1 j2 ... jn 1

0;1

i 1

( wi –

значения,

определенные равенством (2.13)). Условия (2.15)

гаранти-

руют дешифруемость кодирования (2.14). Отметим, что условие pi 0 обеспе-

чивает конечность процедуры кодирования. Поскольку смежные значения раз-

личны: wi 1 wi , i 1, n , то каким бы малым не было различие между

ними,	существует такое n ' , что для разбиения Yn ' 0;1 значения wi 1	и
wi	окажутся в различных (не обязательно смежных) интервалах	из

Yn ' 0;1 .

Пример построения кода. Рассмотрим источник сообщений с алфавитом

X 0,1 . Пусть длина сообщений источника N=3, а длительности кодовых символов t 0 1, t 1 3. В качестве закона распределения вероятностей на множестве бинарных последовательностей источника рассмотрим функцию

p(wi ) 14C3k

(где k – число единиц в слове wi xi1 xi2 xi3 ). Упорядочим последовательности по убыванию их вероятности.

i 1

Вычислим соответствующие каждому блоку значения (wi ) p(wi ' ) .

																										i ' 1

			i			1		2			3		4	5				6		7				8

			wi			000		111			001		010	011				100		101			110

			p(wi )			1/4		1/4			1/12		1/12	1/12				1/12		1/12			1/12

			(wi )			0		1/4			1/2		7/12	8/12				9/12		10/12			11/12

												Табл. 9.
Построим разбиение												согласно заданным длительностям кодовых
Построим разбиение										0;1		согласно заданным длительностям кодовых
символов. Приближенное значение корня																	уравнения					1 3 1						равно
0 1,47 . Определим длины и границы интервалов:
	I0 0;1					1	1,47			1	0,68 ,				I1 0;1						3	1,47		3	0,32		;
						1				1											3			3
				0															0
			I0 0;1 0;0,68 ,															I1 0;1 0,68;1 .

i		1			2				3			4				5					6			7				8

(wi )		0			0,25				0,5			0,5833				0,67					0,75			0,833				0,917

I j 0;1			I0		I0				I0			I0				I0					I1			I1				I1

Табл. 10.

Оба полученных интервала содержат несколько значений (wi ) , следова-

тельно, не выполняется условие 2) из определения кодирования o , p , и необ-

ходимо разбить каждый из полученных интервалов на более мелкие, т.е. найти

разбиение					интервала 0;1 или, другими								словами, разбиения I0 0;1 и
I1 0;1 :
	I00 0;1					2	0,46 ,			I01 0;1		I10 0;1		1		3	0,22	,
						2								1		3
					0									0	0
	I11 0;1					3	3	0,1;		I00 0;1 0;0,46 ,
						3	3
					0		0
	I01 0;1 0,46;0,68 ,									I10 0;1 0,68;0,9 ,						I11 0;1 0,9;1 .

				i			1	2	3		4		5	6			7		8

		(wi )					0	0,25	0,5		0,5833		0,67	0,75		0,833			0,917

		I j	j	0;1		I00		I00	I01		I01		I01	I10			I10		I11
		1		2

											Табл. 11.
В результате,
w1 , w2 I00 0;1 ,											w3 , w4 , w5 I01 0;1 ,
w6 , w7 I10 0;1 ,											w8 I11 0;1 .
				Это означает, что для последнего интервала										I11 0;1			более разбиение

строить не требуется, условия 1)–3) из определения кодирования 3.2.1. выпол-

няются для w

и,

следовательно, определен код

110 11. Остальные

o , p

интервалы необходимо разбить. В

результате

построения разбиений

I00 0;1 , I01 0;1 и I10 0;1 получим:

I000

0;1

0,31,

001

0;1

010

0;1

5 0,15,

100

011

0;1

7 0,07

101

I000 0;1 0;0,31 ,

I001 0;1 0,31;0,46 ,

I010 0;1 0,46;0,61 ,

I011 0;1 0,61;0,68 ,

I100 0;1 0,68;0,83 ,

I101 0;1 0,83;0,9 .

i				1	2	3	4	5	6	7		8

(wi )				0	0,25	0,5	0,5833	0,67	0,75	0,833		0,917

I j	j	j	0;1	I000	I000	I010	I010	I011	I100	I101
1	2		3

							Табл. 12.
	Проверим условия 1)–3) в определении кодирования										:
										o , p

w1 , w2 I000 0;1 ,

w3 , w4 I010 0;1 ,

w5 I011 0;1 ,

w6 I100 0;1 ,

w7 I101 0;1 .

Условия выполняются для

– w7 и, следовательно, определены

кодовые

последовательности

011 011,

100 100

o , p

, p

101

101. Условие 2) еще не выполняется для

w , w ,

w4 , следовательно, необходимо

построить разбиения

I000 0;1

I010 0;1 :

0000

0;1

4 0,21,

0001

0;1

0100

0;1

6 0,1,

I101 0;1 0,83;0,9

0101

0;1

0,05

I0000 0;1 0;0,21 ,

I0001 0;1 0,21;0,31 ,

I0100 0;1 0,46;0,56 ,

I0101 0;1 0,56;0,61 ,

I100 0;1 0,68;0,83 .

На данном этапе условия 1) – 3) из определения кодирования выполняются для всех рассматриваемых значений (wi ) и, следовательно, определены кодо-

вые последовательности:

	, p		000 0000			,	, p	111	0001,			, p	001 0100			и		, p	010 0101.
o	, p					o	, p				o	, p					o	, p

	i					1		2		3	4			5	6		7			8

	(wi )					0		0,25		0,5	0,5833			0,67	0,75		0,833			0,917

	I j		j	j j	0;1	I0000		I0001		I0100	I0101
		1	2	3	4

Табл. 13.

Более наглядно разбиение проиллюстрировано на рисунке 11 (серым цветом

выделены участки, пропорциональные по длине	I	0	1	и соответствующие

			0

кодовому символу «0», а белым цветом – участки, пропорциональные по длине

интервалу

и соответствующие кодовому символу «1»), там же отмече-

ны значения

(wi ) .

Рис. 11. Иллюстрация разбиения интервала и выбора кода.

Соответствующие сообщениям кодовые слова даны в табл. 14:

000

001

010

011

100

101

110

111

0000

0100

0101

011

100

101

0001

Табл. 14.

Лемма 3.2.1. Для кодирования

, p

: X N

Y * , где

, p

...y

имеют место неравенства:

I j

... j

n 1

0;1

p wi ;

0;1

t**

, где t** max t j .

I j

... j

0 o , p i

n 1

1 j m

Доказательство.

1) Рассмотрим произвольное сообщение wi

и соответ-

ствующее ему кодовое слово wi .

Для данного сообщения i Ii i ...i 0;1 ,

1 2

тогда один или оба соседних элемента

i 1

и i 1

принадлежат интервалу

Ii i ...i

0;1 . Следовательно,

длина интервала

Ii i

...i

0;1 больше,

чем рас-

1 2

n 1

1 2

n 1

стояние от i

до ближайшего «соседа»

i 1

или

i 1,

так как по условию

pi 1 pi :

Ii i

...i

0;1

min i i 1, i 1

i min pi 1, pi pi .

1 2

n 1

0;1

t ji

2) Из леммы 3.1.1 следует, что

I j j

... j

n 1

i 1

Преобразуя, получим

n 1

I j j ... j

0;1

t ji

t jn

t**

0 i 1

n 1

где t** max t

Лемма доказана.

1 i m

<<< < Предыдущая 1 2 34 / 84 5 6 7 8 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
12.11.20221.89 Mб6671_Vajspapir_V.JA._Proektirovanie_radiochastotnykh_linij_svjazi_.pdf
#
12.11.20221.06 Mб0672_Otsenka_stoimosti_biznesa_.pdf
#
12.11.2022548.77 Кб4673_Raschet_analogovykh_i_diskretnykh_ustrojstv_.pdf
#
12.11.20223.28 Mб6675_Lebedenko_L.F._Osnovy_vizual'nogo_programmirovanija_.pdf
#
12.11.202224 Mб9676_Noskova_N.V._Izuchenie_funktsionirovanija_setej_.pdf
#
12.11.20222.19 Mб5681_Trofimov_V.K._Teoremy_kodirovanija_neravnoznachnymi_.pdf
#
12.11.20227.92 Mб17683_Filimonova_N.I._Metody_ehlektronnoj_mikroskopii_.pdf
#
12.11.2022880.37 Кб9684_Filimonova_N.I._Metody_ehlektronnoj_spektroskopii_.pdf
#
12.11.2022481.48 Кб0686_CHurkina_N.A._Sotsiologija_kul'tury_.pdf
#
12.11.20224.18 Mб7687_Sazhnev_A.M._Sistemy_ehlektropitanija_.pdf
#
12.11.20224.44 Mб13688_Sergeeva_A.S._Bazovoe_programmnoe_obespechenie_.pdf