Кодирование информации в ЭВМ

В новом формате компакт-дисков Audio DVD за одну секунду сигнал измеряется 96 000 раз, т.е. применяют частоту семплирования 96 кГц. Для экономии места на жестком диске в мультимедийных приложениях довольно часто применяют меньшие частоты: 11, 22, 32 кГц. Это приводит к уменьшению слышимого диапазона частот, а, значит, происходит сильное искажение того, что слышно.    

Если в виде графика представить один и тот же звук высотой 1 кГц (нота до седьмой октавы фортепиано примерно соответствует этой частоте), но семплированный с разной частотой (нижняя часть синусоиды не показана на всех графиках), то будут видны различия. Одно деление на горизонтальной оси, которая показывает время, соответствует 10 семплам. Можно видеть, что на частоте 11 кГц примерно пять колебаний звуковой волны приходится на каждые 50 семплов, то есть один период синусоиды отображается всего при помощи 10 значений. Это довольно неточная передача. В то же время, если рассматривать частоту оцифровки 44 кГц, то на каждый период синусоиды приходится уже почти 50 семплов. Это позволяет получить сигнал хорошего качества.[7]    

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

Для кодирования значения амплитуды используют принцип двоичного кодирования. Звуковой сигнал должен быть представленным в виде последовательности электрических импульсов (двоичных нулей и единиц). Обычно используют 8, 16-битное или 20-битное представление значений амплитуды. При двоичном кодировании непрерывного звукового сигнала его заменяют последовательностью дискретных уровней сигнала. От частоты дискретизации (количества измерений уровня сигнала в единицу времени) зависит качество кодирования. С увеличением частоты дискретизации увеличивается точность двоичного представления информации. При частоте 8 кГц (количество измерений в секунду 8000) качество семплированного звукового сигнала соответствует качеству радиотрансляции, а при частоте 48 кГц (количество измерений в секунду 48000) - качеству звучания аудио- CD.    

Если использовать 8-битное кодирование, то можно достичь точность изменения амплитуды аналогового сигнала до 1/256 от динамического диапазона цифрового устройства (28 = 256).    

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

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

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

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

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

Конечно, такая система кодирования позволяет записать далеко не всякий звук, она годится только для инструментальной музыки. Но есть у нее и неоспоримые преимущества: чрезвычайно компактная запись, естественность для музыканта (практически любой MIDI-редактор позволяет работать с музыкой в виде обычных нот), легкость замены инструментов, изменения темпа и тональности мелодии.

Есть и другие, чисто компьютерные, форматы записи музыки. Среди них – формат MP3, позволяющий с очень большим качеством и степенью сжатия кодировать музыку, при этом вместо 18–20 музыкальных композиций на стандартном компакт-диске (CDROM) помещается около 200. Одна песня занимает, примерно, 3,5 Mb, что позволяет пользователям сети Интернет легко обмениваться музыкальными композициями.

Ухо человека воспринимает звук в диапазоне от 20 Гц до 20 КГц (1 Гц - 1 колебание в секунду).[9]

 

7. Алгоритм Хаффмана

 

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

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

Можно представить, что все файлы - это тексты, написанные в алфавите, состоящем из 256 букв (так оно на самом деле и есть). Рассмотрим все множество файлов, размер которых не превышает n byte (где n произвольное число). И допустим, что существует некий алгоритм кодирования, который любой из этих файлов сжимает с "положительной" эффективностью. Тогда множество всех их архивов содержится во множестве всех файлов, размер которых меньше n byte. Согласно нашему предположению существует взаимно-однозначное соответствие между двумя конечными множествами, число элементов в которых не совпадает. Чего быть не может. Отсюда можно сделать довольно значимые выводы: 1) не существует архиватора, который бы одинаково хорошо паковал любые файлы, 2) для любого архиватора найдутся файлы, в результате сжатия которых будут получаться архивы в лучшем случае не меньшего размера, чем исходные файлы. [4]

 

8. Алгоритм кодирования  Лемпеля – Зива

 

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем, Якобом Зивом и Терри Велчем. Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

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

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

  При кодировании:

1. Выбирается первый символ  сообщения и заменяется на  его код.

2. Выбираются следующие  два символа и заменяются своими  кодами. Одновременно этой комбинации  двух символов присваивается  свой код. Обычно это номер, равный  числу уже использованных кодов. Так, если алфавит включает 8 символов, имеющих коды от 000 до 111, то первая  двухсимвольная комбинация получит  код 1000, следующая - код 1001 и т.д.

3. Выбираются из исходного  текста очередные 2, 3,...N символов  до тех пор, пока не образуется  еще не встречавшаяся комбинация. Тогда этой комбинации присваивается  очередной код, и поскольку совокупность  А из первых N-1 символов уже  встречалась, то она имеет свой  код, который и записывается вместо  этих N-1 символов. Каждый акт введения  нового кода назовем шагом  кодирования.

4. Процесс продолжается  до исчерпания исходного текста.

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

 

9. Помехоустойчивые коды

 

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

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

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

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

В 50-е-70-е годы было разработано большое количество алгебраических кодов с исправлением ошибок, среди которых наиболее востребованными стали коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (РС), Рида-Малера, Адамара, Юстенсена, Гоппы, циклические коды, сверточные коды с разными алгоритмами декодирования (последовательное декодирование, алгоритм Витерби), арифметические коды.

Однако на практике применяется относительно небольшая группа алгебраических помехоустойчивых кодов: БЧХ, Рида-Соломона и сверхточные коды. Наиболее широко применяются циклические коды с обнаружением ошибок в стандартных протоколах HDLC, Х.25/2 (LAP-B, LAP-M). Коды Рида-Соломона с исправлением ошибок находят применение в каналах радиосвязи. В каналах спутниковой связи, характеризующихся независимым характером ошибок, широко применяются сверхточные коды .

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

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

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

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

 

10. Теоремы Шеннона

 

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

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

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