Digital filter device, digital filtering method, and storage medium having digital filter program stored thereon

Abstract

In order to reduce the power consumed when using FFT processing and filtering in the frequency domain together, a digital filter device according to the present invention is provided with: a first filtering means for performing a first fast Fourier transformation using a first data sorting process, first filtering in the frequency domain, a first inverse fast Fourier transformation using a second data sorting process, and overlap removal on a first input block including overlapped data; a second filtering means for performing a second fast Fourier transformation, which simultaneously processes all data in a second input block including overlapped data, second filtering in the frequency domain, a second inverse fast Fourier transformation, which simultaneously processes all received filtered data, and overlap removal; and a data selection means for selecting either the first filtering means or the second filtering means, wherein the operation of the filtering means that is not selected by the data selection means is interrupted.

Claims

1. A digital filter device comprising: a first digital filtering unit comprising: a first overlap addition unit which generates a first overlap block where a first input block comprising time-domain consecutive NM pieces of input data (where N is a positive integer and M is a positive integer equal to or less than N) is given additional consecutive M pieces of data immediately preceding the first input block; a first fast Fourier transform unit which transforms, through a fast Fourier transform process involving a first data sorting process, the first overlap block into a first frequency-domain block being in a frequency domain; a first filter computation unit which performs a first filtering process on the first frequency-domain block; a first inverse fast Fourier transform unit which transforms, through an inverse fast Fourier transform process involving a second data sorting process, the first processed block which underwent the first filtering process into a first time-domain block; and a first overlap removal unit which removes a total of M pieces of data from both ends of a time axis of the first time-domain block and generates first output data; a second digital filtering unit comprising: a second overlap addition unit which generates a second overlap block where a second input block comprising time-domain consecutive QP pieces of input data (where Q is a positive integer and P is a positive integer equal to or less than Q) is given additional consecutive P pieces of data immediately preceding the second input block; a second fast Fourier transform unit which simultaneously inputs all the second input block included in the second overlap block and transforms, through a fast Fourier transform process, the block into a second frequency-domain block being in a frequency domain; a second filter computation unit which performs a second filtering process on the second frequency-domain block; a second inverse fast Fourier transform unit which simultaneously inputs all processed data included in the second processed block which underwent the second filtering process and transforms, through an inverse fast Fourier transform process, the processed data into a second time-domain block; and a second overlap removal unit which removes a total of P pieces of data from both ends of a time axis of the second time-domain block and generates second output data; and a data selection unit which selects either the first output data or the second output data in accordance with a selection signal selecting a filtering process to be performed, wherein the second digital filtering unit stops operating when the first output data is selected by the data selection unit, and wherein the first digital filtering unit stops operating when the second output data is selected by the data selection unit, wherein a first impulse response length of the first filtering process is longer than a second impulse response length of the second filtering process, wherein the M is determined based on the first impulse response length, and wherein the P is determined based on the second impulse response length.

2. The digital filter device according to claim 1, wherein the N is greater than the Q, and wherein the M is greater than the P.

3. The digital filter device according to claim 2, wherein the first data sorting process is a process carried out to rearrange a plurality of pieces of the input data included in the first overlap block in an order of data pieces to be subjected to computation in the first fast Fourier transform unit, and wherein the second data sorting process is a process carried out to rearrange a plurality of pieces of processed data included in the first processed block in an order of data pieces to be subjected to computation in the first inverse fast Fourier transform unit.

4. The digital filter device according to claim 3, wherein the selection signal selects the first filtering process if an impulse response length of an applicable filtering process to be applied to input data is greater than the P, and wherein the selection signal selects the second filtering process if an impulse response length of the applicable filtering process is equal to or less than the P.

5. The digital filter device according to claim 1, wherein the first data sorting process is a process carried out to rearrange a plurality of pieces of the input data included in the first overlap block in an order of data pieces to be subjected to computation in the first fast Fourier transform unit, and wherein the second data sorting process is a process carried out to rearrange a plurality of pieces of processed data included in the first processed block in an order of data pieces to be subjected to computation in the first inverse fast Fourier transform unit.

6. The digital filter device according to claim 5, wherein the selection signal selects the first filtering process if an impulse response length of an applicable filtering process to be applied to input data is greater than the P, and wherein the selection signal selects the second filtering process if an impulse response length of the applicable filtering process is equal to or less than the P.

7. The digital filter device according to claim 1, wherein the selection signal selects the first filtering process if an impulse response length of an applicable filtering process to be applied to input data is greater than the P, and wherein the selection signal selects the second filtering process if an impulse response length of the applicable filtering process is equal to or less than the P.

8. The digital filter device according to claim 2, wherein the selection signal selects the first filtering process if an impulse response length of an applicable filtering process to be applied to input data is greater than the P, and wherein the selection signal selects the second filtering process if an impulse response length of the applicable filtering process is equal to or less than the P.

9. A digital filter device comprising: a first digital filtering unit comprising: a first overlap addition unit which generates a first overlap block where a first input block comprising time-domain consecutive NM pieces of input data (where N is a positive integer and M is a positive integer equal to or less than N) is given additional consecutive M pieces of data immediately preceding the first input block; a first fast Fourier transform unit which transforms, through a fast Fourier transform process involving a first data sorting process, the first overlap block into a first frequency-domain block being in a frequency domain; a first filter computation unit which performs a first filtering process on the first frequency-domain block; a first inverse fast Fourier transform unit which transforms, through an inverse fast Fourier transform process involving a second data sorting process, the first processed block which underwent the first filtering process into a first time-domain block; and a first overlap removal unit which removes a total of M pieces of data from both ends of a time axis of the first time-domain block and generates first output data; a second digital filtering unit comprising: a second overlap addition unit which generates a second overlap block where a second input block comprising time-domain consecutive QP pieces of input data (where Q is a positive integer and P is a positive integer equal to or less than Q) is given additional consecutive P pieces of data immediately preceding the second input block; a second fast Fourier transform unit which simultaneously inputs all the second input block included in the second overlap block and transforms, through a fast Fourier transform process, the block into a second frequency-domain block being in a frequency domain; a second filter computation unit which performs a second filtering process on the second frequency-domain block; a second inverse fast Fourier transform unit which simultaneously inputs all processed data included in the second processed block which underwent the second filtering process and transforms, through an inverse fast Fourier transform process, the processed data into a second time-domain block; and a second overlap removal unit which removes a total of P pieces of data from both ends of a time axis of the second time-domain block and generates second output data; and a data selection unit which selects either the first output data or the second output data in accordance with a selection signal selecting a filtering process to be performed, wherein the second digital filtering unit stops operating when the first output data is selected by the data selection unit, and wherein the first digital filtering unit stops operating when the second output data is selected by the data selection unit, wherein the selection signal selects the first filtering process if an impulse response length of an applicable filtering process to be applied to input data is greater than the P, and wherein the selection signal selects the second filtering process if an impulse response length of the applicable filtering process is equal to or less than the P.

10. The digital filter device according to claim 9, wherein the first data sorting process is a process carried out to rearrange a plurality of pieces of the input data included in the first overlap block in an order of data pieces to be subjected to computation in the first fast Fourier transform unit, and wherein the second data sorting process is a process carried out to rearrange a plurality of pieces of processed data included in the first processed block in an order of data pieces to be subjected to computation in the first inverse fast Fourier transform unit.

11. A digital filtering method comprising: selecting, in accordance with a selection signal selecting a filtering process to be performed, either: a first digital filtering process performed to: generate a first overlap block where a first input block comprising time-domain consecutive NM pieces of input data (where N is a positive integer and M is a positive integer equal to or less than N) is given additional consecutive M pieces of data immediately preceding the first input block; transform, through a fast Fourier transform process involving a first data sorting process, the first overlap block into a first frequency-domain block being in a frequency domain; perform a first filtering process on the first frequency-domain block; transform, through an inverse fast Fourier transform process involving a second data sorting process, the first processed block which underwent the first filtering process into a first time-domain block; and remove a total of M pieces of data from both ends of a time axis of the first time-domain block and generate first output data; or a second digital filtering process performed to: generate a second overlap block where a second input block comprising time-domain consecutive QP pieces of input data (where Q is a positive integer and P is a positive integer equal to or less than Q) is given additional consecutive P pieces of data immediately preceding the second input block; simultaneously input all the second input block included in the second overlap block and transform, through a fast Fourier transform process, the block into a second frequency-domain block being in a frequency domain; perform a second filtering process on the second frequency-domain block; simultaneously input all processed data included in the second processed block which underwent the second filtering process and transform, through an inverse fast Fourier transform process, the processed data into a second time-domain block; and remove a total of P pieces of data from both ends of a time axis of the second time-domain block and generate second output data; stopping the first digital filtering process when the second digital filtering process is selected; and stopping the second digital filtering process when the first digital filtering process is selected, wherein a first impulse response length of the first filtering process is longer than a second impulse response length of the second filtering process, wherein the M is determined based on the first impulse response length, and wherein the P is determined based on the second impulse response length.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a block diagram illustrating a configuration of a digital filter circuit according to an exemplary embodiment of the present invention.

(2) FIG. 2 is a block diagram illustrating a configuration of an FFT circuit according to an exemplary embodiment of the present invention.

(3) FIG. 3 is a diagram illustrating datasets arranged in a sequential order according to an exemplary embodiment of the present invention.

(4) FIG. 4 is a diagram illustrating datasets arranged in a bit reverse order according to an exemplary embodiment of the present invention.

(5) FIG. 5 is a block diagram illustrating an example configuration of a data sorting processing unit according to an exemplary embodiment of the present invention.

(6) FIG. 6 is a block diagram illustrating a configuration of an FFT circuit according to an exemplary embodiment of the present invention.

(7) FIG. 7 is a diagram illustrating a data flow for a 16-point FFT involving two-stage butterfly computations.

(8) FIG. 8 is a diagram illustrating a data flow for a 64-point FFT involving two-stage butterfly computations.

(9) FIG. 9 is a block diagram illustrating a configuration of an FFT circuit.

(10) FIG. 10 is an operation diagram illustrating example operations of a digital filter circuit based on an overlap FDE method.

DESCRIPTION OF EMBODIMENTS

(11) Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 1 is a block diagram illustrating an example configuration of a digital filter circuit 400 according to an exemplary embodiment of the present invention.

(12) The digital filter circuit 400 includes a first digital filter circuit 200, a second digital filter circuit 300, and a data selection unit 410. Thus, the digital filter circuit 400 is structured with two digital filter circuits 200 and 300 being connected in parallel.

(13) Input data inputted to the digital filter circuit 400 is subjected to filtering through either the first digital filter circuit 200 or the second digital filter circuit 300, based on a selection signal 411 given by an upper-level circuit (not shown) such as a CPU.

(14) According to the selection signal 411, the data selection unit 410 selects data filtered through either the first digital filter circuit 200 or the second digital filter circuit 300 and outputs the selected data as output data.

(15) The first and second digital filter circuits 200 and 300 perform filtering, such as FDE, based on the overlap method.

(16) The first digital filter circuit 200 includes an overlap addition circuit 210, an FFT circuit 211, a filter computation circuit 212, an IFFT circuit 213, and an overlap removal circuit 214.

(17) The overlap addition circuit 210 sequentially generates input blocks each of which is composed of consecutive N pieces of data (where N is a positive integer) from the input data representing time-domain input signals and outputs the blocks to the FFT circuit 211. During this operation, the overlap addition circuit 210 overlaps each input block with the immediately preceding block at its end by M pieces of data (where M is a positive integer). Overlap as used herein means that the first predetermined X pieces of data of a block (where X is a positive integer) are handled as the last X pieces of data in the immediately preceding block and that the X pieces of data overlapping between two blocks are included in each of the two blocks. The overlap addition circuit 210 generates an overlap block, which consists of consecutive N pieces of data including M pieces of overlapped data. Note that the overlap addition circuit 210 is structured by a 2-port memory, for example.

(18) The FFT circuit 211 performs an N-point fast Fourier transform (FFT) on an overlap block outputted from the overlap addition circuit 210 to transform the block into a frequency-domain signal. Then, the FFT circuit 211 outputs to the filter computation circuit 212 a frequency-domain block, which consists of N pieces of frequency-domain data.

(19) The filter computation circuit 212 performs filtering on the frequency-domain block outputted from the FFT circuit 211, and then outputs the processed block to the IFFT circuit 213. For example, if the digital filter circuit 200 performs equalization of signal distortion, i.e., FDE, in a communication channel, the filter computation circuit 212 can be composed of a complex number multiplier.

(20) The IFFT circuit 213 performs an N-point inverse fast Fourier transform (IFFT) on the processed block outputted from the filter computation circuit 212 to re-transform the block into a time-domain signal. Then, the IFFT circuit 213 outputs to the overlap removal circuit 214 the time-domain block, which consists of N pieces of time-domain data.

(21) The overlap removal circuit 214 removes a total of M pieces of data from both ends of a time axis of each time-domain block outputted from the IFFT circuit 213, takes out only the middle portion of the time-domain block, and outputs the portion as output data.

(22) The overlap value M may be a predetermined fixed value. In this case, the overlap addition circuit 210 and the overlap removal circuit 214 can be configured to be suited to the overlap value M. Alternatively, an overlap value M may be given by an upper-level circuit, such as a CPU (not shown), to be defined as an overlap value setting during operations. As described above, an overlap value M may be a predetermined fixed value or an externally defined value; provided, however, an overlap value M must be smaller than a block size N for FFT. In the present exemplary embodiment, the values are set to: M=16 and N=64.

(23) Similarly, the second digital filter circuit 300 includes an overlap addition circuit 310, an FFT circuit 311, a filter computation circuit 312, an IFFT circuit 313, and an overlap removal circuit 314.

(24) The overlap addition circuit 310 sequentially generates input blocks each of which is composed of consecutive Q pieces of data (where Q is a positive integer) from the input data representing time-domain input signals and outputs the blocks to the FFT circuit 311. During this operation, the overlap addition circuit 310 overlaps each block with the immediately preceding block at its end by P pieces of data (where P is a positive integer). The overlap addition circuit 310 generates an overlap block, which consists of consecutive Q pieces of data including P pieces of overlapped data.

(25) The FFT circuit 311 performs a Q-point fast Fourier transform (FFT) on an overlap block outputted from the overlap addition circuit 310 to transform the block into a frequency-domain signal. Then, the FFT circuit 311 outputs to the filter computation circuit 312 a frequency-domain block, which consists of Q pieces of frequency-domain data.

(26) The filter computation circuit 312 performs filtering on the frequency-domain block outputted from the FFT circuit 311, and then outputs the processed block to the IFFT circuit 313.

(27) The IFFT circuit 313 performs a Q-point inverse fast Fourier transform (IFFT) on the processed block outputted from the filter computation circuit 312 to re-transform the block into a time-domain signal. Then, the IFFT circuit 313 outputs to the overlap removal circuit 314 a time-domain block, which consists of Q pieces of time-domain data.

(28) The overlap removal circuit 314 removes a total of P pieces of data from both ends of a time axis of each time-domain block outputted from the IFFT circuit 313, takes out only the middle portion of the time-domain block, and outputs the portion as output data.

(29) An overlap value Q may also be a predetermined fixed value or may be given by an upper-level circuit, such as a CPU, to be defined during operations. In either case an overlap value must be smaller than a block size Q for FFT. In addition, the present exemplary embodiment assumes that the block size Q for FFT in the second digital filter circuit 300 is smaller than the block size N for FFT in the first digital filter circuit 200. Specifically, the values are set to: P=4 and Q=16.

(30) A configuration of the FFT circuit 211, which is a component of the first digital filter circuit 200, will now be described.

(31) FIG. 2 is a block diagram illustrating an example configuration of the FFT circuit 211 according to an exemplary embodiment of the present invention.

(32) The FFT circuit 211 processes a 64-point FFT decomposed into two-stage radix-8 butterfly processes based on a pipelined circuit system, according to the data flow 500 shown in FIG. 8. When time-domain data x(n) (where n=0, 1, . . . , 63) is inputted, the FFT circuit 211 performs a Fourier transform through an FFT process on the data to generate and output frequency-domain signals X(k) (k=0, 1, . . . , 63).

(33) In order to implement the 64-point FFT process shown in the data flow in FIG. 8, i.e., all the processes performed on 8 sets of data each including 8 pieces of data, by using 8 separate circuits respectively for each set, huge circuitry would be needed. It is therefore assumed that the FFT circuit 211 performs a 64-point FFT process in 8-data parallel. In this case, the FFT circuit 211 performs a Fourier transform through an FFT process on inputted time-domain data x(n) to generate and output frequency-domain signals X(k). During the processing, input data x(n), which consists of 64 pieces of data in total, is inputted in the order shown in FIG. 3 in units of 8 pieces of data at a time during a period of 8 cycles. Note that the numbers 0 to 63 shown as content of the table in FIG. 3 represent n in x(n).

(34) Specifically, in the 1st cycle, 8 pieces of data x(0), x(1), . . . , x(7) constituting a dataset P1 are inputted. Next, in the 2nd cycle, 8 pieces of data x(8), x(9), . . . , x(15) constituting a dataset P2 are inputted. Similarly, in each of the 3rd to 8th cycles, the pieces of data respectively constituting datasets P3 to P8 are inputted.

(35) Likewise, the output data X(k) consisting of 64 pieces of data is outputted in the order shown in FIG. 3 in units of 8 pieces of data at a time during a period of 8 cycles. Note that the numbers 0 to 63 shown as content of the table in FIG. 3 represent k in X(k).

(36) Specifically, in the 1st cycle, 8 pieces of data X(0), X(1), . . . , X(7) constituting a dataset P1 are outputted. In the 2nd cycle, 8 pieces of data X(8), X(9), . . . , X(15) constituting a dataset P2 are outputted. Similarly, in each of the 3rd to 8th cycles, the pieces of data respectively constituting datasets P3 to P8 are outputted.

(37) The FFT circuit 211 includes a first data sorting processing unit 11, a first butterfly computation processing unit 21, a second data sorting processing unit 12, a twiddle multiplication processing unit 31, a second butterfly computation processing unit 22, and a third data sorting processing unit 13. The FFT circuit 211 performs a first data sorting process, a first butterfly computation process, a second data sorting process, a twiddle multiplication process, a second butterfly computation process, and a third data sorting process in a pipelined manner.

(38) The first and second data sorting processing units 11 and 12 are buffer circuits for rearranging data. The first and second data sorting processing units 11 and 12 respectively rearrange a data sequence both before and after the first butterfly computation processing unit 21 based on data dependence in the FFT processing algorithm.

(39) Likewise, the third data sorting processing unit 13 is a buffer circuit for rearranging data. That is, the third data sorting processing unit 13 rearranges a data sequence subsequent to the second butterfly computation processing unit 22 based on data dependence in the FFT processing algorithm. In addition to the above data rearrangement, the third data sorting processing unit 13 makes a data rearrangement aiming at outputting X(k) and X(N-k) for any k in the FFT circuit 211 within a time lag as few as one cycle or less.

(40) Specifically, the first data sorting processing unit 11 rearranges the input data x(n), which has been inputted in a sequential order shown in FIG. 3, in a bit reverse order shown in FIG. 4, in which order the data will be inputted to the first butterfly computation processing unit 21.

(41) The bit reverse order shown in FIG. 4 corresponds to the datasets inputted to the radix-8 butterfly process 502 in the 1st stage, as illustrated in the data flow diagram in FIG. 8. Specifically, in the 1st cycle, 8 pieces of data x(0), x(8), . . . , x(56) constituting a dataset P1 are set. Next, in the 2nd cycle, 8 pieces of data x(1), x(9), . . . , x(57) constituting a dataset P2 are set. Similarly, in each of the 3rd to 8th cycles, the pieces of data respectively constituting datasets P3 to P8 are set.

(42) The terms sequential order and bit reverse order are now explained in detail. The term sequential order refers to an order of eight datasets P1, P2, P3, P4, P5, P6, P7, and P8 as shown in FIG. 3. A dataset Ps (where s represents an ordinal number of a processing cycle; s=1, . . . , 8) consists of 8 pieces of data ps(0) to ps(7) sequentially arranged, and ps(i) is expressed as:
ps(i)=8(s1)+i

(43) Further, the individual datasets are arranged in the order of P1, P2, P3, P4, P5, P6, P7, and P8 with the progress of processing cycles. In other words, a sequential order is an arrangement of is pieces of data, where s datasets each consisting of i pieces of data are created and arranged in the order of cycle number.

(44) The term bit reverse order refers to an order of eight datasets Q1, Q2, Q3, Q4, Q5, Q6, Q7, and Q8 as shown in FIG. 4. A dataset Qs consists of eight pieces of data qs(0) to qs(7), and qs(i) is expressed as:
qs(i)=(s1)+8i

(45) Further, the individual datasets are arranged in the order of Q1, Q2, Q3, Q4, Q5, Q6, Q7, and Q8 with the progress of processing cycles. In other words, a bit reverse order is a rearrangement of is pieces of data that have been inputted in a sequential order, where the pieces of data are arranged in the order of cycle in units of s and datasets each consisting of i pieces of data of the same cycle are arranged in the order of data.

(46) As seen above, once individual datasets are arranged in a sequential order, individual datasets arranged in a bit reverse order are uniquely identified. The ith data piece in a dataset Qs (where s=1, . . . , 8) in a bit reverse order corresponds to the sth data piece in the ith cycle in a sequential order. That is:
Qs(i)=Pi(s)

(47) Thus, Qs(i) and Pi(s) are correlated such that, with respect to pieces of data constituting a dataset, the orders are exchanged between cycle progress and data position. Accordingly, if pieces of data that have been inputted in a bit reverse order are rearranged in the bit reverse order, the resulting data is arranged in a sequential order.

(48) The lines ps(i) in FIG. 3 and the eight lines qs(i) in FIG. 4 each represent the data to be inputted to the subsequent stage in the ith data piece. Each of eight numbers included in a dataset, which is specifically n in x(n), is an identifier used to identify any one of FFT points.

(49) Note that the sequential and bit reverse orders are not limited to the ones exemplified in FIGS. 3 and 4. In other words, the individual datasets in a sequential order may be created by arranging pieces of data in sequence depending on the number of FFT points, the number of cycles, and the number of data pieces processed in parallel as described above. Further, the individual datasets in a bit reverse order may be created by exchanging the orders between cycle progress and data position on the pieces of data that have been inputted in a sequential order as described above.

(50) The first butterfly computation processing unit 21 is a butterfly circuit which handles the first one butterfly computation process 502 (the first butterfly computation process) of the two radix-8 butterfly computation processes performed in the data flow 500 shown in FIG. 8. The first butterfly computation processing unit 21 outputs results of the butterfly computation as data y(n) (where n=0, 1, . . . , 63) in the sequential order shown in FIG. 3.

(51) The second data sorting processing unit 12 rearranges the data y(n), which has been outputted from the first butterfly computation processing unit 21 in the sequential order, in the bit reverse order as shown in FIG. 4 to be inputted to the second butterfly computation processing unit 22.

(52) The twiddle multiplication processing unit 31, which corresponds to the twiddle multiplication process 504 in the data flow 500 shown in FIG. 8, is a circuit handling rotation of a complex number on the complex plane for FFT processing after the first butterfly computation. Note that the no data rearrangement occurs in the twiddle multiplication process.

(53) The second butterfly computation processing unit 22 is a butterfly circuit which handles the second radix-8 butterfly process 503 shown in the data flow diagram in FIG. 8. The second butterfly computation processing unit 22 performs the butterfly computation on the data y(n) (where n=0, 1, . . . , 63), which has been inputted in the bit reverse order after the twiddle multiplication, and outputs the results X(k) (where n=0, 1, . . . , 63) in the same bit reverse order.

(54) The third data sorting processing unit 13 rearranges the data X(k), which has been outputted from the second butterfly computation processing unit 22 in the bit reverse order, in the sequential order shown in FIG. 3.

(55) The data sorting processing units achieve the respective data sorting processes in the sequential order in FIG. 3 and the bit reverse order in FIG. 4 by temporarily storing the inputted data, and controlling selection and output of the data. The following describes the data sorting processing units by way of specific examples.

(56) The first, second, and third data sorting processing units 11, 12, and 13 each can be implemented by, for example, a data sorting processing unit 100 shown in FIG. 5.

(57) The data sorting processing unit 100 inputs the input information 103, namely datasets D1 to D8 each consisting of eight pieces of data, in the first-in order in a FIFO (First In First Out) butter, and writes and stores the datasets into data storage locations 101a to 101h. Specifically, the datasets D1 to D8 are stored in the data storage locations 101a to 101h, respectively.

(58) The data sorting processing unit 100 then outputs the stored data in the first-out order in a FIFO buffer. Specifically, the data sorting processing unit 100 reads every eight pieces of data constituting a dataset from data read locations 102a to 102h and outputs eight datasets D1 to D8 as the output information 104. Thus, the pieces of data contained in datasets D1 to D8, which have been arranged in the order of cycle, are rearranged in the order of data location and grouped into datasets D1 to D8.

(59) As described above, in the FFT device 211, the first, second, and third data sorting processing units 11, 12, and 13 perform three sorting processes in total respectively in accordance with the sequential order in FIG. 3 and the bit reverse order in FIG. 4. This is because the FFT circuit 211 performs a 64-point FFT in 8-data parallel requiring 8 cycles for the FFT, which means data needs to be rearranged across cycles.

(60) The IFFT circuit 213 can be implemented in a configuration similar to the FFT circuit 211.

(61) Configuration of the FFT circuit 311, a component of the second digital filter circuit 300, will now be described.

(62) FIG. 6 is a block diagram illustrating an example configuration of the FFT circuit 311 according to an exemplary embodiment of the present invention.

(63) The FFT circuit 311 processes a 16-point FFT decomposed into two-stage radix-4 butterfly processes based on a pipelined circuit system, according to the data flow 600 shown in FIG. 7. The FFT circuit 311 inputs time-domain data x(n) (where n=0, 1, . . . , 15) and generates and outputs frequency-domain signals X(k) (where k=0, 1, . . . , 15), which have been Fourier-transformed through an FFT process.

(64) The 16-point FFT process in the data flow 600 shown in FIG. 7 requires a smaller amount of computation than the 64-point FFT process in the data flow 500 shown in FIG. 8. For this reason, even if a 16-point FFT, i.e., all the processes on 16 pieces of data, is implemented altogether by a single circuit, the circuit size is small. It is thus assumed here that the FFT circuit 311 performs a 16-point FFT process in 16-data parallel to achieve all the processes in the data flow 600 in a single circuit. The FFT circuit 311 in the present exemplary embodiment inputs time-domain data x(n) and generates and outputs frequency-domain signals X(k), which have been Fourier-transformed through an FFT process. During this operation, all the 16 pieces of data are inputted as input data x(n) within a period of 1 cycle.

(65) Likewise, all the 16 pieces of data are outputted as output data X(k) within a period of 1 cycle.

(66) The FFT circuit 311 includes a first butterfly computation processing unit 51, a twiddle multiplication processing unit 61, and a second butterfly computation processing unit 52. The FFT device 311 performs a first butterfly computation process, a twiddle multiplication process, and a second butterfly computation process in a pipelined manner.

(67) The first butterfly computation processing unit 21 is a butterfly circuit which performs the first one butterfly computation process 602 (the first butterfly computation process) of the two radix-4 butterfly computation processes performed in the data flow 600 shown in FIG. 7. The first butterfly computation processing unit 21 outputs results of the butterfly computation as data y(n) (where n=0, 1, . . . , 63) in parallel.

(68) The twiddle multiplication processing unit 61, which corresponds to the twiddle multiplication process 604 in the data flow 600 shown in FIG. 7, is a circuit handling rotation of a complex number on the complex plane for FFT computation after the first butterfly computation. No data rearrangement occurs in the twiddle multiplication process.

(69) The second butterfly computation processing unit 52 is a butterfly circuit which performs the second radix-4 butterfly process 603 in the data flow diagram shown in FIG. 7. The second butterfly computation processing unit 22 performs the butterfly computation on the data y(n) (where n=0, 1, . . . , 63), which has been inputted in parallel after the butterfly computation, and outputs the results X(k) (where n=0, 1, . . . , 63) in parallel in the same manner.

(70) As described above, the FFT circuit 311 eliminates the need for a data sorting processing unit that is required in the FFT circuit 211. This is because the FFT circuit 311 performs a 16-point FFT in 16-data parallel to complete the FFT process in one cycle, which means no data rearrangement across cycles is needed. Note that a data sorting processing unit corresponds, for example, to the data sorting process 601 in the example shown in FIG. 7 and to the data sorting process 501 in the example shown in FIG. 8.

(71) The IFFT circuit 313 can be implemented in a configuration similar to the FFT circuit 311.

(72) As described above, the FFT circuit 311 eliminates the need for a data sorting processing unit, and is thus smaller in circuit size than the FFT circuit 211, which requires a data sorting processing unit. Consequently, an FFT process performed by the FFT circuit 311 consumes less power due to the unnecessary data sorting processing unit than an FFT process performed by the FFT circuit 211.

(73) Thus, when the number of points of an FFT process is small, power consumption for an FFT process can be reduced by using the FFT process performed by the FFT circuit 311. In contrast, when the number of points of an FFT is too many to handle in parallel and may be problematic in terms of circuit size, the FFT circuit 211, which is an FFT circuit involving a data sorting process, can be used.

(74) In this case, all the output data can be obtained within one cycle due to the effect of data sorting processing.

Operations of Exemplary Embodiment

(75) The overlap value M for the first digital filter circuit 200 is 16. In other words, the first digital filter circuit 200 can perform filtering of an up to 16-tap long impulse response.

(76) On the other hand, the overlap value Q for the second digital filter circuit 300 is 4. In other words, the second digital filter circuit 300 can perform filtering of an up to 4-tap long impulse response.

(77) The digital filter circuit 400 uses the second digital filter circuit 300 to perform filtering if the impulse response length of filtering is 4 taps or less, whereas it uses the first digital filter circuit 200 to perform filtering if the impulse response length of filtering is 5 taps or more.

(78) Specifically, the digital filter circuit 400 operates as follows depending on the impulse response length of the filtering performed by the digital filter circuit 400:

(79) 1) In cases where the impulse response length is 4 taps or less

(80) A selection signal 411, which instructs to select the second digital filter circuit 300, is given by an upper-level circuit (not shown), such as a CPU. The second digital filter circuit 300, which has been selected by the selection signal 411, performs filtering.

(81) Meanwhile, the first digital filter circuit 200, which is not selected by the selection signal 411, suspends filtering. During the suspension, the first digital filter circuit 200 can reduce power consumption by using clock gating, power gating, or the like to stop circuit operations.

(82) In accordance with the selection signal 411, the data selection unit 410 outputs the data, as output data, outputted from the second digital filter circuit 300.

(83) 2) In cases where the impulse response length is 5 taps or more

(84) A selection signal 411, which instructs to select the first digital filter circuit 200, is given by an upper-level circuit. The first digital filter circuit 200, which has been selected by the selection signal 411, performs filtering. The second digital filter circuit 300, which is not selected by the selection signal 411, suspends filtering. During the suspension, the second digital filter circuit 300 can reduce power consumption by using clock gating, power gating, or the like to stop circuit operations.

(85) In accordance with the selection signal 411, the data selection unit 410 outputs the data, as output data, outputted from the first digital filter circuit 200.

Effect of Exemplary Embodiments

(86) As described above, the digital filter circuit 400 according to the present exemplary embodiment is configured such that the first digital filter circuit 200, which can accept a longer impulse response, and the second digital filter circuit 300, which can accept a shorter impulse response, are connected to each other in parallel. In operation, the second digital filter circuit 300 consumes less power compared with the first digital filter circuit 200. It can be determined which circuit should be selected, the first digital filter circuit 200 or the second digital filter circuit 300, depending on the impulse response length of the target filtering to be performed.

(87) The first digital filter circuit 200 is used when the impulse response length of the target filtering is greater than a predetermined value, whereas the second digital filter circuit 300 is used when the impulse response length of the target filtering is equal to or less than a predetermined value. Therefore, power consumption for filtering can be reduced when the impulse response length is equal to or less than a predetermined value. When the impulse response length is greater than a predetermined value, power consumption is greater because a data sorting process is involved, but all the output data can be outputted within one cycle notwithstanding parallel processing.

(88) Note that the present exemplary embodiment assumes that the overlap value M for the first digital filter circuit 200 is 16, the FFT block size N is 64, the overlap value P for the second digital filter circuit 300 is 4, and the FFT block size Q is 16, but values are not limited thereto. The overlap value and FFT block size for the second digital filter circuit 300 may be set to any values as far as an FFT process can be performed in one cycle. The overlap value and FFT block size for the first digital filter circuit 200 may be set to any values as far as they are greater than the overlap value and FFT block size, respectively, for the second digital filter circuit 300.

(89) In the present exemplary embodiment, it is envisaged that individual processes, such as FFT, IFFT, and filtering, are performed by individual circuits or other components. However, the processes according to the respective exemplary embodiments may be executed by a computer included in a predetermined device, such as a digital signal processor (DSP), in accordance with software that is provided thereon. That is, computer programs responsible for the respective processes are loaded and executed by a DSP (not shown).

(90) For example, the data sorting process may be performed through the use of a program. That is, a DSP and memory may be used to perform the data sorting process by causing a program to control reading and writing data from and to the memory. In addition, in the present exemplary embodiment, FFT processes may be performed under program control.

(91) As described above, programs may be used to perform the same processes as those described in the above exemplary embodiments.

(92) Note that the above processing programs may be stored in a non-transitory medium, including but not limited to, a semiconductor storage device such as ROM (read only memory), RAM (random access memory), or flash memory, or an optical disk, a magnetic disk, or a magneto-optical disk.

(93) While the invention has been particularly shown and described with reference to exemplary embodiments thereof, the invention is not limited to these embodiments. It will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the claims.

(94) This application is based upon and claims the benefit of priority from Japanese patent application No. 2013-152705, filed on Jul. 23, 2013, the disclosure of which is incorporated herein in its entirety by reference.

REFERENCE SIGNS LIST

(95) 11 First data sorting processing unit 12 Second data sorting processing unit 13 Third data sorting processing unit 21 First butterfly computation processing unit 22 Second butterfly computation processing unit 31 Twiddle multiplication processing unit 51 First butterfly computation processing unit 52 Second butterfly computation processing unit 61 Twiddle multiplication processing unit 100 Data sorting processing unit 101a to 101h Data storage location 102a to 102h Data read location 103 Inputted information 104 Outputted information 200 First digital filter circuit 210 Overlap addition circuit 211 FFT circuit 212 Filter computation circuit 213 IFFT circuit 214 Overlap removal circuit 300 Second digital filter circuit 310 Overlap addition circuit 311 FFT circuit 312 Filter computation circuit 313 IFFT circuit 314 Overlap removal circuit 400 Digital filter circuit 410 Data selection unit 411 Selection signal 500 Data flow 501 Data sorting process 502, 503 Butterfly computation process 504 Twiddle multiplication process 505a-505h Partial data flow 600 Data flow 601 Data sorting process 602, 603 Butterfly computation process 604 Twiddle multiplication process 700 Digital filter circuit 710 Overlap addition circuit 711 FFT circuit 712 Filter computation circuit 713 IFFT circuit 714 Overlap removal circuit