14.2. Комбинаторный анализ систем дискретных частотных сигналов

Дискретные частотные сигналы произвольного порядка. Хотя основной материал данной главы посвящен ДЧ сигналам первого порядка, но сначала для общности кратко рассмотрим ДЧ сигналы порядка К и найдем объем подкласса ДЧ сигналов, частотные элементы которых расположены на различных частотах. Напомним (см. § 1.6), что ДЧ сигналы порядка К состоят из временных элементов, каждый из которых состоит из К частотных элементов. Число частот равно Необходимым условием того, что совпадений не будет, является то, что кратно т. е. К делит Более того, должно удовлетворяться равенство

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

Используя определение (8.3), можно непосредственно показать, что

Подставляя (14.21) в (14.20), получаем

Найдем отношение объема исследуемого подкласса к объему класса ДЧ сигналов порядка Из (8.5), (14.22) с учетом (14.19) имеем

При отношение поскольку такие сигналы имеют всего лишь один временной элемент, т. е. являются частотными. В случае ДЧ сигналов первого порядка из (14.22) имеем

а отношение (14.23) имеет следующий вид:

В табл. 14.1 приведены значения отношения (14.25) при различных

Таблица 14.1 (см. скан)

Как следует из табл. 14.1, доля ДЧ сигналов без совпадений элементов резко уменьшается с ростом Чтобы выяснить закон уменьшения , обратимся к асимптотической формуле Стерлинга для факториала

Подставляя (14.26) в (14.23) и преобразуя, находим

Если то, используя предел при , получаем

Из (14.28) следует, что уменьшение определяется в основном экспонентой Из (14.28) для имеем

Если К соизмеримо с то использовать указанный ранее предел нельзя. Но экспоненциальный характер уменьшения сохраняется до относительно больших Например, при из (14.27) находим

т. е. отношение (14.30) изменяется в основном как

Таким образом, при большом подкласс ДЧ сигналов порядка К без совпадений элементов составляет малую долю от всего класса. Если нет регулярного метода, то выбор такого подкласса может быть сопряжен с большими вычислительными трудностями.

Формулы (14.20), (14.24) позволяют найти объем подкласса ДЧ сигналов порядка К, не имеющих на своей частотно-временной плоскости совпадений по частоте. Именно такие сигналы будем рассматривать в данном параграфе. Перейдем к определению числа совпадений элементов ДЧ сигналов при их взаимодействии, т. е. когда на полезный сигнал накладывается мешающий. При этом будем рассматривать ДЧ сигналы первого порядка.

Распределение числа совпадений в периодических корреляционных функциях. Число совпадений элементов в ДЧ сигналах первого порядка согласно (14.10) определяет ВКФ таких сигналов в дискретных точках. Найдем распределение вероятностей появления совпадений. Сначала рассмотрим случай, когда два ДЧ сигнала (полезный и мешающий) полностью перекрываются по времени. При этом число совпадений может изменяться от 0 до Полное перекрытие двух сигналов возможно, когда между полезным и мешающим сигналом нет временного сдвига или когда каждый из сигналов излучается непрерывно (периодически). При этом на выходе согласованного фильтра будем иметь периодическую ВКФ. Перейдем к распределению числа совпадений.

Число ДЧ сигналов первого порядка без совпадающих частот определяется формулой (14.24). Поскольку амплитудная и фазовая манипуляции не влияют на число совпадений в (14.10), то положим, что в (14.24) основание манипуляции При таком предположении число ДЧ сигналов первого порядка без совпадений элементов по частоте согласно (14.6) равно

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

Каждому ДЧ сигналу первого порядка без совпадений элементов по частоте может быть сопоставлена перестановка цифр

соответствующая частотной кодовой последовательности. Например, для все перестановки приведены в табл. 14.2.

Таблица 14.2 (см. скан)

Перестановка соответствует тому, что первый элемент расположен на второй частотной позиции, второй — на первой, третий — на четвертой и четвертый — на третьей.

Произвольная пара перестановок может иметь совпадений, причем Определим число пар перестановок, имеющих заданное число совпадений. Эта задача сводится к комбинаторной задаче встречах» [132]. Решить ее можно следующим образом. Выберем произвольную перестановку из общего числа, например, перестановку № 8 из табл. 14.2 или какую-либо другую. Все выборы равноправны. Обозначим через число перестановок, имеющих совпадений с выбранной. Так как число различных выборок исходной перестановки равно то число пар перестановок, имеющих совпадений, будет равно Относительное число пар перестановок с совпадениями или вероятность совпадений равна

Число называется субфакториалом [132], так как доказано, что оно имеет много свойств аналогичных свойствам факториалов. Чтобы определить используем комбинаторный принцип включения и исключения [132]. Он заключается в следующем. Пусть имеется объектов, из них обладают свойством а. Тогда число объектов, не обладающих свойством а, равно Если рассматриваются два свойства то число объектов, не обладающих ни одним из этих свойств, равно

Общее правило включения и исключения тех или иных дается следующей символической формулой [132]:

Смысл символической формулы (14.33) состоит в том, что сначала вычисляется содержание квадратных скобок, а затем знак функции

применяется к каждому из полученных слагаемых подобно тому, как это сделано в следующем примере: где Вернемся к перестановкам. Обозначим через то свойство пары перестановок выбранной и произвольной), которые имеют на одном месте один и тот же элемент Число таких перестановок обозначим Соответственно через обозначим число перестановок, у которых остается на одном и том же месте элемент Поскольку элементы (числа) в перестановках равноправны, то Так как каждый элемент может быть выбран способами в перестановке из элементов, то общее число перестановок, имеющих на своих местах хотя бы по одной цифре, равно Через обозначим свойство перестановок, имеющих на одинаковых местах элементы Общее число перестановок, имеющих парные совпадения цифр, равно См Продолжая подобные рассуждения и используя формулу (14.33), можно найти [132], что число перестановок, не имеющих совпадений с выбранной, равно

где Определим Если в перестановке фиксируется один элемент, то остальные элементы можно выбрать способами. Поэтому Если фиксируются два элемента, то остальные можно выбрать способами и В общем случае Подставляя эти значения в (14.34) и раскрывая биномиальные коэффициенты, окончательно получаем выражение для субфакториала

В табл. 14.3 приведены значения для субфакториала

Таблица 14.3 (см. скан)

Например, для т. е. имеется 9 перестановок без совпадений. Для перестановки № 8 из табл. 14.2 перестановки с номерами 1, 3, 6, 15, 17, 18, 22, 23, 24 не имеют совпадений.

Перейдем к определению при Число перестановок, у которых элементов совпадают, а остальные меняют свое положение, равно

Действительно, сначала надо выбрать, какие элементы остаются на месте. Это можно сделать способами. Остальные элементов можно переставлять любыми способами, лишь бы не было совпадений. Это можно сделать способами. Используя правило произведения, получаем (14.36). Соотношения (14.35) и (14.36) позволяют рассчитать субфакториалы для любых Таблицы приведены в [132]. Для субфакториалов известно рекуррентное соотношение

которое позволяет найти любое Формулы (14.32), (14.35) — (14.37) позволяют найти вероятность совпадений.

При больших выражение в квадратных скобах (14.35) стремится к что позволяет аппроксимировать распределение вероятностей (14.32) законом Пуассона со средним значением, равным единице [132]:

Формула (14.38) получается при замене субфакториал в (14.32) согласно (14.35), (14.36). Из (14.38) следует, что при вероятность практически не зависит от Наиболее вероятны случаи, когда (совпадений нет) и (одно совпадение). Их вероятности примерно равны . В табл. 14.4 приведены значения вероятностей для рассчитанные по точным формулам (14.32), (14.36) и таблицам, приведенным в [132].

Таблица 14.4 (см. скан)

Сравнение данных табл. 14.4 с законом (14.38) позволяет использовать этот закон для приближенных расчетов. Распределение при (табл. 14.4) незначительно отличается от распределения (14.38), а распределение при практически не отличается от (14.38). Поскольку наиболее вероятными согласно (14.38) являются или или то модуль ВКФ (14.10) наиболее вероятно будет равен или 0 или Среднее значение

числа совпадений, распределенного по закону Пуассона (14.38), равно 1. Поэтому среднее значение модуля ВКФ (14.10) будет равно

Вероятность появления или равна 0,736, вероятность появления равна 0,92, а вероятность появления равна 0,981. Отметим, что эти вероятности согласно (14.38) не зависят от М. И поэтому при уровни ВКФ (14.10) должны быть малыми.

Распределение числа совпадений в апериодических корреляционных функциях. Если полезный и мешающий сигналы перекрываются частично, то в этом случае на выходе согласованного фильтра будет иметь место апериодическая ВКФ. На рис. 14.2 изображено совместное расположение двух частично перекрывающихся ДЧ сигналов первого порядка: сигнал А (левая штриховка) опережает сигнал В (правая штриховка) на два элемента. Перекрытие сигналов возможно только в прямоугольнике выделенном толстой линией. При перекрытии сигналов изображенном на рис. 14.2, имеет место одно совпадение (квадрат с совпадающими иховками).

Рис. 14.2

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

Задачу встречах» при произвольном сдвиге можно свести к предыдущей при Если сдвиг равен , то ширина прямоугольника перекрытия сигналов (прямоугольник на рис. 14.2) равна Число различных ДЧ сигналов, размещающихся на прямоугольнике перекрытия без совпадающих частот, будет меньше определяемого формулой (14.31). Определим это число. На первой временной позиции элемент может быть выбран способами, на второй способами на позиции — способами. В итоге число ДЧ сигналов с числом элементов равно

Число пар тарих сигналов равно

Выберем произвольный ДЧ сигнал с числом элементов и числом частотных поеиций и рассмотрим число его совпадений с другими подобными ДЧ сигналами. Обозначим через число сигналов, имеющих совпадений с выбранным. Отметим, что выбор исходного сигнала, совпадения которого рассматриваются, не имеет значения, так как с комбинаторной (вероятностной) точки зрения все сигналы равноправны. Так как число выборов исходного сигнала равно то число пар сигналов, имеющих совпадений, равно Вероятность совпадений равна относительному числу пар с совпадениями, т. е.

Формула (14.41) получается непосредственно, если число сигналов совпадениями с исходным сигналом разделить на число сигналов

Для определения числа используем принцип включения и исключения [132], символическая запись которого определяется формулой (14.33). Обозначим через то свойство двух перекрывающихся сигналов, что элемент них совпадает. Соответственно через обозначим число сигналов, имеющих совпадающий элемент Точно так же -число сигналов, имеющих совпадающий элемент Так как элементы в перестановках равноправны, то Каждый элемент может быть выбран способами. Поэтому общее число сигналов, имеющих хотя бы одно совпадение, равно Число определяется следующим образом. Так как рассматривается одно совпадение, то зафиксируем этот элемент. Остальные элементы можно выбрать способами. Следовательно,

Обозначим через то свойство двух сигналов, что они имеют два совпадающих элемента Общее число сигналов, имеющих двойные совпадения, равно Фиксируя два элемента и осуществляя перестановки остальных элементов, получаем

Продолжая рассматривать тройные совпадения и т. д. методом математической индукции с применением формулы (14.33), находим число сигналов, не имеющих совпадений с исходным:

Преобразуя, получаем

При правые части формулу (14.42), (14.43) совпадают с определением субфакториала (14.35). Определим при числе совпадений Допустим, что два сигнала имеют совпадений. Элементы, которые совпадают, можно выбрать способами. Остальные элементов не должны иметь совпадений. Их число равно Следовательно, число сигналов, имеющих совпадений, равно

где определяется согласно (14.43).

Расчет вероятностей совпадений следует производить согласно формулам табл. 14.5 приведены результаты расчета этих вероятностей при произвольном сдвиге для а в табл. 14.6 для

Таблица 14.5 (см. скан)

Таблица 14.6 (см. скан)

Считая, что сдвиг может равновероятно принимать любое значение от до определим среднюю по сдвигам вероятность совпадений следующим образом:

Так как совокупность всех сдвигов и совпадений составляет полную группу событий, имеем

В табл. 14.7 приведены средние вероятности совпадений для

Таблица 14.7 (см. скан)

На рис. 14.3 сплошными линиями изображены огибающие, построенные по значениям вероятностей табл. 14.7. Штриховой линией показана огибающая закона (14.38).

Если сдвиг небольшой то для справедлива следующая приближенная формула:

При этом вероятность совпадений (14.41) с учетом (14.44) будет приближенно равна

где определяется согласно (14.38). Более точное приближение для больших обеспечивает следующая формула для вероятности совпадений:

Но формула (14.49) будет справедлива лишь при

Вероятность появления оптимальной пары сигналов. Оптимальной парой ДЧ сигналов назовем такую, сигналы которой имеют не

более одного совпадения при произвольном сдвиге Обозначим вероятность появления такой пары через Для ее определения обратимся к вероятности совпадения и составим таблицу этих вероятностей при всех . Для эти вероятности представлены в табл. 14.8.

При вероятность что было учтено при составлении табл. 14.8. Конкретные значения приведены в табл. 14.5.

Рис. 14.3

Пара сигналов будет оптимальной, если при любом число совпадений равно 0 или 1. Используя правила сложения и умножения вероятностей [104], получаем, что при М = 5 в соответствии с табл. 14.8 вероятность появления оптимальной пары сигналов равна

Суммы в квадратных скобках равны вероятностям появления 0, 1 при заданном сдвиге При выводе (14.50) было допущено, что совпадения при различных сдвигах независимы друг от друга. Поэтому равна произведению сумм вероятностей при Так как вероятности совпадений при равны вероятностям при то под знаком произведения стоят квадраты сумм вероятностей. Подставляя значения вероятностей из

Таблица 14.8 (см. скан)

табл. 14.5 в (14.50), получаем, что вероятность появления оптимальной пары сигналов при равна

При произвольном из формулы (14.50) получаем

Вероятность случайного выбора оптимальной ДЧ системы сигналов. Выберем случайным образом ДЧ систему с объемом Найдем вероятность того, что в выбранной системе все пары сигналов будут оптимальными, т. е. имеется не более одного совпадения. Такую систему назовем оптимальной системой.

В системе из сигналов имеется пар. Из них пар приходится на тождественно одинаковые сигналы, а из оставшихся надо рассматривать только половину. Поэтому необходимо иметь

оптимальных пар. Поскольку вероятность появления случайной пары равна то вероятность случайного выбора оптимальной системы равна

где определяется формулой (14.52). В табл. 14.9 приведены результаты расчета для

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

Таблица 14.9 (см. скан)