Солонина А., Улахович Д. Алгоритмы и процессоры цифровой обработки сигналов (2002) (1095891), страница 6
Текст из файла (страница 6)
36) (1.34) х1(/г) х„(я)+ х,(я) (х,(я) -х,(я))ьу," хт(") Замечание Алгоритмы и процессоры цифровой обработки сигналов Алгоритм БПФ с прореживанием по частоте В этом случае входная посчеловательность т(//) делится пополам на /1//2 первых и /т/2 паслелних отсчетов и так до тех пор, пока нс сформируются /т/2 двухэлсментных послеловательнастей. Базовая операция "бабочка" будет описываться выражением (1.34), а ее направленный граф примет впд. показанный на рпс. 1.8. Рис. 1.8.
Операция "бабочка" с прореживанием по частоте Вычисление согласно данному алгоритму приводит к тол/у. что составлявшие Х(/г) ДПФ располагаются в порядке, соответствуюшем бит-реверсин, поэтому их необходимо пересортировать согласно естественному парялку. Например, Х(3) = Х(0!1) следует разместить па шестом месте, т. к. инверсный номер оказывается равным 110=46. Алгоритмы БПФ являются рекурсивными: невозможно рассчитать И/2-точечное ДПФ, не рассчитав предварительно И/4-точечное ДПФ. 1.3.2.
Дискретное преобразование Хартли (ДПХ] Дискретное преобразование Фурье отображает последовательность вещественных данных в комплексную область, где хорошо разработаны методы анализа, сушественно облегла!ощие изучение и трактовку колебательных процессов. Однако обработку вешественных данных желательно выполнять в вешественной области. Эту задачу решаст дискретное преобразование Хартли (ДПХ). которое, как и ДПФ. люжет прил/еняться в задачах спектрального анализа и цифровой фильтрации. Глава /. Методы и алгоритмы цифровой обработки сигналов Прямое и обратное дискретное преобразование Хартли вешсствепной по- следовательности х(л) длины /Ч опрелеля/отса соотношегпшми: где сазО = сазО + опл.
Между ДПФ и ДПХ существует простая прямая связ!к Ке<Х(8» = (!.37) 1/птх(/г)/= ( ) (1.38) С другой стороны, по известным составлюошим Х(/г) ДПФ можно получить ДПХ Н(/г) = Кс1Х(/г)1-! П11Х(/г» (1.39) Симметричность форлтул прял/ого и обратного ДПХ, отсутствие комплексного представления данных и ряд других свойств ДПХ обеспечивают по сравнени/о с БПФ более высокую вычислительную эффективность при обработке вецтествснных данных, что особенно важно при двумерном анализе. 1.3.3.
Дискретное косинусное преобразование Одной из весьма сложных задач ЦОС является построение вплеокодсков для сжатия изображения с целью уменьшения скорости передачи, а потому и уменьшения спсктра, занимаемого видеосигналом. Рассмотрим существо проблемы па примере телевизионного сигнала. Применяемая система со строчна-перел/енной фазой РАБ (Р!!азе А1(егпа1е )лпе) для образования одного кадра черно-белого изображения использует 625 25 строк, а на каждой строке 625 элементов (пиксслов). Следовательно, для получения одного кадра изображения всего необходимо 380 625 пиксслов.
Для воспроизведения движения приемлемого качества и исключения эффекта лрожашего экрана требуется формировать около 50 кадров в секунду. Отсюда нетрулно рассчитать скорость передачи 380 625х50 = !9 031 250 пикселов/с. что соответствует полосе пропускания окало 20 МГц. Практически используется более узкая полоса около 6 МГц, что достигается, во-первых, сокрашением числа передаваемых строк до 575 и, во-вторых, распределением строк по двум кадрам: нечетные строки вывалятся в первом кадре, четные— гз рлава г. лгвтоды и алгорнпкы циФровой обработки сигналов длгоритыы к пРоцессоры цифровой обрабопск сигналов 22 во втором. При этом частота лискретизашьи составляет 12 МГц, Однако добиться изображения хорошего качества таким способом не удается.
С цветными изображениями дело обстоит еще сложнее. поскольку необходима дополнительная информация о цвете, яркости. а также применение помехозащитного кодирования. Поэтому скорость передачи в канале цвегного телевидения возрастает да 200 Мбит/с, что лля практических целей совершенно недопустима. Целью сжатия как раз и является снижение скорости передачи изображения без существенных, т. е. незаметных глазу, искажений. Все изображения делят на два обширных класса: статические (например, фотографии) и лпдвижные, которые имеют свои особенности. В связи с этим был разработан ряд чежлунаролных станллртов компрессии изображений: (3 стандарт )РЕС ()опп Р1заьалтар)ььс Ехреьтз Сгопр, Объединенная фотографическая экспертная группа) прелназначеьь лля сжатия статических (неподвижных) изображении; П стандарты Н.320 (и его часть Н.261), Н.263 предназначены лля сжатия полвпжных изображений в видеофонах и системах видеоконфсреььцььй; ь3 серия стандартов МРЕСл (Мат!пЗ Р!сцжез Ехрегы Сгоцр, Экспертная группа по движущимся изображениям; л — номер станларта) предназначен для сжатия подвижных изображений в более развитых системах, в частности, МРЕС4 в цифровых носителях палечтн, таких как СО-КОМ.
Все стандарты основаны на кпдирпвпнии нрепбрпзпвпниель, существа которого состоит в следующем. Цветное цли черно-белое изображение расщепляется на блоки из 64 = Зх8 пикселав. К каждому блоку применяется частотное нрепбрпзпвпнив. Таким частотным преобразованием могло бы служить ДПФ, олнако оно формирует мнимые коэффициенты, которые настолько усложняют вычисления, что искльочается воэможность прцмененпя ДПФ для целей сжатия изображений.
В указанных стандартах используется лругое, подобное ДПФ, преобразование — дискретнттпе кпсинугнпе нреппрпзпвпние ~ЯК)73, которое ильеет только вещественные частотна-зависильые коэффициенты. Смысл ДКП рассматривается ниже. На блоке из 64 пикселав формируется двумерный массив коэффициентов, которые переупорядачиваются и преобразуются в олномерный массив.
Полученные коэффьциьепты почвергаьотся дальнейшей статистической обработке, и соответствующие нм паральетры передаются по "аььалу связи. На приеме осущсстачяется восстановление изображения (синтез) путем обратного преобразования. Эта процедура обеспечивает существенное сокращение скорости передачи вплоть да 20 раз (коэффициент ~~иль постигает 20). Дискретное косинусное преобразование прелставляет сигнал рядом гармо- нических функций. Двумерное ттьс)т'ЛКП (2-ДКП) имеет вил: и-ьн-ь ты, ь- ~с<т>сь ьтт ь л г ]Ы+'ьт 1, )а 'О ], клц обратное двумерное ДКП (2-ОДКП) определяется по фарльуле: гле (1.42) Х(й) = ~ — С(й) )ь х(л)соз~ Г2 ! (2л + 1))ьл1 У (Е43) (!йт в о ~ 2)У ДКП !2' ь.>=1~тсьцтьть.к~ь'" ~~"].
ОДКП (! .44) Вилно, что все коэффициенты ДКП являются вещественными. Разлеление двумерного ДКП на одномерные приводит к существенному снижению количества умножений. действительно, можно показать, что для вьгчисления двумерного дКП блока размерности тух)у при разделении необхааильо 2тт'з умножений, в то время как непосредственное применение 2- ДКП требует )т' умножений. Например, прн стандартном расщеплении 4 изображения 256х256 на 1024 блока по Зх8 пикселов количество умножений снижается с !024х84 = 4 194 304 до 1024х2х8з = ! 048 576.
Из с казанного следует, что дискретное косннусное преобразование может обеспечить обработку изображений в реальном времени, если элементная база позволяет бьютро произволить умножение. Здесь х((, т) — яркость пиксела по координатам х и у соответственно; Х(lг, и) — коэффициенты 2-ДКП этого пиксела. Одним нз свойств 2-ДКП является его разделимость. Это означает, что дву- мерное ДКП блока размерности ттхтьь можно представить сьерез одномерные ДКП по строкам и столбцам этого блока.
Одномерные прямое и обратное ДКП задаются выражениями: х4 Замечание (х ) = ',У с„(2)тз„(х), к-О (1.48) н(егыт ~ — ц'А(егыт гз+ тз ! (1.45) где (1,46) з заь и1 Алгоритмы к лдацассоды цифровой обработки сигналов Основная информация об иэображении содержится в низкочастотной области и передается соответствующими коэффициентами ДКП Х(к); поэтому коэффициенты Х(к), отображающие высокочастотную область, оказываются нулевыми или блиэхиии к нулю. Применение ДКП к цветному иэображению позволяет снизить скорость передачи ло каналу связи с 200 Мбит!с до 34 Мбит!с, т.
е. коэффициент сжатия приблизительно равен 6. Сказанное позволяет сделать вывод. задачи цифрового спектрального анализа связаны с многократной обработкой комплексных чисел. больших массивов данных, пх особым упорядочиванием для обеспечения быстрых вычислений. 1.4. Нелинейная обработка В слелуюших разделах приводятся примеры широко используемых алгорит- мов нелинейной обработки. 1.4.1. Вычисление квадратного корня Одной из типичных практических задач ЦОС является многократное вычисление АЧХ фильтра с передаточной функцией гг(г) = 1/А(д) за достаточно короткий временной отрезок, что харалтерно для вокодсров с линейным предсказанием Гсл.
разд, 65). Для этого потребуется ца болыпом множестве частот (ю;) вычислять величину егыт' х) = йе~4(ек" )~ хЗ =1ш1г4(е )1 Если аппаратная !юализацня опсрашщ извлечения корня в процессорах отсутствует, ее воплощают программно. что требует нескольких десятков команлных циклов процессора. В задачах реального времени это может оказаться нелопустнмым, в связи с чем было прелложено аппроксимировать функцию Г;:=' кз+х цолиномом невысокого порядка Г, удобным лля программной реализации на языке ассемблера и отвечающим необходимой точности. Решение минимаксной задачи прнволит к полиному второго порядка Г = 0,828427(х, + х ) — 0.3431452х,хы (1.47) дающему погрешность 6 е (О; 0.17! 573), отлула е .„, = 1,636 дБ, что уловле- творяет требованиям, предъявляемым к системам обработки речи.
Глава Г. Методы и алгоритмы цифровой обработки сигналов 1.4.2. Вычисление функции соби Вычисление тригонометрических функций нетрулно организовать чсрсз вычисление сов(а). для чего чаще всего в палшти процессора фо!хцпруют таблицы. к которым обращаются в ходе вычислений. Когда создание таблиц затруднено илц нецелесообразно вследствие нелостаточпой точности нсобхолина организовывать специальную вычислительную процедуру, которая отвечала бы двум критериям: необходимой точности и минимуму команд. С этих позиций наилучшей оказкзась аппроксимация в виде отрезка ряда по полиномам Чебышева где х = ш/ Л; Л = л. т. е.
х е (О'„!). Исследования, выполненные по отношению к компрессии речи, показали, что прн допустимом отклонении частотной характеристики лостаточно иметь п1ах(и» = 3. В этом случае получаем соз(х) = 0.998568 — 4,888184гз + 3,819208хл — 0,930944хе. (1.49) 1.4.3. Вычисление полиномов Алгебраические и тригонометрические полнномы, используемые в цифро- вой обработке„могут быть представлены в алгебраическом виле простой за- меной переменных.
Поэтому алгоритм вычисления всякого гюлинома не- трудно свести к вычислени|о алгебраического полинома м у(х) = Я а,.х'. (1.50) ые Ясно, что вычисление полппома непосредственно по формуле (1.50) требует операций сложения и (М вЂ” !)Мг2 операций умножения, т. е. всего необходимо произвести (М+ 1)М/2 арифметических операций, что прц больших М, характерных для ЦОС, может стать критическим относительно обеспечения реального времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
