Добавил:

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

Вуз:

Уфимский Государственный Авиационный Технический Университет

Предмет:

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

Файл:

Теория кодирования

.pdf

Скачиваний:

186

Добавлен:

18.03.2015

Размер:

1.39 Mб

Скачать

☆

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

При l 1 c1 k, где k – число букв в алфавите B , следовательно, для префиксного кода можно выбрать c1 однобуквенных кодовых слов.

При l	2 c	k 2	l k	k k c .
	2		1	1
Пусть c1	буква выбрана как однобуквенное кодовое слово, тогда

для построения двухбуквенного кодового слова, обладающего

свойством префикса, у первой буквы остается k	c1 возможность, у
второй буквы k возможностей, то есть всего k k	c1 возможностей,

а c2 , число двухбуквенных кодовых слов в исходном коде, не

превосходит этого числа.

Пусть выбраны c1 кодовое слово длины 1, c2 слова длины два, и так далее вплоть до cl 1 слова длины l 1, обладающих свойством

префикса.

Покажем, что можно выбрать cl кодовых слов длины l , также обладающих свойством префикса.

В алфавите B слов длины l и k l . Найдем количество запрещенных слов, начинающихся с уже выбранных кодовых слов. Если какая-то буква выбрана в качестве однобуквенного кодового слова, то запрещены все слова длины l , начинающиеся с этой буквы, таких слов kl 1 .

Учитывая, что однобуквенных кодовых слов c1 , запрещено c1kl 1 слово. Запрещены все слова длины l , начинающиеся с c2 выбранных двухбуквенных слов, их c2kl 2 .

Таким образом число возможностей для выбора кодовых слов длины l , обладающих свойством префикса равно

kl	c kl 1	c kl 2	c kl 3...	c k , а	c	– число слов длины l в
	1	2	3	l 1	l

исходном алфавите не превосходит этого числа. Следовательно, можно построить префиксный код с тем же набором длин кодовых слов, как в исходном взаимно однозначном коде .

3. Оптимальный код.

В русском алфавите 32 буквы, е и ё можно считать за одну букву, предположим их надо закодировать равномерным кодом в алфавите B {0, 1} . Тогда длина каждого кодового слова должна быть равна 5, любое сообщение становится длиннее в 5 раз. С другой стороны, такие буквы как щ; ч; ы; ъ; ь и так далее встречаются редко, их можно было бы закодировать более длинными кодовыми словами, а встречающиеся часто – более короткими. Так возникает идея оптимальных кодов, которая связана с частотной (вероятностной) характеристикой букв кодируемого алфавита.

Каждая

буква

кодируемого

алфавита A обладает своей

частотой

(вероятностью) использования в языке,

обозначим

ее

pi , pi

pi 1.

Пусть

задано

алфавитное

кодирование:

i 1

Bi ,

длина

равна li . Посмотрим,

как

меняется

при

кодировании длина

N слова

A1 ,

ɱ A , то есть найдем длину

слова

A1 .

Буква ai

входит в слово A1

pi N раз, при кодировании она даст

длину pi Nli , следовательно, длина слова

A1 будет равна

pi Nli

pili .

i 1

Определение. Ценой кодирования называется число c , где

pili .

Цена

кодирования

показывает, во

сколько

раз

увеличивается

длина любого слова при кодировании, и является средней длиной кодового слова (математическим ожиданием кодового слова).

При фиксированных алфавитах A и B рассмотрим множество

взаимно однозначных кодов		, цена кодирования каждого c .
Найдем min c	на	множестве	, он очевидно,	будет
характеристикой кодируемого алфавита A:
min c	c	p1, p2, ...pm		(8)
14

Определение. Код ,такой что c

c p1, p2, ...pm , называется

оптимальным кодом или кодом с минимальной избыточностью. Пусть – оптимальный код, заданный набором кодовых слов

{B1,...Bm} с длинами l1, l2 ,...lm . Можно построить префиксный код ( по

теореме о существовании префиксного кода) с тем же набором длин кодовых слов, следовательно, с той же ценой кодирования.

Замечание. Среди оптимальных кодов всегда есть префиксный

код.
Пример 7. Пусть даны алфавиты					A	{a1, a2 , a3 , a4}		с
вероятностями	p1 0,4,	p2	0,25,	p3 0,2	и	p4	0,15	и
кодирующий алфавит B {0, 1}.
Рассмотрим два кода K1			{00, 01,10,11} и K2			{1, 01, 000, 001}.
Код K1 – равномерный,		K2	–	префиксный,		оба	однозначно

декодируемые. Найдем для каждого цену кодирования.

c	K1	0, 4	2	0, 25 2	0, 2 2	0,15 2	2
c	K2	0, 4 1		0, 25 2	0, 2 3	0,15 3	1,95.

Рассмотрим свойства оптимальных префиксных кодов.

1.Упорядоченность вероятностей кодового дерева по ярусам.

Пусть даны алфавит		A	{a1, a2 ,.. am} с набором вероятностей
P {p1, p2 ,...pm},	алфавит	B	{0, 1}, оптимальный префиксный код
K {B1, B2 ,...Bm}, где Bi		ai	, длина кодового слова Bi			равна li .
Тогда
а) если pi	p j то li	l j ;
б) если lk	max{l1, l2 ,...lm} и кодовое				слово Bk	B	, где
{0, 1}, то существует кодовое слово B				,	входящее в K ,		то есть
{0, 1}, то существует кодовое слово B				,	входящее в K ,		то есть

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

Замечание. Код называется q -ичным, если кодирующий алфавит B содержит q символов.

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

а) Пусть pi

и li

l j . Построим код K1 , переставив в коде K

два кодовых слова:

Bj ,

Bi .

Рассмотрим

c(K )

c K1

p1l1

...

pili ...

p jl j

...pmlm

( p1l1 ...

pil j ...

pjli ...

pmlm )

pili

pjl j

pil j

pjli

l j

pj li

l j

l j pi

откуда следует c K1

c K ,

то есть код

K не оптимальный, что

противоречит условию.

б) Пусть кодовое слово Bk

и имеет максимальную длину

lmax , а кодового слова

нет. Рассмотрим

фрагмент кодового

дерева, построенного для этого кода (рис. 8).

Построим код K1 ,

заменив в коде K

B , в

этом случае вершина B

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

кодовое

дерево

для

префиксного

кода

K1 .

Рассмотрим

c(K)

c K1

p1l1

...

pk lmax

... pmlm

Рис. 8

( p1l1

...

lmax

...pmlm ) pk

0 .

Вновь пришли к противоречию, получив взаимно однозначный

код K1 с ценой меньшей, чем оптимальный код.

Следствие.

В кодовом дереве для оптимального префиксного

кода вероятности, приписанные вершинам предыдущего яруса, не меньше, чем вероятности, приписанные концевым вершинам следующего яруса.

	2. Возможность построения упорядоченного оптимального
кода.
	Пусть K		B1, B2 ,..., Bm – оптимальный префиксный двоичный
код	для		набора	вероятностей	P	p1, p2 ,...pm , причем
p1	p2 ...		pm . Тогда, переставив слова в коде K ,				можно получить
код	K1	B1 , B2 ,..., Bm		с длинами кодовых слов			l1 ,l2 ,...,lm , для

которого будут выполняться три условия:

а) код K1 – оптимальный, то есть c K1		c K ,
б) l1 l2 ...	lm ,
в) кодовые	слова Bm 1 и Bm будут	отличаться только в

последнем разряде.

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

li 1

для какого-нибудь i .

Тогда по

предыдущему свойству

pi 1 , но по условию

pi pi

1 ,

отсюда

pi 1 . Построим код K1

переставив два кодовых слова в коде K ,

то есть положим

ai 1

Bi .

Рассмотрим

c(K )

c K1

p1l1 ...

pili

pi 1li 1

...

pmlm

( p1l1

...

pili 1.

1li ...

pmlm )

pili

pi 1li 1

pili 1

pi 1li

pi 1

li 1 pi 1

c K1

c K ,

– оптимальный код. Переставив так все кодовые

слова,

для

которых

l j

l j 1 , получим

код K1

B1 , B2

,..., Bm

c K1

c K

длины

кодовых

слов будут

расположены

по

неубыванию,

длина

lmax .

Но

возможно,

кодовые

слова

максимальной длины, отличающиеся только в последнем разряде не будут стоять рядом. Пусть Bm B , Bm 2 B , но тогда длина Bm 1 также равна lmax . Переставив местами кодовые слова Bm 1 и Bm 2 ,


получим код K1 , рассмотрим c K1				c K1	=
pm 2lm 2	pm 1lm 1	pm 2lm 1	pm 1lm 2
pm 2lmax	pm 1lmax	pm 2lmax	pm 1lmax		0, цена кодирования не
изменилась,	K1 – оптимальный код.

Лемма о префиксных кодах.

Пусть даны два двоичных кода K1 и K2 . Код

K1 {B1,...Bm , B 0, B 1}с набором вероятностей P {p1,...pm , p , p }, длина кодового слова Bi равна li , длина слова B равна l , тогда длины кодовых слов B 0 и B 1 равны l 1. Код K2 {B1,...Bm , B } с набором

вероятностей p1,...pm , p		p p .
Тогда утверждается:
а) если K1	префиксный код, то K2 тоже префиксный код, и
наоборот;
б) c K1	c K2	p .

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

а) Пусть K1 – префиксный код, тогда для него существует

кодовое дерево, висячим вершинам которого соответствуют кодовые слова. Рассмотрим фрагмент этого дерева (рис.9).

	Если убрать	вершины	B 0 и	B 1	вместе
	инцидентными	ребрами,	вершина	B станет
	висячей, мы получим кодовое дерево для кода K2 , в
	котором кодовым словам соответствуют только
	висячие вершины, следовательно,			код	K2 –
Рис.9	префиксный.

Наоборот, если K2 – префиксный, то вершина, соответствующая кодовому слову B , висячая. Добавив к этой вершине два ребра, получим две висячие вершины B 0 и B 1, а слово B в код K1 не входит, вновь получим кодовое дерево для префиксного кода.

б) Найдем цену кодирования кода K1 .
c K1	p1l1	... pmlm	p	l	1	p	l 1
	p1l1 ...	pmlm	p	p	l	p	p
	p1l1 ...	pmlm	pl	p	c K2		p .

Теорема редукции
Пусть K1		{B1,...Bm , B 0, B 1}		двоичный	код для			вероятностей
кодируемого		алфавита	p1, p2 ,...pm , p , p ,		а		K2	{B1,...Bm B }
двоичный код для вероятностей p1, p2 ,...pm , p					p		p .
Тогда
а) если K1 –оптимальный префиксный код, то K2 также
оптимальный префиксный код;
б)	если	K2 –оптимальный префиксный				код	и	вероятности
упорядочены		p1 p2 ...	pm p	p , то	K1	тоже оптимальный
префиксный код.
Доказательство
а)	Пусть	K1 – оптимальный префиксный код,					K2 –префиксный

код (по лемме), но пусть он не оптимальный. Тогда существует

оптимальный код K2 , такой что c K2				c K2 . Среди оптимальных
кодов можно		найти	префиксный	код K2 ,	такой	что
c K2	c K2	c K2 .
	Пусть	K2 {B1, B2 ,...Bm , B }.		Построим		код
K1	{B1, B2 ,...Bm , B 0 B 1},		он префиксный, цена кодирования			его
c K1	c K2	p c K2	p c K1 , то	есть код K1	имеет	цену
меньше, чем код K1 , что невозможно, так как K1 –оптимальный код.
	б) Пусть K2 – оптимальный префиксный код, K1 –префиксный
код,	но пусть он не оптимальный, тогда существует оптимальный

префиксный код K1 и c K1 c K1 .

Пусть K1 {B1, B2 ,...Bm , Bm 1, Bm 2}. Так как вероятности

упорядочены по невозрастанию, по теореме о возможности построения упорядоченного оптимального кода, можно перестроить код K1 и получить код K1 , в котором кодовые слова расположены в

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

K1 {B1, B2 ,...Bm , B , B	}, c K1 c K1	c K1 .

По коду K1 можно построить код K2		{B1, B2 ,...Bm , B },

c K2 c K1 p c K1 p c K2 , то есть мы нашли код, цена кодирования которого меньше, чем у оптимального кода – противоречие.

Следствие. Теорема редукции дает алгоритм построения оптимального кода, который называется кодом Хаффмена.

Пример 8. Построить оптимальный двоичный префиксный код

для упорядоченного набора вероятностей
P 0,3, 0,3, 0, 2, 0,1, 0,05, 0,05					. Процедура Хаффмена выглядит
следующим образом:
							Таблица 1

			p	1	2	3	4
	00		0,3	0,3	0,3	0, 4	0, 6	0
	01		0,3	0,3	0,3	0,3	0, 4	1
	10		0,2	0,2		0,3	0, 4
	10		0,2	0,2	0, 2	0,3
	110		0,1	0,1		0,3
	110		0,1	0,1	0, 2
	1110		0,05		0, 2
	1110		0,05	0,1
	1111			0,1
	1111		0,05
			0,05

	Для	набора вероятностей			0, 6;0, 4 ,	то есть для	двух	букв,
оптимальным будет код 0,1 .					Он играет роль кода K2		из теоремы
редукции,			тогда код,	построенный из K2		для набора вероятностей

0, 4; 0, 3; 0, 3 , играет роль кода K1 и будет оптимальным. Повторяя

этот процесс, мы получим оптимальный код для исходного набора вероятностей. Для этих «обратных» шагов удобнее строить кодовое дерево (рис. 10).

Рис. 10

На этом примере видно, что хотя шаги 1-4 стандартны, оптимальный код не будет единственным, например, для вероятности 0,6 можно было взять кодовое слово 1, для 0,4 взять 0. На рис. 11 показано другое кодовое дерево для этого же набора вероятностей и соответствующий ему набор кодовых слов

K 11, 10, 01, 000, 0010, 0011

Рис. 11

4. Самокорректирующийся код

При передаче сообщения в канале связи может действовать источник помех или шумов. Ясно, что при произвольных помехах невозможно восстановить исходное сообщение. Код, позволяющий восстановить исходное сообщение при некоторых ограничениях на шумы, так называющий самокорректирующий код, был предложен Ричардом Хэммингом в 1950 году.

Рассмотрим равномерное кодирование, при котором длина каждого кодового слова равна l , а алфавит B 0,1 . Будем

предполагать, что помехи, во первых, не меняют длину кодовых слов, во-вторых, в каждом кодовом слове происходит не более p ошибок

p l типа замещение, то есть 0 меняется на 1, а 1 меняется на 0. Определение. Код называется корректирующим p ошибок типа

замещения, если при замене не более чем p символов в любом кодовом слове, можно восстановит это кодовое слово.

Хэмминг подробно описал код, корректирующий одну ошибку,

именно его мы и рассмотрим.
Пусть кодовое слово Bs	1 2	l , где каждое i 0,1 , и k –
минимальное натуральное число, такое что l 2k			1.

	Тогда все числа от 1 до l можно закодировать k -разрядными
двоичными числами, если t				1,l , то его можно записать
		t	tk 1,tk 2 ,		,t2 ,t1		,t0	2	.
								2
	В	множестве чисел		1, 2,		, l		введем		подмножества
wi	t : ti	1 , тогда
		w0		t : t0	1		1,3,5,7,			,
		w1		t : t1	1		2, 4,6,7,			,
		w2		t : t2	1		4,5,6,7,			,
		wk	1	t : tk 1		1 .

Эти подмножества пересекаются, но не совпадают, причем среди чисел 1,2, ,l есть такие, которые попадают ровно в одно

подмножество. Такими числами будут степени числа два: 20 ,21,22 и так далее, так как в их двоичном представлении присутствует всего одна 1.

Определение.

Кодом Хэмминга длины l называется множество

слов

1 2

l ,

0,1

удовлетворяющих

следующим

условиям:

(9)

t w0

t w1

wk 1

где

означает сумму по модулю 2.

Теорема о коде Хэмминга.

Код Хэмминга длины l

содержит 2l

кодовых слов.

k – целая часть сверху log2

1 :

log2 (l 1) .

Код корректирует одну ошибку типа замещения.

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

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

#
23.08.201962.98 Кб1темы практических занятий.doc
#
17.03.201539.94 Кб40Темы РГР, требования.doc
#
17.03.201533.79 Кб11темы рефератов.doc
#
15.11.201936.43 Кб1теория бух учета.docx
#
19.11.2018785.92 Кб2Теория вышка 1 сем..doc
#
18.03.20151.39 Mб186Теория кодирования.pdf
#
18.03.20155.55 Mб182Теория механизмов (задачник).doc
#
18.03.2015923.07 Кб145Теория множеств(пособие ЕНФ)(Водопьянов).pdf
#
04.05.2019683.4 Кб77Теория на экзамен по физике B1.docx
#
17.03.2015536.58 Кб104Теория оптимизац_Конспект лекций_2012.doc
#
22.08.2019218.62 Кб5теория организ.doc