Preview

Journal of «Almaz – Antey» Air and Space Defence Corporation

Advanced search

Construction of an orthogonal basis based on pseudorandom sequences

https://doi.org/10.38013/2542-0542-2020-4-95-100

Abstract

In this paper, we consider an approach to constructing an orthogonal transform based on pseudorandom sequences with the purpose of providing noiseless coding. This approach ensures the absence of congestion in the channel thus allowing the problem of restricted access in confidential systems to be solved.

For citation:


Svetlov G.V., Sumenkov N.A., Kostrov B.V., Grinchenko N.N., Trushina E.A. Construction of an orthogonal basis based on pseudorandom sequences. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

The problem of ensuring noiseless coding in digital information transmission systems has ever been quite a pressing issue and is going to remain so for a long time yet. Reducing probability of transmitting erroneous bits makes it possible to reduce power of transmitting devices and make the overall dimensions of systems smaller. This is especially relevant for systems admitting of certain probability of a transmission error that does not influence consumer quality of the information received. For example, in image transmitting systems [1][2][3], certain distortions that do not affect perception of images can be tolerable. Such systems will employ compression protocols and noiseless coding based on orthogonal transforms with piecewise constant basic functions [4][5][6]. Despite the simplicity and clarity of using such transforms, they have some inherent disadvantages too. The main one could be uneven distribution of energy across the transform basis, which leads
to substantial power ripples in the transmitting channel.

It is proposed in this paper to construct an orthogonal transform on the base of pseudorandom sequences (hereinafter – PRS) generated by a shift register with linear feedback. A random character of the change of states (pseudo noise feature) in such sequences ensures the absence of sharp variations of power over the interval of transform and will allow to ensure the absence of congestion in the channel. Moreover, through such approach it could be possible to solve the problem of access restriction in confidential systems.

The initial information for PRS construction is a generative polynomial

where aN, a1 = 1; ai ∈ {0,1}; N – number of shift register bits.

The generative polynomial must be irreducible and primitive. Among the many polynomials complying with these requirements the most convenient are those having the fewest number of zero elements, which ensures the minimal configuration of PRS generator with the fewest number of additions by modulo two in the feedbacks. In so doing, it is necessary that the polynomial sets the initial state (a1 = 1) in the least significant bit, otherwise a zero sequence is formed.

Any generative polynomial can be matched by a Fibonacci generator [7]

where gi (t) – state of the i-th shift register bit at clock cycle 

In a matrix form, the sequence generation algorithm will be

G(k +1) = Ψ ∙ G(k), (3)

Let us consider an example.

M(x) = x3 + x2 +1.

In accordance with (2), it can be written as follows:

Or in a matrix form:

A table of register bit states, composed in accordance with (4) and (5), is given below.

Table

Conditions of shift register bits

As can be seen from the table, a full cycle of the sequence consists of 8 clock cycles, 7 of which do not repeat, and the 8th clock cycle is the start of a new period. The PRS is read out from bit g3.
Its period is equal to 2N – 1, N – number of bits.

The considered sequences have the following properties.

1. A PRS period generated in accordance with generative polynomial M(x) is M = 2N – 1 (6)

2. For the set polynomial M(x), there is M number of different PRS’s obtained through cyclic shifting of the initial sequence.

3. The number of unity symbols in PRS period is equal to 2N – 1, and zero symbols – 2N – 1 – 1.

4. In PRS, single-symbol series are encountered 2N – 2 times, series of two similar symbols – 2N – 3 times, and so on. Series of N – 1 zeros and N unities occur just once.

5. An autocorrelation function of the obtained sequence is defined by the expression:

6. Sequence decimation by even index j = M – 1 results in inversion of the initial sequence, which corresponds to the sequence generated by polynomial M–1(x), which is an inverse of M(x). {bi} = {c–i}, where bi – reverse PRS, ci – straight PRS.

The considered PRS’s are customarily referred to as maximum period sequences, or M-sequences.

The number of various polynomials M(x) generating an М-sequence depends on its period M = 2n – 1. It grows rapidly with an increase of n. For n = 8, the number of generating polynomials is 16 [8]. A particular kind of obtained sequence will depend also on the initial conditions specified for initiating sequence generation. At n = 8, the number of initial conditions is 255. Hence, given the setting of n = 8, the number of М-sequence variations is 16 (2n – 1) ≈ 4000. With an increase of n this figure grows rapidly (e.g., at n = 10, up to 60,000).

In this way, by using maximum-period sequence generation mechanism [7], it is possible to construct a sufficiently large number of orthogonal transforms that can be used for conversion of signals transmitted through communication channels [9].

Let us consider the process of transform matrix generation. As follows from property 2, the necessary number of matrix rows can be obtained through cyclic shifting of the initial sequence. The number of rows in such matrix will be equal to period M = 2n – 1, and the matrix will be of the order M × M. All the rows and columns of this matrix will be represented by M-sequences. An example of such matrix generation is given in Fig. 1a. This matrix has the property of symmetry of its rows and columns in accordance with property 5. With rows and columns coinciding, the autocorrelation function is equal to 1. However, if rows and columns do not coincide, the autocorrelation function value is equal to –1/M. The product of matrix M by MT, where MT – matrix transpose, is given in Fig. 1b. The multiplication result is not a unity matrix, which does not comply with the orthogonal transform features.


Fig. 1. Matrix for obtaining sequence by shifting to the left at M(x) = x3+x2+1 and initial state 100(4) (а), and product of multiplication by matrix transpose (b)

To fulfil the orthogonality conditions, it is necessary to:

  • equalise the number of zero and unity symbols in the PRS period, making it equal to 2n – 1;
  • introduce sign alternation in the PRS so as to ensure zero constant component in matrix rows and columns.

Thus generated transform matrix M80 and
its respective product by matrix transpose M8Tare given in Fig. 2.


Fig. 2
. Orthogonal matrix corresponding to M(x) = x3+x2+1 and initial state 100(4) (а), and multiplication product M0∙MT0 (b)

As follows from Fig. 2, matrix M80, constructed for the above example, complies with the orthogonality requirements and can be used for conversion of signals. The number of such matrices depends on the desired n and corresponds to the number of М-sequences that can be constructed on the base of various generative polynomials. In a general case, the transform pair can be written as follows:

where Fnc – matrix (row matrix) of signal conversion factors; Bnc – signal matrix (column matrix); Mn0T – transpose of transform matrix.

Given in Fig. 3 is the result of using this approach for simulating the process of satellite images transmission [10][11][12] through communication channel. Generative polynomial M(x) = x7+ x5+ x4+ x3+1, initial state 10101101(173). Acting as signal matrix Bnc is the grey-level array. Since matrix M0 is symmetrical, there is no need in the transposition operation.


Fig. 3
. Use of orthogonal transform for transmitting satellite image through noise affected channel: initial image (a), noise impact result (RMSD = 40) at transmission without transform (b), and result of transmission with transform (RMSD = 2.55) (c)

The given example shows that application of pseudo-noise orthogonal transforms has a prospect for building systems of noiseless coding and information protection in confidential systems.

References

1. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. М.: Техносфера, 2006. 616 с.

2. Злобин В. К., Костров Б. В., Саблина В. А. Место и роль методов секвентного анализа в обработке аэрокосмических изображений // Радиотехника. 2012. № 3. С. 64-72.

3. Костров Б. В., Саблина В. А. Адаптивная фильтрация изображений со структурными искажениями // Цифровая обработка сигналов. 2008. № 4. С. 49-53.

4. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов / под ред. И. Б. Фоменко. М.: Связь, 1980. 248 с.

5. Злобин В. К., Костров Б. В., Свирина А. Г. Спектральный анализ изображений в конечных базисах. М.: КУРС: ИНФРА, 2016. 172 с.

6. Костров Б. В., Бастрычкин А. С. Сжатие изображений на основе ортогональных преобразований // Известия Тульского государственного университета. Технические науки. 2016. Вып. 9. С. 113-118.

7. Гарифуллина З. Р., Иванов М. А., Рябков В. Е., Чугунков И. В. Способ формирования нелинейных М-последовательностей // Безопасность информационных технологий. 2011. № 2. С. 31-36.

8. Захаров И. Д., Ожиганов А. А. Использование порождающих полиномов М-последовательностей при построении псевдослучайных кодовых шкал // Известия вузов. Приборостроение. 2011. Т. 54. №. 6. С. 49-55.

9. Костров Б. В., Соломенцева Н. И. Моделирование канала связи // Известия Тульского государственного университета. Технические науки. 2017. Вып. 2. С. 95-100.

10. Костров Б. В. Особенности формирования аэрокосмических изображений радиотехническими системами // Проектирование и технология электронных средств. 2011. № 1. С. 4143.

11. Костров Б. В., Гринченко Н. Н., Степанов Д. С., Упакова А. Г. Алгоритм передачи изображения с восстановлением постоянной составляющей // Известия Тульского государственного университета. Технические науки. 2013. Вып. 9. Ч. 1. С. 244-249.

12. Костров Б. В., Упакова А. Г. Квазидвумерная фильтрация синхронных помех на изображении // Проектирование и технология электронных средств. 2012. № 1. С. 32-35.


About the Authors

G. V. Svetlov
Ryazan Industrial and Technical Enterprise Granit
Russian Federation

Svetlov Gennady Valentinovich - Cand. Sci. (Economics), General Director.

Ryazan


N. A. Sumenkov
Ryazan Industrial and Technical Enterprise Granit
Russian Federation

Sumenkov Nikolay Aleksandrovich - Dr. Sci. (Engineering), Deputy General Director, Chief Engineer, Research interests: operation of complex radio engineering systems.

Ryazan


B. V. Kostrov
Ryazan Industrial and Technical Enterprise Granit
Russian Federation

Kostrov Boris Vasilievich - Dr. Sci. (Engineering), Professor, Deputy Head, Automated Control System Department, Research interests: image processing, artificial intelligence, information technologies.

Ryazan


N. N. Grinchenko
Ryazan Industrial and Technical Enterprise Granit
Russian Federation

Grinchenko Natalya Nikolaevna - Cand. Sci. (Engineering), Assoc. Prof., Leading Software Engineer, Sigma Design Bureau, Research interests: application of information technologies and multimedia systems in image processing.

Ryazan


E. A. Trushina
Ryazan State Radio Engineering University
Russian Federation

Trushina Evgeniya Aleksandrovna - Postgraduate Researcher, Research interests: application of information technologies and multimedia systems in image processing.

Ryazan


For citation:


Svetlov G.V., Sumenkov N.A., Kostrov B.V., Grinchenko N.N., Trushina E.A. Construction of an orthogonal basis based on pseudorandom sequences. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2020;(4):95-100. https://doi.org/10.38013/2542-0542-2020-4-95-100

Views: 194


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2542-0542 (Print)