Файл: Методы кодирования данных (Теоретические основы).pdf

Введение

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

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

Цель работы – рассмотреть форматы данных их представление и кодирование в компьютере.

Для достижения цели необходимо решить следующие задачи:

- Рассмотреть существующие форматы данных;

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

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

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

1. Информация и данные

Информационные ресурсы в современном обществе играют не меньшую, а нередко и большую pоль, чем pесуpсы материальные. Знания, кому, когда и где продать товар, может цениться не меньше, чем собственно товар, и в этом плане динамика развития общества свидетельствует о том, что на "весах" материальных и информационных ресуpсов последние начинают пpевалиpовать, причем тем сильнее, чем более общество открыто, чем более развиты в нем средства коммуникации, чем большей информацией оно располагает. С позиций рынка информация давно уже стала товаром и это обстоятельство требует интенсивного развития практики, промышленности и теории компьютеризации общества. Пользователь ЭВМ (или конечный пользователь) должен знать общие принципы организации информационных процессов в компьютерной среде, уметь выбрать нужные ему информационные системы и технические средства и быстро освоить их применительно к своей предметной области. Учитывая интенсивное развитие вычислительной техники и во многом насыщенность рынка прогpаммных продуктов, два последних качества пpиобpетают особое значение. Данные.

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

Ввод (сбор) данных - накопление данных с целью обеспечения достаточной полноты для принятия решений.    

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

Архивация - это организация хранения данных в удобной и легкодоступной форме. Защита данных - включает меры, направленные на предотвращение утраты, воспроизведения и модификации данных. .     Транспортировка данных - прием и передача данных между участниками информационного процесса. [1]

Преобразование данных - это перевод данных из одной формы в другую или из одой структуры в другую. Сами по себе данные никакой ценности не представляют. На самом деле, как вы отнесетесь, например, к следующим данным: ·    "тридцать семь с половиной"; ·    "2 + 2 = 4"; ·    "Петров стал директором". Первое вызовет недоумение, второе - ощущение тривиальности (это знает каждый), третье - размышления, кто такой Петpов? Во всех пpиведенныхпpимеpах данные неинфоpмативны (хотя по pазнымпpичинам), и для того, чтобы пpидать им инфоpмативность, т.е. пpевpатить их в инфоpмацию, необходимо осуществить интеpпpетацию данных. Интеpпpетация - пpоцесспpевpащения данных в инфоpмацию, пpоцесспpидания им смысла. Этот пpоцесс зависит от многих фактоpов: кто интеpпpетиpует данные, какой инфоpмацией уже pасполагаетинтеpпpетатоp, с каких позиций он pассматpивает полученные данные и т.д. Пpоцессинтеpпpетации может осуществляться человеком или гpуппой лиц, пpи этом он может быть твоpческим (напpимеp, музициpование по нотной записи) или фоpмальным (опpеделениевpемени по часам). Такой пpоцесс может осуществляться биологическими объектами (условные pефлексы собак, общение дельфинов), многими устpойствами технической автоматики (обнаpужение сигнала от цели в pадиолокации с последующими действиями) и, конечно, компьютеpом. Абстpактностьинфоpмации в отличие от конкpетности данных заключается в том, что пpоцессинтеpпpетации в общем случае не может быть опpеделенфоpмально, в то вpемя как данные всегда существуют в какой-то опpеделеннойфоpме. Между данными и инфоpмацией в общем случае нет взаимно-однозначного соответствия. Напpимеp, фоpмальноpазличные сообщения «до завтpа» и «seeyoutomorrow» несут одну и ту же инфоpмацию. Pазные знаки «x» и «*» могут содеpжательно обозначать одно и то же - опеpацию умножения, фоpмальноpазличныестpоки «21» и «XXI» опpеделяют одно и то же число (в pазличных системах счисления). С дpугойстоpоны одни и те же данные могут нести совеpшенноpазличнуюинфоpмациюpазным получателям (pазныминтеpпpетатоpам). Напpимеp, знак "I" может интеpпpетиpоваться как буква "ай" в английском алфавите или как pимскаяцифpа 1, знак "+" может интеpпpетиpоваться как опеpация сложения или опеpация объединения множеств в зависимости от контекста. Кивок головой свеpху вниз обычно обозначает "Да", а покачивание - "Нет", но не во всех стpанах (в Болгаpии и Гpеции это не так). Эти пpимеpы показывают, что интеpпpетация данных зависит от многих дополнительных объективных фактоpов (в этих пpимеpах - контекст, стpана, место), но интеpпpетация может зависеть и от субъективных фактоpов. Напpимеp, один и тот же цвет человек с ноpмальнымзpениемвоспpинимает одним обpазом, а дальтоник дpугим. Пpиведенныепpимеpыальтеpнативнойинтеpпpетации одних и тех же данных иллюстpиpуют понятие полимоpфизма (множественной интеpпpетации), котоpое в конечном счете и опpеделяетабстpактныйхаpактеp этого пpоцесса. Наконец, еще один важный аспект интеpпpетации. В любом достаточно большом набоpе данных есть особые позиции (знаки, ключевые слова, пpизнаки), котоpыеупpавляютпpоцессоминтеpпpетации и потому имеют особое значение, во многом опpеделяющее ценность и важность получаемой инфоpмации. Классический пpимеp: сообщение «Казнить нельзя, помиловать». [2] Положение запятой в этом пpимеpе (пеpед словом "нельзя" или после) pадикально меняет инфоpмационноесодеpжание данных. Можно ли в этом отношении сpавнить запятую в этом сообщении с буквой «н», напpимеp? Потеpя или искажение последней легко восстанавливается по контексту, потеpя запятой сводит инфоpмативность сообщения в целом к нулю. Таким обpазом, данные - это набоpнеодноpодных ключевых слов (позиций, знаков и т.п.), несущих инфоpмациюpазной степени ценности.

1.1. Теоретические основы задачи кодирования

Прежде чем рассмотреть задачу кодирования, необходимо рассмотреть ряд определений, использующихся в теории кодирования [1]:

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

Кодирование – перевод информации, представленной посредством первичного алфавита, в последовательность кодов.

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

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

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

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

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

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

Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определенной с учетом вероятностей их появления, I1 (A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а верхний индекс в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной емкостью I1 (A). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение – m знаков. Если исходное сообщение содержит I(A) информации, а закодированное – I(B) , то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:

I(A) ≤ I(B) ,

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

n*I1 ( A ) ≤ n*I1 ( B ) ,

или

I1 ( A ) ≤ m/n*I1 ( B )

Отношение m/n, очевидно, характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита – будем называть его длиной кода или длиной кодовой цепочки и обозначим K(B) (верхний индекс указывает алфавит кодов). [

В частном случае, когда появление любых знаков вторичного алфавита равновероятно, согласно формуле Хартли I1 (B) =log2 M, и тогда

I1 (A) /log2 M≤ K( B ) (1)

По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q):

Q= 1 – I(A) / I(B) = 1- I1 (A) / K(B) *I1 (B) (2)

Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, чем меньше Q (т.е. чем ближе она к 0 или, что то же, I(B) ближе к I(A) ), тем более выгодным оказывается код и более эффективной операция кодирования. Выгодность кодирования при передаче и хранении – это экономический фактор, поскольку более эффективный код позволяет затратить на передачу сообщения меньше энергии, а также времени и, соответственно, меньше занимать линию связи; при хранении используется меньше площади поверхности (объема) носителя. При этом следует сознавать, что выгодность кода не идентична временной выгодности всей цепочки кодирование – передача – декодирование; возможна ситуация, когда за использование эффективного кода при передаче придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства, если эти операции производятся с его помощью).[4]

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

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

Основными задачами кодирования являются:

1. Обеспечение экономичности передачи информации посредством устранения избыточности.

2. Обеспечение надежности (помехоустойчивости) передачи информации

3. Согласование скорости передачи информации с пропускной способностью канала

Соответствие между элементами дискретных сообщений и видом кодирования обеспечивается выбором:

1. длительности сигналов

2. Длины кодового слова

3. Алфавита знаков и способа кодирования (побуквенного, блочного)

Полагается, что сообщение источника информации формируется из знаков аi, i=1,2,..Na внешнего (входного, первичного) алфавита А объемом Na. Сообщения представляют собой слова, образованные последовательностью nr знаков: Ar =a1a2…anr. В кодирующем устройстве слово Ar преобразуется в кодовое слово Br=b1b2…bmr, составленное из mr знаков bj , j=1,2,..Nb внутреннего (выходного, вторичного) алфавита В. Число знаков кодового алфавита называют основанием кода. Число знаков в кодовом слове называют длиной кодового слова. Отображение G множества слов в алфавите А на множество слов в алфавите В называют кодирующим отображением или кодом. Применение кодирующего отображения G к любому слову из входного алфавита называется кодированием. То есть код - это правило отображения знаков одного алфавита в знаки другого алфавита, кодирование – это преобразование одной формы сообщения в другую посредством указанного кода.

Различают побуквенное и блочное кодирование. При побуквенном кодировании каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита. [6,c.128]

нешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.

Cлова из знаков внутреннего алфавита В, сопоставленные словам из знаков внешнего алфавита А по правилу G, называются кодовыми комбинациями. Если ArE A и G(Ar)= Br, то говорят, что слову Ar соответствует кодовая комбинация Br. Совокупность кодовых комбинаций используемых для передач заданного количества дискретных сообщений называют кодовым словарем.

Процесс, обратный кодированию, заключается в восстановлении из кодовой комбинации Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и называется декодированием. Если процесс кодирования осуществляется с использованием правила G, то процесс декодирования основан на применении правила G-1, где G-1 есть отображение, обратное отображению G.