FPGA Intellectual Property
PCI Express*, Networking and Connectivity, Memory Interfaces, DSP IP, and Video IP
6343 Discussions

Digit Reverse Order issue for INTEL FFT IP core

User1582192733150209
1,567 Views

Hello Sir/Madam,

I am simulating the intel FFT IP core, and seems the index of non-natural order FFT output  is not fully match the index digi reverse calculation.

 

Quartus prime pro 17.1

Modelsim-intel  starter 10.5c

Windows 10 pro

Arria10gx

 

What I have done

1, create a Quartus project and install a Intel FFT IP core

2, Choose to generate the testbench when setting up the FFT IP core 

3,start modelsm and compile vendor/user library using automatic generated msim_setup.tcl

4,use matlab2019b to generate IEEE754 format  data source, 32bits single precision floating.

5,In testbench coding to load above data source into FFT input

6, simulation and observe FFT output

 

with above simulation flow ,I have done 2 simulation case, the difference is output order, one is natural order, another one is digit reverse. I will explain it one by one.

 

case 1

FFT configuration is as below

Length:256

Direction: forward

Data flow: variable streaming

Input order: Natural

Output order: Natural

Representation: single floating point

 

natral_ip.JPG

 

below is simulation , seems every signals are correct, and we can find 2 spike
at the output stream, one is at index 4, another one is at index 252.

natral_ip_sim.JPG

because I use x = 10 * cos(2*pi*4*t) to generate data source in matlab2019b, so the above simulation result meet the my understanding, ie at 4hz(index 4) and symmetric location 252(index252) have 2 spike signals.
below is part of the m file used to generate signal source.
fs=256;N=256;
n=0:N-1;t=n/fs;
x = 10 * cos(2*pi*4*t);
y=fft(single(x),N);
mag=abs(y);
f=n*fs/N;
subplot(2,2,1),plot(x); %signal source
xlabel('time domain');
ylabel('Amptitude');title('Signal Source input N=256');grid on;
subplot(2,2,2),plot(f,mag);
xlabel('Frequency Domain/Hz');
ylabel('Amptitude');title('Direct FFT N=256');grid on;
realInput = real(x);
imagInput = imag(x);
realOutput = real(y);
imagOutput = imag(y);
realOutput_s =single(real(y));
imagOutput_s =single(imag(y));
for i = 1 : N
fprintf(f1,'%s\n',float2bin(single(realInput(i)))); % writing bin format sine_input_data_r.txt
fprintf(f1i,'%s\n',float2bin(single(imagInput(i)))); % writing bin format sine_input_data_i.txt
end

 

below is details about 2 location at index 4 and index 252

natral_ip_sim_detial.jpg

case 1 simulation meet my expectation.

 

case 2

the reason I test case 2 because when I was repeating input data source, need to keep a big IPG to avoid timing issue,you can check my SR https://community.intel.com/t5/FPGA-Intellectual-Property/Intel-FFT-IP-core-timing-issue/m-p/1190502#M21698 .

but that big IPG reduce the fft processing bandwidth, that is why I change to digit reverse to avoid timing issue, but seems I got another issue.

 case2 FFT configuration is as below

Length:256

Direction: forward

Data flow: variable streaming

Input order: Natural

Output order: Digit reverse

Representation: single floating point

 digit_reverse_ip.JPG

 

based on the understanding for digit reverse option, the output index should be digit reverse for natural 8 bit index . 

because these 2 case have same data source, so we can expect same result with different output order .

for example

the spike at index 4(00000100) in case 1,  in case 2  should be at index 32(00100000) , however I did find this spike ,but location is at 16(00010000) ,this is not match the address reverse calculation, this is my key question.

another spike at index 252(11111100) in case1,  in case 2   should be at index 63(00111111) ,I did find this spike in case and location is matched.no issue for this one.

 

let's check the simulation as below

digit_reverse_ip_sim.JPG

digit_reverse_ip_sim_detial.jpg

 

I attached my 2 projects here for further analysis ,so you can duplicate my issue.

1,unzip my project,you can put it into the d:  , this is my original location 

2,start modelsim

3, you might need edit the quartus path in msim_setup.tcl ,my quartus is located H:/intelfpga_pro/17.1/quartus/

4,goto D:\fftipsimulation\tfft\sim\mentor

source initial_setup.tcl

5,do run.do

6, if you need to control input data source only once

change multi_cycle=1'b0     in D:\fftipsimulation\tfft\sim\tfft_tb.v

7, you will see the issue I mentioned

 

thanks

 

Jim

0 Kudos
12 Replies
User1582192733150209
1,550 Views

Any update?

 

below is the MATLAB plot for FFT verification . 

left top cornet one is for signal source

right  top cornet one is for direct FFT using matlab itself

with this we can expect 2 spike at index 4 and index 252.

the spike I mentioned is amplitude 1280.

 

thanks

 

Jim 

0 Kudos
CheePin_C_Intel
Employee
1,544 Views

Hi Jim,


Thanks for your detailed elaboration of your issue observation. As I understand it, you have some inquiries related to the digit reverse of the FFT IP output. Please allow me some time to digest the information and to perform replication for further debugging. I will provide you an update on the progress by end of next week or as soon as there is any valid finding. Please ping me if you do not hear back from me. Thank you.


0 Kudos
User1582192733150209
1,530 Views

Hi CheePin,

 

Thanks for your time and effort.

Best regard

 

Jim

 

0 Kudos
CheePin_C_Intel
Employee
1,524 Views

Hi,


For your information, as I tested running simple example design from Q17.0 std with bi-directional, length = 8 and fixed point, I can get the correct digit reverse order when comparing between the digit reverse and natural output test cases. Would you mind to try with dummy design + fixed point to see if can get the right index? To help us narrow down if this only occurs in floating point data format.


In the meantime, I will try to customize the example design to take in your data to see if can replicate any anomaly.


Thank you.


0 Kudos
CheePin_C_Intel
Employee
1,524 Views

Hi Jim,


For your information, I have found out why after digit reversal, your expected data is appearing at index 16 instead of 32. With your FFT configuration, the Radix-4 digit reversal is implied but not Radix-2. You can refer to System Messages at the bottom of your FFT configuration screenshot for the Radix-4 implied.


In your case, the spike is originally at index 4 (Radix-4 = 0010), after digit reversal, it become 0100 which is equivalent to digit-reversed index of 16 which tally with your simulation. As for the other spike at index 252, the digit-reversed index = 63 which tally with your simulation as well. Hope this explain.


Please let me know if there is any concern. Thank you.


Best regards,

Chee Pin



0 Kudos
User1582192733150209
1,523 Views

Hi Chee pin,

 

thanks for your effort.

 

I am not quite understand it.

Can you suggest how can I turn the digit reversed result back into natural order output using my 8 bits index? because I plan to turn result into natural order result in FPGA and forward it to next stream for further usage.

my current logic is 

assign digi_reverse_index[fft_result_address_width-1:0] ={result_index[0], result_index[1], result_index[2], result_index[3],
result_index[4], result_index[5], result_index[6], result_index[7]};

integer i;
always @(posedge clk or negedge reset_n)
begin
if(!reset_n)
  begin
  for (i = 0; i < data_num-1; i = i + 1) begin
       fft_digireverse_result_r[i] <= 32'd0;
      fft_digireverse_result_i[i] <= 32'd0;
  end
end
else if(source_valid) begin
  fft_digireverse_result_r[digi_reverse_index] <=source_real ;
  fft_digireverse_result_i[digi_reverse_index] <=source_imag ;
end
end

thanks

Jim

 

 

0 Kudos
User1582192733150209
1,521 Views

I put form here to summary up, I am not sure with the same data source how can I use digit reverse output to figure out the target frequency .

 

excel.JPG

0 Kudos
CheePin_C_Intel
Employee
1,506 Views

Hi,


Sorry for the delay. Sorry as I am not very familiar with HDL design to implement the digit reverse. However, you can refer to the following mapping table for Radix-4 digit reverse for your 256 data to see if it is helpful.


 Original, Digitrev Radix-4  


   0   0

   1   64

   2  128

   3  192

   4   16

   5   80

   6  144

   7  208

   8   32

   9   96

   10  160

   11  224

   12   48

   13  112

   14  176

   15  240

   16   4

   17   68

   18  132

   19  196

   20   20

   21   84

   22  148

   23  212

   24   36

   25  100

   26  164

   27  228

   28   52

   29  116

   30  180

   31  244

   32   8

   33   72

   34  136

   35  200

   36   24

   37   88

   38  152

   39  216

   40   40

   41  104

   42  168

   43  232

   44   56

   45  120

   46  184

   47  248

   48   12

   49   76

   50  140

   51  204

   52   28

   53   92

   54  156

   55  220

   56   44

   57  108

   58  172

   59  236

   60   60

   61  124

   62  188

   63  252

   64   1

   65   65

   66  129

   67  193

   68   17

   69   81

   70  145

   71  209

   72   33

   73   97

   74  161

   75  225

   76   49

   77  113

   78  177

   79  241

   80   5

   81   69

   82  133

   83  197

   84   21

   85   85

   86  149

   87  213

   88   37

   89  101

   90  165

   91  229

   92   53

   93  117

   94  181

   95  245

   96   9

   97   73

   98  137

   99  201

  100   25

  101   89

  102  153

  103  217

  104   41

  105  105

  106  169

  107  233

  108   57

  109  121

  110  185

  111  249

  112   13

  113   77

  114  141

  115  205

  116   29

  117   93

  118  157

  119  221

  120   45

  121  109

  122  173

  123  237

  124   61

  125  125

  126  189

  127  253

  128   2

  129   66

  130  130

  131  194

  132   18

  133   82

  134  146

  135  210

  136   34

  137   98

  138  162

  139  226

  140   50

  141  114

  142  178

  143  242

  144   6

  145   70

  146  134

  147  198

  148   22

  149   86

  150  150

  151  214

  152   38

  153  102

  154  166

  155  230

  156   54

  157  118

  158  182

  159  246

  160   10

  161   74

  162  138

  163  202

  164   26

  165   90

  166  154

  167  218

  168   42

  169  106

  170  170

  171  234

  172   58

  173  122

  174  186

  175  250

  176   14

  177   78

  178  142

  179  206

  180   30

  181   94

  182  158

  183  222

  184   46

  185  110

  186  174

  187  238

  188   62

  189  126

  190  190

  191  254

  192   3

  193   67

  194  131

  195  195

  196   19

  197   83

  198  147

  199  211

  200   35

  201   99

  202  163

  203  227

  204   51

  205  115

  206  179

  207  243

  208   7

  209   71

  210  135

  211  199

  212   23

  213   87

  214  151

  215  215

  216   39

  217  103

  218  167

  219  231

  220   55

  221  119

  222  183

  223  247

  224   11

  225   75

  226  139

  227  203

  228   27

  229   91

  230  155

  231  219

  232   43

  233  107

  234  171

  235  235

  236   59

  237  123

  238  187

  239  251

  240   15

  241   79

  242  143

  243  207

  244   31

  245   95

  246  159

  247  223

  248   47

  249  111

  250  175

  251  239

  252   63

  253  127

  254  191

  255  255


0 Kudos
User1582192733150209
1,505 Views

Hi CheePin,

 

Thanks for your explanation.

I think I got a bit understanding about digit reverse now .

for radix-4 ,floating representation data,below translation from digit reverse order to natural order index is verified for my case.

 Let's call the digit reversed index(non-natural order) as dr_index[7..0] 8 bits, then we call a natural order index na_index[7..0] ,below is my summary how to convert it

translation.JPG

For my case, let verify it for the first spike at index 4  

translation4.JPG

from above conversion ,index 4(8'b 00000100) will turn to index 16(8'b 00010000, ie index 4 turn to index 16 under digit reverse calculation,that matches the simulation result.

another spike, which presents at index 252(8'b 11111100) , should be at location index 63(8'b 00111111) under digit reverse order output. 

translation252.JPG

that matches the simulation result too.

 

hope this summary can help more people to understand this index conversion.

In verilog ,can use below 

assign na_index[7:0] ={dr_index[1], dr_index[0],
                                          dr_index[3], dr_index[2],
                                          dr_index[5], dr_index[4],
                                          dr_index[7], dr_index[6] };

thanks

Jim

CheePin_C_Intel
Employee
1,470 Views

Hi Jim,


Thanks lot for your sharing.


I believe the initial inquiry has been addressed. This thread will be transitioned to community support. If you have a new question, feel free to open a new thread to get the support from Intel experts. Otherwise, the community users will continue to help you on this thread. Thank you.


User1582192733150209
1,452 Views

Hi CheePin,

yes ,please help to close this service request,  and my initial question has been addressed , thank you very much.

 

Jim

0 Kudos
Reply