Using Models of Parallel Specialized Processors to Solve the Problem of Signal Separation

Abstract

This paper considers models of highly efficient specialized processors used for parallel data processing as part of solving the problem of extracting individual signals from an additive mixture of several signals. The proposed models of recursive, nonrecursive, and regularization-based parallel specialized processors provide versatility in solving the problem of signal separation with various algorithms. An advantage of regularization-based processors is that they make the solution stable under conditions where the parameters of objects exhibit expected uncertainty when the inverse problem of signal separation is ill-posed. This paper presents the results we obtained from an asymptotic analysis of the computational complexity involved. The results identify the time it takes to solve problems by using specialized processors. The paper also identifies the conditions for the efficient use of specialized processors.

1. Introduction

The problem of signal separation consists in determining source signals unavailable for direct measurements by using source signals measured in accessible points where the signals are an additive mixture of source signals that are distorted when transmitted.

The computational complexity of algorithms involved in solving that problem is high and, for many applications, is of O(N 3 ) order, where N is the number of signal sources [ 1 ]. This makes it difficult to use these algorithms.

Computation parallelization is the conventional approach to reducing the time it takes to solve the problem of signal separation [ 2,3 ]. Parallel algorithms for signal separation have been developed for multicore processors, multiprocessor systems with shared and distributed memory, and multicomputer systems [ 4 ]. That solution is needed in many practical fields such as monitoring and diagnosis of technical facilities [ 5 ], communications, medical diagnosis, speech [ 6 ] and image [ 7 ] processing.

This is because in complicated facilities, measured signals present an additive mixture of signals received from many components, and in most practical applications the extraction of parameters that describe the state of specific components is impossible without signal separation.

The next significant performance improvement is possible through the use of specialized processors whose architecture and computational processes correspond most to the structure of the algorithm for the class of problems in question [ 1,8 ].

Signal separation methods can be classified into two groups—deterministic and statistical [ 1 ].

The deterministic group is based on principal information about signal transmission channels (statistical, frequency, amplitude, and other channel characteristics); that is, transmission channels and signals are known.

The statistical group is based on principal information about signal sources such as lacking source correlation and the knowledge of signal distribution laws. In this case, explicit information about transmission channels is unavailable, and only observed signals are known. For that reason, the methods within this group are often called “blind” [ 9 ].

Thus, the solution to the problem of separating of signal sources reduces to using a deterministic or statistical method to calculate the separating matrix equal or close, in terms of specific criteria, to the matrix inverse to mixing matrix.

The functionality of commercially available specialized digital signal processors and fieldprogrammable gate arrays is insufficient for solving the complex problem of signal separation.

Reference [ 10 ] only proposes basic signal-separation functions and objectives for specialized processors used for signal separation and restoration; and for the processor models described in [ 11 ], the analysis of the computational complexity involved in parallel processing is inadequate to identify the conditions for the efficient use of the processors.

It is advisable that the structure of specialized processors should be regular and have a neural network architecture [ 12 ]. Besides, those processors do not provide stable solutions under conditions where the properties of objects exhibit expected uncertainty when the inverse problem of signal separation is illposed.

The purpose of this paper is to develop parallel specialized processors for signal separation under conditions where the parameters of objects exhibit expected uncertainty and to analyze asymptotically the computational complexity of parallel processing to identify the conditions for the efficient use of the processors. 2. Research Area Since there are many algorithms for solving the problem of signal separation [ 1,9-13 ], parallel specialized processors should provide versatility in this class of problems. We will assume that the processor model consists of two units: the generic unit, which carries out the algorithm’s procedure steps; and the specialized unit, which provides structural simulation for the algorithm.

Let us assume that the model of signal formation is a linear multidimensional system with N inputs and M outputs [ 1,14 ]. The model’s input signals are sn  k  , n  1,2,...,N ; its output signals, xm  k  , m 1,2,...,M . The input signals come from a variety of sources unavailable for direct measurement, and the output signals come from various receivers such as detectors and antennas. We will assume that each output M is linked with all the N inputs through linear signal-transmission channels.

The mathematical model of signal formation is described by discrete-convolution equations (1), where the m th observable signal is the additive mixture of channel-distorted source signals and noise [ 1,14 ] - that is,

N G1 xm  k     hmn  g ,I  sn k  g   ym k  , n1 g0 (1) where hmn  g ,I  is the element N  M of the mixing matrix h  g ,I  for the channels’ pulse responses; y  k  is the noise vector; g  0,...,G -1 and k  0,...,K -1 are the samples of the pulse responses for channels and signals, respectively.

Let us assume that the channels’ pulse responses hmn  g ,l  are finite and that they depend on a certain parameter vector, l (time, locations of sources and receivers in relation to one another, etc.) [ 14 ].

Generally, the solution to the problem of separating source signals is (1), and it can be written as

M G1 sn  k     wnm  g ,I  xm k  g  , (2)

m1 g0 where wnm  g ,I  are the pulse responses of separating filters, and they form the separating matrix w  g ,I  , which is equal or close to a matrix inverse to the matrix h  g ,I  .

In separating signals by source, we will split the computation into two steps.

In step 1, the elements wnm  g ,I  of separating matrix w  g ,I  are determined from the measured dynamical properties of channels or from signal parameters, and the signal-separation algorithm is adjusted. The algorithm for computing wnm  g ,I  (the adjustment algorithm) takes into account the nuances of the given signal-separation algorithm.

In step 2, the signals are separated with the digital separating filters adjusted in step 1. This computational process is the same for different signal-separation algorithms.

With this in mind, we will look at two computational units in the model of a parallel specialized processor: the adjusting processor (AP) (the versatile unit) and the functional processor (FP) (the specialized unit).

The nonrecursive, recursive and regularization-based processor models treated below differ in the methods used to solve (1) but feature the same basic elements that the models are based on. 3. Model for a Nonrecursive Parallel Specialized Processor The model for the nonrecursive parallel specialized processor implements the method used to solve the system of equations (1) by inversing the mixing matrix h  g ,I  .

The nonrecursive processor model [ 10,11 ] is best written in the form convenient for parallel stream processing in the time domain:

M G1 s1  k     w1m  g ,I xm k  g 

m1 g0 ................................................... ,

M G1 sN  k     wNm  g ,I xm k  g 

m1 g0 where s1  k  ,...,sN  k  are the calculated signals that are approximations (samples) of the true signals s1  k  ,...,sN  k  in the points they are formed in; and wnm  g ,I  are the elements of separating matrix w  g ,I  obtained from and the mth column of the spectral matrix Wg ,I , which is inverse of the Hg ,I matrix—that is, Wg ,I  H1 g ,I at M=N (or of the pseudo-inverse matrix Wg ,I  H g ,I at M≠N).

The functional processor separates the source signals xm  k  according as they belong to the sources sn  k  . This processor implements a model that is inverse of the signal-formation model, and the processor has the regular homogeneous structure composed of N  M adjustable filters (AF) and N adders (A).

The filters and the units compute linear convolutions simultaneously and independently of one another. The computational complexity LnFoPnrec  K  of the functional processor’s operation algorithm, which determines the processing time, is characterized by the height of its parallel structure, is of LnFoPnrec ( K )  O(K) order, and does not depend on the number of signal sources.

The adjustment processor calculates the coefficients wnm  g ,I  for the AFs from the measurements of the channels’ transient responses (deterministic methods) or from the characteristics of signal sources (statistical separation methods) [ 9,13 ].

For deterministic methods, the algorithm used to compute the coefficients wnm  g ,I  consists of the following steps: using a fast Fourier transform for the channels’ transient responses to obtain the mixing spectral matrix H  ,I  ; inversing the spectral matrix H  ,I  to obtain the separating spectral matrix W  ,I  ; and using an inverse fast Fourier transform (IFFT) for the elements of separating matrix W  ,I  to obtain weight coefficients for the AFs, specified by the matrix w  g ,I  .

The parallel form of the adjustment algorithm’s first and third steps has a width of N  M and is implemented by the N  M units of the fast Fourier transform and the inverse fast Fourier transform. The computational complexity LnAoPn1r,e3c G  , which determines the time it takes to complete these steps depending on the heights of their parallel structures, is of LnAoPn1r,e3c G   O( G log2 G ) order.

The parallel form of the algorithm used to compute the separating matrix has a width of G and is implemented with G units for inversing N order matrices (assuming that N=M). Each of these units, in turn, implements the parallel form of the algorithm used to compute the inverting matrix (e.g., [ 3 ]) with a width of O(N 4 ) .

The height LnAoPn2rec (N)  О(log22 N) of the algorithm’s parallel form determines the time it takes to invert the spectral matrix H  ,I  .

The computational complexity LnAoPn1r,e2c,3 G,N  of the adjustment processor’s operation algorithm is significantly higher than the computational complexity LnFoPnrec  O(K) of the functional processor’s operation algorithm—that is,

O( G log2 G )  O(log22 N )  O( G log2 G  log22 N )  O(K) .

For instance, at K  G  N the relation  log2 G . Thus, separating signals with the LnAoPn1r,e2c,3 G,N 

LnFoPnrec (K) proposed nonrecursive processor is acceptable if within the signal interval determined by K  Glog2 G the parameters of the mixing matrix are assumed invariable—that is, if the signal-formation model is quasistationary.

Furthermore, given the polynomial relationship between the width O(N 4 ) of the parallel form of the matrix-inverting algorithm and the number of signal sources, we can conclude that the model of the nonrecursive processor we discussed can be used in practice to separate the signals sn  k  when the number of signal sources is low.

4. Model for a Recursive Parallel Specialized Processor

Figure 1 shows a recursive parallel specialized processor model that implements the iteration method for solving the system of equations (1).

The model’s functional processor (FP) has a regular homogeneous structure composed of M identical processing units (PU) [ 10,11 ]. All PUs operate parallel in time, and each implements the recursive  algorithm for extracting one signal sn k  from an additive mixture of several signals.

The computational complexity LrFePc  K  of the FP operation algorithm, which determines its operating time, is characterized by the height of its parallel form, is of LrFePc ( K )  O(K  ) order (where  is the number of iterations), and does not depend on the number of signal sources.

The adjusting processor (AP) consists of a clock unit (CU) and M groups of devices comprising an adjusting unit (AU) and a memory unit (MU). The pulse responses of the filters FPmn , n 1,...,N , and m 1,...,M (note the exclusion of m  n ) need not be calculated with the AP since the frequency characteristics of AFmn filters are equal to the frequency characteristics of channels with related indexes in the mixing matrix H  ,I  of the signal-formation model. These characteristics should only be stored in MUm, m 1,...,M .

The transient responses h11  g  , h22  g  ,...,hMN  g  , g  0,...,G 1 of the adjustable inverse filters AIFmn (only if m  n ) are computed in AUm, m 1,...,M .

The algorithm for computing hmn( mn )  g ,I  consists of the following steps: using a fast Fourier transform for the transient responses of the channels hmn( mn )  g ,I  to obtain the characteristics Hmn g ,I  ; computing H mn  g ,I   1 ; and using a fast Fourier transform for the

H mn  g ,I  characteristics Hmn g ,I  to obtain the weight coefficients hmn( mn )  g ,I  for AIFs.

The parallel form of the adjustment algorithm’s first and third steps has a width of N and is implemented by N FFT and IFFT units.

The computational complexity LrAePc1,3 G  , which determines the time it takes to complete these steps AP1,3 G   O( G log2 G ) order. depending on the height of their parallel form, is of Lrec

The parallel form of the algorithm used to compute the channels’ inverse characteristics Hmn g ,I  has a width of O( N  G ) and is implemented with N  G division units, while the height LrCeUc (N)  О(1) of the algorithm’s parallel form is a constant.

The CU synchronizes the transmission of parameters from AP to FP, sets the initial conditions, and controls the output registers while completing processing iterations. This unit’s operation algorithm has a constant complexity of LrCeUc (N)  О(1) .

The assessment of the computational complexity of the AP and FP algorithms (e.g., at K  G ), LrAePc1,2,3 G  

O( G log2 G )  O(1)  O(1)

 log2 G ,

LrFePc (K) O( K ) for the recursive processor presents the conclusion that signal separation with the proposed recursive processor is acceptable for the quasistationary model of signal formation.

But the width of the AP algorithm’s parallel form for the recursive processor is significantly lower than that of the nonrecursive one: O  N  G  O( N 4  G ) .

This advantage of the recursive processor makes it possible to apply the solution to the problem of separating signals sn  k  for many more sources under conditions where computational resources are limited.

For a recursive processor to separate signals steadily, the object must allow the receivers of signals to be installed such that in the linear superposition of signals at the outputs of each of the receivers, the signal from a specific source is predominant [ 1 ].

The solution s functional F s expressed as 5. Model for a Regularization-Based Parallel Specialized Processor If the parameters of the mixing matrix H  ,I  or of the source signals s(k ) make the problem of signal separation ill-posed or if those parameters show expected uncertainty, then one should at once find a regularized, stable solution to (1) or its equivalent in the frequency domain.

The proposed model for a regularization-based specialized processor is based on the Tikhonov regularization [ 15 ].

Two conditions to the Tikhonov regularization are set in the processor model: the disparity minimization Hs  x  min , as in the least-squares technique (LST); and the minimization of the s solution norm, s  min , as in the Moore–Penrose pseudo-inverse of a matrix [ 16 ]. s contained in the processor provides the absolute minimum of the smoothing where   0 is the regularization parameter;  s  is the stabilizing functional; and H and x are approximate values of H and x for which

F s  Hs  x 2

 s ,

H  H   H and x  x   , where  and  H are the upper estimates of absolute measurement errors for the signals x and the mixing-matrix elements H .

The proposed model uses  s   s 2 as a stabilizing functional. For control purposes, it is more natural and convenient to present signals in time form, so we will write the smoothing functional for M = N and K = G as

M K 1 2 N M K 1 F s     xm  k ,I   xm k ,I     sn, k  .2 (3) m1 k0 nm1 k0

The signal xm  k ,I  in (3) derives from the separation results redistorted by the signal formation model; that is,

N xm k,I   sn, k  * hmn (k, l) ,

n1 where sn,  k, I are the regularized results of signal separation for the object’s nth node.

Under the conditions described above, the smoothing functional can be written as

M K 1 2 N M G1 F w     xm  k, I   xm k, I     wnm,  g ,I  ,2

m1 k 0 nm1 g0 an expression that is more suitable for the regularized computation of the elements wnm,  g, I  for the separating matrix w  g,I  , which sets the weights of the functional processor’s AFs.

The elements wnm,  g ,I  for the selected regularization parameter  are determined from the minimum condition of the smoothing functional F w , keeping in mind that this functional’s quadratic form is positively definite.

The elements wnm,  g ,I  are calculable, for instance, by solving the system of M  N  G equations written as

F (w) wnm  g, l

 0 relative to wnm,  g, I  , using the parallel algorithms for solving linear algebraic equations [ 2,3 ].

For the known (specified) errors  H and  , we propose calculating the regularization parameter as the root of the equation

Hs  x 2

   H s 2 / r,M ,N  , in which  is the parameter s , where   r,M ,N   1 is a scalable multiplier determined by the problem’s dimension ( M  N ) and by the measurement error of signal and channel parameters (the error depends, in particular, on the resolution r of analog-to-digital conversion).

With the regularization parameter  so obtained, the smoothness and disparity of the solution for s are acceptable for practical purposes.

Figure 2 shows the model of a regularization-based specialized processor.

The FP is a model that is inverse of the signal-formation model and that separates measured signals. This processor has a homogeneous structure and consists of AFs and AUs.

The computation of regularization parameter  and the adjustment of AFs, whose number is equal to M 2 , are run by the AP. The AP’s processing unit (PU) computes AF parameters with the least-squares technique through minimizing the smoothing functional F w .

The elements of the mixing matrix h  g,I  , which set the samples for the pulse responses of the signal-formation model’s channels, enter the inputs of the AP, and the AP generates a direct signalformation model.

Disparity evaluation units (DEUs) compute the disparity  m2 for each of the processor’s m channels. The units receive signals delayed by delay units (DUs), which serve to delay signals from the processor inputs and signals from the outputs of the direct signal-formation model.

It is advisable to use deterministic parallel optimization algorithms [ 17 ] designed for multicore processors to minimize the smoothing functional F w .

All the AFs operate in parallel independently of one another. This makes the proposed processor fast and reliable.

The processor model shown in figure 2 is generalized to obtain stable solutions for system (1). For that reason, the model is highly complicated. For practical applications, it can be significantly simplified by using prior information about the signal-formation model (such as the presence of reference inputs [ 18 ]) or by using simpler and parallel regularization algorithms [ 19 ].

AP’s processing unit

DUM

Adjusting processor

DEUM

DU1 DEU1 A1 dir AF1N AF11 AF11 AF1M A1 inv

Functional processor

(inverse object model) h11 h1N hM1

hMN

AFMN

AM dir AFM1

Direct object model

AFN1

AFNM

AN inv

6. Modeling Results

Figure 3 shows the modeling results for test signals separated by the nonrecursive parallel specialized processor with a multicore, GPU-based architecture.

The signal-formation model had three signal sources: the first two were triangular pulses with different frequencies and shapes while the third was a speech signal. The signal receivers used 8-bit ADCs with a sample rate of 12 kHz.

The figure 3 shows the initial signals (top), additive mixtures of signals in each of the receivers (middle), and extraction results for each signal (bottom).

The error of signal separation does not exceed 10%, a value acceptable for many engineering applications.

Time (ms)

V Time, sec V Time, sec V

V Time, sec V Time, sec V Time, sec a a b

Time, sec Time, sec Time, sec

The results of computational experiments shown in figure 4 for the example above show notably shorter task times (the Independent Component Analysis (ICA) [ 9 ] algorithm was used). Signal samples

7. Basic Conclusions

This paper proposed using models of highly efficient nonrecursive, recursive and regularization-based parallel specialized processors to solve the problem of signal separation.

Once adjusted, the processors can solve the problem within a period that does not depend on the number of signal sources—that is, the processors have a task time of TFP( N )  O(1) order.

These models are applicable where the parameters of the model-formation model are variable (quasistationary).

Regularization-based processors make the solution stable under conditions where the parameters of objects exhibit expected uncertainty when the inverse problem of signal separation becomes ill-posed.

The regular homogeneous structure of the functional processor can be conveniently implemented as an integrated circuit or a multicore-architecture computational system.

References

[1] Zasov V A 2013 Algorithms and Computational Devices for Separating and Restoring Signals in Multivariable Dynamic Systems (Samara: Samara State Transport University Press) p 233

[2] Gergel V P 2007 Theories and Applications of Parallel Computations (Moscow: IT Internet University: BINOM Knowledge Laboratory) p 423

[3] Demiyanovich Y K , Burova I G , Yevdokimova T O , Ivantsova O N and Miroshnichenko I D 2012 Parallel Algorithms : Development and Implementation (Moscow: IT Internet University: BINOM Knowledge Laboratory) p 344

[4] Patterson D A and Hennessy J L 2012 Computer Organization and Design (Saint Petersburg : Peter) p 784

[5] Vasin N N and Diyazitdinov R R 2016 A machine vision system for inspection of railway track Computer Optics 40 ( 3 ) 410 - 415 DOI: 10.18287/ 2412 -6179-2016-40-3- 410 -415

[6] Ifeachor E C and Jervis B W 2004 Digital Signal Processing: A Practical Approach (Moscow: Williams Publishing House) p 992

[7] Denisova A Y , Juravel Y N and Myasnikov V V 2016 Estimation of parameters of a linear spectral mixture for hyperspectral images with atmospheric distortions Computer Optics 40 ( 3 ) 380 - 387 DOI: 10.18287/ 2412 -6179-2016-40-3- 380 -387

[8] Mitropolskiy Y I 1985 Problems of Versatile to Custom Tools Ratio in Computational Systems Kibernetika i vychislitelnaya tekhnika 1 35 - 48

[9] Cichocki A and Amari Sh 2002 Adaptive blind signal and image processing: Learning algorithms and applications (New-York: John Wiley & Sons, Ltd) p 555

[10] Zasov V A and Romkin M V 2012 Parallel Computations for the Signal Separation Problem in Multidimensional Dynamic Systems Parallel Computations and Management Objectives . Proc. of the 6-th Int. Conf. (Moscow: Russian Academy of Science , Trapeznikov Institute of Control Science Press) 96 - 102

[11] Zasov V A and Romkin M V 2013 Parallel Computational Models for Solving the Problem of Signal Separation Vestnik transporta Povolzhiya 6 ( 42 ) 77 - 86

[12] Haykin S 2006 Neural Networks: A Comprehensive Foundation (Moscow: Williams Publishing House) p 1104

[13] Kravchenko V F 2007 Digital Signal and Image Processing in Radiophysical Applications (Moscow: Nauka, Fizmatlit) p 544

[14] Zasov V A and Nikonorov Ye N 2017 Modeling and Investigating the Stability of a Solution to the Inverse Problem of Signal Separation CEUR Workshop Proceedings 1904 78 - 84

[15] Tikhonov A N and Arsenin V Y 1986 Methods for Solving Ill-posed Problems: a Textbook for Universities (Moscow: Nauka , Fizmatlit) p 288

[16] Tyrtyshnikov E E 2007 Matrix Analysis and Linear Algebra (Moscow: Nauka, Fizmatlit) p 480

[17] Strongin R G , Gergel V P , Grishagin V A and Barkalov K A 2013 Parallel Computation in Global Optimization Problems (Moscow: Moscow State University Press) p 285

[18] Dzhigan V I 2013 Adaptive Signal Filtering: Theory and Algorithms (Moscow: Tekhnosfera) p 528

[19] Zhdanov A I and Sidorov Y V 2015 Parallel implementation of a randomized regularized Kaczmarz's algorithm Computer Optics 39 ( 4 ) 536 - 541 DOI: 10.18287/ 0134 -2452-2015-39-4- 536 -541