Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 91
Текст из файла (страница 91)
к (12-17) Рис. 12.5. Бабочка БПФ с прореживанием по времени Разбив входы бабочки х и,у на действительные и мнимые части и вспомнив, что И'~ч = е-Ркк ''т, мы можем записать (12-17) как к х = хтеа1 ~Жтах ~(е 7 ) (утеа! ~.1уииак) (12 18) Если мы через а обозначим угол поворачивающего множителя 2лй/Ми вспомним, что е л' = соз(а) — 7яп(а), мы можем записать (12-18) в более простом виде х' = х„ы+7х;и, асов(а) — 7з(п(аН ' (у„„ы+7уьк,х) = х „1+ соз(а)Ума(+ з1~(~)Нт +Ит Х+ соз(а)У; ~~ зш(а)Утеад ' (12-19) Рассмотрим, например, только действительную часть х'„, невыхода х'. Она содержит три члена х теа~ = хтеа! + соз(а)утеЫ ч. зш(п)у; (12-20) Если х „ау 1и у;„имеют на входе в бабочку единичные значения, а угол поворачивающего множителя оказывается равным х/4 = 45', тох' 1может оказаться больше 2, т.
к. х' ы = 1 + соз(45') ° 1 + яп(45') ° 1 = 1 + 0707+ 0707 = 2414,,(12-21) 4вв Глава 12. и овыв матыданных и ик оль в об аботкв сигналов Таким образом, мы видим, что действительная часть комплексного числа может более чем удвоиться при выполнении одного каскада БПФ. Мнимая часть комплексного числа тоже может на одном каскаде БПФ более чем удвоиться.
Без решения этой проблемы, связанной с увеличением длины слова, переполнения могут сделать алгоритм практически неприменимым. Проблема переполнений может решаться одним из двух способов — с помощью усечения или округления, каждый из которых, как мы увидим, вносит свои ошибки квантования. 12.3.3. Усечение Усечение представляет собой процедуру, в результате которой значение данных представляется наибольшим уровнем квантования, который не превосходит это значение.
Если уровни квантования обозначены целыми числами, например, действительное значение 1.2 будет усечено до 1. Пример усечения до целых значений приведен на рисунке 12.7 (а), где все значения х в диапазоне 0 < х < 1 приравниваются к О, значения х в диапазоне 1 < х < 2 приравниваются к 1, значения х в диапазоне 2 < х < 3 приравниваются к 2 и так далее. Как и в случае ошибок квантования АЦП, мы можем для описания ошибок, вносимых усечением, прибегнуть к понятию функции плотности вероятности.
Функция плотности вероятности ошибок усечения в терминах шага квантования показана на рисунке 12.7 (Ь). На рисунке 12.7 (а) шаг квантования д равен 1, следовательно, в этом случае мы можем иметь ошибки квантования, достигающие — 1. Используя результаты из (Р-11) и (Р-12) приложения Р, мы можем выразить среднее и дисперсию для равномерной функции плотности вероятности как 1тусэчээцэ = Ч/2 (12-22) (12-23) В некотором смысле ошибка усечения — это цена, которую мы платим за привилегию использования целочисленной двоичной арифметики.
Одно из ее проявлений — ошибка, вносимая при использовании усечения в процессе деления на целую степень двойки. Мы часто говорим, что быстрый способ деления двоичного числа на 2Г состоит в сдвиге двоичного слова на Тбитов вправо, т. е. мы усекаем значение данных (но не слово данных), отсекая после сдвига правые Тбитов. Допустим, например, что мы имеем значение 31, представленное пятибитовым двоичным числом 111112, и мы хотим разделить его на 16, используя сдвиг битов на Т = 4 позиции вправо и игнорируя (отсекая) сдвинутые биты. После сдвига вправо и усечения мы получим двоичное частное 31/16 - 000012. Здесь мы видим значимость проблемы, потому что быстрое деление дало нам в результате единицу вместо правильного результата 31/16 = 1.9375.
Ошибка деления с усечением составляет здесь почти 50 % правильного ответа. Если бы исходное делимое было равно 63 и представлено шестибитовым двоичным числом 1111112, то деление его на 16 путем сдвига вправо на четыре бита дало бы нам двоичный результат 0000112, или 31э. Правильный результат, конечно же, равен 63/16 = 3.9375. В этом случае относительная ошибка составляет 0.9375/3.9375, или примерно 23.8 %. Следовательно, чем больше делимое, тем меньше относительная ошибка усечения.
467 12.3. Э екты конечной донны слова... (а) Функция плотности вероятности д ошибки усечения (Ь) 0 Значение ошибки Рис. 12.7. Усечение: (а) нелинейность квантования; (Ь) функция плотности вероят- ности ошибки Если мы займемся изучением этого вида ошибок, то обнаружим, что результирующая ошибка усечения зависит от трех факторов: количества сдвигаемых и усекаемых битов, значений усекаемых битов (т.е. были эти биты равны нулю или единице) и модуля двоичного числа, оставшегося после усечения. Хотя полный анализ ошибок усечения выходит за рамки этой книги, мы можем оценить максимальную ошибку, которая может возникнуть в нашей схеме деления с усечением при использовании двоичной целочисленной арифметики. Наихудшей будет ситуация, когда все усекаемые биты равны единице.
Для целых двоичных чисел значение комбинации из Тединичных бит справа от запятой равно 1 — 2 т. Если полученное частное Ю мало, значение этих усеченных единиц увеличивает ошибку. Мы можем нормировать максимальную ошибку деления, используя относительную меру ошибки. Таким образом, максимальная относительная ошибка двоичного частного )У после усечения перед Т-битовым сдвигом вправо в случае, когда все отбрасываемые биты равны единице, равна %ошибка усечен ият ((2-24) = 100и(Правильное частное — Частное после усвчвния)/(Лравильное частное) = = 100'(Ошибкаусвчвния)/(Правильновчаппнов) = 1№(1 — 2 Т)/~У+(1-2 Т)~.
Чтобы понять значение выражения (12-24), подставим в него некоторые числа. В первом примере, для деления 31/16, где Т = 4 и частное Ж- 1, относительная ошибка составляет 100 ° (1 — 0.0625)/(1 -~- 1 — 0.0625) = 100 ° (0..9375/1.Я75) = 48.4 % 488 Глава 12. и оные о маты данных и их ель в об аботке сигналов Построив график по (12-24) для трех разных значений сдвига как функцию частного Ж после усечения, получаем рисунок 12.8. 50 45 40 З5 30 25 20 15 10 5 0 1 3 5 7 9 11 1315171921 2325272931 3335 3739 19 Рис.
12.8. Максимальная ошибка при использовании сдвига и усечения для реализации деления на 27. Т= 1 означает деление на 2; Т=2 соответствуетделению на 4, а Т= 8 — делению на 256 Таким образом, чтобы минимизировать этот тип ошибок деления, нам нужно, чтобы значение частного %было как можно больше. Помните, что (12-24) описывает наихудший случай, когда все усекаемые биты равны единице.
С другой стороны, если бы все отбрасываемые биты оказались равными нулю, ошибка была бы равной нулю. На практике ошибки будут где-то между этими крайними значениями. Практический пример того, как деление с усечением может порождать серьезные численные ошибки, приводится в 19], 12.3.4. Округление данных Округление — другой способ борьбы с ошибками переполнения, когда значение данных представляется ближайшим уровнем квантования, или округляется до него. Если уровни квантойания представлены целыми числами, число 1.2 в результате квантования даст 1, а квантование числа 1.6 даст результат, равный 2.
Это показано на рисунке 12.9 (д), где все значения х в диапазоне — 0.5 < х < 0.5 в результате округления превращаются в О, значения х в диапазоне 0.5 < х < 1.5 превращаются в 1, значения х в диапазоне 1.5 < х < 2.5 дают 2, и т. д. Функция плотности вероятности ошибки, вносимой при округлении, показана на рисунке 12.9 (Ц. На рисунке 12.9 (а) уровень квантования д равен 1, так что в этом случае мы можем иметь модуль ошибки не более 0/2, или 1/2.
И снова, используя (П-11) и (П-12) из приложения П, мы можем выразить среднее и дисперсию равномерной функции плотности вероятности как (12-25) и 02 12. (12-26) округления Ч / Поскольку средняя и максимальная ошибки, вызванные округлением, меньше соответствующих ошибок усечения, на практике обычно отдают предпочтение округлению, чтобы минимизировать ошибки переполнения. 12.3. екты конечнойдлины слова... (а) Функция плотности вероятности (Ь) -ф2 0 п12 Значение ошибки Рис.
12.9. Округление: (а) нелинейная характеристика квантования; (Ь) функция плотности вероятности ошибки В цифровой обработке сигналов статистический анализ влияния ошибки квантования обычно очень сложен. Аналитические результаты зависят от типов ошибок квантования, амплитуды квантуемого сигнала, от используемого формата данных и от того, какую из множества структур БПФ или цифровых фильтров мы используем. Как бы то ни было, эксперты цифровой обработки сигналов разработали упрощенные модели ошибки, анализ которых оказался полезным. Обсуждение этих методов анализа и их результатов выходит за рамки этой вводной книги, но для активного читателя найдется множество дополнительных источников информации 110-18].
(В работе 1111 приведен обширный библиографический список по теме анализа ошибок квантования.) Проблемы переполнения при использовании двоичных форматов с фиксированной запятой, последствия которых мы пытаемся облегчить с помощью усечения и округления, возникают снова и снова, потому что многочисленные алгоритмы цифровой обработки сигналов включают огромное количество сложений и умножений. Это препятствие, особенно при аппаратурной реализации цифровых фильтров и БПФ, разработчикам удается обойти с помощью использования двоичных форматов с плавающей запятой. ° В 4ВО Глава 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
