Квантование (обработка сигнала)

Процесс отображения непрерывного множества в счетное множество

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

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

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

Пример

Например, округление действительного числа до ближайшего целого значения образует очень простой тип квантователя – равномерный . Типичный ( средне-ступенчатый ) равномерный квантователь с размером шага квантования, равным некоторому значению, может быть выражен как ${\displaystyle x}$ ${\displaystyle \Delta }$

${\displaystyle Q(x)=\Delta \cdot \left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

где обозначение обозначает функцию пола . ${\displaystyle \lfloor \ \rfloor }$

В качестве альтернативы тот же квантователь может быть выражен в терминах функции потолка , как

${\displaystyle Q(x)=\Delta \cdot \left\lceil {\frac {x}{\Delta }}-{\frac {1}{2}}\right\rceil }$.

(Обозначение обозначает функцию потолка). ${\displaystyle \lceil \ \rceil }$

Существенным свойством квантователя является наличие счетного множества возможных выходных значений, меньшего, чем множество возможных входных значений. Члены множества выходных значений могут иметь целые, рациональные или действительные значения. Для простого округления до ближайшего целого числа размер шага равен 1. При равном или равном любому другому целому значению этот квантователь имеет действительные входы и целочисленные выходы. ${\displaystyle \Delta }$ ${\displaystyle \Delta =1}$ ${\displaystyle \Delta }$

Когда размер шага квантования (Δ) мал по сравнению с изменением квантуемого сигнала, относительно просто показать, что среднеквадратическая ошибка, полученная в результате такой операции округления, будет приблизительно равна . ^{[1] [2] [3] [4] [5] [6]} Среднеквадратическая ошибка также называется мощностью шума квантования . Добавление одного бита к квантователю уменьшает значение Δ вдвое, что уменьшает мощность шума в ⁠ раз . ${\displaystyle \Delta ^{2}/12}$1/4⁠ . В децибелах изменение мощности шума составляет ${\displaystyle \scriptstyle 10\cdot \log _{10}(1/4)\ \approx \ -6\ \mathrm {dB} .}$

Поскольку набор возможных выходных значений квантователя является счетным, любой квантователь можно разложить на два отдельных этапа, которые можно назвать этапом классификации (или этапом прямого квантования ) и этапом реконструкции (или этапом обратного квантования ), где этап классификации сопоставляет входное значение с целочисленным индексом квантования , а этап реконструкции сопоставляет индекс со значением реконструкции , которое является выходным приближением входного значения. Для примера равномерного квантователя, описанного выше, этап прямого квантования можно выразить как ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle y_{k}}$

${\displaystyle k=\left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

и этап реконструкции для этого примера квантователя просто

${\displaystyle y_{k}=k\cdot \Delta }$.

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

Математические свойства

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

Набор возможных входных значений может быть бесконечно большим и, возможно, непрерывным и, следовательно, несчетным (например, набор всех действительных чисел или всех действительных чисел в некотором ограниченном диапазоне). Набор возможных выходных значений может быть конечным или счетно бесконечным . ^[6] Входные и выходные наборы, участвующие в квантовании, можно определить довольно общим образом. Например, векторное квантование — это применение квантования к многомерным (векторнозначным) входным данным. ^[7]

Типы

2-битное разрешение с четырьмя уровнями квантования по сравнению с аналоговым. ^[8]

3-битное разрешение с восемью уровнями.

Аналого-цифровой преобразователь

Аналого -цифровой преобразователь (АЦП) можно смоделировать как два процесса: выборку и квантование. Выборка преобразует изменяющийся во времени сигнал напряжения в дискретный сигнал времени , последовательность действительных чисел. Квантование заменяет каждое действительное число приближением из конечного набора дискретных значений. Чаще всего эти дискретные значения представляются в виде слов с фиксированной точкой. Хотя возможно любое количество уровней квантования, распространенные длины слов составляют 8 бит (256 уровней), 16 бит (65 536 уровней) и 24 бита (16,8 миллионов уровней). Квантование последовательности чисел создает последовательность ошибок квантования, которая иногда моделируется как аддитивный случайный сигнал, называемый шумом квантования из-за его стохастического поведения. Чем больше уровней использует квантизатор, тем ниже его мощность шума квантования.

Оптимизация соотношения скорости и искажения

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

Равномерные квантизаторы средней высоты и средней высоты протектора

Большинство равномерных квантизаторов для входных данных со знаком можно классифицировать как относящиеся к одному из двух типов: средний подъёмник и средний проступь . Терминология основана на том, что происходит в области вокруг значения 0, и использует аналогию рассмотрения функции ввода-вывода квантизатора как лестницы . Квантизаторы среднего подъёмника имеют нулевой уровень реконструкции (соответствующий проступи лестницы ), в то время как квантизаторы среднего подъёмника имеют нулевой порог классификации (соответствующий подъёму лестницы ). ^[9]

Квантование середины протектора подразумевает округление. Формулы для равномерного квантования середины протектора приведены в предыдущем разделе.

${\displaystyle Q(x)=\Delta \cdot \left\lfloor {\frac {x}{\Delta }}+{\frac {1}{2}}\right\rfloor }$,

Квантование среднего уровня включает усечение. Формула ввода-вывода для равномерного квантизатора среднего уровня имеет вид:

${\displaystyle Q(x)=\Delta \cdot \left(\left\lfloor {\frac {x}{\Delta }}\right\rfloor +{\frac {1}{2}}\right)}$,

где правило классификации задается как

${\displaystyle k=\left\lfloor {\frac {x}{\Delta }}\right\rfloor }$

и правило реконструкции

${\displaystyle y_{k}=\Delta \cdot \left(k+{\tfrac {1}{2}}\right)}$.

Обратите внимание, что квантователи mid-riser uniform не имеют нулевого выходного значения – их минимальная выходная величина составляет половину размера шага. Напротив, квантователи mid-tread имеют нулевой выходной уровень. Для некоторых приложений наличие нулевого выходного сигнала может быть необходимостью.

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

Квантизаторы мертвой зоны

Квантизатор с мертвой зоной — это тип квантизатора среднего уровня с симметричным поведением около 0. Область вокруг нулевого выходного значения такого квантизатора называется мертвой зоной или полосой нечувствительности . Мертвая зона иногда может служить той же цели, что и функция шумоподавления или шумоподавления . Особенно для приложений сжатия, мертвой зоне может быть задана другая ширина, чем для других шагов. Для квантизатора, который в остальном является однородным, ширина мертвой зоны может быть установлена ​​на любое значение с помощью правила прямого квантования ^{[10] [11] [12]} ${\displaystyle w}$

${\displaystyle k=\operatorname {sgn}(x)\cdot \max \left(0,\left\lfloor {\frac {\left|x\right|-w/2}{\Delta }}+1\right\rfloor \right)}$,

где функция ( ) является функцией знака (также известной как функция знака ). Общее правило реконструкции для такого квантователя мертвой зоны задается как ${\displaystyle \operatorname {sgn} }$

${\displaystyle y_{k}=\operatorname {sgn}(k)\cdot \left({\frac {w}{2}}+\Delta \cdot (|k|-1+r_{k})\right)}$,

где — значение смещения реконструкции в диапазоне от 0 до 1 как доля размера шага. Обычно при квантовании входных данных с типичной функцией плотности вероятности (PDF), которая симметрична относительно нуля и достигает своего пикового значения в нуле (например, гауссовская , лапласианская или обобщенная гауссовская PDF). Хотя может зависеть от в общем случае и может быть выбрана для выполнения условия оптимальности, описанного ниже, она часто просто устанавливается на константу, например . (Обратите внимание, что в этом определении из-за определения функции ( ) so не имеет никакого эффекта.) ${\displaystyle r_{k}}$ ${\displaystyle 0\leq r_{k}\leq {\tfrac {1}{2}}}$ ${\displaystyle r_{k}}$ ${\displaystyle k}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle y_{0}=0}$ ${\displaystyle \operatorname {sgn} }$ ${\displaystyle r_{0}}$

Очень часто используемый частный случай (например, схема, обычно используемая в финансовом учете и элементарной математике) — установить и для всех . В этом случае квантователь мертвой зоны также является равномерным квантователем, поскольку центральная мертвая зона этого квантователя имеет ту же ширину, что и все его другие шаги, и все его значения реконструкции также равномерно распределены. ${\displaystyle w=\Delta }$ ${\displaystyle r_{k}={\tfrac {1}{2}}}$ ${\displaystyle k}$

Характеристики шума и ошибок

Модель аддитивного шума

Распространенное предположение для анализа ошибки квантования заключается в том, что она влияет на систему обработки сигнала аналогично аддитивному белому шуму – имея незначительную корреляцию с сигналом и приблизительно плоскую спектральную плотность мощности . ^{[2] [6] [13] [14]} Модель аддитивного шума обычно используется для анализа эффектов ошибки квантования в системах цифровой фильтрации, и она может быть очень полезна в таком анализе. Было показано, что она является допустимой моделью в случаях квантования с высоким разрешением (малым относительно силы сигнала) с гладкими PDF. ^{[2] [15]} ${\displaystyle \Delta }$

Поведение аддитивного шума не всегда является допустимым предположением. Ошибка квантования (для квантователей, определенных как описано здесь) детерминированно связана с сигналом и не полностью независима от него. Таким образом, периодические сигналы могут создавать периодический шум квантования. А в некоторых случаях это может даже приводить к появлению предельных циклов в системах цифровой обработки сигналов. Одним из способов обеспечения эффективной независимости ошибки квантования от исходного сигнала является выполнение квантования с дизерингом (иногда с формированием шума ), которое включает добавление случайного (или псевдослучайного ) шума к сигналу перед квантованием. ^{[6] [14]}

Модели ошибок квантования

В типичном случае исходный сигнал намного больше одного младшего бита (LSB). В этом случае ошибка квантования не имеет значительной корреляции с сигналом и имеет приблизительно равномерное распределение . Когда округление используется для квантования, ошибка квантования имеет среднее значение , равное нулю, а среднеквадратичное значение (RMS) является стандартным отклонением этого распределения, заданным как . Когда используется усечение, ошибка имеет ненулевое среднее значение , а среднеквадратичное значение равно . Хотя округление дает меньшую среднеквадратичную ошибку, чем усечение, разница обусловлена ​​только статическим (DC) членом . Среднеквадратические значения ошибки переменного тока в обоих случаях абсолютно одинаковы, поэтому нет особого преимущества округления перед усечением в ситуациях, когда DC-член ошибки можно игнорировать (например, в системах, связанных по переменному току). В любом случае стандартное отклонение, как процент от полного диапазона сигнала, изменяется в 2 раза для каждого изменения на 1 бит в количестве битов квантования. Таким образом, потенциальное отношение мощности сигнала к шуму квантования изменяется на 4, или примерно на 6 дБ на бит. ${\displaystyle \scriptstyle {\frac {1}{\sqrt {12}}}\mathrm {LSB} \ \approx \ 0.289\,\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{2}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{\sqrt {3}}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle {\frac {1}{2}}\mathrm {LSB} }$ ${\displaystyle \scriptstyle 10\cdot \log _{10}(4)}$

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

Модель шума квантования

Сравнение квантования синусоиды до 64 уровней (6 бит) и 256 уровней (8 бит). Аддитивный шум, создаваемый 6-битным квантованием, на 12 дБ больше шума, создаваемого 8-битным квантованием. Когда спектральное распределение плоское, как в этом примере, разница в 12 дБ проявляется как измеримая разница в уровнях шума.

Шум квантования — это модель ошибки квантования, вносимой квантованием в АЦП. Это ошибка округления между аналоговым входным напряжением АЦП и выходным оцифрованным значением. Шум нелинейный и зависит от сигнала. Его можно смоделировать несколькими способами.

В идеальном АЦП, где ошибка квантования равномерно распределена между −1/2 LSB и +1/2 LSB, а сигнал имеет равномерное распределение, охватывающее все уровни квантования, отношение сигнал/шум квантования (SQNR) можно рассчитать по формуле

${\displaystyle \mathrm {SQNR} =20\log _{10}(2^{Q})\approx 6.02\cdot Q\ \mathrm {dB} \,\!}$

где Q — количество бит квантования.

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

Например, 16-разрядный АЦП имеет максимальное отношение сигнал/шум квантования 6,02 × 16 = 96,3 дБ.

Когда входной сигнал представляет собой синусоиду полной амплитуды , распределение сигнала уже не является равномерным, и соответствующее уравнение имеет вид

${\displaystyle \mathrm {SQNR} \approx 1.761+6.02\cdot Q\ \mathrm {dB} \,\!}$

Здесь снова предполагается , что шум квантования распределен равномерно. Когда входной сигнал имеет высокую амплитуду и широкий частотный спектр, это так. ^[16] В этом случае 16-битный АЦП имеет максимальное отношение сигнал/шум 98,09 дБ. Разница в 1,761 в отношении сигнал/шум возникает только из-за того, что сигнал представляет собой полномасштабную синусоидальную волну, а не треугольную или пилообразную.

Для сложных сигналов в АЦП высокого разрешения это точная модель. Для АЦП низкого разрешения, сигналов низкого уровня в АЦП высокого разрешения и для простых форм волн шум квантования распределен неравномерно, что делает эту модель неточной. ^[17] В этих случаях распределение шума квантования сильно зависит от точной амплитуды сигнала.

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

Дизайн

Гранулярные искажения и перегрузочные искажения

Часто конструкция квантизатора включает поддержку только ограниченного диапазона возможных выходных значений и выполнение отсечения для ограничения выходного сигнала этим диапазоном всякий раз, когда входной сигнал превышает поддерживаемый диапазон. Ошибка, вносимая этим отсечением, называется искажением перегрузки . В пределах крайних пределов поддерживаемого диапазона величина интервала между выбираемыми выходными значениями квантизатора называется его гранулярностью , а ошибка, вносимая этим интервалом, называется гранулярным искажением. Обычно при разработке квантизатора определяют правильный баланс между гранулярным искажением и искажением перегрузки. Для заданного поддерживаемого числа возможных выходных значений уменьшение среднего гранулярного искажения может повлечь за собой увеличение среднего искажения перегрузки, и наоборот. Методом управления амплитудой сигнала (или, что эквивалентно, размером шага квантования ) для достижения соответствующего баланса является использование автоматической регулировки усиления (АРУ). Однако в некоторых конструкциях квантователей концепции гранулярной ошибки и ошибки перегрузки могут не применяться (например, для квантователя с ограниченным диапазоном входных данных или со счетно бесконечным набором выбираемых выходных значений). ^[6] ${\displaystyle \Delta }$

Конструкция квантователя скорости-искажения

Скалярный квантователь, выполняющий операцию квантования, обычно можно разложить на два этапа:

Классификация

Процесс, который классифицирует диапазон входного сигнала на неперекрывающиеся интервалы , определяя граничные значения решения , такие, что для , с крайними пределами, определяемыми и . Все входы , которые попадают в заданный диапазон интервала, связаны с одним и тем же индексом квантования . ${\displaystyle M}$ ${\displaystyle \{I_{k}\}_{k=1}^{M}}$ ${\displaystyle M-1}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle I_{k}=[b_{k-1}~,~b_{k})}$ ${\displaystyle k=1,2,\ldots ,M}$ ${\displaystyle b_{0}=-\infty }$ ${\displaystyle b_{M}=\infty }$ ${\displaystyle x}$ ${\displaystyle I_{k}}$ ${\displaystyle k}$

Реконструкция

Каждый интервал представлен значением реконструкции , которое реализует отображение . ${\displaystyle I_{k}}$ ${\displaystyle y_{k}}$ ${\displaystyle x\in I_{k}\Rightarrow y=y_{k}}$

Эти два этапа вместе составляют математическую операцию . ${\displaystyle y=Q(x)}$

Методы энтропийного кодирования могут применяться для передачи индексов квантования от исходного кодера, который выполняет стадию классификации, к декодеру, который выполняет стадию реконструкции. Один из способов сделать это — связать каждый индекс квантования с двоичным кодовым словом . Важным соображением является количество бит, используемых для каждого кодового слова, обозначенное здесь как . В результате, проектирование -уровневого квантователя и связанного набора кодовых слов для передачи его значений индекса требует нахождения значений , и которые оптимально удовлетворяют выбранному набору ограничений проектирования, таким как скорость передачи данных и искажение . ${\displaystyle k}$ ${\displaystyle c_{k}}$ ${\displaystyle \mathrm {length} (c_{k})}$ ${\displaystyle M}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{c_{k}\}_{k=1}^{M}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$ ${\displaystyle R}$ ${\displaystyle D}$

Предполагая, что источник информации создает случайные величины с соответствующей плотностью вероятности , вероятность того, что случайная величина попадает в определенный интервал квантования, определяется по формуле: ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle f(x)}$ ${\displaystyle p_{k}}$ ${\displaystyle I_{k}}$

${\displaystyle p_{k}=P[x\in I_{k}]=\int _{b_{k-1}}^{b_{k}}f(x)dx}$.

Результирующая скорость передачи данных в единицах среднего количества бит на квантованное значение для этого квантователя может быть получена следующим образом: ${\displaystyle R}$

${\displaystyle R=\sum _{k=1}^{M}p_{k}\cdot \mathrm {length} (c_{k})=\sum _{k=1}^{M}\mathrm {length} (c_{k})\int _{b_{k-1}}^{b_{k}}f(x)dx}$.

Если предположить, что искажение измеряется с помощью среднеквадратической ошибки, ^[a] искажение D определяется по формуле:

${\displaystyle D=E[(x-Q(x))^{2}]=\int _{-\infty }^{\infty }(x-Q(x))^{2}f(x)dx=\sum _{k=1}^{M}\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx}$.

Ключевым наблюдением является то, что скорость зависит от границ решения и длины кодового слова , тогда как искажение зависит от границ решения и уровней реконструкции . ${\displaystyle R}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{\mathrm {length} (c_{k})\}_{k=1}^{M}}$ ${\displaystyle D}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$

После определения этих двух показателей производительности квантизатора типичная формула «скорость-искажение» для задачи проектирования квантизатора может быть выражена одним из двух способов:

1. Учитывая максимальное ограничение искажения , минимизируйте скорость передачи данных ${\displaystyle D\leq D_{\max }}$ ${\displaystyle R}$
2. Учитывая ограничение максимальной скорости передачи данных , минимизируйте искажения ${\displaystyle R\leq R_{\max }}$ ${\displaystyle D}$

Часто решение этих проблем может быть эквивалентно (или приблизительно) выражено и решено путем преобразования формулировки в задачу без ограничений , где множитель Лагранжа является неотрицательной константой, которая устанавливает соответствующий баланс между скоростью и искажением. Решение задачи без ограничений эквивалентно нахождению точки на выпуклой оболочке семейства решений для эквивалентной формулировки задачи с ограничениями. Однако нахождение решения — особенно решения в замкнутой форме — для любой из этих трех формулировок задачи может быть сложным. Решения, не требующие многомерных итеративных методов оптимизации, были опубликованы только для трех распределений PDF: равномерного, ^[18] экспоненциального , ^[12] и распределения Лапласа ^[12] . Подходы итеративной оптимизации могут использоваться для поиска решений в других случаях. ^{[6] [19] [20]} ${\displaystyle \min \left\{D+\lambda \cdot R\right\}}$ ${\displaystyle \lambda }$

Обратите внимание, что значения реконструкции влияют только на искажение — они не влияют на скорость передачи данных — и что каждое из них вносит свой вклад в общее искажение, как показано ниже: ${\displaystyle \{y_{k}\}_{k=1}^{M}}$ ${\displaystyle y_{k}}$ ${\displaystyle d_{k}}$

${\displaystyle D=\sum _{k=1}^{M}d_{k}}$

где

${\displaystyle d_{k}=\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx}$

Это наблюдение можно использовать для упрощения анализа — учитывая набор значений, значение каждого из них можно оптимизировать по отдельности, чтобы минимизировать его вклад в искажение . ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle y_{k}}$ ${\displaystyle D}$

Для критерия искажения среднеквадратической ошибки можно легко показать, что оптимальный набор значений реконструкции задается путем установки значения реконструкции в каждом интервале на условное ожидаемое значение (также называемое центроидом ) в пределах интервала, как указано ниже: ${\displaystyle \{y_{k}^{*}\}_{k=1}^{M}}$ ${\displaystyle y_{k}}$ ${\displaystyle I_{k}}$

${\displaystyle y_{k}^{*}={\frac {1}{p_{k}}}\int _{b_{k-1}}^{b_{k}}xf(x)dx}$.

Использование достаточно хорошо разработанных методов энтропийного кодирования может привести к использованию скорости передачи данных, близкой к истинному информационному содержанию индексов , так что эффективно ${\displaystyle \{k\}_{k=1}^{M}}$

${\displaystyle \mathrm {length} (c_{k})\approx -\log _{2}\left(p_{k}\right)}$

и поэтому

${\displaystyle R=\sum _{k=1}^{M}-p_{k}\cdot \log _{2}\left(p_{k}\right)}$.

Использование этого приближения может позволить отделить проблему проектирования энтропийного кодирования от проектирования самого квантователя. Современные методы энтропийного кодирования, такие как арифметическое кодирование, могут достигать скоростей передачи данных, которые очень близки к истинной энтропии источника, учитывая набор известных (или адаптивно оцененных) вероятностей . ${\displaystyle \{p_{k}\}_{k=1}^{M}}$

В некоторых проектах, вместо оптимизации для определенного числа областей классификации , проблема проектирования квантователя может включать оптимизацию значения также. Для некоторых вероятностных моделей источников наилучшая производительность может быть достигнута при приближении к бесконечности. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

Пренебрежение ограничением энтропии: квантование Ллойда–Макса

В приведенной выше формулировке, если пренебречь ограничением скорости передачи данных, установив его равным 0, или, что эквивалентно, если предположить, что для представления квантованных данных будет использоваться код фиксированной длины (FLC) вместо кода переменной длины (или какая-либо другая технология энтропийного кодирования, например арифметическое кодирование, которое лучше FLC в смысле скорости-искажения), задача оптимизации сводится к минимизации только искажения . ${\displaystyle \lambda }$ ${\displaystyle D}$

Индексы, полученные квантователем уровня -level, можно кодировать с помощью кода фиксированной длины, используя биты/символ. Например, при 256 уровнях битрейт FLC составляет 8 бит/символ. По этой причине такой квантователь иногда называют 8-битным квантователем. Однако использование FLC исключает улучшение сжатия, которое может быть получено с помощью лучшего энтропийного кодирования. ${\displaystyle M}$ ${\displaystyle R=\lceil \log _{2}M\rceil }$ ${\displaystyle M=}$ ${\displaystyle R}$

Предполагая FLC с уровнями, проблема минимизации скорости-искажения может быть сведена к минимизации искажения. Сокращенная проблема может быть сформулирована следующим образом: учитывая источник с PDF и ограничение, что квантизатор должен использовать только области классификации, найти границы решения и уровни реконструкции, чтобы минимизировать результирующее искажение ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle f(x)}$ ${\displaystyle M}$ ${\displaystyle \{b_{k}\}_{k=1}^{M-1}}$ ${\displaystyle \{y_{k}\}_{k=1}^{M}}$

${\displaystyle D=E[(x-Q(x))^{2}]=\int _{-\infty }^{\infty }(x-Q(x))^{2}f(x)dx=\sum _{k=1}^{M}\int _{b_{k-1}}^{b_{k}}(x-y_{k})^{2}f(x)dx=\sum _{k=1}^{M}d_{k}}$.

Нахождение оптимального решения вышеуказанной проблемы приводит к квантователю, иногда называемому решением MMSQE (минимальная среднеквадратичная ошибка квантования), а полученный оптимизированный по PDF (неравномерный) квантователь называется квантователем Ллойда–Макса , названным в честь двух людей, которые независимо друг от друга разработали итерационные методы ^{[6] [21] [22]} для решения двух наборов одновременных уравнений, полученных из и , следующим образом: ${\displaystyle {\partial D/\partial b_{k}}=0}$ ${\displaystyle {\partial D/\partial y_{k}}=0}$

${\displaystyle {\partial D \over \partial b_{k}}=0\Rightarrow b_{k}={y_{k}+y_{k+1} \over 2}}$,

который помещает каждый порог в среднюю точку между каждой парой значений реконструкции, и

${\displaystyle {\partial D \over \partial y_{k}}=0\Rightarrow y_{k}={\int _{b_{k-1}}^{b_{k}}xf(x)dx \over \int _{b_{k-1}}^{b_{k}}f(x)dx}={\frac {1}{p_{k}}}\int _{b_{k-1}}^{b_{k}}xf(x)dx}$

который помещает каждое значение реконструкции в центроид (условное ожидаемое значение) соответствующего ему интервала классификации.

Алгоритм метода Ллойда I , первоначально описанный в 1957 году, может быть обобщен простым способом для применения к векторным данным. Это обобщение приводит к методам оптимизации классификатора Линде–Бузо–Грея (LBG) или k-средних . Более того, метод может быть дополнительно обобщен простым способом, чтобы также включить ограничение энтропии для векторных данных. ^[23]

Равномерное квантование и приближение 6 дБ/бит

Квантизатор Ллойда–Макса на самом деле является равномерным квантователем, когда входная PDF равномерно распределена по диапазону . Однако для источника, который не имеет равномерного распределения, квантователь с минимальным искажением может не быть равномерным квантователем. Анализ равномерного квантователя, примененного к равномерно распределенному источнику, можно суммировать следующим образом: ${\displaystyle [y_{1}-\Delta /2,~y_{M}+\Delta /2)}$

Симметричный источник X можно смоделировать с помощью , для и 0 в любом другом месте. Размер шага и отношение сигнала к шуму квантования (SQNR) квантизатора равны ${\displaystyle f(x)={\tfrac {1}{2X_{\max }}}}$ ${\displaystyle x\in [-X_{\max },X_{\max }]}$ ${\displaystyle \Delta ={\tfrac {2X_{\max }}{M}}}$

${\displaystyle {\rm {SQNR}}=10\log _{10}{\frac {\sigma _{x}^{2}}{\sigma _{q}^{2}}}=10\log _{10}{\frac {(M\Delta )^{2}/12}{\Delta ^{2}/12}}=10\log _{10}M^{2}=20\log _{10}M}$.

Для кода фиксированной длины, использующего биты, , что приводит к , ${\displaystyle N}$ ${\displaystyle M=2^{N}}$ ${\displaystyle {\rm {SQNR}}=20\log _{10}{2^{N}}=N\cdot (20\log _{10}2)=N\cdot 6.0206\,{\rm {dB}}}$

или приблизительно 6 дБ на бит. Например, для =8 бит, =256 уровней и SQNR = 8×6 = 48 дБ; и для =16 бит, =65536 и SQNR = 16×6 = 96 дБ. Свойство улучшения SQNR на 6 дБ для каждого дополнительного бита, используемого при квантовании, является общеизвестным показателем качества. Однако его следует использовать с осторожностью: этот вывод применим только для однородного квантователя, применяемого к однородному источнику. Для других исходных PDF и других конструкций квантователей SQNR может несколько отличаться от предсказанного 6 дБ/бит, в зависимости от типа PDF, типа источника, типа квантователя и диапазона скорости передачи битов операции. ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle M}$

Однако принято считать, что для многих источников наклон функции квантователя SQNR может быть аппроксимирован как 6 дБ/бит при работе на достаточно высокой скорости передачи данных. При асимптотически высоких скоростях передачи данных сокращение размера шага вдвое увеличивает скорость передачи данных примерно на 1 бит на выборку (поскольку 1 бит необходим для указания того, находится ли значение в левой или правой половине предыдущего интервала двойного размера) и уменьшает среднеквадратичную ошибку в 4 раза (т. е. на 6 дБ) на основе аппроксимации . ${\displaystyle \Delta ^{2}/12}$

При асимптотически высоких скоростях передачи данных приближение 6 дБ/бит поддерживается для многих исходных PDF-файлов строгим теоретическим анализом. ^{[2] [3] [5] [6]} Более того, структура оптимального скалярного квантователя (в смысле скорости-искажения) приближается к структуре равномерного квантователя в этих условиях. ^{[5] [6]}

В других областях

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

Смотрите также

• Бета-кодер
• Квантование цвета
• Объединение данных
• Дискретизация
• Ошибка дискретизации
• Постеризация
• Импульсно-кодовая модуляция
• Квантиль
• Квантование (обработка изображений)
• Разбавление регрессии – смещение оценок параметров, вызванное ошибками, такими как квантование в объясняющей или независимой переменной.

Примечания

1. Можно также рассмотреть и другие меры искажения, хотя наиболее популярной является среднеквадратическая ошибка.

Ссылки

1. Шеппард, У. Ф. (1897). «О вычислении наиболее вероятных значений частотных констант для данных, расположенных в соответствии с равнопромежуточным делением шкалы». Труды Лондонского математического общества . s1-29 (1). Wiley: 353–380. doi :10.1112/plms/s1-29.1.353. ISSN  0024-6115.
2. WR Bennett, «Спектры квантованных сигналов», Bell System Technical Journal , т. 27, стр. 446–472, июль 1948 г.
3. Оливер, Б. М.; Пирс, Дж. Р.; Шеннон, CE (1948). «Философия PCM». Труды IRE . 36 (11). Институт инженеров по электротехнике и электронике (IEEE): 1324–1331. doi :10.1109/jrproc.1948.231941. ISSN  0096-8390. S2CID  51663786.
4. Сеймур Стайн и Дж. Джей Джонс, Современные принципы коммуникации , McGraw–Hill , ISBN 978-0-07-061003-3 , 1967 (стр. 196). 
5. Gish, H.; Pierce, J. (1968). «Асимптотически эффективное квантование». IEEE Transactions on Information Theory . 14 (5). Институт инженеров по электротехнике и электронике (IEEE): 676–683. doi :10.1109/tit.1968.1054193. ISSN  0018-9448.
6. Gray, RM ; Neuhoff, DL (1998). «Квантование». IEEE Transactions on Information Theory . 44 (6). Институт инженеров по электротехнике и электронике (IEEE): 2325–2383. doi :10.1109/18.720541. ISSN  0018-9448. S2CID  212653679.
7. Аллен Гершо ; Роберт М. Грей (1991). Вектор квантования и сжатие сигнала. Springer . ISBN 978-0-7923-9181-4.
8. Hodgson, Jay (2010). Understanding Records , стр. 56. ISBN 978-1-4411-5607-5 . Адаптировано из Franz, David (2004). Recording and Producing in the Home Studio , стр. 38-9. Berklee Press. 
9. Gersho, A. (1977). «Квантование». Журнал IEEE Communications Society . 15 (5). Институт инженеров по электротехнике и электронике (IEEE): 16–28. doi :10.1109/mcom.1977.1089500. ISSN  0148-9615. S2CID  260498692.
10. Раббани, Маджид; Джоши, Раджан Л.; Джонс, Пол В. (2009). «Раздел 1.2.3: Квантование, в Главе 1: Основная система кодирования JPEG 2000 (часть 1)». В Schelkens, Питер; Skodras, Афанассиос; Ebrahimi, Турадж (ред.). JPEG 2000 Suite . John Wiley & Sons . стр. 22–24. ISBN 978-0-470-72147-6.
11. Таубман, Дэвид С.; Марселлин, Майкл В. (2002). "Глава 3: Квантование". JPEG2000: Основы, стандарты и практика сжатия изображений . Kluwer Academic Publishers . стр. 107. ISBN 0-7923-7519-X.
12. Салливан, Г. Дж. (1996). «Эффективное скалярное квантование экспоненциальных и лапласовских случайных величин». Труды IEEE по теории информации . 42 (5). Институт инженеров по электротехнике и электронике (IEEE): 1365–1374. doi :10.1109/18.532878. ISSN  0018-9448.
13. Видроу, Б. (1956). «Исследование грубого амплитудного квантования с помощью теории выборок Найквиста». Труды IRE по теории цепей . 3 (4). Институт инженеров по электротехнике и электронике (IEEE): 266–276. doi : 10.1109/tct.1956.1086334. hdl : 1721.1/12139 . ISSN  0096-2007. S2CID  16777461.
14. Бернард Видроу , «Статистический анализ систем выборочных данных с квантованием амплитуды», Trans. AIEE Pt. II: Appl. Ind. , Vol. 79, pp. 555–568, January 1961.
15. Marco, D.; Neuhoff, DL (2005). «Достоверность модели аддитивного шума для однородных скалярных квантователей». Труды IEEE по теории информации . 51 (5). Институт инженеров по электротехнике и электронике (IEEE): 1739–1755. doi :10.1109/tit.2005.846397. ISSN  0018-9448. S2CID  14819261.
16. Полман, Кен С. (1989). Принципы цифрового аудио, 2-е издание. САМС. п. 60. ИСБН 9780071441568.
17. Уоткинсон, Джон (2001). Искусство цифрового звука 3-е издание . Focal Press . ISBN 0-240-51587-0.
18. Фарвардин, Н.; Модестино, Дж. (1984). «Оптимальная производительность квантователя для класса негауссовых источников без памяти». Труды IEEE по теории информации . 30 (3). Институт инженеров по электротехнике и электронике (IEEE): 485–497. doi :10.1109/tit.1984.1056920. ISSN  0018-9448.(Раздел VI.C и Приложение B)
19. Бергер, Т. (1972). «Оптимальные квантователи и перестановочные коды». Труды IEEE по теории информации . 18 (6). Институт инженеров по электротехнике и электронике (IEEE): 759–765. doi :10.1109/tit.1972.1054906. ISSN  0018-9448.
20. Бергер, Т. (1982). «Минимальные энтропийные квантователи и перестановочные коды». Труды IEEE по теории информации . 28 (2). Институт инженеров по электротехнике и электронике (IEEE): 149–157. doi :10.1109/tit.1982.1056456. ISSN  0018-9448.
21. Ллойд, С. (1982). «Квантование по наименьшим квадратам в PCM». Труды IEEE по теории информации . 28 (2). Институт инженеров по электротехнике и электронике (IEEE): 129–137. CiteSeerX 10.1.1.131.1338 . doi :10.1109/tit.1982.1056489. ISSN  0018-9448. S2CID  10833328. (работа, задокументированная в рукописи, распространенной для комментариев в Bell Laboratories с датой регистрации отдела 31 июля 1957 года, а также представленная на заседании Института математической статистики в 1957 году , хотя официально не опубликованная до 1982 года).
22. Макс, Дж. (1960). «Квантование для минимального искажения». Труды IEEE по теории информации . 6 (1). Институт инженеров по электротехнике и электронике (IEEE): 7–12. doi :10.1109/tit.1960.1057548. ISSN  0018-9448.
23. Chou, PA; Lookabaugh, T.; Gray, RM (1989). «Векторное квантование с ограничением энтропии». Труды IEEE по акустике, речи и обработке сигналов . 37 (1). Институт инженеров по электротехнике и электронике (IEEE): 31–42. doi :10.1109/29.17498. ISSN  0096-3518.

• Сайуд, Халид (2005), Введение в сжатие данных, третье издание , Морган Кауфманн, ISBN 978-0-12-620862-7
• Джайант, Никил С.; Нолл, Питер (1984), Цифровое кодирование волновых форм: принципы и применение к речи и видео , Prentice–Hall, ISBN 978-0-13-211913-9
• Грегг, У. Дэвид (1977), Аналоговая и цифровая связь , John Wiley, ISBN 978-0-471-32661-8
• Стайн, Сеймур; Джонс, Дж. Джей (1967), Современные принципы коммуникации , McGraw–Hill , ISBN 978-0-07-061003-3

Дальнейшее чтение

• Бернард Видроу; Иштван Коллар (2007). Шум квантования в цифровых вычислениях, обработке сигналов и управлении. Cambridge University Press. ISBN 9780521886710.

Смотрите также

• Наименьшее количество