Формат

Здесь приведено полное описание формата FLAC.

От автора

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

• Э. Робинсону за работу над Shorten. Его статья послужила отправной точкой для нескольких основных методов, заложенных во FLAC. FLAC развил идею постоянных предикторов, используемую в Shorten.
• С. Голомбу и Роберту Райсу. Их универсальные коды используются кодером энтропии.
• Н. Левинсону и Дж. Дарбину. Базовый кодер использует разработанный и улучшенный ими алгоритм для определения LPC коэффициентов из коэффициентов автокорреляции.
• И, конечно же, К. Шеннону.

--Джош Колсон

Область применения

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

В области аудио существует множество возможных подразделов. Например, речь с низким битрейтом, многоканальная музыка с высокой частотой дискретизации и т.д. FLAC не нацелен на какой-либо подраздел, однако большинство параметров по умолчанию базового кодера рассчитаны на CD-аудио (т.е. 44.1кГц, 2 канала, 16 бит на сэмпл). Влияние параметров кодирования на разные типы аудио будет рассмотрено позже.

Архитектура

Подобно большинству программ такого рода, кодер FLAC выполняет следующие действия:

• Разбиение на блоки. Ввод разбивается на множество последовательных блоков, которые могут иметь различный размер. Оптимальный размер блока обычно зависит от многих факторов, таких как частота дискетизации, спектральная характеристика во времени и т.д. Несмотря на то, что формат FLAC позволяет использовать в потоке блоки различного размера, базовый кодер использует постоянный размер.
• Межканальная декорреляция. В случае стереопотоков кодер создает средний и разностный сигналы, основанные на среднем значении между левым и правым каналами и их разности соответственно. На следующий этап кодирования передается лучший из вариантов сжатого сигнала.
• Прогнозирование. Далее кодер пытается найти математическое описание сигнала (обычно приблизительное). Зачастую оно значительно меньше самого сигнала. Так как методы предсказания известны и кодеру, и декодеру в потоке нужно указать только параметры предиктора. Сейчас FLAC использует четыре различных класса предикторов (описанных в разделе Прогнозирование), но в формате предусмотрено место для дополнительных методов. FLAC допускает изменение класса предиктора от блока к блоку и даже в пределах канала в блоке.
• Кодирование остатков. Если предиктор не описывает сигнал точно, разница между оригинальным сигналом и спрогнозированным (называемым еще ошибочным или остаточным) должна быть закодирована без потерь. Если предсказание эффективно, остаточный сигнал будет занимать меньше бит на сэмпл, чем оригинальный сигнал. Сейчас FLAC использует только один метод для кодирования остатков (см. раздел Кодирование остатков), однако в формате предусмотрено место для дополнительных методов. FLAC допускает изменение метода кодирования остатков от блока к блоку и даже в пределах канала в блоке.

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

Определения

Многие термины, такие как "блок" и "фрейм", имеют различное значение в схемах кодирования. Например, фрейм в mp3 сооветствует многим сэмплам во всех каналах, в то время как фрейм S/PDIF представляет только один сэмпл для каждого канала. Обратите внимание на то, что, говоря о "блоках" и "подблоках", мы ссылаемся на незакодированные аудиоданные, а термины "фрейм" и "подфрейм" используем для данных сжатых FLAC.

• Блок - это один или более сэмплов, находящихся в нескольких каналах.
• Подблок - это один или более сэмплов из одного канала. Таким образом, блок содержит подблок для каждого канала и все подблоки в нем содержат одинаковое количество сэмплов.
• Размер блока - это количество сэмплов в любом из своих подблоков. Например, блок длиной в одну секунду с частотой дескретизации 44.1кГц имеет размер блока 44100 вне зависимости от количества каналов.
• Фрейм - это заголовок и один или несколько подфреймов.
• Подфрейм - это заголовок и один или несколько закодированных сэмплов из данного канала. Все подфреймы в данном фрейме содержат одинаковое количество сэмплов.

Разбиение на блоки

Размер блоков сильно влияет на уровень сжатия. Если размер блока будет слишком мал, то в итоге получится очень много фреймов, а это значит, что на заголовки будет потрачено много битов. Если же размер блока большой, а характеристики сигнала сильно варьируются, кодер не сможет найти хороший предиктор. Чтобы упростить кодек, FLAC определяет минимальный размер блока в 16 сэмплов, а максимальный в 65535 сэмплов. Этот интервал покрывает оптимальные размеры блоков для всех аудиоданных, поддерживаемых FLAC.

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

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

Межканальная декорреляция

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

• Независимое. Левый и правый каналы кодируются независимо.
• Разностное. Левый и правый канал преобразовываются в средний и остаточный каналы. Средний канал - это среднее значение левого и правого сигналов, а остаточный - разница между ними (левый минус правый).
• Левостороннее. Кодируется левый и остаточный каналы.
• Правоостороннее. Кодируется правый и остаточный каналы.

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

Прогнозирование

FLAC использует четыре метода для моделирования входного сигнала:

• Дословный. По существу это прогнозирование сигнала нулевого уровня. Предиктором сигнала является сам сигнал, потому сжатие не происходит. Это образец, с которым сверяются все остальные предикторы. Если передать кодеру случайные данные, для всех подблоков скоре всего будет использован дословный предиктор. Так как необработанный сигнал не проходит стадию кодирования остатков, результаты не будут совпадать с линейным предиктором нулевого порядка.
• Постоянный. Этот предиктор используется, когда подблок содержит цифровую тишину, т.е. на вход поступает одна константа. Сигнал кодируется по всей длине и добавляется к потоку.
• Постоянный линейный предиктор. FLAC использует класс эффективно вычисляемых постоянных линейных предикторов (хорошее описание приведено у Shorten и AudioPak). FLAC добавляет предиктор четвертого уровня к использованным в Shorten предикторам от нулевого до третьего уровня. Так как предикторы постоянны, в сжатом потоке необходимо сохранить только порядок предиктора. Остаточный сигнал передается кодеру остатков.
• Линейное прогнозирование FIR. Для более точного моделирования (за счет медленной работы) FLAC поддерживает линейное прогнозирование FIR до 32 порядка (см. Shorten и AudioPak). Базовый кодер использует метод Левинсона-Дарбина для расчета LPC коэффициентов из коэффициентов автокорреляции и коэффициенты разбиваются перед вычислением остатков. В то время как такие кодеры как Shorten используют постоянное разбиение для всего ввода, FLAC позволяет для каждого фрейма менять точность коэффициента разбиения. Базовый кодер FLAC оценивает оптимальную точность, основываясь на размере блока и диапазоне оригинального сигнала.

Кодирование остатков

Для кодирования остаточного сигнала от стадии прогнозирования FLAC использует два похожих метода. Остаточный сигнал сжимается с использованием кодов Райса следующими способами:

1. Кодер оценивает одиночный параметр Райса, основанный на разнице остатка и кодов Райса. Весь остаток кодируется с использованием этого параметра.
2. Остаток делится на несколько интервалов одинаковой длины и каждый из них кодируется со своим параметром Райса, основанным на среднем значении для данного интервала.

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

В формате FLAC зарезервировано место для других методов кодирования. Кто-нибудь может попытаться найти лучшее контекстное моделирование параметра Райса или кодирования Хаффмана. Описания нескольких универсальных кодов можно найти на страницах LOCO-I и pucrunch.

Формат

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

Все числа в формате FLAC являются целыми, младший байт которых записывается вначале (big-endian). Числа являются беззнаковыми, кроме тех случаев, где явно указано обратное.

К потоку FLAC могут быть добавлены тэги ID3v1 (в конце) и ID3v2 (в начале). Эти данные не относятся к формату, однако декодер умеет пропускать их.

Перед полным описанием формата приведем его краткий обзор.

• Формат FLAC состоит из маркера "fLaC" в начале потока, за которым следует обязательный блок STREAMINFO, любое количество других блоков метаданных, а затем аудиофреймы.
• FLAC поддерживает до 128 блоков метаданных. Сейчас определены:
• • STREAMINFO: Этот блок содержит информацию обо всем потоке (частоту дискретизации, количество каналов, количество сэмплов и т.д.). Он всегда должен быть первым блоком метаданных в потоке. Следующие блоки должны следовать за ним, и могут быть пропущены декодером.
  • APPLICATION: Этот блок предназначен для использования приложениями третьих лиц. Единственным обязательным полем является 32-битный идентификатор, который выдается разработчиками FLAC. Формат оставшейся части блока определяется зарегистрированным под этим номером приложением. Чтобы получить id для своего приложения, посетите страницу регистрации.
  • PADDING: Этот блок предназначен для резервирования места. Содержимое блока PADDING не имеет значения. Он полезен в том случае, если известно, что блок после кодирования будет добавлен блок APPLICATION. Пользователь может зарезервировать необходимое пространство с помощью блока PADDING, чтобы приложение смогло записать на его место блок APPLICATION. Эта операция займет намного меньше времени, чем вставка блока в начало файла, так как в втором случае потребуется его полная перезапись.
  • SEEKTABLE: Это необязательный блок для хранения точек поиска. В потоке FLAC можно найти любой сэмпл без этой таблицы, однако задержка может быть непредсказуемой, так как битрейт в потоке может существенно меняться. С помощью таблицы точек поиска пауза может быть существенно сокращена. Каждая точка занимает 18 байтов, поэтому для быстрого поиска с точностью до 1% необходимо всего 2кб. В потоке может быть только одни блок SEEKTABLE, но в нем может быть любое количество точек поиска. Также существуют резервируемые точки, которые пропускаются декодером, но могут использоваться для последующих вставок реальных точек поиска.
  • VORBIS_COMMENT: Этот блок предназначен для хранения списка в удобном для чтения формате (параметр=значение). Значения записываются в кодировке UTF-8. Используется реализация спецификации комментария Vorbis. Это единственный официально поддерживаемый механизм работы с тегами в FLAC. В потоке может быть только один блок VORBIS_COMMENT.
  • CUESHEET: В этом блоке записывается информация из списка разбиения аудиодиска. Сделана поддержка треков и индекса, совместимая со стандартом Red Book CD для аудиодисков, а также других метаданных, таких как номер в каталоге дисков. Этот блок особенно полезен для архивирования аудиодисков, но также может использоваться как механизм для поиска при воспроизведении.
• Аудиопоток состоит из одного или нескольких фреймов. У каждого фрейма есть заголовок, состоящий из кода синхронизации, информации о фрейме (размер блока, частота дискретизации, количество каналов и т.п.) и восьмибитной контрольной суммы. Также в заголовке содержится либо номер первого сэмпла во фрейме относительно всего потока (для потоков с изменяющимся размером блока) или номер фрейма (для потоков с постоянным размером блока). Это позволяет производить быстрый и точный поиск. Далее следуют закодированные подфреймы (по одному на каждый канал) и, наконец, фрейм, дополненный нулями до границы байта. Каждый подфрейм имеет свой заголовок, определяющий способ его декодирования.
• Так как декодер может начать работу в середине потока, должен быть метод определения начала фрейма. Каждый фрейм начинается с 14-битного синхронизирующего кода. Этот код не может появляться ни в одном другом месте заголовка фрейма. Однако так как это код может появиться в подфреймах, у декодера есть два способа определить, что данная последовательность является началом фрейма. Сначала проверяется корректность данных во всем фрейме. Однако этот шаг не может гарантировать отсутствия ошибок, поэтому дополнительно производится расчет восьмибитной контрольной суммы заголовка фрейма и полученный результат сравнивается со значением, полученным при кодировании и записанным после заголовка фрейма.
• Каждый фрейм должен содержать основную информацию о потоке, так как декодер может не иметь доступа к блоку метаданных STREAMINFO в начале потока. Сюда входит частота дискретизации, количество бит на сэмпл, количество каналов и т.д. Так как заголовоки фреймов вносят дополнительные накладные расходы, то они влияют уровень сжатия. Чтобы сделать заголовки фреймов минимальными, FLAC использует таблицы поиска для наиболее часто используемых значений параметров фремов. Например, часть, отвечающая за частоту дискретизации, занимает 4 бита. Восемь предопределенных значений соответствуют наиболее самым распространенным частотам (8/16/22.05/24/32/44.1/48/96 кГц). Однако дополнительные частоты могут быть использованы с помощью специального набора битов, указывающего декодеру, что необходимое значение находится в конце заголовка. Такой же метод используется для указания размера блока и количества битов на сэмпл. В этом случае заголовок остается достаточно малым для наиболее распространенных типов аудиоданных.
• Подфреймы (по одному для каждого канала) кодируются во фрейме отдельно и хранятся в потоке последовательно. Это ведет к упрощению декодера, однако ценой этому является увеличение размеров буффера. У каждого подфрейма есть свой заголовок, определяющий его аттрибуты (метод и порядок прогнозирования, параметры кодирования остатков и т.д.). За заголовком следуют аудиоданные для этого канала.
• Во FLAC определено специальное подмножество формата (Subset format). Все потоки сжатые этим методом на самом деле являются потоковыми, то есть декодер, который не может искать в потоке, имеет возможность перейти к любой его точке и начать воспроизведение. Для файлов, отвечающих этому подмножеству формата, значительно проще сделать аппаратный декодер. flac по умолчанию создает потоки, отвечающие этому подмножеству формата. Ключ --lax запрещает создание таких потоков. Чтобы файл отвечал данному подмножеству, для него должны выполняться следующие ограничения:
• • Значение битов, отвечающих за размер блока, должно быть в пределах 0001-0101 или 1000-1110. Поток должен состоять из блоков одинакового небольшого размера (за исключением последнего), а в блоке метаданных STREAMINFO должны быть указаны равные значения для минимального и максимального размера блока.
  • Частота дискретизации в заголовке фрейма должна описываться следующим диапазоном битов 0001-1011.
  • Количество бит на сэмпл в заголовке фрейма должно описываться следующим диапазоном битов 001-111.

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

 Copyright (c) 2000,2001,2002,2003 Josh Coalson