Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 94
Текст из файла (страница 94)
Во-первых, при определенных условиях переполнение при суммировании двух чисел не приводит к ошибке. Во-вторых, при выполнении множества сложений промежуточные ошибки переполнения не сказываются на окончательной сумме, если результирующий модуль суммы Ь-битовых двоичных дополнительных чисел меньше 2ь 1. Проиллюстрируем эти свойства, рассмотрев четырехбитовый двоичный дополнительный формат на рисунке 12.5, двоичные значения которого взяты из таблицы 12.2. 463 12.3.
Э екты конечной длины слова... Десятичный эквивалент шп +7 +в +з аюа Рис. 12.6. Четырехбитовые двоичные дополнительные числа Первое свойство двоичного дополнительного переполнения, которое иногда не дает ошибок, можно показать на следующих примерах: 0 1 0 - биты переноса -5 в двоичном дополнительном формате - 1 0 1 1 +2 в двоичном дополнительном формате - + 0 0 1 0 -3 в двоичном дополнительном формате— 01101 -правильный отрицательный результат нулевой перенос из знакового бита 1 1 0 - биты переноса -2 в двоичном дополнительном формате- 1 1 1 0 +6 в двоичном дополнительном формате- + 0 1 1 0 +4 в двоичном дополнительном формате- 1 0 1 0 0 — правильный положительный результат перенос из знакового бита игнорируется, ошибка не возникает 464 Глава 12.
и овые о матыданныкиих аль в об аботкв сигналов Следующие примеры показывают, как иногда переполнение двоичных дополнительных чисел приводит к ошибкам: 0 0 0 - биты переноса -7 в двоичном дополнительном формате- 1001 -6 в двоичном дополнительном формате - + 1 0 1 0 10011 -неверный положительный результат +3 в двоичном дополнительном формате -. перенос из знакового бита игнорируется, что вызывает ошибку 1 1 1 биты переноса +7 в двоичном дополнительном формате - 0 1 1 1 +7 в двоичном дополнительном формате - + 0 1 1 1 0 1 1 1 0 - неверный отрицательный результат -2 в двоичном дополнительном формате- нулевой перенос из знакового бита +7 в двоичном дополнительном формате - 0 1 1 1 +6 в двоичном дополнительном формате - + 0 1 1 0 -3 в двоичном дополнительном формате - 1 1 0 1 - ошибка переполнения -7 в двоичном дополнительном формате - + 1 0 0 1 +6 в двоичном дополнительном формате - 1 0 1 1 0 — правильный положительный результат переполнение игнорируется без последствий Модуль суммы трех четырехбитовых чисел был меньше 24 ! (<8), следовательно, результат оказался правильным.
Если мы сложим +6 и +7, а затем прибавим — 5, мы получим переполнение промежуточной суммы, и окончательный результат будет неверным, потому что его модуль не меньше 8. Правило, применяемое в случае сложения двоичных дополнительных чисел, гласит, что, если бит переноса в знаковый разряд совпадает с битом переноса из знакового разряда, бит переполнения можно игнорировать без риска вызвать оигибку; если же бит переноса в знаковый бит отличается от бита переполнения, резулыпат неверный. Еще более интересно свойство двоичного дополнительного кода, состоящее в том, что последовательность Ь-битовых сложений может приводить к ошибкам переполнения промежуточных результатов, но конечная сумма оказывается правильной, если ее модуль меньше 2ь 1. Мы покажем это на следующем примере.
Если мы складываем «-6 с +7, а затем к сумме прибавляем — 7, мы получим ошибку переполнения промежуточной суммы, но наша конечная сумма будет правильной: 12.3. Э кты конечнойдлины слова... 455 +7 в даоичном дополнительном формате - О 1 1 1 +6 в двоичном дополнительном формате - + О 1 1 О -3 вдвоичном дополнительном формате - 1 1 О 1 -ошибка переполнения -5 в двоичном дополнительном формате - + 1 О 1 1 +6 вдвоичном дополнительном формате- 1 1 О О О - правильный положительный результат Другая ситуация, в которой проявляются проблемы переполнений — вычисление БПФ. На первых порах трудно себе представить, что умножение комплексных чисел на синусы и косинусы может привести к чрезмерному росту длины слова данных — особенно потому, что синусы и косинусы по модулю меньше единицы.
Мы можем'показать, как растет длина слова данных, рассмотрев бабочку БПФ с прореживанием по времени, показанную на рисунке 4.14(с), которую мы повторяем на рисунке 12.6, и пройдя через некоторые алгебраические преобразования. Выражение для выхода х'атой бабочки, согласно (4-26), имеет вид х' = х +%'ч ° у . к (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 Т)~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
