3.7. Последовательности максимальной вероятности

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

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

В результате с ростом N АКФ случайной последовательности стремится к идеальной в виде дельта-функции.

Известно также, что сигналы, у которых АКФ обладают малыми боковыми пиками, содержат оптимальное число блоков

Блок — последовательность символов одного знака. Формула (3.81) справедлива для нечетных Для четных или Доказано, что (3.81) является средним значением числа блоков в последовательности из символов. Так как распределение числа блоков описывается биномиальным законом, то (3.81) является также и наиболее вероятным значением числа блоков. Блоки могут быть единичными (состоят из одного символа), двойными (состоят из двух символов) и т. д. Обозначим число блоков одинаковой длины через причем длина блока равна числу символов в нем. Например, число единичных блоков. Для последовательности длины состоящей из М блоков, имеют место два равенства:

где длина максимального блока.

Считая постоянной величиной, усредняя обе части равенства (3.83), обозначая среднее значение через получаем

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

Если последовательность имеет блоков, то

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

Подставляя (3.81) в (3.87), получаем (3.85). Здесь следует отметить одну математическую особенность полученных результатов. Если подставить (3.86) в точное равенство имеет место

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

В табл. 3.17 приведены значения вероятностей появления блоков различной длины в случайных двоичных последовательностях, полученных из десятичных случайных последовательностей. Были взяты выборки из 800 символов.

Таблица 3.1.7. Вероятности появления блоков длины к

Как следует из данных табл. 3.17, эмпирические значения вероятностей, полученные для последовательностей конечной длины, близки к теоретическим значениям (3.85).

Таким образом, в типичной или «средней» случайной последовательности число символов должно удовлетворять равенству (3.82), общее число блоков — равенству (3.81), а число блоков длины равенству (3.86). Число таких последовательностей определяется полиномиальным законом

где аргумент характеризует блоковую структуру последовательности. Например, при имеем При этом число последовательностей, удовлетворяющих (3.85), составляет, примерно, 1/80 часть от общего числа последовательностей длины

Для типичной последовательности, удовлетворяющей равенствам (3.81) — (3.83), можно постулировать следующее утверждение: статистические характеристики их АКФ и ВКФ будут лучше, чем статистические характеристики полного кода, поскольку типичные последовательности являются наиболее вероятным представителем случайной последовательности с хорошими корреляционными свойствами. Именно на этом постулате и основаны последовательности максимальной вероятности.

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

где длина блока, для которого и из Минимальные значения 6 для равны 0 и 1.

Таким образом, единичные блоки должны составлять примерно половину от общего числа блоков, двойные — четвертую часть, тройные — восьмую часть и т. д. При этом блоки чередуются в порядке уменьшения их вероятностей. На первом шаге из блоков выбирается один из наиболее вероятных блоков, т. е. единичный блок, начальная вероятность которого согласно (3.85) равна 0,5. После этого остается блоков и вероятности появления оставшихся блоков изменяются. Для единичных блоков она станет меньше и будет

а для других блоков возрастет и станет

второй индекс означает номер шага формирования последовательности.

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

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

Для полного определения ПМВ необходимо найти значение Поскольку ПМВ, кроме равенств (3.81), (3.89), должны удовлетворять равенству (3.82), то длина максимального блока должна дополнять сумму до значения Например, если то при этом блока длиной быть не может, а должен быть блок длиною т. е. Следовательно,

Число ПМВ определяется числом вариантов чередования блоков разной длины при совпадении их вероятностей и числом таких совпадений. Так, при совпадении вероятностей различных блоков количество вариантов их чередования равно Q. Следовательно,, общее число последовательностей L можно определить по формуле

где число различных длин блоков, число различных длин блоков таких, для которых число различных длин блоков таких, для которых и т. д.

Для случая или для формула (3.93) может быть представлена в виде

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

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

В табл. 3.18 приведены 48 последовательностей максимальной вероятности в виде записи длин блоков для

Таблица 3.18. Последовательности максимальной вероятности с

Для ПМВ табл. 3.18 были рассчитаны АКФ и определены статистические характеристики модулей боковых пиков. В табл. 3.19 приведены статистические характеристики . В этой же таблице приведены характеристики М-последовательностей и случайных последовательностей. В табл. 3.19 приведены границы модуля максимального бокового пика среднее и среднеквадратичное значения.

Как следует из табл. обладают статистическими характеристиками, близкими к характеристикам наилучших последовательностей, а именно М-последовательностей. В то же время

Таблица 3.19. (см. скан) Статистические характеристики АКФ ПМВ

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