Прямая теорема кодирования. «Теория информации и кодирования

Автор проекта

Третьяк Ксения ученица 7 класса

Зайцева Любовь ученица 7 класса

Тема исследования группы

Трение -друг или враг?

Цели исследования

Выяснить роль трения.

Ход исследования

1.Выяснить природу трения.

2.Роль трения в жизни животных и растений.

3.Роль трения в технике.

4.Трение в нашей жизни.

Результаты проведённого исследования

Природа трения.

Трение – удивительный феномен природы! Оно подарило человечеству тепло и огонь, возможность в короткое время остановить скоростной поезд и автомобиль, ускорить химическую реакцию в сто тысяч раз, записать человеческий голос на пластинку, услышать звуки скрипки и многое другое.В 1883 году знаменитый русский инженер и учёный Николай Павлович Петров писал: «Силу трения можно замечать всегда и повсюду, и её надо поставить в ряду могущественнейших способов, при посредстве которых природа превращает один вид энергии в другой, мало-помалу заменяя их тепловыми. Эта сила обнаруживает своё влияние в самых разнообразных явлениях природы, возбуждая живой интерес учёных самых разнообразных направлений. Знание законов трения необходимо и астроному, и физику, и физиологу, и технику».

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

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

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

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

1)Что Вы знаете о явлении трение?

2) Как Вы относитесь к гололёду, скользким тротуарам и дорогам?

3) Ваши пожелания администрации нашего поселка.

В опросе участвовали люди разных возрастов (60 человек)

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

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

Посыпать дороги и тротуары песком, солью; - сделать хорошее освещение, чтобы были видны опасные места; - ограничить во время гололёда скорость транспорта на улицах; - проводить в школах беседы об оказании первой медицинской помощи в таких случаях; - проводить встречи с инспекторами ГИБДД.

Мы обратились в больницу поселения с просьбой о пострадавших во время гололеда

Мы обратились в ГИБДД за сведениями о дорожно - транспортных проишествиях по вине гололеда.

Вывод

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

Сила трения (Fтр.) - это сила, возникающая при контакте поверхностей двух тел и препятствующая их относительному перемещению. Она появляется за счёт электромагнитных сил, возникающих атомами и молекулами в месте контакта этих двух объектов.

Чтобы остановить движущийся объект, сила должна действовать в противоположную по отношению к направлению движения сторону. Например, если толкнуть книгу через стол, то она начнёт движение. Сила, с которой вы воздействовали на книгу, будет перемещать её. Книга скользит, затем замедляется и останавливается из-за влияния силы трения.

Особенности сил трения

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

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

Виды трения

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

Сила трения скольжения

Где N - сила реакции опоры.

Обратите внимание на некоторые ситуации:

Если человек едет на велосипеде, то трение, возникающее во время контакта колеса с дорогой - трение качения. Такой вид силы значительно меньше по величине силы трения скольжения.

Сила трения качения

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

Шарль Огюстен Кулон в своей работе по теории трения предложил вычислять силу трения качения следующим образом:

где λ - коэффициент трения качения, R - радиус ролика или колеса, P - вес тела.
Представьте себе ситуацию, в которой человек пытается передвинуть с места на место диван. Человек воздействует на диван некоторой силой, но не может его сдвинуть. Это происходит потому, что диван не ускоряется. То есть, результат действия на диван внешних сил равен нулю. Следовательно силу человека компенсирует сила, равная по величине, но направленная в противоположную сторону. Это сила трения покоя.

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

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

Сила трения в жидкостях и газах

Такой вид силы называют силой сопротивления среды. Она замедляет движение объекта. Более обтекаемая форма объекта влияет на величину силы сопротивления - она значительно уменьшается. Поэтому в судостроении используются обтекаемые формы корпусов кораблей или подводных лодок.
Сила сопротивления среды зависит от:

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

Работа добавлена на сайт сайт: 2016-03-30

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. Кодирование информации

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. Основные понятия

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

Пусть A – произвольный алфавит. Элементы алфавита A называют буквами (или символами), а конечные последовательности, составленные из букв, – словами в A . При этом считается, что в любом алфавите существует пустое слово, не содержащее букв.

Слово α 1 называют началом (префиксом) слова α , если существует слово α 2 , такое, что α = α 1 α 2 ; при этом слово α 1 называют собственным началом слова α , если α 2 – не пустое слово. Длина слова – это число букв в слове (пустое слово имеет длину 0). Запись α 1 α 2 обозначает соединение (конкатенацию) слов α 1 и α 2 . Слово α 2 называют окончанием (суффиксом) слова α , если существует слово α 1 , такое, что α = α 1 α 2 ; при этом слово α 2 называют собственным окончанием слова α , если α 1 – не пустое слово. Пустое слово по определению считается началом и окончанием любого слова α .

Рассмотрим алфавит B = {0, 1, …, D – 1}, где D ≥ 2, и произвольное множество C . Произвольное отображение множества C в множество слов в алфавите B называют D -ичным кодированием множества C (при D = 2 кодирование будет двоичным). Обратное отображение называют декодированием. Приведем примеры кодирований.

1. Кодирование множества натуральных чисел, при котором числу n = 0 ставится в соответствие слово e (0) = 0, а числу n ≥ 1 двоичное слово

e (n ) = b 1 b 2 … b l (n )

наименьшей длины, удовлетворяющее условию

Очевидно, что b 1 = 1, 2 l (n ) – 1 ≤ n < 2 l (n ) и, следовательно

l (n ) = + 1 = ]log(n + 1)[,

где [ x ] и ] x [ обозначает соответственно наибольшее целое число, не превосходящее x , и наименьшее целое число, превосходящее x . Слово e (n ) называют двоичной записью числа n , а данное кодирование – представление чисел в двоичной системе счисления. Данное кодирование является взаимно однозначным, поскольку при n 1 ≠ n 2 слова e (n 1 ) и e (n 2 ) различны. В таблице 5.1 приведено представление первых 16 натуральных чисел в двоичной системе счисления.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.1

" xml:lang="ru-RU" lang="ru-RU"> Кодирование " xml:lang="en-US" lang="en-US">e " xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n " xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

2. Кодирование первых 2 k натуральных чисел, при котором каждому числу n (0 ≤ n < 2 k ) ставится в соответствие слово

e k (n ) = 0 k – l (n ) e (n ),

где запись 0 k – l (n ) обозначает слово, состоящее из k – l (n ) нулей, e (n ) – представление числа n в двоичной системе счисления, рассмотренное выше. Данное кодирование для первых 16 натуральных чисел ( k = 4) приведено в таблице 5.2.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5. " xml:lang="en-US" lang="en-US">2

" xml:lang="ru-RU" lang="ru-RU"> Кодирование " xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n " xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e ;vertical-align:sub" xml:lang="en-US" lang="en-US">k " xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n " xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0000	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">0100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">0001	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">0101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">0010	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">0110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">0011	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">0111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

Пусть A = { a i , i = 1, 2, …} – конечный или счетный алфавит, буквы которого занумерованы натуральными числами. В этом случае кодирование букв алфавита A можно задать последовательностью D -ичных слов V = { v i , i = 1, 2, …}, где v i есть образ буквы a i . Такие последовательности слов (из множества V ) называют кодами (алфавита А ). Если задан код V алфавита А , то кодирование слов, при котором каждому слову a i 1 a i 2 … a ik ставится в соответствие слово v i 1 v i 2 … v ik , называют побуквенным кодированием.

При переходе от взаимно однозначного кодирования букв алфавита к побуквенному кодированию слов в алфавите свойство взаимной однозначности может не сохраниться. Например, кодирование e (n ) не сохраняет данное свойство, а кодирование e k (n ) его сохраняет. Свойство взаимной однозначности сохраняют разделимые коды. Код V = { v i , i = 1, 2, …} называют разделимым, если из каждого равенства вида

v i 1 v i 2 … v ik = v j 1 v j 2 … v jl

следует, что l = k и v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = v jl . Разделимые коды называют также однозначно декодируемыми кодами.

К классу разделимых кодов принадлежат префиксные коды. Код V = { v i , i = 1, 2, …} называют префиксным, если никакое слово v k не является началом (префиксом) никакого слова v l , l ≠ k . Если каждое слово префиксного кода заменить наименьшим его началом, которое не является началом других кодовых слов, то полученный код также будет префиксным. Такую операцию называют усечением префиксного кода.

Для произвольного кода V , состоящего из различных слов, можно построить кодовое дерево. Это ориентированный граф, не содержащий циклов, в котором вершина β 1 соединена с вершиной β 2 ребром, направленным от β 1 к β 2 , тогда и только тогда, когда β 2 = β 1 b , где b  B = {0, 1, …, D – 1}, D ≥ 2. Для префиксных кодов (и только для них) множество кодовых слов совпадает с множеством концевых вершин (вершин, из которых не исходят ребра) кодового дерева.

5.2. Основные теоремы кодирования

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

Теорема 5.1. Неравенство Крафта. Для существования однозначно декодируемого (разделимого) кода, содержащего N кодовых слов в множестве {0, 1, D – 1} с длинами n 1 , n 2 , …, n N , необходимо и достаточно, чтобы выполнялось неравенство

Доказательство. Представим, что имеется кодовое дерево для префиксного кода. Корень кодового дерева образует уровень 0, вершины, связанные с корнем, – уровень 1 и т.д. Возможное количество вершин на k -м уровне обозначим как D k . Каждая вершина k -го уровня порождает точно D n – k вершин n -го уровня.

n 1 ≤ n 2 ≤…≤ n N = n .

Очевидно, что кодовое слово длины k запрещает в точности D n – k возможных концевых вершин (вершин последнего уровня). Тогда все кодовые слова префиксного кода запрещают концевых вершин. Так как общее число концевых вершин равно D n , то справедливо неравенство

из которого следует, что

Таким образом, неравенство Крафта доказано.

В результате доказательства теоремы 5.1 делается вывод о том, что существуют хотя бы префиксные коды, которые являются однозначно декодируемыми кодами, с длинами кодовых слов n 1 , n 2 , …, n N , удовлетворяющими неравенству Крафта. Следующая теорема, называемая утверждением Мак-Миллана, обобщает данный вывод на все однозначно декодируемые коды.

Теорема 5.2. Неравенство Мак-Миллана. Каждый однозначно декодируемый код удовлетворяет неравенству Крафта.

Доказательство. Возведем сумму в степень L :

. (5.1)

Пусть A k – число комбинаций, содержащих L кодовых слов с суммарной длиной k . Тогда выражение (6.1) можно представить в виде

где L max – максимальная длина сообщения, содержащего L кодовых слов. Если код является однозначно декодируемым, то все последовательности из L кодовых слов суммарной длины k различны. Так как имеется всего D k возможных последовательностей, то A k ≤ D k и тогда

Так как L – это число независимых кодовых слов, которые используются для построения всех возможных последовательностей длины, не превышающей L max . Поэтому L ≤ L max и. А из этого следует, что

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

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

Теорема 5.3. Теорема кодирования источников I . Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H (X ) существует D -ичный префиксный код, в котором средняя длина кодового слова удовлетворяет неравенству

. (5.2)

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

Для этого используем определение энтропии и неравенство Крафта:

Для доказательства правой части неравенства (6.2) перепишем неравенство Крафта в следующем виде:

Затем выберем для каждого слагаемого такое наименьшее целое n i , при котором

Так как неравенство Крафта при таком выборе сохраняется, то можно построить соответствующий префиксный код. Так как n i – наименьшее целое, то для n i – 1 справедливо

Тогда

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

Теорема 5.4. Теорема кодирования источников II . Для блока длины L существует D -ичный префиксный код, в котором средняя длина кодового слова на один символ удовлетворяет неравенству

где.

Доказательство. Здесь в качестве единиц сообщений рассматриваются блоки символов и H (X 1 , X 2 , …, X L ) – это энтропия источника сообщений, приходящаяся на блок из L символов. Для доказательства теоремы можно воспользоваться теоремой о кодировании источников I :

Теорема о кодировании источников II позволяет утверждать, что существуют такие способы кодирования для достаточно длинного сообщения, что средняя длина кодового слова может быть сделана сколь угодно близкой к величине. Действительно, при L  ∞, H L (X )  H , где H – энтропия источника сообщений на один символ, справедливо неравенство

, (5.3)

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

Кроме того, так как минимально достижимой длиной кодового слова на символ является величина, то при D = 2 избыточность кода можно определить по формуле.

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. Оптимальное кодирование

Задача построения оптимального кода заключается в отыскании целых положительных чисел n 1 , n 2 , …, n N , минимизирующих среднюю длину кодового слова при условии выполнения неравенства Крафта:

При построении кодов в случае алфавита A = { a i , i = 1, 2, …, N } с известным распределением вероятностей P = { p i , i = 1, 2, …, N } без ограничения общности можно считать, что буквы алфавита A занумерованы в порядке убывания их вероятностей, т.е. p 1 ≥ p 2 ≥ … ≥ p N . Кроме того, будем рассматривать только двоичные коды.

Известны два метода (Фано и Шеннона) построения кодов, близких к оптимальным. Метод Фано заключается в следующем. Упорядоченный в порядке убывания вероятностей список букв делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1. Далее точно также поступают с каждой из полученных частей, если она содержит, по крайней мере, две буквы. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве. Каждой букве ставится в соответствие последовательность символов, приписанных в результате этого процесса данной букве. Легко видеть, что полученный код является префиксным.

Метод Шеннона применим лишь в том случае, когда все вероятности положительны. Он состоит в том, что букве a i , имеющей вероятность p i > 0, ставится в соответствие последовательность из n i = ] log (1/ p i )[ первых после дробной точки цифр разложения числа в бесконечную дробь (для a 1 полагаем, что q 1 = 0). Поскольку при l > k (в силу того, что p l ≤ p k ) n l ≥ n k и, то полученный таким образом код является префиксным. На основе полученного префиксного кода строится усеченный префиксный код, который и является результатом кодирования по методу Шеннона.

Пусть, например, имеется множество букв A = { a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 } с распределением вероятностей P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}. Выполним кодирование букв по методу Фано.

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

A 1 = { a 1 , a 2 , a 3 }, P 1 = {0.2, 0.2, 0.19};

A 2 = { a 4 , a 5 , a 6 , a 7 }, P 2 = {0.12, 0.11, 0.09, 0.09}.

2. Припишем буквам из первой части символ 0, а буквам второй части символ 1:

A 1 = { a 1 /0, a 2 /0, a 3 /0} ;

A 2 = { a 4 /1, a 5 /1, a 6 /1, a 7 /1}.

3. Повторим последовательно указанные действия для каждой из частей по отдельности. В результате получим :

A 1 1 = { a 1 /00};

A 121 = { a 2 /010};

A 122 = { a 3 /011};

A 211 = { a 4 /100};

A 212 = { a 5 /101};

A 221 = { a 6 /110};

A 222 = { a 7 /111}.

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

Процесс кодирования по методу Фано удобно оформлять в виде таблицы. Для рассматриваемого примера он приведен в таблице 5.3.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.3

" xml:lang="ru-RU" lang="ru-RU"> Кодирование по методу Фано

" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0.20	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU"> 0	" xml:lang="ru-RU" lang="ru-RU"> 00
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">2	" xml:lang="ru-RU" lang="ru-RU">0.20		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">010
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">3	" xml:lang="ru-RU" lang="ru-RU">0.19			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">011
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">4	" xml:lang="ru-RU" lang="ru-RU">0.12	" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">100
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">5	" xml:lang="ru-RU" lang="ru-RU">0.11			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">101
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">6	" xml:lang="ru-RU" lang="ru-RU">0.09		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">110
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">7	" xml:lang="ru-RU" lang="ru-RU">0.09			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">111

Определим среднюю длину кодового слова:

Теперь выполним кодирование по методу Шеннона. Процесс кодирование приведено в таблице 5.4.

" xml:lang="ru-RU" lang="ru-RU">Таблица 5.4

" xml:lang="ru-RU" lang="ru-RU"> Кодирование по методу Шеннона

" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">n ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">q ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Код " xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Усеченный код " xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="en-US" lang="en-US">i
" xml:lang="en-US" lang="en-US">a ;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="en-US" lang="en-US">]2.321…[ = 3	" xml:lang="en-US" lang="en-US">0	000	000
a 2	]2.321…[ = 3	0.2	001	001
a 3	]2.395…[ = 3	0.4	011	01
a 4	]3.058…[ = 4	0.59	1001	100
a 5	]3.183…[ = 4	0.71	1011	101
a 6	]3.472…[ = 4	0.82	1101	110
a 7	]3.472…[ = 4	0.91	1110	111

Как и предыдущего случая найдем среднюю длину кодового слова:

.

Как можно видеть результаты кодирования по методам Фано и Шеннона с точки зрения минимизации средней длины кода практически совпали. Поэтому часто эти методы рассматривают как один (в формулировке Фано) и называют методом Шеннона-Фано.

В 1952 г. Давид Хаффмен предложил метод оптимального префиксного кодирования для дискретных источников, который в отличие от методов Шеннона и Фано до сих пор применяется на практике. Д.Хаффмен доказал, что средняя длина кодового слова, полученная с помощью его метода, будет минимальна. Кодирование Хаффмена производится за три шага.

1. Упорядочение: буквы располагаются в порядке убывания их вероятностей.

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

3. Кодирование: начиная с последнего объединения, последовательно приписываются одной компоненте составной буквы символ 0, а второй – символ 1; процесс продолжается до тех пор, пока все исходные буквы не будут закодированы.

Выполним кодирование по методу Хаффмена для множества, рассматривавшегося в примерах применения методов Фано и Шеннона.

1. Исходный список букв A = { a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 } уже упорядочен, так как P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Объединим буквы a 6 и a 7 в одну букву a 1 с вероятностью 0.18 и переупорядочим список :

P 1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A 1 = { a 1 , a 2 , a 3 , a 1 , a 4 , a 5 }.

3. Повторим шаг 2 до тех пор, пока не останется одна буква в списке:

P 2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A 2 = { a 2 , a 1 , a 2 , a 3 , a 1 };

P 3 = {0.37, 0.23, 0.2, 0.2}, A 3 = { a 3 , a 2 , a 1 , a 2 };

P 4 = {0.4, 0.37, 0.23}, A 4 = { a 4 , a 3 , a 2 };

P 5 = {0.6, 0.4}, A 5 = { a 5 , a 4 };

P 6 = {1}, A 6 = { a 6 }.

4. Присвоим двоичные коды символам :

a 6 : a 5 = 0, a 4 = 1;

a 5 : a 3 = 00, a 2 = 01;

a 4 : a 1 = 10, a 2 = 11;

a 3 : a 3 = 000, a 1 = 001;

a 2 : a 4 = 010, a 5 = 011;

a 1 : a 6 = 0010, a 7 = 0011.

Таким образом, исходным буквам присвоены следующие двоичные коды: a 1 = 10, a 2 = 11, a 3 = 000, a 4 = 010, a 5 = 011, a 6 = 0010, a 7 = 0011, что дает среднюю длину кода, меньшую, чем в случае кодирования Фано и Шеннона.

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

.

Тогда коды имеют следующую избыточность:

код Фано: ;

код Шеннона: ;

код Хаффмена: .

Таким образом, избыточность кода Хаффмена минимальна.

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

PAGE 43