Методы кодирования данных (Программная РАБОТА реализация метода аппаратное кодировки Хаффмана)

Содержание:

Введение

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

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

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

Коды Хаффмана преподаются во всех технических Университетах мира и, не считая того, входят в программку для углубленного исследования информатики в школе.

Потому исследование кодировки информации и способов кодировки, а именно способа кодировки Хаффмана является животрепещущим.

Объект исследования: кодирование и способы кодировки информации.

Предмет исследования: программное приложение, показывающие главные принципы кодировки на примере способа кодировки Хаффмана.

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

1) рассмотреть главные понятия и принципы кодировки информации;

2) изучить способ кодировки Хаффмана,

3) создать методы и программку для реализации программного продукта «Код Хаффмана», с внедрением современной технологии программирования;

Глава 1. Теоретические базы кодировки информации

1.1 Основы и главные понятия кодировки информации

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

Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые композиции. Код - система соответствия меж элементами сообщений и кодовыми комбинациями. Кодер - устройство, осуществляющее кодирование. Декодер - устройство, осуществляющее оборотную операцию, т.е. преобразование кодовой композиции в сообщение. Алфавит - огромное количество вероятных частей кода, т.е. простых знаков (кодовых знаков) X = {xi}, где i = 1, 2,..., m. Количество частей кода - m именуется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность ^[1]знаков данного алфавита именуется кодовой композицией (кодовым словом). Число частей в кодовой композиции - n именуется значностью (длиной композиции). Число разных кодовых композиций (N = mn) именуется объемом либо мощностью кода.

Цели кодировки:

1) Увеличение эффективности передачи данных, за счёт заслуги наибольшей скорости передачи данных.

2) Увеличение помехоустойчивости при передаче данных.

В согласовании с этими целями теория кодировки развивается в 2-ух главных направлениях:

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

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

Научные базы кодировки были описаны К. Шенноном, который изучил процессы передачи информации по техническим каналам связи (теория связи, теория кодировки). При таком подходе кодирование понимается в более узеньком смысле: как переход от представления информации в одной символьной системе к представлению в другой символьной системе. К примеру, преобразование письменного российского текста в код азбуки Морзе для передачи его по телеграфной связи либо радиосвязи. Такое кодирование связано с потребностью приспособить код к применяемым техническим средствам работы с информацией.

Декодирование - процесс оборотного преобразования кода к форме начальной символьной системы, т.е. получение начального сообщения. К примеру: перевод с азбуки Морзе в письменный текст на российском языке.

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

Метод кодировки 1-го и такого же сообщения может быть различным. К примеру, российский текст мы привыкли записывать при помощи российского алфавита. Но то же самое можно сделать, используя британский алфавит. Время от времени так приходится поступать, посылая SMS по мобильному телефону, на котором нет российских букв, либо отправляя электрическое письмо на российском языке из-за границы, если на компьютере нет русифицированного программного обеспечения. К примеру, фразу: «Здравствуй, дорогой определенная Саша!» приходится Баумана писать так: «Zdravstvui, помехами dorogoi Sasha!».

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

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

им Очередное принципиальное другими событие: выбор поле метода кодировки последующее информации может полной быть связан с представлению предполагаемым методом оказывается её обработки. отвечается Покажем это ясно на примере Ind представления чисел - кодирующих количественной информации. ветви Используя российский уже алфавит, можно скрытый записать число «тридцать удовлетворяет пять». Используя многих же алфавит набор арабской десятичной многоуровневого системы счисления, различные пишем: «35». 2-ой метод числовым не только рассмотреть лишь короче Вильямс первого, да и соответствие удобнее для Основы выполнения вычислений. консультативный Какая запись закодированного удобнее для лежат выполнения расчетов: «тридцать 5 программку помножить на 100 20 минимально семь» либо «35 х 127»? префиксными Разумеется - 2-ая.

Но состоящий если принципиально распознавание сохранить число показано без преломления, Знаки то его равна лучше записать в смысла текстовой форме. К они примеру, в валютных именуемых документах нередко узла сумму записывают в записывается текстовой форме: «триста 70 5 использующие руб.» заместо «375 Очевидно руб.». Во 2-м какие случае искажение подстроку одной числа путей изменит все Коды значение. При Матричное использовании текстовой изучил формы даже длиной грамматические ошибки Баджетт могут не численно поменять смысла. К стенограмме примеру, безграмотный обусловится человек написал: «Тристо сжатие семдесять пят приобретенных руб.». Но РАБОТА смысл сохранился.^[3]

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

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

Главным критерий свойством случайных всякую событий является МККТТ отсутствие полной соответственного уверенности в их Начнем наступлении, создающее многоуровневого известную неопределенность применен при выполнении списка связанных с этими Покажем событиями опытов. Декодер Однако совершенно вхождением ясно, что ПК степень этой распространение неопределенности в различных случаях случаях будет или совершенно разной. представляющий Для практики проведен важно уметь Баскаков численно оценивать одновременном степень неопределенности Но самых разнообразных задач опытов, чтобы историю иметь возможность Иванова сравнить их с реализовано этой стороны. два Рассмотрим два даже независимых опыта и а Рассмотрим также сложный безупречное опыт , состоящий в уменьшает одновременном выполнении были опытов и. Пусть обозначать опыт имеет k используем равновероятных исходов, а Описание опыт имеет l самому равновероятных исходов. then Очевидно, что Некие неопределенность опыта самый больше неопределенности Таким опыта, так времени как к неопределенности инкрементировал здесь добавляется популярностью еще неопределенность dorogoi исхода опыта . наступлении Естественно считать, повторяющийся что степень префиксом неопределенности опыта равна последующие сумме неопределенностей, Введение характеризующих опыты и, т.е.

.

изд Условиям:

,

при построен удовлетворяет только Все одна функция - :

.

ил Рассмотрим опыт А, Такое состоящий из трудности опытов и имеющих во вероятности . Тогда кодового общая неопределенность нет для опыта А целей будет равна:

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

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

длинноватого Мы рассмотрим ребер тут только связи простой случай приложение сообщений, записанных с цифрового помощью неких п «букв», программное частоты проявления левому которых на выполнения любом месте смысл сообщения стопроцентно стенографист характеризуется вероятностями р1, р2, … …, Прослеживаем рп, где, преподаются очевидно, р1 + р2 + … + рп = 1, ОБРАЗОВАТЕЛЬНОЕ при котором граф возможность pi просто проявления i-й буквы xi на любом периода месте сообщения статьей подразумевается одной и обыкновенные той же, требуется вне зависимости показываются от того, Стоимость какие буквы групповых стояли на обеспечивает всех прошлых человек местах, т.е. поочередные Условиям буквы сообщения добавить независимы друг кодер от друга. способе По сути в развивается реальных сообщениях корень это почаще многочленов бывает не десятичной так; а именно, в столбцов российском языке Святослав возможность возникновения запускает той либо помещаются другой буквы преломления значительно находится в реальных зависимости от высочайшей предшествующей буквы. вес Но серьезный правые учёт обоюдной кодировке зависимости букв неопределенностей сделал бы Построение все дельнейшие пропускной рассмотрения очень работу сложными, но узлами никак не весом изменит будущие Целью результаты.^[4]

Мы изучить будем пока принципиально рассматривать двоичные Создается коды; обобщение следующего приобретенных при по всем этом них результатов на тему коды, использующие кодового случайное число т статистический простых сигналов, представлению является, как представить обычно, очень углубленного обычным. Начнем с испытано простого варианта сообщению кодов, сопоставляющих среднее отдельное кодовое Но обозначение - последовательность равной цифр 0 и 1 - каждой «букве» местах сообщения. Каждому периода двоичному коду разрядов для п-буквенного алфавита относительной может быть Во сопоставлен некий поначалу способ отгадывания сделанного некого загаданного Borland числа х, не единицей превосходящего п, с помощью понимается вопросов, на экономного которые отвечается предстоящей только «да» (1) либо «нет» (0) , кодировкой что и приводит коде нас к двоичному программку коду. При строить данных вероятностях р1, р2, … …, затратить рп отдельных пользующийся букв передача таких многобуквенного сообщения применена более экономичный работают код будет представление тот, для такого которого при exit этих конкретно просматривать вероятностях п значений х Двоичные среднее значение декодирование числа задаваемых даже вопросов (двоичных символов: 0 и 1 Связной либо простых Все сигналов) оказывается называть минимальным.

Сначала, профилей среднее число уметь двоичных простых неопределенностей сигналов, приходящихся в сопоставлен закодированном сообщении технических на одну цель буковку начального рассмотрения сообщения, не ввел может быть находил меньше Н, где Н = - p1 вправо log p1 - p2 log p2 - … - Фундаментальные pn log учеб pn - энтропия Обширное опыта, состоящего в которое распознавании одной родителю буквы текста (либо, приобретенные короче, просто Создается энтропия одной экономного буквы). Отсюда кодов сходу следует, энтропия что при вниз любом способе малого кодировки для дозволит записи длинноватого один сообщения из М информацию букв требуется больше не меньше знака чем МН вероятностей двоичных символов, и убывания никак не один может превосходить 1-го содержит бита.

Если смысле вероятности р1, р2, … …, рп ВЫСШЕГО не все Прослеживаем равны меж достоверность собой, то Н < группы log n; потому заканчивается естественно мыслить, служит что учёт УНИВЕРСИТЕТ статистических закономерностей учеб сообщения может введенных позволить выстроить границы код более данной экономный, чем берут лучший равномерный разновидности код, требующий году более М log n узел двоичных символов среднюю для записи операцию текста из М получаем букв.

1.2 Классификация разряд предназначения и методы которых представления кодов

разные Коды можно исправляющих систематизировать по все разным признакам:

1. при По основанию (количеству Введение знаков в алфавите): связанные бинарные (двоичные m=2) и не путь бинарные (m № 2).

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

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

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

5. Зависимо алфавите от предназначения и очень применения условно десятичный можно выделить Владея последующие типы Отсюда кодов:

Внутренние число коды - это работают коды, применяемые находится снутри устройств. российский Это машинные устранения коды, также while коды, базирующиеся впереди на использовании финала позиционных систем выполнению счисления (двоичный, десятичный, месте двоично-десятичный, восьмеричный, стер шестнадцатеричный и др.). Исследованы Более всераспространенным весь кодом в ЭВМ качествах является двоичный условно код, который Хаффмана позволяет просто лучший воплотить аппаратное процесса устройства для списка хранения, обработки и сопоставлять передачи данных в семдесять двоичном коде. представления Он обеспечивает убывания высшую надежность УЧРЕЖДЕНИЕ устройств и простоту отрицательным выполнения операций функции над данными в равной двоичном коде. канал Двоичные данные, буквенно объединенные в группы Но по 4, образуют разрешенных шестнадцатеричный код, узла который отлично смысла согласуется с архитектурой количество ЭВМ, работающей с начальных данными кратными б (8 других бит).

Коды иллюстрируют для обмена предложен данными и их закрытия передачи по экономичный каналам связи. Фано Обширное распространение в знаки ПК получил Одной код ASCII (American Морзе Standard Code именовать for Information УНИВЕРСИТЕТ Interchange). ASCII - repeat это 7-битный код экономный буквенно-цифровых и других соответствует знаков. Так элементарных как ЭВМ УНИВЕРСИТЕТ работают с б, то 8-й используемой разряд употребляется объектно для синхронизации устранения либо проверки кодовыми на четность, могут либо расширения нулей кода. В ЭВМ применены компании IBM устрой употребляется расширенный ясно двоично-десятичный код история для обмена нулю информацией EBCDIC (Extended Целью Binary Coded определенная Decimal Interchange присвоено Code). В каналах Расшифровать связи обширно изредка употребляется телетайпный нулей код МККТТ (интернациональный словами консультативный комитет среде по телефонии и стоимости телеграфии) и его левому модификации (МТК и др.).

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

десятичный Коды для поставленные особых применений - всего это коды, букву созданные для исхода решения особых Университетах задач передачи и одну обработки данных. Увеличение Примерами таких какому кодов является программного повторяющийся код статьей Грея, который Interchange обширно употребляется в таблица АЦП угловых и коды линейных перемещений. данная Коды Фибоначчи система употребляются для задачки построения быстродействующих и дерево помехоустойчивых АЦП.^[5]

сумме Зависимо от Узел используемых способов описанного кодировки, употребляют подготовки разные математические простоту модели кодов, да при всем дозволит этом более позволить нередко применяется самый представление кодов в оказывается виде: кодовых Увеличение матриц; кодовых они деревьев; многочленов; сообщениях геометрических фигур и т.д. АЦП Рассмотрим главные Memo методы представления лучшего кодов.

Матричное изучил представление кодов. связанных Употребляется для оборотного представления равномерных n - будит значных кодов. таблицу Для простого (полного и Ветки равномерного) кода двой матрица содержит n - условием столбцов и 2n - строк, т.е. состоящего код употребляет именно все сочетания. стандартного Для помехоустойчивых (подкорректирующих, будет обнаруживающих и исправляющих записанных ошибки) матрица Употребляется содержит n - столбцов (n = k+m, приписать где k-число информационных, а m - префиксным число проверочных потоком разрядов) и 2k - строк (где 2k - прибыльный число разрешенных Код кодовых композиций). повторяются При огромных редчайших значениях n и k матрица высшую будет очень почаще массивной, при программ всем этом оперируют код записывается в вводим сокращенном виде. этой Матричное представление числом кодов употребляется, к пос примеру, в линейных программкой групповых кодах, сжимаемое кодах Хэмминга и т.д.

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

1.3 Способ следующего кодировки Хаффмана

позиционных Способ кодировки Галисеев либо сжатия условием информации на столбцов базе двоичных достаточно кодирующих деревьев Саша был предложен Д.А. таблицу Хаффманом в 1952 году программы за длительное человек время до до возникновения современного остается цифрового компьютера. проектирования Владея высочайшей стер эффективностью, он и ci его бессчетные введенного адаптивные версии Не лежат в базе Олифер многих способов, метода применяемых в современных численно методах кодировки. Этот Код Хаффмана собственный изредка употребляется оборотного раздельно, почаще связи работая в связке с символов другими методами источника кодировки. Способ набора Хаффмана является стер примером построения значных кодов переменной качествах длины, имеющих разные наименьшую среднюю направленное длину. Этот свести способ производит основанием безупречное сжатие, набор другими словами информационных сжимает данные setlength до их еще энтропии, если простота вероятности знаков Майерс точно равны независимы отрицательным степеням семь числа 2.

Этот устрой способ кодировки KolSim состоит из 2-ух нулей главных шагов:

· которое Построение рационального Одной кодового дерева.

· животрепещущим Построение отображения следующего код-символ на же базе построенного просит дерева.

Метод вес основан на изображен том, что возрастает некие знаки испытанная из стандартного 256-символьного изображен набора в случайном передать тексте могут repeat встречаться почаще тайнопись среднего периода оценивать повтора, а другие - Поочередно пореже. Как грамматики следует, если приложение для записи следствие всераспространенных знаков считанным использовать недлинные независимы последовательности бит, спроектировано длиной меньше 8, а переменены для записи появляется редчайших знаков - длиной длинноватые, то имеющих суммарный объём наименьшим файла уменьшится. В несколько итоге выходит имеющая классификация данных в недочетом виде дерева («двоичное существенно дерево»).

Пусть A={a1,a2,...,an} - перечня алфавит из n стороны разных знаков, W={w1,w2,...,wn} - неопределенностей соответственный ему бинарных набор положительных блочные целых весов. аппаратное Тогда набор повышающих бинарных кодов C={c1,c2,...,cn}, собой таковой что:

- кодовых ci не левые является префиксом бывшие для cj, УЧРЕЖДЕНИЕ при i!=j; мала (|ci| указать длина кода эта ci) именуется меньший минимально-избыточным префиксным Факультет кодом либо равен по другому Матричное кодом Хаффмана.

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

to Верхушка бинарного наличия дерева, полустепень знак захода которой счёт равна нулю, техники именуется корнем. ci Для других присвоим вершин дерева применен полустепень захода текстовой равна единице.

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

Алфавит Разумеется, что преобразуются цена хранения записывать информации, закодированной с Эти помощью Т-дерева, равна Увеличение сумме длин понятном путей из ЭВМ корня к каждому испытанный листу дерева, применяется взвешенных частотой Баумана соответственного кодового Традиционный слова либо поле длиной взвешенных оперируют путей: , где - простой частота кодового друга слова длины поиском во входном эффективностью потоке. Рассмотрим в Иванова качестве примера одно шифровку знаков в заслуги эталоне ASCII. Но Тут каждый технологии знак представляет Нгуен собой кодовое Кодер слово фиксированной(8 шифровки бит) длины, информации потому цена др хранения обусловится теперь выражением , где W- Граф количество кодовых каждому слов во Иванова входном потоке.

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

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

1. российского Знаки входного ОБРАЗОВАНИЯ алфавита образуют подразумевается перечень свободных передачу узлов. Каждый УНИВЕРСИТЕТ лист имеет найти вес, который разработки может быть четность равен или перемещение вероятности, или письменный количеству вхождений оборотную знака в сжимаемое потом сообщение;

2. Выбираются Кодер два свободных мала узла дерева с программы меньшими весами;

каждому Создается их определила родитель с весом, dorogoi равным их событиями суммарному весу;

длин Родитель добавляется в задаваемых перечень свободных закодировать узлов, а два телеграфной его потомка Тестирование удаляются из НЕГОСУДАРСТВЕННОЕ этого перечня;

получение Одной дуге, граф выходящей из буфер родителя, ставится в столбцов соответствие бит 1, развития другой - бит 0;^[6]

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

Допустим, у теперь нас есть Decimal последующая таблица работы частот.

Табл. 1

15	7	6	6	5
А	Б	В	Г	Д

pn На первом длин шаге из исхода листьев дерева электрическое выбираются два с них наименьшими весами - Г и Д. или Они присоединяются к пуска новому узлу- букву родителю, вес создать которого устанавливается 5+6= 11. вершины Затем узлы Г и Д начальный удаляются из построен списка свободных. Начнем Узел Г соответствует затратить ветви 0 родителя, фактически узел Д - ветви 1.

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

историей На следующем здесь шаге «наилегчайшей» парой правые оказываются узлы Б/В и Г/Д.

именуемых Для них шифровке еще раз Таковой создается родитель, Так теперь уже с АЦП весом 24. Узел Б/В повысить соответствует ветви 0 котором родителя, Г/Д - ветви 1.

массива На последнем имеется шаге в перечне Выбираются свободных осталось Глава только 2 узла - направлениях это узел А и степеням узел Б (Б/В)/(Г/Д). В очередной производилось раз создается передать родитель с весом 39, и достигнута бывшие свободные подходе узлы присоединяются к Баумана различным его именно веткам.

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

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

процессе Для данной каком таблицы знаков было коды Хаффмана языке будут смотреться, давнишнюю как показано в наибольшей табл. 2.

А	01
Б	100
В	101
Г	110
Д	111

Наиболее цель частый символ ясно сообщения А закодирован схожим наименьшим количеством устанавливается бит, а наиболее расположенные редкий символ Д - рассматривать наибольшим. Стоимость буквы хранения кодированного МККТТ потока, определенная малой как сумма считать длин взвешенных надежность путей, определится выводы выражением 15*1+7*3+6*3+6*3+5*3=87, что сопоставлять существенно меньше российских стоимости хранения именуемых входного потока (312).

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

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

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

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

Традиционный опыт метод Хаффмана приспособить имеет один которых значимый недочет. четность Для восстановления родителя содержимого сжатого цикл сообщения декодер приходится должен знать чтобы таблицу частот, очередной которой воспользовался Шенноном кодер. Как ставится следует, длина мыслить сжатого сообщения энтропия возрастает на значение длину таблицы выбирают частот, которая Баскаков должна посылаться отрицательным впереди данных, научного что может всераспространенным свести на Факультет нет все построен усилия по Для сжатию сообщения. обнаруживающих Не считая которое того, необходимость двой наличия полной отлично частотной статистики Матричное до фактически передать кодировки просит 2-ух dorogoi проходов по возможные сообщению: 1-го для поменять построения модели темпе сообщения (таблицы частот и полустепень дерева Хаффмана), таблица другого фактически слово для кодировки.

Глава 2. Программная РАБОТА реализация метода аппаратное кодировки Хаффмана

2.1 менеджмента Описание процесса разные реализации метода вероятностях кодировки Хаффмана

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

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

· разработки Выписываем в ряд расстоянию все знаки состоящими алфавита в порядке KolSim возрастания либо перемещение убывания вероятности бит их возникновения в смотреться тексте;

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

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

находящихся Для того все чтоб найти машинные сколько циклических просто знаков в сообщении и котором какова все проходов сообщения, я рассматривал наступлении введенные знаки подразумевается как единую связан строчку «s», ввел стопроцентно дополнительную переменную лучший для подстроки «st» и было сделал цикл реальных для которого сжимаемое условием выхода длине есть вся length испытанная строчка. этих При помощи Алфавит стандартной функции «pos» последнем находил схожую речью подстроку в строке т.е. Разработка однообразные знаки «st» в первом строке «s». После комбинациями нахождения схожих объединение знаков удалял приписать отысканный, а количество переменные удаленных инкрементировал. устранения Инкремент и является фигур количеством схожих содержит знаков.

Но со каждый испытанный развития знак необходимо Information снова добавить в русифицированного массив с его именовать числовым вхождением. сообщении Для этого уменьшится был применен историей тот же Затем самый массив, Эти но он программирования увеличивался на независимо то количество, перевод которое было за испытано «setlength(a,KolSim)». В «Memo1» вывел слов итог подсчета содержащий знаков.

begin

превосходит Button2.Enabled:=true;

Button1.Enabled:=false;

ЭВМ Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

Олифер st:=s;

KolSim:=0;

всего while length(s)>0 прошлых do

begin

c:=s[1];

j:=0;

соединяющих repeat

i:=pos(c,s);

if i>0 малого then

begin

систематизировать inc(j);

delete(s,i,1);

серьезный end;

until поле not(i>0);

Memo1.Lines.Add(c+" -> "+inttostr(j));

код inc(KolSim);

setlength(a,KolSim);

a[KolSim-1].Simvol:=c;

a[KolSim-1].Kolizestvo:=j;

a[KolSim-1].R:=-1;

a[KolSim-1].L:=-1;

a[KolSim-1].x:=1;

Конечная end;

Дальше изредка находим два строке меньших элемента равна массива. Для уровнях этого были Прослеживаем переменены две or переменные Ind1 и соединяющий Ind2 - начальные независимых листья дерева. данная Им было групповых присвоено значение «-1» т.е чтении они пустые. Шеннона Обусловил цикл собственный прохождения по ряд массиву, и ввел количеством еще две принципиально переменных малого Хаффманом значения: MinEl1 состоит MinEl2. Эти полученных элементы мы и IBM находим, но превосходить для каждого валютных создаем собственный информационных цикл нахождения:

шифруется repeat

MinEl1:=0;

пропускной MinEl2:=0;

Ind1:=-1;

таком Ind2:=-1;

for i:=0 сообщении to KolSim-1 программное do

if (a[i].x<>-1) позволяющих and ((a[i].Kolizestvo<MinEl1) or (MinEl1=0)) малой then

begin

вся Ind1:=i;

MinEl1:=a[i].Kolizestvo;

очередное end;

for i:=0 переменной to KolSim-1 значений do

if (Ind1<>i) поочередные and (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl2) введенную or (MinEl2=0)) then

каждой begin

Ind2:=i;

проверки MinEl2:=a[i].Kolizestvo;

end;

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

их if (MinEl1>0) and (MinEl2>0) называть then

begin

кодирующих inc(KolSim);

setLength(a,KolSim);

a[KolSim-1].Simvol:="";

a[KolSim-1].Kolizestvo:=MinEl2+MinEl1;

a[KolSim-1].R:=Ind1;

a[KolSim-1].L:=Ind2;

a[Ind1].x:=-1;

a[Ind2].x:=-1;

Они end;

until превосходить not((MinEl1>0) and (MinEl2>0));

который Сейчас всю всякую информацию выведем в « Memo2 », а длину всего сообщения в « Еdit2».

for i:=0 to KolSim-1 do

begin

Memo2.Lines.Add(" s-> "+a[i].Simvol);

Memo2.Lines.Add("Veroat -> "+inttostr(a[i].Kolizestvo));

Memo2.Lines.Add("R -> "+inttostr(a[i].R));

Memo2.Lines.Add("L -> "+inttostr(a[i].L));

Memo2.Lines.Add("------------------------");

end;

Edit2.Text:=inttostr(KolSim);

Рис. 2.1. Отображение информации в полях

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

Индексами были помечены все правые и левые ветки дерева. Рекурсия будет просматривать все дерево, начиная с корня. Если будем идти по правой ветки, то расстоянию от уза до узла присвоим 0, по левому - 1. Ветки буду просматриваться до того времени пока не будет достигнуто начальных листьев «-1 » (знаков).

После заслуги «-1» рекурсия завершает работу и выводит приобретенный итог в Memo3 (рис. 2.2).

Memo3.Lines.Add(a[Ind].Simvol+" -> "+s);

exit;

end;

if a[Ind].R<>-1 then

f(a[Ind].R,s+"0");

if a[Ind].L<>-1 then

f(a[Ind].L,s+"1");

Рис. 2.2. Приобретенный итог кодировки

Таким макаром, мы программно реализовали метод кодировки Хаффмана в объектно-ориентированной технологии программирования, при помощи среды разработки Borland Delphi 7.0. на языка программирования Delphi.

2.2 Интерфейс юзера приложения «Код Хаффмана»

На рис. 2.3 «Приложения код Хаффмана» изображена основная форма сделанного нами программного продукта «Код Хаффмана».

На форме находятся последующие элементы:

Edit1 - «Строка» для ввода сообщения которое необходимо закодировать.

Edit2 - «Длинна» служит для отображения длины всего массива т.е. индекса массива - это объединение 2-ух знаков с меньшими вероятностями.

Memo1 - служит для отображения количество вхождений каждого знака в сообщение введенное в Edit1 - «Строка».

Memo2 - служит для отображения индексов нового узла (ячейки) массива и из каких частей он состоит.

Memo3 - служит для отображения кодов каждого уникального знака введенного в Edit1 - «Строка».

Кнопка «Определить» - запускает работу метода построения дерева.

Кнопка «Освободить» - высвобождает весь массив и поля для предстоящей работы с программкой.

Кнопка «Кодирование» - запускает работу метода который кодирует строчку введенную в Edit1 и выводит бинарный код для каждого уникального знака введенного в Edit1.

Кнопка «Закрыть» - заканчивает работу программы.

Рис. 2.3. «Приложения код Хаффмана»

Для пуска и работы программы «Код Хаффмана» нужно скопировать откомпилированный exe - файл который находится на СD-диске в всякую из директорий жесткого диска компьютера либо флеш-накопителя. Для пуска необходимо открыть файл «Код Хаффмана.exe» двойным щелчком мыши.

Рис. 2.4. «Пример работы приложения»

На рис 2.4 «Пример работы приложения» изображен пример работы программы «Код Хаффмана». В поле «Строка» мы вводим сообщении в данном случаи «привет», которое будит закодировано. Дальше жмем на кнопку «Определить» и лицезреем что в поле «Длинна» отображается длина всего массива, в поле Memo1 отображается количество вхождений каждого знака в сообщение введенное в поле «Строка», а в Memo2 отображается индекс нового узла (ячейки) массива и из каких частей он состоит. Дальше для получения кода знаков введенных в поле «Строка» необходимо надавить на кнопку «Кодирование» и в поле Memo3 показываются бинарные коды знаков. Для закрытия программы жмем на форме подобающую кнопку «Закрыть».^[7]

Заключение

В процессе научного исследования по теме «Кодирование информации. Кодирование по способу Хаффмана» был проведен анализ литературы, статьей по исследуемой теме, исследована нормативная документация, спроектировано и реализовано программное приложение.

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

Рассмотрены главные понятия и принципы кодировки информации;

Исследован способ кодировки Хаффмана.

Исследованы методы кодировки информации для реализации программного продукта «Код Хаффмана», с внедрением современной технологии программирования;

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

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

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

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

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

программный кодирующий хаффман

Список использованной литературы

1. Баскаков, Святослав Иванович. Радиотехнические цепи и сигналы: учеб. / Баскаков, Святослав Иванович. - 5-е изд., стер. - М.: Высш. шк., 2005. - 462c.: ил. - Библиогр.: с. 457-459. - ISBN 5-06-003843-2.
2. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с.
3. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев - М.: Вильямс, 2004. - 288с.
4. Гмурман, Владимир Ефимович. Теория вероятностей и математическая статистика: учеб. пособие / Гмурман, Владимир Ефимович. - 12-е изд., перераб. - М.: Высш. шк., 2008. - 479c.
5. Иванова Г.С. Разработка программирования / Г.С. Иванова - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 320с.
6. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен - Киев: ДиаСофт, 2005. - 544с.
7. Ланских В.Г.: Основы построения информационных сетей: учебно-методическое пособие по выполнению лабораторных работ для студентов направления 220400 «Управление и информатика в технических системах» всех профилей подготовки, всех форм обучения / В.Г. Ланских. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2012. – 99 с.
8. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с.
9. Меняев М.Ф. Информатика и базы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с.
10. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы: учеб. пос. / Олифер, В. Г., Олифер, Н. А. - 3-е изд. - СПб.: Питер, 2007. - 958c.: ил. - Библиогр.: с. 919-922. - ISBN 5-469-00504-6.

1. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с. ↑

2. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с. ↑

3. Меняев М.Ф. Информатика и базы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с. ↑

4. Меняев М.Ф. Информатика и базы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с. ↑

5. Гмурман, Владимир Ефимович. Теория вероятностей и математическая статистика: учеб. пособие / Гмурман, Владимир Ефимович. - 12-е изд., перераб. - М.: Высш. шк., 2008. - 479c. ↑

6. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с. ↑

7. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с. ↑