Формирование пятеричных последовательностей Гордона — Миллса — Велча для систем передачи дискретной информации
Ключевые слова:
псевдослучайные последовательности, конечные поля, неприводимые, примитивные и минимальные полиномы, эквивалентная линейная сложность, децимация, регистры сдвигаАннотация
Предложен алгоритм формирования пятеричных последовательностей Гордона — Миллса — Велча (ГМВ) с периодом N=54–1=624 над конечным полем с двойным расширением GF[(52)2], основанный на матричном представлении базисной М-последовательности с примитивным проверочным полиномом hмп(x) четвертой степени и аналогичным периодом. Показано, что проверочный полином hг(x) ГМВ-последовательностей может быть представлен в виде произведения нескольких неприводимых над простым полем GF(5) полиномов-сомножителей hсi(x) четвертой степени. Получены соотношения между корнями полинома hмп(x) базисной М-последовательности и корнями полиномов hсi(x), на основании которых может быть сформирован весь перечень ГМВ-последовательностей с периодом N=624. Показано, что для каждого из 48 примитивных полиномов четвертой степени, являющихся проверочными полиномами для базисных М-последовательностей, может быть сформировано по три ГМВ-последовательности с эквивалентной линейной сложностью (ЭЛС) ls=12, 24, 40, характеризующей структурную скрытность псевдослучайных последовательностей (ПСП). Представлено устройство формирования ГМВ-последовательности в виде совокупности регистров сдвига с линейными обратными связями, в котором умножители и сумматоры по mod5 расставляются в соответствии с коэффициентами неприводимых полиномов hсi(x). Начальные состояния ячеек регистров сдвига определяются путем децимации символов базисной М-последовательности по индексам децимации, равным минимальным показателям степени корней полиномов hсi(x). Особенностью определения начальных состояний устройств формирования пятеричных ГМВ-последовательностей по сравнению с двоичными является наличие циклических сдвигов суммируемых последовательностей на величину, кратную N/(p–1). Полученные результаты позволяют синтезировать устройства формирования полного перечня из 144 пятеричных ГМВ-последовательностей с периодом N=624 и различной ЭЛС. Применение ГМВ-последовательностей по сравнению с М-последовательностями позволяет существенно (в 3-10 раз) повысить структурную скрытность передаваемых широкополосных сигналов в системах передачи дискретной информации. Результаты исследований могут быть использованы при построении других классов псевдослучайных последовательностей, допускающих аналитическое представление в конечных полях.
Литература
2. Ипатов В.П. Широкополосные системы и кодовое разделение сигналов. Принципы и приложения // М.: Техносфера. 2007. 488 с.
3. Golomb S.W., Gong G. Signal Design for Good Correlation for Wireless Com-munication, Cryptography and Radar // Cambridge University Press. 2005. 438 p.
4. Варакина Л.Е., Шинакова Ю.С. CDMA: прошлое, настоящее, будущее // М.: МАС. 2003. 608 с.
5. Chung H.B., No J.S. Linear span of extended sequences and cascaded GMW sequences // IEEE Transactions on Information Theory. 1999. vol. 45. no. 6. pp. 2060–2065.
6. Rizomiliotis P., Kalouptsidis N. Results on the nonlinear span of binary se-quences // IEEE Transactions on Information Theory. 2005. vol. 51. no. 4. pp. 1555–1563.
7. Ипатов В.П. Периодические дискретные сигналы с оптимальными корре-ляционными свойствами // М.: Радио и связь. 1992. 152 с.
8. No J.S. Generalization of GMW sequences and No sequences // IEEE Transac-tions on Information Theory. 1996. vol. 42. no. 1. pp. 260–262.
9. Стародубцев В.Г., Бородько Д.Н., Мышко В.В. Алгоритм формирования ГМВ-последовательностей с периодом N=4095 в системах передачи теле-метрической информации // Авиакосмическое приборостроение. 2018. № 5. С. 3–15.
10. Стародубцев В.Г., Мышко В.В., Ткаченко В.В. Аппаратная и программная реализация алгоритма формирования последовательностей Гордона–Миллса–Велча // Наукоемкие технологии в космических исследованиях Земли. 2018. Т. 10. № 3. С. 13–20.
11. Tsankov T., Trifonov T., Staneva L. An algorithm for synthesis of phase ma-nipulated signals with high structural complexity // Journal Scientific & Applied Research. 2013. vol. 4. pp. 80–87.
12. Самойленко Д.В., Еремеев М.А., Финько О.А., Диченко С.А. Параллельный линейный генератор многозначных псевдослучайных последовательностей с контролем ошибок функционирования // Труды СПИИРАН. 2018. Вып. 4(59). С. 31–61.
13. Стародубцев В.Г., Чернявских А.Е. Формирование троичных последова-тельностей Гордона–Миллса–Велча на основе регистров сдвига // Известия высших учебных заведений. Приборостроение. 2016. Т. 59. № 3. С. 201–210.
14. Lee W., Kim J.Y., No J.S. New families of p-ary sequence of period (p↑n–1)/2 with low maximum correlation magnitude // IEICE Transactions on Communi-cations. 2014. vol. 97. no. 11. pp. 2311–2315.
15. Cho C.M., Kim J.Y., No J.S. New p-ary sequence families of period (p↑n-1)/2 with good correlation property using two decimated m-sequences // IEICE Transactions on Communications. 2015. vol. 98. no. 7. pp. 1268–1275.
16. Tasheva Z. A short survey of p-ary pseudo-random sequences // Journal Scien-tific & Applied Research. 2014. vol. 2. pp. 17–26.
17. Liang H., Tang Y. The cross correlation distribution of a p-ary m-sequence of period p↑m–1 and its decimated sequences by (p↑k+1)(p↑m+1)/4 // Finite Fields and Their Applications. 2015. vol. 31. pp. 137–161.
18. Zhang T., Li S., Feng T., Ge G. Some new results on the cross correlation of m-sequences // IEEE Transactions on Information Theory. 2014. vol. 60. no. 5. pp. 3062–3068.
19. Владимиров С.С., Когновицкий О.С. Широкополосные сигналы данных с расширением спектра прямой троичной М-последовательностью и их ха-рактеристика // Труды учебных заведений связи. 2017. Т. 3. № 3. С. 28–36.
20. Xia Y., Chen S. A new family of p-ary sequences with low correlation con-structed from decimated sequences // IEEE Transactions on Information Theo-ry. 2012. vol. 58. no. 9. pp. 6037–6046.
21. Helleseth T., Kumar P.V., Martinsen H. A new family of ternary sequences with ideal two-level autocorrelation function // Designs, Codes and Cryptography. 2001. vol. 23. no. 2. pp. 157–166.
22. Tang X.H., Pingzhi Z.F. A class of pseudonoise sequences over GF(p) with low correlation zone // IEEE Transactions on Information Theory. 2001. vol. 47. no. 4. pp. 1644–1649.
23. Bedzhev B.Y., Yordanov S.S. Method for synthesis of large families of signals with low correlation // Journal Scientific & Applied Research. 2012. vol. 2. pp. 13–20.
24. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки // М.: Мир. 1976. 594 с.
Formation of Quinary Gordon-Mills-Welch Sequences for Discrete Information Transmission Systems
Abstract
An algorithm for the formation of the quinary Gordon-Mills-Welch sequences (GMWS) with a period of N=54-1=624 over a finite field with a double extension GF[(52)2] is proposed. The algorithm is based on a matrix representation of a basic M-sequence (MS) with a primitive verification polynomial hмs(x) and a similar period. The transition to non-binary sequences is determined by the increased requirements for the information content of the information transfer processes, the speed of transmission through communication channels and the structural secrecy of the transmitted messages. It is demonstrated that the verification polynomial hG(x) of the GMWS can be represented as a product of fourth-degree polynomials-factors that are indivisible over a simple field GF(5). The relations between roots of the polynomial hмs(x) of the basic MS and roots of the polynomials hсi(x) are obtained. The entire list of GMWS with a period N=624 can be formed on the basis of the obtained ratios. It is demonstrated that for each of the 48 primitive fourth-degree polynomials that are test polynomials for basis MS, three GMWS with equivalent linear complexity (ELC) of ls=12, 24, 40 can be formed. The total number of quinary GMWS with period of N=624 is equal to 144. A device for the formation of a GMWS as a set of shift registers with linear feedbacks is presented. The mod5 multipliers and summators in registers are arranged in accordance with the coefficients of indivisible polynomials hсi(x). The symbols from the registers come to the adder mod5, on the output of which the GMWS is formed. Depending on the required ELC, the GMWS forming device consists of three, six or ten registers. The initial state of cells of the shift registers is determined by the decimation of the symbols of the basic MS at the indexes of decimation, equal to the minimum of the exponents of the roots of polynomials hсi(x). A feature of determining the initial States of the devices for the formation of quinary GMWS with respect to binary sequences is the presence of cyclic shifts of the summed sequences by a multiple of N/(p–1). The obtained results allow to synthesize the devices for the formation of a complete list of 144 quinary GMWS with a period of N=624 and different ELC. The results can also be used to construct other classes of pseudo-random sequences that allow analytical representation in finite fields.
Опубликован
Как цитировать
Раздел
Copyright (c) 2019 Виктор Геннадьевич Стародубцев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).