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

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

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

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

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

Пример

Например, округление действительного числа до ближайшего целого значения образует очень простой тип квантователя – унифицированный . Типичный ( средний шаг ) равномерный квантователь с размером шага квантования , равным некоторому значению, может быть выражен как ${\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}$ ${\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(\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)}$.

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

В общем, квантователь со средним подступенком или средней ступенью может на самом деле не быть однородным квантователем, т. е. не все размеры классификационных интервалов квантователя могут быть одинаковыми или расстояние между его возможными выходными значениями может не быть одинаковым. . Отличительной характеристикой квантователя средней ступени является то, что он имеет пороговое значение классификации, которое равно нулю, а отличительной характеристикой квантователя средней ступени является то, что он имеет значение восстановления, которое точно равно нулю. ^[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)}$,

где функция ( ) является знаковой функцией (также известной как функция Signum ). Общее правило восстановления для такого квантователя мертвой зоны определяется выражением ${\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). Хотя в целом оно может зависеть от и может быть выбрано для выполнения условия оптимальности, описанного ниже, часто ему просто присваивается константа, например . (Обратите внимание, что в этом определении из-за определения функции ( ) это не имеет никакого эффекта.) ${\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) членом . Среднеквадратические значения ошибки по переменному току в обоих случаях одинаковы, поэтому нет особого преимущества округления перед усечением в ситуациях, когда член ошибки по постоянному току можно игнорировать (например, в системах, связанных по переменному току). В любом случае стандартное отклонение, выраженное в процентах от полного диапазона сигнала, изменяется в 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)}$

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

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

Сравнение квантования синусоиды до 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}$

Предполагая, что источник информации создает случайные величины со связанным PDF , вероятность того, что случайная величина попадает в определенный интервал квантования, определяется выражением: ${\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}$

Индексы, создаваемые квантователем уровня, могут быть закодированы с использованием кода фиксированной длины с использованием битов/символов. Например, при 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 можно смоделировать с помощью , for и 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. Шеппард, WF (1897). «О расчете наиболее вероятных значений констант частоты для данных, упорядоченных по эквидистантному делению шкалы». Труды Лондонского математического общества . Уайли. с1-29(1): 353–380. дои : 10.1112/plms/s1-29.1.353. ISSN  0024-6115.
2. WR Беннетт, «Спектры квантованных сигналов», Технический журнал Bell System , Vol. 27, стр. 446–472, июль 1948 г.
3. Оливер, Б.М.; Пирс, младший; Шеннон, CE (1948). «Философия ПКМ». Труды ИРЭ . Институт инженеров по электротехнике и электронике (IEEE). 36 (11): 1324–1331. дои : 10.1109/jrproc.1948.231941. ISSN  0096-8390. S2CID  51663786.
4. Сеймур Стайн и Дж. Джей Джонс, Современные принципы коммуникации , McGraw – Hill , ISBN 978-0-07-061003-3 , 1967 (стр. 196). 
5. Гиш, Х.; Пирс, Дж. (1968). «Асимптотически эффективное квантование». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 14 (5): 676–683. дои : 10.1109/тит.1968.1054193. ISSN  0018-9448.
6. Грей, РМ ; Нойхофф, Д.Л. (1998). «Квантование». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 44 (6): 2325–2383. дои : 10.1109/18.720541. ISSN  0018-9448. S2CID  212653679.
7. Аллен Гершо ; Роберт М. Грей (1991). Векторное квантование и сжатие сигналов. Спрингер . ISBN 978-0-7923-9181-4.
8. Ходжсон, Джей (2010). Понимание записей , стр.56. ISBN 978-1-4411-5607-5 . Адаптировано из книги Франца Дэвида (2004). Запись и продюсирование в домашней студии , стр.38-9. Беркли Пресс. 
9. Гершо, А. (1977). «Квантование». Журнал Общества связи IEEE . Институт инженеров по электротехнике и электронике (IEEE). 15 (5): 16–28. дои : 10.1109/mcom.1977.1089500. ISSN  0148-9615. S2CID  260498692.
10. Раббани, Маджид; Джоши, Раджан Л.; Джонс, Пол В. (2009). «Раздел 1.2.3: Квантование, в главе 1: Базовая система кодирования JPEG 2000 (Часть 1)». В Шелкенсе, Питер; Скодрас, Афанасий; Эбрахими, Турадж (ред.). Пакет JPEG 2000 . Джон Уайли и сыновья . стр. 22–24. ISBN 978-0-470-72147-6.
11. Таубман, Дэвид С.; Марселлин, Майкл В. (2002). «Глава 3: Квантование». JPEG2000: основы, стандарты и практика сжатия изображений . Академическое издательство Kluwer . п. 107. ИСБН 0-7923-7519-Х.
12. Салливан, GJ (1996). «Эффективное скалярное квантование экспоненциальных и лапласовских случайных величин». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 42 (5): 1365–1374. дои : 10.1109/18.532878. ISSN  0018-9448.
13. Уидроу, Б. (1956). «Исследование грубого амплитудного квантования с помощью теории выборки Найквиста». IRE Транзакции по теории цепей . Институт инженеров по электротехнике и электронике (IEEE). 3 (4): 266–276. дои : 10.1109/tct.1956.1086334. hdl : 1721.1/12139 . ISSN  0096-2007. S2CID  16777461.
14. Бернард Уидроу , «Статистический анализ систем дискретных данных с квантованием амплитуды», Trans. AIEE Пт. II: Прил. Инди. , Том. 79, стр. 555–568, январь 1961 г.
15. Марко, Д.; Нойхофф, Д.Л. (2005). «Применимость модели аддитивного шума для равномерных скалярных квантователей». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 51 (5): 1739–1755. дои : 10.1109/tit.2005.846397. ISSN  0018-9448. S2CID  14819261.
16. Полман, Кен С. (1989). Принципы цифрового аудио, 2-е издание. САМС. п. 60. ИСБН 9780071441568.
17. Уоткинсон, Джон (2001). Искусство цифрового аудио, 3-е издание . Фокальная пресса . ISBN 0-240-51587-0.
18. Фарвардин, Н .; Модестино, Дж. (1984). «Оптимальная производительность квантователя для класса негауссовских источников без памяти». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 30 (3): 485–497. дои : 10.1109/тит.1984.1056920. ISSN  0018-9448.(Раздел VI.C и Приложение B)
19. Бергер, Т. (1972). «Оптимальные квантователи и коды перестановок». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 18 (6): 759–765. дои : 10.1109/тит.1972.1054906. ISSN  0018-9448.
20. Бергер, Т. (1982). «Квантаторы минимальной энтропии и коды перестановок». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 28 (2): 149–157. дои : 10.1109/тит.1982.1056456. ISSN  0018-9448.
21. Ллойд, С. (1982). «Квантование по методу наименьших квадратов в PCM». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 28 (2): 129–137. CiteSeerX 10.1.1.131.1338 . дои : 10.1109/тит.1982.1056489. ISSN  0018-9448. S2CID  10833328. (работа задокументирована в рукописи, распространенной для комментариев в Bell Laboratories с датой журнала отдела от 31 июля 1957 года, а также представленной на заседании Института математической статистики 1957 года , хотя официально не публиковалась до 1982 года).
22. Макс, Дж. (1960). «Квантование для минимальных искажений». Транзакции IEEE по теории информации . Институт инженеров по электротехнике и электронике (IEEE). 6 (1): 7–12. дои : 10.1109/тит.1960.1057548. ISSN  0018-9448.
23. Чжоу, Пенсильвания; Лукабо, Т.; Грей, РМ (1989). «Векторное квантование с ограничением энтропии». Транзакции IEEE по акустике, речи и обработке сигналов . Институт инженеров по электротехнике и электронике (IEEE). 37 (1): 31–42. дои : 10.1109/29.17498. ISSN  0096-3518.

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

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

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

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

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