Инструменты пользователя

Инструменты сайта


examination:mszki:question44

Тестирование криптографических алгоритмов на основе спектрального анализа.

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

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

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

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

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

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

Задача спектрального оценивания подразумевает оценивание некоторой функции частоты. О характеристиках спектральной оценки судят по тому, насколько хорошо она согласуется с известным спектром тест-сигнала в некоторой непрерывной области частот.

Спектральная оценка, получаемая по конечной записи данных, характеризует некоторое предположение относительно той истинной спектральной функции, которая была бы получена, если бы в нашем распоряжении имелась запись данных бесконечной длины. Именно поэтому поведение и характеристики спектральных оценок должны описываться с помощью статистических терминов. Общепринятыми статистическими критериями качества оценки являются ее смещение и дисперсия. Аналитическое определение этих величин обычно наталкивается на определенные математические трудности, поэтому на практике просто совмещают графики нескольких реализаций спектральной оценки и визуально определяют смещение и дисперсию как функции частоты. Те области совмещенных графиков спектральных оценок, где экспериментально определенное значение дисперсии велико, будут свидетельствовать о том, что спектральные особенности, видимые в спектре отдельной реализации, не могут считаться статистически значимыми. С другой стороны, особенности совмещенных спектров в тех областях, где эта дисперсия мала, с большой достоверностью могут быть соотнесены с действительными частотными составляющими анализируемого сигнала. Однако в случае коротких записей данных часто не удается получить несколько спектральных оценок, да и сам статистический анализ отдельных спектральных оценок, полученных по коротким записям данных, в общем, случае представляет собой весьма трудную проблему.

Оценки спектральных меодов, основанные на прямом преобразовании данных и последующем усреднении, получили название периодограмм. Оценки СПМ, для получения которых по исходным данным сначала формируется корреляционные оценки, получили название коррелограммных методов спектрального оценивания.

При использовании любого метода оценивания спектральных методов пользователю приходится принимать множество компромиссных решений, с тем, чтобы по конечному количеству отсчетов данных получать статистически устойчивые спектральные оценки с максимально возможным разрешением. К этим компромиссным решениям относятся, в частности, выбор таких функций окна для взвешивания данных и корреляционных функций и таких параметров усреднения во временной и в частотной областях, которые позволяют сбалансировать требования к снижению уровня боковых лепестков, выполнению эффективного усреднения по ансамблю и к обеспечению приемлемого спектрального разрешения. Устойчивые результаты (малые спектральные флюктуации) и хорошая точность (малое смещение относительно истинных спектральных значений на всех частотах) достижимы только тогда, когда произведение TB, где Т - полный интервал записи данных, а B - эффективное разрешение по частоте, значительно превышает единицу. Все эти компромиссы можно количественно охарактеризовать в случае гауссовских процессов, для которых подробно теоретически изучены статистические характеристики классических спектральных оценок. Однако выбор конкретного метода спектрального оценивания в случае негауссовских процессов зачастую обосновывается только экспериментальными данными. Да и выбор функции окна очень часто основывается на данных экспериментальных, а не теоретических исследований.

Классические спектральные оценки тест-последовательности

Для того, чтобы охарактеризовать поведение каждой спектральной оценки при анализекороткой последовательности данных было предложено использовать искусственносинтезированную последовательность данных с заранее известными свойствами. Эта тест-последовательность данных содержит 64 отсчета некоторого комплекснозначногопроцесса, состоящего из 4-х комплексных синусоид и комплексного аддитивногоокрашенного шума. Частоты двух синусоид выбраны очень близкими друг к другу(0,2 и 0,21) с тем, чтобыпроверить разрешающую способность той или иной спектральной оценки. Мощность двух более слабых синусоид с частотами 0,1 и –0,15 на 20 дб меньше мощности двух более сильных. Эти слабые синусоиды используются для испытания способности спектральных оценок обеспечить обнаружение слабых компонент сигналов на фоне сильных сигналов.

Окрашенный шумовой процесс был сформирован пропусканием двух независимых белых шумов через идентичные фильтры с частотными характеристиками типа приподнятой косинусоиды для раздельного получения действительной и мнимой составляющих шумового процесса в тест-последовательности. Высота линий, характеризующих синусоидальные составляющие, выбрана так, чтобы отображать мощность каждой синусоиды относительно мощности окрашенного шума. Следовательно, мощность каждой из сильных синусоид превышает мощность шума, а мощность каждой из 2-х слабых синусоид меньше мощности шума.

Коррелограммные оценки СПМ тест-последовательности показаны на рис.1.18а,б для 16 и 32 значений автокорреляции соответственно и взвешивания окном Хэмминга. Графики на рис. 1. дают полное представление о взаимосвязи между разрешением и гладкостью оценки.

Рис. 1. Коррелограммные оценки СПМ для 64-точечной тест-последовательности: а – 16 значений автокорреляции, окно Хэмминга; б – 32 значения автокорреляции, окно Хэмминга

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

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

examination/mszki/question44.txt · Последние изменения: 2014/01/15 08:20 (внешнее изменение)