Варакин Л.Е. Теория систем сигналов (1978) (1151881), страница 58
Текст из файла (страница 58)
Вернемся к перестановкам. Обозначим через сгг то свойство пары перестановок ( выбранной и произвольной), которые имеют на одном месте один и тот же элемент а,. Число таких перестановок обозначим У(а,). Соответственно через У(аг) обозначим число перестановок, у которых остается на одном и том же месте элемент аг и т. д. Поскольку элементы (числа) в перестановках равноправны, то У (а,) = У (аг) и т.
д. Так как каждый элемент может быть выбран См = М способами в перестановке из М элементов, то общее число перестановок, имеющих на своих местах хотя бы по одной цифре, равно См У (а,) = СмУ,. Через агаг обозначим свойство перестановок, имеющих на одинаковых местах элементы сгг и сгг. Общее число перестановок, имеющих парные совпадения цифр, равно См У (гг,агг) = СмгУг и т. д. Продолжая подобные рассуждения н используя формулу (14.33), можно найти [132), что число перестановок, не имеющих совпадений с выбранной, равно Рм = Рм, а = У вЂ” СмУг + СмУг — СЬЧ, + ... + ( — 1)пса, (14. 34) где У = М!.
Определим Уп 1 = 1, М. Если в перестановке фиксируется один элемент, то остальные М вЂ” 1 элементы можно выбрать (М вЂ” 1)! способами. Поэтому У, = (М вЂ” 1)!. Если фиксируются два элемента, то остальные можно выбрать (М вЂ” 2)! способами и У, = (М вЂ” 2)!. В общем случае У1 — — (У вЂ” !)!. Подставляя эти значения Уг в (14.34) и раскрывая биномиальные коэффициенты, окончательно получаем выражение для субфакториала Рм=М! [! — — + — — +( — !) — ~. (!4.35) 1 ! м ! 1! 2! М! В табл.
14.3 приведены значения для субфакториала Рм. Таблица 14.3 10 1 2 3 4 5 0 ! 14833 ! 33496 1334961 2 9 44 1854 265 Например, для М = 4, Р4 — — 9, т. е. имеется 9 перестановок без совпадений. Для перестановки №8 из табл. 14.2 перестановки с номерами 1, 3, б, 15, 17, 18, 22, 23, 24 не имеют совпадений. 263 Перейдем к определению Рм. при т ) О. Число перестановок, у которых и элементов совпадают, а остальные М вЂ” т меняют свое положение, равно Рм, т = СмРм — а. (14.36) Действительно, сначала надо выбрать, какие и элементы остаются на месте. Это можно сделать См способами.
Остальные М вЂ” т элементов можно переставлять любыми способами, лишь бы не было совпадений. Это можно сделатьРм способами. Используя правило произведения, получаем (14.36). Соотношения (14.35) и (14.36) позволяют рассчитать субфакториалыдля любых М и т. Таблицы Рм, приведены в П32]. Для субфакториалов известно рекуррентное со- отношение Рм=МРм !+ ( — 1)м, (! 4.37) которое позволяет найти любое Рм. Формулы (14.32), (14.35)— (14.37) позволяют найти вероятность т совпадений. При больших М выражение в квадратных скобах (14.35) стремится к е ', что позволяет аппроксимировать распределение вероятностей (14.32) законом Пуассона со средним значением, равным единице П32): Рм (т) 1 ет1 (14.38) Формула (14.38) получается при замене субфакториалаРм, в (14.32) согласно (14.35), (14.36).
Из (14.38) следует, что при М )) 1 вероятность Рм(т) практически не зависит от М. Наиболее вероятны случаи, когда т = 0 (совпадений нет) и т = 1 (одно совпадение). Их вероятности примерно равны е ' 0,368. В табл. 14.4 приведены значения вероятностей Рм (т) для М = 5 и М = 9, рассчитанные по точным формулам (14.32), (14.36) и таблицам, приведенным в (1321. Та блица 14.4 1 2 0,366 0,368 0,37Ь 0,167 0,368 0,184 0,083 0,061 О, 0083 0,003 б 10 0 0,016 !О-а 3 1О-а Сравнение данных табл. 14.4 сзаконом (14.38) позволяет использовать этот закон для приближенных расчетов.
Распределение Р, (т) при М = 5 (табл. 14.4) незначительно отличается от распределения (14.38), а распределение Ра (т) при М = 9 практически не отличается от (14.38), Поскольку наиболее вероятными согласно (14.38) являются или т = О, или т = 1, то модуль ВКФ (14.10) наиболее вероятно будет равен или 0 или 17М.
Среднее значение 264 числа совпадений, распределенного по закону Пуассона (!4.38), равно 1. Поэтому среднее значение модуля ВКФ (14.10) будет равно /с = ш, (!/«/» (!) ! ) = 1/М. (!4.39) Вероятность появления л« = 0 или т = 1 равна 0,736, вероятность появления и ( 2 равна 0,92, а вероятность появления т ( ( 4 равна 0,981. Отметим, что эти вероятности согласно (!4.38) не зависят от М. И поэтому при М )) ! уровни ВКФ (14.10) должны быть малыми.
Распределение числа совпадений в апериодических корреляционных функциях. Если полезный и мешающий сигналы перекрываются частично, то в этом случае на выходе согласованного фильтра будет 1Р иметь место апериодическая ВКФ. На рис. 14.2 изображено совместное л расположение двух частично перекрывающихся ДЧ сигналов первого порядка: сигнал А (левая штриховка) опережает сигнал В (правая штриховка) на два элемента. Перекрытие сигналов возможно только в прямоугольнике АВ, выделенном толстой линией. При перекрытии сигналов А 0 т в и В, изображенном на рис. 14.2, имеет Рис.
14.2 место одно совпадение (квадрат с совпадающими штриховками). Распространим задачу «о встречах» на случай смещения во времени одного сигнала относительно другого. Будем рассматривать временной сдвиг, кратный длительности элемента Ы, т. е. положим т = пИ, где а — целое число, удовлетворяющее условию ! и ! = О,М, где М вЂ” число элементов в ДЧ сигнале. При п = 0 имеем случай периодической ВКФ, при ! и ! = М сигналы не перекрываются.
Так как и полностью характеризует временной сдвиг, то в дальнейшем будем оперировать только с и. Задачу «о встречах» при произвольном сдвиге п можно свести к предыдущей при п = О. Если сдвиг равен п, то ширина прямоугольника перекрытия сигналов (прямоугольник АВ на рис. !4.2) равна М вЂ” и. Число различных ДЧ сигналов, размещающихся на прямоугольнике перекрытия без совпадающих частот, будет меньше определяемого формулой (14.31). Определим это число. На первой временной позиции элемент может быть выбран М способами, на второй — (М вЂ” 1) способами, ...., на М вЂ” п позиции — (и + 1) способами. В итоге число ДЧ сигналов с числом элементов (М вЂ” а) равно И, = М (М вЂ” 1) ... (а + 1) = — . и! Число пар та!«их сигналов равно (М!/и!)».
(! 4.40) 265 Выберем произвольный ДЧ сигнал с числом элементов М вЂ” и и числом частотных позиций М и рассмотрим число его совпадений с другими подобными ДЧ сигналами. Обозначим через Рм „число сигналов, имеющих т совпадений с выбранным. Отметим, что выбор исходного сигнала, совпадения которого рассматриваются, не имеет значения, так как с комбннаторной (вероятностной) точки зрения все сигналы равноправны. Так как число выборов исходного сигнала равно Ь|„(14.40), то число пар сигналов, имеющих т совпадений, равно Рм „ /.|„. Вероятность т совпадений равна относительному числу пар с т совпадениями, т. е.
/!л~~м л! л л! ~~М л! л Рм л(т)— !л (14.41) М! (М вЂ” !)! Рм,ю,л= —— С л+ ьч л! + См~ „— ° +( — 1) л См л (14 42) л! *! Формула (!4А2) была получена О. В. Матвеевой. 266 Формула (14.41) получается непосредственно, если число сигналов Рм „с т совпадениями с исходным сигналом разделить на число сигналов /.!„(14.40). Для определения числа Рм „используем принцип включения и исключения 1132], символическая запись которого определяется формулой (14.33). Обозначим через а, то свойство двух перекрывающихся сигналов, что элемент а, у них совпадает. Соответственно через /!/ (а,) обозначим число сигналов, имеющих совпадающий элемент аы Точно так же /!/ (а,) — число сигналов, имеющих совпадающий элемент ав и т.
д. Так как элементы в перестановках равноправны, то /!/ (а,) = /!/ (ав) = ... = й/,. Каждый элемент может быть выбран См „= М вЂ” и способами. Поэтому общее число сигналов, имеющих хотя бы одно совпадение, равно См ., й/,. Число й/, определяется следующим образом. Так как рассматривается одно совпадение, то зафиксируем этот элемент.
Остальные М вЂ” и — 1 элементы можно выбрать (М вЂ” 1) (М вЂ” 2) ... (и + 1) = (М вЂ” 1)!/и! способами. Следовательно, /)/, = (М вЂ” 1) ! / и!. Обозначим через а,ав то свойство двух сигналов, что они имеют два совпадающих элемента а„ав. Общее число сигналов, имеющих двойные совпадения, равно СЪ „/!/ (а,ав) =См,Ув. Фиксируя два элемента и осуществляя перестановки остальных М вЂ” и — 2 элементов, получаем й/в = (М вЂ” 2)! /и!. Продолжая рассматривать тройные совпадения и т. д.
методом математической индукции с применением формулы (14.33), находим число сигналов, не имеющих совпадений с исходныме): Преобразуя, получаем см а Сма Рм,а,а= — 1 "+ " +( 1) " ° (14.43) При п = О правые части формулу (14.42), (14.43) совпадают с определением субфакториала (14.35). Определим Рм, „при числе совпадений гп ) О. Допустим, что два сигнала имеют т совпадений. Элементы, которые совпадают, можно выбрать См, способами. Остальные М вЂ” и! — п элементов не должны иметь совпадений.
Их число равно Рм, „. Следовательно, число сигналов, имеющих т совпадений, равно Рм,, = См Рм- (14.44) где Рм, а определяется согласно (14.43). Расчет вероятностей л! совпадений следует производить согласно формулам (14.41) — (14.44). В табл. 14.5 приведены результаты расчета этих вероятностей при произвольном сдвиге п для М = 5, а в табл. 14.6 для М = 9. Та б ли ца 14.5 0 0,0083 0,0083 0,366 0,442 0,533 0,65 0,8 0,375 0,367 0,350 0,30 0,2 0,167 0,150 0,100 0,05 0,083 0,033 0,017 Таблица !4.6 0 3.10 3 10 5.10-а 10-а 2.ГО а 2,10-а 7,7 1Π— 8 5,5 1О 1,7 10-8 267 0 1 2 4 5 7 8 0,368 0,408 0,456 0,505 О, 564 О,'630 0,708 0,790 0,889 0,368 0,367 0,362 0,356 0,341 0,300 0,256 0,196 0,111 О, 184 О, 164 О, 140 0,115 0,085 0,062 0,0 35 0,014 О, 061 0,048 0,035 0,024 0,0!4 0,007 0,001 О, 015 0,010 0,006 0,003 0,001 310 а 0,003 0,002 8 10-а 3 1Π— а 7.10-6 Считая, что сдвиг и может равновероятно принимать любое значение от — (М вЂ” 1) до (М вЂ” 1), определим среднюю по сдвигам вероятность совпадений следующим образом: М вЂ” ! Рм(т) =(2М вЂ” 1) г ~~', Рм „(т).
л = — (М-1) Так как совокупность всех сдвигов и совпадений составляет полную группу событий, имеем м ~ч~ Рм(т) =1. (14.46) В табл. 14.7 приведены средние вероятности совпадений для М=бнМ=9. Таблица 14.7 в ) г ( в 5 ОО,585 0,020 0,002 9.10-в 0,019 0,003 5 1О-в 0,312 0,085 0,290 0,083 3 1О 6,8 !0-1 9.!О-е 1,6 10-г Прн этом вероятность совпадений (14.41) с учетом (14.44) будет приближенно равна См — е 1 ~м-е Р, „!ги) м " = м " Рм (т), (14.48) См м1 е СД где Рм(т) определяется согласно (14,38).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
