Методы кодирования данных

Методы кодирования

Б) Классификационные методы

Эти методы ориентированы на проведение предварительной классификации объектов на основе иерархической или фасетной классификации. Включают следующие 2 подхода:

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

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

Решение задачи. Припишем коды из примера 4 раздела Регистрационные методы вершинам классификатора (коды приписаны вершинам справа и выделены жирным стилем; для упрощения рисунка показаны только оценки со значениями 4 и 5):

Тогда, например, для класса студентов из группы ВС, получивших оценку 5 на экзамене по информатике, сформируем код: 1.1.#, где точка играет роль разделителя.

  • параллельное кодирование. Используется для фасетной классификации. Фасеты кодируются с использованием регистрационного кода, между кодами разных уровней возможны разделители.

Пример 7. Выполнить параллельное кодирование для класса со следующими значениями классификационных признаков (при построении кода учитывается и порядок признаков):

название дисциплины = физика;

шифр учебной группы = АС;

оценка за экзамен = 4.

При решении задачи использовать коды признаков, полученные при порядковом кодировании из примера 4 раздела Регистрационные методы.

В результате решения задачи имеем код: 3.2.$, где точка играет роль разделителя.

life-prog.ru

1

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

Порядковый метод кодирования

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

- обеспечивает довольно большую долговечность классификатора при незначительной избыточности кода;

- обладает наибольшей простотой, использует наиболее короткие коды и лучше обеспечивает однозначность определения каждого объекта классификации;

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

- отсутствие в коде какой-либо конкретной информации о свойствах объекта;

-  сложность машинной обработки информации при получении итогов по группе объектов классификации с одинаковыми признаками;

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

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

Серийно-порядковый метод кодирования

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

- наличие в  каждой серии, кроме кодов имеющихся объектов классификации, определенного  количества кодов для резерва, резерв кодов располагается в середине или в конце серии

целесообразно применять для объектов, имеющих два соподчиненных признака

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

Классификационные методы кодирования

Последовательный метод кодирования

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

- логичность построения кода;

- обладает всеми недостатками, присущими иерархическому методу классификации;

- ограниченные  возможности идентификации объектов;

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

- сложность  группировки  объектов по различным сочетаниям имеющихся признаков;

-  практически невозможно вносить новые признаки и производить изменения в коде без  коренной перестройки классификатора

чаще всего используется при иерархическом методе классификации; применять метод  целесообразно в тех случаях, когда набор признаков классификации и их последовательность стабильны в течение длительного времени

Параллельный метод кодирования

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

- гибкость структуры кода, обусловленная блочностью его построения;

- возможность использовать при решении конкретных технико-экономических и социальных задач коды только тех признаков объектов, которые необходимы, что дает возможность работать в каждом отдельном случае с кодами небольшой длины;

- возможность группировки объектов по любому сочетанию признаков;

- наглядность кодовой комбинации (легко указать, набором каких характеристик  описывается рассматриваемый объект);

- набор признаков при необходимости может легко пополняться присоединением кода нового признака

 хорошо приспособлен для машинной обработки информации

Общероссийские классификаторы технико-экономической и социальной информации

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

Классификаторы ТЭиСИ являются нормативными документами. Классификатор содержит систематизированный свод наименований объектов, представленных как классификационные группировки, и присво­енные им коды.

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

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

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

По сфере действия выделяют следующие виды классификато­ров: международные, общегосударственные (общесистемные), отраслевые и локальные классификаторы.

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

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

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

gosisis.narod.ru

Методы кодирования

Дата добавления: 2013-12-24; просмотров: 3592; Нарушение авторских прав

Комбинированные фасетно-иерархические классификации.

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

РАЗРАБОТКА КЛАССИФИКАТОРОВ ТЕХНИКО-ЭКОНОМИЧЕСКОЙ И СОЦИАЛЬНОЙ ИНФОРМАЦИИ

Согласование и утверждение технических условий

Приложения

В разделе устанавливают права и обязанности изготовителя по гарантиям в соответствии с ГОСТ 22352.

В приложении к ТУ, при необходимости, приводят:

- перечень документов (стандартов, инструкций, ТУ и других документов), на которые даны ссылки в данных ТУ;

- перечень оборудования (стендов, приборов, приспособлений, оснастки, инструмента, посуды и др.) материалов и реактивов, необходимых для контроля продукции;

- краткое описание с характеристиками оборудования, материалов и реактивов, необходимых для контроля продукции;

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

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

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

Разработчик согласовывает с заказчиком (потребителем) ТУ и вместе с другими документами, подлежащими согласованию на приёмочной комиссии, направляет их не позднее чем за 1 месяц до начала её работы в организации (предприятия), представители которых включены в состав приёмочной комиссии – по ГОСТ Р 15.201.

ТУ, содержащие требования, относящиеся к компетенции органов государственного контроля и надзора, если они не являются членами приёмочной комиссии, подлежат согласованию с ними.

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

Рассмотрение ТУ, представленных на согласование, не должно превышать 20 дней с момента поступления их в организацию.

Согласование ТУ оформляют подписью руководителя (заместителя руководителя) согласующей организации под грифом «СОГЛАСОВАНО» или отдельным документом (актом приёмочной комиссии, письмом, протоколом и т. п.), при этом под грифом «СОГЛАСОВАНО» указывают дату и номер документа. При согласовании не допускается запись «Согласовано с замечаниями».

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

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

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

ТУ утверждает разработчик ТУ.

Утверждение ТУ (изменений к ним) оформляют подписью руководителя (заместителя руководителя) разработчика под грифом «УТВЕРЖДАЮ» на титульном листе документа.

ТУ утверждают как правило, без ограничения срока действия.

Ограничение срока действия ТУ устанавливают, при необходимости, по согласованию с заказчиком (потребителем).

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

- индекса “ТУ”;

- четырехразрядного кода группы продукции по ОКП (Общероссийский классификатор продукции);

- трехразрядного регистрационного номера, присваиваемого разработчиком;

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

- года утверждения документа (до 2000г. – двух последних цифр).

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

ПРИМЕР: ТУ 4311-182-38576434-92 (АБВГ.523142.025),

4311 – код группы продукции по ОКП,

38576434 - код предприятия по ОКПО.

(ПРАВИЛА ПО СТАНДАРТИЗАЦИИ. ОСНОВНЫЕ ПОЛОЖЕНИЯ ЕДИНОЙ СИСТЕМЫ КЛАССИФИКАЦИИ И КОДИРОВАНИЯ ТЕХНИКО-ЭКОНОМИЧЕСКОЙ И СОЦИАЛЬНОЙ ИНФОРМАЦИИ И УНИФИЦИРОВАННЫХ СИСТЕМ ДОКУМЕНТАЦИИ В РОССИЙСКОЙ ФЕДЕРАЦИИ. ПР 50.1.019-2000. Дата введения 1 апреля 2001 года)

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

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

Термины:

Классификация – разделение множества объектов на подмножества по их сходству или различию в соответствии с принятыми методами классификации.

Объект классификации – элемент классифицируемого множества.

Признак классификации – свойство или характеристика объекта классификации, по которому проводится классификация.

Классификационная группировка – подмножество объектов, полученное в результате классификации.

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

Глубина классификации – число ступеней классификации.

Кодирование – присвоение кода классификационной группировке или объекту классификации.

Алфавит кода – система знаков (символов), принятых для образования кода.

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

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

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

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

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

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

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

Общероссийский классификатор (ОК)– классификатор, принятый Госстандартом России и обязательный для применения при межотраслевом обмене информацией.

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

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

Международная классификация –классификация, принятая международной организацией.

Ведение классификатора– поддержание классификатора в достоверном состоянии и информационное обслуживание заинтересованных или юридических лиц.

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

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

Унифицированная форма документа (УФД)– созданная с использованием методов унификации документации совокупность реквизитов, установленных в соответствии с решаемыми в данном виде экономической деятельности задачами и расположенных в определенном порядке на носителе информации.

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

Общероссийская унифицированная форма документа- унифицированная форма документа, входящая в состав общероссийской унифицированной системы документации и обязательная для применения на всей территории Российской Федерации в определенном виде экономической деятельности.

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

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

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

- общероссийские классификаторы технико-экономической и социальной информации (далее общероссийские классификаторы);

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

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

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

Задачи ЕСКК:

- создание условий для формирования единого информационного пространства на территории РФ;

- систематизация информации по единым классификационным правилам и их использование при прогнозировании социально экономического развития страны и ведении учета и отчетности;

- информационное обеспечение налогообложения, лицензирования, квотирования, операций с недвижимостью, социального страхования, финансового посредничества;

- содействие специализации и кооперированию в области производства продукции и оказываемых услуг;

- упорядочение стандартизации и сертификации выпускаемой продукции и оказываемых услуг;

- создание условий для унификации документации при осуществлении межотраслевого документооборота;

- обеспечение совместимости информационных систем и ресурсов;

- обеспечение межотраслевого обмена информационными ресурсами;

- гармонизация ЕСКК с международными и региональными классификациями и со стандартами.

В зависимости от области применения классификаторы подразделяются на следующие категории:

- общероссийские классификаторы;

life-prog.ru

Методы кодирования данных. — Студопедия

Кодирование данных двоичным кодом

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

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

Своя система существует и в вычислительной технике — она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1. Эти знаки называются двоичными цифрами, по-английски — binary digit или сокращенно hit (бит).

Одним битом могут быть выражены два понятия: 0 или 1 (да или нет, черное или белое, истина или ложь и т. п.). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия:

00 01 10 11

Тремя битами можно закодировать восемь различных значений:

000 001 010 011 100 101 110 111

Увеличивая на единицу количество разрядов в системе двоичного кодирования, мы увеличиваем в два раза количество значений, которое может быть выражено в данной системе, то есть общая формула имеет вид:

N=2,

где N— количество независимых кодируемых значений;

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

studopedia.ru

Методы оптимального кодирования. Сжатие данных.

Методы оптимального кодирования. Сжатие данных. - раздел Философия, Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников Процедуру Оптимального Кодирования Часто Называют Сжатием Данных. Та...

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

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

1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя.

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

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

Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов XX века) мало использовалась в компьютерной технике.

Методы (алгоритмы) сжатия данных без потерь можно разделить на:

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

2.Адаптивные методы. Например, модифицированное кодирование Хаффмана, арифметическое кодирование. Здесь распределение вероятностей символов вначале считается равномерным на заданном интервале, а потом оно меняется во времени по мере накопления статистики.

3.Динамические методы (алгоритмы). Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела-Зива. LZ77 …LZW.

allrefs.net

ктн Е. В. Курапова, кф-мн Е. П. Мачикина

Основные методы кодирования данных: Методические указания. / Сиб. гос. ун-т телекоммуникаций и информатики. – Новосибирск, 2010. – 54 с.

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

Рисунков ¾13, таблиц ¾ 8. Список лит. –6 назв.

Кафедра прикладной математики и кибернетики.

Рецензент:

телекоммуникаций и информатики, 2010 г.

3. Кодирование целых чисел.. 8

3.1 Коды класса Fixed + Variable 8

3.2 Коды класса Variable + Variable 9

3.3 Кодирование длин серий 11

4. Некоторые теоремы ПОБУКВЕННОГО кодирования.. 12

5. оптимальное ПОБУКВЕННОЕ кодирование. 16

5.1 Основные понятия 16

5.2 Оптимальный код Хаффмана 19

6. почти оптимальное кодирование. 23

6.1 Код Шеннона 23

6.3 Алфавитный код Гилберта – Мура 26

7. арифметический код.. 29

8. адаптивные методы кодирования.. 34

8.1 Адаптивный код Хаффмана 35

8.2 Код «Стопка книг» 38

8.3 Интервальный код 40

9. словарные коды класса Lz. 45

9.1 Кодирование с использованием скользящего окна 46

9.2 Кодирование с использованием адаптивного словаря 47

Лабораторные работы.. 53

Приложение А.. 61

1.  ВВЕдение

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

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

2.  Необходимые понятия и определения

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

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

1.  представление данных произвольной структуры (числа, текст, графика) в памяти компьютера;

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

3.  сжатие информации в базах данных.

Основной моделью, которую изучает теория информации, является модель системы передачи сигналов:

Рисунок 1 Модель системы передачи сигналов

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

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

Пример. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

Далее будем рассматривать двоичное кодирование, т. е. размер кодового алфавита равен 2. Конечную последовательность битов (0 или 1) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Пример. Код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.

Дадим строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех сообщений в алфавите А обозначим S. Тогда отображение , которое преобразует множество сообщений в кодовые слова в алфавите В, называется кодированием. Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.

Задача кодирования сообщения ставится следующим образом. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными. Приведем некоторые из них:

1.  существование декодирования;

2.  помехоустойчивость или исправление ошибок при кодировании: декодирование обладает свойством , β~β¢ (эквивалентно β¢ с ошибкой);

3.  обладает заданной трудоемкостью (время, объем памяти).

Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше символов, где m – размер исходного алфавита, n – размер кодового алфавита.

Пример. Для кодирования источника, порождающего 26 букв латинского алфавита, равномерным двоичным кодом требуется построить кодовые слова длиной не меньше =5 бит.

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

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

Методы сжатия данных можно разделить на две группы: статические методы и адаптивные методы. Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Эти методы базируются на знании статистической структуры исходных данных. К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известные сведения о вероятностях порождения источником различных символов или их сочетаний.

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

Существует множество различных адаптивных методов сжатия данных. Наиболее известные из них – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды, а также методы из класса Лемпела-Зива.

3.  Кодирование целых чисел

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

Основная идея кодирования состоит в том, чтобы отдельно кодировать порядок значения элемента («экспоненту» ) и отдельно – значащие цифры значения («мантиссу» i). Значащие цифры мантиссы начинаются со старшей ненулевой цифры, а порядок числа определяется позицией старшей ненулевой цифры в двоичной записи числа. Как и при десятичной записи, порядок равен числу цифр в записи числа без предшествующих незначащих нулей.

Пример. Порядок двоичного числа равен 4, а мантисса – 1101.

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

  теперь в вашем аккаунте есть возможность создания тестов Проводите тестирования ваших пользователей! добавляйте статьи, новости, фото, контакты, файлы! Открыть сайт
  •   Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы)
  •   Variable + Variable (переменная длина экспоненты + переменная длина мантиссы)

3.1  Коды класса Fixed + Variable

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.

Пример. Пусть R = 15 – количество бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т. к. R≤24. При записи мантиссы можно сэкономить 1 бит: не писать первую единицу, т. к. это всегда будет только единица. Таким образом, количество бит мантиссы меньше на один бит, чем количество бит для порядка.

Таблица 1 Код класса Fixed + Variable

pandia.ru

Статьи по теме