Квантование в математике и цифровой обработке сигналов — это процесс преобразования входных значений из большого набора (часто непрерывного набора) в выходные значения в (счетном) меньшем наборе, часто с конечным числом элементов . Округление и усечение являются типичными примерами процессов квантования. Квантование в той или иной степени участвует практически во всех процессах цифровой обработки сигналов, поскольку процесс представления сигнала в цифровой форме обычно включает округление. Квантование также составляет основу практически всех алгоритмов сжатия с потерями .
Разница между входным значением и его квантованным значением (например, ошибкой округления ) называется ошибкой квантования . Устройство или алгоритмическая функция , выполняющая квантование, называется квантователем . Аналого -цифровой преобразователь является примером квантователя.
Например, округление действительного числа до ближайшего целого значения образует очень простой тип квантователя – унифицированный . Типичный ( средний шаг ) равномерный квантователь с размером шага квантования , равным некоторому значению, может быть выражен как
где обозначение обозначает функцию пола .
В качестве альтернативы тот же квантователь может быть выражен через функцию потолка , как
(Обозначения обозначают функцию потолка).
Существенным свойством квантователя является наличие счетного набора возможных членов выходных значений, меньшего, чем набор возможных входных значений. Члены набора выходных значений могут иметь целые, рациональные или действительные значения. Для простого округления до ближайшего целого числа размер шага равен 1. При наличии или равенстве любому другому целочисленному значению этот квантователь имеет вещественные входы и целочисленные выходы.
Когда размер шага квантования (Δ) мал по сравнению с изменением квантованного сигнала, относительно просто показать, что среднеквадратическая ошибка, возникающая в результате такой операции округления, будет равна примерно . [1] [2] [3] [4] [5] [6] Среднеквадратическую ошибку также называют мощностью шума квантования . Добавление одного бита к квантователю уменьшает вдвое значение Δ, что снижает мощность шума в ¼ раза. В децибелах изменение мощности шума равно
Поскольку набор возможных выходных значений квантователя счетен, любой квантователь можно разложить на два отдельных этапа, которые можно назвать этапом классификации ( или этапом прямого квантования ) и этапом реконструкции (или этапом обратного квантования ), где этап классификации отображает входное значение в целочисленный индекс квантования, а этап реконструкции отображает индекс в значение восстановления , которое является выходной аппроксимацией входного значения. Для примера однородного квантователя, описанного выше, этап прямого квантования может быть выражен как
и этап реконструкции для этого примера квантователя просто
Такое разложение полезно для проектирования и анализа поведения квантования и иллюстрирует, как квантованные данные могут передаваться по каналу связи : исходный кодер может выполнять этап прямого квантования и отправлять индексную информацию по каналу связи, а декодер — может выполнить этап реконструкции для получения выходной аппроксимации исходных входных данных. В общем, этап прямого квантования может использовать любую функцию, которая отображает входные данные в целочисленное пространство данных индекса квантования, а этап обратного квантования может концептуально (или буквально) представлять собой операцию поиска в таблице для сопоставления каждого индекса квантования с соответствующее значение реконструкции. Это двухэтапное разложение одинаково хорошо применимо как к векторным , так и к скалярным квантователям.
Поскольку квантование представляет собой отображение «многие к немногим», это по своей сути нелинейный и необратимый процесс (т. е., поскольку одно и то же выходное значение используется несколькими входными значениями, в общем случае невозможно восстановить точное входное значение, когда задано только выходное значение).
Набор возможных входных значений может быть бесконечно большим и, возможно, непрерывным и, следовательно, несчетным (например, набор всех действительных чисел или всех действительных чисел в некотором ограниченном диапазоне). Набор возможных выходных значений может быть конечным или счетным . [6] Входные и выходные наборы, участвующие в квантовании, могут быть определены довольно общим способом. Например, векторное квантование — это применение квантования к многомерным (векторным) входным данным. [7]
Аналого -цифровой преобразователь (АЦП) можно смоделировать как два процесса: выборку и квантование. Выборка преобразует изменяющийся во времени сигнал напряжения в сигнал дискретного времени , представляющий собой последовательность действительных чисел. Квантование заменяет каждое действительное число приближением из конечного набора дискретных значений. Чаще всего эти дискретные значения представляются в виде слов с фиксированной запятой. Хотя возможно любое количество уровней квантования, обычная длина слова составляет 8 бит (256 уровней), 16 бит (65 536 уровней) и 24 бита (16,8 миллиона уровней). Квантование последовательности чисел приводит к последовательности ошибок квантования, которую иногда моделируют как аддитивный случайный сигнал, называемый шумом квантования, из-за его стохастического поведения. Чем больше уровней использует квантователь, тем ниже мощность его шума квантования.
Квантование , оптимизированное по скорости искажений , встречается при исходном кодировании для алгоритмов сжатия данных с потерями, целью которых является управление искажениями в пределах скорости передачи данных , поддерживаемой каналом связи или носителем данных. Анализ квантования в этом контексте включает изучение объема данных (обычно измеряемого в цифрах, битах или скорости передачи данных), который используется для представления выходного сигнала квантователя, и изучение потери точности, вносимой процессом квантования (который называется искажением ) .
Большинство унифицированных квантователей для входных данных со знаком можно отнести к одному из двух типов: промежуточный и промежуточный . Терминология основана на том, что происходит в области вокруг значения 0, и использует аналогию рассмотрения функции ввода-вывода квантователя как лестницы . Квантизаторы средней ступени имеют нулевой уровень реконструкции (соответствует ступеньке лестницы ), тогда как квантователи средней ступени имеют порог классификации с нулевым значением (соответствует подступенку лестницы ). [9]
Квантование в середине протектора включает округление. Формулы для равномерного квантования в середине протектора представлены в предыдущем разделе.
Квантование среднего уровня включает усечение. Формула ввода-вывода для равномерного квантователя среднего уровня определяется следующим образом:
где правило классификации определяется выражением
и правило реконструкции
Обратите внимание, что однородные квантователи со средней высотой не имеют нулевого выходного значения — их минимальная выходная величина составляет половину размера шага. Напротив, квантователи средней ступени имеют нулевой уровень выходного сигнала. Для некоторых приложений может оказаться необходимым наличие нулевого представления выходного сигнала.
В общем, квантователь со средним подступенком или средней ступенью может на самом деле не быть однородным квантователем, т. е. не все размеры классификационных интервалов квантователя могут быть одинаковыми или расстояние между его возможными выходными значениями может не быть одинаковым. . Отличительной характеристикой квантователя средней ступени является то, что он имеет пороговое значение классификации, которое равно нулю, а отличительной характеристикой квантователя средней ступени является то, что он имеет значение восстановления, которое точно равно нулю. [9]
Квантизатор мертвой зоны — это тип квантователя в середине шага с симметричным поведением вокруг 0. Область вокруг нулевого выходного значения такого квантователя называется мертвой зоной или зоной нечувствительности . Мертвая зона иногда может служить той же цели, что и шумоподавитель или функция шумоподавления . Специально для приложений сжатия мертвая зона может иметь другую ширину, чем ширина для других ступеней. Для однородного в остальном квантователя ширина мертвой зоны может быть установлена на любое значение с помощью правила прямого квантования [10] [11] [12]
где функция ( ) является знаковой функцией (также известной как функция Signum ). Общее правило восстановления для такого квантователя мертвой зоны определяется выражением
где — значение смещения реконструкции в диапазоне от 0 до 1 в виде доли размера шага. Обычно при квантовании входных данных используется типичная функция плотности вероятности (PDF), которая симметрична относительно нуля и достигает своего пикового значения в нуле (например, гауссиан , лапласиан или обобщенный гауссиан PDF). Хотя в целом оно может зависеть от и может быть выбрано для выполнения условия оптимальности, описанного ниже, часто ему просто присваивается константа, например . (Обратите внимание, что в этом определении из-за определения функции ( ) это не имеет никакого эффекта.)
Очень часто используемый частный случай (например, схема, обычно используемая в финансовом учете и элементарной математике) — это установить и для всех . В этом случае квантователь мертвой зоны также является однородным квантователем, поскольку центральная мертвая зона этого квантователя имеет ту же ширину, что и все его другие шаги, и все его значения восстановления также расположены на одинаковом расстоянии друг от друга.
Распространенным предположением при анализе ошибки квантования является то, что она влияет на систему обработки сигналов аналогично аддитивному белому шуму – имея незначительную корреляцию с сигналом и примерно плоскую спектральную плотность мощности . [2] [6] [13] [14] Модель аддитивного шума обычно используется для анализа эффектов ошибок квантования в системах цифровой фильтрации, и она может быть очень полезна в таком анализе. Было показано, что эта модель действительна в случаях квантования с высоким разрешением (малым по сравнению с уровнем сигнала) с гладкими PDF-файлами. [2] [15]
Поведение аддитивного шума не всегда является верным предположением. Ошибка квантования (для квантователей, определенных, как описано здесь) детерминированно связана с сигналом и не полностью от него независима. Таким образом, периодические сигналы могут создавать периодический шум квантования. А в некоторых случаях это может даже привести к появлению предельных циклов в системах цифровой обработки сигналов. Одним из способов обеспечить эффективную независимость ошибки квантования от исходного сигнала является выполнение квантования со сглаживанием (иногда с формированием шума ), которое включает добавление случайного (или псевдослучайного ) шума к сигналу перед квантованием. [6] [14]
В типичном случае исходный сигнал намного больше одного младшего бита (LSB). В этом случае ошибка квантования незначительно коррелирует с сигналом и имеет приблизительно равномерное распределение . Когда для квантования используется округление, ошибка квантования имеет среднее значение , равное нулю, а среднеквадратичное значение (RMS) представляет собой стандартное отклонение этого распределения, определяемое выражением . При использовании усечения ошибка имеет ненулевое среднее значение, а среднеквадратичное значение равно . Хотя округление дает меньшую среднеквадратическую ошибку, чем усечение, разница обусловлена только статическим (DC) членом . Среднеквадратические значения ошибки по переменному току в обоих случаях одинаковы, поэтому нет особого преимущества округления перед усечением в ситуациях, когда член ошибки по постоянному току можно игнорировать (например, в системах, связанных по переменному току). В любом случае стандартное отклонение, выраженное в процентах от полного диапазона сигнала, изменяется в 2 раза на каждое изменение количества бит квантования на 1 бит. Таким образом, потенциальное отношение мощности сигнала к шуму квантования изменяется на 4 или примерно 6 дБ на бит.
При более низких амплитудах ошибка квантования становится зависимой от входного сигнала, что приводит к искажениям. Это искажение создается после фильтра сглаживания, и если эти искажения превышают половину частоты дискретизации, они возвращаются в интересующую полосу. Чтобы сделать ошибку квантования независимой от входного сигнала, сигнал подвергается сглаживанию путем добавления к сигналу шума. Это немного снижает соотношение сигнал/шум, но позволяет полностью устранить искажения.
Шум квантования — это модель ошибки квантования, вносимой квантованием в АЦП. Это ошибка округления между аналоговым входным напряжением АЦП и выходным цифровым значением. Шум нелинейен и зависит от сигнала. Его можно смоделировать несколькими различными способами.
В идеальном АЦП, где ошибка квантования равномерно распределена между −1/2 LSB и +1/2 LSB, а сигнал имеет равномерное распределение, охватывающее все уровни квантования, отношение сигнал/шум квантования (SQNR) может рассчитываться из
где Q — количество битов квантования.
Наиболее распространенными тестовыми сигналами, отвечающими этому требованию, являются треугольные волны полной амплитуды и пилообразные волны .
Например, 16-битный АЦП имеет максимальное отношение сигнал/шум квантования 6,02 × 16 = 96,3 дБ.
Когда входной сигнал представляет собой синусоидальную волну полной амплитуды , распределение сигнала больше не является равномерным, и вместо этого соответствующее уравнение имеет вид
Здесь снова предполагается , что шум квантования распределен равномерно. Это тот случай, когда входной сигнал имеет большую амплитуду и широкий частотный спектр. [16] В этом случае 16-битный АЦП имеет максимальное отношение сигнал/шум 98,09 дБ. Разница в соотношении сигнал-шум в 1,761 возникает только из-за того, что сигнал представляет собой полномасштабную синусоидальную волну, а не треугольник или пилообразную форму.
Для сложных сигналов в АЦП высокого разрешения это точная модель. Для АЦП с низким разрешением, сигналов низкого уровня в АЦП с высоким разрешением и для простых сигналов шум квантования распределяется неравномерно, что делает эту модель неточной. [17] В этих случаях на распределение шума квантования сильно влияет точная амплитуда сигнала.
Расчеты относятся к полномасштабным входным данным. Для сигналов меньшего размера относительное искажение квантования может быть очень большим. Чтобы обойти эту проблему, можно использовать аналоговое компандирование , но это может привести к искажениям.
Часто конструкция квантователя предполагает поддержку только ограниченного диапазона возможных выходных значений и выполнение ограничения для ограничения выходного сигнала этим диапазоном всякий раз, когда входной сигнал превышает поддерживаемый диапазон. Ошибка, вызванная этим ограничением, называется искажением из-за перегрузки . В крайних пределах поддерживаемого диапазона величина интервала между выбираемыми выходными значениями квантователя называется его степенью детализации , а ошибка, вносимая этим интервалом, называется гранулярным искажением. Обычно при проектировании квантователя необходимо определить правильный баланс между гранулярными искажениями и искажениями из-за перегрузки. Для заданного поддерживаемого числа возможных выходных значений уменьшение среднего гранулярного искажения может привести к увеличению среднего искажения от перегрузки, и наоборот. Методом управления амплитудой сигнала (или, что то же самое, размером шага квантования ) для достижения соответствующего баланса является использование автоматической регулировки усиления (АРУ). Однако в некоторых конструкциях квантователей концепции гранулярной ошибки и ошибки перегрузки могут не применяться (например, для квантователя с ограниченным диапазоном входных данных или со счетным бесконечным набором выбираемых выходных значений). [6]
Скалярный квантователь, выполняющий операцию квантования, обычно можно разбить на два этапа:
Эти два этапа вместе составляют математическую операцию .
Методы энтропийного кодирования могут применяться для передачи индексов квантования от исходного кодера, который выполняет этап классификации, в декодер, который выполняет этап реконструкции. Один из способов сделать это — связать каждый индекс квантования с двоичным кодовым словом . Важным фактором является количество битов, используемых для каждого кодового слова, обозначенное здесь . В результате проектирование квантователя уровня и связанного с ним набора кодовых слов для передачи значений его индекса требует нахождения значений , которые оптимально удовлетворяют выбранному набору конструктивных ограничений, таких как скорость передачи данных и искажения .
Предполагая, что источник информации создает случайные величины со связанным PDF , вероятность того, что случайная величина попадает в определенный интервал квантования, определяется выражением:
Результирующая скорость передачи данных в единицах среднего числа битов на квантованное значение для этого квантователя может быть получена следующим образом:
Если предположить, что искажение измеряется с помощью среднеквадратической ошибки, [a] искажение D определяется выражением:
Ключевое наблюдение состоит в том, что скорость зависит от границ решения и длины кодового слова , тогда как искажение зависит от границ решения и уровней реконструкции .
После определения этих двух показателей производительности квантователя типичная формулировка коэффициента искажений для задачи проектирования квантователя может быть выражена одним из двух способов:
Часто решение этих проблем может быть эквивалентно (или приблизительно) выражено и решено путем преобразования формулировки к задаче без ограничений, где множитель Лагранжа является неотрицательной константой, которая устанавливает соответствующий баланс между скоростью и искажением. Решение задачи без ограничений эквивалентно поиску точки на выпуклой оболочке семейства решений эквивалентной постановки задачи с ограничениями. Однако найти решение – особенно решение в закрытой форме – для любой из этих трех формулировок проблемы может быть сложно. Решения, не требующие методов многомерной итеративной оптимизации, были опубликованы только для трех PDF-распределений: равномерного, [18] экспоненциального , [12] и лапласова [12] распределений. Итерационные подходы к оптимизации можно использовать для поиска решений и в других случаях. [6] [19] [20]
Обратите внимание, что значения реконструкции влияют только на искажения – они не влияют на скорость передачи данных – и что каждый человек вносит отдельный вклад в общее искажение, как показано ниже:
где
Это наблюдение можно использовать для облегчения анализа — учитывая набор значений, значение каждого можно оптимизировать отдельно, чтобы минимизировать его вклад в искажение .
Для критерия искажения среднеквадратической ошибки можно легко показать, что оптимальный набор значений восстановления задается путем установки значения восстановления в каждом интервале на условное ожидаемое значение (также называемое центроидом ) внутри интервала, как указано к:
Использование достаточно хорошо разработанных методов энтропийного кодирования может привести к использованию скорости передачи данных, близкой к истинному информационному содержанию индексов , так что эффективно
и поэтому
Использование этого приближения может позволить отделить проблему проектирования энтропийного кодирования от проектирования самого квантователя. Современные методы энтропийного кодирования, такие как арифметическое кодирование, могут обеспечить скорость передачи данных, очень близкую к истинной энтропии источника, с учетом набора известных (или адаптивно оцененных) вероятностей .
В некоторых проектах вместо оптимизации для определенного числа областей классификации проблема проектирования квантователя может также включать оптимизацию значения . Для некоторых вероятностных моделей источников наилучшая производительность может быть достигнута при приближении к бесконечности.
В приведенной выше формулировке, если ограничением скорости передачи данных пренебречь, установив его равным 0, или, что то же самое, если предполагается, что код фиксированной длины (FLC) будет использоваться для представления квантованных данных вместо кода переменной длины (или некоторые другие технологии энтропийного кодирования, такие как арифметическое кодирование, которое лучше, чем FLC в смысле скорости-искажения), задача оптимизации сводится к минимизации только искажений.
Индексы, создаваемые квантователем уровня, могут быть закодированы с использованием кода фиксированной длины с использованием битов/символов. Например, при 256 уровнях скорость передачи данных FLC составляет 8 бит/символ. По этой причине такой квантователь иногда называют 8-битным квантователем. Однако использование FLC исключает улучшение сжатия, которое можно получить за счет использования лучшего энтропийного кодирования.
Если предположить, что FLC имеет уровни, то проблема минимизации скорости и искажений может быть сведена только к минимизации искажений. Сокращенную задачу можно сформулировать следующим образом: учитывая источник с PDF и ограничение, согласно которому квантователь должен использовать только области классификации, найти границы решения и уровни реконструкции , чтобы минимизировать результирующее искажение.
Поиск оптимального решения вышеуказанной проблемы приводит к появлению квантователя, который иногда называют решением MMSQE (минимальная среднеквадратическая ошибка квантования), а полученный в результате квантователь, оптимизированный для PDF (неравномерный), называется квантователем Ллойда – Макса , названным в честь два человека, которые независимо разработали итерационные методы [6] [21] [22] для решения двух наборов одновременных уравнений, возникающих из и , следующим образом:
который помещает каждый порог в среднюю точку между каждой парой значений реконструкции, и
который помещает каждое значение реконструкции в центроид (условное ожидаемое значение) соответствующего классификационного интервала.
Алгоритм Ллойда I , первоначально описанный в 1957 году, можно легко обобщить для применения к векторным данным. Результатом этого обобщения являются методы оптимизации классификатора Линде – Бьюзо – Грея (LBG) или k-средних . Более того, этот метод можно дополнительно обобщить, включив в него также ограничение энтропии для векторных данных. [23]
Квантизатор Ллойда-Макса на самом деле является равномерным квантователем, когда входной PDF-файл равномерно распределен по диапазону . Однако для источника, который не имеет равномерного распределения, квантователь с минимальными искажениями может не быть равномерным квантователем. Анализ однородного квантователя, примененного к равномерно распределенному источнику, можно резюмировать следующим образом:
Симметричный источник X можно смоделировать с помощью , for и 0 в другом месте. Размер шага и отношение сигнал/шум квантования (SQNR) квантователя равны
Для кода фиксированной длины, использующего биты, что приводит к ,
или приблизительно 6 дБ на бит. Например, для =8 бит, =256 уровней и SQNR = 8×6 = 48 дБ; и для =16 бит =65536 и SQNR = 16×6 = 96 дБ. Свойство улучшения SQNR на 6 дБ для каждого дополнительного бита, используемого при квантовании, является хорошо известным показателем качества. Однако его следует использовать с осторожностью: этот вывод применим только для однородного квантователя, примененного к однородному источнику. Для других исходных PDF-файлов и других конструкций квантователей SQNR может несколько отличаться от прогнозируемого на 6 дБ/бит, в зависимости от типа PDF-файла, типа источника, типа квантователя и диапазона скорости передачи данных.
Однако принято предполагать, что для многих источников крутизна функции квантования SQNR может быть приблизительно равна 6 дБ/бит при работе на достаточно высокой скорости передачи данных. При асимптотически высоких скоростях передачи данных сокращение размера шага вдвое увеличивает скорость передачи данных примерно на 1 бит на выборку (поскольку 1 бит необходим для указания того, находится ли значение в левой или правой половине предыдущего интервала двойного размера) и уменьшает среднеквадратическая ошибка в 4 раза (т. е. 6 дБ) на основе аппроксимации .
При асимптотически высоких скоростях передачи данных приближение 6 дБ/бит подтверждается для многих исходных PDF-файлов строгим теоретическим анализом. [2] [3] [5] [6] Более того, структура оптимального скалярного квантователя (в смысле скорости-искажения) приближается к структуре равномерного квантователя в этих условиях. [5] [6]
Многие физические величины фактически квантуются физическими объектами. Примеры областей, в которых применяется это ограничение, включают электронику (из-за электронов ), оптику (из-за фотонов ), биологию (из-за ДНК ), физику (из-за пределов Планка ) и химию (из-за молекул ).