Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»

Получено выражение для определения минимально возможной длины последовательностей со свойством «не более одного совпадения». Эта оценка использована для проведения сравнительного анализа эффективности известных регулярных методов построения синтезированных последовательностей. Показана высокая эффек...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Неврев, А.И., Галчёнков, О.Н.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України 2016
Назва видання:	Технология и конструирование в электронной аппаратуре
Теми:	Системы передачи и обработки сигналов
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/115679
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения» / А.И. Неврев, О.Н. Галчёнков // Технология и конструирование в электронной аппаратуре. — 2016. — № 2-3. — С. 33-36. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-115679
record_format	dspace
spelling	irk-123456789-1156792017-04-10T03:02:25Z Эффективность методов синтеза последовательностей со свойством «не более одного совпадения» Неврев, А.И. Галчёнков, О.Н. Системы передачи и обработки сигналов Получено выражение для определения минимально возможной длины последовательностей со свойством «не более одного совпадения». Эта оценка использована для проведения сравнительного анализа эффективности известных регулярных методов построения синтезированных последовательностей. Показана высокая эффективность методов построения, основанных на теории расширенных полей Галуа. Отримано вираз для визначення мінімально можливої довжини послідовностей з властивістю «не більше одного збігу». Цю оцінку використано для проведення порівняльного аналізу ефективності відомих регулярних методів побудови синтезованих послідовностей. Показано високу ефективність методів побудови, заснованих на теорії розширених полів Галуа. The author presents an expression for determining the minimum possible length of binary sequences with "not more than one coincidence" property. Obtained low bound length value allows quantitatively estimating efficiency of any known synthesis methods for creation of binary sequences with "not more than one coincidence" property. The efficiency of known methods of creating binary sequences based on extended Galois fields theory is analyzed by comparing the obtained sequences length with a theoretical low bound estimation. The paper shows high performance of the known methods of creation of sequences with "not more than one coincidence" property based on extended Galois fields. 2016 Article Эффективность методов синтеза последовательностей со свойством «не более одного совпадения» / А.И. Неврев, О.Н. Галчёнков // Технология и конструирование в электронной аппаратуре. — 2016. — № 2-3. — С. 33-36. — Бібліогр.: 8 назв. — рос. 2225-5818 DOI: 10.15222/TKEA2016.2-3.33 http://dspace.nbuv.gov.ua/handle/123456789/115679 612.391.15 ru Технология и конструирование в электронной аппаратуре Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системы передачи и обработки сигналов Системы передачи и обработки сигналов
spellingShingle	Системы передачи и обработки сигналов Системы передачи и обработки сигналов Неврев, А.И. Галчёнков, О.Н. Эффективность методов синтеза последовательностей со свойством «не более одного совпадения» Технология и конструирование в электронной аппаратуре
description	Получено выражение для определения минимально возможной длины последовательностей со свойством «не более одного совпадения». Эта оценка использована для проведения сравнительного анализа эффективности известных регулярных методов построения синтезированных последовательностей. Показана высокая эффективность методов построения, основанных на теории расширенных полей Галуа.
format	Article
author	Неврев, А.И. Галчёнков, О.Н.
author_facet	Неврев, А.И. Галчёнков, О.Н.
author_sort	Неврев, А.И.
title	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
title_short	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
title_full	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
title_fullStr	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
title_full_unstemmed	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
title_sort	эффективность методов синтеза последовательностей со свойством «не более одного совпадения»
publisher	Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
publishDate	2016
topic_facet	Системы передачи и обработки сигналов
url	http://dspace.nbuv.gov.ua/handle/123456789/115679
citation_txt	Эффективность методов синтеза последовательностей со свойством «не более одного совпадения» / А.И. Неврев, О.Н. Галчёнков // Технология и конструирование в электронной аппаратуре. — 2016. — № 2-3. — С. 33-36. — Бібліогр.: 8 назв. — рос.
series	Технология и конструирование в электронной аппаратуре
work_keys_str_mv	AT nevrevai éffektivnostʹmetodovsintezaposledovatelʹnostejsosvojstvomneboleeodnogosovpadeniâ AT galčënkovon éffektivnostʹmetodovsintezaposledovatelʹnostejsosvojstvomneboleeodnogosovpadeniâ
first_indexed	2025-07-08T09:12:50Z
last_indexed	2025-07-08T09:12:50Z
_version_	1837069471721717760
fulltext	Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2016, ¹ 2–3 33 ÑèÑòåìû ïåðåäàЧè è îáðàáîòêè Ñèãíàëîâ ISSN 2225-5818 ÓÄÊ 612.391.15 К. т. н. А. И. Неврев, к. т. н. О. Н. ГАлчёНКОв Украина, Одесский национальный политехнический университет E-mail: a.i.nevrev@gmail.com ЭФФЕКТИВНОСТЬ МЕТОДОВ СИНТЕЗА ПОСЛЕДОВАТЕЛЬНОСТЕЙ СО СВОЙСТВОМ «НЕ БОЛЕЕ ОДНОГО СОВПАДЕНИЯ» Двоичные импульсные сигналы на базе по- следовательностей или множеств со свойством «не более одного совпадения» (ìîÑ) нахо- дят широкое применение в радиолокационных системах при формировании сложных сигна- ëîâ [1—3], â ðàдèîíàâèãàцèîííыõ ñèñòåмàõ, àñèíõðîííыõ àдðåñíыõ ñèñòåмàõ ñâÿзè [4], волоконно-оптических сетях и системах связи [5]. В [2, 3] òàêèå ïîñëåдîâàòåëьíîñòè ïðåдëî- жено использовать в системах связи и переда- чи информации в качестве кодов, обнаружива- ющих и исправляющих ошибки. Последовательности со свойством «не более одного совпадения» начинаются и заканчива- ются единичным импульсом и состоят из набо- ра импульсов единичной и нулевой амплитуды, размещенных таким образом, что боковые ле- пестки функции автокорреляции не превыша- ют единицу. Получение сигналов с максималь- ной энергетикой требует минимально возмож- ной длины последовательности N для заданно- го веса M, которым называют число единичных импульсов последовательности. Существует ряд регулярных методов построе- ния МОС, основанных на методах целочисленно- ãî ïðîãðàммèðîâàíèÿ, ðàзíîñòíыõ мíîжåñòâ [1], òåîðèè ïîëåé Гàëóà [1, 6, 7]. Изâåñòíыå мåòîды построения характеризуются различной вычисли- тельной эффективностью и различными резуль- татами — длиной получаемых последовательно- стей. Ясно, однако, что чем меньше длина после- довательности, тем более эффективным будет ее применение для решения поставленных задач. В [1, 6—8] ïðåдëîжåíы ðåãóëÿðíыå мåòîды синтеза МОС с произвольным весом M над рас- ширенными полями Галуа и приведены постро- Получено выражение для определения минимально возможной длины последовательностей со свой- ством «не более одного совпадения». Эта оценка использована для проведения сравнительного ана- лиза эффективности известных регулярных методов построения синтезированных последователь- ностей. Показана высокая эффективность методов построения, основанных на теории расширен- ных полей Галуа. Ключевые слова: последовательность, «не более одного совпадения», регулярные методы построе- ния, нижняя граница длины последовательности, эффективность метода. енные последовательности вплоть до М = 1000. Что касается численной оценки эффективности разработанных методов, то этот вопрос остает- ся неисследованным. Целью настоящей работы является оценка эффективности как известных методов синтеза МОС, так и любых вновь разрабатываемых, пу- тем определения теоретически минимально воз- можной длины последовательности Nmin для за- данного веса М и сравнения с ней значений ре- альной длины синтезированных последователь- ностей. МОС полностью определяется множеством номеров единичных позиций di, i = 0, …, M – 1. В соответствии с подходом к анализу МОС, ïðåдëîжåííîмó â [4], зàïèшåм âñå ïîñëåдîâà- тельные разности единичных позиций в виде треугольной матрицы 1 0 2 0 1 0 2 1 1 1 1 1 2 0 ... 0 0 ... , . . . . . . . . . . . 0 0 0 ... M M M M d d d d d d d d d d D d d             (1) ненулевые элементы которой определяются че- рез элементы первой наддиагонали: dj,l =dl – dj= 1 1 1 , 1 0 0 l j l j k k k k k k d d d            ; j<l; j, l = 0, 1, …, M – 1. (2) Длина МОС минимальна, когда ненулевые элементы матрицы D образуют ряд натураль- ных чисел: dj,l ∈[1, 2, ..., 0,5M(M – 1)]. (3) DOI: 10.15222/TKEA2016.2-3.33 Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2016, ¹ 2–3 34 ÑèÑòåìû ïåðåäàЧè è îáðàáîòêè Ñèãíàëîâ ISSN 2225-5818 Если Su — сумма элементов u-й наддиагона- ли, то сумма элементов k наддиагоналей равна 1 1 1 1( 1) 1 ( 1) . 2 2 2 k u u S Mk k k Mk k k                  . (4) C óчåòîм óñëîâèÿ (3) ïðàâàÿ чàñòь âыðàжå- ния (4) представляет собой оценку снизу для суммы элементов k наддиагоналей. С другой стороны, если учесть, что сумма S1 первой наддиагонали матрицы (1) равна длине последовательности N, то величину Su можно выразить через N следующим образом: 1 , 1 1, 0 ( 1)( ). u u i i M i M i i S uN u i d d            . Очевидно, что сумма элементов u-й надди- агонали максимальна, если наименьшие числа первых u – 1 íàддèàãîíàëåé ðàñïîëîжåíы ïî их краям, то есть выполняется условие di, i+1+dM–i–1,M–i > 4i – 1, i = 1, …, u – 1, и тогда 1 0 2 3 2 ( 1)(4 1) 1 ( 1) 2 ( 1) 2 2 ( 3 ). 3 u u i S uN u i i uN u u u u u u u                   В этом случае оценка сверху для суммы эле- ментов k наддиагоналей матрицы D принимает вид 1 1 2( 1) ( 1)( 1) 2 3 1 ( 1)( 1)( 2). 6 k u u S k k N k k k k k k k             (5) Из сопоставления верхней оценки (5) с ниж- ней (4) получаем оценку снизу длины МОС:      н 1 11 1 1 2 2 1 1 1 1 . 3 MN Mk k k k k k                      (6) Правая часть неравенства (6) зависит от пере- менной k, определенной на отрезке [1, M –1], îò которой можно избавиться при поиске экстрему- ма правой части выражения (6). Окончательно нижнюю оценку длины МОС запишем в следу- ющем виде:      min 1 1max 1 1 1 2 2 1 1 1 1 , 3 MN Mk k k k k k                      (7) где максимум ищется по всем значениям k∈[M–1]. Полученное выражение позволяет количе- ственно оценить эффективность известных ме- тодов построения МОС, определяя величину р — превышение длины рассматриваемой по- следовательности над минимально возможной. В [1, 6] ðàзðàбîòàí мåòîд ïîñòðîåíèÿ íà базе расширенных полей Галуа и просчитаны МОС для диапазона M = 5—50. В более позд- íèõ ðàбîòàõ [7, 8] èñïîëьзîâàí ïîõîжèé ïîд- ход и получены МОС с величиной М вплоть до 1000, причем результаты синтеза для диапазона M = 5—50 практически совпали с известными ре- зóëьòàòàмè, ïîëóчåííымè â [1, 6]. Пîëóчåííыå в результате синтеза последовательности с ве- ñîм 1000 ïðèâåдåíы â [8]. Òàêèм îбðàзîм, â óêà- занных работах для большого диапазона M (от 5 до 1000) предложены регулярные методы по- строения и построены МОС, имеющие конкрет- ную длину. На основании этих данных прове- ден анализ эффективности рассмотренных ме- тодов, численные результаты которого приведе- ны на рисунке. Результаты сравнения длины последовательностей, ïîëóчåííыõ â [1, 6] (а) è â [7, 8] (б), с минималь- но возможной длиной МОС, рассчитанной в соответ- ствии с выражением (7) P, % 15 10 5 0 10 20 30 40 M P, % 15 10 5 0 200 400 600 800 M а) б) Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2016, ¹ 2–3 35 ÑèÑòåìû ïåðåäàЧè è îáðàáîòêè Ñèãíàëîâ ISSN 2225-5818 Для интегральной оценки эффективности регулярных методов построения МОС на базе ðàñшèðåííыõ ïîëåé Гàëóà [1, 6—8] быëî ïðî- ведено поинтервальное сравнение значений длины полученных в этих работах последова- тельностей с оценкой (7). При этом ряд зна- чений M = 5—1000 разбивался на поддиапазо- ны, для каждого из которых было просчитано значение р* — средний процент превышения длины синтезированных последовательностей над оценкой (7). Результаты сравнения приве- дены в таблице. Приведенные на графиках и в таблице дан- ные свидетельствуют о высокой эффективности ðåãóëÿðíыõ мåòîдîâ ïîñòðîåíèÿ [1, 6—8], âè- димо, асимптотически стремящейся к предель- ной при неограниченном увеличении M (для М = 3000 зíàчåíèå р ñîñòàâëÿåò мåíåå 3%). Таким образом, полученное выражение для расчета минимальной предельной длины МОС позволяет проводить количественную оценку эф- фективности регулярных методов построения по- следовательностей со свойством «не более одно- го совпадения». ИСПОЛЬЗОВАННЫЕ ИСТОЧНИКИ 1. Свердлик М.Б. Оптимальные дискретные сигналы.— Мîñêâà: Сîâåòñêîå ðàдèî, 1975. 2. Ипатов В.П. Широкополосные системы и кодовое разделение сигналов. Принципы и приложения.— Москва: Техносфера, 2007. — 488 с. 3. Сêëÿð Б. Цèфðîâàÿ ñâÿзь. Òåîðåòèчåñêèå îñíîâы è практическое применение.— Москва: Издательский дом «Вèëьÿмñ», 2003. 4. Глобус И. А. Двоичное кодирование в асинхронных ñèñòåмàõ.— Мîñêâà: Сâÿзь, 1972. — 108 ñ. 5. Скляров О.В. Волоконно-оптические сети и системы связи.— Москва: СОЛОН-Пресс, 2004. 6. Свердлик М.Б, Мелешкевич А.Н. Синтез оптималь- ных множеств со свойством «не более одного совпадения» // Рàдèîòåõíèêà è ýëåêòðîíèêà.— 1976.— T. 19, ¹ 7.— C. 1443—1451. 7. Гантмахер В.Е., Платонов С.М. Синтез оптималь- ных импульсных последовательностей со свойством «не бо- лее одного совпадения» над расширенными полями Галуа второй и третьей степени. // Известия вузов России. Рàдèîýëåêòðîíèêà.— 2009.— ¹ 6.— С. 31—36. 8. База данных оптимальных импульсных последова- тельностей со свойством «не более одного совпадения»: Сâèд. î ãîñ. ðåãèñòðàцèè ¹ 2009620525 / Нîâãîðîдñêèé гос. ун-т имени Ярослава Мудрого / Платонов С.М., Гантмахер В.Е.— 11.01.2010. Äата поступления рукописи в редакцию 18.02 2016 г. М 5—10 10—20 20—30 30—40 40—50 50—70 70—100 р, % 4,3 10,7 11 11,7 11 17,6 17,7 М 100—150 150—200 200—300 300—400 400—600 600—1000 р, % 17,5 12,7 10,3 8 7 4,5 О. I. Неврев, О. М. ГАлчОНКОв Україна, Одеський національний політехнічний університет e-mail: a.i.nevrev@gmail.com ЕФЕКТИВНІСТЬ МЕТОДІВ СИНТЕЗУ ПОСЛІДОВНОСТЕЙ З ВЛАСТИВІСТЮ «НЕ БІЛЬШЕ ОДНОГО ЗБІГУ» Отримано вираз для визначення мінімально можливої довжини послідовностей з властивістю «не більше одного збігу». Цю оцінку використано для проведення порівняльного аналізу ефективності відомих регу- лярних методів побудови синтезованих послідовностей. Показано високу ефективність методів побудо- ви, заснованих на теорії розширених полів Галуа. Ключові слова: послідовність, «не більше одного збігу», регулярні методи побудови, нижня межа довжи- ни послідовності, ефективність методу. A. I. Nevrev, O. N. GAlcheNkOv Ukraine, Odessa National Polytechnic University e-mail: a.i.nevrev@gmail.com EffIcIENcy Of SEqUENcE SyNthESIS mEthOdS wIth thE «NOt mOrE thaN ONE cOINcIdENcE» PrOPErty The author presents an expression for determining the minimum possible length of binary sequences with «not more than one coincidence» property. Obtained low bound length value allows quantitatively estimating DOI: 10.15222/TKEA2016.2-3.33 Udc 612.391.15 Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2016, ¹ 2–3 36 ÑèÑòåìû ïåðåäàЧè è îáðàáîòêè Ñèãíàëîâ ISSN 2225-5818 rEfErENcES 1. Sverdlik m.B. Optimal’nye diskretnye signaly [Optimal discrete signals]. Moscow, Sovetskoe Radio, 1975, 200 p. 2. Ipatov V.P. Shirokopolosnye sistemy i kodovoe razdelenie signalov. Printsipy i prilozheniyа [wideband Systems and code Signal Separation. Principles and Applications]. Moscow, Technosphera, 2007, 488 p. 3. Sclar Bernard. Digital communication. Fundamentals and Application. Prentice hall rtP, 2001. 4. Globus I. a. Dvoichnoe kodirovanie v asinkhronnykh sistemakh [Binary coding in asynchronous systems]. Moscow, Svyàz’, 1972, 108 p. 5. Sklyаrov O.V. volokonno-opticheskie seti i sistemy svyаzi [Fiber optic networks and communication systems]. Moscow, SOLON-Press, 2004, 272 p. 6. Sverdlik m.B, meleshkevich a.N. [Synthesis of optimal sequences with property “not more than one coincidence]. radiotekhnika i elektronika, 1976, vol. 19, no. 7, pp. 1441-1451. 7. Gantmakher V.E., Platonov S.m. [Optimal pulse sequences with property “Not more than one coincidence” synthesis over extended Galois fields to the second and third power] Proceedings of the russian Universities. radioelektroniks, 2009, no. 6, pp. 31-36. (Rus) 8. [Data base for optimal pulse sequences with property “not more than one coincidence”]: Certificate database state registration number 2009620525 / Yaroslav-the-Wise Novgorod State University / Platonov S.m., Gantmakher V.E., 11.01.2010. efficiency of any known synthesis methods for creation of binary sequences with «not more than one coincidence» property. The efficiency of known methods of creating binary sequences based on extended Galois fields theory is analyzed by comparing the obtained sequences length with a theoretical low bound estimation. The paper shows high performance of the known methods of creation of sequences with «not more than one coincidence» property based on extended Galois fields. keywords: binary sequences, sequences with «not more than one coincidence», lower bound sequence length estimate, Galois fields. ÍÎÂÛÅ ÊÍÈÃÈ Í Î Â Û Å Ê Í È Ã È òеслюк â. ì., ïукач à. І., Загарю ð. â. ìетоди, моделі та засоби автоматизації визначення ємнісних і резистивних параметрів елементів ìåìÑ.— ëьвів: âидавництво ëьвівської політехніки, 2015. Проаналізовано методи, моделі та засоби визначення електрично- го опору резистивних параметрів електричних кіл, а також роз- глянуто резистивні та ємнісні параметри МЕМС та особливості автоматизації визначення їх значення. Наведено розроблені методи для автоматичного визначення електричного опору та ємності рези- стивних та ємнісних параметрів МЕМС, що враховують особливості та специфіку МЕМС-технологій. Здійснено моделювання роботи розроблених методів та аналіз отриманих результатів. Для радіоінженерів, науковців і студентів, які спеціалізуються у сфері автоматизації вимірювання та контролю ємнісних і резистивних параметрів мікроелектронних пристроїв та систем. áобало Ю. Я., Ñтахів ï. ã., ðендзіняк Ñ. Й. та ін. êомбінований (гібридний) лабораторний практикум з теорії електричних та електрон- них кіл, сигналів і вимірювань у комп’ютеризованій лабораторії.— ëьвів: âидавництво ëьвівської політехніки, 2016. Навчальний посібник містить комплекс лабораторних робіт з теорії електричних та електронних кіл, сигналів і вимірювань, які вико- нують у два етапи: фізичний експеримент та віртуальний експери- мент. Такий підхід дає змогу поглибити здобуті теоретичні знан- ня, набути практичних навичок роботи з технічним обладнанням. Для студентів електротехнічних та електромеханічних спеціальностей вищих навчальних закладів. Í Î Â Û Å Ê Í È Ã È

Эффективность методов синтеза последовательностей со свойством «не более одного совпадения»

Репозитарії

Схожі ресурси