Prev: Quality Assessment
Next: how to get continuous images display using web cam
From: Lei on 5 Apr 2010 09:42
I grabbed a bit-reversal algorithm from the Internet and re-programmed it into an Matlab Mex-file. Amazingly, when I test its function, problems occurs when the input data is a set of random complex number(the number of input data should be power of 2).

Here I attach the C source code of this algorithm, it should be compiled into an Mex-file in matlab.
In the matlab command window, type:
mex -setup %select the compiler

After that, type,
mex bitrev.c

After compiling, using the following test commands(M-file):
clear
data = rand(1,8)+1i*rand(1,8);
%data = [0:7].*complex(1,1); If data is like this, the result is CORRECT!
data2 =bitrevorder(data)
b = bitrev(data)

Comparing with the output of the matlab built-in function, bitrevorder, the output "b" is not corresponding to "data2" (But they should be the same)
Is there anyone who can address the problem? I will be very grateful for the help.

Here I attach the C source code "bitrev.c" of the bit-reverse algorithm:
#include "mex.h"
#include <math.h>
void mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[])
{
int f,g, m, n, n1, n2,t1,t2, p;
double *ar,*ai, *br,*bi;

if (!mxIsComplex(prhs[0])) {mexErrMsgTxt("Input data must be complex number.");}
mexPrintf("This algorithm has a problem when dealing with random complex numbers.\n");



m = mxGetM(prhs[0]); //Find the dimensions of the data
n = mxGetN(prhs[0]);

ar = mxGetPr(prhs[0]); // Retrieve the input data
ai = mxGetPi(prhs[0]);

plhs[0] = mxCreateDoubleMatrix(m, n, mxCOMPLEX); // Create an mxArray for the output data

br = mxGetPr(plhs[0]); // Create a pointer to the output data
bi = mxGetPi(plhs[0]);

g = 0; //bit-reverse
n2 = n/2;
for (f=1; f < n - 1; f++)
{
n1 = n2;
while ( g >= n1 )
{
g = g - n1;
n1 = n1/2;
}
g = g + n1;
if (f < g)
{
t1 = ar[f];
ar[f] = ar[g];
ar[g] = t1;
t2 = ai[f];
ai[f] = ai[g];
ai[g] = t2;
}
}


for (p = 0; p < m*n; p++) /* Put data in the output array */
{
br[p] = ar[p];
bi[p] = ai[p];
}
}
From: Roger Stafford on 5 Apr 2010 23:13
"Lei " <mikej.edu(a)gmail.com> wrote in message <hpcpbp$i3l$1(a)fred.mathworks.com>...
> .......
> After compiling, using the following test commands(M-file):
> clear
> data = rand(1,8)+1i*rand(1,8);
> %data = [0:7].*complex(1,1); If data is like this, the result is CORRECT!
> data2 =bitrevorder(data)
> b = bitrev(data)
>
> Comparing with the output of the matlab built-in function, bitrevorder, the output "b" is not corresponding to "data2" (But they should be the same)
> Is there anyone who can address the problem? I will be very grateful for the help.
> .........
------------------------
What are the actual rearrangement results with bitrev on complex vectors? In your example which worked with [0:7].*complex(1,1), the real and imaginary parts were equal. Does it also work if this is a column vector? When the real and imaginary components are unequal, how is each separate component rearranged? Does one of them do the correct bit-reversal? Is the other one unchanged? Is one a copy of the other? Are some values lost? Information of this kind provides important clues as to where the trouble lies. How about showing us an example of one of your eight-element random complex vectors both before and after a call to bitrev?

The n-element bit reversal algorithm itself using f and g pointers looks correct to me. However I see that apparently bitrev does not handle a two-dimensional array properly. Only the first n elements of data(:) would be bit-reversed. Just n elements of the ar and ai inputs are bit-reversed, whereas m*n of them are transferring into the br and bi outputs. Did you intend it to function only for vectors?

Roger Stafford
From: Roger Stafford on 6 Apr 2010 09:52
"Lei " <mikej.edu(a)gmail.com> wrote in message <hpcpbp$i3l$1(a)fred.mathworks.com>...
> .......
> void mexFunction(int nlhs, mxArray *plhs[],
> int nrhs, const mxArray *prhs[])
> ........
> ar = mxGetPr(prhs[0]); // Retrieve the input data
> ai = mxGetPi(prhs[0]);
> ........
> t1 = ar[f];
> ar[f] = ar[g];
> ar[g] = t1;
> t2 = ai[f];
> ai[f] = ai[g];
> ai[g] = t2;
> .......

It has occurred to me that your bitrev troubles may possibly derive from the fact that you have altered the input values ar and ai rather than the outputs br and bi in the swapping that occurs in the bit reversal procedure. You wrote:

t1 = ar[f];
ar[f] = ar[g];
ar[g] = t1;
t2 = ai[f];
ai[f] = ai[g];
ai[g] = t2;

and I believe that violates the declaration "const mxArray *prhs[]". Here is what Mathworks' MEX-files Guide has to say about doing that: "The variables prhs and plhs are not mxArrays. They are arrays of pointers to mxArrays. So if a function is given three inputs, prhs will be an array of three pointers to the mxArrays that contain the data passed in. The variable prhs is declared as const. This means that the values that are passed into the MEX-file should not be altered. Doing so can cause segmentation violations in MATLAB. The values in plhs are invalid when the MEX-file begins. The mxArrays they point to must be explicitly created before they are used. Compilers will not catch this issue, but it will cause incorrect results or segmentation violations."

Also it seems to me you should be doing the above swapping on an array of pointers internal to bitrev so that it will involve only a single n-element bit reversal process. Then these pointers can be used to rearrange both the real and imaginary parts of each row of a two-dimensional input array without any further bit-reversal manipulation.

Roger Stafford
 | 
Pages: 1
Prev: Quality Assessment
Next: how to get continuous images display using web cam