IP Core of On-line ICA Algorithm

Song-Ju Kim ¹⁾, Hideaki Terai ²⁾, and Ken Umeno ^1,2)
National Institute of Information and Communications Technology ¹⁾
ChaosWare, Inc. ²⁾

Abstract :

We propose IP core of on-line ICA algorithm. The on-line ICA algorithm can decompose input signals into statistically independent components. We demonstrate that we can recover original chaotic signals from linearly mixed chaotic signals without any information of mixing. We implement the ICA and chaos generator modules to Xilinx Virtex-II FPGA on the HERON ready-to-go systems provided by Hunt engineering. The total gate size of all modules is 527,656, and the maximum frequency is 20.820MHz. This IP can be used for blind source separation (BSS) in MIMO type receivers of communication systems.

INTRODUCTION

Independent component analysis (ICA) for@blind@source separation (BSS)@has recently attracted much attention in various fields, such as biomedical signal processing (EEG/MEG signals), audio, acoustics, and image enhancement systems, and wireless@telecommunication systems [1]. The ICA algorithms can decompose observed signals into statistically independent components. Therefore, we can recover original source signals s(t) from observed signals x(t) = A s(t) if the original source signals are mutually independent (A is an unknown mixing matrix).

In this paper, we use chaotic signals generated by Chebyshev map as original source signals because these signals are mutually independent. Recently, we originally found that chaotic signals recovered by ICA are very useful as spreading sequences in code division multiple access (CDMA) [2]. The signal-to-interference ratio (SIR) of the recovered signals is much larger than those of the original signals although the waveforms of the recovered signals are almost the same as those of the original signals [3].

Many on-line ICA algorithms have been proposed so far. We focus on the equivariant adaptive separation via independence (EASI) algorithm proposed by Cardoso et al. [4] because the EASI algorithm has simple parallel structure, and is suitable for hardware implementation [5,6]. In fact, we implement the EASI module, chaos generator modules, and other modules needed for BSS experiment in 16-bit fixed-point arithmetic. We show the FPGA implementation results of all modules and of the EASI module only.

EASI ALGORITHM

In ICA algorithms, the basic goal is to find the separating matrix W, such that y(t) = W x(t), without knowing the mixing matrix A. Here, x(t) = A s(t) are observed signals or mixed signals, and y(t) is a scaled and permuted version of the original source signals s(t). That is, the equation WA = D P holds, where D is a diagonal matrix and P is a permutation matrix.

Cardoso et al. proposed the following EASI algorithm [4].
 
 (1)
 (2)

use g(y) = -tanh(y) and the learning rate   = 0.001953125 (= 2^-9).

As original source signals, we use chaotic signals generated by Chebyshev map. Each signal is defined as follows:

  (3)

Here,  is the q-th order Chebyshev polynomial defined by . It is known that this Chebyshev map is ergodic and it has the ergodic invariant measure,

 (4)

and it satisfies the orthogonal relation,

 
 (5)

where  is the Kronecker delta function.

FPGA IMPLEMENTATION

As original source signals, the chaos generator implemented in FPGA generates two chaotic signals, where j-th source signal is produced by the (j+1)-th order Chebyshev polynomial. Thus, we have two original chaotic signals which have the mapping forms,

 (6)

We use fixed-point (16-bit) arithmetic and the bit-harnessing method [7] for this implementation.

The bit-harnessing method is the one of methods to produce chaotic signals in fixed-point arithmetic. At each time step t, a random bit (Gold sequence) is added to the LSB of chaotic signals after exclusive ORed (XORed) with *18* in order to avoid a short period. As a result, each chaotic signal is generated by following equations,

 (7)

Here, T1 = s, T0 =1, and g1, g2, g2, g3, g4 are random bits from Gold sequences which have period

 

Figure 1: HERON ready-to-go systems provided by Hunt engineering.

These two chaotic signals are linearly mixed in the mixing module according to the mixing matrix A. The mixing matrix A is given by GUI in PC which is connected with the USB port shown in figure 1. These mixed signals are transmitted through D/A converter (16-bit), and received through A/D converter (12-bit) without any information loss. This is because the transmitted data always have negligible bits (4-bit). Then, the EASI module separates the mixed signals into original chaotic signals without any information of the matrix A. These recovered signals and mixed signals are written to FIFO, and we can obtain these four signals, namely recovered signal y1 and y2, and mixed signal x1 and x2, through USB port connected with FIFO.

The mixed signals and recovered signals are shown in figure 2 and figure 3, respectively. In each figure, the upper windows show the time series of mixed (recovered) signal 1 and its return plot, and the bottom windows also show the time series of mixed (recovered) signal 2 and its return plot. In return plots shown in middle windows in fig. 2, the vertical axis denotes x (t+1), and the horizontal axis denotes x (t). We cannot find any form in these return plots.

On the other hand, we can find T2and T3forms of equation (6) in return plots in fig. 3. We can confirm the successful recovery of original chaotic signals since these forms are characteristics the original chaotic signal must have. However, these T2 and T3 forms may be slightly unclear. The FIFO we used has 32-bit x 512 memory. So, only 8-bit of each signal are written to FIFO at each time step. As a result, we discarded negligible bits (4-bit) and lower 4-bit of each 16-bit signal. We can confirm T2 and T3 forms more clearly if we do not discard the lower 4-bit.



Figure 2: Time series (leftmost windows) and the return plots (middle windows) of the mixed signal 1 (upper windows) and 2 (bottom windows).

 

Figure 3: Time series (leftmost windows) and the return plots (middle windows) of the recovered signal 1 (upper windows) and 2 (bottom windows).

IMPLEMENTATION RESULT

We implemented modules needed for BSS experiment to Xilinx Virtex-II V3000 FPGA using ISE 9.1 design tool. The implemented modules are 1) EASI module (2x2), 2) chaos generators (2nd order and 3rd order), 3) mixing module, 4) FIFO (32-bit x 512), 5) interface between PC and FPGA, and 6) D/A converter interface. Source codes are written by VHDL. We check our implementation using ModelSim XE III simulator. The simplified block diagrams are shown in figure 4-(a) and figure 4-(b).

Table 1 shows the device utilization summary and the maximum frequency (MHz). The columns@denote 1) the design name, 2) the total number 4 input look-up-tables (LUTs), 3) the utilization of the digital signal processing (DSP) blocks included in FPGA (the DSP block contains 18x18 multiplier, adder, and multiplexer),  4) the total equivalent gate count for the design, and 5) the maximum frequency (MHz), respectively. The design eAllf means all modules needed for BSS experiment.

Table 1: Implementation result (Virtex-II).

Design	LUT 28,672	DSP 96	Gate Size	Max. Freq.
All	3,694 35	527,656	20.820

RESULTS OF THE EASI MODULE ONLY

Table 2 and Table 3 show the implementation results when we implement the EASI module only to Virtex-IV (SX25) and to Virtex-V (SX95T) FPGAs, respectively. Here, the 2x2 denotes the design in which the number of original signals is 2 and the number of recovered signals is also 2. Due to the limitation of logic cells (LUTs) in the device Virtex-IV, we cannot implement the 5x5 design as shown in table 2. If we use larger FPGA, which has more LUTs, the 5x5 design can also be implemented. In fact, we can implement the EASI module up to the 7x7 design in Virtex-V FPGA.

Table 2: Implementation results (Virtex-IV).

Design	LUT 20,480	DSP 128	Gate Size	Max. Freq.
2x2	1,992	17	18,864	27.386
3x3	5,422	48	49,788	26.105
4x4	11,180	102	103,812	24.496

Table 3: Implementation results (Virtex-V).

Design	LUT 58,880	DSP 640	Gate Size	Max. Freq.
2x2	1,869	17	20,385	33.813
3x3	5,293	48	55,742	32.526
4x4	10,981	102	116,797	30.455
5x5	20,456	185	212,444	29.742
6x6	33,179	303	346,899	28.185
7x7	51,434	462	529,690	28.678

CONCLUSIONS
 
We proposed IP core of on-line ICA algorithm which can recover original chaotic signals from linearly mixed chaotic signals.  We implemented the 2x2 EASI module, chaos generator modules, and interface modules needed for BSS experiment to Xilinx Virtex-II FPGA on the HERON ready-to-go systems provided by Hunt engineering. The total gate size is 527,656, and the maximum frequency is 20.820MHz. We can implement the EASI module only to Virtex-V (SX95T) FPGA up to the 7x7 design.

 

Figure 4-(a): The simplified block diagram.



Figure 4-(b): The EASI module.

ACKNOWLEDGMENTS

This work was financially supported by NEDO Grant for Industrial Technology Research (FY2005-2).

REFERENCES

[1] K. Umeno, gChaos and codes in communications systemsh, Proceedings of IPSJ Symposium f05,  vol.19, pp.312-316, 2005.
[2] R. Takahashi, S. J. Kim, and K. Umeno, gSuper amplification of SNR with an independent component analysis in chaos CDMAh, Technical Report of IEICE, vol.106, no.413, NLP2006-102, pp.1-6, 2006.
[3] R. Takahashi, S. J. Kim, and K. Umeno, gAnalysis of bit error rate using the chaos spreading sequence with an independent component analysis filterh, Technical Report of IEICE, vol.106, no.573, NLP2006-142, pp.1-6, 2007.
[4] J. -F. Cardoso, and B. H. Laheld, gEquivariant adaptive source separationh, IEEE Trans. on Signal Processing, vol.44, pp.3017-3030, 1996.
[5] S. J. Kim, K. Umeno, and R. Takahashi, gRecovery of chaotic signals using on-line ICA algorithmh, Proceedings of NOLTAf07, pp.192-195, 2007.
[6] S. J. Kim, K. Umeno, and R. Takahashi, gFPGA implementation of EASI algorithmh, to be published in IEICE Electronics Express, vol.4, no.22, 2007.
[7]@K. Umeno, H. Lin, and S. Shih, gFIPS 140-1 passed digital chaos generatorsh, Proceedings of IEEE ISPACS f02, 2002.