Store 
| Products & Services | Solutions | Academia | Support | User Community | Company |
 |
Download Product Updates | | |  |
Get Pricing | | | |
Trial Software |
| Documentation → Video and Image Processing Blockset |
| Products & Services | Solutions | Academia | Support | User Community | Company |
|
Download Product Updates | | | |
Get Pricing | | | |
Trial Software |
| Documentation → Video and Image Processing Blockset |
| Contents | Index |
| Learn more about Video and Image Processing Blockset |
Transforms
The 2-D FFT block computes the fast Fourier transform (FFT) of a two-dimensional M-by-N input matrix in two steps. First it computes the one-dimensional FFT along one dimension (row or column). Then it computes the FFT of the output of the first step along the other dimension (column or row). The dimensions of the input matrix, M and N, must be powers of two. To work with other input sizes, use the Pad block to pad or truncate these dimensions to powers of two.
The output of the 2-D FFT block is equivalent to the MATLAB® fft2 function:
y = fft2(A) % Equivalent MATLAB code
Computing the FFT of each dimension of the input matrix is equivalent to calculating the two-dimensional discrete Fourier transform (DFT), which is defined by the following equation:
where
and
.
| Port | Description | Supported Data Types | Complex Values Supported |
|---|---|---|---|
Input | Vector or matrix of intensity values |
| Yes |
Output | 2-D FFT of the input | Same as input port | Yes |
Ifthe input signal data type is floating point, the data type of the output signal uses the same floating-point data type. Otherwise, the output can be any fixed-point data type.
The block computes all the possible trigonometric values of the twiddle factor
where K is the
greater value of either M or N and
.
The block stores these values in a table and retrieves them during
simulation. You can optimize the table of trigonometric values for
memory or speed using the Optimize table for parameter.
This parameter varies the number of table entries as summarized in
the following table.
Optimize Table for Parameter Setting | Number of Table Entries for N-Point FFT |
|---|---|
Speed | 3N/4-floating point N - fixed point |
Memory | N/4 -floating point Not supported for fixed point |
Use the Output in bit-reversed order parameter to specify the ordering of the column elements of the output as either linear or bit-reversed. If you select the Output in bit-reversed order check box, the row and column elements are output in bit-reversed order. Thus, the mth row element appears at the kth position, where k is the bit reversed value of m. Also, the nth column element appears at the lth position, where l is the bit reversed value of n. If you clear the Output in bit-reversed order check box, the channel elements are output in linear order.
Note The 2D-FFT block calculates its output in bit-reversed order. Linearly ordering the 2D-FFT block output requires an extra bit-reversal operation. Thus, in many situations, you can increase the speed of the 2D-FFT block by selecting the Output in bit-reversed order check box. |
For more information ordering of the output, see Bit-Reversed Order. The 2-D FFT block bit-reverses the order of both the columns and the rows.
Which algorithms the block uses depends on whether the block input is floating-point or fixed-point, real or complex. The choice of algorithms is also affected by whether you want the output in linear or bit-reversed order. Based on these specifications, the block can use any of the following algorithms:
Bit-reversal operation
Double-signal algorithm
Half-length algorithm
Radix-2 decimation-in-time (DIT) algorithm
Radix-2 decimation-in-frequency (DIF) algorithm
Floating-Point Signals
Complexity of Input | Output Ordering | Algorithms Used for FFT Computation |
|---|---|---|
Complex | Linear | Bit-reversal operation and radix-2 DIT |
Complex | Bit-reversed | Radix-2 DIF |
Real | Linear | Bit-reversal operation and radix-2 DIT in conjunction with the half-length and double-signal algorithms |
Real | Bit-reversed | Radix-2 DIF in conjunction with the half-length and double-signal algorithms |
Fixed-Point Signals
Complexity of Input | Output Ordering | Algorithms Used for FFT Computation |
|---|---|---|
Real or complex | Linear | Bit-reversal operation and radix-2 DIT |
Real or complex | Bit-reversed | Radix-2 DIF |
The following diagrams show the data types used in the 2-D FFT block for fixed-point signals. You can set the sine table, accumulator, product output, and output data types displayed in the diagrams in the 2-D FFT dialog box as discussed in Dialog Box.
The block first casts inputs to the output data type and stores them in the output buffer. Each butterfly stage then processes signals in the accumulator data type, with the final output of the butterfly being cast back into the output data type. The block multiplies twiddle factor values before each butterfly stage in a decimation-in-time FFT and after each butterfly stage in a decimation-in-frequency FFT.
The output of the multiplier appears in the accumulator data type because both of the inputs to the multiplier are complex. For details on the complex multiplication performed, refer to Multiplication Data Types in the Signal Processing Blockset documentation.
Two numbers are bit-reversed values of each other when the binary representation of one is the mirror image of the binary representation of the other. For example, in a three-bit system, one and four are bit-reversed values of each other because the three-bit binary representation of one, 001, is the mirror image of the three-bit binary representation of four, 100. The following diagram shows the row indices in linear order. To put them in bit-reversed order
Translate the indices into their binary representation with the minimum number of bits. In this example, the minimum number of bits is three because the binary representation of 7 is 111.
Find the mirror image of each binary entry, and write it beside the original binary representation.
Translate the indices back to their decimal representation.
The row indices now appear in bit-reversed order.
If, on the 2-D FFT block parameters dialog box, you select the Output in bit-reversed order check box, the block bit-reverses the order of both the columns and the rows. The next diagram illustrates the linear and bit-reversed outputs of the 2-D FFT block. The output values are the same, but they appear in different order.
The Main pane of the 2-D FFT dialog box appears as shown in the following figure.
Optimize the table of twiddle factor values for Speed or Memory. This parameter must be set to Speed for fixed-point signals.
Designate the order of the output channel elements relative to the ordering of the input elements. When selected, the output channel elements appear in bit-reversed order relative to the input ordering. Otherwise, the output column elements display in linear order relative to the input ordering. Linearly ordering the output requires extra data sorting manipulation. For more information, see Bit-Reversed Order.
When you select this parameter, the output of each butterfly of the FFT is divided by two.
The Fixed-point pane of the 2-D FFT dialog box appears as shown in the following figure.
Select the rounding mode for fixed-point operations. The sine table values do not obey this parameter; instead, they always round to Nearest.
Select the overflow mode for fixed-point operations. The sine table values do not obey this parameter; instead they are always saturated.
Choose how to specify the word length of the values of the sine table. The fraction length of the sine table values always equals the word length minus one:
When you select Same word length as input, the word length of the sine table values match that of the input to the block.
When you select Binary point scaling, you can enter the word length of the sine table values, in bits.
When you select Slope and bias scaling, you can enter the word length of the sine table values, in bits.
The sine table values do not obey the Rounding mode and Overflow mode parameters; they are always saturated and rounded to Nearest.
Use this parameter to specify how to designate the product output word and fraction lengths. Refer to Fixed-Point Data Types and Multiplication Data Types in the Signal Processing Blockset documentation for illustrations depicting the use of the product output data type in this block:
When you select Inherit via internal rule, the product output word length and fraction length are automatically set according to the following equations:
ideal product output word length = output word length + sine table values word length
ideal product output fraction length = output fraction length + sine table values fraction length
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and the fraction length of the product output, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the product output. The bias of all signals in the Video and Image Processing Blockset software is 0.
Use this parameter to specify how to designate the accumulator word and fraction lengths. Refer to Fixed-Point Data Types and Multiplication Data Types in the Signal Processing Blockset documentation for illustrations depicting the use of the accumulator data type in this block:
When you select Inherit via internal rule, the accumulator word length and fraction length are automatically set according to the following equations:
ideal accumulator word length = product output word length + 1
ideal accumulator fraction length = product output fraction length
When you select Same as product output, these characteristics match those of the product output.
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and the fraction length of the accumulator, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the accumulator. The bias of all signals in the Video and Image Processing Blockset software is 0.
Choose how to specify the output word length and fraction length:
When you select Inherit via internal rule, the output word length and fraction length are automatically set according to the following equations, where the input matrix is M-by-N:
If M>1 and N>1, output word length = input word length + floor(log 2((M-1)(N-1)))+1
If M>1 and N=1, output word length = input word length + floor(log 2(M-1))+1
If M=1 and N>1, output word length = input word length + floor(log 2(N-1))+1
output fraction length = input fraction length
When you select Same as input, these characteristics match those of the input to the block.
When you select Binary point scaling, you can enter the word length and the fraction length of the output, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the output. The bias of all signals in the Video and Image Processing Blockset software is 0.
Video and Image Processing Blockset software | |
Video and Image Processing Blockset software | |
Video and Image Processing Blockset software | |
Signal Processing Blockset software | |
Signal Processing Blockset software | |
Signal Processing Blockset software | |
Signal Processing Toolbox software | |
MATLAB | |
MATLAB |
 | 2-D DCT | 2-D FIR Filter |  |
Learn more about Simulink through this collection of videos, articles, technical literature and the Getting Started with Simulink Guide.
| © 1984-2009- The MathWorks, Inc. - Site Help - Patents - Trademarks - Privacy Policy - Preventing Piracy - RSS |
