International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
April 2013, pp.
ISSN: 2088-8708
Design of Real Time Walsh Transform for Processing of Multiple Digital Signals Zulfikar*.
Shuja A.
Abbasi**.
Alamoud** * Departement of Electrical Engineering.
Syiah Kuala University ** Departement of Electrical Engineering.
King Saud University Article Info
ABSTRACT
Article history:
This paper presents the design and implementation of multiple digital signals processing using real-time Walsh transforms.
The design of real time Walsh transform is done in such a way that it starts producing outputs instantly even before all input data have entered the system.
The system consists of Walsh Transform circuit, several Digital Signal Processing (DSP) circuits, and an inverse Walsh transform circuit.
The real time Walsh and inverse Walsh transforms are also designed to produce right results for any possible combinations of input data.
DSP blocksare able to perform addition, subtraction, and dyadic convolution process of Walsh coefficients of more than one digital signals.
Comparisons to the previous methods are briefly It was found that the design of real time Walsh transform structure has better performance than many of the previously reported results in the Received Dec 22, 2012 Revised Feb 27, 2013 Accepted Mar 6, 2013 Keyword:
Fast Hadamard transform Walsh transform Real time Walsh transform Inverse Walsh transform Dyadic convolution Copyright A 2013 Institute of Advanced Engineering and Science.
All rights reserved.
Corresponding Author:
Zulfikar.
Departement of Electrical Engineering.
Syiah Kuala University.
Darussalam.
Banda Aceh 23111.
Indonesia, phone: 62 651 7554336 Email: zulfikarsafrina@yahoo.
INTRODUCTION
The area ofDigital Signal Processing (DSP) is currently a well established area of research.
The techniques for analysis, synthesis and processing of two or more digital signals have been established.
However, some of them required certain tasks of DSP which are difficult to be performed in time domain and hence the information has to be transformed to other domains.
Frequency domain is the most popularly used domain for the tasks which cannot be, or are difficult to be done in the time domain.
Fourier transform is the most widely used technique for transforming information from time domain to frequency domain.
This is a very useful tool in DSP.
In the group of 2m transform length, the Fourier transform is better described as the Walsh transform.
The Walsh transform (WT) may be obtained using the Walsh functions.
It is also well known that the Walsh functions may be evaluated using Rademacher functions .
We preferred this technique since the Rademacher functions may be conveniently realized using a binary counter .
, .
However, it should be noted that it is not always necessary to use the above technique and the Walsh transform (WT) may be performed just by using adders and subtractors .
This idea interested many scientists and engineers for hardware realization of the Walsh transform.
This method is known as Fast Hadamard Transform (FHT) since it is derived from Hadamard matrices .
Distributed Arithmetic (DA) and Systolic Architecture (SA) are two types of structures that have been proposed in order to further simplify the FHT .
Amira et al .
proposed an improved structure and claimed better performance on the basis of an elaborate comparative study.
They also reported the results of power analysis.
Later on.
Meher and Patra .
introduced a very simple technique based on combination Journal homepage: http://iaesjournal.
com/online/index.
php/IJECE A ISSN:2088-8708 of unified algorithm .
and Rademacher functions.
This technique is based upon the use of simple 4 points FHTs arranged in such a way that the higher points FHTs .
, 16, .
may be obtained easily.
The technique was also implemented on FPGAs.
Superior results were claimed.
It is found that the original Walsh functions, defined in terms of products of Rademacher functions can be used to transform the information into frequency domain faster than FHT and thus leads to speed up the DSP process.
Therefore, the original Walsh transform technique based on Walsh functions and Rademacher functions is proposed and the results of hardware realization on FPGAs are presented.
Moreover, a good design of Walsh transform is able to produce output immediately.
Further, we also designed and implemented the Inverse Walsh Transform (IWT) for conversion from frequency domain to time domain.
FPGA based hardware realization has been used to process two digital signals using the Walsh transform and the Inverse Walsh transform techniques.
The results of hardware realization like the occupied area and delays have been compared with the results reported by other workers.
The paper is organized as follows.
In section 2, the basic theory of Walsh transform and signal processing is presented.
Section 3 deals with the proposed structure of real time Walsh transform and inverse Walsh transform.
Section 4 deals with control signals of the design system.
The hardware implementation on FPGAs is presented in section 5.
Section 6 deals with analysis and discussions of the proposed Walsh and inverse Walsh transforms.
Conclusions are presented in Section 7.
WALSH TRANSFORM AND SIGNAL PROCESSING
Definition of Walsh functions based upon derivation from Rademacher functions is found to be more appropriate for hardware implementation.
The Rademacher functions are defined as follows .
A ( n A 1, x ) A Sgn .
in 2A 2 n x ), n = 0,1,2,A0 C x A 1 Where.
A A0, x A A 1 and the signum function Sgn.
is defined by:
EA 1 ,
Sgn A y A A E
EA 1 ,
yA0 Walsh functions are defined in terms of product of Rademacher functions as follows .
A ( n , t ) A Ei AuA ( i A 1, t ) Ayn , n i Ea .
n A Eu2n iA0 A digital signal x.
of length N may be represented as a Walsh series which is given by .
N A1
x ( t ) A Eu AnA An , t A .
nA0 The Walsh coefficients An are evaluated as .
An A 1 N A1 Eu x nA An , t A N nA0 If the signals h.
, p.
and q.
are defined as the summation, subtraction and multiplication of two signals given by:
) A x.
) A g .
) .
) A x.
) A g .
) .
IJECE Vol.
No.
April 2013: 197Ae206
IJECE
ISSN: 2088-8708
) A x.
) g .
) .
Where the function x.
has the Walsh series expansion as in .
and g.
has the following Walsh series N A1 ) A Eu B nA An , t A n A0 Then the Walsh expansion of h.
, p.
and q.
are given by .
N A1
h At A A Eu C nA An , t A .
N A1
p At A A Eu D nA An , t A .
N A1
q At A A Eu E nA An , t A .
nA0 Where the expansion coefficients of Cn .
Dn and En are computed as .
, .
, .
Cn A An A Bn Dn A An A Bn E n A Eu AnEI m Bm m A0 Where EI refers to dyadic addition (XOR) and the last expression is the well known dyadic convolution.
DESIGN OF COMPLETE SET OF REAL TIME WALSH AND INVERSE WALSH
TRANSFORMS
Figure 1 shows complete set of circuits which perform signal processing of multiple digital signals.
The design consists of Walsh transform blocks, a DSP block, one Inverse Walsh Transform block and a dividing block.
Input digital signals x1.
, x2.
etc are passed into the system serially.
Similarly, the output signal h.
is also produced in series.
Figure 1.
Walsh and Inverse Walsh for signal processing Number of Walsh transform blocks used depends on number of input signals.
Figure 2 views basic design of the Walsh transform.
The design consists of a negative circuit, a circuit to produce (N-.
orders of Walsh functions, a block of N-1 number of 2 to 1 multiplexers.
N data buffers.
N accumulators, and N output Design of Real Time Walsh Transform for Processing of Multiple Digital Signals (Zulfika.
A ISSN:2088-8708 Figure 2.
Design of Walsh transform for transform length of N Input data .
of X are passed serially.
Walsh circuit is used to select the suitable data X or Ae X and pass it through the multiplexers.
The outputs of the multiplexers will accumulate at the accumulators and they will form the output transformed coefficients (AAo.
Figure 3 views circuit realization of the proposed Walsh transform for N=4 and input word lengths WI=4 .
sed to represent input data X).
The output transformed coefficients (AAo.
have to be represented in 6 bits .
utput word lengths WO=.
Figure 3.
Circuit realization of WT for N=4 and WI=4 The proposed WT is able to start producing output results instantly even before all input data have been given to the system.
For example, if input data of N=4 are X{-6, -2, 3, .
WT (Walsh coefficient.
of these data can be calculated as follows.
A0 = (-.
(-.
3 7 = 2 A1 = (-.
Ae (-.
3 Ae 7 = -8 A2 = (-.
(-.
Ae 3 Ae 7 = -18 A3 = (-.
Ae (-.
Ae 3 7 = 0 When input data X have not completely entered into the system, say only -6 and -2 have just passed, the output Walsh coefficients are:
A0 = (-.
(-.
0 0 = -8
A1 = (-.
Ae (-.
0 Ae 0 = -4 A2 = (-.
(-.
Ae 0 Ae 0 = -8 A3 = (-.
Ae (-.
Ae 0 0 = -4 IJECE Vol.
No.
April 2013: 197Ae206
IJECE
ISSN: 2088-8708
Those coefficients are true by assuming the rest of input data are all zero.
For transform lengths N, the coefficients will be produced N times.
Therefore, we call the design of Walsh transform as real-time Walsh transform.
The Walsh circuit realization for N=4 is shown in Figure 4.
It is designed to produce complement of 2nd, 3rd and 4th orders of Walsh functions based on Hadamard ordering.
For higher transform lengths, obviously it will require more XOR gates in order to perform multiplications of Rademacher functions.
Figure 4.
Walsh Circuit realization for N=4 The inverse Walsh transform may be obtained using most of the blocks designed for Walsh The complete block diagram is shown in Figure 5.
The circuit requires a set of N negative circuits to receive N parallel inputs, (N-.
number of 2 to 1 multiplexers.
N data buffers, (N-.
adders, and an output Figure 6 views circuit realization of the proposed Inverse Walsh transform for N=4 and input word lengths WI=6 .
sed to represent input coefficient CAo.
The output data (H) are represented in 4 bits .
utput word lengths WO=.
This (WO<WI) is due to dividing by factor of N=4.
Figure 5.
Design of inverse Walsh transform for transform length of N Figure 6.
Circuit realization of IWT for N=4 and WI=6 The process flow of inverse Walsh transform is similar to Walsh transform, all input data either C or AeC are selected to pass the multiplexers based on outputs of Walsh circuits.
These data will then be added one by one using the adders sequentially.
In determining coefficients AAos and BAos, and to avoid floating numbers, factor 1/N in Eq.
6 is ignored for the time being.
This factor will be implemented towards the end of the process in dividing block.
The circuits to perform this job are installed together with the Inverse Walsh transform circuit.
For addition and subtraction, the outputs of inverse Walsh transform have to be divided by N.
Meanwhile, for multiplication process, the outputs should be divided by factor of N2 .
CIRCUIT CONTROL SIGNALS
The operation of the proposed WT and IWT has to be controlled carefully in order to gather optimum results.
There are three basic control signals as follows:
Clock.
it is used to synchronize buffers and other storage elements.
Design of Real Time Walsh Transform for Processing of Multiple Digital Signals (Zulfika.
TEnter
ISSN:2088-8708
Reset.
it is used to reset .
all buffers and storage elements.
Before input data are fed to the circuit, signal Reset normally goes high.
Enter.
it is used to control input data.
How fast the data enters the system, is based upon this signal.
This signal has to be high for at least twice of clock period.
C 2 TClock Therefore, this signal is non periodic.
Figure 7 shows relation between signal Enter and Clock.
Figure 7.
Relation between Clock and signal Enter Figure 8.
Relation between signal Enter and input data
(X)
The availability of this signal is based on the availability of input data.
The signal arrives just after the input data (X) available at input port of the circuits.
Figure 8 shows relation between signal Enter and input data.
IMPLEMENTATION RESULTS
In order to show step by step process of the design on chip, the implementation will be performed and displayed for every step (Walsh transform.
DSP.
Inverse Walsh transfor.
and limited to two input signals only.
Three types of signal processing steps viz.
addition, subtraction and multiplication will be demonstrated for transform length N=4 and word lengths of input signals WI=4 based on natural or Hadamard ordering.
The implementations are targeted to Virtex chips from Xilinx.
Figure 9 and 10 show Walsh transforms of input signals x.
and g.
The transformed coefficients A and B are represented in word lengths WO=6 bits.
Figure 9.
Walsh transform of signal x.
Figure 10.
Walsh transform of signal g.
Output coefficients A and B are produced in real-time by the system.
Here, the coefficients are produced four times.
The first coefficients are available just after two cycles of signal Enter.
The second and the third series of coefficients are available after three and four cycles of signal Enter respectively.
The last coefficients will be available after signal Enter goes high five times.
Since the Walsh coefficients for AAos and BAos are available, we may now perform addition, subtraction and multiplication of signal x.
and g.
As mentioned earlier in section II, the addition and subtraction can be performed by simply adding and subtracting both coefficients AAos and BAos as follow .
IJECE Vol.
No.
April 2013: 197Ae206
IJECE
ISSN: 2088-8708
Addition process:
C0 = A0 B0 = 2 12 = 14
C1 = A1 B1 = -8 10 = 2
C2 = A2 B2 = -18 12 = -6
C3 = A3 B3 = 0 (-.
= -10
Subtraction process:
D0 = A0 - B0 = 2 - 12 = -10
D1 = A1 - B1 = -8 - 10 = -18
D2 = A2 - B2 = -18 - 12 = -30
D3 = A3 - B3 = 0 Ae (-.
= 10 The coefficients CAos and DAos are then transformed back into the time domain by using IWT proposed in Figure 6.
The results are shown in Figs.
11 and 12 for addition and subtraction of signal x.
and g.
Figure 11.
Inverse Walsh transform of addition coefficients AAos and BAos Figure 12.
Inverse Walsh transform of subtraction coefficients AAos and BAos For multiplication process, we need to perform dyadic convolution between coefficients AAos and BAos in order to find Coefficients EAos .
Manual calculations for this process based on Equation 16 are listed E0 = A0*B0 A1*B1 A2*B2 A3*B3 = 2*12 (-.
*10 (-.
*12 0*(-.
= -272
E1 = A1*B0 A0*B1 A3*B2 A2*B3
= -8*12 2*10 0*12 (-.
*(-.
= 104
E2 = A2*B0 A3*B1 A0*B2 A1*B3
= -18*12 0*10 2*12 (-.
*(-.
= -112
E3 = A3*B0 A2*B1 A1*B2 A0*B3
= 0*12 (-.
*10 (-.
*12 2*(-.
= -296
The FPGA implementation of this convolution is shown in Figure 13.
These coefficients are then passed to the inverse Walsh circuit and the result signal h.
is shown in Figure 14.
Design of Real Time Walsh Transform for Processing of Multiple Digital Signals (Zulfika.
A ISSN:2088-8708 Figure 13.
Dyadic convolution between coefficients AAos and BAos Figure 14.
Inverse Walsh transform of dyadic convolution between coefficients AAos and BAos To summarize the implementation of the proposed design, all the signals and coefficients are listed in Table 1.
Table 1.
List of all signals and coefficients Signal/ Coefficients x.
ANALYSIS AND DISCUSSIONS In the design of the proposed real-time Walsh transform and its inverse, special care is needed for the selection of word lengths representing input signals, coefficients and the output signal.
This requires detailed analysis of each step of the processes.
The implementation results shown in the previous section clearly indicate that the word lengths for different coefficients and output signals vary.
The design is implemented on Xilinx Virtex-4 chip .
c4vlx15-12-sf.
Various results are shown in Table 2.
Table 2.
Comparison of area, speed and word lengths for Walsh transform, inverse Walsh and dyadic Process Slice Walsh Transform Inverse Walsh Transform Inverse Walsh Transform^ Dyadic Convolution Note:
LUTs Flip Flops Speed (MH.
Inverse Walsh transform of addition or subtraction of coefficients AAos and BAos ^ Inverse Walsh transform of dyadic convolution of coefficients AAos and BAos In order to make a comparison with the results reported by other works, we implemented real-time Walsh transform for N=4, 8, 16 and WI=8 on Xilinx Virtex-IIP and Virtex-4.
The results of comparison are presented in Table 3.
IJECE Vol.
No.
April 2013: 197Ae206
IJECE
ISSN: 2088-8708
Table 3.
Comparison the proposed Walsh transform to previous methods for various Xilinx Virtex series (WI=.
FPGA Platform Virtex-IIP Virtex-4 Proposed Slice Speed (MH.
Structure .
Slice Speed (MH.
Structure .
Slice Speed (MH.
It may be seen that the proposed structure for the Walsh Transform is superior to the others except for N=4, in which case, the area occupied is a bit higher than the one proposed in .
We also implemented the Inverse Walsh transform for N=4, 8, 16 and WO=8 on Xilinx Virtex-IIP and Virtex-4 based on Hadamard ordering.
Table 4 shows the results of these implementations.
Table 4.
Implementation of Inverse Walsh transform to various Xilinx Virtex series (WO=.
FPGA Platform Virtex-IIP Virtex-4 Inverse Walsh Transform Slices Speed (MH.
CONCLUSION A complete set of real-time Walsh and Inverse Walsh transforms for signal processing has been proposed and demonstrated on various Xilinx Virtex chips.
The design consists of real-time Walsh transforms, inverse Walsh transform.
DSP block and dividing block.
Real-time Walsh transform is controlled by independent, random signal Enter.
The availability of this signal is based on the availability of data in input ports of the design system.
It requires N 1 cycles of signal Enter for completing the process of transforming input data to the frequency domain.
On the basis of implementation results, it is concluded that the proposed Walsh transform structure is superior to many of the structures reported in literature.
The Inverse Walsh transform, requires more area but is faster than the Walsh transform itself.
The results clearly show that the DSP (Dyadic convolutio.
for multiplication process requires 7 times larger area than other processes.
When combining the proposed realtime Walsh transform.
DSP block and inverse Walsh transform into a single system, the designed inverse Walsh transform is fully controlled by Clock, instead of signal Enter.
ACKNOWLEDGEMENTS
The authors gratefully acknowledge the financial support from National Plan for Science.
Technology and Innovation (NPST).
Saudi Arabia under project no.
09-ELE854-02.
REFERENCES