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

Автор(и)

  • Владимир-Мирон Владимирович Мискив Национальный университет "Львовская политехника", Ukraine
  • Иван Никифорович Прудиус Национальный университет "Львовская политехника", Ukraine https://orcid.org/0000-0003-3331-0892
  • Роман Владимирович Янкевич Национальный университет "Львовская политехника", Ukraine

DOI:

https://doi.org/10.20535/S0021347018070026

Ключові слова:

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

Анотація

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

Критерием эффективности каждого из предложенных алгоритмов принято отношение количества всех возможных вариантов кодовых двоичных последовательностей заданной размерности l к количеству, определяемому предложенными алгоритмами и получены выражения для этих количеств. Эффективность предложенных метода и алгоритмов подтверждена результатами моделирования и возрастает с увеличением размерности l.

Біографії авторів

Иван Никифорович Прудиус, Национальный университет "Львовская политехника"

Director of Institute of Telecommunications and Radio Electronincs

Роман Владимирович Янкевич, Национальный университет "Львовская политехника"

Assistant at REDS department

Посилання

Barker, R. H. “Group synchronizing of binary digital systems,” in: Jackson, W. (ed.) Communication Theory. New York: Academic Press, 1953, pp. 273-287.

Варакин, Л. Е. Системы связи с шумоподобными сигналами. М.: Радио и связь, 1985. 384 с.

Skolnik, M. I. Radar Handbook, 3rd ed. New York: McGraw-Hill, 2008.

IRIG STANDARD 106-04. Telemetry Standards.

Jedwab, J. “What can be used instead of a Barker sequence?” Contemp. Math., Vol. 461, pp. 153-178, 2008. DOI: http://doi.org/10.1090/conm/461/08991.

Leung, K. H.; Schmidt, B. “The field descent method,” Des. Codes Crypt., Vol. 36, No. 2, P. 171-188, 2005. DOI: https://doi.org/10.1007/s10623-004-1703-7.

Jedwab, J.; Parker, M. G. “Golay complementary array pairs,” Des. Codes Crypt., Vol. 44, No. 1-3, P. 209-216, 2007. DOI: https://doi.org/10.1007/s10623-007-9088-z.

Alquaddoomi, S.; Scholtz, R. A. “On the nonexistence of Barker arrays and related matters,” IEEE Trans. Inf. Theory, Vol. 35, No. 5, P. 1048-1057, 1989. DOI: https://doi.org/10.1109/18.42220.

Davis, J. A.; Jedwab, J.; Smith, K. W. “Proof of the Barker array conjecture,” Proc. Amer. Math. Soc., Vol. 135, P. 2011-2018, 2007. DOI: http://doi.org/10.1090/S0002-9939-07-08703-5.

Jedwab, J.; Parker, M. G. “There are no Barker arrays having more than two dimensions,” Des. Codes Crypt., Vol. 43, No. 2-3, P. 79-84, 2007. DOI: https://doi.org/10.1007/s10623-007-9060-y.

Golomb, S. W.; Gong, G. Signal Design for Good Correlation: for Wireless Communication, Cryptography, and Radar. New York, NY: Cambridge University Press, 2005.

Moon, J. W.; Moser, L. “On the correlation function of random binary sequences,” SIAM J. Appl. Math., Vol. 16, No. 2, P. 340-343, 1968. URI: https://www.jstor.org/stable/2099297.

Jedwab, J.; Yoshida, K. “The peak sidelobe level of families of binary sequences,” IEEE Trans. Inf. Theory, Vol. 52, No. 5, P. 2247-2254, 2006. DOI: https://doi.org/10.1109/TIT.2006.872863.

Dmitriev, D.; Jedwab, J. “Bounds on the growth rate of the peak sidelobe level of binary sequences,” Adv. Math. Commun., Vol. 1, No. 4, P. 461-475, 2007. DOI: http://dx.doi.org/10.3934/amc.2007.1.461.

Zeng, Xiangyong; Hu, Lei; Liu, Qingchong. “A family of binary sequences with optimal correlation property and large linear span,” The Computing Research Repository, August 2005. URI: https://arxiv.org/abs/cs/0508114.

Jensen, H. E.; Hoholdt, T. “Binary sequences with good correlation properties,” Proc. of 5th Int. Conf. on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5 15-19 Jun. 1987. Springer-Verlag, Berlin, 1989, pp. 306-320.

Borwein, P.; Choi, K.-K. S.; Jedwab, J. “Binary sequences with merit factor greater than 6.34,” IEEE Trans. Inf. Theory, Vol. 50, No. 12, P. 3234-3249, 2004. DOI: https://doi.org/10.1109/TIT.2004.838341.

Банкет, В. Л.; Токарь, М. С. “Композитные коды Баркера,” Цифровые технологии, № 2, С. 8–18, 2007. URI: https://ojs.onat.edu.ua/index.php/digitech/article/view/592.

Nunn, Carroll J.; Coxson, Gregory E. “Best-known autocorrelation peak sidelobe levels for binary codes of length 71 to 105,” IEEE Trans. Aerosp. Electron. Syst., Vol. 44, No. 1, P. 392-395, 2008. DOI: https://doi.org/10.1109/TAES.2008.4517015.

Schmidt, Kai-Uwe. “Binary sequences with small peak sidelobe level,” IEEE Trans. Inf. Theory, Vol. 58, No. 4, P. 2512-2515, 2012. DOI: https://doi.org/10.1109/TIT.2011.2178391.

Packebusch, T.; Mertens, S. “Low autocorrelation binary sequences,” J. Phys. A: Math. Theor., Vol. 49, No. 16, 165001, 2016. DOI: https://doi.org/10.1088/1751-8113/49/16/165001.

Бобало, Ю. Я.; Міськів, В.-М. В.; Міськів, А. В.; Прудиус, І. Н.; Янкевич, Р. В. “Аспекти оптимізації кодових конструкцій,” Матеріали V міжнар. наук.-практ. конф. «Фізико-технологічні проблеми передавання, обробки та зберігання інформації в інфокомунікаційних системах,» 3–5 листопада 2016, Чернівці, Україна. Чернівці, Місто, 2016, pp. 191–192.

Miskiv, Volodymyr-Myron; Prudyus, I.; Yankevych, R. “Properties of binary code sequences on the periodical convolution,” Proc. of 2017 ІЕЕЕ Int. Conf. on Information and Telecommunication Technologies and Radio Electronics, UkrMiCo’2017. 11-15 Sept. 2017, Odessa, Ukraine. IEEE, 2017, pp. 95-98. DOI: https://doi.org/10.1109/UkrMiCo.2017.8095373.

Mis’kiv, A.; Mis’kiv, V.-M.; Prudyus, I.; Yankevych, R. “Discrete sequencies with optimal aperiodic autocorrelation functions. Conditions for existance,” Proc. of 14th Int. Conf. on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering, TCSET, 20-24 Feb. 2018, Lviv-Slavske, Ukraine. IEEE, 2018, pp. 1264-1267. DOI: https://doi.org/10.1109/TCSET.2018.8336424.

Прудников, А. П.; Брычков, Ю. А.; Маричев, О. И. Интегралы и ряды. М.: Наука, ГРФМЛ, 1981. 800 с.

Меньшиков, М. В.; и др. Комбинаторный анализ. Задачи и упражнения. Под ред. К. А. Рыбникова. М.: Наука. ГРФМЛ, 1982. 368 с.

##submission.downloads##

Опубліковано

2018-07-28

Як цитувати

Мискив, В.-М. В., Прудиус, И. Н., & Янкевич, Р. В. (2018). Оптимизация кодовых конструкций класса двоичных последовательностей на основе их теоретико-множественного представления. Вісті вищих учбових закладів. Радіоелектроніка, 61(7), 383–397. https://doi.org/10.20535/S0021347018070026

Номер

Том 61 № 7 (2018)

Розділ

Оригінальні статті

Ліцензія

Авторське право (c) 2018 Известия высших учебных заведений. Радиоэлектроника

Издатель журнала Известия высших учебных заведений. Радиоэлектроника (сокр. "Известия вузов. Радиоэлектроника"), Национальный технический университет Украины "Киевский политехнический институт", учитывает, что доступ автора к его статье является важным как для самого автора, так и для спонсоров его исследований. Мы представлены в базе издателей SHERPA/RoMEO как зеленый издатель (green publisher), что позволяет автору выполнять самоархивирование своей статьи. Однако важно, чтобы каждая из сторон четко понимала свои права. Просьба более детально ознакомиться с Политикой самоархивирования нашего журнала.

Политика оплаченного открытого доступа POA (paid open access), принятая в журнале, позволяет автору выполнить все необходимые требования по открытому доступу к своей статье, которые выдвигаются институтом, правительством или фондом при выделении финансирования. Просьба более детально ознакомиться с политикой оплаченного открытого доступа нашего журнала (см. отдельно).

Варианты доступа к статье:

1. Статья в открытом доступе POA (paid open access)

В этом случае права автора определяются лицензией CC BY (Creative Commons Attribution).

2. Статья с последующим доступом по подписке

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

  • Автор (каждый соавтор) уступает Издателю журнала «Известия высших учебных заведений. Радиоэлектроника» НТУУ «КПИ» на срок действия авторского права эксклюзивные права на материалы статьи, в том числе право на публикацию данной статьи издательством Аллертон Пресс, США (Allerton Press) на английском языке в журнале «Radioelectronics and Communications Systems». Передача авторского права охватывает исключительное право на воспроизведение и распространение статьи, включая оттиски, переводы, фото воспроизведения, микроформы, электронные формы (он- и оффлайн), или любые иные подобные формы воспроизведения, а также право издателя на сублицензирование третьим лицам по своему усмотрению без дополнительных консультаций с автором. При этом журнал придерживается Политики конфиденциальности.
  • Передача прав включает право на обработку формы представления материалов с помощью компьютерных программам и систем (баз данных) для их использования и воспроизводства, публикации и распространения в электронном формате и внедрения в системы поиска (базы данных).
  • Воспроизведение, размещение, передача или иное распространение или использование материалов, содержащихся в статье должно сопровождаться ссылкой на Журнал и упоминанием Издателя, а именно: название статьи, имя автора (соавторов), название журнала, номер тома, номер выпуска, копирайт авторов и издателя "© Национальный технический университет Украины "Киевский политехнический институт"; © автор(ы)".
  • Автор (каждый соавтор) материалов сохраняет все права собственника материалов, включая патентные права на любые процессы, способы или методы и др., а также права на товарные знаки.
  • Издатель разрешает автору (каждому соавтору) материалов следующее:
  1. Право пользоваться печатными или электронными вариантами материалов статьи в форме и содержании, принятыми Издателем для публикации в Журнале. Подробнее см. политики Оплаченного открытого доступа, подписки и самоархивирования.
  2. Право бесплатно копировать или передавать коллегам копию напечатанной статьи целиком или частично для их личного или профессионального использования, для продвижения академических или научных исследований или для учебного процесса или других информационных целей, не связанных с коммерческими целями.
  3. Право использовать материалы из опубликованной статьи в написанной автором (соавторами) книге, монографии, учебнике, учебном пособии и других научных и научно-популярных изданиях.
  4. Право использовать отдельные рисунки или таблицы и отрывки текста из материалов в собственных целях обучения или для включения их в другую работу, которая печатается (в печатном или электронном формате) третьей стороной, или для представления в электронном формате во внутренние компьютерные сети или на внешние сайты автора (соавторов).
  • Автор (соавторы) соглашаются, что каждая копия материалов или любая ее часть, распространенная или размещенная ими в печатном или электронном формате, будет содержать указание на авторское право, предусмотренное в Журнале и полную ссылку на Журнал Издателя.
  • Автор (соавторы) гарантирует, что материалы являются оригинальной работой и представлены впервые на рассмотрение только в этом Журнале и ранее не публиковались. Если материалы написаны совместно с соавторами, автор гарантирует, что проинформировал их относительно условий публикации материалов и получил их подписи или письменное разрешение подписываться от их имени.
  • Если в материалы включаются отрывки из работ или имеются указания на работы, которые охраняются авторским правом и принадлежат третьей стороне, то автору необходимо получить разрешение владельца авторских прав на использование таких материалов в первом случае и сделать ссылку на первоисточник во втором.
  • Автор гарантирует, что материалы не содержат клеветнических высказываний и не посягают на права (включая без ограничений авторское право, права на патент или торговую марку) других лиц и не содержат материалы или инструкции, которые могут причинить вред или ущерб третьим лицам. Автор (каждый соавтор) гарантирует, что их публикация не приведет к разглашению секретных или конфиденциальных сведений (включая государственную тайну). Подтверждением этого является Экспертное заключение (см. перечень документов в Правила для авторов).
  • Издатель обязуется опубликовать материалы в случае получения статьей положительного решения редколлегии о публикации на основании внешнего рецензирования (см. Политика рецензирования).
  • В случае публикации статьи на английском языке в журнале «Radioelectronics and Communications Systems» (Издатель: Аллертон Пресс, США, распространитель Springer) автору (соавторам) выплачивается гонорар после выхода последнего номера журнала года, в котором опубликована данная статья.
  • Документ Согласие на публикацию, который подают русскоязычные авторы при подаче статьи в редакцию, является краткой формой данного договора, в котором изложены все ключевые моменты настоящего договора и наличие которого подтверждает согласие автора (соавторов) с ним. Аналогичным документом для англоязычных авторов является Copyright Transfer Agreement (CTA), предоставляемый издательством Allerton Press.
  • Настоящий Договор вступает в силу в момент принятия статьи к публикации. Если материалы не принимаются к публикации или до публикации в журнале автор (авторы) отозвал работу, настоящий Договор не приобретает (теряет) силу.