The paper develops a new channel estimation algorithm for use in broadband OFDM data transmission over non-ideal channels. The channel is described by Gauss-Markov AR model of a given order in state-space form. One of the existing solutions to channel estimation is based on the well-known Kalman filter (KF). Another approach is to use the information formulation of KF, the so-called Information filter (IF). To improve the numerical properties of the IF implementation, we propose a new numerically efficient channel estimation algorithm, the so-called combined array UD Information Filter (caUD-IF). The algebraic equivalence between IF and new caUD-IF is proved. The aspects of a parallel implementation of the suggested algorithm are also considered.
The data bits are first converted from serial stream to parallel stream depending on the number of sub-carriers named from 0 to . The Serial to Parallel converter takes the serial stream of input bits and outputs parallel streams. They are individually converted into the required digital modulation format (BPSK, QPSK, QAM, etc.).
Let us call this output . The conversion of parallel data into the digitally modulated data is usually achieved by a constellation mapper, which is essentially a look-up table (LUT). Once the data bits are converted to required modulation format, they are superimposed on the required orthogonal subcarriers for transmission through the channel. This is achieved by a series of parallel sinusoidal oscillators tuned to orthogonal frequencies . The resultant output from the parallel arms is summed up together to produce the OFDM signal. Figure 2 shows the entire architecture of a basic OFDM system with both transmitter and receiver.
The FFT/IFFT (Fast Fourier Transform / Inverse Fast Fourier Transform) length defines the number of total subcarriers present in the OFDM system. For example, an OFDM system with provides 64 subcarriers. In reality, not all the subcarriers are utilized for data transmission. Some subcarriers are reserved for pilot carriers (used for channel estimation/equalization and to combat magnitude and phase errors in the receiver) and some are left unused to act as a guard band.
In the simplest case, the channel is modeled as a simple AWGN (additive white Gaussian noise) channel. In a more realistic case, the channel is modeled as a first rank Markov process. In our research work, we model the channel by the Gauss–Markov AR model of rank written in the state space for each -th sub-channel allocated for the -th user.
Consider the Gauss–Markov AR model written in the state space
The following nomenclature (see table 1) gives an insight into variables and parameters used in the
channel model:
where
combined
state
vector
consists
of
sub-vectors
measurement vector; the process noise
random (Gaussian) sequences, i.e.,
ent of some random initial state
block (array) forms:
matrices in (
and . Let these noises be independ. Covariance matrices and have the following and . The system
Meaning channel (state of) channel transition channel noise input matrix channel noise observed signal channel pilot subcarriers channel observation noise channel noise covariance channel noise covariance
Our goal is to estimate unknown state vector , i.e., to calculate, at each discrete time instant , the one-step predicted estimate minimizing the MSE criterion , given the available measurements . The well-known Kalman filter algorithm [2, 3] is an ideal theoretical tool for solving the linear estimation problem. At each discrete-time moment KF yields to compute the linear least-square predicted estimate , of the state vector and the predicted error covariance matrix given the measurements .
, and also the filtered estimate
and the filtered error covariance matrix
(
There is no doubt that the main computational effort in Kalman filtering is spent in solving the Riccati equation. This effort is needed to calculate the Kalman gains. However, only the value of the predicted error covariance matrix is required for this purpose. A value of the filtered error covariance matrix is only used as an intermediate result on the way to compute the next value of .
Actually, it is not necessary to compute matrix explicitly. It is possible to compute the predicted error covariance matrix from one temporal epoch to the next, without going through the intermediate values of the filtered error covariance. This approach, and the algorithms for doing it, are called the combined measurement/time update or one-stage filters [3, 4]. The equations of the onestage conventional KF can be found in [3, p. 317]. Thus, a combined (one-stage) KF formulation requires less computation than a two-stage one.
The well-known Information filter (IF) is an alternative formulation of the Kalman filter, where the covariance matrix is replaced by its inverse matrix , which is called the information matrix. The information formulation is particularly useful when there is no prior information, i.e. the initial covariance matrix . In this case, the covariance formulation of the KF is not defined, while the information formulation is, and can start from .
Information filter does not use the same state vector representation as the conventional KF. Those that use the information matrix in the filter implementation use the information state . The implementation equations for the “straight” information filter (i.e., using Y) one can find in [2, p. 263]. This algorithm has the two-stage formulation, i.e. it consists of the time update step and the measurement update step. It is easy to reformulate it in a combined (one-stage) form.
Here we suggest using the information filter for solving the channel estimation problem. Let us
formulate the combined (one-stage) information algorithm (cIF) for OFDM channel estimation with
the above mathematical model (
For we implement the combined Information Filter to estimate the unobservable state vector from the noise-corrupted measurements
as it is shown in table 2.
,
,
Remark 1. At any discrete-time moment , one can easily obtain the predicted state estimate
, where
and
(
Remark 2. It is obvious that the bank of cIFs is ideal for the organization of a parallel computing scheme that can significantly accelerate the process of channel estimation.
Recently, different solutions of various channel estimation problems with the use of the Kalman
filtering technique were considered in [5–8]. However, it is well-known that the conventional KF
algorithm is numerically unstable due to the Riccati computational procedure (see, for instance, the
discussion in [9]), and the same is true for the information filter (
Since the invention of the KF in the 1960s, there has been a great interest in the development of numerically stable and efficient KF implementation methods [2]. In this paper, we study KF implementation algorithms of information type and propose the novel numerically efficient combined array UD information filter (caUD-IF) for solving the channel estimation problem. This new estimation algorithm was constructed for the first time. Although the UD-based information-type KF implementation was recently proposed in [10], it does not have a convenient array form for processing homogeneous large-scale data. 4. Numerically stable channel estimation algorithm based on the new combined array UD Information Filter The main idea of the KF array formulation is that the required quantities of the discrete filter are updated in an array form using the orthogonal matrix transforms. It means that numerically stable orthogonal transforms are used for updating the corresponding factors of the state error covariance matrix (and also state estimate) at each iteration step. In other words, orthogonal operators are applied to the pre-array (which contains the filter quantities available at the current step) to get the post-array in some special form. Then, the required updated filter quantities are simply read out from the post-array. This feature makes the array algorithms better suited to the parallel computations and to the very large scale integration (VLSI) implementations [11, 12]. The first information-type array filter was built in [13]. The covariance-type array square-root algorithms were constructed in [12].
Another important class of array algorithms is the UD KF methods. The special feature of it is that these algorithms are based on the modified Cholesky factorization of the state prediction error covariance matrix , where is a unit upper triangular matrix, is a diagonal matrix. The first UD filter was developed by G.J. Bierman; see [14] for more details. J.M. Jover and T. Kailath proposed in [15] the array form of UD based measurement update algorithm. Recently, a new extended array UD covariance filter (eUD-CF) was proposed in [16] and then apply to the channel estimation problem [17].
The modified Cholesky decomposition implies the factorization of a symmetric positive definite complex matrix in the form , where denotes a diagonal matrix and is an upper triangular matrix with 1’s on the main diagonal. We need to note that the Cholesky decomposition (and its modified version) exists and is unique when the matrix to be decomposed is positive definite; see [18]. If the matrix is a positive semi-definite, then the Cholesky decomposition still exists, however, it is not unique.
Concerning the Information formulation of the KF, the matrix factorization must perform for the
initial information matrix and the covariance matrices , . For the examined discrete-time
stochastic model (
Cholesky factors: I.3. Set:
II.1. For ,
construct a pair of the pre-arrays : II.2. Apply the MWGS transforms of the columns of with respect to the weighting matrix to obtain a pair of the post-arrays
: II.3. For
, construct a pair of the pre-arrays : II.4. Apply the MWGS transforms of the columns of with respect to the weighting matrix to obtain a pair of the post-arrays
: II.5. Compute information estimate:
For the UD-based KF implementations, the modified weighted Gram-Schmidt (MWGS) orthogonalization is used for the recursive update of the error covariance UD-factors. It was shown that the MWGS outperforms the usual Gram-Schmidt orthogonalization for accuracy; see [19].
In this paper, we construct the UD-based formulations of the newly developed combined array
Information Filter (caUD-IF) by using MWGS orthogonalization. More precisely, each iteration of the
new caUD-IF algorithm should have the following form: given a pair of the pre-arrays ,
compute a pair of the post-arrays by means of the MWGS orthogonalization, , i.e.,
(
Further, taking into account the block structure of the system matrices in (
The caUD-IF implementation scheme of main steps II.1–II.4 is shown in figure 3.
,
,
and
,
,
,
as follows (
):
(
It is very simple because of consists of only three steps: 1. Fill in the block pre-arrays with the input data. 2. Perform the MWGS-UD transforms.
3. Extract the required output data from the block post-arrays.
The designed eUD-CF estimator presented in table 2 has the main property to improve the accuracy and robustness of the computations for a finite-precision arithmetics. Now, we can formulate and prove our main result.
Statement 1. Algorithm caUD-IF is algebraically equivalent to the combined implementation of the
Information Filter given by equations (
Proof: First, we can show the algebraic equivalence between equations (
Next, we can show that equations (
It is obvious that expression (
Finally, there is no need to prove the equivalence of (
In this section, we consider a new channel estimation framework with concurrent caUD-IF algorithms. This general scheme (see figure 4) is composed of a bank of blocks with MWGS-UD transforms, each filled in with its own subsystem matrices , , , , . Each -th caUD-IF algorithm, , calculates its own information state estimate independently of the other filters. This framework can be naturally implemented on a set of parallel processors using the concept of the coarse-grained parallelism.
On the other hand, each caUD-IF block in the proposed channel estimation framework is based on the time-consuming MWGS-UD transform and its effective implementation is important to overall performance. Since MWGS-UD transform consists of two computationally intensive nested loops they can be parallelized using the concept of the fine-grained parallelism and OpenMP technology. In [17] we have implemented MWGS-UD algorithm using Armadillo library [20] and parallelized the inner loop using the #pragma omp parallel for directive with num_threads clause. Using this implementation we have conducted computational experiments with different number of threads 1, 2, 4 and 8 on the set of randomly generated test matrices of sizes 100x100, 200x100, 200x200, 500x500, 1000x500, 1000x1000, 1500x1000, 1500x1500, 2000x1500 and 2000x2000.
Numerical experiments were conducted at Scientific Research Laboratory of Mathematical Modeling, Ulyanovsk State Pedagogical University named after I. N. Ulyanov. Figure 5 illustrates the obtained results for each number of threads averaged over 20 runs.
The result of our work is twofold. Firstly, we have proposed the new numerically favored and convenient combined array UD Information Filter (caUD-IF algorithm). Secondly, we have demonstrated how network practitioners can efficiently use and implement this newest array algorithm based on MWGS transforms for coping with the difficulties caused by the numerical inefficiency of the standard Kalman Filter in attempting to use the latter for the OFDM multi-channel impulse response estimation. The advantages of the suggested solution are as follows:
The channel estimating results are robust against the round-off errors.
The computations do not contain the most time-consuming square-root operation.
The compact and regular orthogonal array form of algorithm poses the best option for parallel computations in the Orthogonal Frequency-Division Multiple Access (OFDMA) multi-subchannel organization.
The first three authors thank the support of Russian Foundation for Basic Research and the government of the Ulyanovsk region of the Russian Federation within the scope of project 18-47-730001 p_a.