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

где H - энтропия данного кода, а Н макс. - максимальное значение энтропии. Избыточность кода является дополнением к относительной энтропии:

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

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

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

Избыточность сообщения можно сводить к нулю при пользовании оптимальным кодом. При неравномерном распределении вероятностей символов и при наличии их внутренней вероятностной связи (корреляции) уменьшается относительная энтропия и возрастает избыточность сообщения. При создании текста мы делаем меньше выборов, чем число букв в тексте, так как мы действуем в рамках грамматических правил образования слов и предложений. Только примерно от 1 / 4 и до 1 / 3 числа букв мы можем выбирать произвольно: мы можем выбрать данные буквы или не выбрать их. Следовательно, при оптимальном коде мы могли бы выражаться втрое или вчетверо короче. Любая комбинация букв здесь создавала бы слово, полное смысла, так как все буквы и комбинации их встречались бы одинаково часто и каждая таблица букв могла бы годиться для кроссворда. Однако при обычном общении людей избыточность всегда имеет место, она имеется в каждом разговоре, в газетном языке и в научной литературе. Каждый национальный язык имеет значительную степень избыточности. Как уже было сказано, избыточность имеет не только отрицательные, но и положительные, полезные стороны. Она обеспечивает возможность понять друг друга, возможность исправить ошибки, получившиеся при передаче, тогда как при нулевой избыточности ошибки при передаче сильно искажали бы конечное сообщение.

Избыточность можно снизить путем перекодирования, путем изменения статистической структуры сигнала. Так, например, Нейдхардт 1 указывает, что в телевидении можно снизить избыточность путем уменьшения скорости развертывания передаваемого образа в тех местах, где сконцентрировано наибольшее информационное содержание, и путем ускорения развертывания в тех частях, где имеются свободные места и где можно эти промежутки интегрировать во времени. Если переходные вероятности между элементами одинаковы, нет взаимозависимости символов, то корреляция между ними нулевая. Если же, наоборот, они различны, то это дает экономию передачи и уменьшает избыточность. При передаче информацию несет только часть сигналов, остальные сигналы избыточны; в полезной части сообщения одна и та же информация может содержаться несколько раз, что дает возможность дальнейшего сжатия сообщения. Нейдхардт различает холостую (бесполезную) и полезную избыточность. Из неизбыточного сообщения нельзя изъять ни один знак, не изменяя этим его смысл. Если мы хотим установить избыточность сообщения, то мы убираем из этого сообщения знаки до тех пор, пока это не лишает сообщение понятности, то есть пока оно не теряет своего смысла. В противоположность холостой избыточности полезная избыточность обеспечивает или же и повышает верность передачи сообщения, и, наоборот, появление холостой избыточности не повышает ясности сообщения.

1 (См. Р. Neidehardt, Einf?hrung in die Informationstheorie, Berlin, 1958. )

Выявление избыточности печатного текста выполняется, например, с помощью так называемой ампутации текста, при которой из полной формы напечатанных букв убирают какие-то части, так что мы можем определить предел читаемости, а следовательно, и меру избыточности. Аналогичным образом эта мера применяется для определения видимости цветов с помощью так называемых псевдоизохроматических таблиц. На использовании (вернее на устранении) избыточности основана стенография, а также экономия времени при телеграфировании. Так, например, в телеграфном коде Морзе наиболее короткие знаки - точки - используются для буквы Е , чаще всех встречающейся в английском языке.

Наглядный пример использования избыточности для сжатия передаваемого текста приводит Мейер-Эпплер 1 . Имеем текст, состоящий из 23 букв:

1 (W. Meyer-Eppler, Informationstheorie, "Naturwiss.", № 15, 1952, S. 341. )

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

можно заменить буквами

а вместо буквы V будем писать НС , так что путем такого перекодирования мы получим новый текст, состоящий уже только из 18 букв.

Другой пример с более высокой и более низкой избыточностью в коде приводит Черри 1:

1 (C. Cherry, On Human Communication, New York, 1957, p. 186. )

Если бы мы закодировали буквы А , В , С и D только с помощью двух бинарных знаков, например, как

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

то код станет более избыточным, но он будет иметь большую помехоустойчивость. Если, например, помеха коснется одного знака (он исказится), то эту помеху можно обнаружить (но, конечно, не сразу же исправить ее). Так, например, при одной помехе код для A может измениться в 1110, 1101, 1011 (вместо 1111) или же 0111, то есть во всех этих случаях код А нельзя будет спутать с группой кодовых символов для В , С или D , как это может иметь место в случае двухзначного кода при одной помехе (когда получится 0 вместо 1 или 1 вместо 0). Конечно, например, группа 1110 может при одной ошибке получиться при искажении не только кода буквы A , но и кодовых букв В , С или D . Еще большая помехоустойчивость может быть получена при еще большем усложнении кода, при придании ему еще большей избыточности.

Правильное кодирование передаваемых и записываемых сообщений имеет большое значение для человеческого общества, которое поэтому и изыскивает все более экономичные способы кодирования сообщений. Сообщение можно расположить, например, в ряды, но более экономичным будет расположение сообщений в группы. Например, в телеграфной передаче каждой из 32 букв отведена какая-то единица времени, в телетайпе же введена более экономичная система, состоящая только из пяти единиц времени для всех 32 букв. Вместо 32 знаков здесь используется только 5 знаков. 32 знака управляются пятью двоичными шагами. Групповая компоновка использована также при написании чисел в десятичной системе. Совокупность всех сообщений о тысяче численных данных (чисел от 0 до 999) можно выразить только тремя цифрами. В противоположность этому расположение в ряд требовало бы тысячи знаков и выбора из тысячи возможностей. Поэтому прежнюю римскую цифровую систему, у которой было именно рядовое расположение цифр, заменили арабской цифровой системой. (Римская цифровая система состояла, собственно говоря, из ряда линий, но притом так, что для пяти линий ввели знак V , для десяти линий - знак X , для пятидесяти линий - знак L и т. д.)

Совокупность сообщений V требует не менее log M V данных, если каждое данное касается одного решения из M возможностей. На этом принципе можно построить ограничение числа разрешающих шагов. Если, например, мы имеем 32 (карты (или буквы и т. п.), то вероятность того, что мы угадаем, какая карта вытянута из колоды, будет 1 / 32 , и в среднем необходимо 16 раз гадать, прежде чем угадаешь правильно, какая карта вытянута. Однако, чтобы угадать это, достаточно иметь только пять ответов "да - нет" на пять вопросов, что соответствует числу log 2 32.

Эти пять вопросов можно составить следующим образом:

1. Красная ли это карта? (Если "да", то это значит, что червовая или бубновая карта, "нет" - значит либо трефовая, либо пиковая карта.)

2. Червовая ли это карта (или бубновая)?

3. Фигура ли это? (При ответе "нет" это значит, что карта цифровая.)

4. Это карта из высшей половины (фигур или цифровых карт)?

5. Это четная карта из данной половины?

После пяти ответов на эти вопросы мы получим ответ, какая именно карта вытянута.

Таким образом, с помощью надлежащей упорядоченности можно добиться экономии и снижения избыточности. Хорошим примером низкой избыточности, приводимым Земанеком 1 , является шрифт для слепых, в котором остается неиспользованным лишь небольшое пространство из шести полей одной буквы. Здесь избыточность составляет только 31,4%. В противоположность этому блочный типографский шрифт, где для одной буквы используется 35 полей карты, имеет сравнительно большую избыточность - 88,3%. Письменный шрифт имеет довольно большую избыточность, и он должен ее иметь хотя бы по той причине, что индивидуальные отклонения в начертании отдельных букв приводили бы при низкой избыточности к большей степени искажений. Как отмечает Земанек, только благодаря тому, что письменный шрифт имеет большую избыточность, получается, что аптекарь может прочитывать ^написанные врачами рецепты, которые для профанов совершенно непонятны. Стенография является, собственно говоря, сильно упрощенным письменным шрифтом с низкой степенью избыточности. Можно с уверенностью сказать, что избыточность существует не только в языке письма или речи, но и в языке нашего мышления (так называемый внутренний язык, по Теплову), и в мышлении, и познании вообще. Не исключено, что на основе математических исследований информации и избыточности мы придем к созданию универсального шрифта и языка для максимально экономичного кодирования научной информации. Само собой разумеется, что в зависимости от назначения данного научного сообщения степень избыточности в нем должна быть различной и, например, для научно-популярной работы нужна большая степень избыточности, чем для работы, предназначенной для специалистов по данному вопросу.

1 (H. Zemanek, Ungewohnte Zahlen aus der Informations-theory, "Radiotechnik", № 6, 1954, S. 188. )

В вышеназванной статье Земанек указывает, что в среднем в нашей речи избыточность составляет 75% (различные национальные языки имеют, конечно, различную степень избыточности, причем сравнительно наименьшую избыточность имеет английский язык). Страница книги, содержащая 500 - 2500 букв, содержит не 2500 - 12500 двоичных единиц информации, а только лишь 600 - 3000 этих единиц. Если книга имеет 500 страниц, то в ней содержится 10 6 двоичных единиц информации. Среднее количество томов в каждой из десяти крупнейших американских библиотек было в 1850 году 2·10 4 , в 1900 году - 2·10 5 , в 1950 году - 2·10 6 , гак что можно ожидать, что в 2000 году среднее количество томов в таких библиотеках составит примерно 2·10 7 . Количество двоичных единиц информации, находящихся в этих книгах, возрастет соответственно с 2·10 10 до 2·10 12 . Исходя из этого, Земанек считает, что данное количество книг могло бы служить базой для составления приблизительной картины роста человеческих знаний. Конечно, тут Земанек измеряет информацию только технически - по количеству букв, но не семантически, то есть по смыслу и по плотности информационного содержания. В этой статье Земанек пытается также определить верхний предел объема информации, могущего быть использованным одним читателем в течение всей его жизни, и этот объем не превышает, по Земанеку, 5·10 10 двоичных единиц информации.

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

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

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

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

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

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

Теория помехоустойчивого кодирования

Лекция 10. Теория помехоустойчивого кодирования

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

Для импульсных последовательностей спектр является дискретным:

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

Т.е. в спектре имеются только нечетные гармоники: 1, 3, 5,…..

Цель лекции: ознакомление c теорией помехоустойчивого кодирования и теоремой об эффективном кодировании.

а) теория помехоустойчивого кодирования;

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

в) избыточность сообщений;

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

10.1 Пропускная способность и скорость передачи информации

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

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

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

R= I(A’,A)/T H =F*[(H(A)-H(A/A’)]=F*. (10.1)

Пропускная способность – это максимально достижимая для данного канала скорость передачи информации

C= R max = max F*I (A’,A), {P} или {W} (10.2)

где максимум ищется по всем распределениям вероятностей источника ДС или всем ФПВ источники НС. Величина С является характеристикой только канала связи и не зависит от статистики источника сообщений.

В качестве источника сообщений рассмотрим оператора, который вводит в компьютер текста на русском языке. Очевидно, что буквы в тексте появляются с разными вероятностями. Так, буква А передается значительно чаще чем Ц или Ю . Кроме того, появление очередной буквы зависит от предыдущей. Ясно, что после гласных не появится Ь , Ъ или Ы . Весьма редким будет появление подряд трех букв Е (в слове «змееед»). Таким образом, на выходе источника «с памятью» (зависимыми сообщениями) неопределенность оказывается меньше, чем при отсутствии памяти, когда сообщения появляются хаотично. Таким образом, мы подошли к понятию избыточности источника, которую формально можно определить соотношением:

Отсюда видно, чем больше энтропия, тем меньше избыточность источника и наоборот. Ясно также, что величина избыточности принимает значения в пределах 0≤ρ≤1.

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

Избыточность можно определить так:

ρ=(n-n min)/n=1-n min /n. (10.4)

Величину μ=H(A)/logN=n min /n называют коэффициентом сжатия. Он показывает, до какого значения без потери информации можно сжимать передаваемые сообщения, если устранить содержащуюся в них избыточность. Например, при передаче телеграмм из текста исключают союзы, знаки препинания которые легко восстанавливаются при чтении на основании известных правил.

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

Помимо избыточности важным параметром, характеризующим любой источник с фиксированной скоростью V и =1/Т и симв/с выдачи сообщений, является его производительность, которую определяют как энтропию в единицу времени (секунду):

H’(A)=V и H(A). (10.5)

Если энтропия максимальна и равна log N, то величина R и =logN/T и, бит/с, называется информационной скоростью источника.

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

Задача 1: Предложите обобщающий термин следующим понятиям: данные, сведения, сообщения, знания, смысл символа, прогноз, высказывание, вывод, результат. Ответ: Информация Задача 2: Установите соответствие между существующими подходами к феномену «информация» и их названиями. Название Подход 1) АтрибутизмА) Об информации можно говорить по отношению к биологическим, социальным и социотехническим системам. 2) АнтропоцентризмБ) Информация является семантическим свойством любой материи. 3) ФункционализмВ) Об информации можно говорить только по отношению к человеку и социальным системам Ответ: 1Б, 2В, 3А

Задача 3: Установите соответствие между существующими определениями информации и названиями соответствующих областей знаний, где применяется данное определение. Область знаний Определение «информация» 1) В теории связиА) Отраженное многообразие, возникающее в результате взаимодействия объектов. 2) В философииБ) Сведения, которые уменьшают существующую до их получения неопределенность 3) В теории управленияВ) Сообщения в форме знаков или сигналов, которые хранятся, обрабатываются и передаются с помощью технических средств. 4) В теории информацииГ) Знания, которые используются в управлении для сохранения и развития системы. Ответ: 1В, 2А, 3Г, 4Б

Задача 4: Заполните таблицу, ответив в соответствии с различными определениями «информации» на следующие вопросы: 1. Являются ли для вас информацией сведения, содержащиеся в библиотеке Московского государственного университета? 2. Являются ли информацией нерасшифрованные космические послания? 3. Являются ли информацией сведения, содержащиеся в книге по искусству, которые вы повторно читаете? Определение «информация» Ответы (да/нет) Вопрос 1Вопрос 2Вопрос 3 Отраженное многообразие, возникающее в результате взаимодействия объектов Сведения, которые уменьшают существующую до их получения неопределенность Сообщения в форме знаков или сигналов, которые хранятся, обрабатываются и передаются с помощью технических средств. Знания, которые используются в управлении для сохранения и развития системы.

Ответ: Результат данного задания может быть различным, в зависимости от уточняющей информации, которая принимается в процессе обсуждения. Одним из вариантов решения может быть следующим: Определение «информация» Ответы (да/нет) Вопрос 1Вопрос 2Вопрос 3 Отраженное многообразие, возникающее в результате взаимодействия объектов Да Сведения, которые уменьшают существующую до их получения неопределенность Нет Да Сообщения в форме знаков или сигналов, которые хранятся, обрабатываются и передаются с помощью технических средств. Да Нет Знания, которые используются в управлении для сохранения и развития системы. Да Нет

Задача 5: Заполните таблицу следующими видами информации: визуальная, числовая, личная, графическая, тактильная, мультимедийная, общественная, звуковая, обонятельная, специальная, аудиальная, текстовая, вкусовая. По способу восприятия По форме представления По общественному значению Ответ: По способу восприятия По форме представления По общественному значению Визуальная Аудиальная Тактильная Обонятельная Вкусовая Числовая Графическая Мультимедийная Звуковая Текстовая Личная Общественная Специальная

Задача 6: Определите какие виды знаний отражены в следующих предложениях: Я знаю, что процессор служит для обработки информации» Я знаю, как набирать знания; Я знаю, как искать грибы; Я знаю, что грибы растут в лесу; Я знаю, как зовут собаку у моего друга; Я знаю, что надо делать, если «завис» компьютер. Ответ: Декларативные Декларативные Процедурные Декларативные Процедурные

Задача 7: Проанализируйте, что вы могли бы потерять или приобрести, если бы избегали избыточной информации (т.е. информации, исключения которой не отразится на смысле сообщения) в общении, в художественной литературе, в точных науках? Ответ оформите в виде следующей таблицы: Сфера деятельности ПотериПриобретения Общение Художественная литература Точные науки Ответ: Сфера деятельности ПотериПриобретения Общение Формальность человеческих отношений Экономия времени при общении Художественная литература Отсутствие образности, индивидуальности Краткость, понятность, простота Точные науки Непонимание неспециалистами Однозначность понимания специалистами

Задача 8: Укажите, в каком виде представлена информация в следующих примерах: Пример Вид информации По способу восприятия По форме представления Письмо другу Картина на стене Радиопередача Телепередача Аромат сирени Температура воздуха Желтый цвет Вкус лимона Таблица умножения

Ответ: Пример Вид информации По способу восприятия По форме представления Письмо другу ВизуальнаяТекстовая Картина на стене ВизуальнаяГрафическая Радиопередача АудиальнаяЗвуковая Телепередача Визуальная и аудиальная Мультимедийная Аромат сирени Обонятельная- Температура воздуха Тактильная- Желтый цвет Визуальнаяграфическая Вкус лимона Вкусовая- Таблица умножения ВизуальнаяЧисловая

Избыточность сообщений.

Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения.

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

Русский алфавит, включая пропуск между словами, содержит 32 элемента, следовательно, Н = Iog32 = 5 бит. Анализ показывает, что с учетом неравномерности появления различных букв алфавита Н = 4,35 бит, а с учетом зависимости двухбуквенных сочетаний Н = 3,52 бит.

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

Эффективное кодирование. При кодировании каждая буква исходного алфавита представляется различимыми последовательностями, состоящими из кодовых букв (цифр). Если исходный алфавит содержит т букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение т < k q , где q - количество элементов в кодовой последовательности. Отсюда

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как q –разрядные числа в k-ичной системе счисления. Например, при двоичном кодировании 32 букв русского алфавита используется q - Iog32 = 5 разрядов, на чем и основан телетайпный код. Кроме двоичных, наибольшее распространение получили восьмеричные коды. Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется 6 двоичных или 2 восьмеричных разряда. Буква с номером 13 получит соответственно коды 001 101 или 15. Часто используются также двоично-десятичные коды, в которых цифры десятичного номера буквы представляются двоичными кодами. Так, для нашего примера буква с номером 13 кодируется как 0001 0011.

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

При построении неравномерных кодов необходимо обеспечить возможность их однозначной расшифровки. В равномерных кодах такая проблема не возникает, так как при расшифровке достаточно кодовую последовательность разделить на группы, каждая из которых состоит из q элементов. В неравномерных кодах можно использовать разделительный символ между буквами алфавита (так поступают, например, при передаче сообщений с помощью азбуки Морзе). Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.

Практические методы оптимального кодирования просты и основаны на очевидных соображениях. Прежде всего, буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается на два подмножества так, чтобы суммарные вероятности этих подмножеств были примерно равны. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей. Такое разбиение продолжается до тех пор, пока в подмножествах не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества - 0.

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

Ошибка в кодовой комбинации появляется вследствие замены одних элементов другими, причем r-кратная ошибка возникает при искажении г элементов. Например, если кодовая комбинация 0110111 принята как 0100110, то имеет место двукратная ошибка. Вообще различие между парой кодовых комбинаций выражается расстоянием, которое равно числу несовпадающих двоичных разрядов. Его можно также определить как число единиц в сумме этих комбинаций по модулю два: 0110111 +0100110 = 0010001. Если двоичным комбинациям длины q (равномерный код) сопоставить вершины q-мерного куба, то расстояние означает число ребер, отделяющих одну вершину от другой.

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

Наименьшее расстояние между комбинациями данного кода называют кодовым расстоянием. Более полное представление о свойствах кода дает матрица расстояний D, элементы которой равны расстояниям между каждой парой из всех т разрешенных комбинаций. Например, код 000; 001; 010; 111, кодовое расстояние которого d = 1, представляется симметричной матрицей четвертого порядка:

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

Взаимная энтропия

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

При отсутствии помех различий между ансамблями Х и Y не будет, а энтропии передаваемого и принимаемого сообщений будут равны: Н(Х) = Н(Y).

Воздействие помех оценивают условной энтропией Н Y (X). Поэтому получаемое потребителем количество информации на один элемент сообщения равно: Е(Х,Y) = Н(Х) – Н Y (X)

Величину Е(Х,Y) называют взаимной энтропией .

Если ансамбли Х и Y независимы, то это означает, что помехи в канале привели к полному искажению сообщения, т.е. Н Y (X) = Н(Х), а получаемое потребителем количество информации на один элемент сообщения:Е(Х,Y)=0.

Если Х и Y полностью зависимы, т.е. помехи в канале отсутствуют, то Н Y (X) = 0 и Е(Х,Y) = H(Y).

Так как Н Y (X) = Н(Х,Y) – H(Y), то Е(Х,Y) = H(X) + H(Y) – H(X,Y), или

Пример15 : Определите Н(Х) и Е(Х,Y), если Р(х 1 ,y 1) = 0,3; P(x 1 ,y 2) = 0,2;

P(x 2 ,y 3) = 0,1; P(x 3 ,y 2) = 0,1; P(x 3 ,y 3) = 0,25.

Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения.

Пусть энтропии двух источников сообщений Н 1 <Н 2 , а количество информации, получаемое от них одинаковое, т.е. I = n 1 H 1 = n 2 H 2 , где n 1 и n 2 - длина сообщения от первого и второго источников. Обозначим

При передаче одинакового количества информации сообщение тем длиннее, чем меньше его энтропия.

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

При этом доля излишних элементов оценивается коэффициентом избыточности :

Русский алфавит, включая пропуски между словами, содержит 32 элемента (см. Пример), следовательно, при одинаковых вероятностях появления всех 32 элементов алфавита, неопределенность, приходящаяся на один элемент, составляет Н 0 = log 32 = 5 бит

Анализ показывает, что с учетом неравномерного появления различных букв алфавита H = 4,42 бит, а с учетом зависимости двухбуквенных сочетаний H’ = 3,52 бит, т.е. H’< H < H 0

Обычно применяют три коэффициента избыточности:

1) частная избыточность, обусловленная взаимосвязью r’ = 1 - H’/H;

2) частная избыточность, зависящая от распределения r’’ = 1 - H/ H 0;

3) полная избыточность r 0 = 1 - H’/ H 0

Эти три величины связаны зависимостью r 0 = r’ + r’’ - r’r’’

Вследствие зависимости между сочетаниями, содержащими две и больше букв, а также смысловой зависимости между словами, избыточность русского языка (как и других европейских языков) превышает 50% (r 0 =1 - H’/ H 0 = 1 - 3,52/5 = 0,30).

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

Вполне нормальный на вид лазерный диск может содержать внутренние (процесс записи сопряжен с появлением различного рода ошибок) и внешние (наличие физических разрушений поверхности диска) дефекты. Однако даже при наличии физических разрушений поверхности лазерный диск может вполне нормально читаться за счет избыточности хранящихся на нем данных. Корректирующие коды С 1, С 2, Q - и Р - уровней восстанавливают все известные приводы, и их корректирующая способность может достигать двух ошибок на каждый из уровней С 1 и C 2 и до 86 и 52 ошибок на уровни Q и Р соответственно. Но затем, по мере разрастания дефектов, корректирующей способности кодов Рида-Соломона неожиданно перестает хватать, и диск без всяких видимых причин отказывает читаться, а то и вовсе не опознается приводом. Избыточность устраняют построением оптимальных кодов, которые укорачивают сообщения по сравнению с равномерными кодами. Это используют при архивации данных. Действие средств архивации основано на использовании алгоритмов сжатия, имеющих достаточно длинную историю развития, начавшуюся задолго до появления первого компьютера -/еще в 40-х гг. XX века. Группа ученых-математиков, работавших в области электротехники, заинтересовалась возможностью создания технологии хранения данных, обеспечивающей более экономное расходование пространства. Одним из них был Клод Элвуд Шеннон , основоположник современной теории информации. Из разработок того времени позже практическое применение нашли алгоритмы сжатия Хаффмана и Шеннона-Фано . А в 1977 г. математики Якоб Зив и Абрахам Лемпел придумали новый алгоритм сжатия, который позже доработал Терри Велч . Большинство методов данного преобразования имеют сложную теоретическую математическую основу. Суть работы архиваторов: они находят в файлах избыточную информацию (повторяющиеся участки и пробелы), кодируют их, а затем при распаковке восстанавливают исходные файлы по особым отметкам. Основой для архивации послужили алгоритмы сжатия Я. Зива и А. Лемпела . Первым широкое признание получил архиватор Zip . Со временем завоевали популярность и другие программы: RAR, ARJ, АСЕ, TAR, LHA и т. д.В операционной системе Windows достаточно четко обозначились два лидера: WinZip (домашняя страница этой утилиты находится в Internet по адресу http://www.winzip.com) и WinRAR , созданный российским программистом Евгением Рошалем (домашняя страница http://www.rarlab.com). WinRAR активно вытесняет WinZip так как имеет: удобный и интуитивно понятный интерфейс; мощную и гибкую систему архивации файлов; высокую скорость работы; более плотно сжимает файлы. Обе утилиты обеспечивают совместимость с большим числом архивных форматов. Помимо них к довольно распространенным архиваторам можно причислить WinArj (домашняя страница http://www.lasoft-oz.com) . Стоит назвать Cabinet Manager (поддерживает формат CAB , разработанный компанией Microsoft для хранения дистрибутивов своих программ) и WinAce (работает с файлами с расширением асе и некоторыми другими). Необходимо упомянуть программы-оболочки Norton Commander, Windows Commander или Far Manager. Они позволяют путем настройки файлов конфигурации подключать внешние DOS-архиваторы командной строки и организовывать прозрачное манипулирование архивами, представляя их на экране в виде обычных каталогов. Благодаря этому с помощью комбинаций функциональных клавиш можно легко просматривать содержимое архивов, извлекать файлы из них и создавать новые архивы. Хотя программы архивации, предназначенные для MS-DOS, умеют работать и под управлением большинства версий Windows (в окне сеанса MS-DOS), применять их в этой операционной системе нецелесообразно. Дело в том, что при обработке файлов DOS-архиваторами их имена урезаются до 8 символов, что далеко не всегда удобно, а в некоторых случаях даже противопоказано.

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

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

При архивации надо иметь в виду, что качество сжатия файлов сильно зависит от степени избыточности хранящихся в них данных, которая определяется их типом. К примеру, степень избыточности у видеоданных обычно в несколько раз больше, чем у графических, а степень избыточности графических данных в несколько раз больше, чем текстовых. На практике это означает, что, скажем, изображения форматов BMP и TIFF, будучи помещенными в архив, как правило, уменьшаются в размере сильнее, чем документы MS Word . А вот рисунки JPEG уже заранее компрессированы, поэтому даже самый лучший архиватор для них будет мало эффективен. Также крайне незначительно сжимаются исполняемые файлы программ и архивы.

Программы-архиваторы можно разделить на три категории.

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

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

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

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

В В В В В L L L L L А А А А А

В шестнадцатеричной системе

42 42 42 42 42 4С 4С 4С 4С 4С 41 41 41 41 41

Архиватор может представить этот файл в следующем виде (шестнадцатеричном):

01 05 42 06 05 4С 0А 05 41

Это значит: с первой позиции пять раз повторяется символ "В", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "А". Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.

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

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

Код переменной длины позволяет записывать наиболее часто встречающиеся символы и группы символов всего лишь несколькими битами, в то время как редкие символы и фразы будут записаны более длинными битовыми строками. Например, в любом английском тексте буква Е встречается чаще, чем Z, а X и Q относятся к наименее встречающимся. Таким образом, используя специальную таблицу соответствия, можно закодировать каждую букву Е меньшим числом битов и использовать более длинный код для более редких букв.

Популярные архиваторы ARJ, РАК, PKZIP работают на основе алгоритма Лемпела-Зива. Эти архиваторы классифицируются как адаптивные словарные кодировщики, в которых текстовые строки заменяются указателями на идентичные им строки, встречающиеся ранее в тексте. Например, все слова какой-нибудь книги могут быть представлены в виде номеров страниц и номеров строк некоторого словаря. Важнейшей отличительной чертой этого алгоритма является использование грамматического разбора предшествующего текста с расположением его на фразы, которые записываются в словарь. Указатели позволяют сделать ссылки на любую фразу в окне установленного размера, предшествующего текущей фразе. Если соответствие найдено, текущая фраза заменяется указателем на своего предыдущего двойника.

При архивации, как и при компрессировании, степень сжатия файлов сильно зависит от формата файла. Графические файлы, типа TIF и GIF , уже заранее компрессированы (хотя существует разновидность формата TIFF и без компрессии), и здесь даже самый лучший архиватор мало чего найдет для упаковки. Совсем другая картина наблюдается при архивации текстовых файлов, файлов PostScript , файлов BMP и им подобных.