THE ACCELERATED METHOD OF CALCULATION LOGARITHMIC FUNCTION VALUES FOR THE TASK SOLUTION OF GENERATION CODE SETS

Full Text

Последние годы возрастает актуальность обеспечения защищенности информационного обмена в спутниковых радионавигационных системах (СРНС) между навигационными космическими аппаратами (НКА) и аппаратурой потребителей (АП). В качестве варианта решения указанной задачи в работе [2] приведена методика повышения структурной скрытности НС СРНС на основе стохастического использования различных уникальных систем квазиортогональных кодовых последовательностей с требуемыми характеристиками. В работе [3] предложен вариант получения необходимого количества систем квазиортогональных кодовых последовательностей на основе метода функциональных преобразований псевдослучайных аргументов. Реализация предложенного метода на практике включает в себя следующие основные этапы. 1. Формирование исходного ряда равномерно распределенных псевдослучайных чисел md. 2. Функциональное преобразование псевдослучайных чисел с помощью выбранной функции τ; = G^frndi). 3. Дискретизация полученных действительных значений функции τ,. с выбранным шагом d для получения натуральных значений длин серий элементов в формируемых двоичных кодовых последовательностях: t. =]τ./ί/[. 4. Получение двоичной последовательности, в которой tt определяет длину серии последовательно идущих элементов одного знака: И^_1+1 · ■ Л-ι«,· = Н)г К,1+1 ·-а^м, ) > где a'-aN -последовательность единичных элементов. На рис. 1 наглядно проиллюстрирована суть предложенного метода. Как было отмечено в [4], кодовые последовательности обладают оптимальными корреляционными характеристиками в том случае, когда серии элементов в них подчиняются закону ł-распределенности. Такое распределение серий элементов достигается в полной мере при использовании функции вида τ = 1оё2 "7 · md Рис. 1. Иллюстрация метода функциональных преобразований псевдослучайных аргументов При достаточно большом периоде генератора псевдослучайных чисел (ГПСЧ) можно получить большое число неповторяющихся кодовых последовательностей: при длине периода ГПСЧ равному N количество кодовых последовательностей, которое теоретически может быть получено при использовании единственного функционального преобразования, составит Q*2N/l, где/ - длина кодовых последовательностей в битах. Поскольку расчетное время эксплуатация НКА не превышает 15 лет, достаточно обеспечить защищенность НС на указанный период. Необходимое количество кодовых последовательностей для обеспечения защищенности НС в течение 15 лет составляет Ą = 2,3652-1012 [3]. При этом должно выполняться следующее неравенство: Q^Ar . Тогда при длине последовательностей / = 10230 бит N > 1,2098-1016 . ГПСЧ «Вихрь Мерсенна» имеет период N = (219937 -1)/32 « 1,3486-Ю6000 , который многократно превосходит значение Ą. и удовлетворяет приведенному неравенству. Поскольку вышесказанное доказывает, что при использовании ГПСЧ «Вихрь Мерсен-на» можно с помощью лишь одной функции получить необходимое количество последовательностей для защиты НС в течение 15 лет, то целесообразно использовать единственную функцию T = log2-, поскольку ґ- md „ она обеспечивает ł-распределенность серий элементов в получаемых кодовых последовательностях. При этом выбор начального бита ГПСЧ в качестве секрета позволит обеспечить высокую структурную скрытность кодовых последовательностей. Метод получения систем двоичных ква-зиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов предполагает вычисление значений функции с определенной точностью. Согласно стандарту IEEE 754-2008 [5] в подавляющем большинстве современных устройств числовые данные обрабатываются в формате представления чисел с плавающей точкой и имеют определенный класс точности: половинную, одинарную, двойную или расширенную. Особенности представления чисел с различной точностью представлены в таблице 1 (S - знак, E - показатель степени, I - целая часть, F - дробная часть). «Инфокоммуникационные технологии» Том 11, № 2, 2013 30 Жук А.П., Орел Д.В. Таблица 1. Особенности представления чисел с различной точностью Точность Половинная (half-precision) Одинарная (single-precision) Двойная (doubleprecision) Двойная расширенная (doubleextended precision) Характеристи ки Размер слова (байты) 2 4 8 10 Число десятичных знаков 3 7 15 19 Наименьшее значение 5,96-10-8 1,2-Ю38 2,3-Ю“308 3,4-ΙΟ-4932 Наибольшее значение 65504 3,4-1038 1,7-10308 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 бит дальномерного кода. Для формирования двоичных последовательностей на основе предложенного метода с такой скоростью с использованием стандартных классов точности представления чисел требуется выполнять порядка 104-108 операций в сек. В то же время известно [6], что бортовые ЭВМ НКА способны осуществлять до 2,1-106 операций в сек. Таким образом, в некоторых случаях всех имеющихся вычислительных ресурсов бортовой ЭВМ будет недостаточно для формирования кодовых последовательностей. Повышение производительности бортовой ЭВМ ограничивается допустимыми массогабаритными параметрами и максимальным возможным энергопотреблением. Учитывая, что бортовая ЭВМ НКА должна выполнять и другие задачи, помимо вычисления значений функции, актуальность приобретает задача снижения требуемых вычислительных ресурсов для вычисления значений функции до нижней границы диапазона - 104 операций в секунду. Целью статьи является снижение максимального необходимого числа операций при нахождении значений логарифмической функции для получения возможности реализации в СРНС метода формирования увеличенного количества систем квазиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов. Известно, что чаще всего вычисления производятся с двойной точностью [8], которая обеспечивает относительную точность в 15 десятичных символов. Так, например, функциональное преобразование x = log2- при rnd=0,21 с двойной md точностью составляет τ = 2,25153876 6995965. В то же время в методе [3] получения систем ква-зиортогональных кодовых последовательностей результат функционального преобразования τ при шаге дискретизации d = 1 округляется в большую сторону до ближайшего целого. Найденное значение будет преобразовано следующим образом: τ = 2,251538766995965 -> ί = 3. Тогда вычисление Т допустимо производить с меньшей точностью, отбрасывая всю дробную часть числа и увеличивая на единицу его целую часть. Как известно, в цифровой электронной вычислительной технике для вычисления значений различных функций применяются различные численные методы [9]. Численные методы позволяют вычислять приближенные значения функций: численным методом обычно решается некоторая другая, более простая задача, аппроксимирующая (приближающая) исходную задачу. В ряде случаев используемый численный метод строится на базе бесконечного процесса, который в пределе приводит к искомому решению. Примером этого может служить вычисление значений элементарной функции с помощью частичных сумм степенного ряда, в который разлагается эта функция. Однако реально предельный переход обычно не удается осуществить, и процесс, прерванный на некотором шаге, дает приближенное решение. Таким образом, осуществляется аппроксимация функции, позволяющая вычислить ее значение с необходимой точностью. Точность вычисления значения функции, как известно, определяется количеством слагаемых при разложении функции в ряд. Для приближения функций, у которых достаточно просто вычисляются старшие производные, широко используется ряд Тейлора. К таким функциям относится и натуральный логарифм. Ряд Тейлора для функции натурального логарифма имеет вид: + , „ . X їх2 2х3 6х3 1п(1 + х) =---+--- 1! 2! 3! 4! Их2 2!х3 --h - 2! (-1) (п-Х)\х” _х п\ ~ 1! (-1)"+1 (п-1)1хп 3! · + 3!х 4! ■ + + и! 2 3 X X = X--+ — 2 3 ----+ + (-1) и+1 . п =Σ л=0 нг* и + 1 И+1 ОО —Σ (-1) и+1 . л=1 (1) для всех X є (-1,1]. «Инфокоммуникационные технологии» Том 11, № 2, 2013 Жук А.П., Орел Д.В. 31 Если аргументом x функции и соответствующего ей функционального ряда является действительное число, то аргумент x и в функции, и в числовом ряде можно заменить произвольной функцией Q'(x) при единственном условии, что функция во всей области определения выражается действительным числом. Это положение основывается на принципе суперпозиции, а такой метод образования новых функций и их разложений в ряд называется композиционным [10]. Ограничение значения переменной х є (-1,1] можно записать иначе следующим образом: -1<л:<1. Тогда составной аргумент функции натурального логарифма должен находиться в интервале 0<1 + ;с<2. Поскольку значения аргумента md принимают значения 0 < md < 1, то область возможных значений md при замене аргумента функции полностью входит в область допустимых значений аргумента функции натурального логарифма (і + х). Используя формулы преобразований логарифмов, получим следующее: T = log 1 ln 1 rnd _ Hrnd~l) md - ln rnd ln 2 ln2 1 ln2 ln2 ln rnd. (2) Произведем замену аргумента rnd =1 + x . Выразим x: x = rnd — 1. Тогда выражение (2) будет выглядеть следующим образом: τ = —— ln md = —— ln(l + jc) = ln 2 ln2 = _j_ |,(-і)и+У = ln 2 n=i n = _J_ z(-l)n+l(md-l)n = ln 2 n=i n _£(-1)я+1(1 -md)" n=i и ln 2 Разложение логарифмической функции τ - log2 в ряд Тейлора имеет вид (3) md , 1 ™(-\)n+](\-rnd)n τ = log2 — = Σ-—-· rnd η=ι n m2 (4) При этом количество слагаемых ряда n определяется в зависимости от необходимой точности вычисления значения функции. Чем большая точность требуется, тем большее количество слагаемых ряда необходимо для вычисления значения функции. Согласно второму следствию из теоремы Лейбница остаток сходящегося знакочередующегося ряда Ra=S-Sn, где S = , S„ = f4bi, будет по модулю меньше первого отброшенного слагаемого: |^|<|έ„+1|. В свою очередь для нахождения суммы числового ряда с определенной точностью ε первое отбрасываемое слагаемое Ьп+1 должно быть по модулю меньше значения ε: |ε|>|6Β+1|. Это позволяет сделать заключение о том, что нахождение неполной суммы слагаемых числового П ряда Sn = Σ&,· без учета всех последующих сла-i=l гаемых начиная с Ьп+1 позволит вычислить значение функции с точностью ε. Поскольку первое отброшенное слагаемое равно (-1)"+1(1 -md) ^п+1 и+1 (5) (и + і)-1п2 ’ то для оценки минимального необходимого ко личества слагаемых необходимо решить следую щее неравенство: ε > (-1)"+1(1 -md) л+1 (6) (и + і)-1п2 то есть найти такое наибольшее п относительно минимального и максимального значений аргумента md , при котором неравенство (6) верно. Поскольку в неравенстве (6) значения обеих частей приведены по модулю, а значение точности всегда будет выражаться положительным числом, то знак последнего отбрасываемого члена можно не учитывать. Тогда: ε > (1 - rnd) и+1 (7) (и + l) 1п2 Поскольку In 2 - число, перенесем его в ле вую часть неравенства: ε ln 2 > (1 - rnd) и + 1 л+1 Как было упомянуто в [7], скорость сходимости ряда ô(x)=ln(l + x) меняется на его круге сходимости: при значениях x из центра круга сходимости ряд сходится быстро, в то время как при значениях x, близких к границам круга сходимости, ряд сходится медленнее. Для определения минимального необходимого числа слагаемых числового ряда необходимо решить неравенство (8) относительно п. Поскольку неизвестно способов выражения п из неравенства (8), решить его возможно аналитическим или графическим путем. Учитывая, что граничные значения не включаются в промежуток (0;1), а минимальная раз «Инфокоммуникационные технологии» Том 11, № 2, 2013 32 Жук А.П., Орел Д.В. ница между соседними псевдослучайными числами составляет 10-4 для формирования кодовых последовательностей длиной 10230 бит, то минимальное и максимальное значения аргумента будут соответственно равны rndmi„ =10^* и ™/ш = 0,9999 . Почленное вычитание логарифмических рядов позволяет переходить к другим видам функций и их разложений. Существует альтернативный способ представления аргумента логарифмической функции, при использовании которого, как отмечается в [11], минимально необходимое количество слагаемых для нахождения значения функции с заданной точностью при минимальном значении аргумента существенно меньше, чем при рассмотренном выше способе. С учетом свойства логарифмической функции ln = ln(l + x) - ln(l - х), 1-х (9) функция ln(l-x) может быть разложена в ряд Тейлора следующим образом: x2 2х3 6х4 (и — 1)! хи ~2!~~ 3! 4! и! x2 x3 x4 _ х" _~2~ п В свою очередь, функция 1п(1 + х) раскладывается в ряд Тейлора согласно выражению (1). 1 + x « Тогда разложение функции In-в ряд Тейлора примет вид: 1-х In 1 + х 1-х = X- 2 3 X X ---1— 2 3 = 2 x4 x2 хъ x4 ---Ь · · · + X H---1---1-- 4 2 3 4 f 3 5 7 XXX x л---1---1---y · ч 3 5 7 Л 1 + Г 00 хп ln—= 2 Σ—, и = 1;3;5;7 ... 1-JC n=l η (10) Представленный числовой ряд (10) имеет круг сходимости при x є (-1;1), тогда аргумент функ- П 1+* π ции лежит в пределах 0 <-< оо. В свою очередь, в этот диапазон полностью входит область допустимых значений аргумента функции , 1 τ = log2-- : 0 < md < 1. md Числовой ряд на основе функции In-, так 1-х же как и ряд на основе функции 1п(1+лс), будет иметь различную скорость сходимости на различных участках круга сходимости. Исследования [10] показывают, что в некоторых случаях использование такого разложения в ряд существенно сокращает количество слагаемых числового ряда, сумму которых необходимо найти для вычисления значения функции. 1 + л: Произведем замену аргумента: md = Тогда 1 1 1 + х τ =--ln md =--ln-= ln 2 ln 2 1-х 1 00 xn 2 00 xn = —— 2 Σ—= —— Σ—· ln 2 и=і n ln 2 d=i n 1-х (11) Неравенство | ε | > | bn+l | будет выглядеть следующим образом: \ε\ > й+1 1η2 η +1 (12) Значения x при различных rnd представлены в таблице 2. Таблица 2. Значения x при различных значениях rnd . rnd 0,9999 0,5 0,0001 X 9999 1 3 -0,3333 1 10001 -0,9998 19999 -0,00005 Поскольку обе части неравенства рассматриваются по модулю, то знак «-» в правой его части не влияет на результат, его можно опустить. По этой же причине можно опустить и знак аргумента x, поэтому допустимо использовать модуль x. В таблице 3 представлены результаты исследований числа слагаемых числового ряда, сумму которых необходимо найти для вычисления значения функции с обозначенной точностью. Как видно из таблицы 3, при первом способе представления аргумента в виде rnd = 1 + х максимальное число слагаемых требуется для нахождения значения функции при наименьшем возможном значении аргумента. Наоборот, при втором рассмотренном способе представления , 1 + х аргумента в виде та =- максимальное чис- 1-х ло слагаемых числового ряда требуется при на- «Инфокоммуникационные технологии» Том 11, № 2, 2013 Жук А.П., Орел Д.В. 33 хождении значения функции при максимальном значении аргумента. Таблица 3. Число слагаемых числового ряда для вычисления значения логарифмической функции с различной точностью τ = log2 Точ ность Тип замены аргумента Значение аргумента rnd КГ4 0,5 0,9999 10"15 md=1 + X 225 768 44 3 , 1 + л; md =- 1-х 3 29 119 523 10“3 rnd = 1 + X 1 270 7 1 . 1 + je md =- 1-х 1 5 1 953 1 rnd =1 + X 1 1 1 , Ι + χ md -- 1-х 1 1 1 При уменьшении точности уменьшается и число слагаемых числового ряда для вычисления функции. Использование второго способа разложения функции в ряд с представлением аргумента в виде md — --в большинстве случаев позволяет сократить минимальное необходимое число слагаемых для вычисления значения функции по сравнению с первым способом разложения функции в ряд при представлении аргумента в виде md = 1 + X . Для вычисления значения функции с точностью до единицы требуется найти всего одно слагаемое числового ряда при любом представлении аргумента. Таким образом, при практической реализации метода формирования систем квазиортого-нальных кодовых последовательностей на основе преобразования x = log2- требуется найти md первое слагаемое числового ряда Тейлора, которое является первой производной функции τ. На основе выражения: ,=юе ' -L ,13) rnd ln 2 η-ι η первое слагаемое ряда Тейлора будет иметь следующий вид: τ(1) = I-md ln 2 ' (14) Тогда вычисление значения функции с точностью до целого значения можно представить в следующем виде: rnd \-md ln 2 (15) Уменьшение минимального необходимого числа слагаемых числового ряда для вычисления значения функции приведет к снижению количества выполняемых арифметических операций и увеличению скорости вычисления этого значения. Выражение (15) представляет собой ускоренный метод вычисления значений функции x = log2-. Вычисление логарифма в (15) замеmd нено на элементарные операции вычитания, деления и округления до целого, поэтому оно может быть положено в основу работы блока вычисления значения функционального преобразования. Оценим повышение скорости вычисления AV значения функции с точностью до единицы относительно скорости вычисления значения функции с половинной точностью при формировании одной кодовой последовательности длиной 10230 бит. Для этого необходимо вычислить разность между числом арифметических операций, необходимых для вычисления значений функции при обоих классах точности при одном и том же значении аргумента: Щ =КЩ -Кеді, где AKt =КЩ -Keàj - разность между числом слагаемых числового ряда, необходимых для вычисления значения функции с половинной точностью (КПі ) и с точностью до единицы (Кедг ) при одинаковом значении аргумента. Необходимо вычислить такие разности для требуемого количества аргументов. Найдем повышение скорости вычисления с точностью до первого знака после запятой, в таком случае будет достаточно найти разности для 33 значений аргумента, равномерно распределенных по области определения: і = 33 . Тогда повышение скорости вычисления можно найти как среднее арифметическое между найденными разностями АКІ на основе следующей формулы: AV ■ ΣΔΚ, /=1 (16) Поскольку график зависимости числа слагаемых числового ряда от значения аргумента Θ при использовании класса половинной точности ε = 10_3 является нелинейным, то необходимо осуществить аппроксимацию зависимости Θ методом наименьших квадратов [9]. В таблице 4 приведены 33 опорные точки, представляющие собой число слагаемых числового ряда для вы- «Инфокоммуникационные технологии» Том 11, № 2, 2013 34 Жук А.П., Орел Д.В. числения значения функции при равномерно распределенных значениях аргумента на области определения с точностями ε = 10“3 и ε = 10 =1. Таблица 4. Число слагаемых для вычисления значения логарифмической функции с различной точностью для 33 значений аргумента Значение аргумента Точность Значение аргумента Точность Значение аргумента Точность СП о 1-Н - СП о - СП о т—н - Число слагаемых Число слагаемых Число слагаемых 0,0001 1270 1 0,3437 11 1 0,6875 4 1 0,0312 88 1 0,375 11 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, при точности ε = 10_3 число слагаемых ряда Тейлора постепенно уменьшается при увеличении значения аргумента. При точности ε = 1 число слагаемых ряда Тейлора, необходимое для вычисления значения функции, равно одному при любом значении аргумента. При одном слагаемом ряда Тейлора количество арифметических операций для формирования кодовой последовательности длиной 10230 элементов составляет порядка 104 операций в секунду. На основе опорных точек из таблицы 4 методом наименьших квадратов с помощью полинома 20 степени была построена аппроксимирующая функция Θ для класса половинной точности, ε = 10“3. Она представлена на рис. 3. Рис. 3. Опорные точки, характеризующие число слагаемых ряда Тейлора для вычисления значения функции τ и аппроксимированная функция Θ для точности ε = 10_3 Затем были выбраны 5263 точки, равномерно распределенные на интервале [0, 0001;0, 9999] с шагом 0,00019. Такое число аргументов близко к количеству серий элементов в кодовой последовательности длиной 10230 бит. Для выбранных аргументов были найдены значения К аппроксимирующей функции Θ . На основе найденных значений Кп по формуле (16) был вычислен коэффициент увеличения скорости вычислений значений функции с точностью до единицы относительно скорости вычисления значения функции с половинной точностью при формировании одной кодовой последовательности: AV = 23,95. Некоторые данные, показывающие увеличение скорости вычислений значений функции, приведены в таблице 4. Так, например, при значении аргумента md= 0,1562 число арифметических операций при понижении точности вычисления сократилось в 24 раза, поскольку количество слагаемых числового ряда, необходимых для вычисления значения функции, сократилось с 24 до 1. Выводы 1. При практической реализации метода получения систем квазиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов необходимо производить вычисления значений функции x = log2—-, обеспечивающей та ł-распределенность серий элементов в последовательностях, 2. Нахождение значений логарифмической функции T = log2—при помощи численного md метода разложения в ряд Тейлора при использовании стандартных классов точности представления двоичных чисел требуется выполнять порядка 104-108 операций в с, в то время как бортовые ЭВМ НКА способны осуществлять до 2,1 -106 операций в с. В связи с этим возникает необходимость снижения требуемого для вычисления значений функции количества арифметических операций до нижней границы диапазона 104 операций в с. 3. В используемом методе получения систем квазиортогональных кодовых последовательностей на основе функциональных преобразований псевдослучайных аргументов значения функции используются как длины серий элементов и округляются до целых значений, поэтому точность вычисления значений функции может быть уменьшена. 4. Вычисление значения функции T = log2- _ md с точностью до целого числа можно приблизить использованием всего одного слагаемого числового ряда Тейлора на всем интервале области определения функции и перейти к выражению, «Инфокоммуникационные технологии» Том 11, № 2, 2013 Жук А.П., Орел Д.В. 35 в котором производятся элементарные операции вычитания, деления и округления вверх. 5. Предложенный ускоренный численный метод вычисления значений логарифмической функции x = log2- позволяет сократить мита^ нимальное необходимое число арифметических операций для вычисления значений функции. Скорость вычисления повышается более чем в 23 раза по сравнению с вычислением значений функции с половинной точностью, а количество арифметических операций достаточно порядка 104 операций в с.

About the authors

A. I Zhuk

Email: alekszhuk@mail.ru

D. V Orel

Email: orel@otzi-ncfu.ru

References

Supplementary files