Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки»



Скачать 219.02 Kb.
Дата09.10.2012
Размер219.02 Kb.
ТипДокументы




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

2. Рассмотрим основные характеристики систем передачи данных по каналу связи без ошибок: V(x) и C.

3. V(X).Среднее количество информации, передаваемое по каналу в единицу времени, называется скоростью передачи информации: V(x).
V(x) = lim(I(x)/T)

T

4. Пропускная способность к.с. является важнейшей характеристикой к.с. и формально определяется как максимально возможная скорость передачи информации:
C = {V(x)}max

5. Одним из важнейших вопросов проектирования системы передачи данных является согласование V и C:

а) Для эффективного использования канала связи необходимо принять меры

к V(x) C;

б) Вместе с тем, для передачи всей информации по каналу связи (отсутствие режима «захлебывания» канала связи): V(x) < C.

6. Впервые эти вопросы были исследованы К. Шенноном, который показал, что основным условием динамического согласования источника сообщений и информационного канала является соотношение:

V(x)  C


Рассмотрим это соотношение на примере дискретного канала без помех.

Постановка задачи: а) как определить (оценить) V(x) и C?

б) практический вопрос: VC. Как?

1. Дискретный источник информации создает сообщение из X={X1, X2, … Xn} – символов первичного алфавита, которые подаются на вход канала. В любом реальном канале всегда присутствуют помехи. Однако, если уровень помех так мал, что вероятность искажения приблизительно равно нулю, то можно считать, что: символы передаются без искажений.

а) При этом среднее количество информации, переносимое одним символом:

I(x) = H(x),

а максимальное значение среднего количества информации на символ Hmax(Х), получается в случае:

P1 = P2 = … = Pn = ½,

при этом, Hmax(X) = log2n

б) скорость информации будет определяться:

V(X) = 1/ *H(X),

где  - длительность передачи символа;

H(X) – количество информации переносимое одним символом.

V –скорость передачи сообщения = сообщ./с

в) по соотношению: V(x)  C

V(x) = C – для случая, когда V(X) = Vmax (X),

т.е.
C = max{1/ * H(X)}= 1/ *max[H(X)] = 1/ * log2n, где 1/ - чистая характеристика канала.

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

Необходимо различать C и V(X).

а) С – зависит только от характеристик канала;

V(X) – от H(X) – статистического распределения источника сообщений;

  • ограничена сверху С.

б) по размерности

V(X) – для двоичного канала измеряется в бит/сек.

С – количество двоичных разрядов (двоичных единиц), проходящих в единицу времени по каналу. С = дв.ед./сек.

в) V(x)  C , т.е. в пределе один двоичный знак может нести информацию не более 1 бита (т.е. двоичный разряд не может содержать более 1 бита информации).

0  I дв. разр.  1 бита

Первая теорема (практическое значение) ВСТАВКА 2А

А) передача информации по каналу связи без помех

Б) хранение информации

*) защита от несанкционированного доступа

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

Wmin ЗУ  I

Пример 1.

Источник вырабатывает сообщения с вероятностью: P1, P2, P3, P4 и подключен к синхронному двоичному каналу с пропускной способностью C = 1000 дв.ед./с. Определить скорость передачи для случаев:

А) P1 = ½ B) P1 = ¼

P2 = ¼ P2 = ¼

P3 = ⅛ P3 = ¼


P4 = ⅛ P4 = ¼

  1. Пропускная способность, не зависящая от априорной вероятности C = 1 000 000 дв.ед./с

 = 2 дв.ед./букв. V = C/ = 500 000 дв.ед./с

  1. Скорость для случая А:

4 -2 -1 -3 2 4

а) I(X) = -  Pi *log2Pi = ¼ *log2¼ +½ *log2½ + 2/8 *log2⅛ = 2/4 + ½ + 6/8 = (4+4+6)/8 = 14/8 =

i

= 1,75 дв.ед./сообщ.

б) V = V *I(X) = 1/ *I(X) = 500 000 сообщ./с * 1,75 дв.ед./сообщ. = 875 000 дв.ед./с

Скорость для случая В (равновероятное распределение):

4

а) I(X) = -  Pi *log2Pi = 4* ¼ *log2¼ = 2 дв.ед./сообщ.

i

б) V = V *I(X) = 1/ *I(X) = 500 000 сообщ./с * 2 дв.ед./сообщ. = 1 000 000 дв.ед./с
Пример 2

Провести оценку объема ЗУ, требуемого для хранения 1 страницы стандартного текстового материала с использованием русского алфавита.

а) Стандартный (используемый) способ [коды ASCI]:

1800 знаков х 1 байт – 1800 байт

б) с использованием равномерного кодирования (ПРОМЕЖУТОЧНЫЙ) (32 буквы – 5 знаков);

1800 знаков х 5 дв. разр. = 1125 байт

8 дв. разр.

в) минимально возможная (принципиально достижимая) величина:

1800 знаков х 2 дв. разр. = 450 байт разница в 4 раза между а) и в)

8 дв. разр.

Для каждого источника сообщений соотношение V(X) C может быть достигнуто специальным выбором способа кодирования сигналов (сообщений).

О степени приближения скорости передачи информации V(X) к пропускной способности канала утверждает теорема Шеннона для дискретного канала без помех.
Первая теорема Шеннона (об эффективности передачи информации по каналу связи)
Пусть источник сообщений характеризуется средним количеством информации I [бит/сообщ.], а канал связи имеет пропускную способность С дв.ед./с. Тогда можно закодировать сообщение на выходе источника таким образом, чтобы передавать сообщения по каналу со средней скоростью V(X) = C -  бит/сек, где   сколь угодно малая величина. V(X) – практический параметр. Передавать сообщение со средней скоростью V(X)  C/I – невозможно.

Иными словами: всегда можно построить такую систему передачи (с помощью специального кодирования), при которой среднее количество двоичных единиц на букву приближается к среднему количеству информации как угодно близко.
Первая теорема Шеннона утверждает, что существует системное кодирование, обеспечивающее V(X)  C, однако не указывает конкретную процедуру кодирования.

Вместе с тем,

а) V(X)  C осуществляется для I(X) = max,

б) что, в свою очередь, обеспечивается при равномерном распределении передаваемых символов сообщения.

Подобные процедуры кодирования, обеспечивающие V(X)  C, называются эффективными (оптимальными) и, впервые, были предложены Шенноном, Фано, Хаффменом.
Статистическое эффективное кодирование. (Использование при передаче и хранении).
Кодирование, учитывающее статистические особенности источника сообщений называется статистическим (эффективным) кодированием.

В настоящее время разработано большое количество различных способов оптимального статистического кодирования. Все они должны обеспечивать решение двух основных задач:

  1. при заданной статистике сообщений {Pi}формировать кодовые комбинации, допускающие V(X)  C

  2. возможность однозначного декодирования сигналов на приемной стороне

Для двоичного канала с отсутствием статистических связей между символами этим требованиям удовлетворяет код Шеннона-Фано.

Известно, что V  C выполняется при равной вероятности появления различных сообщений.

В соответствии с этим, построение кода выполняется по следующей последовательности:

А) все буквы алфавита выписывают столбцом в порядке убывания вероятности;

Б) столбец последовательно делят на группы с приблизительно равной суммарной вероятностью.

При этом:

  • верхней половине  «0»;

  • нижней половине  «1»;

В качестве примера рассмотрим алфавит сообщений из 8 букв (для С = 3000 дв.ед./с)





Pi

Эффективное кодирование

Равномерное кодирование







1

2

3

4

5

6

7

8

1

2

3

Z1

½

0






















0

0

0

Z2

¼

1

0



















0

0

1

Z3



1

1

0
















0

1

0

Z4

1⁄₁₆

1

1

1

0













0

1

1

Z5

1⁄₃₂

1

1

1

1

0










1

0

0

Z6

1⁄₆₄

1

1

1

1

1

0







1

0

1

Z7

1⁄₁₂₈

1

1

1

1

1

1

0




1

1

0

Z8

1⁄₁₂₈

1

1

1

1

1

1

1




1

1

1

Особенности


В) Полученный код является неравномерным, т.к. длина кодовых комбинаций находится в обратной зависимости от их вероятности.

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

Оценим скорость передачи информации для методов:

а) статистического кодирования;

V = C *I /ср.

На передачу каждого сообщения в среднем требуется V = C/  1500 сообщ./с

8

ср. = Pi *i = 163/64 дв.разр. ср.= H(X)

i=1

8

H(X) = - Pi *log2Pi =163/64 бит/символ. Для C = 3000 дв.ед./с  V(Z) = 3000 бит/с;


i=1

б) равномерного кодирования;

Каждому сообщению требуется 3 двоичных разряда равн.= log2N, а каждое сообщение Zi содержит:

8

I(Z) = H(Z) = - Pi*log2Pi = 163/64 бит/сообщ.

i=1

Поэтому, при C = 3000 дв.ед./с имеем: V = 1000сообщ./с V(Z) = 1*1000 = 1984 бит/с

В рассмотренном примере получено:

V(Z) = C и Kотн. =1 -идеальный случай.

Это удалось получить благодаря тому, что в рассмотренном примере значения P(Zi) были заданы такие, что подгруппы точно делились пополам.
2. ВВЕДЕНИЕ В КРИПТОГРАФИЮ.

  1. Приближение V к C было осуществлено за счет:

“качественно” – наиболее часто передаваемые сообщения кодировались наиболее короткой длиной двоичных разрядов, и наоборот.

“количественно” – (более строго) за счет нового кодирования получено равномерное распределение i.

После кодирования сообщения, буквы алфавита Zi были заменены на значения двоичных разрядов j.

Рассмотрим вероятность появления значений j (двоичных разрядов) для статистического и равномерного методов кодирования.

Статистическое Равномерное

j 1 0 P0 = 15/16

1 P1= 1/16

Pj = 0  0,5 j   равенство  2 0 P0 = 51/64

Pj = 1  0,5 стремится к = 1 P1= 13/64

3 0 P0 = 87/128

1 P1= 41/128





1 231 2 3

явно неравномерное распределение

В реальных условиях это, как правило, не обеспечивается.

Рассмотрим следующий пример.

Источник вырабатывает сообщения, формируемые из трех независимых символов с вероятностями:

x1 P1= 0,65; x2 P2= 0,23; x3 P3= 0,12

  1. оценить эффективность применения равномерного и статистического способа кодирования

  2. каким образом можно добиться V = 0,99 *C, C = 1000 дв.ед./с

а) дв.равн.= [log2N] = [log23] = 2 дв.ед.

3

H(X) = Pi *log2Pi = 1,26 бит

i=1

V(X) = H(X)/ дв.равн.* C = 630 бит/с ; K = H(X)/ дв.равн.= 1,26/2 = 0,63

что соответствует 63% от С.

б) применим эффективное кодирование

Pi 12

X1 0,65  0

X2 0,23  1 0

X3 0,12  1 1

3

При этом: дв.=Pi *дв.i= 1* 0,65 + 2* 0,23 + 0,12 *2 = 1,35 дв.ед.

i=1

Kотн.коэф.= 0,933

Причиной C > V(X) и Kотн. эфф. 1 при использовании эффективного способа кодирования является невозможность разбиения сообщений { Xi } на подгруппы с достаточно близкой вероятностью.

Кодирование сложных сообщений



в) Дальнейшим возможным способом повышения скорости передачи информации является кодирование не каждого символа сообщения, а группы из двух символов, что позволяет получить новый набор из 9 групп {XiXj} и возможность деления на более близкие по суммарной вероятности подгруппы:

Сообщение Yk = Xi *Xj Вероятность PYk = PXi *PXj
Y1 = X1*X1 0,4225

Y2 = X1*X2 0,1495


Y3 = X1*X3 0,0780

Y4 = X2* X1 0,1495

Y5 = X2*X2 0,0529

Y6 = X2*X3 0,0276

Y7 = X3*X1 0,0780

Y8 = X3*X2 0,0276

Y9 = X3*X3 0,0144
Далее КС РС

Применим принцип кодирования Шеннона-Фано.





Вероят -ность

1

2

3

4

5

6

1

2

3

4

5

6

Длитель-ность (i)

Y1

0,4225

I

}I













1

1













2

Y2

0,1495




}II













1

0













2

Y4

0,1495




I

}I










0

1

1










3

Y3

0,0780







}II










0

1

0










3

Y7

0,0780






}I










0

0

1










3

Y5

0,0529

II








}I







0

0

0

1







4

Y6

0,0276



II

II





}I




0

0

0

0

1




5

Y8

0,0276









II

II


}I

0

0

0

0

0

1

6

Y9

0,0144















}II


0

0

0

0

0

0

6

9

При этом, ср. = Pi *i = 2,67 дв.ед./сообщ.

i=1

H(X) - энтропия сообщения, состоящего из двух символов, определяется как

9

H(X) =  P(Yi)*log2P(Yi)  2,53 бит/сообщ.

i=1

V(X) = C/ср.* H(X) = 948 бит/с

K = 2,53=H(X)/2,67= ср.= 0,948 < 1
Рассмотренная процедура кодирования, основанная на методе Шеннона-Фано, не всегда является однозначной, так как возможны различные варианты разбиения сообщения на подгруппы с близкими вероятностями (пример:{Y1}и {Y2÷Y9}).

Рассмотрим последовательность кодирования {Yi}по методу Хаффмена, гарантирующему однозначность разбиения на подгруппы и являющегося более рациональным при кодировании достаточно больших групп сообщений.

Метод Хаффмена – гарантирует однозначное построение кода с наименьшим для данного распределения {Pi} - ср. – средним числом двоичных разбиений на сообщения.

1. Буквы алфавита сообщения выписывают в основной столбец в порядке убывания вероятностей.

2. Две последние буквы объединяются в одну вспомогательную, которой приписывается суммарная вероятность.

  1. Процесс продолжается до получения единственной буквы.







Вероят -ность

1

2

3

4

5

6

7

8

9

Y1

0,4225

0,4225

0,4225

0,4225

0,4225

0,4225

0,4225

0,5775

1,0000




Y2

0,1495

1495

1495

1495

1560

2720

0,3055

0,4225







Y4

0,1495

1495

1495

1495

1495

1560

0,2720










Y3

0,0780

0780

0780

1225

1495

1495













Y7

0,0780

0780

0780

0780

1225
















Y5

0,0529

0529


0696

0780



















Y6

0,0276

0420

0529




















Y8

0,0276

0276



















Y9

0,0144




























  1. Кодирование сообщений осуществляется по результатам построения «кодового дерева».

Y1 Y2 Y4 Y3 Y7 Y5 Y6 Y8 Y9

0 110 101 1111 1110 1000 100111 10010 100110
9

ср. =  Pi*i = 2,55 дв. разр./сообщ.

i=1

H(Y)  2,53 бит


V  C/ср.* H(Y)  993 бит/с

Далее КСРС

Kотн.эфф. = 0,993

Vравн. = 630;

VШ.Ф.прост.сообщ. = 933;

VШ.Ф.двух сообщ. = 948;

VХафф.двух сообщ. = 993;

0,5775

1,0000




3055

1495 1495

0,4225

2720
1

0

1 0


Y1

1560

1225

0696



  1. 0

1 0


Y2

Y4


0529

0780

0780

1 0


Y3

Y7

Y9

Y8

Y5

0420

0276

0144
1 0


0276



  1. 0


Y6


1 0

Похожие:

Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconКритерии помех для защиты фиксированной службы от изменяющихся во времени совокупных помех со стороны других служб радиосвязи, совместно использующих частоты в полосе 17,7–19,3 ггц на равной первичной основе
В настоящей Рекомендации определяются критерии помех, необходимые для защиты фиксированной службы от изменяющихся во времени совокупных...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» icon«Математические методы», «Численные методы» студент Седых К. Г. Тьютор: Пантюхина Н. В. Москва
Пво противника. Атакам подвергается только постановщик помех. Поток атак — пуассоновский, с интенсивностью λ (атак/час). В результате...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconПередатчик помех с артилерийскими носителями
Передатчик помех р-032st доставляеться до цели при помощи следующих артилерийских систем
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconАнализ помехоустойчивости цифровых схем с учетом логических ограничений
Это приводит к резкому возрастанию помех (паразитных сигналов), индуцируемых в проводниках другими (соседними) проводниками. Эта...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconОбщие вопросы оптимальной оценки параметров сигналов при наличии помех
Вопросы оптимальных оценок параметров сигналов на фоне аддитивных помех типа белого нормального шума впервые (1946 г.) были поставлены...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconЛекции 8 10. Достаточно общая теория управления (в кратком изложении 1 )
Балансировочные режимы и манёвры. Понятие о теориях подобия. «Информационная безопасность» — устойчивость управления под воздействием...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconАнализ помех, влияющих на задержку, с помощью графа парных ограничений
В современной практике разработки сбис указанные факторы учитываются с использованием новейших методов статического временного анализа...
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconПодгруппа: Адаптеры/разъемы Тип: "банан"
Хромированные металлические разъемы с внутренним металлическим корпусом для максимальной защиты от радиоактивных помех
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconИсследование элементов и систем зенитных ракетных комплексов средней дальности
Исходные данные для курсовой работы: Система защиты от активных помех когерентно-импульсной рлс
Передача, хранение информации по каналу без помех. Часто на практике уровень помех, действующих в к с., достаточно мал, или конструктивные методы защиты от помех «достаточно высоки» iconИзмерения уровней создаваемых помех

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org