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

| | если i<22016

| | | то x:=x+i/22016

| | все

| | вывод x; i:=i+1

| кц

| кончить запись; кончить чтение

кон

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

Кодирование музыкального звука

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

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

Такой объект, как музыкальный звук, имеет 2 свойства:

1)высота звучания. Это свойство кодируется положением нотного значка на нотных линейках. В физическом смысле это - частота колебаний звука.

2)долгота (длительность) звучания. Она кодируется видом ноты (пустая/закрашенная, без штиля/со штилем, без флажка/ с флажками). Это временная характеристика музыкального звука.

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

В некоторых случаях, например, при пении под гитару для записи аккомпанимента используется система аккордов-созвучий. Партия записывается в строку последовательными названиями аккордов, например: Аm Dm E7 Am и т.д.

В силу особенностей человеческого восприятия те звуки, частоты которых отличаются в два раза, кажутся "похожими", как бы повторяют друг друга, но выше или ниже. Отсюда - деление музыкальных звуков по высоте (то есть по частоте) на октавы: интервал от 262 Гц до 2*262 Гц=524 Гц - это 12 нот 1-й октавы; если удвоить частоты еще раз, то получатся ноты 2-й октавы. В компьютерных программах для простых мелодий используется такой способ кодирования: указываются частота и длительность каждого звука мелодии: нота(цел f,t), где f - частота в Гц, а t - сотые доли секунды. Для паузы, например, используется частота f=0: нота(0,5) - пауза в 0.05 доли секунды.

В некоторых других языках программирования команда "исполнить музыкальный звук" записывается проще: латинская буква, соответствующая данной ноте (ноты от "ля" малой октавы до "соль" 1-й октавы обозначены латинскими буквами от "А" до "G") и длительность, записанная соответствующим числом (1 - целая, 2 - половинная, 4 - четверть, 8 - восьмая и т.д.). Также перед буквой ставится номер октавы, например, четвертная нота "ми" 1-й октавы будет записана так: 1Е4.

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

В начале 80-х годов появились электронные музыкальные инструменты - синтезаторы, способные воспроизводить звуки многих существующих и несуществующих инструментов. В 1983 году производители синтезаторов и компьютеров договорились о системе команд универсального синтезатора, об электрических сигналах, с помощью которых будут подаваться эти команды и даже о разъемах и кабелях, соединяющих синтезатор с компьютером. Это соглашение назвали стандарт MIDI (англ. Musical Instrument Digital Interface - описание цифрового музыкального инструмента). Этот стандарт удобно кодирует музыку. Запись музыкального произведения в формате MIDI - это программа игры на воображаемом музыкальном инструменте - синтезаторе. Состоит она из последовательности закодированных сообщений, разделенных закодированными паузами. Примеры таких сообщений:

- команды синтезатору (нажать или отпустить клавишу, изменить тембр звучания);

- описание параметров воспроизведения (значение силы давления на клавишу и др.);

- управляющее сообщение (например, включение полифонического режима.

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

Кодирование фильмов

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

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

Для "озвучивания" фильма звук записывается отдельно от изображения (как в кино).

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

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

- параметры звука (частота и разрешение);

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

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

1.2 Классификация кодов

Коды можно классифицировать по различным признакам^[4]:

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

2. По длине кодовых комбинаций (слов):

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

неравномерные - если длина кодовой комбинации не постоянна.

3. По способу передачи:

последовательные и параллельные;

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

4. По помехоустойчивости:

простые (примитивные, полные) - для передачи информации используют все возможные кодовые комбинации (без избыточности);

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

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

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

Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code).

В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

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

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

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

2.1 Матричное кодирование

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

Пример

a₁ 1 1000 111 011 Необходимо закодировать

a₂ 0 0100 110 101информационную комбинацию:

a₃1 0010 101 110 1011

a₄1 0001 011 111

Полученное значение проверочных

1011 001 разрядов.

В общем случае: a₁, a₂, a₃, a₄ – информационная кодовая комбинация в общем виде:

a₁ a₂ a₃ a₄ b₁ b₂ b₃ b₁ = a₁ a₂  a₃ Для заданной образующей матрицы

b₂ = a₁ a₂  a₄

b₃ = a₁ a₃  a₄

В самом общем случае алгоритм образования проверочных символов b₁…b₂ по известной информационной частиa₁, a₂, … a_k может быть записан следующем образом:

_k

b₁ = p₁₁a₁  p₂₁a₂  p … _k1a_k p= _i1a_i

ⁱ⁼¹

_k

b₂ = p₁₂a₁  p₂₂a₂  p … _k2a_k p= _i2a_i

ⁱ⁼¹

----------------------------------------------

_k

bj = p_1ja₁  p_2ja₂  p … _kja_k p= _ija_i

ⁱ⁼¹

----------------------------------------------

_k

b_r = p_1ra₁  p_2ra₂  p … _kra_k p= _ira_i

ⁱ

Рассмотрим теперь метод построения образующей матрицы

Из свойств группового следует, что

dW _min

С другой стороны W_i = Wн_i  d+ Wпi _min

W_п d_min – Wн

Т.к. вес всех сторон ||Н||:W₁₁=1, то имеем

dWп _min – 1, d_min  d t+1_min  t–1

dWп _min  t Wп  t – 1

Необходимые и Отсюда: для кодов, обнаруживающихt– кратные ошибки:

достаточные требования W_{п (строки)}  t

для построения проверочной для кодов, исправляющих t – кратные ошибки :

матрицы W_{п (строки)}  2t

Рассмотрим частные случаи:

1.) Коды, обнаруживающие одиночную ошибку.

d_min= 2 ( N=15, t=1 )

W_п 1

Единая матрица для d_min2

100…0 1 _{k k}

010…0 1 b₁ a=_ip_1i a=_i Не что иное, как

001…0 1 ^{i=1 i=1} проверка на четность.

000…1 1

И П

Во всех комбинациях построенного кода – четное.

Для d_min  3 проверочная матрица не может быть представлена в общей (единой) форме, т.к. дляd_min  r зависит отk. 3 

Построение кодовой комбинацииEв матричной форме имеет вид:

образующая матрица

E = IG_n,k , гдеI– вектор длиныk, компонентами которой являются

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

кодовый вектор информационный

вектор

2.2 Представление кодов в виде кодовых деревьев

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