Ускоренный метод вычисления значений логарифмической функции для решения задачи формирования систем кодовых последовательностей

Последние годы возрастает актуальность обеспечения защищенности информационного обмена в спутниковых радионавигационных системах (СРНС)меж-ду навигационными космическими аппаратами (НКА) и аппаратурой потребителей (АП).В качестве варианта решения указанной задачи в работе [2]приведена методика повышения структурной скрытности НС СРНС на основе стохастического использования различных уникальных систем квазиортогональных кодовых последовательностей с требуемыми характеристиками.В работе [3]предложен вариант получения необходимого количества систем квазиортогональных кодовых последовательностей на основе метода функциональных преобразований псевдослучайных аргументов.Реали-зация предложенного метода на практике включает в себя следующие основные этапы.

• 1.    Формирование исходного ряда равномерно распределенных псевдослучайных чисел .

• 2.    Функциональное преобразование псевдослучайных чисел с помощью выбранной функции т_г = G~\rnd^.

• 3.    Дискретизация полученных действительных значений функции т,- с выбранным шагом d для получения натуральных значений длин серий элементов в формируемых двоичных кодовых последователь-ностях:'/4M-

• 4.    Получение двоичной последовательности, в которой t, определяет длину серии последовательно идущих элементов одного знака: ”/,_, ₊i • • • X_{x +ti} =(-!)' (а,_{и +1}... а,_{н +ti} ), где Of-.C^ – последовательность единичных элементов.

На рис. 1 наглядно проиллюстрирована суть предложенного метода. Как было отмечено в [4], кодовые последовательности обладают оптимальными корреляционными характеристиками в том случае,когда серии элементов в них подчиняются закону k -распределенности. Такое распределение серий элементов достигается в полной мере при использовании функции вида

, 1

• ^T = o§2 —7 ■

rnd

Рис. 1. Иллюстрация метода функциональных преобразований псевдослучайных аргументов

При достаточно большом периоде генератора псевдослучайных чисел (ГПСЧ) можно получить большое число неповторяющихся кодовых последовательностей: при длине периода ГПСЧ равному N количество кодовых последовательностей, которое теоретически может быть получено при использовании единственного функционального преобразования, составит Q « IN/l, где / – длина кодовых последовательностей в битах. Поскольку расчетное время эксплуатация НКА не превышает 15 лет, достаточно обеспечить защищенность НС на указанный период.Необ- ходимое количество кодовых последовательностей для обеспечения защищенности НС в течение 15 лет составляет 4 =2,3652-IO12 [3]. При этом должно выполняться следующее неравенство: Q ^ dr . Тогда при длине последовательностей / = 10230 бит .

ГПСЧ «Вихрь Мерсенна» имеет период N = (219937 -1)/32 « 1,3486- IO6000 , который многократно превосходит значение Лг и удовлетворяет приведенному неравенству. Поскольку вышесказанное доказывает, что при использовании ГПСЧ «Вихрь Мерсенна» можно с помощью лишь одной функции получить необходимое количество последовательностей для защиты НС в течение 15

лет, то целесообразно использовать един-ф ственную функцию т = log2---, поскольку она обеспечивает k-распределенность серий элементов в получаемых кодовых последова-тельностях.При этом выбор начального бита ГПСЧ в качестве секрета позволит обеспечить высокую структурную скрытность кодовых последовательностей.

Метод получения систем двоичных ква-зиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов предполагает вычисление значений функции с определенной точностью. Согласно стандарту IEEE 754-2008 [5] в подавляющем большинстве современных устройств числовые данные обрабатываются в формате представления чисел с плавающей точкой и имеют определенный класс точности: половинную, одинарную, двойную или расши-ренную.Особенности представления чисел с различной точностью представлены в таблице 1 (S – знак, E – показатель степени, I – целая часть, F – дробная часть).

Таблица 1. Особенности представления чисел с различной точностью

Точность	К Ед к 3 2 о ^ о —	к .2 ° .2	о 'Н ‘Ед )К Ct о «	ct^g 'S .2 ^   3 о д й х р « к О ^ о я CQ и r^C ct
Характеристики
Размер слова (байты)	2	4	8	10
Число десятичных знаков	3	7	15	19
Наименьшее значение	5,9610-8	1,2-10"38	2,3-10"308	3,4-10"4932
Наибольшее значение	65504	3,4-1038	1,7-Ю308	1,1-ю4932
Поля	S-E-F	S-E-F	S-E-F	S-E-I-F
Размеры полей, бит	1-5-10	1-8-23	1-11-52	1-15-1-63

Поскольку частота трансляции некоторых НС достигает 10,23 МГц,каждую секунду требуется формирование до 10 230 000 бит дальномерного кода. Для формирования двоичных последовательностей на основе предложенного метода с такой скоростью с использованием стандартных классов точности представления чисел требуется выполнять порядка 10 ⁴ -10 ⁸ операций в сек. В то же время известно [6], что бортовые ЭВМ НКА способны осуществлять до 2,1-10 операций в сек.Таким образом,в некоторых случаях всех имеющихся вычислительных ресурсов бортовой ЭВМ будет недостаточно для формирования кодовых последовательностей. Повышение производительности бортовой ЭВМ ограничивается допустимыми массогабаритными параметрами и максимальным возможным энергопотреблением. Учитывая, что бортовая ЭВМ НКА должна выполнять и другие задачи, помимо вычисления значений функции, актуальность приобретает задача снижения требуемых вычислительных ресурсов для вычисления значений функции до нижней границы диапазона - 10⁴ операций в секунду.

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

Известно, что чаще всего вычисления производятся с двойной точностью [8], которая обеспечивает относительную точность в 15 десятичных символов.Так, например,функциональное преоб- разование т = 1о§2 —; при rnd = 0,21 с двойной ~ rnd точностью составляет                        .

В то же время в методе [3] получения систем ква-зиортогональных кодовых последовательностей результат функционального преобразования т при шаге дискретизации d = 1 округляется в большую сторону до ближайшего целого. Найденное значение будет преобразовано следующим образом: г = 2,251538766995965 ^1=3.

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

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

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

,        . х 1х'2х

1п(1 + х) =---+--

1!     2!3!

6х³ "аГ

2!

(-1)"+10?-1)!т

п\              1!

(-1)"+| (и-1)!х”

п\

(-1)"+|х” _

п

1!х2 2!х3 З!х3

2!

3!       4!

з X

2    3

_^(-1)"+|х

п

для всех.

Если аргументом x функции и соответствующего ей функционального ряда является действительное число, то аргумент x и в функции, и в числовом ряде можно заменить произвольной функцией QXx) при единственном условии, что функция во всей области определения выражается действительным числом. Это положение основывается на принципе суперпозиции, а такой метод образования новых функций и их разложений в ряд называется композиционным [10].

Ограничение значения переменной x e (-1,1] можно записать иначе следующим образом: -1 < x < 1. Тогда составной аргумент функции натурального логарифма должен находиться в интервале 0rnd принимают значения 0 < rnd< 1, то область возможных значений rnd при замене аргумента функции полностью входит в область допустимых значений аргумента функции натурального логарифма (1 + x).

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

Т = 1„8,2- = ^2И^=1*^

" rnd In 2 In 2

- In rnd 1 ,,

--------=--In rnd.

In 2In 2

Произведем замену аргумента rnd = 1 + x . Выразим x: x = rnd - 1. Тогда выражение (2) будет выглядеть следующим образом:

t =—— In гис/ =—— ln(l + x) = ln2ln2

In 2 _n=i n

_1_ ^(-|]^tW-1£_

In 2 »=i n

_ ^-W⁺4\-rndy

,7=i n In 2

Разложение логарифмической функции т = log,--- в ряд Тейлора имеет вид

~ rnd

т = 1ое ■ ^(-1Г«     (4)

rnd 7?=1 и In 2

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

Согласно второму следствию из теоремы Лейбница остаток сходящегося знакочередующегося ряда Rn =s-s„,гдеs-i^, s^t^,будет по модулю меньше первого отброшенного слагаемого: N

Поскольку первое отброшенное слагаемое равно

_<-\T\\-rndy^+A "^ti" (,? + l).ln2

то для оценки минимального необходимого количества слагаемых необходимо решить следующее неравенство:

Is!

(-i)24i^z^22L

(и + 1)-1п2

то есть найти такое наибольшее n относительно минимального и максимального значений аргумента rnd , при котором неравенство (6) верно.

Поскольку в неравенстве (6) значения обеих частей приведены по модулю, а значение точности всегда будет выражаться положительным числом, то знак последнего отбрасываемого члена можно не учитывать. Тогда:

y-rndy^+x (;? + l) In 2

Поскольку In 2 – число, перенесем его в левую часть неравенства:

8 In 2 >

(1 - rndy^+x 77 + 1

Как было упомянуто в [7], скорость сходимости ряда Q^ = ln( 1 + x) меняется на его круге сходимости: при значениях x из центра круга сходимости ряд сходится быстро, в то время как при значениях x, близких к границам круга сходимости, ряд сходится медленнее. Для определения минимального необходимого числа слагаемых числового ряда необходимо решить неравенство (8) относительно n. Поскольку неизвестно способов выражения n из неравенства (8), решить его возможно аналитическим или графическим путем.

Учитывая, что граничные значения не включаются в промежуток (0;1), а минимальная раз- ница между соседними псевдослучайными числами составляет 10-4 для формирования кодовых последовательностей длиной 10230 бит, то минимальное и максимальное значения аргумента будут соответственно равны mdтт = 10 и md™ = 0,9999 .

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

Числовой ряд на основе функции In—так 1 - X же как и ряд на основе функции ln(l + x), будет иметь различную скорость сходимости на различных участках круга сходимости. Исследования [10] показывают, что в некоторых случаях использование такого разложения в ряд существенно сокращает количество слагаемых числового ряда, сумму которых необходимо найти для вычисления значения функции.

l + x

Произведем замену аргумента:

Тогда                                     1 X

1		1 ,	l + x
T =--	In md =	--In	i------=
In 2		In 2	1-x
1	x"	2	” Xй
			z—.
~~ln2	„=1 n	~”ln2	„=1 n

Неравенство H>IM будет выглядеть следующим образом:

функция ln(l — x) может быть разложена в ряд Тейлора следующим образом:

n\ x"

и

В свою очередь, функция ln(l + X ) раскладывается в ряд Тейлора согласно выражению (1).

1H- X            v

Тогда разложение функции In—- в ряд Тейлора

1-x примет вид:

1 + X       03

In—= 2 Z—, n = l;3;5;7 ...

1 —X      „=1 77

Представленный числовой ряд (10) имеет круг сходимости при x e (—1;1), тогда аргумент функ-

_                 „ 1 + X      _ ции лежит в пределах 0 <---< co . В свою оче редь, в этот диапазон полностью входит область допустимых значений аргумента функции

, 1

т = log,----: 0 < nid< 1 . " md

2	x и+1
In 2	n + 1

Значения x при различных md представлены в таблице 2.

Таблица 2. Значения x при различных значениях md .

md	0,9999	0,5	0,0001
X	9999 10001 -0,9998	3 -0,3333	1 19999 -0,00005

Поскольку обе части неравенства рассматриваются по модулю, то знак «–» в правой его части не влияет на результат, его можно опустить. По этой же причине можно опустить и знак аргумента x, поэтому допустимо использовать модуль x.

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

Как видно из таблицы 3, при первом способе представления аргумента в виде md=1 + x максимальное число слагаемых требуется для нахождения значения функции при наименьшем возможном значении аргумента. Наоборот, при втором рассмотренном способе представления

, l + x аргумента в виде md =--- максимальное чис-

1-x ло слагаемых числового ряда требуется при на-

Таблица 3. Число слагаемых числового ряда для вычисления значения логарифмической функции с различной точностью

1    43 У н м к Тип замены аргумента Значение аргумента rnd IO"4 0,5 0,9999 IO"15 rnd = 1 + x 225 768 44 3 , 1 + x rnd =--- 1-x 3 29 119 523 IO"3 rnd = 1 + x 1 270 7 1 , 1 + x rnd =--- 1-x 1 5 1 953 1 rnd = 1 + x 1 1 1 , 1 +x rnd =--- 1-x 1 1 1 хождении значения функции при максимальном значении аргумента.

т = log₂ —- = rnd

1 - rnd

In 2

При уменьшении точности уменьшается и число слагаемых числового ряда для вычисления функции. Использование второго способа разложения функциив ряд спредставлением аргумента - 1+А" - D                О в виде          в большинстве случаев позво ляет сократить минимальное необходимое число слагаемых для вычисления значения функции по сравнению с первым способом разложения фун- кции в ряд при представлении аргумента в виде rnd = 1 + х . Для вычисления значения функции с точностью до единицы требуется найти всего одно слагаемое числового ряда при любом представлении аргумента.

Таким образом, при практической реализации метода формирования систем квазиортого-нальных кодовых последовательностей на основе преобразования т = log2 —- требуется найти * rnd первое слагаемое числового ряда Тейлора, которое является первой производной функции т . На основе выражения:

,     1    1   »(-1Г+1(1-г^)"

T = log2 —= — Z----------- (13)

rnd In 2 »=1 п первое слагаемое ряда Тейлора будет иметь следующий вид:

\-rnd т =------

In 2

Тогда вычисление значения функции с точностью до целого значения можно представить в следующем виде:

Уменьшение минимального необходимого числа слагаемых числового ряда для вычисления значения функции приведет к снижению количества выполняемых арифметических операций и увеличению скорости вычисления этого значения. Выражение (15) представляет собой ускоренный метод вычисления значений функции т = log2 —Ц . Вычисление логарифма в (15) заме' rnd нено на элементарные операции вычитания, деления и округления до целого, поэтому оно может быть положено в основу работы блока вычисления значения функционального преобразования.

Оценим повышение скорости вычисления AK значения функции с точностью до единицы относительно скорости вычисления значения функции с половинной точностью при формировании одной кодовой последовательности длиной 10230 бит. Для этого необходимо вычислить разность между числом арифметических операций, необходимых для вычисления значений функции при обоих классах точности при одном и том же значении аргумента: ^^K,,-^, где NK.=K_n-K_edi – разность между числом слагаемых числового ряда, необходимых для вычисления значения функции с половинной точностью ( ^H; ) и с точностью до единицы ( ^ed- ) при одинаковом значении аргумента. Необходимо вычислить такие разности для требуемого количества аргументов. Найдем повышение скорости вычисления с точностью до первого знака после запятой, в таком случае будет достаточно найти разности для 33 значений аргумента, равномерно распределенных по области определения: / = 33 . Тогда повышение скорости вычисления можно найти как среднее арифметическое между найденными разностями NK; на основе следующей формулы:

AK = I^.           (16)

i

Поскольку график зависимости числа слагаемых числового ряда от значения аргумента 0 при использовании класса половинной точности 8 = 10~3 является нелинейным, то необходимо осуществить аппроксимацию зависимости 0 методом наименьших квадратов [9]. В таблице 4 приведены 33 опорные точки, представляющие собой число слагаемых числового ряда для вы- числения значения функции при равномерно распределенных значениях аргумента на области определения с точностями 8 = 10 и 8 = 10° =1 .

Таблица 4. Число слагаемых для вычисления значения логарифмической функции с различной точностью для 33 значений аргумента

а. СО к в ЕГ >о СО U ЕЕ ГО	Точность		03 сО К ЕЕ S 2 о S У >> СО U ЕЕ ГО	Точность		СЕ со О н 5 s ЕЕ >т СО U ЕЕ ГО	Точность
	о	’—1		о	’—1		о	’—1
	Число слагаемых			Число слагаемых			Число слагаемых
0,0001	1270	1	0,3437	и	1	0,6875	4	1
0,0312	88	1	0,375	и	1	0,7187	4	1
0,0625	52	1	0,4062	9	1	0,75	4	1
0,0937	37	1	0,4375	8	1	0,7812	3	1
0,125	29	1	0,4687	8	1	0,8125	3	1
0,1562	24	1	0,5	7	1	0,8437	3	1
0,1875	20	1	0,5312	7	1	0,875	3	1
0,2187	17	1	0,5625	6	1	0,9062	2	1
0,25	15	1	0,5937	6	1	0,9375	2	1
0,2812	14	1	0,625	5	1	0,9687	1	1
0,3125	12	1	0,6562	5	1	0,9999	1	1

Как видно из таблицы 4, при точности 8 = 10“³ число слагаемых ряда Тейлора постепенно уменьшается при увеличении значения аргумента. При точности 8 = 1 число слагаемых ряда Тейлора, необходимое для вычисления значения функции, равно одному при любом значении аргумента. При одном слагаемом ряда Тейлора количество арифметических операций для формирования кодовой последовательности длиной 10230 элементов составляет порядка 10⁴операций в секунду.

На основе опорных точек из таблицы 4 методом наименьших квадратов с помощью полинома 20 степени была построена аппроксимирующая функция 0 для класса половинной точности, .

Рис.3.Опорныеточки,характеризующиечисло слагаемых ряда Тейлора для вычисления значения функции ти аппроксимированная функция 0 для точности 8 = 10“3

Затембыливыбраны5263точки,равномернорас-пределенные на интервале [0,0001;0,9999] с шагом 0,00019.Такое число аргументов близко к количес- тву серий элементов в кодовой последовательности длиной 10230 бит.Для выбранных аргументов были найдены значения Кп аппроксимирующей функции 0 . На основе найденных значений Кп по формуле (16) был вычислен коэффициент увеличения скорости вычислений значений функции с точностью до единицы относительно скорости вычисления значения функции с половинной точностью при формировании одной кодовой последовательности: ДГ = 23,95. Некоторые данные, показывающие увеличение скорости вычислений значений функции, приведены в таблице 4. Так,например, при значении аргумента /W=0,1562 число арифметических операций при понижении точности вычисления сократилось в 24 раза, поскольку количество слагаемых числового ряда,необходимых для вычисления значения функции,сократилось с 24 до 1.

Выводы

• 1.    При практической реализации метода получения систем квазиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов необходимо производить вычисления значений функции T = log₂—обеспечивающей та

• 2.    Нахождение значений логарифмической ,           ¹

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

• 4.    Вычислениезначенияфункции т = log₂ —-с точностью до целого числа можно приблизить использованием всего одного слагаемого числового ряда Тейлора на всем интервале области определения функции и перейти к выражению,

• 5.    Предложенный ускоренный численный метод вычисления значений логарифмической функции т = log₂ -Ц позволяет сократить ми' rnd

k-распределенность серий элементов в последовательностях,

функции           при помощи численного

' md метода разложения в ряд Тейлора при использовании стандартных классов точности представления двоичных чисел требуется выполнять порядка 104-108 операций в с, в то время как бортовые ЭВМ НКА способны осуществлять до 2,1-106 операций в с. В связи с этим возникает необходимость снижения требуемого для вычисления значений функции количества арифметических операций до нижней границы диапазона 104 операций в с.

в котором производятся элементарные операции вычитания, деления и округления вверх.

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