WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные материалы
 

«Конспект лекций по Теории информции В.Н. Горбачев† Лаборатория квантовой информации, СПб университет аэрокосмического приборостроения, С-Пб, 190000, ...»

Конспект лекций

по

Теории информции

В.Н. Горбачев†

Лаборатория квантовой информации, СПб университет аэрокосмического приборостроения, С-Пб, 190000, Большая Морская, 67. тел: (+7 812) 110-6234, факс: (+7 812) 315-7778.

† Северо-Западный институт СПб университета технологии и дизайна, С-Пб, 191180, Джамбула, 13, тел: (+7 812) 764-6556,

факс: (+7 812) 764-6556

Содержание

1 Случайные величины. 5

1.1 Вероятность. Частотное определение................................. 5

1.2 Сложение и умножение событий................................... 5

1.3 Условные вероятности......................................... 6

1.4 Закон больших чисел.......................................... 7

1.5 Вероятностное пространство...................................... 8

1.6 Случайная величина.......................................... 9

1.7 Вероятностная мера........................................... 9

1.8 Функция распределения........................................ 10

1.9 Представление случайной величины................................. 11

1.10 Моменты случайной величины.................................... 11



1.11 Совместные случайные величины................................... 12

1.12 Условные вероятности......................................... 13

1.13 Случайные проце

–  –  –

Введение Информация играет важную роль в нашей жизни. Однако, наряду с осознанием ее роли, полезно иметь элементарные представления о том, что такое информация. Такие представления могут быть почерпнуты из многочисленной литературы, которую можно разделить на два класса. Первый, написанный профессионалами, как правило, сильно математизирован из-за погони к общности, поэтому материал оказывается доступным лишь для самих авторов и узкого круга специалистов. Напротив, в текстах второго класса, широко представленных в Сети интернет, из-за стремления к популярности страдает точность обсуждаемых понятий. Среди всей литературы непревзойденной остается книга К. Шеннона, основоположника теории информации, "Работы по теории информации и кибернетике".

Настоящий конспект лекций представляют собой спецкурс, который читается с 2001 г. студентам специальности 220200 ("Автоматические системы переработки информации и управления") в Северо-Западном институте печати С-Петербургского государственного университета технологии и дизайна. Основное внимание уделено разъяснению сути дела наряду со строгим изложением, однако строгость не является самоцелью. В шести представленных разделах рассмотрены основные фундаментальные понятия и методы классической теории информации такие, как: энтропия и мера информации, энтропия источника дискретных сообщений, кодирование и сжатие информации, пропускная способность дискретных каналов и корректирующие коды. Изложение начинается с обсуждения случайной величины, она составляет основу теории вероятностей, которая необходима для понимания методов теории информации. Знакомство со специальным разделам математики и теории вероятностей не требуется, поскольку все нужные сведения вводятся по мере изложения, хотя знание курса высшей математики в объеме вуза необходимы.

Работа выполнена при поддержке Delzell Foundation, Inc.

1 Случайные величины.

1.1 Вероятность. Частотное определение Будет использоваться следующая терминология: опыт, исходы опыта и события. Опыт имеет исходы, которые являются элементарными событиями. Из исходов строятся более сложные события. Исход опыта достоверно предсказать нельзя.

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

Исходам можно сопоставить числа x = x1,..., xN, каждое из которых случается с вероятностью p(x) =

p(x1 ),..., p(xN ), тогда возникает случайная величина X:

X = {x; p(x); |X|}, (1)

где |X| = N – число исходов. Аналогично события 1 A = A1... AM представляются своей вероятностью p(A) = p(A1 ),..., p(AM ): A = {A; p(A)}.

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

Пример. Пусть в урне находятся 10 шаров красных, зеленых и голубых R,G и B. Из них 5 шаров R, 3 шара G и 2 шара B. Их вытаскивают не глядя. Какова вероятность того, что вынутый шар будет того или иного цвета?

Решение. Опыт имеет 10 исходов. Ясно, что есть 5 шансов из 10 вынуть шар R и т. п. Поэтому вероятность вынуть R, G и B шары соответственно равны 5/10 = 1/2, 3/10, 2/10 = 1/5.

В данном случае рассматривается вероятность события AR,G,B : "Вынули шар R,G,B ". Если много раз повторять этот опыт: вытащили шар, положили обратно, все тщательно перемешали, чтобы воспроизвести исходные условия, то можно убедиться в справедливости найденных вероятностей.

Пример. Какова вероятность того, что брошенная монетка выпадает "орлом"?

Решение. Задача эквивалентна предыдущей, где в урне лежат только два шара R и G. Вероятность равна 1/2.

Пример. Какова вероятность того, что при бросании кубика выпадет номер грани, который делится на 3?

Решение. Пусть в урне лежат шары с номерами 1, 2, 3, 4, 5, 6. Пусть два шара 3 и 6 закрашены красной краской, а остальные нет. Тогда вероятность равна 2/6 = 1/3.

В этом случае опыт имеет 6 исходов, а событие AR состоит в том, что вытащили либо шар с номером 3, либо 6, какой неважно, важно, что есть 2 шанса из 6.

В рассмотренных примерах опыт имеет N исходов, которые равновероятны, поэтому вероятность каждого исхода равна 1/N. Если интересующий исход или событие происходит m раз, то его вероятность, а точнее частота, равна p = m/N. Для кубика с 6 гранями возникает случайная величина X, которая принимает 6 значений x = 1,... 6, с вероятностью p = 1/6. Среднее значение случайной величины определяется соотношением x = E{X} = xk p(xk ). (2) k

1.2 Сложение и умножение событий События представляют собой множество исходов, поэтому над ними, как над множествами, можно совершать операции объединение и пересечение, что соответствует сложению и умножению событий. События бывают достоверные и невозможные, взаимоисключающие или дополнительные, совместные и несовместные. Вероятность события есть неотрицательное число: 0 p(A) 1.

Если p(A) = 1, то событие A называют достоверным. Оно возникает при любом исходе опыта. Так, если в урне лежат только шары R, то вероятность вынуть R шар равна единице. Если p(A) = 0, то событие A невозможное.

Два события A и B взаимоисключающие, если p(A) + p(B) = 1. (3) 1 Ниже будут даны строгие определения на основе вероятностного пространства.

Если событие A реализуется в m из N исходах, то взаимоисключающее событие B = A возникает в N m исходах. Говорят, что B является дополнением множества A.

Пример. Пусть в урне всего 5 шаров, из них 2 шара R и 3 шара G. События A: "извлечен R шар"и событие B = A "извлечен G шар"являются взаимоисключающими, p(A) = 2/5, p(B) = 3/5 = 1 p(A).

События совместные, если могут произойти одновременно. Это означает, что пересечение множеств A и B не пустое. Если A и B не могут произойти вместе, то они несовместные. Соответственно множества A и B не пересекаются.

Суммой двух событий A и B называют событие A + B, которое состоит в том, что случилось событие A или B или случились оба сразу. Сумме событий A + B соответствует операция объединения двух множеств. Для нахождения вероятности суммы событий нужно различать два случая: 1) события A и B несовместные, 2) события A и B совместные. Для несовместных событий p(A + B) = p(A) + p(B). (4) Если A и B события совместные, это означает, что иногда они происходят вместе. Тогда p(A + B) = p(A) + p(B) p(AB), (5) где произведение событий AB означает событие, в котором A и B возникают вместе. Формулу можно пояснить, используя частотное представление вероятности. Пусть q раз из N происходят оба события AB, пусть A случилось в mA q случаев из N, аB в mB q случаях из N. Тогда A + B случается в (mA q) + (MB q) + q раз из N, или mA + mB q раз.





Пример. В урне находится 6 шаров, из них 2 шара R, 3 шара G и 1 шар B. Рассмотрим событие AX "извлекли X = R, G, B шар". События AR, AG, AB неcовместные и взаимоисключающие, поэтому p(AR ) + p(AG ) + p(AB ) = 2/6 + 3/6 + 1/6 = 1. Попарные события типа AR, AG несовместные, но не являются взаимоисключающими, поэтому p(AR ) + p(AG ) = 2/6 + 3/6.

Если события A и B независимы, то p(AB) = p(A)p(B). (6) Независимость событий означает, что исходы одного не влияют на исходы другого.

Пример. В колоде 52 карты. Одна из четырех мастей козырная, пусть "крести". Какова вероятность того, что взятая наугад карта будет: 1) тузом, 2) козырем, 3) козырным тузом?

Решение. Пусть событие A "выбранная карта – туз". Тогда p(A) = 4/52 = 1/13. Пусть событие B "выбранная карта – козырь". Тогда p(B) = 1/4. В этом случае произведение AB означает, что выбранная карта козырной туз, сумма A + B означает, что выбранная карта либо туз, либо козырь. Поэтому p(AB) = p(A)p(B) = 1/52, p(A + B) = p(A) + p(B) p(AB) = 4/13.

Если X и Y две случайные величины, то всегда x + y = x + y, если они независимы, то xy = x y.

1.3 Условные вероятности Если события A и B независимы, то исходы опыта, в которых случается A, не влияют на исходы, в которых случается B. Однако это может быть не так.

Например, пусть в урне находится M шаров, из них m шаров R и M m шаров G. Пусть событие A заключается в том, что извлечен R шар. Пусть событие B заключается в том, что извлечен R шар из той же урны после того, как из нее вынут один любой шар. В данном случае вероятность B будет зависеть от A.

Если первый вынутый шар был R, случилось A, то R шаров стало m 1. Тогда вероятность события B равна (m 1)/(M 1). Если первый вынули шар G, то произошло событие A, и вероятность B равна m/(M 1). Непосредственно видно, что вероятность события B меняется в зависимости от того, случилось A или нет.

Вероятность события B при условии, что произошло A, называется условной вероятностью и обозначается p(B|A). В рассмотренном примере p(B|A) = (m1)/(M 1) m/M = p(B), p(B|A) = m/(M 1) m/M = p(B).

Для условных вероятностей справедливо выражение p(A, B) = p(B|A)p(A) = p(A|B)p(B). (7) Эту формулу можно пояснить, используя частотное определение вероятности. Так, можно считать, что p(B|A) = /µ, (8) где событие B случается раз из µ, а µ число исходов, в которых случается событие A и может случиться или нет событие B. В рассмотренном опыте по извлечению двух шаров из урны, где общее число шаров M, полное число исходов равно K = M (M 1): сначала можно вынуть любой из M шаров, потом один из M 1 оставшихся.

Число исходов, в которых случается A и может произойти B, равно µ = m(M 1):

вынули один из m шаров R и любой оставшийся. Однако событие B могло не случиться. Число исходов, в которых происходит еще и событие B, равно = m(m1): вынули сначала один шар R из m шаров, затем один шар R из оставшихся m 1 шаров. Условная вероятность будет p(B|A) = /µ = (m 1)/(M 1).

Справедливо следующее тождество K =, (9) µ Kµ где /K = m(m 1)/M (M 1) = p(A, B) число исходов, в которых происходят оба события A и B, µ/K = m/(M 1) = p(A) число исходов, в которых происходит событие A. В результате выражение (9) принимает вид (7).

Для условных вероятностей справедливы следующие свойства

–  –  –

1.4 Закон больших чисел Рассмотрим случайную величину X = {x1... xN, p(x1 )... p(xN )} со средним значением E{X} = m. Ее дисперсия, которая характеризует среднее отклонение от среднего, определяется соотношением

–  –  –

где 0. Оно означает, что вероятность отклонения случайной величины X от своего среднего значения m зависит от дисперсии и величины самого отклонения. Если в качестве случайной величины X в (13) взять Z, определенную (12), то неравенство Чебышева принимает вид P (|Z m| ). (13) n2 Отсюда следует, что для любого 0 всегда можно выбрать число n настолько большим, чтобы гарантировать маленькое отклонение от среднего. Это утверждение известно, как закон больших чисел, который устанавливает общий характер поведение случайной величины. Так, сумма большого числа случайных величин в отличие от одной случайной величины с большой вероятностью принимает значения близкие к своему среднему значению, а большие отклонения от среднего. Одно из практических применений закона больших чисел на практике состоит в том, что по сравнительно небольшой пробе судят о качестве однородного материала, например, как при дегустации.

Еще вариант неравенства Чебышева. Пусть случайная величина X принимает только положительные значения x 0, тогда

–  –  –

1.5 Вероятностное пространство Для описания случайной величины служит вероятностное пространство (, A, P ), которое состоит из пространства элементарных исходов или элементарных событий, поля событий или алгебры A и вероятностной меры P.

Рассмотрим эксперимент, исходы которого нельзя предсказать достоверно. Пусть любой из исходов.

Пространство элементарных событий есть множество всех элементарных исходов = {}. Число элементарных исходов может быть конечным, счетным или бесконечным. Если в урне имеется M шаров, то эксперимент по вытаскиванию шаров имеет M исходов.

Элемент вероятностного пространства A называется полем, или алгеброй событий. Алгебра A состоит из множества событий A, которые в свою очередь составлены из элементарных исходов. Говорят, что событие происходит, если элементарный исход A. Алгебра A = {A : A } обладает следующими свойствами.

1. Достоверное событие принадлежит A. Действительно, если выполнен эксперимент, то он завершиться одним из исходов A. (15)

2. Невозможное событие или пустое множество содержится в A. Действительно, если выполнен эксперимент, то он может не завершиться ни одним из интересующих исходов

–  –  –

Любое множество A подмножеств пространства, удовлетворяющее (15) - (18), называется алгеброй или полем.

Множество всех событий A меньше или равно множеству всех подмножеств пространства элементарных событий, которое называют булиан P(). Если пространство конечно и содержит, например, M элементов, то |P()| = 2M и число элементов A не больше 2M.

Пример. Пусть пространство исходов содержит M = 3 элемента = {a, b, c}. Тогда множество всех возможных подмножеств будет состоять из четырех множеств, которые содержат 0 элементов, 1 элемент, 2 элемента и 3 соответственно: 0 = {}, 1 = {a, b, c}, 2 = {ab, ac, bc, } и 3 = {abc}. В итоге 1+3+3+1 = 23 = 8.

Результат, согласно которому число всех подмножеств, составленных из M элементов, равно 2M, легко понять из следующих соображений. Пусть каждому исходу 1, 2... M сопоставлено число, которое принимает два значения 0 и 1: bk = 0, 1, k = 1,... M. Тогда все исходы можно представить строкой b1 b2... bM длины M, составленной из 0 и 1. Так будет строка 11... 0, где первые две цифры 1, а остальные 0. Эта строка описывает множество, состоящее из двух элементов {1, 2 }. Всего будет 2M различных строк или различных множеств, составленных из элементов. Число множеств n(K), состоящих из K элементов, N будет равно числу различных строк, содержащих K единиц: n(K) = M !/K!(M K)! = CK. В частности при M = 3, найдем, что для K = 2 число n(2) = 3, для K = 3 число n(3) = 1.

1.6 Случайная величина Случайная величина X представляет собой функцию, которая отображает пространство элементарных исходов в пространство состояний, в качестве которого выбирают множество вещественных чисел X :

R.

Функция X будет случайной величиной, если она обладает следующим свойством

A = { : X() x} A x R. (19)

Это условие означает, что X будет случайной величиной только в том случае, если множество A, состоящее из элементарных исходов, для которых функция X() ограничена, будет событием. Из условия ограниченности функции X() (; x] следует, что элементарному исходу ставится в соответствие интервал (, x] на вещественной оси. Если ввести обратную функцию X 1, то

A = X 1 ((, x]) A x R. (20)

Функция X преобразует исходы из пространства элементарных событий в пространство состояний (, x] R. Ее можно интерпретировать, как некоторую процедуру измерения, которая позволяет получить информацию об основном пространстве элементарных исходов с помощью прибора, осуществляющего преобразование X : R. Тогда пространство R можно принять за новое пространство элементарных событий величины X. События в R определяются интервалами (, x]. 2 Разумно потребовать, чтобы любое событие X в пространстве R соответствовало событию в основном пространстве. В противном случае измерительный прибор будет давать ложную информацию. Но в самом общем случае не всякое событие A A представимо в виде A = X 1 (, x]. Поэтому поле, порожденное всеми множествами вида A(X) = {X 1 ((, x]), x R}, является лишь подполем поля событий A.

Является ли X случайной величиной, определяется выбором поля событий. Рассмотрим пример. Пусть в сосуде находится M газовых молекул. Пусть пространство составлено из этих молекул и, следовательно, содержит M элементарных исходов. Пусть в качестве функции X выбрана скорость: X = V. Это означает, что молекуле сопоставляется скорость. Является ли скорость случайной величиной? Иными словами, будет ли A = { : V () v} событием: A A, x R? Рассмотрим два случая выбора A: 1) A = P(), где P() множество всевозможных подмножеств молекул, 2) A = {,, A+, A }, где A± количество молекул, скорость которых направлена по или против некоторой оси. Число молекул A, скорость которых меньше заданного значения A = { : V () u}, не совпадает ни с одним из элементов,, A+, A. Поэтому во втором случае скорость не является случайной величиной.

1.7 Вероятностная мера В вероятностном пространстве {, A, P } элемент P представляет собой вероятностную меру. Функция P осуществляет отображение P : A [0, 1], которое сопоставляет событию A A число на интервале [0, 1], называемое вероятностью. Можно заметить, что функция P определена на поле A, а не на пространстве исходов. Поэтому вероятность определена для событий, а не только для элементарных исходов. Эта особенность будет существенной для бесконечного множества исходов, когда вероятность элементарного 2 В общем случае можно взять интервалы B = [x, y]. Если над ними производить теоретико - множественные операции пересечения, объединения и дополнения, то они порождают поле B, известное как борелевское поле. Чтобы породить борелевское поле, достаточно использовать интервалы (, x].

события часто строго равна нулю.

По определению любая функция P является вероятностной мерой, если обладает следующими свойствами

–  –  –

Эти свойства отражают наши интуитивные представления о вероятности. Так, невозможное событие имеет нулевую вероятность, вероятность достоверного события равна единице, а вероятности двух взаимно исключающих события (непересекающихся) складываются. Последнее условие сохраняется для счетного числа взаимно исключающих событий.

В приложениях вероятность может выводиться из длинной серии испытаний, где определяется относительная частота события. Но в таком подходе есть математические тонкости. Задача теории вероятностей состоит не в определении вероятностной меры, а в вычислении новых вероятностей по заданным.

Вероятность событий в пространстве состояний R случайной величины X можно выразить через P. Действительно, случайная величина X : R осуществляет перенос вероятностной меры P из пространства элементарных событий в R, где элементарным событием является интервал (; x]. Поскольку P () = p [0, 1] то событию X() x можно приписать вероятность p. Иными словами, можно ввести вероятность P (X x), c которой случайная величина X попадает в интервал (; x]. В результате вероятностная мера будет определена уже на пространстве состояний.

–  –  –

где p(x) – плотность вероятности, а p(x)dx – вероятность найти значение X в интервале x ± dx. Условие F () = 1 означает, что площадь под кривой p(x) равна 1.

Для случая дискретной величины

–  –  –

Откуда видно, что P (X = x0 ) = 0. Иными словами, случайная величина не может принимать какое-либо определенное значение.

1.9 Представление случайной величины В пространстве состояний R случайная величина X полностью описывается своей функцией распределения F (x) = P (X x). Поэтому вероятностное пространство {, A, P } можно опустить, считая что X задана функцией распределения, для кототой существует плотность вероятности. Далее будем представлять X в виде <

–  –  –

где X – название случайной величины, x – значения, которые она принимает. Для дискретных величин p(x) – вероятность, с которой случается значение x, для непрерывных величин p(x) – плотность вероятности. Через |X| обозначена мощность множества X.

–  –  –

Моментами случайной величины X называются средние вида E{X q }. В то время как нулевой момент существует всегда 1 = P (), высшие моменты могут обращаться в бесконечность.

Мерой флуктуаций служит дисперсия, которая описывает среднее отклонение случайной величины от среднего значения. Она определяется соотношением 2 = E{(X E{X})2 } = x2 x 2. (30) Дисперсия является вторым центральным моментом, в общем случае центральные моменты определены соотношением Mq = E{(X E{X})q }. (31) Если дисперсия характеризует ширину плотности вероятности, то третий центральный момент описывает асимметрию или "перекос". Для симметричной относительно среднего значения функции E{(X E{X})2q+1 } = 0, q = 1, 2...

Три примера.

1) Гауссовское распределение. Плотность распределения имеет вид

–  –  –

где m – среднее значение, 2 – дисперсия. Распределение описывается полностью двумя первыми моментами m и 2 и симметрично относительно среднего значения. Для центральных моментов

–  –  –

Величины X и Y могут быть независимыми, тогда p(x, y) = p(x)p(y) и E{XY } = E{X}E{Y }. В противном случае это не так. Чтобы характеризовать связь X и Y вводится ковариация xy = E{(X mX )(Y mY )} = E{XY } E{X}E{Y }.

Если xy = 0, то говорят, что X и Y нескоррелированы.

3 Если слагаемые вносят равномерно малый вклад в сумму.

1.12 Условные вероятности Задача об определении вероятности события B, если произошло событие A, приводит к условной вероятности P (B|A). Если события A и B совместны, условная вероятность определяется соотношением

–  –  –

где p(x|y) и p(y|x) – условные вероятности, которые равны вероятности найти x либо y, если случилось значение y либо x.

Для условной вероятности справедливы следующие свойства. Используя определения, найдем p(x) = y p(x, y) = y p(y|x)p(x). Отсюда

–  –  –

1.13 Случайные процессы Если случайная величина X меняется со временем, то возникает случайный процесс. Чтобы отличать его от детерминированной функции X(t), вводится обозначение Xt. В результате отображение R будет разным для разных моментов времени t. Поэтому случайный процесс можно рассматривать как функцию Xt () двух аргументов параметра t и элементарного события. Если зафиксировать время t, и разрешить принимать все свои значения, то будет случайная величина. Если фиксировать, выбрав некоторое элементарное событие, и отпустить время, то будет реализация случайного процесса.

Пример.

–  –  –

2 Энтропия и информация

2.1 Представление информации Информация – это сведения о каких-либо событиях.

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

Информацию, фиксированную в определенной форме, называют сообщением. Сообщение может иметь разное содержание. Однако, как правило, оно состоит из последовательности символов, которые рассматривают как буквы некоторого алфавита. Алфавит может содержать любое количество букв или символов, например, x1, x2... xN. В русском языке N = 32 (приравнивают ъ и ь, е и ё, тогда 33 2 + пробел = 32 = 25 ), в алфавите с N = 2 есть две буквы, которые обозначают символами 0 и 1.

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

Наши интуитивные представления об информации отчасти связаны с двумя свойствами: различимость и неопределенность. Если буквы хорошо различаются, то текст можно прочитать. Сколько информации содержится в сообщении "дважды два четыре"? Ответ зависит от того, знаем ли мы таблицу умножения.

Поэтому говорят, что информация есть мера нашего незнания. Математически "незнание"можно описать случайной величиной, значения которой можно только предсказать с некоторой вероятностью.

В стандартной схеме источник информации или отправитель A посылает сообщение в канал, на выходе которого находится получатель B. В теории информации одним из главных является вопрос: сколько информации A должен отправить в канал, чтобы B восстановил исходное сообщение. Реальный канал обладает шумами, что является источником ошибок, поэтому задача усложняется. В действительности возможен еще один персонаж E, злоумышленник, который прослушивает канал. Поэтому возникает задача, как защитить информацию или как обеспечить конфиденциальность передаваемых сведений. Чтобы сохранить секрет, криптография рекомендует зашифровать сообщение. Однако существует ли надежный шифр? Эти и другие задачи рассмотрены в классической теории информации Шеннона, где центральным является вопрос измерения количества информации.

2.2 Энтропия Энтропия служит мерой неопределенности или информации.

Неопределенность можно связать с вероятностью: чем вероятность события выше, тем меньше его неопределенность. Пусть событие A заключается в том, чтобы определить цвет первой попавшейся вороны. Поскольку все вороны в основном черные, энтропия A будет мала, равно как и количество информации.

Есть и белые вороны, но они встречаются редко.

Количество энтропии или информации, которая содержится в случайной величине

–  –  –

Если основание логарифма b = 2, то энтропия измеряется в битах, иногда используют натуральный логарифм. С помощью формулы logb Z = loga Z logb a можно перейти от одного основания к другому.

Наряду со случайной величиной X энтропию можно определить для элементарных исходов опыта или отдельных значений hk = log p(xk ). Тогда из определения (45) может показаться, что с точки зрения случайных величин энтропия H(X) представляет собой среднее значение E{h(xk )}. Однако такая интерпретация небезопасна. С физической точки зрения это означает введение динамической переменной для энтропии или наблюдаемой в классической или квантовой механике, например, H = log, где – оператор плотности. Если эволюция описывается унитарным оператором U, то (t) = U (t)U † (t) и среднее значение рассматриваемого оператора энтропии H меняется: Sp{H(t)} = H(t). Однако известно, что при унитарной эволюции, описывающей обратимый процесс, энтропия сохраняется.

Рассмотрим кубик. Если он идеальный, то при бросании вероятность того, что выпадет любая грань равна 1/6. В данном случае имеет место случайная величина X, которая принимает N = 6 значений с вероятностью p(xk ) = 1/6. Количество информации, которое в ней содержится, будет H = log 6 2.58 бита.

Пусть кубик неидеальный, и пусть вероятности p(xk ) = 1/10, k = 1, 2, 3, 4, 5, а вероятность p(x6 ) = 1/2.

Для такого неравномерного распределения H = 2, 15 бит, что меньше чем maxH = 2, 58 бит.

2.3 Функция энтропии Случайная величина X называется бинарной, если она принимает два значения. Эти значения можно обозначить 0 и 1. Пусть 0 и 1 случаются с вероятностью p(0) = q и p(1) = p, где q + p = 1. Для бинарной величины энтропия, определенная согласно (45), будет зависеть только от p:

H(X) H(p) = p log p (1 p) log(1 p). (49)

Функция H(p) определена лишь на промежутке [0, 1], где для значений p = 0 и p = 1 она обращается в ноль. При p = 1/2, когда оба значения случайной переменной равновероятны, функция имеет максимум, где H(1/2) = 1. Энтропия бинарной величины H(P ) имеет важное значение.

Бинарная переменная с равновероятными значениями называется бит. В такой величине содержится H(1/2) = 1 бит информации, что и принимают за единицу ее измерения. Другими словами, с помощью бинарной переменной можно закодировать или сохранить 1 бит.

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

Разумеется, состояния должны быть устойчивыми или по крайней мере не распадаться за время вычислений. Можно указать следующие примеры. Электрический импульс, где одно состояние – напряжение равное нулю, другое – напряжение, скажем, +5В. Можно и наоборот. Монета, два состояния которой "орел"и "решетка". Электрическая лампочка, где горящая лампочка кодирует 1, а выключенная – 0. Фотон, квант света, у которого есть две поляризации или направления, вдоль которых смотрит вектор электрического поля, к примеру, это горизонтально и вертикально поляризованный фотон.

Следует иметь в виду, что в бинарной переменной количество информации может быть меньше одного бита, если ее значения не равновероятны. Если распределение случайной величины неравномерное, то в ней содержится меньше 1 бита информации. Это согласуется с интуитивным представлением об информации как мере нашего незнания. Вместе с тем неравномерность связана с избыточностью информации.

Последнее обстоятельство играет важную роль, и связано, в частности, с возможностью сжатия данных.

Для измерения информации помимо бита используется байт – величина в 8 раз большая, чем бит. Байт обозначают заглавной буквой Б или B. Используются производные от этих единиц, образованные при помощи приставок кило (К), мега (М), гига (Г или G), тера (Т) и др. Но для битов и байтов они означают не степени 10, а степени 2. Так кило – 210 = 1024 103, мега – 220 106, гига – 230 109, тера – 240 1012. Например, 1 MБ = 1024 КБ = 1048576 Б = 8192 Кбит.

2.4 Взаимная и условная энтропия Рассмотрим две случайные величины X = {x, p(x)}, Y = {y, p(y)}, где для краткости обозначено x = x1..., xN, p(x) = p(x1 )..., p(xN ) и т. п. Для их описания служит совместная вероятность p(x, y), которую можно представить в виде произведения условных и безусловных вероятностей

–  –  –

где, например, p(x|y) вероятность случиться величине x, при условии, что случилось фиксированное значение y. Тогда можно ввести следующий набор функций энтропии

–  –  –

Величина H(X, Y ) описывает энтропию или информацию, которая содержится в X и Y, условная энтропия H(X|Y ) характеризует количество информации в X, если известно Y, взаимная энтропия I(X : Y ) показывает сколько информации X и Y содержат друг о друге.

Эти величины имеют простой "геометрический смысл который следует, непосредственно из определений.

Так, энтропия двух случайных величин H(X, Y ) соответствует объединению двух множеств X Y, где каждый элемент из множества X и Y учитывают только один раз. H(X|Y ) отвечает дополнению Y множества Y до X и состоит из тех элементов x, которых нет у Y. Наконец условная энтропия H(X|Y ) = H(Y |X) аналогична операции пересечения двух множеств X Y.

С помощью определений можно записать следующие соотношения H(X, Y ) = H(X) + H(Y ) H(X|Y ), (54) H(X|Y ) = H(X) I(X : Y ), (55) H(X, Y ) = H(X) + H(Y |X), (56) H(X, Y ) = H(Y ) + H(X|Y ). (57) Взаимная энтропия H(X : Y ) характеризует корреляцию двух случайных величин, которая описывается отношением p(x, y)/p(x)p(y). Если x и y независимы, то p(x, y) = p(x)p(y), поэтому взаимная энтропия H(X : Y ) = 0 и H(X|Y ) = H(X), а общая энтропия равна сумме: H(X, Y ) = H(X) + H(Y ).

Пример. Пусть в урне содержится m черных и n m белых шаров. Пусть эксперимент A и B заключается в последовательном извлечении шаров: A – "вынули любой первый шар B – "вынули любой второй шар". Вынутые шары обратно не возвращаются. Найти энтропию экспериментов A, B и условные энтропии.

Решение. Пусть исходы экспериментов A и B описываются случайными величинами X и Y, принимающие каждая два значения x = x1, x2 и y = y1, y2. Пусть значения x = x1 и y = y1 описывают исходы экспериментов A и B, в которых вытащен черный шар, а значения x = x2 и y = y2 – исходы, в которых вытащен белый шар. Чтобы вычислить энтропии, нужно найти набор условных и безусловных вероятностей для X и Y. Безусловные вероятности p(x) и p(y) описывают два одинаковых события: "вынули черный шар если x = x1, y = y1 или "вынули белый шар если x = x2, y = y2. Поскольку всего шаров n, то p(x1 ) = p(y1 ) = m/n, и p(x2 ) = p(y2 ) = (n m)/n. Если в эксперименте A получен определенный исход, или у величины X случилось значение x = x1, то исходы эксперимента B или значения величины Y будут описываться условной вероятностью p(y|x).

Значения вероятностей приведены в следующей таблице:

p(y|x) p(x) p(y) x1, y1 (m 1)/(n 1) p p x1, y2 (n m)/(n 1) p 1p x2, y1 m/(n 1) 1p p x2, y2 (n m 1)/(n 1) 1p 1p Отсюда следует, что обе случайные величины имеют одинаковую энтропию H(X) = H(Y ) = H(p), где p = m/n, где функция энтропии H(p) определена согласно (49). Воспользовавшись соотношением p(x, y) = p(y|x)p(x) можно найти безусловную вероятность p(x, y) и условную вероятность p(x|y) = p(x, y)/p(y), которые необходимы для вычисления энтропии H(X, Y ), H(X|Y ), I(X : Y ) и H(Y |X).

Пример. Пусть эксперимент B заключается в определении положения точки Q, относительно которой известно заранее, что она лежит на отрезке CD длиной L. Пусть эксперимент A заключается в измерении длины отрезка CM с помощью линейки, дающей ошибку. Чему равна информация I(A : B), содержащаяся в результате измерения положения точки Q.

Решение. В данном случае оба эксперимента могут иметь бесконечное число исходов, поскольку, например, положение точки Q может совпадать с любой точкой отрезка CD. Чтобы обойти эту трудность, можно считать, что длины L и соизмеримы. Это означает, что можно выбрать маленький отрезок, квант длины, такой что он целиком уложится на L и, при этом оба отношения L/ и / будут целыми числами. Тогда положение Q будет определяться с точностью. Поскольку заранее известно, что точка Q расположена где-то на отрезке CD, то эксперимент B имеет L/ равновероятных исходов с вероятностью p = /L. Поэтому энтропия равна H(B) = log l/. После того, как проведен эксперимент A, где измеряют длину CQ, установлено, что точка Q может находиться в окрестности CQ ±. Эта окрестность имеет размер 2, поэтому эксперимент A имеет 2/ исходов с вероятностью /2. Тогда условная энтропия H(B|A) = log( /2), а количество информации, полученной в результате измерения равно L I(A : B) = H(B) H(B|A) = log.

Отсюда следует, что количество информации не зависит от, поэтому приведенный вывод будет справедлив в общем случае. Количество информации определяется отношением L/2, которое будет возрастать с уменьшением, т. е. с увеличение точности измерения.

2.5 Иерархическая аддитивность Свойство иерархической аддитивности. Пусть X1,... Xn, случайные величины, тогда

–  –  –

Здесь энтропия H(Xn |X1, X2,... Xn1 ) определяется условной вероятностью p(xn |x1, x2... xn1 ), которая показывает вероятность значения xn, если случились значения x1, x2... xn1. Соотношение (58) вытекает из свойства условной вероятности

–  –  –

2.6 Энтропийные свойства секретных систем Использование введенного понятия энтропии для анализа секретных систем позволяет установить свойства совершенной секретности.

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

–  –  –

где M – множество сообщений, D – множество криптограмм, K – множество ключей. Ключ k, который используется с вероятностью p(k), определяет процесс шифрования Ek : m d и расшифрования Dk : d m, где Dk Ek = 1, чтобы прочитать сообщение. Поскольку для шифрования и расшифрования используется один ключ, то секретная система называется симметричной 4. Важным свойством секретной системы является ее стойкость против атак противника.

При математической оценке стойкости считают, что противник имеет неограниченные вычислительные ресурсы и неограничен во времени. В результате атаки противник может перехватить сообщение или криптограмму, вычислить вероятности p(m|d), p(d|m) и определить H(M |D) и H(D|M ).

Справедливо следующее определение (Шеннон 1949). Система называется совершенно секретной, если

H(M |D) = H(M ). (61)

Это условие означает, что неопределенность или информация о сообщении не изменяется, если известна криптограмма. Другими словами, перехваченная криптограмма не добавляет никаких новых сведений о сообщении. Из (61) следует, что M и D независимы, поэтому для совершенно секретных систем

–  –  –

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

Используя свойство иерархической аддитивности (58), можно получить связь между длиной ключа и длиной сообщения. Для безусловной энтропии H(D, M, K) следует выражение

–  –  –

где H(M |K, D) = 0, поскольку при фиксированном ключе и фиксированном сообщении само сообщение m = Dk d не является случайной величиной. Тогда, вычитая (64) и (63), найдем H(M |D) = H(K|D) H(K|M, D). (65) Поскольку H(K|D) H(K), а для совершенно секретных систем H(M |D) = H(M ), то (65) принимает вид H(M ) H(K). (66) Выражения для энтропии H(M ) и H(K) можно записать как произведение числа букв на энтропию одной буквы, тогда nM log NM nK log NK, (67) где nM, nK – длина сообщения и длина ключа, NM, NK – количество букв в алфавите сообщения и ключа.

Для бинарного алфавита NM = NK = 2, тогда nM nK. (68) Это условие означает, что для совершенно секретной системы длина ключа должна быть не меньше длины сообщения, а ключ должен представлять собой случайную последовательность из 0 и 1 и использоваться только один раз (Шеннон, 1949).

Примером совершенно секретной симметричной системы является шифр Вернама, известный как одноразовый блокнот (one time pad). В этой системе сообщение и ключ, который представлен случайной двоичной последовательностью, имеют одинаковые длины, а правило шифрования имеет вид d = m + k, где сложение осуществляется по mod 2. Например, m = 0100111, k = 0010110, тогда d = 0110001.

Можно ли взломать совершенно секретную систему? Ответ положительный. Для этого нужно угадать секретный ключ, который представляет собой двоичную строку пусть длиной n, взятую случайным образом из множества всевозможных последовательностей {0, 1}n. Общее число всех последовательностей равно C = 2n, вероятность угадать нужную последовательность p = 1/2n. При n 1 вероятность угадывания p 0, однако можно заняться перебором всех вариантов, число которых C. Поскольку C имеет экспоненциальную зависимость от n, то с точки зрения теории вычислений такая задача считается трудной или NP задачей. Решение NP задач требует больших вычислительных ресурсов. Поэтому при n 1 для решения задачи может потребоваться слишком много времени или неоправданное количество ресурсов.

2.7 Энтропия и термодинамика Понятие энтропии в термодинамику было введено Больцманом для описания физических систем. Согласно одной из формулировок II Начала термодинамики замкнутая система может развиваться только по пути увеличения энтропии. Это утверждение согласуется со свойством субаддитивности для энтропии двух систем:

H(X, Y ) H(X) + H(Y ). (69) В общем случае есть два подхода для описания эволюции: 1) метод открытых систем, 2) метод замкнутых систем. В первом есть две взаимодействующие системы A и E, где E - окружение, и рассматривается эволюция A. Во втором случае есть одна большая замкнутая система. Чтобы описать ее часть вводят грубый временной или пространственный масштаб, который позволяет записать замкнутые уравнения известные в физике как кинетические.

Рассмотрим две системы A и E, которые вначале были независимые. Для них H(A, E) = H(A) + H(E). (70) За счет взаимодействия, которое в самом общем случае описывается унитарным оператором U : U U † = 1, состояние систем изменяется: A A, E E. Из физики известно, что при унитарном преобразовании энтропия не изменяется, поэтому H(A, E) = H(A, E ). Кроме того из-за взаимодействия системы не будут независимыми, тогда H(A) + H(E) = H(A, E ) H(A ) + H(E ). (71) Это означает, что в результате эволюции энтропия всего мира может только увеличиваться.

3 Источник дискретных сообщений

3.1 Статистическая модель ИДС В качестве источника сообщений может выступать текст. В основе статистического описания источника сообщений лежит следующее свойство. Текст, составленный из букв, представляет собой случайный процесс, где буквы встречаются со своей вероятностью.

Пусть X = {x1,... xN } алфавит источника. Если он содержит конечное число букв 2 N, то говорят об источнике дискретных сообщений (ИДС). Помимо алфавита ИДС задается множеством сообщений M = {m; p(m), |M |}, (72) где каждое сообщение представляет последовательность из n символов m = s1... sn {x1... xN }n, а каждый символ sk = x1,..., xN, k = 1,... n.

Сообщение m описывается набором из n случайных величин s1,..., sn и характеризуется своей вероятностью p(m), которая определяется n – мерной вероятностью p(s1,..., sn ). Различают два типа ИДС: без памяти и с памятью. Для ИДС без памяти все символы независимы, поэтому p(s1,..., sn ) = p(s1 )p(s2 )... p(sn ). (73) Для ИДС с памятью это не так, поскольку в осмысленном языке между буквами есть связь. Так, сочетание "ий"встречается часто, а "иы"никогда.

В общем случае для многомерных вероятностей следует правило самосогласования

–  –  –

1. Неотрицательность. Энтропия H(M ) 0 и обращается в ноль для вырожденного распределения:

p(xq ) = 1, p(xk ) = 0, k = q.

2. Для алфавита ИДС с мощностью N максимальное значение

–  –  –

достигается при равномерном распределении символов p(xk ) = 1/N, k = 1... n. Для доказательства можно воспользоваться неравенством Йенсена: E{f (w)} f (E{w}), которое справедливо для любой случайной величины w и произвольной выпуклой вверх функции f (w). Полагая w = 1/p(x), f (w) = log w, где f = 1/(x2 ln 2) 0 выпуклая вверх функция, найдем, что E{f (w)} = H(p(x)), E{w} = N, f (E{w}) = log N.

3. Аддитивность. Если два символа s1 и s2 независимы, то совместная энтропия равна сумме энтропий

–  –  –

3.3 Асимптотические свойства стационарного ИДС Если буквы ИДС имеют неравномерное распределение, что характерно для осмысленного текста, то множество всех сообщений можно разделить на два подмножества, в одном из которых содержится высоковероятные сообщения, число которых определяется количеством информации, содержащимся в сообщении.

Это свойство является основой оптимального кодирования и сжатия информации.

Пусть алфавит ИДС без памяти состоит из двух букв 0 и 1. Пусть буквы случаются с вероятностями p(0) = q, p(1) = p, p + q = 1. Положим q p, это означает, что p 1/2. Противоположный случай p 1/2 получается простым переобозначением 0 1. Пусть рассматриваемый источник генерирует сообщение длиной n

–  –  –

Поскольку H(p) 1, то fn будет маленькой величиной, если n 1. Так, полагая p = 0.1 и n = 100, найдем, что доля сообщений, заслуживающих внимание, составляет 1016.

4 Кодирование дискретного источника

4.1 Кодирование и дихотомия Кодирование можно рассматривать как преобразование сообщений.

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

Кодирование необходимо для: 1) хранения информации, при этом осуществляется сжатие данных, 2) для передачи информации через канал связи, 3) для защиты информации путем шифрования. Интерес представляют оптимальные коды, которые экономят место и время, например, ячейки памяти и время передачи данных.

В общем случае преобразование кодирования имеет вид

m {x1... xN }n d {y1... yL }l, (98)

где каждому сообщению ИДС длиной n сопоставляется кодовое слово d, составленное из l букв нового алфавита y1... yL. Таким образом возникает множество кодовых слов или код D = {d; p(d), |D|}.

Часто используется двоичное кодирование, связанное с принципом дихотомии, который применяется для решения различных задач. Рассмотрим пример. Пусть нужно угадать некоторое число от 0 до N 1, если ответ на вопрос имеет только две формы "да"и "нет"Пусть N = 8. Согласно принципу дихотомии нужно разбить интервал пополам и выяснить в какой из половинок, [0; 3] или [4; 7], лежит неизвестное число.

Для этого можно задать вопрос "находится ли задуманное число в интервале [0; 3]?"Если оно лежит в [4; 7], то следует разделить интервал [4; 7] еще раз пополам и выяснить, лежит ли неизвестное число в [4; 5] или [6; 7]. И так далее. Пусть ответы "да"кодируются символом 0, а "нет"символом 1. Пусть было задумано число 5. Для него возникает последовательность 101, которая означает, что 5 [0; 3] – нет = 1, 5 [4; 7] – да = 0 и 5 = 4 – нет = 1 Последовательность 101 является двоичным представлением числа 5, а общее количество вопросов в среднем будет равно log N = log 8 = 3. В данном случае каждое из чисел кодируется своим двоичным представлением. Вместо чисел можно взять N различных сообщений и поставить им в соответствие двоичную последовательность длиной log N. Другими словами, любую последовательность из N символов можно закодировать с помощью log N бит.

4.2 Коды с фиксированной длиной Пусть все кодовые слова имеют одинаковую длину. Два примера. ASCII (American Standard Code for Information Interchange) – Американский стандартный код для обмена информацией) на каждый символ отводится байт (8 бит), что позволяет закодировать 28 = 256 символов. Но чтобы построить однозначное соответствие для всех букв из множества национальных алфавитов народов мира, требуется по крайней мере 16 бит на символ, что обеспечивает стандарт Unicode, где возникает возможность закодировать 216 = 65536 букв.

Из требования однозначности кодирования можно установить основные свойства кодов с фиксированной длиной. Для этого преобразование (98) запишем в виде

–  –  –

2. Поскольку максимальное значение энтропии ИДС max H(m) = n log N и кодера max H(d) = l log L, то количество информации в кодовом слове не меньше, чем в сообщении

–  –  –

4.3 Неравномерное кодирование. Префиксный код Пусть длина кодового слова будет разной для разных сообщений. Основу такого кодирования составляет неравномерность появления букв в ИДС. Поэтому часто повторяющиеся буквы можно кодировать короткими последовательностями, а редко повторяющиеся – более длинными. В среднем при большом количестве сообщений будет возникать экономия при равенстве информации в исходном тексте и коде.

При таком подходе методы кодирования оказываются неоднозначными, но среди них есть оптимальные.

Однако само понятие оптимальности требует уточнения.

Если рассматривать кодирование букв xk, k = 1,... N из алфавита ИДС, то при неравномерном кодировании длина кодового слова lk зависит от выбранной буквы:

–  –  –

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

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

Префиксом называют любую последовательность, составленную из начальной части кодового слова. Так, префиксом слова q1... qr... ql является q1... qr, где r l.

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

Какой длины могут быть кодовые слова для однозначного декодирования? Например, префиксного двоичного кода из трех кодовых слов с длинами 1,1 и 2 не существует. Действительно, здесь кодовые слова нужно взять из набора {0, 1, 00, 01, 10, 11}. Пусть, например, {0, 1, 00}. Тогда кодовое слово 000 при декодировании может быть воспринято неоднозначно: 0 0 0 или 0 00. Однако префиксный код в 100 слов с длинами от 1 до 100 существует.

–  –  –

C и k Nk = N.

Для фиксированного значения k число различных кодовых слов Nk ограничено: Nk 2k. Однако для префиксного кода это неравенство следует уточнить. Для заданных значений N1,... Nk1

–  –  –

то существует префиксный код с алфавитом из L символов и длинами кодовых слов l1... lN. При L = 2 возникает двоичный код.

Верно и обратное утверждение: длины кодовых слов любого префиксного кода удовлетворяют неравенству (110).

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

Пример. Два двоичных кода, которые удовлетворяют неравенству Крафта: K1 = {0, 00, 11} и K2 = {0, 10, 11}. Здесь l1 = 1, l2 = l3 = 2 и 21 + 2 · 22 = 1. Однако в отличие от K2 код K1 не является префиксным.

4.5 Построение префиксного кода Для построения префиксного кода удобно использовать кодовое дерево.

Кодовое дерево имеет высоту, равную максимальной длине кодового слова C = max Ck. При двоичном кодировании у дерева из корня, это нулевой этаж, идут две ветви, которым присваивают значения 0 и 1.

На первом этаже есть две концевые вершины, из каждой идут две ветви, этим ветвям также присваивают значения 0 и 1. На этаже k, где k = 1,... C имеется 2k вершин, из каждой вершины идут две ветви.

Для построения префиксного кода нужно выбрать Nk слов с длиной lk. Это означает, что на первом этаже фиксировано N1 концевых вершин, на втором этаже фиксировано N2 концевых вершин и т. д. Из неравенства (106) следует Nk 2k 2k1 N1 2k2 N2 · · · 2Nk1. (111) При k = 1 получим N1 2, что не превосходит общего числа вершин на 1 этаже. Значит на этом этаже можно выбрать число концевых вершин N1 = 0, 1, 2. Если это сделано, то их общего числа вершин на 2 этаже останется N2 4 2N1. Если фиксировать число N2, то на 3 этаже число концевых вершин будет N3 = 8 2N2 4N1. Выбранные концевые вершины являются кодовыми словами, которым можно поставить в соответствие последовательность двоичных символов.

Пример. Пусть максимальная длина кодовых слов равна 2. Пусть фиксирована одна вершина на первом этаже N1 = 1 и две вершины на втором этаже N2 = 2. Тогда возникает набор из трех кодовых слов, отвечающих одной вершине на первом этаже – слово "1 и двум вершинам на втором этаже по ветви "0.. которыми являются слова "00 "01". Кодовый набор 1, 00, 01 является префиксным, и им можно закодировать какие-нибудь три символа исходного текста.

4.6 Полнота префиксного кода и обезьяна Префиксный код называется полным, если добавление к нему нового кодового слова нарушает префиксность. Пусть, к примеру, буквам A, B и C сопоставлены кодовые слова 1, 00, 01. Тогда любая попытка закодировать еще одну букву приведет к нарушению свойства префиксности, поскольку кодирование будет осуществляться через ветвь 1, либо через 0, поэтому, например, слово 1 может стать началом нового кодового слова 11. Это означает, что код 1, 00, 01 является полным. Напротив код 00, 01, 10 неполный, поскольку через ветвь 11... можно закодировать новые буквы не нарушая свойство префиксности. Неполным также является код 1, 000, 001.

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

Теорема. Префиксный код является полным тогда и только тогда, когда неравенство Крафта становится равенством dl1 + dl2 + · · · + dlN = 1. (112) Доказательство. Пусть d = 2, что отвечает двоичному кодированию. Рассмотрим дерево, которое описывает полный префиксный код. Пусть на дерево взбирается обезьяна. Начав с корня, она выбирает любую из d = 2 двух исходящих из него ветвей. Вероятность выбора равна 1/2. Добравшись до очередной развилки, она вновь выбирает одну из двух ветвей с вероятностью 1/2. Тогда с вероятностью (1/2)k обезьяна окажется на этаже k и достигнет какой-нибудь концевой вершины. Если таких вершин Nk, то с вероятностью Nk 2k обезьяна останется на высоте k. Обезьяна может остановиться на любом этаже, поэтому вероятность найти ее на дереве равна 1. С другой стороны, эта вероятность равна k Nk 2k = 1, что и завершает доказательство.

Из приведенного доказательства легко увидеть, где использовано условие полноты префиксного кода.

Если код полный, то на любом этаже кодового дерева есть хотя бы одна концевая вершина, которая отвечает кодовому слову. Поэтому обезьяна может остановиться на любом из этажей. В рассмотренных выше примерах код 1, 00, 01 полный: одна концевая вершина на первом этаже и две – на втором. Код 00, 01, 10 неполный: на 1 этаже нет фиксированных концевых вершин. Код 1, 000, 001 также неполный, в его кодовом дереве отсутствуют фиксированные вершины на 2 этаже.

4.7 Код Фано Код Фано является префиксным полным кодом. Метод кодирования осуществляется по следующей схеме.

1. Расположить буквы алфавита исходного текста в порядке убывания их вероятностей.

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

3. Одному из множеству присвоить значение 0, другому 1.

4. Рассматривая каждое из двух множеств, как исходное, осуществить операции, указанные в пп. 2 и 3.

5. Процесс продолжается, пока в очередном подмножестве не останется одна буква.

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

–  –  –

Средняя длина кодового слова l = k p(xk )lk = 2, 8 будет меньше на 7 %, чем при равномерном кодировании, где на букву требуется 3 двоичных символа.

4.8 Код Хаффмана Метод Хаффмана (1952) обеспечивает наименьшую возможную при побуквенном кодировании длину кодового слова. В этом смысле он является оптимальным.

Кодирование осуществляется по следующей схеме.

1. Расположить буквы алфавита исходного текста списком в порядке убывания их вероятностей. Двум буквам с самой низкой вероятностью присваиваются значения 0 и 1.

–  –  –

4.9 Оптимальный код Оптимальный код обладает наименьшей длиной кодового слова. Такой код может быть не единственным, однако для него можно сформулировать некоторые общие свойства.

Пусть алфавит исходного текста x1, x2... xN имеет вероятности p1 p2 · · · pn, где pm = p(xm ), и кодируются двоичными словами длиной l1, l2... lN. Оптимальный код имеет следующие свойства.

1. Менее вероятный символ не может кодироваться более коротким словом.

2. Всегда можно так переименовать символы и соответствующие им кодовые слова, что p1 · · · pN при l1 · · · lN.

3. В оптимальном двоичном коде всегда найдется по крайней мере два слова наибольшей длины, равной lN, которые отличаются друг от друга в последнем символе.

Приведем некоторые пояснения.

Относительно свойства 1 заметим. Пусть проведено кодирование xk, pk lk, и xm, pm lm. Оно оптимальное, если pk pm, и lk lm. Для выбранного оптимального кодирования средняя длина кодового слова будет lcp = pk lk +pm lm. Заменим lk lm. Это означает, что часто встречающемуся символу xk будет сопоставлено более длинное кодовое слово lm lk. При таком кодировании средняя длина кодового слова будет lcp = pk lm + pm lk. Видно, что длина кодового слова lcp lcp = (lm lk )(pm pk ) 0 увеличивается.

Что касается свойства 2, то нужную нумерацию можно получить путем переобозначения символов. Тогда символ с наименьшей вероятностью xN будет кодироваться самым длинным словом lN. Если свойство 3 не выполняется, то оба слова с наибольшей длиной содержат одинаковые символы. Тогда можно откинуть последний символ кодового слова не нарушая префиксности. В результате длина кодового слова уменьшилась бы, что противоречит оптимальности.

Код Хаффмена является оптимальным.

4.10 Сжатие текстов Простым примером сжатия является сокращение слов при письме. Это оказывается возможным, поскольку в словах есть избыточная информация. Под сжатием понимают кодирование, при котором сжатый блок содержит меньше битов, чем исходный, но возможно однозначное декодирование. В практике используются следующие термины: кодирование/декодирование, сжатие/разжатие, компрессия/декомпрессия, упаковка/распаковка.

Различают следующие типы сжатия: 1) без потерь, 2) с потерями. Сжатие с потерями содержит два этапа. Вначале выделяется часть информации на основе некоторых критериев и модели источника, затем выделенная информация сжимается без потерь. Далее будет рассматриваться сжатие без потерь.

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

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

Свойство. Ни один компрессор не может сжать любой файл. После обработки компрессором часть файлов уменьшается, а оставшаяся часть либо увеличивается, либо не изменяется.

Доказательство. Это утверждение можно доказать в самом общем случае, однако мы ограничимся простой иллюстрацией. Если n длина файла или сообщения, то всего будет 2n различных сообщений. Если каждое сообщение уменьшилось на 1 бит, их длина стала n1, а общее число 2n1, что в 2 раза меньше исходного числа сообщений. При таком сжатии 2n элементов преобразуется в 2n /2, поэтому двум исходным сообщениям ставится в соответствие одно. Откуда следует невозможность однозначного декодирования.

Благодаря указанному свойству не существует "вечного архиватора"который сжимает до бесконечности свой архив. Наилучшим архиватором является копирование, поскольку объем данных при таком преобразовании не увеличивается.

Заметим, что в русском алфавите максимальное количество информации в букве log 32 = 5 бит, в кодировке ASCII на символ приходится 8 бит, а в Unicode – 16 бит. Однако эти значения справедливы, если считать что все буквы появляются одинаково часто, что не так для осмысленного текста, который обладает большой избыточностью.

4.11 Предельное сжатие Условие однозначного декодирования означает, что исходная информация не должна уменьшиться. Это согласуется с известным принципом физики о возрастания энтропии. Используя это условие можно пояснить наличие предела для сжатия информации.

При двоичном побуквенном кодировании xk lk в кодовом слове должно содержаться информации не меньше, чем в букве исходного текста. Средняя длина кодового слова lcp = k lk pk показывает, сколько бит требуется для его записи, или количество информации, которое в нем содержится. Средняя длина кодового слова будет определяться как методом кодирования, так и количеством информации в исходном символе H(X), при этом lcp H(X). (113) Пример. Рассмотрим алфавит из 3 символов, с вероятностями 0, 8; 0, 1; 0, 1. Побуквенное кодирование по схеме Фано или Хаффмена дает одинаковый результат x1 0, 8 0 x2 0, 01 10 x3 0, 01 11 Отсюда средняя длина кодового слова или количество бит в кодовом слове равно lcp = 0, 8 + 2 · 0, 1 = 1, 20, а количество информации в одном символе H(X) = (0, 8 log 0, 8 + 2 · 0, 1 log 0, 1) = 0, 92, что находится в соответствии с (113).

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

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

–  –  –

Cхемы Фано и Хаффмена приводят к одинаковой длине кодового слова lcp (2) = 1, 92, но это среднее число бит на два символа исходного алфавита, поэтому на один символ lcp (2)/2 = 0, 96, что по-прежнему находится в соответствии с неравенством (113).

Приведенные соображения о предельном сжатии, которые носят качественный характер, можно сформулировать в виде теоремы (Шеннон 1948).

4.12 Предельное сжатие текстов. Теорема Шеннона Предельное сжатие устанавливается теоремой Шеннона, которая имеет разные формулировки.

Теорема. Пусть букве ИДС сопоставляется кодовое слово xk lk со средней длиной lcp = k lk p(xk ).

Пусть H(X) – энтропия одной буквы ИДС, а алфавит кодера содержит L букв. Тогда

–  –  –

Доказательство. Основано на неравенстве Крафта k Llk 1, и свойстве функции log, согласно которому log z (z 1) loge при z 0. Пусть L = 2, тогда нужно доказать, что

–  –  –

Приведенная теорема (114) имеет довольно простой смысл: количество информации в кодовом слове lcp log L (напомним, что log L – максимальное количество информации в одной букве алфавита кодера) должно быть не меньше, чем количество информации H(X) в кодируемом символе ИДC.

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

Теорема. При любом кодировании сообщения m = {x1... xN }n средняя длина кодового слова в расчете на один символ сообщения

lcp /n H(X)/ log L, (115)

где H(X) – энтропия буквы алфавита источника.

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

Теорема Шеннона, однако, не дает никакого рецепта, как построить код, для которого lcp = H(X). Она лишь гарантирует его существование, и устанавливает нижнюю границу, которая определяется энтропией H(X). Эта граница находится в соответствии с интуитивно ясным требованием: в результате преобразования количество информации или энтропии не должно уменьшится. С другой стороны, это требование находится в рамках Второго Начала термодинамики, согласно которому энтропия может только возрастать.

Пример. Для этой теоремы рассмотрим иллюстрацию, которая использует асимптотические свойства ИДС. Пусть L = N = 2 и двоичное сообщение имеет длину n : m = {0, 1}n. Пусть вероятности появления символов p(1) = p и p(0) = q, p + q = 1. Тогда в m среднее число "1"будет pn, а среднее число "0"будет qn. Число различных сообщений длиной n, которые содержат r = pn единиц, равно n!

K=. (116) r!(n r)!

Если n велико: n 1, то для оценки K можно воспользоваться формулой Стирлига log n! n log n n, где n 1. Тогда из (116) следеут, что log K nH(p), (117) где H(p) = k pk log pk – энтропия в одной букве алфавита. Весь набор из K сообщений в среднем будет иметь одинаковую вероятность, равную 1/K = 2nH(p), поскольку все сообщения содержат одинаковое количество "1"и "0". Построенное множество K совпадает с высоковероятным множеством B из теоремы об асимптотических свойствах ИДС.

Чтобы закодировать K 2nH(X) элементов с одинаковой вероятностью, потребуется кодовое слово длиной l = log K nH(X). В итоге возникает сжатие, поскольку блок длиной n бит преобразуется в кодовое слово длиной l = nH(p) n бит в соответствии с (115).

5 Дискретные каналы

5.1 Пропускная способность дискретного канала без памяти Канал представляет собой физическую систему, которая служит для передачи информации от отправителя к получателю. Закодированные сообщения ИДС поступают в канал, на выходе которого находится получатель. Каналы связи могут иметь разную природу. Далее будет рассматриваться дискретный канал без памяти, где символ на выходе в данный момент времени зависит лишь от символа, поступившего на вход. Если все входные символы воспроизводятся на выходе, то канал называют идеальным или нешумящим. Однако в реальной ситуации всегда существует шум.

Действие канала можно рассматривать как преобразование

T: X Y, (118)

где X = {x1... xN } – случайная величина на входе, а Y = {y1... yM } – случайная величина на выходе.

Это преобразование описывается передаточными функциями p(y|x), которые представляют вероятность принять значение y, если отправлено значение x. Безусловная вероятность появления символа на выходе будет p(y) = p(y|x)p(x). Передаточные функции образуют матрицу передаточную M N x

–  –  –

Поскольку p(x, y) = p(y|x)p(x), то отсюда следует, что сумма всех элементов в строке матрицы: y p(y|x) = 1.

Соответствие между посланным и принятым сообщением определяется взаимной информацией или энтропией

–  –  –

Отсюда видно, что условная энтропия H(X|Y ) приводит к уменьшению взаимной информации. Это связано с шумами канала, которые приводят к ошибке при приеме.

Взаимная информация I(X : Y ) зависит от свойств канала, которые описываются p(y|x), и свойств источника сообщений, который определяется вероятностью p(x):

–  –  –

где N – число букв в алфавите исходного сообщения. Это означает, что будет получено log N бит на один отправленный символ. Если величины X и Y оказываются полностью независимыми, то H(X|Y ) = H(X) и взаимная информация равна нулю. В таком канале C = 0, это означает, что шумы настолько велики, что передавать информацию нельзя.

В общем случае взаимная энтропия H(X|Y ), H(Y |X) 0, поэтому количество принятой информации будет меньше, чем в H(X), и соответственно C H(X). Это означает, что появление символа на выходе канала не дает получателю с уверенностью судить, какой символ был послан.

5.2 Скорость передачи информации Обычно источник генерирует символы с некоторой скоростью. Пусть T время, которое требуется на передачу одного символа, пусть оно одинаково для всех символов. Если H(X) энтропия на один символ, то производительность дискретного источника можно определить как энтропию в единицу времени H (X) = H(X) = H(X), (125) T где введена скорость передачи символа.

Можно определить взаимную энтропию в единицу времени

I (X : Y ) = [H(X) H(X|Y )] = [H(Y ) H(Y |X)], (126)

которую называют скоростью передачи информации по каналу. Здесь H(X) – производительность источника, а H(Y ), называют "производительность"канала. Две условные энтропии H(X|Y ) и H(Y |X) можно рассматривать как потерю информации или ненадежность канала в единицу времени, соотношение между ними зависит от свойств канала.

С помощью (126) можно определить пропускную способность канала в единицу времени или скорость передачи информации по каналу C = max I (X : Y ). (127) Эта величина имеет размерность бит на переданный символ в секунду: за секунду принимают C бит на переданный символ. Для C можно указать нижнюю и верхнюю границы

0 C log N, (128)

где свое максимальное значение max C = log N скорость передачи принимает для канала без шумов.

Заметим, что скорость передачи может зависеть от физических свойств канала. Тогда пропускная способность будет ограничена этой величиной. Так, говорят, что для следующих каналов связи справедливы оценки для предельных частот. Телеграф – 140 Гц, телефон до 3,1 КГц, короткие волны (10 – 100 м) – 3–30 МГц, УКВ (1–10 м) – 30–300 МГц, спутник (сантиметровые волны) – до 30 ГГц, оптические (инфракрасный дипазон) – 0,15 – 400 ТГц (Тера = 1012 ), оптический (видимый диапазон) – 400–700 ТГц.

Скорость передачи информации измеряется в количестве бит, переданных за одну секунду или в бодах (baud): 1 бод = 1 бит/с (bps). Производные единицы для бода такие-же как и для бита и байта, например, 10 Kbaud = 1024 baud.

5.3 Вычисление пропускной способности Пропускная способность C определяется как максимум взаимной энтропии I(X : Y ) по распределению источника, поэтому для вычисления C нужно найти такое распределение p(x), для которого функционал I(X : Y ) принимает максимальное значение. С математической точки зрения это задача вариационного исчисления. Однако при некоторых предположениях можно получить простые рецепты для вычисления пропускной способности.

Для взаимной информации справедливо выражение (121)

–  –  –

где X(x : Y ) = y p(y|x) log p(y|x)/p(y). Пусть величина X(x : Y ) не зависит от x. Это означает, что X(x1 : Y ) = X(x2 : Y ) =... Тогда по определению

–  –  –

Чтобы воспользоваться найденным рецептом, можно угадать вид распределения p(x), которое приводит к (130). В ряде случаев удачным оказывается равномерное распределение p(x) = 1/N.

5.4 Симметричные каналы Если канал обладает свойствами симметрии, то можно получить точные и простые выражения для его пропускной способности. Так, пропускная способность симметричного канала

–  –  –

Задача определения максимума энтропии H(Y ) на входном распределении p(x) упрощается, если канал симметричный по входу обладает дополнительной симметрией.

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

Это означает, что все столбцы составлены из одного набора элементов, поэтому аналогично (134) справедливо следующее.

Свойство. Для любого столбца сумма от произвольной функции условных вероятностей f (p(y|x)) постоянна и не зависит от y

–  –  –

Строки матрицы получаются друг из друга перестановкой, поэтому канал является симметричным по входу и его пропускная способность определяется выражением (137)

–  –  –

6 Защита от случайных помех

6.1 Корректирующие коды При хранении и передаче информации возникают ошибки. Их причиной являются шумы, устранить которые невозможно. Для исправления ошибок служат корректирующие коды.

Оптимальное кодирование позволяет экономить ресурсы при передаче и хранении информации. Однако сообщение оказывается беззащитным, поскольку любой символ содержит максимально возможную информацию, которая теряется в случае ошибки. Чтобы обнаружить ошибки, вводятся дополнительные исправляющие символы. Пусть алфавит ИДС содержит 2m букв xk, k = 1,... N = 2m, тогда при двоичном побуквенном кодировании

xk {0, 1}m + z, (152)

где m – длина кодового слова, z – число исправляющих символов. Используя простые соображения, можно получить оценку для числа исправляющих символов z. Пусть ошибка происходит только в одном символе, и пусть все ошибки независимы. Тогда один символ может измениться или остаться неизменным в m+z+1 случаях, поэтому количество информации об ошибках будет равно log(m + z + 1) бит. Чтобы исправлять ошибки, количество информации в исправляющих битах, равное z при двоичном кодировании, должно быть

z log(m + z + 1). (153)

6.2 Коды с повторением Чтобы защитить сообщение от ошибок, его можно повторить несколько раз.

При кодировании с повторением каждый символ преобразуется в блок длиной z, например, 0 {0}z, 1 {1}z. При декодировании блока решение принимается "большинством голосов": если в принятом блоке нулей больше, чем единиц, то он декодируется как 0. Код позволяет восстанавливать посланные символы, если ошибки произошли меньше, чем в 50% символов. Если выбрать большую длину блока z, то ошибок практически не будет, однако возрастет длина кодового слова.

6.3 Арифметика по модулю 2 В арифметике по модулю 2 есть две цифры 0 и 1 и две операции: сложение и умножение. Умножение определяется следующим образом 0·0=0 0·1=0 1·0=0 1 · 1 = 1.

Сложение по модулю 2 a + b mod 2 определяется как 0+0=0 0+1=1 1+0=1 1 + 1 = 0.

где z mod 2 = z, если z 2 и z mod 2 = остаток от деления z/2, если z 2. В этой арифметике справедливы все законы сложения и умножения. Кроме того

–  –  –

Полученные уравнения решают задачу. Так, с помощью (158) для заданного сообщения записываются исправляющие символы, а место ошибочного символа определяется из (157).

Для примера рассмотрим сообщение a1 a2 a3 a4 = 1001. Для него согласно (158) исправляющие символы будут a5 a6 a7 = 100. Кодовое слово имеет вид 1101100. Пусть в кодовом слове произошла ошибка, скажем во втором символе, тогда будет новое кодовое слово 1001100. Для него согласно (157) e0 = 1 + 0 + 1 + 0 = 0, e1 = 1 + 0 + 0 + 0 = 1, e2 = 1 + 1 + 0 + 0 = 0. Последовательность e2 e1 e0 = 010 = 2 указывает позицию ошибочного символа.

Список литературы [1] К. Шеннон. Работы по теории информации и кибернетике. М., ИЛ, 1963.

[2] Б.Д. Гнеденко. Курс теории вероятностей. М., ГИФМЛ, 1961.

[3] А.М. Яглом, И. М. Яглом. Вероятность и информация. М., ГИФМЛ, 1960.

[4] Р. Галлагер. Теория информации и надежная связь. М. Советское радио, 1974.

[5] М.Н. Аршинов, Л.Е. Садовский. Коды и математика. М., Наука, 1983.

Похожие работы:

«Ткачев Александр Сергеевич ИССЛЕДОВАНИЕ И ОЦЕНКА ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ТРУБЧАТЫХ ЭЛЕКТРОДОВ С ЦЕЛЬЮ СНИЖЕНИЯ ЭНЕРГЕТИЧЕСКИХ ЗАТРАТ ПРИ ВЫПЛАВКЕ СТАЛИ В ДУГОВЫХ СТАЛЕПЛАВИЛЬНЫХ ПЕЧАХ МАЛОЙ И СРЕДНЕЙ ВМЕСТИМОСТИ Спе...»

«УДК 658.5.011 Дубиновский Марк Зиновьевич Dubinovskiy Mark Zinovievich доктор технических наук, Dr. Sci. (Phys.-Math.), профессор кафедры государственного Professor of the State and Municipal и муниципального управления Administration Sub...»

«Модель MCD-220U FM/УКВ CD/MP3 ресивер Руководство пользователя Руководство пользователя определяет порядок установки и эксплуатации автомобильного FM/УКВприемника и проигрывателя MP3/WMA и компакт-дисков (далее CD-ресивера) в автомобиле с напряжением бортовой сети 12 В. Установку CD-ресивера рекомендуется про...»

«Кафедра "Вычислительная техника" Выпускающая кафедра факультета МПиТК Заведующий кафедрой ВТ Знание есть сила, Бархоткин сила есть знание. Вячеслав Александрович Бэкон Ф. Член-корреспондент РАРАН, доктор технических наук, профессор Миссия кафедры ВТ: Развитие и саморазвитие целостной личности – профес...»

«Персоналии ГЕРМАН ПЛАТОНОВИЧ ВЯТКИН. К 80-ЛЕТИЮ СО ДНЯ РОЖДЕНИЯ В.П. Бескачко1 1 мая 2015 года исполнилось 80 лет со дня рождения известного ученого, член-корреспондента Российской академии наук, доктора химических наук, профессора Германа Платоновича Вятки...»

«Агафонкин Александр Владимирович ИНГИБИРОВАНИЕ КОРРОЗИИ МЕТАЛЛОВ ЛЕТУЧИМИ ОСНОВАНИЯМИ ШИФФА И КОМПОЗИЦИЯМИ НА ИХ ОСНОВЕ специальность 05.17.03 – “Технология электрохимических процессов и защита от коррозии” Автореферат диссертации на с...»

«ЗАО " Система измерений количества нефти Внесены в Г осударственный реестр на узле учета нефти "Псекупский" средств измерений Регистрационный № 2joO(bO-C& Взамен № Изготовлена в единичном экземпляре в соответствии с технической документацией 022.43121843...»

«Саратовский государственный университет Механико-математический факультет Математическая экономика Составители: Дудов С. И., Мещерякова Е. А. 9 октября 2008 г. Оглавление Введение 3 1 Элементы не...»

«Богомолов Денис Игоревич СТРУКТУРА И СВОЙСТВА НИЗКОТЕМПЕРАТУРНЫХ ТЕРМОЭЛЕКТРИЧЕСКИХ МАТЕРИАЛОВ, ПОЛУЧЕННЫХ ИНТЕНСИВНОЙ ПЛАСТИЧЕСКОЙ ДЕФОРМАЦИЕЙ Специальность 05.27.06 "Технология и оборудова...»

«Министерство образования и науки Российской Федерации федеральное государственное автономное образовательное учреждение высшего образования "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ" Институт сициально-гуманитарных технологий Направление подготовки 38.03.02 менедж...»

«Форма типового технического задания СОГЛАСОВАНО УТВЕРЖДАЮ Генеральный директор Главный инженер ООО "НИИ ТНН" ОСТ И.О. Фамилия _ И.О. Фамилия "_" 20 г. "_" 20 г. ТЕХНИЧЕСКОЕ ЗАДАНИЕ № на проведение обследования коррозионного состоян...»

«ПРОГРАММИРУЕМЫЙ БЛОК УПРАВЛЕНИЯ МАССАЖЕРОМ. БМ-2 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ г. Днепропетровск 2007 г. СОДЕРЖАНИЕ 1.Назначение 2.Технические данные 3.Комплект поставки 4.Маркировка 5.Указания мер безопасности 6.Порядок работы 7. Характерные неиспра...»

«Казанский государственный архитектурно-строительный университет Кафедра прикладной математики Методические указания к лабораторным работам по курсу "Информатика" для студентов всех специальностей Microsoft Ac...»

«Электронный архив УГЛТУ МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра информационных технологий и модел...»

«НПК "ЛЕНПРОМАВТОМАТИКА" САУ автомобильной газонаполнительной компрессорной станцией КСПА–007 и КСПА-007-00-01 Назначение САУ АГНКС КСПА-007(-00-01) применяется для автоматизации автомобильных газонаполнительных компрессорных станций типа МБКИ-250 либо БК...»

«РОСЖЕЛДОР ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ" (ФГБОУ ВО РГУПС) ТЕХНИКУМ (ТЕХНИКУМ ФГБОУ ВО РГУПС) МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ И ПРАКТИЧЕСКИХ РАБОТ МДК.03.03 НЕРАЗРУШАЮЩИЙ КОНТРОЛЬ РЕЛЬСОВ ДЛЯ СПЕЦИАЛЬНОСТИ СТРОИ...»

«Известия ТулГУ. Технические науки. 2016. Вып. 12. Ч. 2 EXPERIMENTAL SUBSTANTIATION OF THE POSSIBILITY OF DETERMINING BREATHING STOPS ON A SIGNAL FROM GREES A.V. Prohortsov, M.B. Bogdanov, A.N. Senin The possibility of determining a person's respiratory parameters including respiratory arrest, the signals mik...»

«XVII Международная конференция “Физика прочности и пластичности материалов” 23-25 июня 2009 г. Самара МЕХАНИЗМЫ ИНТЕНСИВНОЙ ПЛАСТИЧЕСКОЙ ДЕФОРМАЦИИ НА МЕЗОМАСШТАБНОМ УРОВНЕ ПОЛИКРИСТАЛЛОВ ПРИ ЦИКЛИЧЕСКОМ НАГРУЖЕНИИ Елсукова Т. Ф., Панин В. Е., Ваулина О. Ю., Попкова Ю. Ф.1 Институт физики прочности и материалов...»

«ВВЕДЕНИЕ Настоящее руководство по эксплуатации (РЭ) предназначено для изучения устройства, принципа работы, правил эксплуатации и технического обслуживания датчиков уровня емкостных ДУЕ-1В-0 (в дальнейшем датчики). В РЭ приведены основные технические характеристики датчиков, сведения о работе отдельных фу...»

«2013 ПРАВИЛА ЗЕМЛЕПОЛЬЗОВАНИЯ И ЗАСТРОЙКИ МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЯ "БЕЛОМЕСТНОКРИУШИНСКИЙ СЕЛЬСОВЕТ" ТАМБОВСКОГО РАЙОНА ТАМБОВСКОЙ ОБЛАСТИ ООО "Национальная градостроительная компания" Правила землепользования и застройки муниципального образования "Беломестнокриушинский сельсовет" Заказчик пр...»

«УДК 303.7: 504.05 В.А. Минаев1, А.И. Мохов2, А.О. Фаддеев3, Н.А. Кузьменко4 (1Академия ГПС МЧС России, 2Государственная Академия Минстроя России, Академия ФСИН России; 4ЗАО РТИ-Инвест; e-mail: m1va@yandex.ru) ИНТЕГРАЦ...»

«48 8120 ОГРАНИЧИТЕЛЬ НАГРУЗКИ КРАНА МОСТОВОГО ТИПА ОНК-160М Руководство по эксплуатации НПКУ.408844.029 РЭ Содержание 1 Описание и работа изделия 3 2 Описание и работа составных частей изделия 9 3 Меры безопасности...»










 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.